{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T17:15:56Z","timestamp":1780766156309,"version":"3.54.1"},"reference-count":64,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,5,26]],"date-time":"2023-05-26T00:00:00Z","timestamp":1685059200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Resistance distance is a fundamental metric to measure the similarity between two nodes in graphs which has been widely used in many real-world applications. In this paper, we study two problems on approximately computing resistance distance: (i) single-pair query which aims at calculating the resistance distance r(s, t) for a given pair of nodes (s, t); and (ii) single-source query which is to compute all the resistance distances r(s, u) for all nodes u in the graph with a given source node s. Existing algorithms for these two resistance distance query problems are often costly on large graphs. To efficiently solve these problems, we first establish several interesting connections among resistance distance, a new concept called v-absorbed random walk, random spanning forests, and a newly-developed v-absorbed push procedure. Based on such new connections, we propose three novel and efficient sampling-based algorithms as well as a deterministic algorithm for single-pair query; and we develop an online and two index-based approximation algorithms for single-source query. We show that the two index-based algorithms for single-source query take almost the same running time as the algorithms for single-pair query with the aid of a linear-size index. The striking feature of all our algorithms is that they are allowed to select an easy-to-hit node by random walks on the graph. Such an easy-to-hit landmark node v can make the v-absorbed random walk sampling, spanning tree sampling, as well as the v-absorbed push more efficient, thus significantly improving the performance of our algorithms. Extensive experiments on 5 real-life datasets show that our algorithms substantially outperform the state-of-the-art algorithms for two resistance distance query problems in terms of both running time and estimation errors.<\/jats:p>","DOI":"10.1145\/3588922","type":"journal-article","created":{"date-parts":[[2023,5,30]],"date-time":"2023-05-30T17:42:05Z","timestamp":1685468525000},"page":"1-27","source":"Crossref","is-referenced-by-count":13,"title":["Efficient Resistance Distance Computation: The Power of Landmark-based Approaches"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5808-3131","authenticated-orcid":false,"given":"Meihao","family":"Liao","sequence":"first","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8658-6599","authenticated-orcid":false,"given":"Rong-Hua","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8569-6558","authenticated-orcid":false,"given":"Qiangqiang","family":"Dai","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7626-0162","authenticated-orcid":false,"given":"Hongyang","family":"Chen","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Zhejiang, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4364-0633","authenticated-orcid":false,"given":"Hongchao","family":"Qin","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0181-8379","authenticated-orcid":false,"given":"Guoren","family":"Wang","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","unstructured":"2016. DBLP: DBLP Collaboration Network. http:\/\/dblp.uni-trier.de\/~ley\/db."},{"key":"e_1_2_2_2_1","unstructured":"2022. Project WordGraph. http:\/\/www.ims.uni-stuttgart.de\/en\/research\/projects\/wordgraph\/."},{"key":"e_1_2_2_3_1","volume-title":"9th Innovations in Theoretical Computer Science Conference, ITCS.","author":"Alev Vedat Levi","year":"2018","unstructured":"Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference, ITCS."},{"key":"e_1_2_2_4_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen Christian Borgs Jennifer T. Chayes John E. Hopcroft Vahab S. Mirrokni and Shang-Hua Teng. 2008. Local Computation of PageRank Contributions. Internet Math. (2008) 23--45.","DOI":"10.1080\/15427951.2008.10129302"},{"key":"e_1_2_2_5_1","volume-title":"Lang","author":"Andersen Reid","year":"2006","unstructured":"Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. 2006. Local Graph Partitioning using PageRank Vectors. In FOCS. 475--486."},{"key":"e_1_2_2_6_1","unstructured":"Eugenio Angriman Maria Predari Alexander van der Grinten and Henning Meyerhenke. 2020. Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis. In ESA."},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643799"},{"key":"e_1_2_2_8_1","volume-title":"Graphs and matrices","author":"Bapat Ravindra B","unstructured":"Ravindra B Bapat. 2010. Graphs and matrices. Vol. 27. Springer."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2020.03.061"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2006.10129116"},{"key":"e_1_2_2_11_1","volume-title":"Modern graph theory","author":"Bollob\u00e1s B\u00e9la","unstructured":"B\u00e9la Bollob\u00e1s. 1998. Modern graph theory. Vol. 184. Springer Science & Business Media."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2013.05.003"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/0603033"},{"key":"e_1_2_2_14_1","doi-asserted-by":"crossref","unstructured":"Pavel Chebotarev and Elena Deza. 2020. Hitting time quasi-metric and its forest representation. Optim. Lett. (2020) 291--307.","DOI":"10.1007\/s11590-018-1314-2"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Paul F. Christiano Jonathan A. Kelner Aleksander Madry Daniel A. Spielman and Shang-Hua Teng. 2011. Electrical flows laplacian systems and faster approximation of maximum flow in undirected graphs. In STOC.","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_2_16_1","doi-asserted-by":"crossref","unstructured":"Mustafa Coskun Ananth Grama and Mehmet Koyut\u00fcrk. 2016. Efficient Processing of Network Proximity Queries via Chebyshev Acceleration. In KDD. 1515--1524.","DOI":"10.1145\/2939672.2939828"},{"key":"e_1_2_2_17_1","first-page":"840","article-title":"Indexed Fast Network Proximity Querying","volume":"11","author":"Coskun Mustafa","year":"2018","unstructured":"Mustafa Coskun, Ananth Grama, and Mehmet Koyut\u00fcrk. 2018. Indexed Fast Network Proximity Querying. VLDB 11, 8 (2018), 840--852.","journal-title":"VLDB"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5948\/UPO9781614440222"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_2_20_1","unstructured":"Massimo Franceschet and Enrico Bozzo. 2017. Approximations of the Generalized Inverse of the Graph Laplacian Matrix. Internet Math. (2017)."},{"key":"e_1_2_2_21_1","unstructured":"Takanori Hayashi Takuya Akiba and Yuichi Yoshida. 2016. Efficient Algorithms for Spanning Tree Centrality. In IJCAI. 3733--3739."},{"key":"e_1_2_2_22_1","doi-asserted-by":"crossref","unstructured":"Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity. In KDD.","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_2_23_1","doi-asserted-by":"crossref","unstructured":"Glen Jeh and Jennifer Widom. 2003. Scaling personalized web search. In WWW. 271--279.","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_2_24_1","doi-asserted-by":"crossref","unstructured":"Jinhong Jung Namyong Park Lee Sael and U Kang. 2017. BePI: Fast and Memory-Efficient Method for Billion-Scale Random Walk with Restart. In SIGMOD. 789--804.","DOI":"10.1145\/3035918.3035950"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2043932.2043945"},{"key":"e_1_2_2_26_1","volume-title":"Collaborative Filtering Using Electrical Resistance Network Models. In Industrial Conference on Data Mining.","author":"Kunegis J\u00e9r\u00f4me","year":"2007","unstructured":"J\u00e9r\u00f4me Kunegis and Stephan Schmidt. 2007. Collaborative Filtering Using Electrical Resistance Network Models. In Industrial Conference on Data Mining."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289026"},{"key":"e_1_2_2_28_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_2_29_1","volume-title":"Qiangqiang Dai, Hongyang Chen, Hongchao Qin, and Guoren Wang.","author":"Liao Meihao","year":"2023","unstructured":"Meihao Liao, Rong hua Li, Qiangqiang Dai, Hongyang Chen, Hongchao Qin, and Guoren Wang. 2023. Efficient Resistance Distance Computation: the Power of Landmark-based Approaches. Full version: https:\/\/github.com\/mhliao516\/Resistance-Landmark (2023)."},{"key":"e_1_2_2_30_1","doi-asserted-by":"crossref","unstructured":"Meihao Liao Rong-Hua Li Qiangqiang Dai and Guoren Wang. 2022. Efficient Personalized PageRank Computation: A Spanning Forest Sampling based Approach. In SIGMOD. 1996--2008.","DOI":"10.1145\/3514221.3526140"},{"key":"e_1_2_2_31_1","volume-title":"Kleinberg","author":"Liben-Nowell David","year":"2003","unstructured":"David Liben-Nowell and Jon M. Kleinberg. 2003. The link prediction problem for social networks. In CIKM."},{"key":"e_1_2_2_32_1","volume-title":"Min Xie, and Victor Junqiu Wei.","author":"Lin Dandan","year":"2020","unstructured":"Dandan Lin, Raymond Chi-Wing Wong, Min Xie, and Victor Junqiu Wei. 2020. Index-Free Approach with Theoretical Guarantee for Efficient Random Walk with Restart Query. In ICDE. 913--924."},{"key":"e_1_2_2_33_1","doi-asserted-by":"crossref","unstructured":"Qin Liu Zhenguo Li John C. S. Lui and Jiefeng Cheng. 2016. PowerWalk: Scalable Personalized PageRank via Random Walks with Vertex-Centric Decomposition. In CIKM. 195--204.","DOI":"10.1145\/2983323.2983713"},{"key":"e_1_2_2_34_1","doi-asserted-by":"crossref","unstructured":"Peter Lofgren Siddhartha Banerjee and Ashish Goel. 2016. Personalized PageRank Estimation and Search: A Bidirectional Approach. In WSDM. 163--172.","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_2_35_1","volume-title":"Personalized PageRank to a Target Node. CoRR abs\/1304.4658","author":"Lofgren Peter","year":"2013","unstructured":"Peter Lofgren and Ashish Goel. 2013. Personalized PageRank to a Target Node. CoRR abs\/1304.4658 (2013). arXiv:1304.4658 http:\/\/arxiv.org\/abs\/1304.4658"},{"key":"e_1_2_2_36_1","volume-title":"Paul erdos is eighty 2, 1--46","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Random walks on graphs. Combinatorics, Paul erdos is eighty 2, 1--46 (1993), 4."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"Aleksander Madry Damian Straszak and Jakub Tarnawski. 2015. Fast Generation of Random Spanning Trees and the Effective Resistance Metric. In SODA. 2019--2036.","DOI":"10.1137\/1.9781611973730.134"},{"key":"e_1_2_2_39_1","volume-title":"The core decomposition of networks: theory, algorithms and applications. VLDB","author":"Malliaros Fragkiskos D.","year":"2020","unstructured":"Fragkiskos D. Malliaros, Christos Giatsidis, Apostolos N. Papadopoulos, and Michalis Vazirgiannis. 2020. The core decomposition of networks: theory, algorithms and applications. VLDB (2020), 61--92."},{"key":"e_1_2_2_40_1","doi-asserted-by":"crossref","unstructured":"Charalampos Mavroforakis Richard Garcia-Lebron Ioannis Koutis and Evimaria Terzi. 2015. Spanning Edge Centrality: Large-scale Computation and Applications. In WWW. 732--742.","DOI":"10.1145\/2736277.2741125"},{"key":"e_1_2_2_41_1","unstructured":"Qiaozhu Mei Dengyong Zhou and Kenneth Ward Church. 2008. Query suggestion using hitting time. In CIKM."},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-018-0504-3"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.13225"},{"key":"e_1_2_2_44_1","doi-asserted-by":"crossref","unstructured":"Pan Peng Daniel Lopatta Yuichi Yoshida and Gramoz Goranci. 2021. Local Algorithms for Estimating Effective Resistance. In KDD. 1329--1338.","DOI":"10.1145\/3447548.3467361"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1997.0917"},{"key":"e_1_2_2_46_1","doi-asserted-by":"crossref","unstructured":"Purnamrita Sarkar Andrew W. Moore and Amit Prakash. 2008. Fast incremental proximity search in large graphs. In ICML.","DOI":"10.1145\/1390156.1390269"},{"key":"e_1_2_2_47_1","doi-asserted-by":"crossref","unstructured":"Tam\u00e1s Sarl\u00f3s Andr\u00e1s A. Bencz\u00far K\u00e1roly Csalog\u00e1ny D\u00e1niel Fogaras and Bal\u00e1zs R\u00e1cz. 2006. To randomize or not to randomize: space optimal summaries for hyperlink analysis. In WWW. 297--306.","DOI":"10.1145\/1135777.1135823"},{"key":"e_1_2_2_48_1","doi-asserted-by":"crossref","unstructured":"Aaron Schild Satish Rao and Nikhil Srivastava. 2018. Localization of Electrical Flows. In SODA Artur Czumaj (Ed.).","DOI":"10.1137\/1.9781611975031.103"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.14778\/3384345.3384347"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723716"},{"key":"e_1_2_2_51_1","volume-title":"Robust Routing Using Electrical Flows. In SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems.","author":"Sinop Ali Kemal","year":"2021","unstructured":"Ali Kemal Sinop, Lisa Fawcett, Sreenivas Gollapudi, and Kostas Kollias. 2021. Robust Routing Using Electrical Flows. In SIGSPATIAL '21: 29th International Conference on Advances in Geographic Information Systems."},{"key":"e_1_2_2_52_1","volume-title":"Spielman and Nikhil Srivastava","author":"Daniel","year":"2008","unstructured":"Daniel A. Spielman and Nikhil Srivastava. 2008. Graph sparsification by effective resistances. In STOC."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"e_1_2_2_54_1","unstructured":"Ulrike von Luxburg Agnes Radl and Matthias Hein. 2010. Getting lost in space: Large sample analysis of the resistance distance. In NIPS. 2622--2630."},{"key":"e_1_2_2_55_1","volume-title":"Hitting and commute times in large graphs are often misleading. arXiv:1003.1266","author":"Luxburg Ulrike Von","year":"2010","unstructured":"Ulrike Von Luxburg, Agnes Radl, and Matthias Hein. 2010. Hitting and commute times in large graphs are often misleading. arXiv:1003.1266 (2010)."},{"key":"e_1_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Hanzhi Wang Zhewei Wei Junhao Gan Sibo Wang and Zengfeng Huang. 2020. Personalized PageRank to a Target Node Revisited. In KDD. 657--667.","DOI":"10.1145\/3394486.3403108"},{"key":"e_1_2_2_57_1","doi-asserted-by":"crossref","unstructured":"Shuguang Wang and Milos Hauskrecht. 2010. Effective query expansion with the resistance distance based term similarity metric. In SIGIR.","DOI":"10.1145\/1835449.1835580"},{"key":"e_1_2_2_58_1","first-page":"205","article-title":"HubPPR: Effective Indexing for Approximate Personalized PageRank","volume":"10","author":"Wang Sibo","year":"2016","unstructured":"Sibo Wang, Youze Tang, Xiaokui Xiao, Yin Yang, and Zengxiang Li. 2016. HubPPR: Effective Indexing for Approximate Personalized PageRank. VLDB 10, 3 (2016), 205--216.","journal-title":"VLDB"},{"key":"e_1_2_2_59_1","volume-title":"Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries. TODS","author":"Wang Sibo","year":"2019","unstructured":"Sibo Wang, Renchi Yang, Runhui Wang, Xiaokui Xiao, Zhewei Wei, Wenqing Lin, Yin Yang, and Nan Tang. 2019. Efficient Algorithms for Approximate Single-Source Personalized PageRank Queries. TODS (2019), 18:1--18:37."},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_2_61_1","doi-asserted-by":"crossref","unstructured":"David Bruce Wilson. 1996. Generating Random Spanning Trees More Quickly than the Cover Time. In STOC.","DOI":"10.1145\/237814.237880"},{"key":"e_1_2_2_62_1","doi-asserted-by":"crossref","unstructured":"Hao Wu Junhao Gan Zhewei Wei and Rui Zhang. 2021. Unifying the Global and Local Approaches: An Efficient Power Iteration with Forward Push. In SIGMOD. 1996--2008.","DOI":"10.1145\/3448016.3457298"},{"key":"e_1_2_2_63_1","volume-title":"TPA: Fast, Scalable, and Accurate Method for Approximate Random Walk with Restart on Billion Scale Graphs. In ICDE. 1132--1143.","author":"Yoon Minji","year":"2018","unstructured":"Minji Yoon, Jinhong Jung, and U Kang. 2018. TPA: Fast, Scalable, and Accurate Method for Approximate Random Walk with Restart on Billion Scale Graphs. In ICDE. 1132--1143."},{"key":"e_1_2_2_64_1","unstructured":"Zhen Zhang Mianzhi Wang Yijian Xiang Yan Huang and Arye Nehorai. 2018. RetGK: Graph Kernels based on Return Probabilities of Random Walks. In NeurIPS."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588922","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588922","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:37Z","timestamp":1750178857000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588922"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":64,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588922"],"URL":"https:\/\/doi.org\/10.1145\/3588922","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}