Minimizing Total Biharmonic Distance in Large Graphs via Link Recommendation

The total biharmonic distance, which is the sum of the biharmonic distance between every pair of nodes in a network, is a key metric for evaluating network connectivity and robustness. In this paper, we study the problem of minimizing the total biharmonic distance by adding 𝑘 nonexistent edges for a given graph 𝐺 and budget 𝑘. The problem is computationally challenging. We show that the objective function of the problem is monotone but not supermodular. To solve this problem, we propose simple greedy algorithms with cubic time complexity. To mitigate the high time complexity of these greedy algorithms, we apply several techniques, including the projection method, the Laplacian solver, and convex hull approximation. These techniques reduce the time complexity of our proposed algorithms from cubic to nearly linear while providing error guarantees. Finally, extensive experiments on real datasets demonstrate both the efficiency and effectiveness of our proposed algorithms.

This paper has been published in Proceedings of the 32nd ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (KDD '26).