In the graph-based semi-supervised learning, the Green-function method is a classical method that works by computing the Green's function in the graph space. However, when applied to large graphs, especially those sparse ones, this method performs unstably and unsatisfactorily. We make a detailed analysis on it and propose a novel method from the perspective of optimization. On fully connected graphs, the method is equivalent to the Green-function method and can be seen as another interpretation with physical meanings, while on non-fully connected graphs, it helps to explain why the Green-function method causes a mess on large sparse graphs. To solve this dilemma, we propose a workable approach to improve our proposed method. Unlike the original method, our improved method can also apply two accelerating techniques, Gaussian Elimination, and Anchored Graphs to become more efficient on large graphs. Finally, the extensive experiments prove our conclusions and the efficiency, accuracy, and stability of our improved Green's function method.

Multi-view learning has raised more and more attention in recent years. However, traditional approaches only focus on the difference while ignoring the consistency among views. It may make some views, with the situation of data abnormality or noise, ineffective in the progress of view learning. Besides, the current datasets have become high-dimensional and large-scale gradually. Therefore, this paper proposes a novel multi-view compressed subspace learning method via low-rank tensor constraint, which incorporates the clustering progress and multi-view learning into a unified framework. First, for each view, we take the partial samples to build a small-size dictionary, which can reduce the effect of both redundancy information and computation cost greatly. Then, to find the consistency and difference among views, we impose a low-rank tensor constraint on these representations and further design an auto-weighted mechanism to learn the optimal representation. Last, due to the non-square of the learned representation, the bipartite graph has been introduced, and under the structured constraint, the clustering results can be obtained directly from this graph without any post-processing. Extensive experiments on synthetic and real-world benchmark datasets demonstrate the efficacy and efficiency of our method, especially for the views with noise or outliers.

In this article, we focus on utilizing the idea of co-clustering algorithms to address the subspace clustering problem. In recent years, co-clustering methods have been developed greatly with many important applications, such as document clustering and gene expression analysis. Different from the traditional graph-based methods, co-clustering can utilize the bipartite graph to extract the duality relationship between samples and features. It means that the bipartite graph can obtain more information than other traditional graph methods. Therefore, we proposed a novel method to handle the subspace clustering problem by combining dictionary learning with a bipartite graph under the constraint of the (normalized) Laplacian rank. Besides, to avoid the effect of redundant information hiding in the data, the original data matrix is not used as the static dictionary in our model. By updating the dictionary matrix under the sparse constraint, we can obtain a better coefficient matrix to construct the bipartite graph. Based on Theorem 2 and Lemma 1, we further speed up our algorithm. Experimental results on both synthetic and benchmark datasets demonstrate the superior effectiveness and stability of our model.

Multitask learning (MTL) is a joint learning paradigm, which fuses multiple related tasks together to achieve the better performance than single-task learning methods. It has been observed by many researchers that different tasks with certain similarities share a low-dimensional common yet latent subspace. In order to get the low-rank structure shared across tasks, trace norm has been used as a convex relaxation of the rank minimization problem. However, trace norm is not a tight approximation for the rank function. To address this important issue, we propose two novel regularization-based models to approximate the rank minimization problem by minimizing the k minimal singular values. For our new models, if the minimal singular values are suppressed to zeros, the rank would also be reduced. Compared with the standard trace norm, our new regularization-based models are the tighter approximations, which can help our models capture the low-dimensional subspace among multiple tasks better. Besides, it is an NP-hard problem to directly solve the exact rank minimization problem for our models. In this article, we proposed two simple but effective strategies to optimize our models, which tactically solves the exact rank minimization problem by setting a large penalizing parameter. Experimental results performed on synthetic and real-world benchmark datasets demonstrate that the proposed models have the ability of learning the low-rank structure shared across tasks and the better performance than other classical MTL methods.

In this paper, a novel low-rank structural model is proposed for segmenting data drawn from a high-dimensional space. Our method is based on the fact that all groups clustered from a high-dimensional dataset are distributed in multiple low-rank subspaces. In general, it’s a very difficult task to find the low-rank structures hidden in data. Different from the classical sparse subspace clustering (SSC) and low-rank representation (LRR) which all take two steps including building the affinity matrix and spectral clustering, we introduce a new rank constraint into our model. This constraint allows our model to learn a subspace indicator which can capture different clusters directly from the data without any postprocessing. To further approximate the rank constraint, a piecewise function is utilized as the relaxing item for the proposed model. Besides, under the subspace indicator constraints, the integer programming problem is avoided, which makes our algorithm more efficient and scalable. In addition, we prove the convergence of the proposed algorithm in theory and further discuss the general case in which subspaces don’t pass through the origin. Experiment results on both synthetic and real-world datasets demonstrate that our algorithm significantly outperforms the state-of-the-art methods.

Multi-task learning has been observed by many researchers, which supposes that different tasks can share a low-rank common yet latent subspace. It means learning multiple tasks jointly is better than learning them independently. In this paper, we propose two novel multi-task learning formulations based on two regularization terms, which can learn the optimal shared latent subspace by minimizing the exactly k minimal singular values. The proposed regularization terms are the more tight approximations of rank minimization than trace norm. But it's an NP-hard problem to solve the exact rank minimization problem. Therefore, we design a novel re-weighted based iterative strategy to solve our models, which can tactically handle the exact rank minimization problem by setting a large penalizing parameter. Experimental results on benchmark datasets demonstrate that our methods can correctly recover the low-rank structure shared across tasks, and outperform related multi-task learning methods.

Clustering task has been greatly developed in recent years like partition-based and graph-based methods. However, in terms of improving robustness, most existing algorithms only focus on noise and outliers between data, while ignoring the noise in feature space. To deal with this situation, we propose a novel weight learning mechanism to adaptively reweight each feature in the data. Combining with the clustering task, we further propose a robust fuzzy K-Means model based on the auto-weighted feature learning, which can effectively reduce the proportion of noisy features. Besides, a regularization term is introduced into our model to make the sample-to-clusters memberships of each sample have suitable sparsity. Specifically, we design an effective strategy to determine the value of the regularization parameter. The experimental results on both synthetic and real-world datasets demonstrate that our model has better performance than other classical algorithms.

This paper addresses the subspace clustering problem based on low-rank representation. Combining with the idea of co-clustering, we proposed to learn an optimal structural bipartite graph. It's different with other classical subspace clustering methods which need spectral clustering as post-processing on the constructed graph to get the final result, our method can directly learn a structural graph with k connected components so that the different clusters are obtained easily. Furthermore, we introduce a regularization term of error matrix to our model which helps the proposed algorithm to be more effective to learn an optimal graph under the circumstances of various noise. Experimental results both on synthetic and benchmark datasets are presented to show the effectiveness and robustness of our model.