Density estimation from unweighted k-nearest neighbor graphs: a roadmap
Ulrike von Luxburg, Morteza Alamgir · 2013
Consider an unweighted k-nearest neighbor graph on n points that have been sam-pled i.i.d. from some unknown density p on Rd. 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 in-sights 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. 1