Timezone: »
Poster
Density estimation from unweighted k-nearest neighbor graphs: a roadmap
Ulrike von Luxburg · Morteza Alamgir
Sat Dec 07 07:00 PM -- 11:59 PM (PST) @ Harrah's Special Events Center, 2nd Floor
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 Tuebingen)
Morteza Alamgir (University of Hamburg)
More from the Same Authors
-
2022 Poster: Interpolation and Regularization for Causal Learning »
Leena Chennuru Vankadara · Luca Rendsburg · Ulrike Luxburg · Debarghya Ghoshdastidar -
2019 Poster: Foundations of Comparison-Based Hierarchical Clustering »
Debarghya Ghoshdastidar · Michaël Perrot · Ulrike von Luxburg -
2018 Poster: When do random forests fail? »
Cheng Tang · Damien Garreau · Ulrike von Luxburg -
2018 Poster: Measures of distortion for machine learning »
Leena Chennuru Vankadara · Ulrike von Luxburg -
2018 Poster: Practical Methods for Graph Two-Sample Testing »
Debarghya Ghoshdastidar · Ulrike von Luxburg -
2017 : Ordinal distance comparisons: from topology to geometry »
Ulrike von Luxburg -
2017 Poster: Kernel functions based on triplet comparisons »
Matthäus Kleindessner · Ulrike von Luxburg -
2011 Workshop: Relations between machine learning problems - an approach to unify the field »
Robert Williamson · John Langford · Ulrike von Luxburg · Mark Reid · Jennifer Wortman Vaughan -
2011 Poster: Phase transition in the family of p-resistances »
Morteza Alamgir · Ulrike von Luxburg -
2011 Spotlight: Phase transition in the family of p-resistances »
Morteza Alamgir · Ulrike von Luxburg -
2010 Spotlight: Getting lost in space: Large sample analysis of the resistance distance »
Ulrike von Luxburg · Agnes Radl · Matthias Hein -
2010 Poster: Getting lost in space: Large sample analysis of the resistance distance »
Ulrike von Luxburg · Agnes Radl · Matthias Hein -
2009 Workshop: Clustering: Science or art? Towards principled approaches »
Margareta Ackerman · Shai Ben-David · Avrim Blum · Isabelle Guyon · Ulrike von Luxburg · Robert Williamson · Reza Zadeh -
2008 Poster: Influence of graph construction on graph-based clustering measures »
Markus M Maier · Ulrike von Luxburg · Matthias Hein -
2008 Oral: Influence of graph construction on graph-based clustering measures »
Markus M Maier · Ulrike von Luxburg · Matthias Hein -
2007 Session: Spotlights »
Ulrike von Luxburg -
2007 Session: Spotlights »
Ulrike von Luxburg -
2007 Spotlight: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann -
2007 Poster: Consistent Minimization of Clustering Objective Functions »
Ulrike von Luxburg · Sebastien Bubeck · Stefanie S Jegelka · Michael Kaufmann