7 papers
An algorithm for counting spanning trees by -regularized resistance
Rong-Hua Li, Yichun Yang
We study the basic problem of approximating the number of spanning trees of a graph. For a graph with vertices, edges, We propose an algorithm that approximates the number…
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…
Fast counting and sampling for ferromagnetic two-spin systems
Weiming Feng, Heng Guo, Yichun Yang
We introduce two new models equivalent to ferromagnetic two-spin systems: a weighted subgraph model and a random cluster type model. Using these new connections, we obtain an effic…
An Exponential Lower Bound for Spectral Density Estimation on Unweighted Graphs
Pan Peng, Yuyang Wang, Joy Qiping Yang +1
We study lower bounds for estimating the spectral density of the normalized adjacency matrix of a graph. Previously, Cohen-Steiner et al. [KDD 2018] proposed an algorithm for $\var…
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…
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…