Hitting and commute times in large random neighborhood graphs

Ulrike von Luxburg, Agnes Radl, Matthias HeinJMLR 2014 · OpenReview

Abstract

In machine learning, a popular tool to analyze the structure of graphs is the hitting time and the commute distance (resistance distance). For two vertices u and v, the hitting time Huv is the expected time it takes a random walk to travel from u to v. The commute distance is its symmetrized version Cuv = Huv +Hvu. In our paper we study the behavior of hitting times and commute distances when the number n of vertices in the graph tends to infinity. We focus on random geometric graphs (ε-graphs, kNN graphs and Gaussian similarity graphs), but our results also extend to graphs with a given expected degree distribution or Erdos-Rényi graphs with planted partitions. We prove that in these graph families, the suitably rescaled hitting time Huv converges to 1/dv and the rescaled commute time to 1/du+1=dv where du and dv denote the degrees of vertices u and v. In these cases, hitting and commute times do not provide information about the structure of the graph, and their use is discouraged in many machine learning applications.
BibTeX
@article{luxburg2014hitting,
  author = {Ulrike von Luxburg and Agnes Radl and Matthias Hein},
  title = {{Hitting and commute times in large random neighborhood graphs}},
  journal = {J. Mach. Learn. Res.},
  year = {2014},
  url = {https://openreview.net/forum?id=CyQPB2jiJ0_},
}

Loading related content...

Figure