Abstract
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 language | English |
---|---|
Article number | 6849939 |
Pages (from-to) | 2088-2098 |
Number of pages | 11 |
Journal | IEEE Transactions on Cybernetics |
Volume | 44 |
Issue number | 11 |
DOIs | |
Publication status | Published - Nov 2014 |
Keywords
- Graph construction
- graph-based learning
- manifold learning
- semi-supervised learning
- spectral clustering