Crate lapl 

lapl

Spectral methods: graph Laplacians, eigenmaps, spectral clustering.

The Core Idea

The graph Laplacian L = D - A encodes graph structure in a matrix whose eigenvalues and eigenvectors reveal connectivity, communities, and geometry.

Key Functions

Function	Purpose
[laplacian]	Unnormalized Laplacian L = D - A
normalized_laplacian	Symmetric L_sym = I - D^{-1/2} A D^{-1/2}
random_walk_laplacian	L_rw = I - D^{-1} A
[fiedler_vector]	Second eigenvector (graph bisection)
spectral_embedding	Low-dim representation from eigenvectors

Quick Start

use lapl::{adjacency_to_laplacian, normalized_laplacian, degree_matrix};
use ndarray::array;

// Simple graph: 0 -- 1 -- 2
let adj = array![
    [0.0, 1.0, 0.0],
    [1.0, 0.0, 1.0],
    [0.0, 1.0, 0.0]
];

let lap = adjacency_to_laplacian(&adj);
let lap_norm = normalized_laplacian(&adj);

Why Spectral Methods?

• Spectral clustering: k-means on Laplacian eigenvectors finds communities
• Dimensionality reduction: Laplacian eigenmaps preserve local structure
• Graph partitioning: Fiedler vector gives optimal 2-way cut
• Diffusion: Heat kernel e^{-tL} describes information spreading

The Laplacian Zoo

Unnormalized:   L = D - A
  - Simple, but eigenvalues scale with degree
  - Null space dimension = number of connected components

Normalized (symmetric):   L_sym = I - D^{-1/2} A D^{-1/2}
  - Eigenvalues in [0, 2]
  - Used for spectral clustering (Ng, Jordan, Weiss)

Random walk:   L_rw = I - D^{-1} A
  - Related to random walk transition matrix
  - Same eigenvalues as L_sym, different eigenvectors

The Fiedler Vector

The second smallest eigenvalue λ_2 (algebraic connectivity) measures how well-connected the graph is. Its eigenvector (Fiedler vector) gives an optimal graph bisection: partition by sign.

Spectral Clustering

1. Compute k smallest eigenvectors of L_sym (excluding constant)
2. Form n × k matrix U from eigenvectors as columns
3. Normalize rows of U
4. Run k-means on rows → cluster assignments

Connections

• rkhs: Gaussian kernel → similarity graph → Laplacian
• strata: Spectral clustering uses this crate
• rmt: Random graph Laplacians follow RMT eigenvalue distributions

What Can Go Wrong

1. Disconnected graph: Zero eigenvalue multiplicity = number of components.
2. Zero degree nodes: Normalized Laplacian undefined. Remove isolated nodes.
3. Numerical precision: Very small/large edge weights cause instability.
4. Eigendecomposition: this crate includes a pragmatic, dependency-free approximate spectral embedding (spectral_embedding) for dense graphs. For large graphs, you still want a sparse representation + a real eigensolver.
5. Scaling: O(n²) storage for dense adjacency. Use sparse formats for large graphs.

References

• Fiedler (1973). “Algebraic connectivity of graphs”
• Shi & Malik (2000). “Normalized cuts and image segmentation”
• Ng, Jordan, Weiss (2001). “On Spectral Clustering”
• von Luxburg (2007). “A Tutorial on Spectral Clustering”

Structs

SpectralEmbeddingConfig

Configuration for approximate spectral embedding.

Enums

Error

Functions

adjacency_to_laplacian

Unnormalized Laplacian: L = D - A

degree_matrix

Compute degree matrix D from adjacency matrix A.

degree_vector

Compute degree vector from adjacency matrix.

directed_laplacian

Directed Laplacian for reachability spectral embeddings.

epsilon_graph

Epsilon-neighborhood graph.

gaussian_similarity

Compute similarity matrix from points using Gaussian kernel.

is_connected

Number of connected components (approximation via Laplacian properties).

knn_graph

Compute k-nearest neighbor graph.

laplacian_quadratic_form

Compute Laplacian quadratic form: x^T L x

normalized_laplacian

Symmetric normalized Laplacian: L_sym = I - D^{-1/2} A D^{-1/2}

normalized_laplacian_checked

Symmetric normalized Laplacian, but rejects isolated nodes.

random_walk_laplacian

Random walk Laplacian: L_rw = I - D^{-1} A

spectral_embedding

Approximate spectral embedding: the k eigenvectors after the trivial constant one.

transition_matrix

Transition matrix: P = D^{-1} A

Type Aliases

Result