Abstract
Spectral clustering is a powerful technique for identifying complex, non-convex clusters, but it is hindered by high computational costs ($O(n^3)$) and the necessity of sensitive post-processing steps like k-means. This paper introduces Orthogonal and Nonnegative Graph Reconstruction (ONGR), a framework that addresses these limitations by reframing clustering as a graph reconstruction problem. By integrating nonnegativity and orthogonality constraints directly into the objective function, ONGR achieves linear scalability ($O(n)$) and produces interpretable cluster labels directly, eliminating the need for additional post-processing.
Introduction
Traditional spectral clustering faces two primary challenges: scalability and the "messy" transition from continuous eigenvectors to discrete cluster labels. The eigen-decomposition of a Laplacian matrix is computationally prohibitive for large-scale datasets. Furthermore, the standard practice of applying k-means to the resulting eigenvectors introduces initialization sensitivity that can undermine performance.
The proposed ONGR method seeks to overcome these "Achilles' heels" by learning a structured, block-diagonal matrix that reconstructs the similarity graph. This approach provides a "plug-and-play" solution for large-scale clustering tasks.
Methodology
ONGR views clustering as finding the optimal block-diagonal representation of a noisy similarity graph. The core of the method lies in its constraints:
- Nonnegative Constraints: By enforcing $G \ge 0$, the resulting label matrix becomes directly interpretable, where each row indicates cluster membership.
- Orthogonal Constraints: These ensure that learned features remain distinct and properly scaled, preserving the strengths of spectral methods.
- Anchor-based Graph Construction: To maintain linear complexity, ONGR utilizes a small set of representative "anchors" to build a sparse bipartite graph, avoiding the $O(n^2)$ cost of a full similarity matrix.
The optimization process uses an alternating algorithm with low-rank matrix operations, ensuring that the massive $n \times n$ similarity matrix is never explicitly stored or calculated.
Key Results
The authors evaluated ONGR across diverse benchmarks, including image datasets (COIL, MNIST) and large-scale tabular data (CoverType).
- Performance: ONGR consistently outperformed state-of-the-art methods like Nyström and Landmark-based Spectral Clustering (LSC). Notably, it achieved accuracy improvements of over 9% on the CoverType dataset.
- Efficiency: The algorithm processed the 630,000-sample MNIST-extend dataset in under 150 seconds, demonstrating its readiness for large-scale applications.
- Stability: Direct label extraction from the nonnegative matrix proved more reliable than k-means-based post-processing.
As shown in the figures above, the algorithm demonstrates rapid convergence of the objective value and the reconstruction error. Furthermore, the performance remains stable across a wide range of values for the hyperparameter $\lambda$, indicating robustness.
Conclusion
ONGR represents a significant step forward in making spectral clustering practical for massive datasets. While highly effective, future work may address sensitivities to outliers by exploring more robust norms (e.g., $\ell_{2,1}$-norm) and investigating more sophisticated anchor selection strategies to further enhance the quality of the reconstructed graph.
Summary updated