Analyzing the Harmonic Structure in Graph-Based Learning
Analyzing the Harmonic Structure in Graph-Based Learning
复制标题
DOI：
--
复制
发表时间：
2013-12
期刊：
影响因子：
--
通讯作者：
Xiao-Ming Wu;Zhenguo Li;Shih-Fu Chang
中科院分区：
文献类型：
--
作者：
Xiao-Ming Wu;Zhenguo Li;Shih-Fu Chang
我们发现，各种著名的基于图的模型在其目标函数中表现出一个共同的重要调和结构-顶点的值近似于其相邻邻居的值的加权平均值。对这种结构的理解和对这种结构上定义的损失的分析有助于揭示图上目标函数的重要性质。在本文中，我们表明，目标函数的变化跨越削减可以由其谐波损耗和削减成本的比率的上界和下界。我们用它来开发一个分析工具，并分析五个流行的基于图形的模型：吸收随机游动，部分吸收随机游动，命中时间，伪逆的图形拉普拉斯算子，和特征向量的拉普拉斯矩阵。我们的分析揭示了与这些模型相关的几个开放问题的新见解，并为其实际应用提供了理论依据和指导方针。在合成和真实的数据集上的模拟证实了所提出的理论和工具的潜力。
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 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.