# Stochastic Parallelizable Eigengap Dilation for Large Graph Clustering

arXiv: https://arxiv.org/abs/2207.14589 · HTML: https://mlsanity.com/paper/2207.14589/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 16 of its 37 references that are in the map.
- First posted on arXiv 29 Jul 2022.

## Builds on (most cited first, 16 of 16)

- [A Laplacian Framework for Option Discovery in Reinforcement Learning](https://mlsanity.com/paper/1703.00956/) (2017)
- [EigenGame: PCA as a Nash Equilibrium](https://mlsanity.com/paper/2010.00554/) (2020)
- [First Efficient Convergence for Streaming k-PCA: a Global, Gap-Free, and Near-Optimal Rate](https://mlsanity.com/paper/1607.07837/) (2016)
- [An Improved Gap-Dependency Analysis of the Noisy Power Method](https://mlsanity.com/paper/1602.07046/) (2016)
- [Spectral Clustering of Graphs with the Bethe Hessian](https://mlsanity.com/paper/1406.1880/) (2014)
- [A Stochastic PCA and SVD Algorithm with an Exponential Convergence Rate](https://mlsanity.com/paper/1409.2848/) (2014)
- [Faster Eigenvector Computation via Shift-and-Invert Preconditioning](https://mlsanity.com/paper/1605.08754/) (2016)
- [EigenGame Unloaded: When playing games is better than optimizing](https://mlsanity.com/paper/2102.04152/) (2021)
- [Compressive Spectral Clustering](https://mlsanity.com/paper/1602.02018/) (2016)
- [Exponentially convergent stochastic k-PCA without variance reduction](https://mlsanity.com/paper/1904.01750/) (2019)
- [Principal Component Projection Without Principal Component Analysis](https://mlsanity.com/paper/1602.06872/) (2016)
- [Distributed Stochastic Algorithms for High-rate Streaming Principal Component Analysis](https://mlsanity.com/paper/2001.01017/) (2020)
- [Efficient and Local Parallel Random Walks](https://mlsanity.com/paper/2112.00655/) (2021)
- [Preconditioning in Expectation](https://mlsanity.com/paper/1401.6236/) (2014)
- [An Efficient Parallel Algorithm for Spectral Sparsification of Laplacian and SDDM Matrix Polynomials](https://mlsanity.com/paper/1507.07497/) (2015)
- [Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications](https://mlsanity.com/paper/1810.02348/) (2018)

## Abstract (arXiv)

Large graphs commonly appear in social networks, knowledge graphs, recommender systems, life sciences, and decision making problems. Summarizing large graphs by their high level properties is helpful in solving problems in these settings. In spectral clustering, we aim to identify clusters of nodes where most edges fall within clusters and only few edges fall between clusters. This task is important for many downstream applications and exploratory analysis. A core step of spectral clustering is performing an eigendecomposition of the corresponding graph Laplacian matrix (or equivalently, a singular value decomposition, SVD, of the incidence matrix). The convergence of iterative singular value decomposition approaches depends on the eigengaps of the spectrum of the given matrix, i.e., the difference between consecutive eigenvalues. For a graph Laplacian corresponding to a well-clustered graph, the eigenvalues will be non-negative but very small (much less than 1) slowing convergence. This paper introduces a parallelizable approach to dilating the spectrum in order to accelerate SVD solvers and in turn, spectral clustering. This is accomplished via polynomial approximations to matrix operations that favorably transform the spectrum of a matrix without changing its eigenvectors. Experiments demonstrate that this approach significantly accelerates convergence, and we explain how this transformation can be parallelized and stochastically approximated to scale with available compute.