Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver
Abstract
Graph-based Semi-Supervised learning is one of the most popular and successful semi-supervised learning methods. Typically, it predicts the labels of unlabeled data by minimizing a quadratic objective induced by the graph, which is unfortunately a procedure of polynomial complexity in the sample size $n$. In this paper, we address this scalability issue by proposing a method that approximately solves the quadratic objective in nearly linear time. The method consists of two steps: it first approximates a graph by a minimum spanning tree, and then solves the tree-induced quadratic objective function in O(n) time which is the main contribution of this work. Extensive experiments show the significant scalability improvement over existing scalable semi-supervised learning methods.
Cite
Text
Zhang et al. "Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver." AAAI Conference on Artificial Intelligence, 2016. doi:10.1609/AAAI.V30I1.10218Markdown
[Zhang et al. "Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver." AAAI Conference on Artificial Intelligence, 2016.](https://mlanthology.org/aaai/2016/zhang2016aaai-large/) doi:10.1609/AAAI.V30I1.10218BibTeX
@inproceedings{zhang2016aaai-large,
title = {{Large-Scale Graph-Based Semi-Supervised Learning via Tree Laplacian Solver}},
author = {Zhang, Yan-Ming and Zhang, Xu-Yao and Yuan, Xiao-Tong and Liu, Cheng-Lin},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2016},
pages = {2344-2350},
doi = {10.1609/AAAI.V30I1.10218},
url = {https://mlanthology.org/aaai/2016/zhang2016aaai-large/}
}