Adjacency-Matrix Preservation Test¶

Preservation audit — instantiates Neighborhood-Preserving Substrate Mapping

Checks that pairs which are neighbors in the source stay neighbors on the substrate by differencing the two adjacency matrices directly — reporting the exact pairs the map tore apart or falsely joined, not just a score.

Adjacency-Matrix Preservation Test takes the source neighborhood graph and the realized substrate neighborhood graph and compares them as adjacency matrices, entry by entry. Its defining move is that it reports not a single global fidelity number but the named list of violations: which source-neighbors ended up far apart on the substrate (tears) and which source-strangers ended up adjacent (false merges). Because it keeps the identity of every offending pair, a distortion can be localized to specific elements and either fixed or documented — the test answers "did this map keep these neighbors together?", with culprits attached, rather than handing back a score that hides where the damage is.

Example¶

A lab embeds 30,000 immune cells from high-dimensional expression space into a two-dimensional layout for browsing. The plot shows clean islands, but a reviewer suspects some are artifacts of the projection. The adjacency-matrix preservation test builds the k-nearest-neighbor graph in the original expression space and the k-NN graph in the 2-D layout, then differences the two matrices. It surfaces specifics: a group of regulatory T cells — genuine neighbors of helper T cells in expression space — was split to opposite corners of the plot (a tear), while two unrelated populations were rendered touching (a false merge). Those named violations, not the overall agreement percentage, are what tell the team the layout is fine for coarse browsing but must never be used to argue two populations are related merely because they sit next to each other. The picture looked trustworthy; the matrix diff showed exactly where it wasn't.

How it works¶

Fix a neighbor definition (k-NN, an ε-ball, or explicit edges) and apply it identically in both spaces. Form both adjacency matrices, then take their set difference per element: edges present in the source but missing on the substrate are tears; edges present on the substrate but absent in the source are false merges. Rank the violations by severity and report them as a list. The whole point is that it preserves which pairs failed — a scalar metric throws that away.

Tuning parameters¶

Neighborhood size (k or ε) — how many neighbors count as "near"; small k tests only the tightest locality, large k a looser one, and a map can pass at one and fail at another.
Violation direction — whether to penalize tears, false merges, or both; the two have different downstream costs and a map can be lopsided.
Edge weighting — binary adjacency versus distance-weighted, which catches near-misses a hard cutoff hides.
Severity ranking — how violations are ordered for triage (by distance blown, by element importance).
Pass threshold — how many violations are tolerated before the map is declared failing.

When it helps, and when it misleads¶

Its strength is localization: by naming the pairs, it turns "the projection might be lying" into a targeted fix or a precise caveat, and it is the honest check on a layout that merely looks well-clustered. Its limits are real. It is sensitive to the neighbor definition — the same map can pass at k=5 and fail at k=50, so the choice must be fixed in advance, not tuned until the map passes. It tests adjacency, not finer rank order or continuity — the graded question belongs to the Neighborhood Trustworthiness and Continuity Metric. And local adjacency can be perfectly preserved while the map is globally folded, which this test is blind to; that is the province of the Map Fold and Collision Scan and the Topographic Error Measure. The discipline that keeps it honest is to freeze the neighbor definition before running and report the violation list, not just the verdict.^[1]

How it implements the components¶

This is a measurement mechanism; it fills the neighbor-relation and adjacency-invariant components and nothing on the construction side:

source_neighborhood_relation — it reads and formalizes the source's own neighbor graph as one operand of the comparison.
adjacency_preservation_invariant — it operationalizes the invariant as a checkable matrix difference and reports each place the invariant is broken.

It does not compute the continuous, rank-based fidelity score — that is the Neighborhood Trustworthiness and Continuity Metric — and it does not detect global folds or collisions, which is the Map Fold and Collision Scan.

Instantiates: Neighborhood-Preserving Substrate Mapping — this test verifies the archetype's core adjacency-preservation promise on a specific map.
Sibling mechanisms: Neighborhood Trustworthiness and Continuity Metric · Topographic Error Measure · Map Fold and Collision Scan · Adaptive Remeshing and Reallocation · Boundary and Seam Regression Test · Calibration Anchor Stimuli · Canary Region Probe · Coverage-Hole Heatmap · Elastic-Net Embedding · Lateral-Interaction Smoothing · Local Ablation or Lesion Probe · Magnification Function · Map Registration and Alignment · Multidimensional Scaling Layout · Perturbation-Response Map · Receptive-Field Tiling Grid · Self-Organizing Map Training · Versioned Coordinate Atlas

References¶

[1] The co-ranking matrix framework (Lee & Verleysen, 2009) formalizes exactly this source-versus-embedding neighbor comparison and separates tears from false merges. Cited as the real conceptual anchor for adjacency-based preservation checking. ↩