Shortest path distance in random k-nearest neighbor graphs

Consider a weighted or unweighted k-nearest neighbor graph that has been built on n data points drawn randomly according to some density p on Rd. We study the convergence of the shortest path distance in such graphs as the sample size tends to infinity. We prove that for unweighted kNN graphs, this dis-tance converges to an unpleasant distance function on the underlying space whose prop-erties are detrimental to machine learning. We also study the behavior of the shortest path distance in weighted kNN graphs. 1