{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:59:35Z","timestamp":1775638775602,"version":"3.50.1"},"reference-count":70,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2025,2,10]],"date-time":"2025-02-10T00:00:00Z","timestamp":1739145600000},"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":[[2025,2,10]]},"abstract":"<jats:p>\n                    In this paper, we study a problem of index maintenance on evolving graphs for effective resistance computation. Unlike an existing matrices-based index, we show that the index can be efficiently maintained by directly preserving samples of random walks and loop-erased walks. This approach not only enables efficient storage and rapid query response but also supports effective maintenance. We propose a novel approach to convert edge updates into\n                    <jats:italic toggle=\"yes\">landmark<\/jats:italic>\n                    node updates. Building upon this, we present two new update algorithms for random walk and loop-erased walk samples respectively. Both algorithms update samples without requiring complete resampling, ensuring accuracy and high efficiency. A particularly challenging and innovative technique involves updating loop-erased walks. Here we develop a novel and powerful cycle decomposition technique for loop-erased walks, enabling us to update samples at the cycle level rather than the node level, significantly enhancing efficiency. Furthermore, we show that both of our methods achieve an \u00d5 (1) time complexity per edge update in real-world graphs under a mild assumption. We conduct extensive experiments using 10 large real-world datasets to evaluate the performance of our approaches. The results show that our best algorithm can be up to two orders of magnitude faster than the baseline methods.\n                  <\/jats:p>","DOI":"10.1145\/3709686","type":"journal-article","created":{"date-parts":[[2025,2,11]],"date-time":"2025-02-11T15:45:06Z","timestamp":1739288706000},"page":"1-27","source":"Crossref","is-referenced-by-count":2,"title":["Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs"],"prefix":"10.1145","volume":"3","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":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4496-8518","authenticated-orcid":false,"given":"Cheng","family":"Li","sequence":"additional","affiliation":[{"name":"Beijing Institute of Technology, Beijing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,2,11]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Ittai Abraham David Durfee Ioannis Koutis Sebastian Krinninger and Richard Peng. 2016. On Fully Dynamic Graph Sparsifiers. In FOCS. 335--344.","DOI":"10.1109\/FOCS.2016.44"},{"key":"e_1_2_1_2_1","volume-title":"A random graph model for power law graphs. Experimental mathematics","author":"Aiello William","year":"2001","unstructured":"William Aiello, Fan Chung, and Linyuan Lu. 2001. A random graph model for power law graphs. Experimental mathematics, Vol. 10, 1 (2001), 53--66."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"Reid Andersen Christian Borgs Jennifer T. Chayes John E. Hopcroft Vahab S. Mirrokni and Shang-Hua Teng. 2007. Local Computation of PageRank Contributions. In WAW. 150--165.","DOI":"10.1007\/978-3-540-77004-6_12"},{"key":"e_1_2_1_4_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_1_5_1","first-page":"1","article-title":"Approximation of the Diagonal of a Laplacian's Pseudoinverse for Complex Network Analysis","volume":"173","author":"Angriman Eugenio","year":"2020","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, Vol. 173. 6:1--6:24.","journal-title":"ESA"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-017-0771-3"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.14778\/1929861.1929864"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2020.04.006"},{"key":"e_1_2_1_9_1","volume-title":"Graphs and matrices","author":"Bapat Ravindra B","unstructured":"Ravindra B Bapat. 2010. Graphs and matrices. Vol. 27."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-022-00860-5"},{"key":"e_1_2_1_11_1","doi-asserted-by":"crossref","unstructured":"B\u00e9la Bollob\u00e1s and B\u00e9la Bollob\u00e1s. 1998. Random graphs.","DOI":"10.1007\/978-1-4612-0619-4_7"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2013.05.003"},{"key":"e_1_2_1_13_1","first-page":"1","article-title":"Effective Resistances in Non-Expander Graphs","volume":"274","author":"Cai Dongrun","year":"2023","unstructured":"Dongrun Cai, Xue Chen, and Pan Peng. 2023. Effective Resistances in Non-Expander Graphs. In ESA, Vol. 274. 29:1--29:18.","journal-title":"ESA"},{"key":"e_1_2_1_14_1","doi-asserted-by":"crossref","unstructured":"Li Chen Rasmus Kyng Yang P. Liu Simon Meierhans and Maximilian Probst Gutenberg. 2024. Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection SCCs s-t Shortest Path and Minimum-Cost Flow. In STOC. 1165--1173.","DOI":"10.1145\/3618260.3649745"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/jgt.22887"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2019.09.017"},{"key":"e_1_2_1_17_1","first-page":"95","article-title":"A growth model, a game, an algebra, Lagrange inversion, and characteristic classes","volume":"49","author":"Diaconis Persi","year":"1991","unstructured":"Persi Diaconis and William Fulton. 1991. A growth model, a game, an algebra, Lagrange inversion, and characteristic classes. Rend. Sem. Mat. Univ. Pol. Torino, Vol. 49, 1 (1991), 95--119.","journal-title":"Rend. Sem. Mat. Univ. Pol. Torino"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"David Durfee Yu Gao Gramoz Goranci and Richard Peng. 2019. Fully dynamic spectral vertex sparsifiers and applications. In STOC. 914--925.","DOI":"10.1145\/3313276.3316379"},{"key":"e_1_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Rajat Vadiraj Dwaraknath Ishani Karmarkar and Aaron Sidford. 2023. Towards Optimal Effective Resistance Estimation. In NIPS.","DOI":"10.52202\/075280-2575"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Katherine Fitch and Naomi Ehrich Leonard. 2013. Information centrality and optimal leader selection in noisy networks. In CDC. 7510--7515.","DOI":"10.1109\/CDC.2013.6761082"},{"key":"e_1_2_1_21_1","doi-asserted-by":"crossref","unstructured":"Yu Gao Yang P. Liu and Richard Peng. 2021. Fully Dynamic Electrical Flows: Sparse Maxflow Faster Than Goldberg-Rao. In FOCS. 516--527.","DOI":"10.1109\/FOCS52979.2021.00058"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/140976649"},{"key":"e_1_2_1_23_1","unstructured":"Joseph E. Gonzalez Reynold S. Xin Ankur Dave Daniel Crankshaw Michael J. Franklin and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In OSDI. 599--613."},{"key":"e_1_2_1_24_1","first-page":"1","article-title":"Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs","volume":"112","author":"Goranci Gramoz","year":"2018","unstructured":"Gramoz Goranci, Monika Henzinger, and Pan Peng. 2018. Dynamic Effective Resistances and Approximate Schur Complement on Separable Graphs. In ESA, Vol. 112. 40:1--40:15.","journal-title":"ESA"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00612"},{"key":"e_1_2_1_26_1","unstructured":"Takanori Hayashi Takuya Akiba and Yuichi Yoshida. 2016. Efficient Algorithms for Spanning Tree Centrality. In IJCAI. 3733--3739."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-023-01154-8"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588705"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"Glen Jeh and Jennifer Widom. 2002. SimRank: a measure of structural-context similarity. In KDD. 538--543.","DOI":"10.1145\/775047.775126"},{"key":"e_1_2_1_30_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_1_31_1","doi-asserted-by":"crossref","unstructured":"Rasmus Kyng and Sushant Sachdeva. 2016. Approximate Gaussian Elimination for Laplacians - Fast Sparse and Simple. In FOCS. 573--582.","DOI":"10.1109\/FOCS.2016.68"},{"key":"e_1_2_1_32_1","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. http:\/\/snap.stanford.edu\/data."},{"key":"e_1_2_1_33_1","doi-asserted-by":"crossref","unstructured":"Huan Li Richard Peng Liren Shan Yuhao Yi and Zhongzhi Zhang. 2019. Current Flow Group Closeness Centrality for Complex Networks. In WWW. 961--971.","DOI":"10.1145\/3308558.3313490"},{"key":"e_1_2_1_34_1","volume-title":"Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs. Full version: https:\/\/github.com\/mhliao0516\/LEindex","author":"Liao Meihao","year":"2024","unstructured":"Meihao Liao, Cheng Li, Rong-Hua Li, and Guoren Wang. 2024a. Efficient Index Maintenance for Effective Resistance Computation on Evolving Graphs. Full version: https:\/\/github.com\/mhliao0516\/LEindex (2024)."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588922"},{"key":"e_1_2_1_36_1","doi-asserted-by":"crossref","unstructured":"Meihao Liao Rong-Hua Li Qiangqiang Dai and Guoren Wang. 2022. Efficient Personalized PageRank Computation: A Spanning Forests Sampling Based Approach. In SIGMOD. 2048--2061.","DOI":"10.1145\/3514221.3526140"},{"key":"e_1_2_1_37_1","first-page":"133","article-title":"Efficient and Provable Effective Resistance Computation on Large Graphs","volume":"2","author":"Liao Meihao","year":"2024","unstructured":"Meihao Liao, Junjie Zhou, Rong-Hua Li, Qiangqiang Dai, Hongyang Chen, and Guoren Wang. 2024b. Efficient and Provable Effective Resistance Computation on Large Graphs: An Index-based Approach. Proc. ACM Manag. Data, Vol. 2, 3 (2024), 133.","journal-title":"An Index-based Approach. Proc. ACM Manag. Data"},{"key":"e_1_2_1_38_1","volume-title":"Sukumar","author":"Lim Seung-Hwan","year":"2015","unstructured":"Seung-Hwan Lim, Sangkeun Lee, Gautam Ganesh, Tyler C. Brown, and Sreenivas R. Sukumar. 2015. Graph Processing Platforms at Scale: Practices and Experiences. In ISPAS. 42--51."},{"key":"e_1_2_1_39_1","doi-asserted-by":"crossref","unstructured":"Yang Liu Chuan Zhou Shirui Pan Jia Wu Zhao Li Hongyang Chen and Peng Zhang. 2023. CurvDrop: A Ricci Curvature Based Approach to Prevent Graph Neural Networks from Over-Smoothing and Over-Squashing. In WWW. 221--230.","DOI":"10.1145\/3543507.3583269"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.006"},{"key":"e_1_2_1_41_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_1_42_1","first-page":"1023","article-title":"Computing Personalized PageRank Quickly by Exploiting Graph Structures","volume":"7","author":"Maehara Takanori","year":"2014","unstructured":"Takanori Maehara, Takuya Akiba, Yoichi Iwata, and Ken-ichi Kawarabayashi. 2014. Computing Personalized PageRank Quickly by Exploiting Graph Structures. VLDB, Vol. 7, 12 (2014), 1023--1034.","journal-title":"VLDB"},{"key":"e_1_2_1_43_1","volume-title":"Proceedings of the international multiconference of engineers and computer scientists","volume":"1","author":"Niwattanakul Suphakit","year":"2013","unstructured":"Suphakit Niwattanakul, Jatsada Singthongchai, Ekkachai Naenudorn, and Supachanun Wanapu. 2013. Using of Jaccard coefficient for keywords similarity. In Proceedings of the international multiconference of engineers and computer scientists, Vol. 1. 380--384."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1093\/comnet\/cnx021"},{"key":"e_1_2_1_45_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_1_46_1","doi-asserted-by":"crossref","unstructured":"Yusuf Yigit Pilavci Pierre-Olivier Amblard Simon Barthelm\u00e9 and Nicolas Tremblay. 2020. Smoothing Graph Signals via Random Spanning Forests. In ICASSP. 5630--5634.","DOI":"10.1109\/ICASSP40776.2020.9054497"},{"key":"e_1_2_1_47_1","volume-title":"Graph Tikhonov Regularization and Interpolation Via Random Spanning Forests","author":"Pilavci Yusuf Yigit","year":"2021","unstructured":"Yusuf Yigit Pilavci, Pierre-Olivier Amblard, Simon Barthelm\u00e9, and Nicolas Tremblay. 2021. Graph Tikhonov Regularization and Interpolation Via Random Spanning Forests. IEEE Trans. Signal Inf. Process. over Networks (2021), 359--374."},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.3150\/16-BEJ916"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s13278-023-01137-1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-12691-3_54"},{"key":"e_1_2_1_51_1","doi-asserted-by":"crossref","unstructured":"Sushant Sachdeva and Yibin Zhao. 2023. A Simple and Efficient Parallel Laplacian Solver. In SPAA. 315--325.","DOI":"10.1145\/3558481.3591101"},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Scott Sallinen Juntong Luo and Matei Ripeanu. 2023. Real-Time PageRank on Dynamic Graphs. In HPDC. 239--251.","DOI":"10.1145\/3588195.3593004"},{"key":"e_1_2_1_53_1","doi-asserted-by":"crossref","unstructured":"Aaron Schild. 2018. An almost-linear time algorithm for uniform random spanning tree generation. In STOC. 214--227.","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_2_1_54_1","volume-title":"Cheung","author":"Shi Jieming","year":"2014","unstructured":"Jieming Shi, Nikos Mamoulis, Dingming Wu, and David W. Cheung. 2014. Density-based place clustering in geo-social networks. In SIGMOD. 99--110."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2723716"},{"key":"e_1_2_1_56_1","doi-asserted-by":"crossref","unstructured":"Ali Kemal Sinop Lisa Fawcett Sreenivas Gollapudi and Kostas Kollias. 2021. Robust Routing Using Electrical Flows. In SIGSPATIAL. 282--292.","DOI":"10.1145\/3474717.3483961"},{"key":"e_1_2_1_57_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. 563--568."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01046996"},{"key":"e_1_2_1_59_1","volume-title":"Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein.","author":"Topping Jake","year":"2022","unstructured":"Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. 2022. Understanding over-squashing and bottlenecks on graphs via curvature. In ICLR."},{"key":"e_1_2_1_60_1","doi-asserted-by":"crossref","unstructured":"Oskar van Rest Sungpack Hong Jinha Kim Xuming Meng and Hassan Chafi. 2016. PGQL: a property graph query language. In GRADES. 7.","DOI":"10.1145\/2960414.2960421"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_62_1","doi-asserted-by":"crossref","unstructured":"Jim Webber. 2012. A programmatic introduction to Neo4j. In SPLASH. 217--218.","DOI":"10.1145\/2384716.2384777"},{"key":"e_1_2_1_63_1","doi-asserted-by":"crossref","unstructured":"David Bruce Wilson. 1996. Generating Random Spanning Trees More Quickly than the Cover Time. In STOC. 296--303.","DOI":"10.1145\/237814.237880"},{"key":"e_1_2_1_64_1","doi-asserted-by":"crossref","unstructured":"Renchi Yang Jieming Shi Yin Yang Keke Huang Shiqi Zhang and Xiaokui Xiao. 2021. Effective and Scalable Clustering on Massive Attributed Graphs. In WWW. 3675--3687.","DOI":"10.1145\/3442381.3449875"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588696"},{"key":"e_1_2_1_66_1","doi-asserted-by":"crossref","unstructured":"Minji Yoon Woojeong Jin and U Kang. 2018. Fast and Accurate Random Walk with Restart on Dynamic Graphs with Guarantees. In WWW. 409--418.","DOI":"10.1145\/3178876.3186107"},{"key":"e_1_2_1_67_1","doi-asserted-by":"crossref","unstructured":"Hongyang Zhang Peter Lofgren and Ashish Goel. 2016. Approximate Personalized PageRank on Dynamic Graphs. In KDD. 1315--1324.","DOI":"10.1145\/2939672.2939804"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Yanping Zheng Hanzhi Wang Zhewei Wei Jiajun Liu and Sibo Wang. 2022. Instant Graph Neural Networks for Dynamic Graphs. In KDD. 2605--2615.","DOI":"10.1145\/3534678.3539352"},{"key":"e_1_2_1_69_1","doi-asserted-by":"crossref","unstructured":"Kai Zhou Tomasz P. Michalak Marcin Waniek Talal Rahwan and Yevgeniy Vorobeychik. 2019. Attacking Similarity-Based Link Prediction in Social Networks. In AAMAS. 305--313.","DOI":"10.65109\/JOOP7570"},{"key":"e_1_2_1_70_1","first-page":"718","article-title":"Graph Clustering Based on Structural\/Attribute Similarities","volume":"2","author":"Zhou Yang","year":"2009","unstructured":"Yang Zhou, Hong Cheng, and Jeffrey Xu Yu. 2009. Graph Clustering Based on Structural\/Attribute Similarities. VLDB, Vol. 2, 1 (2009), 718--729.","journal-title":"VLDB"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709686","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3709686","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T18:22:44Z","timestamp":1774981364000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3709686"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,2,10]]},"references-count":70,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,2,10]]}},"alternative-id":["10.1145\/3709686"],"URL":"https:\/\/doi.org\/10.1145\/3709686","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,2,10]]}}}