Analyzing the Harmonic Structure in Graph-Based Learning
Xiao-Ming Wu, Zhenguo Li, Shih-Fu Chang · 2013
We find that various well-known graph-based models exhibit a common important 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 im-portant 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, par-tially absorbing random walks, hitting times, pseudo-inverse of the graph Lapla-cian, and eigenvectors of the Laplacian matrices. Our analysis sheds new insights into several open questions related to these models, and provides theoretical justi-fications and guidelines for their practical use. Simulations on synthetic and real datasets confirm the potential of the proposed theory and tool. 1