2025/12/05 by Dehong Zheng, Zhongzhi Zhang, Zheng, Dehong +1
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Complex Network Analysis Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms #Social and Information Networks (cs.SI)
paper · pdf · doi:10.48550/arxiv.2512.05460
openalex publication_date 2025/12/05 · openalex created_date 2025/12/09 · openalex updated_date 2026/07/28
The biharmonic distance is a fundamental metric on graphs that measures the dissimilarity between two nodes, capturing both local and global structures. It has found applications across various fields, including network centrality, graph clustering, and machine learning. These applications typically require efficient evaluation of pairwise biharmonic distances. However, existing algorithms remain computationally expensive. The state-of-the-art method attains an absolute-error guarantee epsilonabs with time complexity O(L5 / epsilonabs2), where L denotes the truncation length. In this work, we improve the complexity to O(L3 / epsilon2) under a relative-error guarantee epsilon via probe-driven random walks. We provide a relative-error guarantee rather than an absolute-error guarantee because biharmonic distances vary by orders of magnitude across node pairs. Since L is often very large in real-world networks (for example, L >= 103), reducing the L-dependence from the fifth to the third power yields substantial gains. Extensive experiments on real-world networks show that our method delivers 10x-1000x per-query speedups at matched relative error over strong baselines and scales to graphs with tens of millions of nodes.