{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,19]],"date-time":"2026-06-19T17:38:16Z","timestamp":1781890696839,"version":"3.54.5"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"14","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2013,9]]},"abstract":"<jats:p>Analysis of large graphs is critical to the ongoing growth of search engines and social networks. One class of queries centers around node affinity, often quantified by random-walk distances between node pairs, including hitting time, commute time, and personalized PageRank (PPR). Despite the potential of these \"metrics,\" they are rarely, if ever, used in practice, largely due to extremely high computational costs.<\/jats:p>\n          <jats:p>In this paper, we investigate methods to scalably and efficiently compute random-walk distances, by \"embedding\" graphs and distances into points and distances in geometric coordinate spaces. We show that while existing graph coordinate systems (GCS) can accurately estimate shortest path distances, they produce significant errors when embedding random-walk distances. Based on our observations, we propose a new graph embedding system that explicitly accounts for per-node graph properties that affect random walk. Extensive experiments on a range of graphs show that our new approach can accurately estimate both symmetric and asymmetric random-walk distances. Once a graph is embedded, our system can answer queries between any two nodes in 8 microseconds, orders of magnitude faster than existing methods. Finally, we show that our system produces estimates that can replace ground truth in applications with minimal impact on application output.<\/jats:p>","DOI":"10.14778\/2556549.2556554","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1690-1701","source":"Crossref","is-referenced-by-count":31,"title":["On the embeddability of random walk distances"],"prefix":"10.14778","volume":"6","author":[{"given":"Xiaohan","family":"Zhao","sequence":"first","affiliation":[{"name":"Department of Computer Science, U. C. Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Adelbert","family":"Chang","sequence":"additional","affiliation":[{"name":"Department of Computer Science, U. C. Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Atish Das","family":"Sarma","sequence":"additional","affiliation":[{"name":"eBay Inc."}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haitao","family":"Zheng","sequence":"additional","affiliation":[{"name":"Department of Computer Science, U. C. Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ben Y.","family":"Zhao","sequence":"additional","affiliation":[{"name":"Department of Computer Science, U. C. Santa Barbara"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,9]]},"reference":[{"key":"e_1_2_1_1_1","first-page":"130","volume-title":"Nature","author":"Albert R.","year":"1999","unstructured":"R. Albert, H. Jeong, and A. Barabasi. Diameter of the world-wide web. Nature, pages 130-131, 1999."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1458082.1458122"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2012.625256"},{"key":"e_1_2_1_7_1","volume-title":"Proc. of SDM","author":"Brand M.","year":"2005","unstructured":"M. Brand. A random walks perspective on maximizing satisfaction and profit. In Proc. of SDM, 2005."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242650"},{"key":"e_1_2_1_9_1","first-page":"1647","volume-title":"Proc. of INFOCOM","author":"Cvetkovski A.","year":"2009","unstructured":"A. Cvetkovski and M. Crovella. Hyperbolic embedding and routing for dynamic graphs. In Proc. of INFOCOM, pages 1647-1655, 2009."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015467.1015471"},{"key":"e_1_2_1_11_1","first-page":"11","volume-title":"ICDCN","author":"Das Sarma A.","year":"2013","unstructured":"A. Das Sarma, A. R. Molla, G. Pandurangan, and E. Upfal. Fast distributed pagerank computation. In ICDCN, pages 11-26, 2013."},{"key":"e_1_2_1_12_1","first-page":"1079","volume-title":"Proc. of Adv. Phys","author":"Dorogovtsev S. N.","year":"2002","unstructured":"S. N. Dorogovtsev and J. F. F. Mendes. Evolution of networks. In Proc. of Adv. Phys, pages 1079-1187, 2002."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2005.10129104"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2392622.2392623"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2006.253"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/040609008"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2008.10129303"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775190"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13672-6_41"},{"key":"e_1_2_1_21_1","volume-title":"The pagerank citation ranking: Bringing order to the web. Technical report","author":"Lawrence P.","year":"1998","unstructured":"P. Lawrence et al. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford University, 1998."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1232722.1232727"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/1081870.1081893"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956972"},{"key":"e_1_2_1_26_1","first-page":"1","article-title":"Random walks on graphs: A survey","volume":"2","author":"Lov\u00e1sz L.","year":"1993","unstructured":"L. Lov\u00e1sz. Random walks on graphs: A survey. Bolyai Society Mathematical Studies, 2:1-46, 1993.","journal-title":"Bolyai Society Mathematical Studies"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2008.27"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/977400.977998"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060745.1060829"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/7.4.308"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/INFCOM.2002.1019258"},{"key":"e_1_2_1_32_1","first-page":"929","volume-title":"Proc. of BMVC","author":"Qiu H.","year":"2005","unstructured":"H. Qiu and E. Hancock. Image segmentation using commute times. In Proc. of BMVC, pages 929-938, 2005."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11744023_13"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304983"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1150402.1150443"},{"key":"e_1_2_1_36_1","first-page":"371","volume-title":"Proc. of ECML","author":"Saerens M.","year":"2004","unstructured":"M. Saerens et al. The principal components analysis of a graph, and its relationships to spectral clustering. In Proc. of ECML, pages 371-383, 2004."},{"key":"e_1_2_1_37_1","first-page":"335","volume-title":"Proc. of UAI","author":"Sarkar P.","year":"2007","unstructured":"P. Sarkar and W. Moore. A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In Proc. of UAI, pages 335-343, 2007."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1135777.1135823"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1644893.1644932"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1519065.1519089"},{"key":"e_1_2_1_42_1","first-page":"317","volume-title":"Proc. of ESANN","author":"Yen L.","year":"2005","unstructured":"L. Yen et al. Clustering using a random walk based distance measure. In Proc. of ESANN, pages 317-324, 2005."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1159913.1159945"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.13"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5555\/1895868.1895900"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2398776.2398795"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.5555\/1863190.1863199"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.4108\/icst.collaboratecom.2011.247162"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2556549.2556554","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,23]],"date-time":"2024-10-23T22:35:24Z","timestamp":1729722924000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2556549.2556554"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":48,"journal-issue":{"issue":"14","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.14778\/2556549.2556554"],"URL":"https:\/\/doi.org\/10.14778\/2556549.2556554","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2013,9]]}}}