slt Thumb sm ulrike luxburg
Ulrike von Luxburg (Project leader)
Max Planck Research Group Leader
ei Thumb sm thumb morteza alamgir
3 results

2012


Shortest path distance in random k-nearest neighbor graphs

Alamgir, M., von Luxburg, U.

In Proceedings of the 29th International Conference on Machine Learning, International Machine Learning Society, International Conference on Machine Learning (ICML), 2012 (inproceedings)

PDF Web Project Page [BibTex]

2012

PDF Web Project Page [BibTex]

2011


Phase transition in the family of p-resistances

Alamgir, M., von Luxburg, U.

In Advances in Neural Information Processing Systems 24, pages: 379-387, (Editors: J Shawe-Taylor and RS Zemel and P Bartlett and F Pereira and KQ Weinberger), Twenty-Fifth Annual Conference on Neural Information Processing Systems (NIPS), 2011 (inproceedings)

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 → ∞ 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.

PDF Web Project Page [BibTex]

2011

PDF Web Project Page [BibTex]

2010


Getting lost in space: Large sample analysis of the resistance distance

von Luxburg, U., Radl, A., Hein, M.

In Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, Advances in Neural Information Processing Systems 23, pages: 2622-2630, (Editors: Lafferty, J. , C. K.I. Williams, J. Shawe-Taylor, R. S. Zemel, A. Culotta), Curran, Red Hook, NY, USA, Twenty-Fourth Annual Conference on Neural Information Processing Systems (NIPS), 2010 (inproceedings)

Abstract
The commute distance between two vertices in a graph is the expected time it takes a random walk to travel from the first to the second vertex and back. We study the behavior of the commute distance as the size of the underlying graph increases. We prove that the commute distance converges to an expression that does not take into account the structure of the graph at all and that is completely meaningless as a distance function on the graph. Consequently, the use of the raw commute distance for machine learning purposes is strongly discouraged for large graphs and in high dimensions. As an alternative we introduce the amplified commute distance that corrects for the undesired large sample effects.

PDF Web Project Page [BibTex]

2010

PDF Web Project Page [BibTex]