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

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

DetailsSummary

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

von Luxburg, U., Radl, A., & Hein, M. (2011). Getting lost in space: Large sample analysis of the resistance distance. In J. Lafferty (Ed.), 24th Annual Conference on Neural Information Processing Systems (NIPS 2010) (pp. 2622-2630). Red Hook, NY: Curran.

Item is Released

show all hide all

Basic

show hide

Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-4CD3-D Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-4CD4-B

Genre: Conference Paper

Files

show Files

Locators

show

Creators

show

hide

Creators:
von Luxburg, U.¹, Author
Radl, A.², Author
Hein, M.³, Author

Affiliations:
1Research Group Machines Learning Theory, Max Planck Institute for Intelligent Systems, Max Planck Society, ou_1497665
2Dept. Empirical Inference, Max Planck Institute for Intelligent Systems, Max Planck Society, ou_1497647
3Max Planck Society, ou_persistent13

Content

show

hide

Free keywords: MPI für Intelligente Systeme; Abt. Schölkopf;

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.

Details

show

hide

Language(s):

Dates: Date issued: 2011-06-01

Publication Status: Issued

Pages: -

Publishing info: -

Table of Contents: -

Rev. Type: -

Identifiers: eDoc: 596833
URI: http://www.kyb.tuebingen.mpg.de//fileadmin/user_upload/files/publications/NIPS2010-Luxburg_6766[0].pdf
Other: 6766

Degree: -

Event

show

hide

Title: 24th Annual Conference on Neural Information Processing Systems (NIPS 2010)

Place of Event: Vancouver, BC, Canada

Start-/End Date: 2010-12-06 - 2010-12-09

Legal Case

show

Project information

show

Source 1

show

hide

Title: 24th Annual Conference on Neural Information Processing Systems (NIPS 2010)

Source Genre: Proceedings

Creator(s):
Lafferty, J., Editor

Affiliations:
-

Publ. Info: Red Hook, NY : Curran

Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 2622 - 2630 Identifier: -

Source 2

show

hide

Title: Advances in neural information processing systems

Source Genre: Series

Creator(s):

Affiliations:

Publ. Info: -

Pages: - Volume / Issue: 23 Sequence Number: - Start / End Page: - Identifier: -