Conservation Tomography

Inverse Spectral Graph Reconstruction from Conservation Signatures

The Problem

Given only conservation measurements (eigenvalue spectrum + conservation ratios), reconstruct the transition graph that produced them.

This is an inverse problem:

• Forward: graph → Laplacian → eigenvalues → conservation
• Inverse: conservation → eigenvalues → Laplacian → graph

Core Algorithm: Iterative Spectral Matching

1. Initialize random graph G₀ on n nodes
2. Compute its Laplacian L(G₀), eigenvalues λ, conservation ratios CR
3. Compare to target eigenvalues λ* and target conservation CR*
4. Compute gradient: ∂λ_k/∂w_uv = -(φ_k)_u · (φ_k)_v  (eigenvalue perturbation)
5. Update edge weights: w_uv ← w_uv - α × Σ_k (∂λ_k/∂w_uv) × (λ_k - λ*_k)
6. Repeat until convergence

Results

Experiment 1: Perfect Information (all eigenvalues)

Metric	Value
Eigenvalue RMSE	0.001587
Edge correlation	0.9959
Edge accuracy	0.8222
Relative Frobenius	0.0772

Experiment 2: Partial Information

k eigenvalues	Edge Corr	Edge Acc	Eigen RMSE
3	-0.12	0.33	3.318
5	-0.38	0.36	2.747
7	-0.28	0.38	3.000
10	0.996	0.822	0.002

Experiment 3: Noisy Information

Noise σ	Edge Corr	Edge Acc	Eigen RMSE
0.00	0.996	0.822	0.002
0.01	0.996	0.778	0.009
0.05	0.996	0.733	0.038
0.10	0.995	0.733	0.076
0.20	0.993	0.667	0.150
0.50	0.982	0.622	0.354

Experiment 4: Wrong n

Assumed n	Overlap RMSE	Notes
8	0.000025	Underestimate OK
9	0.000023	Underestimate OK
10	0.003733	Correct
11	1.278	Overestimate: catastrophic
12	1.787	Overestimate: catastrophic

Key Findings

1. Eigenvalue reconstruction is excellent with all eigenvalues: RMSE < 0.002
2. Edge weight correlation reaches 0.996 when eigenvector initialization + multiple restarts are used
3. All eigenvalues needed for structural recovery — partial info gives cospectral ambiguity
4. Noise degrades gracefully — edge correlation stays >0.98 even at σ=0.5
5. Underestimating n is safe; overestimating is catastrophic

Files

• tomography.py — Core ConservationTomography class with forward/inverse
• experiments.py — All four experiments + plotting
• plot_data.npz — Saved numpy data for external visualization

Usage

from tomography import ConservationTomography, TensionGraph, forward_model

# Create a known graph
graph = TensionGraph.random_weighted(10, edge_density=0.3, seed=42)

# Forward: graph → eigenvalues + conservation
fwd, attrs = forward_model(graph)

# Inverse: eigenvalues + conservation → reconstructed graph
ct = ConservationTomography(10)
result = ct.inverse(
    target_eigenvalues=fwd.eigenvalues,
    target_conservation=fwd.conservation_ratios,
    target_eigenvectors=fwd.eigenvectors,
    attributes=attrs,
    n_iter=1000,
    n_restarts=5,
)

# Check quality
metrics = ct.reconstruction_error(result.reconstructed_graph, graph)
print(f"Edge correlation: {metrics['edge_correlation']:.4f}")

Theory

See docs/INVERSE-CONSERVATION-PROBLEM.md for the full theoretical treatment.

The key mathematical insight is the eigenvalue perturbation formula:

∂λ_k/∂w_uv = -(φ_k)_u · (φ_k)_v

This provides a locally efficient gradient for adjusting edge weights to match a target spectrum.

Part of the SuperInstance OpenConstruct ecosystem.