Learning locality preserving graph from data.

Journal Article (Journal Article)

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.

Full Text

Duke Authors

Cited Authors

  • Zhang, Y-M; Huang, K; Hou, X; Liu, C-L

Published Date

  • November 2014

Published In

Volume / Issue

  • 44 / 11

Start / End Page

  • 2088 - 2098

PubMed ID

  • 25020223

Electronic International Standard Serial Number (EISSN)

  • 2168-2275

International Standard Serial Number (ISSN)

  • 2168-2267

Digital Object Identifier (DOI)

  • 10.1109/tcyb.2014.2300489


  • eng