Graph Laplacians and Spectral Clustering¶

The module graph provides graph Laplacian operators and a spectral clustering algorithm built on a Jacobi diagonaliser.

Laplacians¶

For a weighted undirected graph with adjacency matrix \(W \in \mathbb{R}^{n\times n}_{\ge 0}\) and degree matrix \(D = \mathrm{diag}(W \mathbf{1})\):

Combinatorial: \(L = D - W\).
Symmetric normalised: \(L_{\mathrm{sym}} = I - D^{-1/2} W D^{-1/2}\).
Random-walk normalised: \(L_{\mathrm{rw}} = I - D^{-1} W\).

Each operator is positive semidefinite and the multiplicity of the zero eigenvalue equals the number of connected components.

Spectral Clustering¶

Given \(W\) and a target number of clusters \(k\):

Build \(L_{\mathrm{sym}}\) (or another Laplacian).
Diagonalise via cyclic Jacobi rotations to obtain the eigenpairs \((\lambda_i, u_i)\).
Stack the \(k\) eigenvectors associated with the smallest eigenvalues as columns of \(U \in \mathbb{R}^{n \times k}\).
Normalise rows of \(U\) and run Lloyd’s algorithm with k-means++ initialisation on the rows.

The Fiedler eigenvalue \(\lambda_2\) is reported separately as a proxy for the spectral gap.

API¶

pub enum LaplacianKind { Combinatorial, SymmetricNormalised, RandomWalk }
pub fn combinatorial_laplacian(w: ArrayView2<f64>) -> Result<Array2<f64>>;
pub fn normalised_laplacian(w: ArrayView2<f64>) -> Result<Array2<f64>>;
pub fn random_walk_laplacian(w: ArrayView2<f64>) -> Result<Array2<f64>>;

pub struct SpectralClusterResult {
    pub labels: Vec<usize>,
    pub eigenvalues: Vec<f64>,
    pub fiedler_value: f64,
}
pub fn spectral_cluster(w: ArrayView2<f64>, k: usize, n_kmeans_iter: usize, seed: u64)
    -> Result<SpectralClusterResult>;