Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering

Junwei Han, Kai Xiong, Feiping NieIJCAI 2017 · DOI

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.
Visualizing the orthogonal and block-diagonal constraints of the ONGR framework.

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.
Convergence and parameter sensitivity of ONGR on COIL-20, MNIST-extend, and USPS datasets.

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

BibTeX
@inproceedings{han2017orthogonal,
  author = {Junwei Han and Kai Xiong and Feiping Nie},
  title = {{Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/251},
}
Figure