Learning locality preserving graph from data

Yan Ming Zhang*, Kaizhu Huang, Xinwen Hou, Cheng Lin Liu

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

34 Citations (Scopus)


Machine learning based on graph representation, or manifold learning, has attracted great interest in recent years. As the discrete approximation of data manifold, the graph plays a crucial role in these kinds of learning approaches. In this paper, we propose a novel learning method for graph construction, which is distinct from previous methods in that it solves an optimization problem with the aim of directly preserving the local information of the original data set. We show that the proposed objective has close connections with the popular Laplacian Eigenmap problem, and is hence well justified. The optimization turns out to be a quadratic programming problem with n(n-1)/2 variables (n is the number of data points). Exploiting the sparsity of the graph, we further propose a more efficient cutting plane algorithm to solve the problem, making the method better scalable in practice. In the context of clustering and semi-supervised learning, we demonstrated the advantages of our proposed method by experiments.

Original languageEnglish
Article number6849939
Pages (from-to)2088-2098
Number of pages11
JournalIEEE Transactions on Cybernetics
Issue number11
Publication statusPublished - Nov 2014


  • Graph construction
  • graph-based learning
  • manifold learning
  • semi-supervised learning
  • spectral clustering


Dive into the research topics of 'Learning locality preserving graph from data'. Together they form a unique fingerprint.

Cite this