Constructing a Non-Negative Low Rank and Sparse Graph with Data-Adaptive Features
This addresses graph construction for semi-supervised learning, offering a method that is incremental but shows strong performance gains.
The paper tackles the problem of constructing a graph for semi-supervised learning by proposing a non-negative low-rank and sparse graph that captures global and local data structures, and jointly learning data embeddings with graph construction. Experiments on three datasets show it outperforms state-of-the-art methods by a large margin for classification and discriminative analysis.
This paper aims at constructing a good graph for discovering intrinsic data structures in a semi-supervised learning setting. Firstly, we propose to build a non-negative low-rank and sparse (referred to as NNLRS) graph for the given data representation. Specifically, the weights of edges in the graph are obtained by seeking a nonnegative low-rank and sparse matrix that represents each data sample as a linear combination of others. The so-obtained NNLRS-graph can capture both the global mixture of subspaces structure (by the low rankness) and the locally linear structure (by the sparseness) of the data, hence is both generative and discriminative. Secondly, as good features are extremely important for constructing a good graph, we propose to learn the data embedding matrix and construct the graph jointly within one framework, which is termed as NNLRS with embedded features (referred to as NNLRS-EF). Extensive experiments on three publicly available datasets demonstrate that the proposed method outperforms the state-of-the-art graph construction method by a large margin for both semi-supervised classification and discriminative analysis, which verifies the effectiveness of our proposed method.