# Spectral Clustering via Orthogonalization-Free Methods

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 7 of its 68 references that are in the map.
- First posted on arXiv 16 May 2023.

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

- [Compressive Spectral Clustering](https://mlsanity.com/paper/1602.02018/) (2016)
- [Spectral Clustering via the Power Method -- Provably](https://mlsanity.com/paper/1311.2854/) (2013)
- [Compressive spectral embedding: sidestepping the SVD](https://mlsanity.com/paper/1509.08360/) (2015)
- [Preconditioned Spectral Clustering for Stochastic Block Partition Streaming Graph Challenge](https://mlsanity.com/paper/1708.07481/) (2017)
- [Design, Generation, and Validation of Extreme Scale Power-Law Graphs](https://mlsanity.com/paper/1803.01281/) (2018)
- [A Distributed Block Chebyshev-Davidson Algorithm for Parallel Spectral Clustering](https://mlsanity.com/paper/2212.04443/) (2022)
- [Fast Eigenspace Approximation using Random Signals](https://mlsanity.com/paper/1611.00938/) (2016)

## Built on by (most cited first, 1 of 1)

- [Wormhole: Concept-Aware Deep Representation Learning for Co-Evolving Sequences](https://mlsanity.com/paper/2409.13857/) (2024)

## Abstract (arXiv)

While orthogonalization exists in current dimensionality reduction methods in spectral clustering on undirected graphs, it does not scale in parallel computing environments. We propose four orthogonalization-free methods for spectral clustering. Our methods optimize one of two objective functions with no spurious local minima. In theory, two methods converge to features isomorphic to the eigenvectors corresponding to the smallest eigenvalues of the symmetric normalized Laplacian. The other two converge to features isomorphic to weighted eigenvectors weighting by the square roots of eigenvalues. We provide numerical evidence on the synthetic graphs from the IEEE HPEC Graph Challenge to demonstrate the effectiveness of the orthogonalization-free methods. Numerical results on the streaming graphs show that the orthogonalization-free methods are competitive in the streaming graph scenario since they can take full advantage of the computed features of previous graphs and converge fast. Our methods are also more scalable in parallel computing environments because orthogonalization is unnecessary. Numerical results are provided to demonstrate the scalability of our methods. Consequently, our methods have advantages over other dimensionality reduction methods when handling spectral clustering for large streaming graphs.