Poster
Density estimation from unweighted k-nearest neighbor graphs: a roadmap
Ulrike von Luxburg · Morteza Alamgir

Sat Dec 7th 07:00 -- 11:59 PM @ Harrah's Special Events Center, 2nd Floor #None

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 their distance or similarity scores. The key insights are that local differences in link numbers can be used to estimate some local function of p, and that integrating this function along shortest paths leads to an estimate of the underlying density.

Author Information

Ulrike von Luxburg (University of Tübingen)
Morteza Alamgir (University of Hamburg)

More from the Same Authors