{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T19:06:25Z","timestamp":1779131185899,"version":"3.51.4"},"reference-count":83,"publisher":"Association for Computing Machinery (ACM)","issue":"3","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62372112"],"award-info":[{"award-number":["62372112"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61872093"],"award-info":[{"award-number":["61872093"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2026,5,18]]},"abstract":"<jats:p>\n                    <jats:italic toggle=\"yes\">Biharmonic distance<\/jats:italic>\n                    (BD) is a fundamental metric that measures the dissimilarity of a node pair\n                    <jats:italic toggle=\"yes\">s, t<\/jats:italic>\n                    in a graph, encapsulating rich local and global structural information. It has found applications across various fields, including network science, graph machine learning, and computational graphics. Existing algorithms for pairwise BD queries, including the state-of-the-art (SOTA) solution that relies on sampling a significant number of long random walks, are often computationally infeasible on large graphs. In this work, we propose two novel formulations of BD based on a pivot node, derived through novel proof techniques. These formulations enhance our theoretical understanding of BD and enable efficient approximation algorithms. Our first algorithm, B\n                    <jats:sc>ac<\/jats:sc>\n                    kP\n                    <jats:sc>ush<\/jats:sc>\n                    , is a deterministic method based on a newly established local\n                    <jats:italic toggle=\"yes\">pushback<\/jats:italic>\n                    operation designed for BD. The second algorithm, F\n                    <jats:sc>ast<\/jats:sc>\n                    W\n                    <jats:sc>alk<\/jats:sc>\n                    , is a randomized approach that estimates BD using \u2113-truncated absorbing random walks and counting their collisions. Lastly, we introduce F\n                    <jats:sc>ast<\/jats:sc>\n                    T\n                    <jats:sc>ree<\/jats:sc>\n                    , an algorithm inspired by a novel connection between BD and spanning trees. These algorithms, tailored to leverage more prior structural knowledge (particularly the relative connectivity to the pivot node), significantly improve efficiency and versatility compared to existing methods. Extensive empirical evaluations on benchmark networks with hundreds of millions of edges demonstrate that our algorithms can produce more accurate solutions than the SOTA methods over 100 times faster.\n                  <\/jats:p>","DOI":"10.1145\/3802058","type":"journal-article","created":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:19:16Z","timestamp":1779128356000},"page":"1-27","source":"Crossref","is-referenced-by-count":0,"title":["Fast Estimation of Pairwise Biharmonic Distance on Graphs"],"prefix":"10.1145","volume":"4","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5894-3130","authenticated-orcid":false,"given":"Changan","family":"Liu","sequence":"first","affiliation":[{"name":"College of Computer Science and Artificial Intelligence, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0009-6506-4885","authenticated-orcid":false,"given":"Xinna","family":"Zhou","sequence":"additional","affiliation":[{"name":"College of Computer Science and Artificial Intelligence, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0002-9123-6045","authenticated-orcid":false,"given":"Bo","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Artificial Intelligence, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8569-6347","authenticated-orcid":false,"given":"Ahad","family":"N. Zehmakan","sequence":"additional","affiliation":[{"name":"School of Computing, Australian National University, Canberra, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1260-2079","authenticated-orcid":false,"given":"Zhongzhi","family":"Zhang","sequence":"additional","affiliation":[{"name":"College of Computer Science and Artificial Intelligence, Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,5,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-55699-4_26"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463676.2465315"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777891"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/3216622.3216635"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAC.2012.2202052"},{"key":"e_1_2_1_7_1","first-page":"509","volume-title":"Science","volume":"286","author":"Barab\u00e1si Albert-L\u00e1szl\u00f3","year":"1999","unstructured":"Albert-L\u00e1szl\u00f3 Barab\u00e1si and R\u00e9ka Albert. 1999. Emergence of Scaling in Random Networks. Science, Vol. 286, 5439 (1999), 509-512."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0090283"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 41st International Conference on Machine Learning. 4077-4102","author":"Black Mitchell","year":"2024","unstructured":"Mitchell Black, Lucy Lin, Weng-Keen Wong, and Amir Nayyeri. 2024. Biharmonic Distance of Graphs and its Higher-order Variants: Theoretical Properties with Applications to Centrality and Clustering. In Proceedings of the 41st International Conference on Machine Learning. 4077-4102."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 40th International Conference on Machine Learning. 2528-2547","author":"Black Mitchell","year":"2023","unstructured":"Mitchell Black, Zhengchao Wan, Amir Nayyeri, and Yusu Wang. 2023. Understanding Oversquashing in GNNs through the Lens of Effective Resistance. In Proceedings of the 40th International Conference on Machine Learning. 2528-2547."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-0619-4"},{"key":"e_1_2_1_12_1","volume-title":"Proceedings of the 46th Annual Symposium on Theory of Computing. 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\/2 n$ Time. In Proceedings of the 46th Annual Symposium on Theory of Computing. 343-352."},{"key":"e_1_2_1_13_1","first-page":"77","volume-title":"First-passage Times in Complex Scale-invariant Media. Nature","volume":"450","author":"Condamin S.","year":"2007","unstructured":"S. Condamin, O. B\u00e9nichou, V. Tejedor, R. Voituriez, and J. Klafter. 2007. First-passage Times in Complex Scale-invariant Media. Nature, Vol. 450, 7166 (2007), 77-80."},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/3690624.3709298"},{"key":"e_1_2_1_15_1","doi-asserted-by":"crossref","unstructured":"P.G. Doyle and J.L. Snell. 1984. Random Walks and Electric Networks. Mathematical Association of America.","DOI":"10.5948\/UPO9781614440222"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1038\/s42005-022-00949-5"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 37th International Conference on Machine Learning. 2985-2995","author":"Fan Zhou","year":"2020","unstructured":"Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. 2020. Spectral Graph Matching and Regularized Quadratic Relaxations: Algorithm and Theory. In Proceedings of the 37th International Conference on Machine Learning. 2985-2995."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCNS.2015.2481138"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/120890971"},{"key":"e_1_2_1_20_1","volume-title":"Harvey","author":"Fung Wai Shing","year":"2010","unstructured":"Wai Shing Fung and Nicholas J. A. Harvey. 2010. Graph Sparsification by Edge-Connectivity and Random Spanning Trees. CoRR, Vol. abs\/1005.0265 (2010). arXiv:1005.0265"},{"key":"e_1_2_1_21_1","volume-title":"Spielman","author":"Gao Yuan","year":"2023","unstructured":"Yuan Gao, Rasmus Kyng, and Daniel A. Spielman. 2023. Robust and Practical Solution of Laplacian Equations by Approximate Elimination. CoRR, Vol. abs\/2303.00709 (2023). arXiv:2303.00709"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_2_1_23_1","volume-title":"Goldberg and Chris Harrelson","author":"Andrew","year":"2005","unstructured":"Andrew V. Goldberg and Chris Harrelson. 2005. Computing the Shortest Path: A Search Meets Graph Theory. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms. 156\u2013165."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3349164"},{"key":"e_1_2_1_25_1","volume-title":"Topic-sensitive PageRank. In Proceedings of the 11th International Conference on World Wide Web. 517\u2013526","author":"Haveliwala Taher H.","year":"2002","unstructured":"Taher H. Haveliwala. 2002. Topic-sensitive PageRank. In Proceedings of the 11th International Conference on World Wide Web. 517\u2013526."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/775152.775191"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00044"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.65.056101"},{"key":"e_1_2_1_30_1","first-page":"497","volume-title":"Annalen der Physik","volume":"148","author":"Kirchhoff G.","year":"1847","unstructured":"G. Kirchhoff. 1847. Ueber die Aufl\u00f6sung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Str\u00f6me gef\u00fchrt wird. Annalen der Physik, Vol. 148, 12 ( 1847), 497-508."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01164627"},{"key":"e_1_2_1_32_1","first-page":"21618","volume-title":"Proceedings of the 35th International Conference on Neural Information Processing Systems","volume":"34","author":"Kreuzer Devin","year":"2021","unstructured":"Devin Kreuzer, Dominique Beaini, Will Hamilton, Vincent L\u00e9tourneau, and Prudencio Tossou. 2021. Rethinking Graph Transformers With Spectral Attention. Proceedings of the 35th International Conference on Neural Information Processing Systems, Vol. 34, 21618-21629."},{"key":"e_1_2_1_33_1","first-page":"655","article-title":"A Self-avoiding Random Walk","volume":"47","author":"Gregory Lawler","year":"1980","unstructured":"Lawler and F. Gregory. 1980. A Self-avoiding Random Walk. Duke Mathematical Journal, Vol. 47, 3 (1980), 655-693.","journal-title":"Duke Mathematical Journal"},{"key":"e_1_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Lawler and F. Gregory. 2012. Intersections of Random Walks. Springer New York.","DOI":"10.1007\/978-1-4614-5972-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2898361"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588922"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3654936"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.4754735"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805964.1805971"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2026.115765"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2025.3621520"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3637528.3671856"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3309987"},{"key":"e_1_2_1_44_1","first-page":"353","article-title":"Random Walks on Graphs: A Survey. In Combinatorics, Paul Erd\u0151s is Eighty. Vol. 2","author":"Lov\u00e1sz L.","year":"1996","unstructured":"L. Lov\u00e1sz. 1996. Random Walks on Graphs: A Survey. In Combinatorics, Paul Erd\u0151s is Eighty. Vol. 2. J\u00e1nos Bolyai Mathematical Society, 353-398.","journal-title":"J\u00e1nos Bolyai Mathematical Society"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2016.06.007"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732977.2732978"},{"key":"e_1_2_1_47_1","first-page":"795","article-title":"Shortest Path Tree Sampling for Landmark Selection in Large Networks","volume":"5","author":"Maliah Shlomi","year":"2017","unstructured":"Shlomi Maliah, Rami Puzis, and Guy Shani. 2017. Shortest Path Tree Sampling for Landmark Selection in Large Networks. Journal of Complex Networks, Vol. 5, 5 (2017), 795-815.","journal-title":"Journal of Complex Networks"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2015.103"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(96)00032-3"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-8655(94)90095-7"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01990530"},{"key":"e_1_2_1_52_1","volume-title":"Networks","author":"Newman Mark","unstructured":"Mark Newman. 2018. Networks. Oxford University Press."},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196913"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467361"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/9\/6\/175"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1390156.1390269"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1080\/0025570X.1987.11977274"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2925610"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1038\/srep34944"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys266"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_2_1_62_1","volume-title":"International Conference on Learning Representations.","author":"Topping Jake","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 International Conference on Learning Representations."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1145\/2063576.2063834"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3366423.3380026"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.120.084101"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.5555\/3294771.3294780"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.14778\/3021924.3021936"},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098072"},{"key":"e_1_2_1_69_1","first-page":"440","volume-title":"Nature","volume":"393","author":"Watts Duncan J","year":"1998","unstructured":"Duncan J Watts and Steven H Strogatz. 1998. Collective Dynamics of `Small-world' Networks. Nature, Vol. 393, 6684 (1998), 440-442."},{"key":"e_1_2_1_70_1","unstructured":"Y. Wei R. Li and W. Yang. 2021. Biharmonic Distance of Graphs. arXiv preprint arXiv:2110.02656v1 (2021)."},{"key":"e_1_2_1_71_1","volume-title":"Approximating Single-source Personalized PageRank with Absolute Error Guarantees. In 27th International Conference on Database Theory","volume":"290","author":"Wei Zhewei","year":"2024","unstructured":"Zhewei Wei, Ji-Rong Wen, and Mingji Yang. 2024. Approximating Single-source Personalized PageRank with Absolute Error Guarantees. In 27th International Conference on Database Theory, Vol. 290. 9:1-9:19."},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2024.3376000"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485447.3511959"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3588696"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2018\/503"},{"key":"e_1_2_1_77_1","volume-title":"Biharmonic Distance and Performance of Second-Order Consensus Networks with Stochastic Disturbances. In Annual American Control Conference. 4943-4950","author":"Yi Yuhao","year":"2018","unstructured":"Yuhao Yi, Bingjia Yang, Zhongzhi Zhang, and Stacy Patterson. 2018b. Biharmonic Distance and Performance of Second-Order Consensus Networks with Stochastic Disturbances. In Annual American Control Conference. 4943-4950."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2021.3127272"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.14778\/2311906.2311916"},{"key":"e_1_2_1_80_1","volume-title":"Pruning Based Distance Sketches with Provable Guarantees on Random Graphs. In The World Wide Web Conference. 2301-2311","author":"Zhang Hongyang","year":"2019","unstructured":"Hongyang Zhang, Huacheng Yu, and Ashish Goel. 2019. Pruning Based Distance Sketches with Provable Guarantees on Random Graphs. In The World Wide Web Conference. 2301-2311."},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/44\/7\/075102"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.85.011106"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3543507.3583243"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,5,18]],"date-time":"2026-05-18T18:21:56Z","timestamp":1779128516000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,5,18]]},"references-count":83,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,5,18]]}},"alternative-id":["10.1145\/3802058"],"URL":"https:\/\/doi.org\/10.1145\/3802058","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,5,18]]}}}