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