Non-backtracking spectra of weighted inhomogeneous random graphs

  • Ludovic Stephan

    École Polytechnique Fédérale de Lausanne, Switzerland
  • Laurent Massoulié

    PSL Research University, Paris, France
Non-backtracking spectra of weighted inhomogeneous random graphs cover
Download PDF

This article is published open access under our Subscribe to Open model.


We study a model of random graphs where each edge is drawn independently (but not necessarily identically distributed) from the others, and then assigned a random weight. When the mean degree of such a graph is low, it is known that the spectrum of the adjacency matrix AA deviates significantly from that of its expected value EA\mathbb{E} A .

In contrast, we show that over a wide range of parameters the top eigenvalues of the non-backtracking matrix BB – a matrix whose powers count the non-backtracking walks between two edges – are close to those of EA\mathbb{E} A , and all other eigenvalues are confined in a bulk with known radius. We also obtain a precise characterization of the scalar product between the eigenvectors of BB and their deterministic counterparts derived from the model parameters.

This result has many applications, in domains ranging from (noisy) matrix completion to community detection, as well as matrix perturbation theory. In particular, we establish as a corollary that a result known as the Baik–Ben Arous–Péché phase transition, previously established only for rotationally invariant random matrices, holds more generally for matrices AA as above under a mild concentration hypothesis.

Cite this article

Ludovic Stephan, Laurent Massoulié, Non-backtracking spectra of weighted inhomogeneous random graphs. Math. Stat. Learn. 5 (2022), no. 3/4, pp. 201–271

DOI 10.4171/MSL/34