spectral-graph-v2

The refined spectral graph engine.

A zero-dependency Rust library for measuring structural coherence in graphs using spectral analysis. Compute the conservation ratio, find critical nodes, grow teams along Fibonacci lines, and learn from failure.

[dependencies]
spectral-graph-v2 = "0.2"

The Conservation Ratio

The central idea: CR = λ₂ / λ_max.

Given the Laplacian matrix of a graph, λ₂ (the algebraic connectivity / Fiedler value) and λ_max (the largest eigenvalue) form a ratio that captures how coherent the structure is.

CR	Meaning
≈ 0	Graph is nearly disconnected — fragile, bottlenecked
≈ 1	Graph is dense and uniform — resilient but expensive
0.3–0.7	Sweet spot: structured but not rigid

CR works because it's scale-invariant. A 10-node path and a 1000-node path have similar CR profiles. You can compare graphs of different sizes directly.

What's New in v2

v1 computed CR and called it a day. v2 does something with it.

Fibonacci Module

Teams grow by adding nodes that push CR toward 1/φ ≈ 0.618. Not because Fibonacci is magical — because it's the unique ratio where adding a node changes the structure without breaking it. Teams that converge here are neither too sparse nor too dense.

use spectral_graph_v2::{Graph, fibonacci};

let mut g = Graph::new();
// ... add some nodes and edges ...
let next = fibonacci::next_addition(&g);
// next is the node (or new node) whose addition moves CR toward 1/φ

Adaptive Module

Static thresholds are brittle. The adaptive module tracks CR over time and drifts thresholds based on what the ecosystem is doing.

use spectral_graph_v2::adaptive;

let config = adaptive::Config::new()
    .window(50)          // look at last 50 CR values
    .drift_rate(0.02)    // how fast thresholds can move
    .lower_bound(0.15);  // never drop below this

let monitor = adaptive::Monitor::new(config);
let should_alert = monitor.observe(current_cr);

NegativeSpace

Records failure patterns — edges that were tried and didn't help, configurations that degraded CR — and avoids repeating them. Think of it as a learned set of anti-patterns.

use spectral_graph_v2::NegativeSpace;

let mut ns = NegativeSpace::new();

// Record a failure: "adding edge (3,7) made CR worse"
ns.record_failure(3, 7, "cr_degraded");

// Later, when considering additions:
let candidates = vec![(1, 4), (3, 7), (5, 8)];
let safe: Vec<_> = candidates.into_iter()
    .filter(|(a, b)| !ns.is_known_failure(*a, *b))
    .collect();
// (3, 7) is filtered out — we've been there before

Perturbation

Gradient ascent toward higher CR. For each possible edge addition, compute the projected change in CR and pick the best one.

use spectral_graph_v2::perturbation;

let g = /* your graph */;
let best_edge = perturbation::optimal_addition(&g);
// best_edge is the (u, v) pair that maximizes ΔCR

node_criticality

Which nodes are load-bearing? Remove each node, recompute CR, rank by impact.

use spectral_graph_v2::criticality;

let rankings = criticality::node_criticality(&g);
// rankings[0] is the node whose removal drops CR the most

Full Example: Build a Graph, Compute CR

use spectral_graph_v2::{Graph, Laplacian, cr};

let mut g = Graph::new();
g.add_node(0);
g.add_node(1);
g.add_node(2);
g.add_node(3);

g.add_edge(0, 1);
g.add_edge(1, 2);
g.add_edge(2, 3);
g.add_edge(3, 0);
g.add_edge(0, 2);

let lap = Laplacian::from_graph(&g);
let ratio = cr::conservation_ratio(&lap);

println!("CR = {:.6}", ratio);
// CR ≈ 0.4 — a small, moderately connected graph

The Math: Why CR Works

The Laplacian L = D - A (degree matrix minus adjacency) has eigenvalues 0 = λ₁ ≤ λ₂ ≤ ... ≤ λₙ.

• λ₂ (Fiedler value) measures connectivity. Zero iff the graph is disconnected.
• λ_max measures how much total degree variation exists.
• CR = λ₂ / λ_max normalizes connectivity against the scale of the graph.

Properties:

• Scale-invariant: Adding isolated nodes doesn't change CR much (both numerator and denominator shift).
• Monotone under edge addition: Adding an edge can only increase CR (up to the limit of the complete graph).
• Interpretable: CR = 1 iff the graph is regular and connected.

When CR Doesn't Work

• Ising-type models: CR doesn't capture phase transitions well. A graph at critical temperature has the same CR as one far from it.
• Cospectral graphs: Different graphs can have identical spectra. CR can't distinguish them. If you need uniqueness, use additional structural features.
• Directed graphs: The Laplacian spectral theory for directed graphs is weaker. CR is defined but less meaningful.

Performance

• Zero dependencies. No nalgebra, no ndarray. All eigenvalue computation is hand-rolled.
• Jacobi eigenvalue algorithm with convergence to 1e-14 (machine epsilon for f64).
• O(n³) per eigenvalue computation — fine for graphs up to a few hundred nodes. For larger graphs, use power iteration or Lanczos (not yet implemented).
• All operations are deterministic. Same graph, same CR, every time.

Repository

github.com/SuperInstance/spectral-graph-v2

License

MIT

Part of the SuperInstance OpenConstruct ecosystem.