LGSSL:icml2010

Wei Liu, Junfeng He, Shih-Fu Chang. Large Graph Construction for Scalable Semi-Supervised Learning. In the 27th International Conference on Machine Learning (ICML), Haifa, Israel, June 2010.

Download [help]

Download paper: Adobe portable document (pdf)

Copyright notice:This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.

Abstract

In this paper, we address the scalability issue plaguing graph-based semi-supervised learning via a small number of anchor points which adequately cover the entire point cloud. Critically, these anchor points enable nonparametric regression that predicts the label for each data point as a locally weighted average of the labels on anchor points. Because conventional graph construction is inefficient in large scale, we propose to construct a tractable large graph by coupling anchorbased label prediction and adjacency matrix design. Contrary to the Nystr¡§om approximation of adjacency matrices which results in indefinite graph Laplacians and in turn leads to potential non-convex optimization over graphs, the proposed graph construction approach based on a unique idea called AnchorGraph provides nonnegative adjacency matrices to guarantee positive semidefinite graph Laplacians. Our approach scales linearly with the data size and in practice usually produces a large sparse graph. Experiments on large datasets demonstrate the significant accuracy improvement and scalability of the proposed approach

Contact

Wei Liu
Junfeng He
Shih-Fu Chang

BibTex Reference

@InProceedings{LGSSL:icml2010,
   Author = {Liu, Wei and He, Junfeng and Chang, Shih-Fu},
   Title = {Large Graph Construction for Scalable Semi-Supervised Learning},
   BookTitle = {the 27th International Conference on Machine Learning (ICML)},
   Address = {Haifa, Israel},
   Month = {June},
   Year = {2010}
}

EndNote Reference [help]

Get EndNote Reference (.ref)

For problems or questions regarding this web site contact The Web Master.