{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,2]],"date-time":"2026-06-02T21:32:39Z","timestamp":1780435959334,"version":"3.54.1"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:p>Distance oracles answer shortest-path queries between any pair of nodes in a graph. They are often built using succinct graph representations such as spanners, sketches, and compressors to minimize oracle size and query answering latency. Node embeddings, in particular, offer graph representations that place adjacent nodes nearby each other in a low-rank space. However, their use in the design of distance oracles has not been sufficiently studied.<\/jats:p>\n          <jats:p>In this paper, we empirically compare exact distance oracles constructed based on a variety of node embeddings and other succinct representations. We evaluate twelve such oracles along three measures of efficiency: construction time, memory requirements, and query-processing time over fourteen real datasets and four synthetic graphs. We show that distances between embedding vectors are excellent estimators of graph distances when graphs are well-structured, but less so for more unstructured graphs. Overall, our findings suggest that exact oracles based on embeddings can be constructed faster than multi-dimensional scaling (MDS) but slower than compressed adjacency indexes, require less memory than landmark oracles but more than sparsifiers or indexes, can answer queries faster than indexes but slower than MDS, and are exact more often with a smaller additive error than spanners (that have multiplicative error) while not being lossless like adjacency lists. Finally, while the exactness of such oracles is infeasible to maintain for huge graphs even under large amounts of resources, we empirically demonstrate that approximate oracles based on GOSH embeddings can efficiently scale to graphs of 100M+ nodes with only small additive errors in distance estimations.<\/jats:p>","DOI":"10.14778\/3551793.3551794","type":"journal-article","created":{"date-parts":[[2022,9,29]],"date-time":"2022-09-29T22:25:03Z","timestamp":1664490303000},"page":"2297-2306","source":"Crossref","is-referenced-by-count":1,"title":["Succinct graph representations as distance oracles"],"prefix":"10.14778","volume":"15","author":[{"given":"Arpit","family":"Merchant","sequence":"first","affiliation":[{"name":"University of Helsinki"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aristides","family":"Gionis","sequence":"additional","affiliation":[{"name":"KTH Royal Institute of Technology"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Michael","family":"Mathioudakis","sequence":"additional","affiliation":[{"name":"University of Helsinki"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,9,29]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"On Approximate Distance Labels and Routing Schemes with Affine Stretch","author":"Abraham Ittai","unstructured":"Ittai Abraham and Cyril Gavoille . 2011. On Approximate Distance Labels and Routing Schemes with Affine Stretch . In Distributed Computing, David Peleg (Ed.). Springer Berlin Heidelberg , Berlin, Heidelberg , 404--415. Ittai Abraham and Cyril Gavoille. 2011. On Approximate Distance Labels and Routing Schemes with Affine Stretch. In Distributed Computing, David Peleg (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg, 404--415."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132959"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/3404397.3404456"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805875.2805976"},{"key":"e_1_2_1_5_1","volume-title":"The isomap algorithm and topological stability. Science 295, 5552","author":"Balasubramanian Mukund","year":"2002","unstructured":"Mukund Balasubramanian , Eric L Schwartz , Joshua B Tenenbaum , Vin de Silva , and John C Langford . 2002. The isomap algorithm and topological stability. Science 295, 5552 ( 2002 ), 7--7. Mukund Balasubramanian, Eric L Schwartz, Joshua B Tenenbaum, Vin de Silva, and John C Langford. 2002. The isomap algorithm and topological stability. Science 295, 5552 (2002), 7--7."},{"key":"e_1_2_1_6_1","volume-title":"Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error","author":"Baswana Surender","unstructured":"Surender Baswana , Akshay Gaur , Sandeep Sen , and Jayant Upadhyay . 2008. Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error . In Automata, Languages and Programming, Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 609--621. Surender Baswana, Akshay Gaur, Sandeep Sen, and Jayant Upadhyay. 2008. Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error. In Automata, Languages and Programming, Luca Aceto, Ivan Damg\u00e5rd, Leslie Ann Goldberg, Magn\u00fas M. Halld\u00f3rsson, Anna Ing\u00f3lfsd\u00f3ttir, and Igor Walukiewicz (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 609--621."},{"key":"e_1_2_1_7_1","volume-title":"Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation 15, 6","author":"Belkin Mikhail","year":"2003","unstructured":"Mikhail Belkin and Partha Niyogi . 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation 15, 6 ( 2003 ), 1373--1396. Mikhail Belkin and Partha Niyogi. 2003. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation 15, 6 (2003), 1373--1396."},{"key":"e_1_2_1_8_1","volume-title":"Stochastic Algorithms: Foundations and Applications","author":"Berchenko Yakir","unstructured":"Yakir Berchenko and Mina Teicher . 2009. Graph Embedding through Random Walk for Shortest Paths Problems . In Stochastic Algorithms: Foundations and Applications , Osamu Watanabe and Thomas Zeugmann (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 127--140. Yakir Berchenko and Mina Teicher. 2009. Graph Embedding through Random Walk for Shortest Paths Problems. In Stochastic Algorithms: Foundations and Applications, Osamu Watanabe and Thomas Zeugmann (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 127--140."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3458064.3458238"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1002\/spe.587"},{"key":"e_1_2_1_11_1","volume-title":"Complex brain networks: graph theoretical analysis of structural and functional systems. Nature reviews neuroscience 10, 3","author":"Bullmore Ed","year":"2009","unstructured":"Ed Bullmore and Olaf Sporns . 2009. Complex brain networks: graph theoretical analysis of structural and functional systems. Nature reviews neuroscience 10, 3 ( 2009 ), 186--198. Ed Bullmore and Olaf Sporns. 2009. Complex brain networks: graph theoretical analysis of structural and functional systems. Nature reviews neuroscience 10, 3 (2009), 186--198."},{"key":"e_1_2_1_12_1","first-page":"e73","article-title":"The first comprehensive and quantitative analysis of human platelet protein composition allows the comparative analysis of structural and functional pathways","volume":"120","author":"Burkhart Julia M","year":"2012","unstructured":"Julia M Burkhart , Marc Vaudel , Stepan Gambaryan , Sonja Radau , Ulrich Walter , Lennart Martens , J\u00f6rg Geiger , Albert Sickmann , and Ren\u00e9 P Zahedi . 2012 . The first comprehensive and quantitative analysis of human platelet protein composition allows the comparative analysis of structural and functional pathways . Blood, The Journal of the American Society of Hematology 120 , 15 (2012), e73 -- e82 . Julia M Burkhart, Marc Vaudel, Stepan Gambaryan, Sonja Radau, Ulrich Walter, Lennart Martens, J\u00f6rg Geiger, Albert Sickmann, and Ren\u00e9 P Zahedi. 2012. The first comprehensive and quantitative analysis of human platelet protein composition allows the comparative analysis of structural and functional pathways. Blood, The Journal of the American Society of Hematology 120, 15 (2012), e73--e82.","journal-title":"Blood, The Journal of the American Society of Hematology"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2807452"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806512"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958016.1958031"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591801"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-013-0346-6"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020579"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1281100.1281133"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1039488.1039492"},{"key":"e_1_2_1_21_1","volume-title":"A new O (N (2)) algorithm for the symmetric tridiagonal eigenvalue\/eigenvector problem","author":"Dhillon Inderjit Singh","unstructured":"Inderjit Singh Dhillon . 1997. A new O (N (2)) algorithm for the symmetric tridiagonal eigenvalue\/eigenvector problem . University of California , Berkeley, Berkeley, CA, USA . Inderjit Singh Dhillon. 1997. A new O (N (2)) algorithm for the symmetric tridiagonal eigenvalue\/eigenvector problem. University of California, Berkeley, Berkeley, CA, USA."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939862"},{"key":"e_1_2_1_23_1","volume-title":"Benchmarking Graph Neural Networks. CoRR abs\/2003.00982","author":"Dwivedi Vijay Prakash","year":"2020","unstructured":"Vijay Prakash Dwivedi , Chaitanya K. Joshi , Thomas Laurent , Yoshua Bengio , and Xavier Bresson . 2020. Benchmarking Graph Neural Networks. CoRR abs\/2003.00982 ( 2020 ), 47. https:\/\/arxiv.org\/abs\/2003.00982 Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. 2020. Benchmarking Graph Neural Networks. CoRR abs\/2003.00982 (2020), 47. https:\/\/arxiv.org\/abs\/2003.00982"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02760037"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2004.05.002"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/217391.217463"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.48550\/ARXIV.1709.05584"},{"key":"e_1_2_1_28_1","volume-title":"Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33","author":"Hu Weihua","year":"2020","unstructured":"Weihua Hu , Matthias Fey , Marinka Zitnik , Yuxiao Dong , Hongyu Ren , Bowen Liu , Michele Catasta , and Jure Leskovec . 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33 ( 2020 ), 22118--22133. Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems 33 (2020), 22118--22133."},{"key":"e_1_2_1_29_1","volume-title":"Proc. of IEEE international telecommunications symposium (ITS). sn, IEEE","author":"Huffaker Bradley","year":"2002","unstructured":"Bradley Huffaker , Marina Fomenkov , Daniel J Plummer , David Moore , Kimberly Claffy , 2002 . Distance metrics in the Internet . In Proc. of IEEE international telecommunications symposium (ITS). sn, IEEE , New York, NY, USA, 20. Bradley Huffaker, Marina Fomenkov, Daniel J Plummer, David Moore, Kimberly Claffy, et al. 2002. Distance metrics in the Internet. In Proc. of IEEE international telecommunications symposium (ITS). sn, IEEE, New York, NY, USA, 20."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(92)90229-4"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.70"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/100810447"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4135\/9781412985130"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the First General Conference on Social Graphics. US Department of the Census, United States Government Printing Office","author":"Kruskal Joseph B","year":"1980","unstructured":"Joseph B Kruskal and Judith B Seery . 1980 . Designing network diagrams . In Proceedings of the First General Conference on Social Graphics. US Department of the Census, United States Government Printing Office , Washington, DC, USA, 22--50. Joseph B Kruskal and Judith B Seery. 1980. Designing network diagrams. In Proceedings of the First General Conference on Social Graphics. US Department of the Census, United States Government Printing Office, Washington, DC, USA, 22--50."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_2_1_36_1","volume-title":"ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods","author":"Lehoucq Richard B","unstructured":"Richard B Lehoucq , Danny C Sorensen , and Chao Yang . 1998. ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods . SIAM , Philadelphia, PA, USA . Richard B Lehoucq, Danny C Sorensen, and Chao Yang. 1998. ARPACK users' guide: solution of large-scale eigenvalue problems with implicitly restarted Arnoldi methods. SIAM, Philadelphia, PA, USA."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1753326.1753532"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2806416.2806501"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319877"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3186728.3164141"},{"key":"e_1_2_1_43_1","volume-title":"Spectral embedding of graphs. Pattern recognition 36, 10","author":"Luo Bin","year":"2003","unstructured":"Bin Luo , Richard C Wilson , and Edwin R Hancock . 2003. Spectral embedding of graphs. Pattern recognition 36, 10 ( 2003 ), 2213--2230. Bin Luo, Richard C Wilson, and Edwin R Hancock. 2003. Spectral embedding of graphs. Pattern recognition 36, 10 (2003), 2213--2230."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.3190130114"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/MCSA.1999.749281"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3289600.3290962"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313446"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/1181967.1324391"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/3382225.3382437"},{"key":"e_1_2_1_51_1","unstructured":"Benedek Rozemberczki Carl Allen and Rik Sarkar. 2019. Multi-scale Attributed Node Embedding. arXiv:1909.13021 [cs.LG]  Benedek Rozemberczki Carl Allen and Rik Sarkar. 2019. Multi-scale Attributed Node Embedding. arXiv:1909.13021 [cs.LG]"},{"key":"e_1_2_1_52_1","volume-title":"Collective classification in network data. AI magazine 29, 3","author":"Sen Prithviraj","year":"2008","unstructured":"Prithviraj Sen , Galileo Namata , Mustafa Bilgic , Lise Getoor , Brian Galligher , and Tina Eliassi-Rad . 2008. Collective classification in network data. AI magazine 29, 3 ( 2008 ), 93--93. Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93--93."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2530531"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/1044731.1044732"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186120"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447713"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1096-9128(199704)9:4<255::AID-CPE250>3.0.CO;2-2"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNNLS.2020.2978386"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-2864-4_568"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_61_1","volume-title":"7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). IEEE","author":"Zhao Xiaohan","unstructured":"Xiaohan Zhao , Alessandra Sala , Haitao Zheng , and Ben Y. Zhao . 2011. Efficient shortest paths on massive social graphs . In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). IEEE , New York, NY, USA, 77--86. Xiaohan Zhao, Alessandra Sala, Haitao Zheng, and Ben Y. Zhao. 2011. Efficient shortest paths on massive social graphs. In 7th International Conference on Collaborative Computing: Networking, Applications and Worksharing (CollaborateCom). IEEE, New York, NY, USA, 77--86."},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aiopen.2021.01.001"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3551793.3551794","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:21:14Z","timestamp":1672222874000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3551793.3551794"}},"subtitle":["an experimental evaluation"],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":62,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["10.14778\/3551793.3551794"],"URL":"https:\/\/doi.org\/10.14778\/3551793.3551794","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2022,7]]}}}