mirror of https://github.com/ruvnet/RuVector.git synced 2026-05-25 06:36:37 +00:00

History

rUv 1d60bf0a28 feat: add ruvector-sparsifier — dynamic spectral graph sparsification * feat: add ruvector-sparsifier crate — dynamic spectral graph sparsification Implements AdaptiveGeoSpar, a dynamic spectral sparsifier that maintains a compressed shadow graph preserving Laplacian energy within (1±ε). Core crate (ruvector-sparsifier): - SparseGraph with dynamic edge operations and Laplacian QF - Backbone spanning forest via union-find for connectivity - Random walk effective resistance estimation for importance scoring - Spectral sampling proportional to weight × importance × log(n)/ε² - SpectralAuditor with quadratic form, cut, and conductance probes - Pluggable traits: Sparsifier, ImportanceScorer, BackboneStrategy - 49 tests (31 unit + 17 integration + 1 doc-test), all passing - Benchmarks: build 161µs, insert 81µs, audit 39µs (n=100) WASM crate (ruvector-sparsifier-wasm): - Full wasm-bindgen bindings via WasmSparsifier and WasmSparseGraph - JSON-based API for browser/edge deployment - Compiles cleanly on native target Research (docs/research/spectral-sparsification/): - 00: Executive summary and impact projections - 01: SOTA survey (ADKKP 2016 → STACS 2026) - 02: Rust crate design and API - 03: RuVector integration architecture (4-tier control plane) - 04: Companion systems (conformal drift, attributed ANN) https://claude.ai/code/session_01A6YKtTrSPeV36Xamz9hRCb * perf: ultra optimizations across core distance, SIMD, and sparsifier hot paths Core distance.rs: - Manhattan distance now delegates to SIMD (was pure scalar) - Cosine fallback uses single-pass computation (was 3 separate passes) - Euclidean fallback uses 4x loop unrolling for better ILP SIMD intrinsics: - Add AVX2 manhattan distance (was only AVX-512 or scalar fallback) - 2x loop unrolling with dual accumulators for AVX2 manhattan - Sign-bit mask absolute value for branchless abs diff Sparsifier (O(m) -> O(1) per insert): - Cache total importance to avoid iterating ALL edges per insert - Parallel edge scoring via rayon for graphs >100 edges - Pre-sized HashMap adjacency lists (4 neighbors avg) - Inline annotations on hot-path graph query methods https://claude.ai/code/session_01A6YKtTrSPeV36Xamz9hRCb * fix: resolve clippy warnings in ruvector-sparsifier - Replace map_or(false, ...) with is_some_and(...) in graph.rs - Derive Default instead of manual impl for LocalImportanceScorer - Fix inner/outer attribute conflict on prelude module Co-Authored-By: claude-flow <ruv@ruv.net> --------- Co-authored-by: Claude <noreply@anthropic.com>		2026-03-20 10:37:39 -04:00
..
src	feat: add ruvector-sparsifier — dynamic spectral graph sparsification	2026-03-20 10:37:39 -04:00
Cargo.toml	feat: add ruvector-sparsifier — dynamic spectral graph sparsification	2026-03-20 10:37:39 -04:00
README.md	feat: add ruvector-sparsifier — dynamic spectral graph sparsification	2026-03-20 10:37:39 -04:00

README.md

RuVector Sparsifier WASM

WebAssembly bindings for dynamic spectral graph sparsification.

Enables browser-side and edge-deployed spectral sparsification with the same guarantees as the native Rust crate.

Quick Start

import init, { WasmSparsifier, default_config } from 'ruvector-sparsifier-wasm';

await init();

// Build from edges: [[u, v, weight], ...]
const spar = WasmSparsifier.buildFromEdges(
  '[[0,1,1.0],[1,2,1.0],[2,3,1.0],[3,0,1.0],[0,2,0.5]]',
  default_config()
);

// Dynamic updates
spar.insertEdge(1, 3, 2.0);
spar.deleteEdge(0, 2);

// Audit quality
const audit = JSON.parse(spar.audit());
console.log('Passed:', audit.passed, 'Max error:', audit.max_error);

// Stats
console.log('Compression:', spar.compressionRatio(), 'x');
console.log('Full edges:', spar.numEdges());
console.log('Sparse edges:', spar.sparsifierNumEdges());

API

`WasmSparsifier`

Method	Description
`new(config_json)`	Create empty sparsifier with config
`buildFromEdges(edges_json, config_json)`	Build from edge list
`insertEdge(u, v, weight)`	Insert edge
`deleteEdge(u, v)`	Delete edge
`updateEmbedding(node, old_json, new_json)`	Handle point move
`audit()`	Run spectral audit (JSON)
`sparsifierEdges()`	Get sparsifier edges (JSON)
`stats()`	Get statistics (JSON)
`compressionRatio()`	Compression ratio
`rebuildLocal(nodes_json)`	Rebuild around nodes
`rebuildFull()`	Full reconstruction

`WasmSparseGraph`

Method	Description
`new(n)`	Create graph with n vertices
`addEdge(u, v, weight)`	Add edge
`removeEdge(u, v)`	Remove edge
`degree(u)`	Vertex degree
`numEdges()`	Edge count
`toJson()`	Serialize to JSON

Helpers

Function	Description
`init()`	Initialize WASM module
`version()`	Crate version
`default_config()`	Default config JSON

Build

wasm-pack build crates/ruvector-sparsifier-wasm --target web

Memory

For a 10K-vertex graph: ~1.6 MB WASM linear memory (26 pages).

License

MIT