Graph-based subspace clustering methods have exhibited promising performance. However, they still suffer some of these drawbacks: they encounter the expensive time overhead, they fail to explore the explicit clusters, and cannot generalize to unseen data points. In this work, we propose a scalable graph learning framework, seeking to address the above three challenges simultaneously. Specifically, it is based on the ideas of anchor points and bipartite graph. Rather than building an $n\times n$ graph, where $n$ is the number of samples, we construct a bipartite graph to depict the relationship between samples and anchor points. Meanwhile, a connectivity constraint is employed to ensure that the connected components indicate clusters directly. We further establish the connection between our method and the $K$ -means clustering. Moreover, a model to process multiview data is also proposed, which is linearly scaled with respect to $n$ . Extensive experiments demonstrate the efficiency and effectiveness of our approach with respect to many state-of-the-art clustering methods.

Learning graphs from data automatically have shown encouraging performance on clustering and semisupervised learning tasks. However, real data are often corrupted, which may cause the learned graph to be inexact or unreliable. In this paper, we propose a novel robust graph learning scheme to learn reliable graphs from the real-world noisy data by adaptively removing noise and errors in the raw data. We show that our proposed model can also be viewed as a robust version of manifold regularized robust principle component analysis (RPCA), where the quality of the graph plays a critical role. The proposed model is able to boost the performance of data clustering, semisupervised classification, and data recovery significantly, primarily due to two key factors: 1) enhanced low-rank recovery by exploiting the graph smoothness assumption and 2) improved graph construction by exploiting clean data recovered by RPCA. Thus, it boosts the clustering, semisupervised classification, and data recovery performance overall. Extensive experiments on image/document clustering, object recognition, image shadow removal, and video background subtraction reveal that our model outperforms the previous state-of-the-art methods.

Multi-view graph clustering has been intensively investigated during the past years. However, existing methods are still limited in two main aspects. On the one hand, most of them can not deal with data that have both attributes and graphs. Nowadays, multi-view attributed graph data are ubiquitous and the need for effective clustering methods is growing. On the other hand, many state-of-the-art algorithms are either shallow or deep models. Shallow methods may seriously restrict their capacity for modeling complex data, while deep approaches often involve large number of parameters and are expensive to train in terms of running time and space needed. In this paper, we propose a novel multi-view attributed graph clustering (MAGC) framework, which exploits both node attributes and graphs. Our novelty lies in three aspects. First, instead of deep neural networks, we apply a graph filtering technique to achieve a smooth node representation. Second, the original graph could be noisy or incomplete and is not directly applicable, thus we learn a consensus graph from data by considering the heterogeneous views. Third, high-order relations are explored in a flexible way by designing a new regularizer. Extensive experiments demonstrate the superiority of our method in terms of effectiveness and efficiency.

Auto-Encoder (AE)-based deep subspace clustering (DSC) methods have achieved impressive performance due to the powerful representation extracted using deep neural networks while prioritizing categorical separability. However, self-reconstruction loss of an AE ignores rich useful relation information and might lead to indiscriminative representation, which inevitably degrades the clustering performance. It is also challenging to learn high-level similarity without feeding semantic labels. Another unsolved problem facing DSC is the huge memory cost due to n×n similarity matrix, which is incurred by the self-expression layer between an encoder and decoder. To tackle these problems, we use pairwise similarity to weigh the reconstruction loss to capture local structure information, while a similarity is learned by the self-expression layer. Pseudo-graphs and pseudo-labels, which allow benefiting from uncertain knowledge acquired during network training, are further employed to supervise similarity learning. Joint learning and iterative training facilitate to obtain an overall optimal solution. Extensive experiments on benchmark datasets demonstrate the superiority of our approach. By combining with the k-nearest neighbors algorithm, we further show that our method can address the large-scale and out-of-sample problems. The source code of our method is available: https://github.com/sckangz/SelfsupervisedSC.