Skip to content

spatial_graph_algorithms.spatial_coherence

Score whether graph topology has a low-dimensional Euclidean distance spectrum.

Use this when you want a topology-only check of whether a graph still behaves like a low-dimensional spatial proximity graph. It is especially useful for comparing clean versus noisy graphs, denoising outputs, or experimental edge lists before reconstruction.

Usage

from spatial_graph_algorithms.simulate import generate
from spatial_graph_algorithms.spatial_coherence import score

sg = generate(n=500, mode="knn", k=8, seed=42)
result = score(sg, dim=2)

print(result["spectral_score"])
print(result["spectral_gap"])
print(result["negative_eigenvalue_ratio"])

# Optional: include all positive eigenvalue contributions instead of the
# first five.
full = score(sg, dim=2, n_eigenvalues="all")

The default score uses all-pairs shortest-path distances from the graph topology. Ground-truth positions are not required.

To create the diagnostic plot:

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

Metric interpretation

Metric Meaning
spectral_score Fraction of leading positive Gram-matrix eigenvalue mass explained by the expected dimension. Higher means stronger low-dimensional concentration.
eigenvalue_contribution_by_rank Dictionary with one scalar per returned eigenvalue, e.g. eigenvalue_1_contribution.
spectral_gap Relative drop from eigenvalue dim to dim + 1. Higher means a clearer cutoff at the expected dimension.
mean_dim_gap_score Relative drop from the mean contribution of the first dim eigenvalues to eigenvalue dim + 1.
negative_eigenvalue_ratio Absolute negative eigenvalue mass divided by positive mass. Lower means the shortest-path distances are closer to Euclidean.

cumulative_variance_dim is kept as a compatibility alias for spectral_score.

Example

Open examples/spatial_coherence_false_edges.ipynb for an interactive clean-vs-noisy walkthrough that writes comparison plots under .planning/artifacts/examples/spatial_coherence_false_edges/.

API Reference

spatial_graph_algorithms.spatial_coherence.score(sg, *, dim=2, n_eigenvalues=5, plot=False, output_dir=None)

Compute the exact Gram-matrix spectral coherence score from graph topology.

The graph adjacency is converted to all-pairs shortest-path distances. Squared distances are double-centered into a classical MDS Gram matrix, whose eigenvalue spectrum measures how strongly the topology concentrates in a low-dimensional Euclidean structure.

When to use: graphs up to ~2 000 nodes, or any time an exact and comparable result is needed. Runtime is O(n²) memory and O(n³) compute.

Parameters:

Name Type Description Default
sg SpatialGraph

Input graph. Only :attr:~spatial_graph_algorithms.network.SpatialGraph.adjacency_matrix is used.

 required
dim int

Expected spatial dimension. Default is 2.

 2
n_eigenvalues int or 'all'

Number of leading positive eigenvalue contributions to return. Must be at least dim + 1 when an integer is given. Pass "all" to return contributions for every positive eigenvalue. Default is 5.

 5
plot bool

If True, write a diagnostic eigenvalue contribution plot. Default is False.

 False
output_dir str or Path

Directory for diagnostic plots. Required when plot=True.

 None

Returns:

Type Description
dict

Keys: n_nodes, dim, n_eigenvalues, n_positive_eigenvalues, spectral_score, cumulative_variance_dim, spectral_gap, mean_dim_gap_score, negative_eigenvalue_ratio, eigenvalue_contributions, eigenvalue_contribution_by_rank, spectrum (DataFrame).

Raises:

Type Description
ValueError

If parameters are invalid, the graph has no finite pairwise distances, or too few positive eigenvalues exist to compute the requested score.

Examples:

>>> from spatial_graph_algorithms.simulate import generate
>>> from spatial_graph_algorithms.spatial_coherence import score
>>> sg = generate(n=80, mode="knn", k=6, seed=0)
>>> result = score(sg, dim=2)
>>> 0.0 <= result["spectral_score"] <= 1.0
True
Source code in src/spatial_graph_algorithms/spatial_coherence/__init__.py 
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
def score(
    sg: SpatialGraph,
    *,
    dim: int = 2,
    n_eigenvalues: int | str = 5,
    plot: bool = False,
    output_dir: str | Path | None = None,
) -> dict:
    """Compute the exact Gram-matrix spectral coherence score from graph topology.

    The graph adjacency is converted to all-pairs shortest-path distances.
    Squared distances are double-centered into a classical MDS Gram matrix,
    whose eigenvalue spectrum measures how strongly the topology concentrates
    in a low-dimensional Euclidean structure.

    **When to use:** graphs up to ~2 000 nodes, or any time an exact and
    comparable result is needed.  Runtime is O(n²) memory and O(n³) compute.

    Parameters
    ----------
    sg : SpatialGraph
        Input graph. Only :attr:`~spatial_graph_algorithms.network.SpatialGraph.adjacency_matrix`
        is used.
    dim : int
        Expected spatial dimension. Default is 2.
    n_eigenvalues : int or "all"
        Number of leading positive eigenvalue contributions to return.
        Must be at least ``dim + 1`` when an integer is given. Pass ``"all"``
        to return contributions for every positive eigenvalue. Default is 5.
    plot : bool
        If ``True``, write a diagnostic eigenvalue contribution plot.
        Default is ``False``.
    output_dir : str or Path, optional
        Directory for diagnostic plots. Required when ``plot=True``.

    Returns
    -------
    dict
        Keys: ``n_nodes``, ``dim``, ``n_eigenvalues``, ``n_positive_eigenvalues``,
        ``spectral_score``, ``cumulative_variance_dim``, ``spectral_gap``,
        ``mean_dim_gap_score``, ``negative_eigenvalue_ratio``,
        ``eigenvalue_contributions``, ``eigenvalue_contribution_by_rank``,
        ``spectrum`` (DataFrame).

    Raises
    ------
    ValueError
        If parameters are invalid, the graph has no finite pairwise distances,
        or too few positive eigenvalues exist to compute the requested score.

    Examples
    --------
    >>> from spatial_graph_algorithms.simulate import generate
    >>> from spatial_graph_algorithms.spatial_coherence import score
    >>> sg = generate(n=80, mode="knn", k=6, seed=0)
    >>> result = score(sg, dim=2)
    >>> 0.0 <= result["spectral_score"] <= 1.0
    True
    """
    _validate_score_inputs(dim=dim, n_eigenvalues=n_eigenvalues, plot=plot, output_dir=output_dir)

    distances = _shortest_path_distances(sg)
    eigenvalues = _gram_eigenvalues(distances)
    metrics = _spectral_metrics_from_eigenvalues(eigenvalues, dim=dim, n_eigenvalues=n_eigenvalues)

    result = {
        "n_nodes": int(sg.adjacency_matrix.shape[0]),
        "dim": int(dim),
        "n_eigenvalues": n_eigenvalues,
        **metrics,
    }

    if plot:
        result["plot_path"] = str(
            _plot_eigenvalue_contributions(
                spectrum=metrics["spectrum"],
                dim=dim,
                spectral_gap=metrics["spectral_gap"],
                output_dir=Path(output_dir),
            )
        )

    return result