Article

Density estimation from unweighted k-nearest neighbor graphs: a roadmap

Authors:

Ulrike von Luxburg,

Morteza AlamgirAuthors Info & Claims

NIPS'13: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1

Pages 225 - 233

Published: 05 December 2013 Publication History

Abstract

Consider an unweighted k-nearest neighbor graph on n points that have been sampled i.i.d. from some unknown density p on ℝ^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.

References

[1]

S. Agarwal, J. Wills, L. Cayton, G. Lanckriet, D. Kriegman, and S. Belongie. Generalized non-metric multidimensional scaling. In AISTATS, 2007.

[2]

M. Alamgir and U. von Luxburg. Shortest path distance in random k-nearest neighbor graphs. In International Conference on Machine Learning (ICML), 2012.

[3]

N. Alon, M. Bădoiu, E. Demaine, M. Farach-Colton, M. Hajiaghayi, and A. Sidiropoulos. Ordinal embeddings of minimum relaxation: general properties, trees, and ultrametrics. ACM Transactions on Algorithms, 4(4):46, 2008.

[4]

M. Bădoiu, E. Demaine, M. Hajiaghayi, A. Sidiropoulos, and M. Zadimoghaddam. Ordinal embedding: approximation algorithms and dimensionality reduction. In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Springer, 2008.

[5]

Y. Bilu and N. Linial. Monotone maps, sphericity and bounded second eigenvalue. Journal of Combinatorial Theory, Series B, 95(2):283-299, 2005.

[6]

I. Borg and P. Groenen. Modern multidimensional scaling: Theory and applications. Springer, 2005.

[7]

D. Burago, Y. Burago, and S. Ivanov. A course in metric geometry. American Mathematical Society, 2001.

[8]

G. Gutin, E. Kim, M. Mnich, and A. Yeo. Ordinal embedding relaxations parameterized above tight lower bound. arXiv preprint arXiv:0907.5427, 2009.

[9]

K. Jamieson and R. Nowak. Low-dimensional embedding using adaptively selected ordinal data. In Conference on Communication, Control, and Computing, pages 1077-1084, 2011.

[10]

B. McFee and G. Lanckriet. Partial order embedding with multiple kernels. In International Conference on Machine Learning (ICML), 2009.

[11]

H. Ouyang and A. Gray. Learning dissimilarities by ranking: from SDP to QP. In International Conference on Machine Learning (ICML), pages 728-735, 2008.

[12]

M. Schultz and T. Joachims. Learning a distance metric from relative comparisons. In Neural Information Processing Systems (NIPS), 2004.

[13]

B. Shaw and T. Jebara. Structure preserving embedding. In International Conference on Machine Learning (ICML), 2009.

[14]

B. Shaw, B. Huang, and T. Jebara. Learning a distance metric from a network. Neural Information Processing Systems (NIPS), 2011.

[15]

R. Shepard. Metric structures in ordinal data. Journal of Mathematical Psychology, 3(2):287-315, 1966.

Cited By

Kleindessner MVon Luxburg U(2017)Lens depth function and k-relative neighborhood graph: versatile tools for ordinal data analysisThe Journal of Machine Learning Research10.5555/3122009.315301418:1(1889-1940)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3153014

Density estimation from unweighted k-nearest neighbor graphs: a roadmap
1. Computing methodologies
2. Mathematics of computing
  1. Discrete mathematics

Recommendations

Triangle-free subcubic graphs with minimum bipartite density

A graph is subcubic if its maximum degree is at most 3. The bipartite density of a graph G is max{@e(H)/@e(G):H is a bipartite subgraph of G}, where @e(H) and @e(G) denote the numbers of edges in H and G, respectively. It is an NP-hard problem to ...
Neighbor sum distinguishing index of planar graphs

A proper [k]-edge coloring of a graph G is a proper edge coloring of G using colors from [k]={1,2,...,k}. A neighbor sum distinguishing [k]-edge coloring of G is a proper [k]-edge coloring of G such that for each edge uv@__ __E(G), the sum of colors ...
Edge integrity of nearest neighbor graphs and separator theorems
Abstract
We give upper bounds for the edge integrity and the vertex integrity of k-type nearest neighbor graphs in R d. For n the order of a graph, examples are constructed to show that the bounds are best possible in the parameters n and k. ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

NIPS'13: Proceedings of the 26th International Conference on Neural Information Processing Systems - Volume 1

December 2013

3236 pages

Publisher

Curran Associates Inc.

Red Hook, NY, United States

Publication History

Published: 05 December 2013

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kleindessner MVon Luxburg U(2017)Lens depth function and k-relative neighborhood graph: versatile tools for ordinal data analysisThe Journal of Machine Learning Research10.5555/3122009.315301418:1(1889-1940)Online publication date: 1-Jan-2017
https://dl.acm.org/doi/10.5555/3122009.3153014

View Options

View options

Media

Figures

Other

Tables

View Table of Contents