nips nips2011 nips2011-213 nips2011-213-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Morteza Alamgir, Ulrike V. Luxburg
Abstract: We study the family of p-resistances on graphs for p 1. This family generalizes the standard resistance distance. We prove that for any fixed graph, for p = 1 the p-resistance coincides with the shortest path distance, for p = 2 it coincides with the standard resistance distance, and for p ! 1 it converges to the inverse of the minimal s-t-cut in the graph. Secondly, we consider the special case of random geometric graphs (such as k-nearest neighbor graphs) when the number n of vertices in the graph tends to infinity. We prove that an interesting phase transition takes place. There exist two critical thresholds p⇤ and p⇤⇤ such that if p < p⇤ , then the p-resistance depends on meaningful global properties of the graph, whereas if p > p⇤⇤ , it only depends on trivial local quantities and does not convey any useful information. We can explicitly compute the critical values: p⇤ = 1 + 1/(d 1) and p⇤⇤ = 1 + 1/(d 2) where d is the dimension of the underlying space (we believe that the fact that there is a small gap between p⇤ and p⇤⇤ is an artifact of our proofs). We also relate our findings to Laplacian regularization and suggest to use q-Laplacians as regularizers, where q satisfies 1/p⇤ + 1/q = 1. 1
M. Bazaraa, J. Jarvis, and H. Sherali. Linear Programming and Network Flows. Wiley-Interscience, 2010. B. Bollobas. Modern Graph Theory. Springer, 1998. T. B¨ hler and M. Hein. Spectral clustering based on the graph p-Laplacian. In Proceedings of the u International Conference on Machine Learning (ICML), pages 81–88, 2009. P. Chebotarev. A class of graph-geodetic distances generalizing the shortets path and the resistance distances. Discrete Applied Mathematics, 159(295 – 302), 2011. P. G. Doyle and J. Laurie Snell. Random walks and electric networks, 2000. URL http://www. citebase.org/abstract?id=oai:arXiv.org:math/0001057. M. Herbster and G. Lever. Predicting the labelling of a graph via minimum p-seminorm interpolation. In Conference on Learning Theory (COLT), 2009. B. Nadler, N. Srebro, and X. Zhou. Semi-supervised learning with the graph Laplacian: The limit of infinite unlabelled data. In Advances in Neural Information Processing Systems (NIPS), 2009. J. Tenenbaum, V. de Silva, and J. Langford. Supplementary material to ”A Global Geometric Framework for Nonlinear Dimensionality Reduction”. Science, 290:2319 – 2323, 2000. URL http://isomap.stanford.edu/BdSLT.pdf. U. von Luxburg, A. Radl, and M. Hein. Getting lost in space: Large sample analysis of the commute distance. In Neural Information Processing Systems (NIPS), 2010. L. Yen, M. Saerens, A. Mantrach, and M. Shimbo. A family of dissimilarity measures between nodes generalizing both the shortest-path and the commute-time distances. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785–793, 2008. D. Zhou and B. Sch¨ lkopf. Regularization on discrete spaces. In DAGM-Symposium, pages 361– o 368, 2005. X. Zhu, Z. Ghahramani, and J. D. Lafferty. Semi-supervised learning using Gaussian fields and harmonic functions. In ICML, pages 912–919, 2003. 9