Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications

AmirMahdi Ahmadinejad, Arun Jambulapati, Amin Saberi, Aaron Sidford

TL;DR

This paper presents the first nearly linear time algorithms for fundamental problems in Perron-Frobenius theory, specifically computing the "Perron vector" (the top eigenvector of a non-negative matrix) and solving linear systems involving M-matrices. By cleverly reducing these problems to well-studied diagonally dominant systems, the authors provide a massive theoretical speedup for applications ranging from economic modeling to graph-based machine learning.

What Problem Does This Paper Address?

The Perron-Frobenius theorem is a pillar of linear algebra, stating that any non-negative square matrix has a unique largest real eigenvalue with a corresponding eigenvector whose entries are all positive. This "Perron vector" is essential for understanding Markov chains, ranking web pages (like PageRank), and analyzing social networks.

Despite its importance, computing this vector or solving linear systems for related "M-matrices" (a generalization of graph Laplacians) has historically been slow. Previous algorithms typically required quadratic time ($O(n^2)$) or had runtimes that scaled poorly with the "condition number"—a measure of how numerically unstable the problem is. This paper aims to bridge that gap, providing algorithms that run in time nearly proportional to the number of non-zero entries in the matrix ($m$), with only a logarithmic dependence on accuracy and stability.

Methods

The authors' primary strategy is a reduction to RCDD systems. Row-Column Diagonally Dominant (RCDD) matrices are a class of matrices that can already be solved in nearly linear time. The challenge is that M-matrices aren't RCDD by default.

The paper identifies a "chicken and egg" problem: to solve an M-matrix system, you ideally need the Perron vector to scale it into an RCDD form; but to find the Perron vector, you often need to solve M-matrix systems.

To break this cycle, they introduce a novel iterative framework:

  1. Shift-and-Invert Preconditioning: They consider a "shifted" version of the matrix ($M + \alpha I$). When $\alpha$ is very large, the matrix is easily solvable.
  2. The Scaling Loop: They start with a large $\alpha$ and find a scaling. They then repeatedly halve $\alpha$, using the solution from the previous step as a "preconditioner" to solve the next, more difficult step.
  3. MMatrix-Decide: They develop a "decision" procedure that can either certify a matrix is an M-matrix by finding its scaling or provide a proof that it isn't.
  4. Doubling Scheme: Since the "condition number" (the difficulty of the problem) is often unknown, they use a doubling strategy—starting with a small guess for the difficulty and doubling it until the algorithm succeeds.

Datasets

As a theoretical computer science paper, this work does not use empirical datasets for training or evaluation. Instead, it provides rigorous mathematical proofs of algorithmic complexity. The "evaluation" is the reduction of the asymptotic runtime from $O(n^2)$ or $O(poly(K))$ to $\tilde{O}(m)$.

Key Insights and Ideas

  • Scaling is Everything: The core insight is that every invertible M-matrix is just an RCDD matrix in disguise. If you find the right diagonal scaling (using the left and right Perron vectors), the problem becomes easy.
  • Multiplicative Closeness: The authors prove that if you shift an M-matrix by two different values of $\alpha$ that are close to each other, the inverse of one is an excellent approximation (preconditioner) for the other. This justifies the "halving $\alpha$" approach.
  • Escaping the Circularity: By showing that you only need approximate Perron vectors to achieve RCDD-ness, they allow the algorithm to converge without needing the exact answer upfront.
  • Generalization of Laplacians: The work shows that many tools developed for symmetric graph Laplacians can be extended to the much broader, asymmetric world of M-matrices.

Key Results

  • Perron Vector Computation: The first algorithm to compute the top eigenvector of a non-negative irreducible matrix in $\tilde{O}(m)$ time.
  • M-Matrix Solver: A nearly linear time solver for systems of the form $(sI - A)x = b$, where $A$ is non-negative.
  • Katz Centrality: Improved runtime for computing this social network influence measure, which was previously difficult to compute for large graphs compared to PageRank.
  • Graph Kernels: They provide a faster way to compute "random walk kernels," which are used to measure the similarity between two graphs in bioinformatics and NLP.
  • Leontief Economies: A faster method for checking the "Hawkins-Simons condition," which determines if an economic model can actually produce enough to meet demand.

Limitations and Future Work

  • Theoretical Constants: While the "nearly linear" complexity is a breakthrough, the "polylogarithmic" factors and hidden constants in the $O$ notation might be large, meaning the algorithm may need further optimization for practical, real-world use.
  • Dependency on RCDD Solvers: The algorithm relies on existing RCDD solvers as a "black box." These solvers are themselves quite complex to implement.
  • Future Directions: The authors suggest that these new linear algebraic primitives could be used to solve even more complex combinatorial problems on directed graphs, similar to how Laplacian solvers revolutionized undirected graph algorithms.

Summary updated

Abstract

In this paper we provide nearly linear time algorithms for several problems closely associated with the classic Perron-Frobenius theorem, including computing Perron vectors, i.e. entrywise non-negative eigenvectors of non-negative matrices, and solving linear systems in asymmetric M-matrices, a generalization of Laplacian systems. The running times of our algorithms depend nearly linearly on the input size and polylogarithmically on the desired accuracy and problem condition number. Leveraging these results we also provide improved running times for a broader range of problems including computing random walk-based graph kernels, computing Katz centrality, and more. The running times of our algorithms improve upon previously known results which either depended polynomially on the condition number of the problem, required quadratic time, or only applied to special cases. We obtain these results by providing new iterative methods for reducing these problems to solving linear systems in Row-Column Diagonally Dominant (RCDD) matrices. Our methods are related to the classic shift-and-invert preconditioning technique for eigenvector computation and constitute the first alternative to the result in Cohen et al. (2016) for reducing stationary distribution computation and solving directed Laplacian systems to solving RCDD systems.
BibTeX
@inproceedings{ahmadinejad2019perron,
  author = {AmirMahdi Ahmadinejad and Arun Jambulapati and Amin Saberi and Aaron Sidford},
  title = {{Perron-Frobenius Theory in Nearly Linear Time: Positive Eigenvectors, M-matrices, Graph Kernels, and Other Applications}},
  booktitle = {SODA},
  year = {2019},
  doi = {10.1137/1.9781611975482.85},
}

Loading related content...

Figure