7 papers
Classical and quantum spectral density estimation under local graph access
Rong-Hua Li, Meihao Liao, Yichun Yang
We study spectral density estimation for the normalized adjacency matrix of an unweighted graph under local access model. Previously, Cohen-Steiner et al. [KDD 2018] proposed an al…
Theoretically and Practically Efficient Resistance Distance Computation on Large Graphs
Yichun Yang, Longlong Lin, Rong-Hua Li +2
The computation of resistance distance is pivotal in a wide range of graph analysis applications, including graph clustering, link prediction, and graph neural networks. Despite it…
BD-Index: Scalable Biharmonic Distance Queries on Large Graphs via Divide-and-Conquer Indexing
Yueyang Pan, Meihao Liao, Rong-Hua Li
Biharmonic distance (\bd) is a powerful graph distance metric with many applications, including identifying critical links in road networks and mitigating over-squashing problem in…
Scalable and Provable Kemeny Constant Computation on Static and Dynamic Graphs: A 2-Forest Sampling Approach
Cheng Li, Meihao Liao, Rong-Hua Li +1
Kemeny constant, defined as the expected hitting time of random walks from a source node to a randomly chosen target node, is a fundamental metric in graph data management with man…
Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
Meihao Liao, Yueyang Pan, Rong-Hua Li +1
Resistance distance computation is a fundamental problem in graph analysis, yet existing random walk-based methods are limited to approximate solutions and suffer from poor efficie…
Improved Algorithms for Effective Resistance Computation on Graphs
Yichun Yang, Rong-Hua Li, Meihao Liao +1
Effective Resistance (ER) is a fundamental tool in various graph learning tasks. In this paper, we address the problem of efficiently approximating ER on a graph $\mathcal{G}=(\mat…