Density estimation from unweighted k-nearest neighbor graphs: a roadmap
Consider an unweighted k-nearest neighbor graph on n points that have been sampled i.i.d. from some unknown density p on R d . We prove how one can estimate the density p just from the unweighted adjacency matrix of the graph, without knowing the points themselves or any distance or similarity scores. The key insights are that local differences in link numbers can be used to estimate a local function of the gradient of p, and that integrating this function along shortest paths leads to an estimate of the underlying density.
QUALITY: This work shows an interesting way of 
      estimating the density of a random vector from an unweighted k-NN graph. 
      It assumes that the density is differentiable and bounded away from zero 
      in the epsilon-interior of the support. Some minor points: 
      Page 2: in the definition of In(x), "E" has not been defined. Did the 
      authors mean "E_n"? Page 2: last paragraph: the unweighted shortest 
      path distance needs to be defined. Page 4: Proposition 1: I guess the 
      condition n/log(k) goes to infinity must be changed to k/log(n) goes to 
      infinity. CLARITY: The paper is nicely written. The main 
      results are motivated with examples and illustrations, and the proofs of 
      the results are sufficiently sketched. ORIGINALITY: The 
      main idea is to use rectifiable paths connecting two vertices to define 
      "order" (that is right and left) in a higher dimensional space. This is a 
      clever idea. It is known that in Euclidean space, a weighted k-NN graph 
      can give a rough (but asymptotically acceptable) estimate of the density. 
      In this work, the authors conjecture that even the unweighted k-NN graph 
      gives an estimate of the density. The authors show support for their 
      conjecture by showing that asymptotically their procedure converges to the 
      true density with a little more knowledge of the geometry. But as in the 
      case of the weighted graph, for real life applications, this estimate may 
      not be too good, unless the size of the sample is large. This is what the 
      authors do in their simulation: n=2000 with k=50 in one or two dimensions. 
      Higher dimensions will require an enormous quantity if data. The procedure 
      uses the knowledge of the vector dimension. In an unweighted graph, the 
      actual dimension may be unknown. The suggestion given by the authors to 
      estimate it will work again only if n is very large. 
      SIGNIFICANCE: I like the extended application suggested at 
      the end of the paper for multi-dimensional scaling. This might be a good 
      and very practical application of the procedure.