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

2010

Conference Paper

ei


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.

Author(s): von Luxburg, U. and Radl, A. and Hein, M.
Book Title: Advances in Neural Information Processing Systems 23
Journal: Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010
Pages: 2622-2630
Year: 2010
Day: 0
Editors: Lafferty, J. , C. K.I. Williams, J. Shawe-Taylor, R. S. Zemel, A. Culotta
Publisher: Curran

Department(s): Empirical Inference
Research Project(s): Random geometric graphs
Bibtex Type: Conference Paper (inproceedings)

Address: Red Hook, NY, USA
Digital: 0
Event Name: Twenty-Fourth Annual Conference on Neural Information Processing Systems (NIPS 2010)
Event Place: Vancouver, BC, Canada
ISBN: 978-1-617-82380-0
Language: en
Organization: Max-Planck-Gesellschaft
School: Biologische Kybernetik

Links: PDF
Web

BibTex

@inproceedings{6766,
  title = {Getting lost in space: Large sample analysis of the resistance distance},
  author = {von Luxburg, U. and Radl, A. and Hein, M.},
  journal = {Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010},
  booktitle = {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},
  publisher = {Curran},
  organization = {Max-Planck-Gesellschaft},
  school = {Biologische Kybernetik},
  address = {Red Hook, NY, USA},
  year = {2010}
}