ruvector_sparsifier/
types.rs

1//! Core types for spectral graph sparsification.
2//!
3//! This module defines the configuration, scoring, audit, and statistics
4//! types used throughout the crate. The main graph type [`SparseGraph`] lives
5//! in the [`graph`](crate::graph) module.
6
7use serde::{Deserialize, Serialize};
8
9// ---------------------------------------------------------------------------
10// Configuration
11// ---------------------------------------------------------------------------
12
13/// Configuration for the adaptive spectral sparsifier.
14///
15/// Controls approximation quality (`epsilon`), memory budget, audit frequency,
16/// and random-walk parameters.
17///
18/// # Defaults
19///
20/// | Parameter          | Default   | Notes                            |
21/// |--------------------|-----------|----------------------------------|
22/// | `epsilon`          | 0.2       | (1 +/- eps) spectral guarantee   |
23/// | `edge_budget_factor`| 8        | budget = factor * n              |
24/// | `audit_interval`   | 1000      | updates between audits           |
25/// | `walk_length`      | 6         | random-walk hops for importance  |
26/// | `num_walks`        | 10        | walks per edge for scoring       |
27/// | `n_audit_probes`   | 30        | random vectors per audit         |
28#[derive(Debug, Clone, Serialize, Deserialize)]
29pub struct SparsifierConfig {
30    /// Spectral approximation factor in `(0, 1)`.
31    ///
32    /// Smaller values yield a more faithful sparsifier but require more
33    /// edges. A value of 0.2 means the Laplacian quadratic form is
34    /// preserved within a factor of `(1 +/- 0.2)`.
35    pub epsilon: f64,
36
37    /// Edge budget expressed as a multiple of `n` (number of vertices).
38    ///
39    /// The sparsifier will target at most `edge_budget_factor * n` edges.
40    /// Typical values range from 4 (aggressive) to 12 (conservative).
41    pub edge_budget_factor: usize,
42
43    /// Number of dynamic updates between automatic spectral audits.
44    pub audit_interval: usize,
45
46    /// Maximum number of hops in importance random walks.
47    pub walk_length: usize,
48
49    /// Number of random walks per edge for importance estimation.
50    pub num_walks: usize,
51
52    /// Number of random probe vectors used in spectral audits.
53    pub n_audit_probes: usize,
54
55    /// Whether to automatically trigger a rebuild when an audit fails.
56    pub auto_rebuild_on_audit_failure: bool,
57
58    /// Fraction of the graph to rebuild during a local rebuild (0..1].
59    pub local_rebuild_fraction: f64,
60}
61
62impl Default for SparsifierConfig {
63    fn default() -> Self {
64        Self {
65            epsilon: 0.2,
66            edge_budget_factor: 8,
67            audit_interval: 1000,
68            walk_length: 6,
69            num_walks: 10,
70            n_audit_probes: 30,
71            auto_rebuild_on_audit_failure: true,
72            local_rebuild_fraction: 0.1,
73        }
74    }
75}
76
77// ---------------------------------------------------------------------------
78// Edge importance
79// ---------------------------------------------------------------------------
80
81/// Importance score for a single edge combining effective resistance and
82/// weight information.
83///
84/// The importance `score` is proportional to `weight * effective_resistance`
85/// and determines the sampling probability during sparsification.
86#[derive(Debug, Clone, Copy, Serialize, Deserialize)]
87pub struct EdgeImportance {
88    /// Source vertex.
89    pub u: usize,
90    /// Target vertex.
91    pub v: usize,
92    /// Edge weight in the original graph.
93    pub weight: f64,
94    /// Estimated effective resistance between `u` and `v`.
95    pub effective_resistance: f64,
96    /// Combined importance score = `weight * effective_resistance`.
97    pub score: f64,
98}
99
100impl EdgeImportance {
101    /// Create a new importance score.
102    pub fn new(u: usize, v: usize, weight: f64, effective_resistance: f64) -> Self {
103        let score = weight * effective_resistance;
104        Self {
105            u,
106            v,
107            weight,
108            effective_resistance,
109            score,
110        }
111    }
112}
113
114// ---------------------------------------------------------------------------
115// Audit result
116// ---------------------------------------------------------------------------
117
118/// Result of a spectral audit comparing the sparsifier against the full graph.
119///
120/// An audit samples random vectors `x` and compares `x^T L_full x` against
121/// `x^T L_spec x`. The sparsifier passes when all relative errors stay
122/// within `epsilon`.
123#[derive(Debug, Clone, Serialize, Deserialize)]
124pub struct AuditResult {
125    /// Maximum relative error observed across all probe vectors.
126    pub max_error: f64,
127    /// Average relative error across all probe vectors.
128    pub avg_error: f64,
129    /// Whether the audit passed (max_error <= epsilon).
130    pub passed: bool,
131    /// Number of probe vectors used.
132    pub n_probes: usize,
133    /// The epsilon threshold used for pass/fail.
134    pub threshold: f64,
135}
136
137impl AuditResult {
138    /// Create a passing audit result with zero error.
139    pub fn trivial_pass(threshold: f64) -> Self {
140        Self {
141            max_error: 0.0,
142            avg_error: 0.0,
143            passed: true,
144            n_probes: 0,
145            threshold,
146        }
147    }
148}
149
150// ---------------------------------------------------------------------------
151// Statistics
152// ---------------------------------------------------------------------------
153
154/// Runtime statistics for the sparsifier.
155#[derive(Debug, Clone, Default, Serialize, Deserialize)]
156pub struct SparsifierStats {
157    /// Number of edges in the current sparsifier.
158    pub edge_count: usize,
159    /// Number of edges in the full graph.
160    pub full_edge_count: usize,
161    /// Number of vertices.
162    pub vertex_count: usize,
163    /// Compression ratio: `full_edge_count / edge_count`.
164    pub compression_ratio: f64,
165    /// Total number of edge insertions processed.
166    pub insertions: u64,
167    /// Total number of edge deletions processed.
168    pub deletions: u64,
169    /// Total number of spectral audits performed.
170    pub audit_count: u64,
171    /// Number of audits that passed.
172    pub audit_pass_count: u64,
173    /// Number of local rebuilds triggered.
174    pub local_rebuilds: u64,
175    /// Number of full rebuilds triggered.
176    pub full_rebuilds: u64,
177    /// Updates since the last audit.
178    pub updates_since_audit: u64,
179}
180
181impl SparsifierStats {
182    /// Recompute the compression ratio from current edge counts.
183    pub fn refresh_ratio(&mut self) {
184        if self.edge_count > 0 {
185            self.compression_ratio = self.full_edge_count as f64 / self.edge_count as f64;
186        } else {
187            self.compression_ratio = 0.0;
188        }
189    }
190}
ruvector_sparsifier/types.rs

ruvector_sparsifier/
types.rs
