53 lines
1.9 KiB
ReStructuredText
53 lines
1.9 KiB
ReStructuredText
|
Graph Laplacians and Spectral Clustering
|
||
|
|
========================================
|
||
|
|
|
||
|
|
The module :code:`graph` provides graph Laplacian operators and a
|
||
|
|
spectral clustering algorithm built on a Jacobi diagonaliser.
|
||
|
|
|
||
|
|
Laplacians
|
||
|
|
----------
|
||
|
|
|
||
|
|
For a weighted undirected graph with adjacency matrix :math:`W \in \mathbb{R}^{n\times n}_{\ge 0}`
|
||
|
|
and degree matrix :math:`D = \mathrm{diag}(W \mathbf{1})`:
|
||
|
|
|
||
|
|
- **Combinatorial**: :math:`L = D - W`.
|
||
|
|
- **Symmetric normalised**: :math:`L_{\mathrm{sym}} = I - D^{-1/2} W D^{-1/2}`.
|
||
|
|
- **Random-walk normalised**: :math:`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 :math:`W` and a target number of clusters :math:`k`:
|
||
|
|
|
||
|
|
1. Build :math:`L_{\mathrm{sym}}` (or another Laplacian).
|
||
|
|
2. Diagonalise via cyclic Jacobi rotations to obtain the eigenpairs
|
||
|
|
:math:`(\lambda_i, u_i)`.
|
||
|
|
3. Stack the :math:`k` eigenvectors associated with the smallest
|
||
|
|
eigenvalues as columns of :math:`U \in \mathbb{R}^{n \times k}`.
|
||
|
|
4. Normalise rows of :math:`U` and run Lloyd's algorithm with
|
||
|
|
k-means++ initialisation on the rows.
|
||
|
|
|
||
|
|
The Fiedler eigenvalue :math:`\lambda_2` is reported separately as a
|
||
|
|
proxy for the spectral gap.
|
||
|
|
|
||
|
|
API
|
||
|
|
---
|
||
|
|
|
||
|
|
.. code-block:: rust
|
||
|
|
|
||
|
|
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>;
|