Metric recovery from directed unweighted graphs

Tatsunori Hashimoto, Yi Sun, Tommi Jaakkola
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:342-350, 2015.

Abstract

We analyze directed, unweighted graphs obtained from x_i∈\RR^d by connecting vertex i to j iff |x_i - x_j| < ε(x_i). Examples of such graphs include k-nearest neighbor graphs, where ε(x_i) varies from point to point, and, arguably, many real world graphs such as co-purchasing graphs. We ask whether we can recover the underlying Euclidean metric ε(x_i) and the associated density p(x_i) given only the directed graph and d. We show that consistent recovery is possible up to isometric scaling when the vertex degree is at least ω(n^2/(2+d)\log(n)^d/(d+2)). Our estimator is based on a careful characterization of a random walk over the directed graph and the associated continuum limit. As an algorithm, it resembles the PageRank centrality metric. We demonstrate empirically that the estimator performs well on simulated examples as well as on real-world co-purchasing graphs even with a small number of points and degree scaling as low as \log(n).

Cite this Paper

BibTeX
@InProceedings{pmlr-v38-hashimoto15, title = {{Metric recovery from directed unweighted graphs}}, author = {Hashimoto, Tatsunori and Sun, Yi and Jaakkola, Tommi}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {342--350}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/hashimoto15.pdf}, url = {https://proceedings.mlr.press/v38/hashimoto15.html}, abstract = {We analyze directed, unweighted graphs obtained from x_i∈\RR^d by connecting vertex i to j iff |x_i - x_j| < ε(x_i). Examples of such graphs include k-nearest neighbor graphs, where ε(x_i) varies from point to point, and, arguably, many real world graphs such as co-purchasing graphs. We ask whether we can recover the underlying Euclidean metric ε(x_i) and the associated density p(x_i) given only the directed graph and d. We show that consistent recovery is possible up to isometric scaling when the vertex degree is at least ω(n^2/(2+d)\log(n)^d/(d+2)). Our estimator is based on a careful characterization of a random walk over the directed graph and the associated continuum limit. As an algorithm, it resembles the PageRank centrality metric. We demonstrate empirically that the estimator performs well on simulated examples as well as on real-world co-purchasing graphs even with a small number of points and degree scaling as low as \log(n).} }
Endnote
%0 Conference Paper %T Metric recovery from directed unweighted graphs %A Tatsunori Hashimoto %A Yi Sun %A Tommi Jaakkola %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-hashimoto15 %I PMLR %P 342--350 %U https://proceedings.mlr.press/v38/hashimoto15.html %V 38 %X We analyze directed, unweighted graphs obtained from x_i∈\RR^d by connecting vertex i to j iff |x_i - x_j| < ε(x_i). Examples of such graphs include k-nearest neighbor graphs, where ε(x_i) varies from point to point, and, arguably, many real world graphs such as co-purchasing graphs. We ask whether we can recover the underlying Euclidean metric ε(x_i) and the associated density p(x_i) given only the directed graph and d. We show that consistent recovery is possible up to isometric scaling when the vertex degree is at least ω(n^2/(2+d)\log(n)^d/(d+2)). Our estimator is based on a careful characterization of a random walk over the directed graph and the associated continuum limit. As an algorithm, it resembles the PageRank centrality metric. We demonstrate empirically that the estimator performs well on simulated examples as well as on real-world co-purchasing graphs even with a small number of points and degree scaling as low as \log(n).
RIS
TY - CPAPER TI - Metric recovery from directed unweighted graphs AU - Tatsunori Hashimoto AU - Yi Sun AU - Tommi Jaakkola BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-hashimoto15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 342 EP - 350 L1 - http://proceedings.mlr.press/v38/hashimoto15.pdf UR - https://proceedings.mlr.press/v38/hashimoto15.html AB - We analyze directed, unweighted graphs obtained from x_i∈\RR^d by connecting vertex i to j iff |x_i - x_j| < ε(x_i). Examples of such graphs include k-nearest neighbor graphs, where ε(x_i) varies from point to point, and, arguably, many real world graphs such as co-purchasing graphs. We ask whether we can recover the underlying Euclidean metric ε(x_i) and the associated density p(x_i) given only the directed graph and d. We show that consistent recovery is possible up to isometric scaling when the vertex degree is at least ω(n^2/(2+d)\log(n)^d/(d+2)). Our estimator is based on a careful characterization of a random walk over the directed graph and the associated continuum limit. As an algorithm, it resembles the PageRank centrality metric. We demonstrate empirically that the estimator performs well on simulated examples as well as on real-world co-purchasing graphs even with a small number of points and degree scaling as low as \log(n). ER -
APA
Hashimoto, T., Sun, Y. & Jaakkola, T.. (2015). Metric recovery from directed unweighted graphs. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:342-350 Available from https://proceedings.mlr.press/v38/hashimoto15.html.

Related Material