Research map / Learning theory and algorithms / Clustering
Pass-Efficient Algorithms for Graph Spectral Clustering (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes pass-efficient randomized spectral clustering algorithms (T+1-pass and one-pass) that avoid full Laplacian eigendecomposition by using vertex-edge matrix structure and randomized eigendecomposition, scaling linearly in vertices and edges.
Problem
Classical spectral clustering requires cubic-time eigendecomposition of the graph Laplacian, which is infeasible for large graphs stored on slow memory.
Approach
Compute the k smallest Laplacian eigenpairs via randomized eigendecomposition of the shifted matrix 2I−L, expressed through the vertex-edge matrix so that each pass over the graph is cheap; a vertex-neighbor representation lets the algorithm run with T+1 passes and a one-pass variant avoids the Q-phase passes.
Key results
- Algorithm 3 is more than 15X faster than classical spectral clustering on graphs with 10^4 nodes.
- Algorithms 2 and 3 produce identical clusters at any given T; with T>=20 Algorithm 3 matches classical clustering results.
- Algorithm 3 identified cell clusters in a 200,000-cell dataset within five minutes (single-cell application, reported as future work).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the efficient vertex-neighbors implementation instead of classical spectral clustering | Algorithm 3 · Synthetic graphs with 10^4 nodes | speedup: more than 15X | Helped |
| Use Algorithm 3 for spectral clustering | Algorithm 3 · Synthetic graphs | clustering quality (NCut and ARI) | Helped |
| Increase T in the Q phase (ablation) | Algorithms 2 and 3 · Synthetic graphs | clustering quality (NCut and ARI) | Helped |
| Use the efficient vertex-neighbors implementation rather than Algorithm 2 (ablation) | Randomized T+1-pass spectral clustering · Synthetic graphs | runtime | Helped |
| Replace the T+1-pass W phase with the one-pass W computation (ablation) | One-pass variants of Algorithms 2 and 3 · Synthetic graphs | clustering quality | Hurt |
| Use Algorithm 3 for clustering instead of Leiden | Single-cell clustering · Single-cell dataset, 200,000 cells | runtime | No clear effect |
| Use Algorithm 3 instead of Leiden | Single-cell clustering · Single-cell data | identification of small distinct clusters | Helped |
Surprising findings
- Classical and other algorithms failed to produce results beyond 10^4 nodes in the experiments.
Limitations
- Algorithm 2 assumes access to the full vertex-edge matrix, which is not available in practice.
- Accuracy of Algorithm 3 requires T>=20 passes to match classical clustering on the tested data.
- Experiments are limited to synthetic graphs; single-cell application is only preliminary.
Experimental setup
Datasets: synthetic graphs with known cluster assignments
Benchmarks: synthetic graphs with known clusters
Metrics: approximation error (Frobenius norm) NCut ARI runtime (s)
Baselines: classical spectral clustering (Ng et al. 2001) Leiden algorithm
Builds on: Halko et al. randomized eigendecomposition Ng-Jordan-Weiss spectral clustering Von Luxburg spectral clustering tutorial
Closest papers by meaning
- Fast and Simple Spectral Clustering in Theory and Practice (NeurIPS 2023 · similarity 0.94)
- A Tighter Analysis of Spectral Clustering, and Beyond (ICML 2022 · similarity 0.93)
- Structure-Aware Spectral Sparsification via Uniform Edge Sampling (NeurIPS 2025 · similarity 0.91)
- Dynamic Spectral Clustering with Provable Approximation Guarantee (ICML 2024 · similarity 0.89)
- Equivalence between Graph Spectral Clustering and Column Subset Selection (Student Abstract) (AAAI 2024 · similarity 0.89)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 2025 · similarity 0.89)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.