Hitting and Commute Times in Large Random Neighborhood Graphs

Ulrike von Luxburg; Agnes Radl; Matthias Hein

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

$H_{uv}$ is the expected time it takes a random walk to travel from

$u$ to

$v$ . The commute distance is its symmetrized version

$C_{uv} = H_{uv} + H_{vu}$ . 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 (

$\epsilon$ -graphs, kNN graphs and Gaussian similarity graphs), but our results also extend to graphs with a given expected degree distribution or Erdos-Renyi graphs with planted partitions. We prove that in these graph families, the suitably rescaled hitting time

$H_{uv}$ converges to

$1/d_v$ and the rescaled commute time to

$1/d_u + 1/d_v$ where

$d_u$ and

$d_v$ 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.

Hitting and Commute Times in Large Random Neighborhood Graphs

Abstract