  The pseudo-inverse of a graph Laplacian matrix, denoted as $L^\dagger$, finds
extensive application in various graph analysis tasks. Notable examples include
the calculation of electrical closeness centrality, determination of Kemeny's
constant, and evaluation of resistance distance. However, existing algorithms
for computing $L^\dagger$ are often computationally expensive when dealing with
large graphs. To overcome this challenge, we propose novel solutions for
approximating $L^\dagger$ by establishing a connection with the inverse of a
Laplacian submatrix $L_v$. This submatrix is obtained by removing the $v$-th
row and column from the original Laplacian matrix $L$. The key advantage of
this connection is that $L_v^{-1}$ exhibits various interesting combinatorial
interpretations. We present two innovative interpretations of $L_v^{-1}$ based
on spanning trees and loop-erased random walks, which allow us to develop
efficient sampling algorithms. Building upon these new theoretical insights, we
propose two novel algorithms for efficiently approximating both electrical
closeness centrality and Kemeny's constant. We extensively evaluate the
performance of our algorithms on five real-life datasets. The results
demonstrate that our novel approaches significantly outperform the
state-of-the-art methods by several orders of magnitude in terms of both
running time and estimation errors for these two graph analysis tasks. To
further illustrate the effectiveness of electrical closeness centrality and
Kemeny's constant, we present two case studies that showcase the practical
applications of these metrics.
