Low Complexity Computation of the Pseudo-Inverse of a Digraph Laplacian [conference paper]

Conference

XXI Householder Symposium on Numerical Linear Algebra - June 14, 2020

Authors

Daniel Boley (professor)

Abstract

The pseudo-inverse of the graph Laplacian matrix is often the basis to compute many aggregate quantities related to graphs. Recently it has been shown that a non-symmetric Laplacian derived for a strongly connected directed graph can be used to obtain many similar properties for a directed graph. In [2], it was shown how the pseudo-inverse of the Laplacian with the right scaling leads directly to the average one-way hitting times and average round-trip commute times for a random walk on the digraph. The symmetric part of the pseudo-inverse is a Gram matrix yielding an embedding in Euclidean space where the distance squared between two nodes is directly proportional to the round-trip commute time. It was shown in [7, 3] how this same pseudo-inverse can be used to obtain a third order tensor with entries N (i,j,k) equal to the average number of visits to intermediate mode j in a random walk starting at node i and ending at node k, as well as the probability P (i,j,k) of passing node j at all in those same random walks. All these quantities lead directly to a ranking of nodes based on their proximity to other nodes(random walk centrality), random-walk betweeness measures, and the centrality with respect to propagation of trust or influence through a social network [4].

In all these cases, the quantities of interest can be computed directly from the the pseudo-inverse of the digraph Laplacian. But this computation itself presents a challenge. A naive computation based on the SVD would cost O (n3) which would be prohibitively expensive for even modestly sized graphs. Using mix of a careful ordering of the vertices and carefully crafted preconditioners for iterative methods, a recent result [5, 6] showed it is theoretically possible to find this inverse in almost linear time per column. But these results involve very special methods whose practical implementation remains open.

Here we discuss a complexity bound for the computation of the Moore-Penrose pseudo-inverse that depends entirely on ”off-the-shelf” iterative matrix methods well-established in numerical computation. Using these methods, we can arrive at a cost bound that is essentially linear in the number of edges in the graph augmented by a coefficient related to how easily the graph splits. For strongly connected digraphs that satisfy a power-law distribution of the degrees and that are not easily split, this leads to methods to obtain the pseudo-inverse that is almost quadratic in the dimension, i.e., constant time per matrix entry, which is the best one can attain. While the methods are not the most modern ones to accomplish the task and hence might not be the most efficient, they enjoy relatively straightforward bounds on the time complexity. Hence it is a good example of a theoretical cost bound which has a corresponding practical algorithm.

Link to full paper

Low Complexity Computation of the Pseudo-Inverse of a Digraph Laplacian

Keywords

numerical computation