A lot of graph inference problems consist in finding a low-rank structure planted in the adjacency matrix of the graph. When sparse enough, the simple study of the adjacency matrix is not enough; the individual variance of each vertex influences too much the overall spectrum of \(A\). In contrast, we show how the non-backtracking matrix \(B\) recovers these low-rank structures more consistently. The goal of this talk is to provide an overview of these results beyond the seminal works of Bordenave et al., expanding the horizon of those methods to much more general settings and higher-order relationships.

Based on joint works with Laurent Massoulié, Simon Coste and Yizhe Zhu.