Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering

Orthogonal and Nonnegative Graph Reconstruction for Large Scale Clustering

Junwei Han, Kai Xiong, Feiping Nie

Proceedings of the Twenty-Sixth International Joint Conference on Artificial Intelligence
Main track. Pages 1809-1815. https://doi.org/10.24963/ijcai.2017/251

Spectral clustering has been widely used due to its simplicity for solving graph clustering problem in recent years. However, it suffers from the high computational cost as data grow in scale, and is limited by the performance of post-processing. To address these two problems simultaneously, in this paper, we propose a novel approach denoted by orthogonal and nonnegative graph reconstruction (ONGR) that scales linearly with the data size. For the relaxation of Normalized Cut, we add nonnegative constraint to the objective. Due to the nonnegativity, ONGR offers interpretability that the final cluster labels can be directly obtained without post-processing. Extensive experiments on clustering tasks demonstrate the effectiveness of the proposed method.
Keywords:
Machine Learning: Machine Learning
Machine Learning: Unsupervised Learning
Machine Learning: Structured Learning