spatial_graph_algorithms — Handbook

A plain-English guide to what the package is, the problem it solves, and how it works end to end. This page is the source for the printable PDF (docs/spatial_graph_algorithms_handbook.pdf, built with python scripts/build_handbook_pdf.py). For runnable API details see the documentation site.

1. What this package is

spatial_graph_algorithms is a Python toolkit for analysing proximity graphs that come from sequencing-based spatial microscopy assays such as Slide-tags, Pixelgen, and related methods. In these experiments you do not directly observe where each molecule or cell sits in space. Instead you observe which entities are near each other, encoded as a graph: nodes are entities, edges connect neighbours.

The central scientific question is therefore: given only the connectivity, can we recover the underlying spatial layout — and how good is the recovery? The package answers this with one coherent workflow: load or simulate a graph, clean spurious edges, reconstruct coordinates, score the result, and produce plots or reports.

The whole library is organised around a single data object, SpatialGraph, that every step consumes and returns. There are no hidden global states and no black boxes that mutate data behind your back.

2. Installation in one minute

# Recommended: source checkout (most complete, up to date)
git clone https://github.com/DavidFernandezBonet/spatial-graph-algorithms
cd spatial-graph-algorithms
conda env create -f environment.yml
conda activate spatial-graph-algorithms

# Or a quick package install
pip install spatial_graph_algorithms

The base install covers simulation, MDS/STRND reconstruction, metrics, and plotting. Optional extras add Leiden community detection ([leiden]) and the GSE reconstructor ([gse]). Full dependency rationale is in requirements.md.

3. The data model: `SpatialGraph`

Everything flows through one dataclass. Understanding its fields is enough to understand the whole pipeline.

Field	Meaning	Set by
`adjacency_matrix`	Sparse connectivity (who is near whom)	`simulate.generate()` or your own loader
`positions`	Ground-truth coordinates `(n, dim)`, when known	`simulate.generate()`
`reconstructed_positions`	Coordinates recovered from topology	`reconstruct.reconstruct()`
`edge_metadata`	Per-edge table; includes an `is_false` flag in simulations	`simulate.generate()`
`node_metadata`	Per-node table; includes simulation parameters	`simulate.generate()`
`node_id_map`	Maps your original node IDs to `0..n-1`	`from_edge_list()`

Three invariants matter in practice:

The adjacency diagonal is always zero (no self-loops).
By default only the largest connected component is retained, so reconstruction and metrics operate on a graph where every node is reachable.
positions and adjacency_matrix always agree on node count.

SpatialGraph is never mutated in place by pipeline functions. Each step returns a new object, which is what makes pipelines easy to reason about and to test.

To bring in your own data, load_edge_list() turns a CSV path or a pandas DataFrame of edges into a SpatialGraph.

4. The pipeline at a glance

Point cloud ──► Edges ──► SpatialGraph ──► (denoise) ──► Reconstruct ──► Evaluate ──► Plot / Report
                              │
                       ground-truth positions (simulation only)

A minimal run:

from spatial_graph_algorithms.simulate import generate
from spatial_graph_algorithms.reconstruct import reconstruct
from spatial_graph_algorithms.metrics import evaluate

sg     = generate(n=500, mode="delaunay_corrected", false_edge_fraction=0.05, seed=42)
sg_rec = reconstruct(sg, method="strnd", dim=2, seed=42)
report = evaluate(sg_rec)

The modules obey a strict left-to-right import rule (simulate → reconstruct → metrics → plot → verify); nothing imports from a module further right. This keeps each stage independently testable.

5. The modules

simulate — controlled test graphs

Generates point clouds for a chosen shape, connects them into a proximity graph using one of several construction modes (k-nearest-neighbour, epsilon-ball, Delaunay and corrected variants, bipartite modes, and more), and can inject a controlled fraction of false edges to mimic experimental noise. Because the ground-truth positions are known, simulation is how the package measures reconstruction quality objectively.

denoise — remove spurious edges

Real proximity graphs contain edges that do not reflect true spatial adjacency. The denoise module scores each edge by how well the surrounding topology supports it and filters the weakest ones before reconstruction. Available strategies include betweenness, Jaccard overlap, community-based filtering, bipartite square-count support, and random-walk / edge-support scoring. A denoiser returns a SpatialGraph with fewer edges, the original positions untouched, and edge_metadata updated to mark what was removed.

reconstruct — recover coordinates

Takes the graph topology and produces reconstructed_positions. Several algorithms are available (see §6). All share a common contract: deterministic given a seed, they never mutate the input adjacency, they handle disconnected inputs gracefully, and they return an (n, dim) array.

metrics — score the result

evaluate() produces a unified report. With ground truth it reports CPD (global accuracy via Procrustes/correlation of pairwise distances), KNN (local neighbourhood preservation), and distortion; it also summarises graph structure (degree statistics, clustering, component sizes). graph_report() characterises a graph before reconstruction.

spatial_coherence — quality without ground truth

On real data there are no true coordinates to compare against. The spatial-coherence module scores whether the graph's topology still looks like it came from a low-dimensional space — for example via a Gram-matrix spectral score — letting you judge structure before and after reconstruction without labels.

plot — figures

Network plots in 2D and 3D, side-by-side comparison figures (ground truth vs reconstruction), degree histograms, and denoising diagnostics. Plot functions return Matplotlib Figure objects and never write files themselves. The module also includes export_to_blender() and headless_render() for publication-quality 3-D Cycles rendering via a standalone Blender installation (≥ 3.6); GPU is auto-detected. Use check_blender() to test availability before calling these functions.

verify — one-call pipeline

run_report() runs the full simulate → reconstruct → evaluate → plot pipeline from a VerifyConfig and writes CSV metrics plus PNG artefacts. This is the convenient entry point for reproducible, batch-style runs.

compare — systematic studies

Runs parameter-grid studies and the benchmark gym across graph conditions and reconstruction methods, producing the data behind the leaderboards (see §7).

6. Reconstruction methods

Method	Idea	Notes
MDS	Classical multidimensional scaling on graph shortest-path distances.	Strong baseline; disconnected gaps filled with `2 × max_finite`.
Landmark MDS	MDS anchored on a subset of landmark nodes.	Scales to larger graphs than full MDS.
STRND	Node2Vec biased random walks (via `pecanpy`) embedded with UMAP.	Captures non-linear structure; stochastic, so seed it.
GSE	Graph spatial embedding using approximate-nearest-neighbour and graph-partitioning backends.	Optional `[gse]` extra; suited to large/bipartite graphs.
Quantum Interferometry (QI)	Bipartite resolvent-response embedding.	Experimental; aimed at bipartite assays.

All methods are invoked the same way: reconstruct(sg, method="<name>", dim=2, seed=...).

7. Benchmark gym & leaderboards

The package ships a benchmark gym: a suite of datasets graded easy / mid / hard, against which every denoiser + reconstructor combination is run and scored. Results feed interactive and per-dataset leaderboards that answer two questions at a glance — which method combination wins on each dataset, and how much room is left to beat the current champion. The leaderboards are published with the docs site; see leaderboards.md for how to read and regenerate them.

This makes method comparison reproducible and honest: a new method earns its place by beating the recorded champion on shared data, not by anecdote.

8. End-to-end example

from spatial_graph_algorithms.simulate import generate
from spatial_graph_algorithms.reconstruct import reconstruct
from spatial_graph_algorithms.metrics import evaluate
from spatial_graph_algorithms.plot import plot_comparison

# 1. Make a noisy test graph with known ground truth
sg = generate(n=300, mode="delaunay_corrected", false_edge_fraction=0.05, seed=42)

# 2. Recover coordinates from topology alone
sg_rec = reconstruct(sg, method="strnd", dim=2, seed=42)

# 3. Score against ground truth
print(evaluate(sg_rec))          # CPD, KNN, distortion, structure summary

# 4. Visualise truth vs reconstruction
fig = plot_comparison(sg_rec)
fig.savefig("comparison.png", dpi=150, bbox_inches="tight")

To run on your own data, replace step 1 with load_edge_list("edges.csv") and skip the ground-truth metrics — use spatial_coherence instead.

9. Where to go next

Quickstart: quickstart.md — the same workflow with more explanation.
Architecture & import rules: Architecture.
Contributing / developer guide: contributing.md.
API reference: the api/ pages on the documentation site.
Examples: runnable notebooks in the examples/ directory.