Mixing Time Matters: Accelerating Effective Resistance Estimation via Bidirectional Method

Guanyu Cui, Hanzhi Wang, Zhewei Wei

We study the problem of efficiently approximating the \textit{effective resistance} (ER) on undirected graphs, where ER is a widely used node proximity measure with applications in…