{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T10:52:52Z","timestamp":1790765572721,"version":"4.1.0"},"reference-count":76,"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"}],"funder":[{"name":"A*STAR Singapore","award":["A19E3b0099"],"award-info":[{"award-number":["A19E3b0099"]}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["U22B2060"],"award-info":[{"award-number":["U22B2060"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100020084","name":"Guangzhou Municipal Science and Technology Bureau","doi-asserted-by":"crossref","award":["2023A03J0667"],"award-info":[{"award-number":["2023A03J0667"]}],"id":[{"id":"10.13039\/501100020084","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2023,5,26]]},"abstract":"<jats:p>Given an undirected graph G, the effective resistance r(s,t) measures the dissimilarity of node pair s,t in G, which finds numerous applications in real-world problems, such as recommender systems, combinatorial optimization, molecular chemistry, and electric power networks. Existing techniques towards pairwise effective resistance estimation either trade approximation guarantees for practical efficiency, or vice versa. In particular, the state-of-the-art solution is based on a multitude of Monte Carlo random walks, rendering it rather inefficient in practice, especially on large graphs.<\/jats:p>\n          <jats:p>Motivated by this, this paper first presents an improved Monte Carlo approach, AMC, which reduces both the length and amount of random walks required without degrading the theoretical accuracy guarantee, through careful theoretical analysis and an adaptive sampling scheme. Further, we develop a greedy approach, GEER, which combines AMC with sparse matrix-vector multiplications in an optimized and non-trivial way. GEER offers significantly improved practical efficiency over AMC without compromising its asymptotic performance and accuracy guarantees. Extensive experiments on multiple benchmark datasets reveal that GEER is orders of magnitude faster than the state of the art in terms of computational time when achieving the same accuracy.<\/jats:p>","DOI":"10.1145\/3588696","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":17,"title":["Efficient Estimation of Pairwise Effective Resistance"],"prefix":"10.1145","volume":"1","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7284-3096","authenticated-orcid":false,"given":"Renchi","family":"Yang","sequence":"first","affiliation":[{"name":"Hong Kong Baptist University, Hong Kong, Hong Kong"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0785-707X","authenticated-orcid":false,"given":"Jing","family":"Tang","sequence":"additional","affiliation":[{"name":"The Hong Kong University of Science and Technology (Guangzhou) &amp; The Hong Kong University of Science and Technology, Guangzhou, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,5,30]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.44"},{"key":"e_1_2_2_2_1","first-page":"41","article-title":"Graph Clustering using Effective Resistance","volume":"94","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 Innovations in Theoretical Computer Science (ITCS), Vol. 94. 41.","journal-title":"Innovations in Theoretical Computer Science (ITCS)"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen Christian Borgs Jennifer Chayes John Hopcraft Vahab S Mirrokni and Shang-Hua Teng. 2007. Local computation of PageRank contributions. In WAM. 150--165.","DOI":"10.1007\/978-3-540-77004-6_12"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_2_5_1","unstructured":"Alexandr Andoni Robert Krauthgamer and Yosef Pogrow. 2018. On Solving Linear Systems in Sublinear Time. In Innovations in Theoretical Computer Science (ITCS)."},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Jean-Yves Audibert R\u00e9mi Munos and Csaba Szepesv\u00e1ri. 2007. Tuning bandit algorithms in stochastic environments. In ALT. 150--165.","DOI":"10.1007\/978-3-540-75225-7_15"},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Necdet Serhat Aybat and Mert G\u00fcrb\u00fczbalaban. 2017. Decentralized computation of effective resistances and acceleration of consensus algorithms. In GlobalSIP. 538--542.","DOI":"10.1109\/GlobalSIP.2017.8308701"},{"key":"e_1_2_2_8_1","volume-title":"Fast Bidirectional Probability Estimation in Markov Models. Advances in Neural Information Processing Systems (NeurIPS)","author":"Banerjee Siddhartha","year":"2015","unstructured":"Siddhartha Banerjee and Peter Lofgren. 2015. Fast Bidirectional Probability Estimation in Markov Models. Advances in Neural Information Processing Systems (NeurIPS) (2015), 1423--1431."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2008.4587840"},{"key":"e_1_2_2_10_1","volume-title":"Proceedings of the Annual ACM Symposium on Theory of computing (STOC). 47--55","author":"Bencz\u00far Andr\u00e1s A","year":"1996","unstructured":"Andr\u00e1s A Bencz\u00far and David R Karger. 1996. Approximating s-t minimum cuts in $tildeO(n^2)$ time. In Proceedings of the Annual ACM Symposium on Theory of computing (STOC). 47--55."},{"key":"e_1_2_2_11_1","volume-title":"Fast matrix computations for pairwise and columnwise commute times and Katz scores. Internet Mathematics","author":"Bonchi Francesco","year":"2012","unstructured":"Francesco Bonchi, Pooya Esfandiar, David F Gleich, Chen Greif, and Laks VS Lakshmanan. 2012. Fast matrix computations for pairwise and columnwise commute times and Katz scores. Internet Mathematics (2012), 73--112."},{"key":"e_1_2_2_12_1","unstructured":"Felix Broberg. 2020. Prediction Assisted Fully Dynamic All-Pairs Effective Resistance."},{"key":"e_1_2_2_13_1","volume-title":"The electrical resistance of a graph captures its commute and cover times. computational complexity","author":"Chandra Ashok K","year":"1996","unstructured":"Ashok K Chandra, Prabhakar Raghavan, Walter L Ruzzo, Roman Smolensky, and Prasoon Tiwari. 1996. The electrical resistance of a graph captures its commute and cover times. computational complexity (1996), 312--340."},{"key":"e_1_2_2_14_1","series-title":"SIAM J. Comput. (1976), 724--742","volume-title":"Finding minimum spanning trees","author":"Cheriton David","unstructured":"David Cheriton and Robert Endre Tarjan. 1976. Finding minimum spanning trees. SIAM J. Comput. (1976), 724--742."},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993674"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0708838104"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.69"},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the Annual ACM Symposium on Theory of computing (STOC). 343--352","author":"Cohen Michael B","year":"2014","unstructured":"Michael B Cohen, Rasmus Kyng, Gary L Miller, Jakub W Pachocki, Richard Peng, Anup B Rao, and Shen Chen Xu. 2014. Solving SDD linear systems in nearly $m\u0142og^1\/2n$ time. In Proceedings of the Annual ACM Symposium on Theory of computing (STOC). 343--352."},{"key":"e_1_2_2_19_1","volume-title":"Introduction to algorithms","author":"Cormen Thomas H","unstructured":"Thomas H Cormen, Charles E Leiserson, Ronald L Rivest, and Clifford Stein. 2009. Introduction to algorithms. MIT press."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432624"},{"key":"e_1_2_2_21_1","doi-asserted-by":"crossref","unstructured":"James W Demmel. 1997. Applied numerical linear algebra. SIAM.","DOI":"10.1137\/1.9781611971446"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/SMARTGRID.2010.5622040"},{"key":"e_1_2_2_23_1","volume-title":"Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics","author":"Fogaras D\u00e1niel","year":"2005","unstructured":"D\u00e1niel Fogaras, Bal\u00e1zs R\u00e1cz, K\u00e1roly Csalog\u00e1ny, and Tam\u00e1s Sarl\u00f3s. 2005. Towards scaling fully personalized pagerank: Algorithms, lower bounds, and experiments. Internet Mathematics (2005), 333--358."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_2_25_1","unstructured":"Gramoz Goranci Monika Henzinger and Pan Peng. 2018. Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs. In ESA."},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Linqi Guo Chen Liang and Steven H Low. 2017. Monotonicity properties and spectral characterization of power redistribution in cascading failures. In Allerton. 918--925.","DOI":"10.1109\/ALLERTON.2017.8262836"},{"key":"e_1_2_2_28_1","volume-title":"Topic-sensitive PageRank. In The Web Conference (WWW). 517--526","author":"Haveliwala Taher H","year":"2002","unstructured":"Taher H Haveliwala. 2002. Topic-sensitive PageRank. In The Web Conference (WWW). 517--526."},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI)","volume":"16","author":"Hayashi Takanori","year":"2016","unstructured":"Takanori Hayashi, Takuya Akiba, and Yuichi Yoshida. 2016. Efficient Algorithms for Spanning Tree Centrality. In Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI), Vol. 16. 3733--3739."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_2_31_1","volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2487--2503","author":"Jambulapati Arun","year":"2018","unstructured":"Arun Jambulapati and Aaron Sidford. 2018. Efficient $tildeO(n\/\u03b5)$ Spectral Sketches for the Laplacian and its Pseudoinverse. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2487--2503."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.16"},{"key":"e_1_2_2_34_1","volume-title":"Incremental commute time and its online applications. Pattern Recognition","author":"Dang Khoa Nguyen Lu","year":"2019","unstructured":"Nguyen Lu Dang Khoa, Yang Wang, and Sanjay Chawla. 2019. Incremental commute time and its online applications. Pattern Recognition (2019), 101--112."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623706"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-73435-2_21"},{"key":"e_1_2_2_37_1","doi-asserted-by":"crossref","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.","DOI":"10.1137\/1.9780898719628"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-26784-5_13"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2835776.2835823"},{"key":"e_1_2_2_40_1","volume-title":"Paul erdos is eighty","author":"Lov\u00e1sz L\u00e1szl\u00f3","year":"1993","unstructured":"L\u00e1szl\u00f3 Lov\u00e1sz. 1993. Random walks on graphs: a survey. Combinatorics, Paul erdos is eighty, Vol. 2, 4 (1993), 1--46."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2736277.2741125"},{"key":"e_1_2_2_43_1","unstructured":"Julian J McAuley and Jure Leskovec. 2012. Learning to discover social circles in ego networks.. In Advances in Neural Information Processing Systems (NeurIPS). 548--56."},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390241"},{"key":"e_1_2_2_45_1","volume-title":"Randomized algorithms","author":"Motwani Rajeev","unstructured":"Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized algorithms. Cambridge University Press."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004100033879"},{"key":"e_1_2_2_47_1","unstructured":"James William Nilsson. 2008. Electric circuits. Pearson Education India."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2019.2952653"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467361"},{"key":"e_1_2_2_50_1","unstructured":"Huaijun Qiu and Edwin R Hancock. 2005. Image Segmentation using Commute Times.. In BMVC. 929--938."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2007.1103"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457329"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509932"},{"key":"e_1_2_2_54_1","volume-title":"Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 335--343","author":"Sarkar Purnamrita","year":"2007","unstructured":"Purnamrita Sarkar and Andrew W Moore. 2007. A tractable approach to finding closest truncated-commute-time neighbors in large graphs. In Proceedings of the Conference on Uncertainty in Artificial Intelligence (UAI). 335--343."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390269"},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610497"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.14778\/3357377.3357379"},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2015.2498464"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2017.2654162"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCSI.2019.2929180"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_2_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2612184"},{"key":"e_1_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"e_1_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2006.70"},{"key":"e_1_2_2_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467243"},{"key":"e_1_2_2_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_2_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196920"},{"key":"e_1_2_2_70_1","volume-title":"Providence","author":"Wilmer EL","year":"2009","unstructured":"EL Wilmer, David A Levin, and Yuval Peres. 2009. Markov chains and mixing times. American Mathematical Soc., Providence (2009)."},{"key":"e_1_2_2_71_1","doi-asserted-by":"publisher","DOI":"10.1145\/3448016.3457298"},{"key":"e_1_2_2_72_1","volume-title":"Defining and Evaluating Network Communities Based on Ground-Truth. In International Conference on Data Mining (ICDM). 745--754","author":"Yang Jaewon","year":"2012","unstructured":"Jaewon Yang and Jure Leskovec. 2012. Defining and Evaluating Network Communities Based on Ground-Truth. In International Conference on Data Mining (ICDM). 745--754."},{"key":"e_1_2_2_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/3299869.3319886"},{"key":"e_1_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1401984"},{"key":"e_1_2_2_75_1","volume-title":"Michel Verleysen, Marco Saerens, et al.","author":"Yen Luh","year":"2005","unstructured":"Luh Yen, Denis Vanvyve, Fabien Wouters, Francc ois Fouss, Michel Verleysen, Marco Saerens, et al. 2005. Clustering using a random walk based distance measure. In ESANN. 317--324."},{"key":"e_1_2_2_76_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311916"},{"key":"e_1_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.14778\/2556549.2556554"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588696","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3588696","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:47:14Z","timestamp":1750178834000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3588696"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,5,26]]},"references-count":76,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,5,26]]}},"alternative-id":["10.1145\/3588696"],"URL":"https:\/\/doi.org\/10.1145\/3588696","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,5,26]]}}}