  Graphs have become increasingly popular in modeling structures and
interactions in a wide variety of problems during the last decade. Graph-based
clustering and semi-supervised classification techniques have shown impressive
performance. This paper proposes a graph learning framework to preserve both
the local and global structure of data. Specifically, our method uses the
self-expressiveness of samples to capture the global structure and adaptive
neighbor approach to respect the local structure. Furthermore, most existing
graph-based methods conduct clustering and semi-supervised classification on
the graph learned from the original data matrix, which doesn't have explicit
cluster structure, thus they might not achieve the optimal performance. By
considering rank constraint, the achieved graph will have exactly $c$ connected
components if there are $c$ clusters or classes. As a byproduct of this, graph
learning and label inference are jointly and iteratively implemented in a
principled way. Theoretically, we show that our model is equivalent to a
combination of kernel k-means and k-means methods under certain condition.
Extensive experiments on clustering and semi-supervised classification
demonstrate that the proposed method outperforms other state-of-the-art
methods.
