Struct SpectralAuditor 

pub struct SpectralAuditor {
    pub n_probes: usize,
    pub threshold: f64,
}

Generates random probe vectors and compares Laplacian quadratic forms between the full graph and its sparsifier.

Fields

n_probes: usize

Number of random probes per audit.

threshold: f64

Acceptable relative error threshold.

Implementations

impl SpectralAuditor

pub fn new(n_probes: usize, threshold: f64) -> Self

Create a new auditor.

pub fn audit_quadratic_form( &self, g_full: &SparseGraph, g_spec: &SparseGraph, n_probes: usize, ) -> AuditResult

Audit by comparing x^T L_full x vs x^T L_spec x for random x.

Each probe vector has i.i.d. standard-normal entries. The relative error for each probe is |full - spec| / max(full, tiny).

pub fn audit_cuts( &self, g_full: &SparseGraph, g_spec: &SparseGraph, n_cuts: usize, ) -> AuditResult

Audit by comparing random cut values.

Generates n_cuts random binary partitions and checks that the cut weight in the sparsifier is within (1 +/- threshold) of the full graph cut weight.

pub fn audit_conductance( &self, g_full: &SparseGraph, g_spec: &SparseGraph, k_clusters: usize, ) -> AuditResult

Audit via random cluster conductance estimation.

Generates k_clusters random cluster indicator vectors and checks spectral consistency.

Trait Implementations

impl Clone for SpectralAuditor

fn clone(&self) -> SpectralAuditor

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl Debug for SpectralAuditor

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<'de> Deserialize<'de> for SpectralAuditor

fn deserialize<__D>(__deserializer: __D) -> Result<Self, __D::Error>

where __D: Deserializer<'de>,

Deserialize this value from the given Serde deserializer.

impl Serialize for SpectralAuditor

fn serialize<__S>(&self, __serializer: __S) -> Result<__S::Ok, __S::Error>

where __S: Serializer,

Serialize this value into the given Serde serializer.