Spectral clustering is a quite simple but effective method for solving graph clustering problem. It projects the original data points into a lower dimensional space with spectral embedding, and then relies on an algorithm to obtain the cluster labels. Since it involves eigendecomposition of the graph Laplacian matrix for embedding, spectral clustering has high time complexity and is not able to process large scale data. The performance of spectral clustering is also limited by a post-processing algorithm such as kmeans. To tackle the two issues, we propose a method called Orthogonal and Nonnegative Graph Reconstruction (ONGR) for large scale clustering. The two constraints serve as a structure constraint with which the graph reconstructed by the indicator matrix is structured. The proposed method has linear time complexity with respect to the data size that it mainly needs to implicitly construct a graph and iteratively perform economical singular value decomposition for a small size matrix. Moreover, the interpretability of the indicator matrix is offered due to the nonnegative constraint, and thus our method can provide the cluster labels with no post-processing. The experiments on benchmark datasets show the effectiveness of the proposed scalable clustering method.

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.

Many previous graph-based methods perform dimensionality reduction on a pre-defined graph. However, due to the noise and redundant information in the original data, the pre-defined graph has no clear structure and may not be appropriate for the subsequent task. To overcome the drawbacks, in this paper, we propose a novel approach called linear manifold regularization with adaptive graph (LMRAG) for semi-supervised dimensionality reduction. LMRAG directly incorporates the graph construction into the objective function, thus the projection matrix and the optimal graph can be simultaneously optimized. Due to the structure constraint, the learned graph is sparse and has clear structure. Extensive experiments on several benchmark datasets demonstrate the effectiveness of the proposed method.