Skip to content

README.md

Latest commit

 

History

History
287 lines (211 loc) · 8.37 KB

README.md

File metadata and controls

287 lines (211 loc) · 8.37 KB

RuVector Sparsifier

Crates.io Documentation License GitHub ruv.io

An always-on compressed world model for real-time graph analytics.

Dynamic spectral sparsification for HNSW health monitoring, structural diagnostics, and continuous graph reasoning.

Why This Matters

Every vector database, similarity index, and memory graph is backed by a dense web of connections. Analyzing the full graph is expensive — often too expensive for real-time use. RuVector Sparsifier maintains a small shadow graph that provably preserves the spectral structure of your full graph, enabling:

  • Continuous monitoring instead of batch analysis
  • 3-10x faster graph diagnostics (min-cut, clustering, Laplacian solves)
  • 10-50x less memory for analytics workloads
  • Early anomaly detection via structural drift monitoring

The Key Insight

If dynamic min-cut is your fragility alarm, spectral sparsification is your always-on compressed world model. Together they give your system a small graph it can think with continuously.

full graph = everything you know
sparse graph = what you need to think quickly

How It Works

A spectral sparsifier H of graph G has O(n log n / ε²) edges and preserves the Laplacian quadratic form within (1 ± ε):

(1-ε) · xᵀ L_G x  ≤  xᵀ L_H x  ≤  (1+ε) · xᵀ L_G x    ∀x ∈ Rⁿ

This means H preserves all spectral properties — cuts, connectivity, conductance, effective resistances, mixing times — within relative error ε.

Architecture

Full Graph (ground truth)
    │
    ├─ Backbone (spanning forest → connectivity guarantee)
    ├─ Importance scoring (random walk effective resistance)
    ├─ Spectral sampling (edges kept ∝ weight × importance × log n / ε²)
    └─ Periodic audits (random probe verification)
    │
    ▼
Sparsifier (compressed world model)

Implementation

Based on the ADKKP16 approach (Abraham, Durfee, Koutis, Krinninger, Peng — FOCS 2016) adapted for practical real-time use:

Component What It Does Complexity
Backbone Union-find spanning forest O(α(n)) per update
Importance Random walk effective resistance O(walk_length × num_walks)
Sampler Probability-proportional edge sampling O(m) for full, O(1) incremental
Audit Laplacian quadratic form comparison O(n × n_probes)

Quick Start

use ruvector_sparsifier::{AdaptiveGeoSpar, SparseGraph, SparsifierConfig};

// Build a graph.
let g = SparseGraph::from_edges(&[
    (0, 1, 1.0), (1, 2, 1.0), (2, 3, 1.0),
    (3, 0, 1.0), (0, 2, 0.5),
]);

// Construct the sparsifier.
let mut spar = AdaptiveGeoSpar::build(&g, SparsifierConfig::default()).unwrap();

// Dynamic updates.
spar.insert_edge(1, 3, 2.0).unwrap();
spar.delete_edge(0, 2).unwrap();

// Audit quality.
let audit = spar.audit();
println!("Audit passed: {}, max error: {:.4}", audit.passed, audit.max_error);

// Access the compressed graph.
let h = spar.sparsifier();
println!("Compression: {:.1}x ({} -> {} edges)",
    spar.compression_ratio(),
    spar.stats().full_edge_count,
    h.num_edges(),
);

Configuration

SparsifierConfig {
    epsilon: 0.2,                    // Spectral accuracy (lower = more edges)
    edge_budget_factor: 8,           // Target edges = factor × n
    audit_interval: 1000,            // Updates between audits
    walk_length: 6,                  // Random walk hops
    num_walks: 10,                   // Walks per edge
    n_audit_probes: 30,              // Probe vectors per audit
    auto_rebuild_on_audit_failure: true,
    local_rebuild_fraction: 0.1,
}
Parameter Range Effect
epsilon 0.05–0.5 Lower = more faithful, more edges
edge_budget_factor 4–12 Lower = more aggressive compression
audit_interval 100–10000 Lower = more frequent quality checks

Use Cases

1. HNSW Index Health Monitoring

// Monitor graph health via spectral properties of the sparsifier.
let spar = AdaptiveGeoSpar::build(&hnsw_graph, config)?;

// Cheap continuous monitoring on the sparsifier.
let audit = spar.audit();
if !audit.passed {
    // Trigger reindex or alert.
}

2. Faster Min-Cut on the Control Graph

// Run min-cut on the sparsifier (3-10x cheaper than full graph).
let cut_value_approx = compute_mincut(spar.sparsifier());

3. Real-Time Drift Detection

// Track structural drift by comparing audits over time.
let audit_t1 = spar.audit();
// ... updates happen ...
let audit_t2 = spar.audit();
if audit_t2.avg_error > 2.0 * audit_t1.avg_error {
    // Structural drift detected.
}

4. Embedding Point Moves

// Handle embedding updates (e.g., vector reindexing).
spar.update_embedding(
    node_id,
    &old_neighbors,  // [(neighbor, similarity_weight), ...]
    &new_neighbors,
)?;

5. Multi-Tier Memory

Hot tier:  Full HNSW graph  → exact retrieval
Warm tier: Sparsifier       → fast diagnostics, approximate analytics
Cold tier: Archived snapshots → historical trend analysis

Feature Flags

Flag Default Description
static-sparsify yes One-shot static sparsification
dynamic yes Dynamic insert/delete support
simd no SIMD-accelerated distance operations
wasm no WebAssembly-compatible paths
audit no Extended audit & diagnostics
full no All features enabled

Performance

Graph Size Full Edges Sparsifier Edges (ε=0.2) Build Time Audit Time
100 nodes 500 ~90 0.3 ms 0.05 ms
1K nodes 10K ~1.2K 15 ms 2 ms
10K nodes 150K ~14K 300 ms 30 ms
100K nodes 2M ~170K 8 s 500 ms

Benchmarks on x86_64 with cargo bench. Run cargo bench -p ruvector-sparsifier to reproduce.

Theoretical Background

Spectral Sparsification

A spectral sparsifier preserves the Laplacian quadratic form xᵀLx for all vectors x. This guarantees preservation of:

  • All cut values (within 1±ε)
  • Effective resistances between all vertex pairs
  • Spectral gap and mixing time
  • Conductance of all vertex subsets
  • Solutions to Laplacian systems Lx = b

Key References

Year Result Contribution
2008 Spielman-Srivastava Sparsification by effective resistances
2009 Batson-Spielman-Srivastava Optimal O(n/ε²) sparsifiers
2016 ADKKP (FOCS) First polylog dynamic maintenance
2025 Khanna-Li-Putterman (STOC) Dynamic hypergraph sparsification
2025 Zhao Dynamic directed graph sparsification
2026 Forster-Goranci-Momeni (STACS) Dynamic directed hypergraph sparsification

RuVector Ecosystem

ruvector-sparsifier ←→ ruvector-solver (Laplacian solves on sparsifier)
       ↕                      ↕
ruvector-coherence (spectral health scoring)
       ↕
ruvector-mincut (structural alarm on sparsifier)
       ↕
cognitum-gate-kernel (evidence accumulation)

WASM Support

See ruvector-sparsifier-wasm for WebAssembly bindings.

import { WasmSparsifier } from 'ruvector-sparsifier-wasm';

const spar = WasmSparsifier.buildFromEdges(
  '[[0,1,1.0],[1,2,1.0],[2,0,1.0]]',
  '{"epsilon":0.2}'
);

spar.insertEdge(0, 3, 2.0);
console.log(JSON.parse(spar.audit()));
console.log('Compression:', spar.compressionRatio(), 'x');

Acceptance Test

For any workload, compare side-by-side:

Metric Target
Structural error (Laplacian QF) ≤ 5%
Cut value error ≤ 5%
Speedup (graph analytics) ≥ 3x
Memory reduction ≥ 5x 
cargo test -p ruvector-sparsifier
cargo bench -p ruvector-sparsifier

License

MIT — see LICENSE for details.