How to Round Subspaces: A New Spectral Clustering Algorithm

Ali Kemal Sinop

TL;DR

This paper introduces a breakthrough algorithm for "rounding" the continuous subspaces produced by spectral relaxation into discrete clusters. By achieving an $O(\sqrt{OPT})$ approximation—a significant jump over previous $O(k \cdot OPT)$ bounds—the method recovers high-quality partitions even when clusters vary wildly in size or the data is "rotated" away from a perfect integral solution.

What Problem Does This Paper Address?

Spectral clustering is a staple of data science: you take a graph, compute the top (or bottom) $k$ eigenvectors of its Laplacian matrix, and use those to find clusters. However, there is a fundamental "rounding" gap.

The spectral relaxation provides a $k$-dimensional subspace, but because of rotational invariance, the basis of this subspace might look nothing like the "indicator vectors" (the 1s and 0s) of the actual clusters. If the clusters are well-separated, simple methods like $k$-means work. But if the clusters are of different sizes or the "noise" (the distance from a perfect partition) is high, traditional rounding fails. Specifically, previous algorithms couldn't find a partition closer than a factor of $k$ (the number of clusters) times the optimum error. This paper asks: can we find the true clusters even when they are hidden behind an arbitrary rotation and varying scales?

Methods

The author proposes a new iterative spectral clustering algorithm that moves away from the standard "cluster all at once" approach. Its key components include:

  • Iterative "Peeling": Instead of finding all $k$ clusters simultaneously, the algorithm finds one "core" cluster, refines it, and then projects the remaining data onto the orthogonal complement of that cluster's center. This prevents large, obvious clusters from "drowning out" smaller, subtler ones.
  • FINDCLUSTER & BOOST: A two-step refinement process. FINDCLUSTER identifies a coarse "core" of a cluster using singular value decomposition. BOOST then uses the top singular vector to refine this core into a high-precision estimate, preventing error accumulation across iterations.
  • UNRAVEL via Bipartite Matching: Because iterative steps might produce overlapping sets, the algorithm uses a bipartite matching formulation to "unravel" these estimates into a true disjoint partition.
  • Spectral Norm Focus: Unlike $k$-means, which minimizes the Frobenius norm (sum of squared distances), this algorithm minimizes the spectral norm. This is geometrically equivalent to finding a subspace that makes the minimum possible angle with the target subspace.

Datasets

This is a theoretical computer science paper focused on algorithmic proofs and complexity analysis. Consequently, no empirical datasets (like ImageNet or social network graphs) were used for evaluation. The "data" consists of mathematical constructs: $k$-dimensional linear subspaces of $\mathbb{R}^n$ and weighted undirected graphs used to prove approximation guarantees.

Key Insights and Ideas

  • The $k$-Factor Breakthrough: The most significant insight is that we can move from an error bound that scales linearly with the number of clusters ($k$) to one that scales with the square root of the optimum error ($O(\sqrt{OPT})$). This makes the algorithm much more robust for large-scale partitioning.
  • Size Doesn't Matter: Traditional spectral methods often struggle with "imbalanced" clusters. This algorithm's iterative projection (the "peeling" method) allows it to recover very small clusters that would normally be ignored as noise by global solvers.
  • Spectral Gap Relaxation: In graph theory, the "Cheeger Inequality" relates the expansion of a graph to its eigenvalues. This paper improves the requirement for finding the "sparsest $k$-partition." It shows that we can find good clusters as long as the expansion $\phi_k$ is smaller than the $(k+1)^{th}$ eigenvalue $\lambda_{k+1}$, removing a previous $1/k$ dependency.

Key Results

  • Subspace Rounding: The algorithm finds a $k$-partition whose indicator vectors span a subspace that is $O(\sqrt{OPT})$ close to the input subspace in spectral norm.
  • Graph Approximation: The paper demonstrates an application where a graph can be approximated as a disjoint union of "expanders" (well-connected subgraphs) in spectral norm.
  • Improved $k$-Expansion: For the $k$-way graph partitioning problem, the algorithm achieves a significant improvement in stability. It can recover the optimal partition even when the spectral gap is much narrower than previously required ($\phi_k \leq O(\lambda_{k+1})$ vs. the previous $\phi_k \leq O(\lambda_{k+1}/k)$).

Limitations and Future Work

  • Computational Complexity: While the algorithm is polynomial-time, the iterative nature involving SVDs, projections, and bipartite matching is computationally heavier than a simple $k$-means pass on eigenvectors.
  • Constant Optimization: The author notes that the analysis focuses on provable bounds rather than optimizing constants (e.g., one constant $c_0$ is simply bounded by 50). Practical implementations would likely need tuning.
  • General $k$-Expansion: While this provides a massive leap for graphs with a spectral gap, the general $k$-expansion problem (without a gap) remains one of the "holy grails" of approximation algorithms, with the best known factor still being $O(k^4)$ or $O(\sqrt{\log n \log k})$. This paper provides a "prerequisite" for solving that larger puzzle but does not close it entirely.

Summary updated

Abstract

A basic problem in spectral clustering is the following. If a solution obtained from the spectral relaxation is close to an integral solution, is it possible to find this integral solution even though they might be in completely different basis? In this paper, we propose a new spectral clustering algorithm. It can recover a $k$-partition such that the subspace corresponding to the span of its indicator vectors is $O(\sqrt{opt})$ close to the original subspace in spectral norm with $opt$ being the minimum possible ($opt \le 1$ always). Moreover our algorithm does not impose any restriction on the cluster sizes. Previously, no algorithm was known which could find a $k$-partition closer than $o(k \cdot opt)$. We present two applications for our algorithm. First one finds a disjoint union of bounded degree expanders which approximate a given graph in spectral norm. The second one is for approximating the sparsest $k$-partition in a graph where each cluster have expansion at most $\phi_k$ provided $\phi_k \le O(\lambda_{k+1})$ where $\lambda_{k+1}$ is the $(k+1)^{st}$ eigenvalue of Laplacian matrix. This significantly improves upon the previous algorithms, which required $\phi_k \le O(\lambda_{k+1}/k)$.
BibTeX
@inproceedings{sinop2016how,
  author = {Ali Kemal Sinop},
  title = {{How to Round Subspaces: A New Spectral Clustering Algorithm}},
  booktitle = {SODA},
  year = {2016},
  url = {https://openreview.net/forum?id=RUTAaYFDGVK},
}

Loading related content...

Figure