nips nips2013 nips2013-35 nips2013-35-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Xiao-Ming Wu, Zhenguo Li, Shih-Fu Chang
Abstract: 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.
[1] M. Alamgir and U. von Luxburg. Phase transition in the family of p-resistances. In NIPS. 2011.
[2] R. Andersen, F. Chung, and K. Lang. Local graph partitioning using pagerank vectors. In FOCS, pages 475–486, 2006.
[3] M. Belkin. Problems of Learning on Manifolds. PhD thesis, The University of Chicago, 2003.
[4] M. Belkin, I. Matveeva, and P. Niyogi. Regularization and semi-supervised learning on large graphs. In COLT, pages 624–638, 2004.
[5] M. Belkin, Q. Que, Y. Wang, and X. Zhou. Toward understanding complex spaces: Graph laplacians on manifolds with singularities and boundaries. In COLT, 2012.
[6] O. Bousquet, O. Chapelle, and M. Hein. Measure based regularization. In NIPS, 2003.
[7] F. Chung. Spectral Graph Theory. American Mathematical Society, 1997.
[8] R. Coifman and S. Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.
[9] P. G. Doyle and J. L. Snell. Random walks and electric networks. Mathematical Association of America, 1984.
[10] F. Fouss, A. Pirotte, J.-M. Renders, and M. Saerens. Random-walk computation of similarities between nodes of a graph with application to collaborative recommendation. IEEE Transactions on Knowledge and Data Engineering, 19(3):355–369, 2007.
[11] L. Hagen and A. B. Kahng. New spectral methods for ratio cut partitioning and clustering. IEEE transactions on Computer-aided design of integrated circuits and systems, 11(9):1074– 1085, 1992.
[12] D. J. Klein and M. Randi´ . Resistance distance. Journal of Mathematical Chemistry, 12(1):81– c 95, 1993.
[13] S. S. Lafon. Diffusion maps and geometric harmonics. PhD thesis, Yale University, 2004.
[14] M. H. G. Lever and M. Herbster. Predicting the labelling of a graph via minimum p-seminorm interpolation. In COLT, 2009.
[15] Q. Mei, D. Zhou, and K. Church. Query suggestion using hitting time. In CIKM, pages 469– 478, 2008.
[16] B. Nadler, N. Srebro, and X. Zhou. Statistical analysis of semi-supervised learning: The limit of infinite unlabelled data. In NIPS, pages 1330–1338, 2009.
[17] L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. 1999.
[18] J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Trans. PAMI, 22(8):888– 905, 2000.
[19] M. Szummer and T. Jaakkola. Partially labeled classification with Markov random walks. In NIPS, pages 945–952, 2002.
[20] U. Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395–416, 2007.
[21] U. Von Luxburg, M. Belkin, and O. Bousquet. Consistency of spectral clustering. The Annals of Statistics, pages 555–586, 2008.
[22] U. Von Luxburg, A. Radl, and M. Hein. Hitting and commute times in large graphs are often misleading. Arxiv preprint arXiv:1003.1266, 2010.
[23] X.-M. Wu, Z. Li, A. M.-C. So, J. Wright, and S.-F. Chang. Learning with partially absorbing random walks. In NIPS, 2012.
[24] D. Zhou, O. Bousquet, T. Lal, J. Weston, and B. Sch¨ lkopf. Learning with local and global o consistency. In NIPS, 2004.
[25] X. Zhou and M. Belkin. Semi-supervised learning by higher order regularization. In AISTATS, 2011.
[26] X. Zhu, Z. Ghahramani, and J. Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In ICML, 2003. 9