  Graph-based clustering has shown promising performance in many tasks. A key
step of graph-based approach is the similarity graph construction. In general,
learning graph in kernel space can enhance clustering accuracy due to the
incorporation of nonlinearity. However, most existing kernel-based graph
learning mechanisms is not similarity-preserving, hence leads to sub-optimal
performance. To overcome this drawback, we propose a more discriminative graph
learning method which can preserve the pairwise similarities between samples in
an adaptive manner for the first time. Specifically, we require the learned
graph be close to a kernel matrix, which serves as a measure of similarity in
raw data. Moreover, the structure is adaptively tuned so that the number of
connected components of the graph is exactly equal to the number of clusters.
Finally, our method unifies clustering and graph learning which can directly
obtain cluster indicators from the graph itself without performing further
clustering step. The effectiveness of this approach is examined on both single
and multiple kernel learning scenarios in several datasets.
