Crate ruvector_sparsifier 

ruvector-sparsifier

Dynamic spectral graph sparsification for the RuVector ecosystem.

This crate maintains a small weighted shadow graph H (the sparsifier) that preserves the Laplacian energy of a full graph G within a factor of (1 +/- epsilon). It follows the ADKKP16 approach adapted for practical real-time use:

1. Backbone: a spanning forest guaranteeing global connectivity.
2. Importance scoring: random-walk-based effective-resistance estimation.
3. Spectral sampling: edges kept proportional to w * R_eff * log(n) / eps^2.
4. Periodic audits: random quadratic-form probes detect drift.

Quick start

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

// 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(),
);

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

Re-exports

pub use audit::SpectralAuditor;

pub use backbone::Backbone;

pub use error::Result;

pub use error::SparsifierError;

pub use graph::SparseGraph;

pub use importance::EffectiveResistanceEstimator;

pub use importance::LocalImportanceScorer;

pub use sampler::SpectralSampler;

pub use sparsifier::AdaptiveGeoSpar;

pub use traits::BackboneStrategy;

pub use traits::ImportanceScorer;

pub use traits::Sparsifier;

pub use types::AuditResult;

pub use types::EdgeImportance;

pub use types::SparsifierConfig;

pub use types::SparsifierStats;

Modules

audit

Spectral audit system for verifying sparsifier quality.

backbone

Backbone (spanning forest) maintenance via union-find.

error

Error types for the spectral graph sparsifier.

graph

Sparse weighted graph with dynamic edge operations.

importance

Edge importance scoring via random walks.

prelude

Prelude for convenient imports.

sampler

Edge sampling proportional to importance scores.

sparsifier

Main adaptive spectral sparsifier (AdaptiveGeoSpar).

traits

Trait definitions for the sparsifier framework.

types

Core types for spectral graph sparsification.

Constants

NAME

Crate name.

VERSION

Crate version.