Skip to content

Module: spatial_coherence

File: src/spatial_graph_algorithms/spatial_coherence/__init__.py
Status: Initial implementation — Gram-matrix spectral score.

Purpose

Assess whether graph topology behaves like distances sampled from a low-dimensional spatial structure. The v1 implementation scores the all-pairs shortest-path distance matrix by converting it to a classical MDS Gram matrix and summarising its eigenvalue spectrum.

This is useful as a topology-only sanity check before reconstruction. A well-behaved 2-D proximity graph should put most positive Gram-matrix eigenvalue mass in the first two eigenvalues and have a clear drop after dimension 2. Random shortcut or false edges tend to flatten the spectrum, lower spectral_score, and increase negative eigenvalue mass.

This module is canonical. spatial_graph_algorithms.coherence.score remains as a backward-compatible alias.

Public API

from spatial_graph_algorithms.spatial_coherence import score

result = score(sg, dim=2)
# {
#   "spectral_score": 0.91,
#   "spectral_gap": 0.72,
#   "negative_eigenvalue_ratio": 0.04,
#   "eigenvalue_contribution_by_rank": {...},
#   "spectrum": pandas.DataFrame(...),
# }

score() uses graph topology by default; ground-truth positions are not required. It returns the first five positive eigenvalue contributions by default; pass n_eigenvalues="all" to include every positive eigenvalue.

The most compact scalar is spectral_score. It is the cumulative variance contribution through the expected dimension. For a 2-D graph, it is the combined contribution of the first two positive Gram-matrix eigenvalues.

eigenvalue_contribution_by_rank keeps the individual values:

{
    "eigenvalue_1_contribution": 0.50,
    "eigenvalue_2_contribution": 0.42,
    "eigenvalue_3_contribution": 0.04,
    ...
}

Use plot=True to write a diagnostic bar/line plot:

result = score(sg, dim=2, plot=True, output_dir="results/spatial_coherence")
print(result["plot_path"])

Method

  1. Compute all-pairs shortest-path distances with scipy.sparse.csgraph.shortest_path.
  2. Replace infinite distances from disconnected components with 2 × max_finite_distance.
  3. Convert squared distances to a double-centered Gram matrix.
  4. Compute descending eigenvalues.
  5. Report leading positive eigenvalue contributions, spectral_score at the expected dimension, spectral gap, and negative eigenvalue mass.

Planned Follow-Ups

  • Spatial constant estimation by BFS subgraph growth.
  • Dimension prediction from neighbourhood growth curves.
  • Optional comparison against Euclidean distances when ground-truth positions are available.

Example

Open examples/spatial_coherence_false_edges.ipynb for an interactive walkthrough. It compares a clean n=1000, delaunay_corrected graph against the same setup with 5% false edges, prints scalar scores, per-eigenvalue contributions, and writes plots under .planning/artifacts/examples/spatial_coherence_false_edges/.