Xiao-Ming Wu, Zhenguo Li, Shih-Fu Chang. Analyzing the Harmonic Structure in Graph-Based Learning. In Proceedings of Annual Conference on Neural Information Processing Systems (NIPS), Lake Tahoe, NV, USA, 2013.
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.
Supplementary material available here
We find that various well-known graph-based models exhibit a common important \emph{harmonic} structure in its target function - the value of a vertex is approximately the weighted average of the values of its adjacent neighbors. Understanding of such structure and analysis of the loss defined over such structure help reveal important properties of the target function over a graph. In this paper, we show that the variation of the target function across a cut can be upper and lower bounded by the ratio of its harmonic loss and the cut cost. We use this to develop an analytical tool and analyze five popular graph-based models: absorbing random walks, partially absorbing random walks, hitting times, pseudo-inverse of the graph Laplacian, and eigenvectors of the Laplacian matrices. Our analysis sheds new insights into several open questions related to these models, and provides theoretical justifications and guidelines for their practical use. Simulations on synthetic and real datasets confirm the potential of the proposed theory and tool
Xiao-Ming Wu
Zhenguo Li 
Shih-Fu Chang
@InProceedings{NIPS13:Harmony,
Author = {Wu, Xiao-Ming and Li, Zhenguo and Chang, Shih-Fu},
Title = {Analyzing the Harmonic Structure 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).