Xiao-Ming Wu, Zhenguo Li, Shih-Fu Chang. Harmony in Graph-Based Learning. In Proceedings of Annual Conference on Neural Information Processing Systems (NIPS), Lake Tahoe, NV, USA, 2013.
Most graph-based models are developed based on Laplacian regularization or random walks, which turn out to impose a significant structure on the resulting target function where the value on a vertex is approximately the weighted average of the values on its adjacent neighbors (harmonic structure). In this paper, we study the harmonic structure systematically and show that the associate target function can faithfully capture the graph topology in that it drops little in dense area and sharply otherwise. We apply our analysis to various popular graph-based models including absorbing random walks, partially absorbing random walks, hitting times, the pseudo-inverse of graph Laplacian, and the eigenvectors of the Laplacian matrices. The insights obtained thereby enable us to provide corrections or justifications to their applications in classification, retrieval, recommendation, and clustering. In general, our analysis justifies Laplacian regularization and random walks for graph-based learning while emphasizing the role of proper use. Simulations on synthetic and real datasets validate our analysis
Xiao-Ming Wu
Zhenguo Li 
Shih-Fu Chang
@InProceedings{NIPS13,
Author = {Wu, Xiao-Ming and Li, Zhenguo and Chang, Shih-Fu},
Title = {Harmony in Graph-Based Learning},
BookTitle = {Proceedings of Annual Conference on Neural Information Processing Systems (NIPS)},
Address = {Lake Tahoe, NV, USA},
Year = {2013}
}
Get EndNote Reference (.ref)
For problems or questions regarding this web site contact The
Web Master.
This document was translated automatically from BibTEX by bib2html (Copyright 2003 © Eric Marchand, INRIA, Vista Project).