Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs

Introduction

Given a finite (simple, non-oriented) graph $G=(V,E)$, several matrices of interest can be associated to $G$, besides its adjacency matrix $A=(1\!\!{\sf I}_{\{u,v\}\in E})_{u,v\in V}$. In this work we are interested in the so-called non-backtracking matrix of $G$, denoted by $B$. It is indexed by the set $\vec{E}=\{(u,v):\{u,v\}\in E\}$ of oriented edges in $E$ and defined by

where for any $e=(u,v)\in\vec{E}$, we set $e_{1}=u$, $e_{2}=v$, $e^{-1}=(v,u)$. This matrix was introduced by Hashimoto . A non-backtracking walk is a directed path of directed edges of $G$ such that no edge is the inverse of its preceding edge. It is easily seen that for any $k\geq 1$, $B^{k}_{ef}$ counts the number of non-backtracking walks of $k+1$ edges on $G$ starting with $e$ and ending with $f$.

Our focus is the spectrum of $B$, referred to in the sequel as the non-backtracking spectrum of $G$, when $G$ is a sparse random graph. Specifically we shall characterize the asymptotic behavior of the leading eigenvalues and associated eigenvectors in the non-backtracking spectrum of sparse random graphs in the limit $n\to\infty$ where $n=|V|$.

The random graphs we consider are drawn according to the Stochastic Block Model, a generalization of Erdős-Rényi graphs due to Holland et al. . In this model nodes $v\in V$ are partitioned into $r$ groups. An edge between two nodes $u,v$ is drawn with probability $W(\sigma(u),\sigma(v))/n$, where $\sigma(u)\in[r]$ denotes the group node $u$ belongs to. Thus when the $r\times r$ matrix $W$ is fixed the expected node degrees remain of order 1 as $n\to\infty$. We focus moreover on instances where the fraction of nodes in group $i$ converges to a limit $\pi(i)$ as $n\to\infty$.

Our primary motivation stems from the problem of community detection, namely: how to estimate a clustering of graph nodes into groups close to the underlying blocks, based on the observation of such a random graph $G$? Decelle et al. conjectured a phase transition phenomenon on detectability, namely: the underlying block structure could be detected if and only if $|\mu_{2}|>\sqrt{\alpha}$.

In the case of two communities with roughly equal sizes ($\pi(1)=\pi(2)=1/2$) and symmetric matrix $W$, the negative part (impossibility of detection when $|\mu_{2}|\leq\sqrt{\alpha}$) was proven by Mossel et al . As for the positive part (feasibility of detection when $|\mu_{2}|>\sqrt{\alpha}$), it was conjectured in that the so-called belief propagation algorithm would succeed. Krzakala et al. then made their so-called “spectral redemption conjecture” according to which detection based on the second eigenvector of the non-backtracking matrix $B$ would succeed.

Recently a variant of the spectral redemption conjecture was proven by Massoulié : the spectrum of a matrix counting self-avoiding paths in $G$ allows to detect communities through thresholding of the second eigenvector. More recently and independently of , an alternative proof of the positive part of the conjecture in was given by Mossel et al. , based on an elaborate construction involving countings of non-backtracking paths in $G$.

The two approaches of and to proving the positive part of the conjecture in , while both relying ultimately on properties of specific path counts, differ however in the following respects. The method in relies on a clear spectral separation property but its implementation is computationally expensive, as the counts of self-avoiding walks it relies upon take super-linear (though polynomial) time. The method in is computationally efficient as it runs in quasi-linear time, but the proof does not establish a spectral separation property. The other two methods conjectured to achieve successful reconstruction, namely belief propagation and analysis of non-backtracking spectrum, are computationally efficient and they are motivated by a clear intuition as described in the spectral redemption conjecture.

Our present work proves the spectral redemption conjecture. More generally by characterizing all the leading eigen-elements it determines the limits of community detection based on the non-backtracking spectrum in the presence of an arbitrary number of communities.

Ihara zeta function

Hashimoto introduced the matrix $B$ in the context of the Ihara zeta function . We have the identity

where $\zeta_{G}$ is the Ihara zeta function of the graph, refer to . It follows that the poles of the Ihara zeta function are the reciprocal of the eigenvalues of $B$. Our main results have thus consequences on the localization of the poles of the zeta function of random graphs.

Weak Ramanujan property

Our result also has an interpretation from the standpoint of Ramanujan graphs, introduced by Lubotzky et al. (see Murty for a recent survey). These are by definition $k$-regular graphs such that the second largest modulus of its eigenvalues is at most $2\sqrt{k-1}$. By a result of Alon and Boppana (see ) for fixed $k$, $k$-regular graphs on $n$ nodes must have their second largest eigenvalue at least $2\sqrt{k-1}-o(1)$ as $n\to\infty$. Hence Ramanujan graphs are regular graphs with maximal spectral gap between the first and second eigenvalue moduli. A celebrated result of Friedman states that random $k$-regular graphs achieve this lower bound with high probability as their number of nodes $n$ goes to infinity.

Lubotzky has proposed an extension of the definition of Ramanujan graphs to the non-regular case. Specifically, $G$ is Ramanujan according to this definition if and only if

where $A$ is the adjacency matrix of $G$, $\rho$ its spectral radius, and $\sigma$ the spectral radius of the adjacency operator on the universal covering tree of $G$.

Using the analogy between the Ihara zeta function and the Riemann zeta function, Stark and Terras (see ) have defined a graph to satisfy the graph Riemann hypothesis if its non-backtracking matrix $B$ has no eigenvalues $\lambda$ such that $|\lambda|\in(\sqrt{\rho_{B}},\rho_{B})$, where $\rho_{B}$ is the Perron-Frobenius eigenvalue of $B$. Interestingly, a regular graph $G$ is Ramanujan if and only if it satisfies the graph Riemann hypothesis (see and ). Thus the graph Riemann hypothesis can also be seen as a generalization of the notion of Ramanujan graphs to the non-regular case, phrased in terms of non-backtracking spectra rather than on spectra of universal covers as in the definition of Lubotzky .

Our results imply that for fixed $\alpha>1$, Erdős-Rényi graphs $\mathcal{G}(n,\alpha/n)$ have an associated non-backtracking matrix $B$ such that $\rho_{B}\sim\alpha$ and all its other eigenvalues $\lambda$ verify $|\lambda|\leq\sqrt{\alpha}+o(1)$ with high probability as $n\to\infty$. In this sense, Erdős-Rényi graphs asymptotically satisfy the graph Riemann hypothesis, itself is a plausible extension of the notion of Ramanujan graphs to the non-regular case. This may be seen as an analogue of Friedman’s Theorem in the context of Erdős-Rényi graphs. Similarly, for the Stochastic Block Model, our main result is analogue to recent results on the eigenvalues of random $n$-lifts of base graphs, see . Interestingly, in , the methods developed in the present paper are adapted to lead to a new and simpler proof of Friedman’s Theorem and its extensions to random $n$-lifts. The random graphs studied here will require a more delicate analysis.

Organization

The paper is organized as follows. We start in Section 2 with preliminaries on non-backtracking matrices. We state our main results in Section 3, namely Theorems 3 and 4 characterizing properties of non-backtracking spectra of Erdős-Rényi graphs and Stochastic Block Models respectively, and Theorem 5 establishing their consequence for community detection.

In Section 4, we provide the algebraic ingredients we shall need. Specifically we establish general bounds on the perturbation of eigenvalues and eigenvectors of not necessarily symmetric matrices that elaborate on the Bauer-Fike Theorem.

In Section 6 we detail another combinatorial argument needed in our proof, namely we establish bounds on the norms of the various matrices involved in the previous matrix expansion. The latter norm bounds are established by the trace method, adapting arguments due to Fűredi and Komlós .

Section 7 gives the proof strategy for Theorem 4 on non-backtracking spectra of Stochastic Block Models.

In Section 8 we establish convergence results on multitype branching processes that extend results of Kesten and Stigum . These are then used in Section 9 to characterize the local structure of the random graphs under study. Specifically we relate the local statistics of Stochastic Block Models to branching processes via coupling, and then establish weak laws of large numbers on these local statistics. These probabilistic arguments together with the previous algebraic and combinatorial arguments allow us to conclude the proofs of Theorems 3 and 4. Section 11 contains the proof of Theorem 5 on community detection.

Preliminaries on non-backtracking matrices

We set $m=|\vec{E}|$. A priori, $B$ is not a normal matrix. We are interested in its eigenvalues $\lambda_{1}(B),\ldots,\lambda_{m}(B)$ ordered non-increasingly, $|\lambda_{1}(B)|\geq\ldots\geq|\lambda_{m}(B)|$. The Perron-Frobenius Theorem implies notably that $\lambda_{1}(B)$ is a non-negative real. If $G$ is connected, $\lambda_{1}(B)$ is equal to the growth rate of the universal cover of $G$ (see Angel, Friedman and Hoory ).

Hence $B^{k}P$ is a symmetric matrix (in mathematical physics, this type of symmetry is called PT-invariance, PT standing for parity-time). If $(\sigma_{j,k})$, $1\leq j\leq m$, are the eigenvalues of $B^{k}P$ and $(x_{j,k})$, $1\leq j\leq m$, is an orthonormal basis of eigenvectors, we deduce that

This is precisely the singular value decomposition of $B^{k}$.

For example, for $k=1$, it is a simple exercise to compute $(\sigma_{j,1})_{1\leq j\leq m}$. We find that the eigenvalues of $BP$ are $(\deg(v)-1)$, $1\leq v\leq n$, and $-1$ with multiplicity $m-n$. In particular, the singular values of $B$ contain only information on the degree sequence of the underlying graph $G$.

For large $k$ however, we may expect that the decomposition (3) carries more structural information on the graph (this will be further discussed in Subsection 2.2 below). This will be the underlying principle in the proof of our main results. For the moment, we simply note the following. Assume that $B$ is irreducible. From Perron-Frobenius theorem, if $\xi$ is the Perron eigenvector of $B$, $\|\xi\|=1$, then for any $n$ fixed,

A quantitative version of the above limits will be given in the forthcoming Proposition 7. Another consequence of (3) is that, for $i\neq j$, $x_{i,k}$ and $\check{x}_{j,k}$ should be nearly orthogonal if these vectors converge as $k\to\infty$. Indeed, a heuristic computation gives

We will exploit this general phenomenon in the proof of our main results.

2 Chung, Cheeger and Alon-Boppana inequalities for non-backtracking matrices

The aim of this subsection is to advocate the use of non-backtracking matrices. Here, we discuss briefly candidate counterparts for irregular graphs of inequalities that are classical in the context of regular graphs. This subsection will not be used in the proof of our main results, it may be skipped.

The diameter bound of Chung gives an upper bound on the diameter of a regular graph in terms of its spectral gap. The following lemma, expressed in terms of the decomposition (4) of $B^{k}$, is an analogue:

Let $e=(u,u^{\prime})$, $f=(v,v^{\prime})\in\vec{E}$ be such that

Then, the graph distance between $u$ and $v$ is at most $k+1$.

Observe that if $B^{k}_{ef^{-1}}>0$ then $u$ and $v$ are at most at distance $k+1$. On the other hand from (4),

has absolute value at most $s_{2,k}$ from Cauchy-Schwartz inequality and the orthonormality of the $x_{j,k}$, $1\leq j\leq m$. Thus finally, $B^{k}_{ef^{-1}}\geq s_{1,k}x_{1,k}(e)x_{1,k}(f)-s_{2}.$ ∎

Cheeger-type inequalities connect the expansion ratio (isoperimetry) of the graph and its spectral gap, for a survey see . For a subset $X\subset\vec{E}$ of edges, we measure its volume by

By construction, our volume is normalized with $V_{k}(\vec{E})=1$. We say that $X\subset\vec{E}$ is edge-symmetric if $\check{X}=X$. For example the set of edges adjacent to a given subset of vertices is edge-symmetric. If $X,Y$ are edge-symmetric, we define

Since $B^{k}_{ef}$ is the number of non-backtracking walks of length $k+1$ starting with $e$ and ending with $f$, $E_{k}(X,Y)$ measures a kind of conductance between $X$ and $Y$ with a proximity range of radius $k+1$. If $X^{c}=X\backslash\vec{E}$, the scalar

can be thought of as the outer surface of a set $X$. The $k$-th expansion ratio of $G$ is then defined as

In (3), after reordering the eigenvalues of $B^{k}P$ as $\sigma_{1,k}\geq\sigma_{2,k}\geq\ldots\geq\sigma_{m,k}$, $\sigma_{1,k}-\sigma_{2,k}$ plays the role of the spectral gap in the classical Cheeger inequality. With this new convention, the following lemma is the analog of the easy part of Cheeger’s inequality for graphs.

The argument is standard. For simplicity, we drop the index $k$. From Courant-Fisher min-max Theorem, we have

Let $X\subset\vec{E}$ be edge-symmetric. We set

By construction $\langle x,x_{1}\rangle=0$ and $\|x\|^{2}=1/V(X)+1/V(X^{c})$. Hence,

However, using the edge-symmetry of $X$ and $X^{c}$,

Also, using the singular value equation $B^{k}\check{x}_{1}=\sigma_{1}x_{1}$,

Since, for $x,x^{\prime}>0$, $1/x+1/x^{\prime}\leq 2/(x\wedge x^{\prime})$, it concludes the proof. ∎

The Alon-Boppana theorem gives a lower bound on the second largest eigenvalue of the adjacency matrix of a regular graph (see ). We conclude this paragraph with an elementary bound of this type. We introduce for $e\in\vec{E}$,

In words, $S_{k}(e)$ is the number of non-backtracking walks of length $k+1$ starting with $e$. As already pointed, if $B$ is irreducible, the Perron eigenvalue is the growth rate of the universal cover of the graph: for any $e\in\vec{E}$,

This last crude inequality gives a lower bound on the second largest singular value of $B^{k}$.

Main results

We now state our results on the non-backtracking spectra of Erdős-Rényi graphs first, and Stochastic Block Models next.

Let $G$ be an Erdős-Rényi graph with parameters $(n,\alpha/n)$ for some fixed parameter $\alpha>1$. Then, with probability tending to $1$ as $n\to\infty$, the eigenvalues $\lambda_{i}(B)$ of its non-backtracking matrix $B$ satisfy

Moreover the normalized Perron-Frobenius eigenvector associated to $\lambda_{1}(B)$ is asymptotically aligned with

Theorem 3 is illustrated by Figure 1. We conjecture that the lower bound $|\lambda_{2}(B)|\geq\sqrt{\alpha}-o(1)$ holds, it is reasonable in view of Figure 1. We shall prove a weaker lower bound, see forthcoming Remark 12. It is also an interesting open problem to study the convergence of the empirical distribution of the eigenvalues of $B$.

2 Stochastic Block Model

For integer $k\geq 1$, we set $[k]=\{1,\ldots,k\}$. We consider a random graph $G=(V,E)$ on the vertex set $V=[n]$ defined as follows. Each vertex $v\in[n]$ is given a type $\sigma_{n}(v)$ from the set $[r]$ where the number of types $r$ is assumed fixed and the map $\sigma_{n}:[n]\to[r]$ is such that, for all $i\in[r]$,

for some probability vector $\pi=(\pi(1),\cdots,\pi(r))$. For ease of notation, we often write $\sigma$ in place of $\sigma_{n}$.

i.e. for some integer $k\geq 1$, $M^{k}$ has positive coefficients. In particular, $\mu_{1}>\max_{k\geq 2}|\mu_{k}|$ is the Perron-Frobenius eigenvalue. It implies notably that for all $i\in[r]$, $\pi(i)>0$. We define $r_{0}$ by

(with $\mu_{r+1}=0$). Since $M=\Pi^{1/2}S\Pi^{-1/2}$, the matrix $M$ is diagonalizable. Let $\{u_{i}\}_{i\in[r]}$ be an orthonormal basis of eigenvectors of $S$ such that $Su_{i}=\mu_{i}u_{i}$. Then $\phi_{i}:=\Pi^{-1/2}u_{i}$ and $\psi_{i}=\Pi^{1/2}u_{i}$ are the left and right-eigenvectors associated to eigenvalue $\mu_{i}$, $\phi_{i}^{*}M=\mu_{i}\phi^{*}_{i}$, $M\psi_{i}=\mu_{i}\psi_{i}$. We get

where the second identity comes from $\psi_{k}=\Pi\phi_{k}$ and $W=\Pi^{-1}M$.

We will make the further assumption that each vertex type has the same asymptotic average degree $\alpha>1$, i.e.,

This entails that $M^{*}/\alpha$ is a stochastic matrix and we then have

We will also assume that a quantitative version of (7) holds, namely that for some $\gamma\in(0,1]$,

The random graph $G$ is usually called the stochastic block model (SBM for short) or inhomogeneous random graph, see Bollobás, Janson and Riordan and Holland, Laskey and Leinhardt . A popular case is when the map $\sigma$ is itself random and $\sigma(v)$ are i.i.d. with distribution $(\pi(1),\cdots,\pi(r))$. In this case, with probability one, condition (13) is met for any $\gamma<1/2$.

If $r=2$, then we have $\pi(1)=1-\pi(2)$. Under condition (11), we have $W_{22}=(\pi(1)W_{11}+(1-2\pi(1))W_{12})/(1-\pi(1))$ so that $\mu_{1}=\alpha=\pi(1)W_{11}+(1-\pi(1))W_{12}$ and $\mu_{2}=\pi(1)\left(W_{11}-W_{12}\right)$.

If $r\geq 2$, $\pi(i)=1/r$ and $W_{ii}=a\neq b=W_{ij}$ for all $i\neq j$ so that condition (11) is satisfied. We have $\mu_{1}=\alpha=(a+(r-1)b)/r$ and $\mu_{2}=\ldots=\mu_{r}=(a-b)/r$.

In particular, $\chi_{1}=\chi$. Our main result is the following generalization of Theorem 3.

Let $G$ be an SBM as above such that hypotheses (8,11,13) hold. Then with probability tending to $1$ as $n\to\infty$,

Moreover, if $\mu_{k}$ is a simple eigenvalue of $M$ for some $k\in[r_{0}]$, then a normalized eigenvector, say $\xi_{k}$, of $\lambda_{k}(B)$ is asymptotically aligned with

It follows from this result that a non-trivial estimation of the node types $\sigma(v)$ is feasible on the basis of the eigenvectors $\{\xi_{k}\}_{2\leq k\leq r_{0}}$ provided $r_{0}>1$. More precisely, for vertex type estimators $\hat{\sigma}(v):[n]\to[r]$ based on the observed random graph $G$, following Decelle et al. , define the overlap $\hbox{ov}(\hat{\sigma},\sigma)$ as the minimum over permutations $p:[r]\to[r]$ of the quantity

We shall say that $\hat{\sigma}$ has asymptotic overlap $\delta$ if $\hbox{ov}(\hat{\sigma},\sigma)$ converges in probability to $\delta$ as $n$ grows. It has asymptotic positive overlap if for some $\delta>0$, $\hbox{ov}(\hat{\sigma},\sigma)>\delta$ with probability tending to $1$ as $n$ grows. Note that an asymptotic overlap of zero is always achievable by assigning to each vertex the type $k^{*}$ that maximizes $\pi(k)$. In the case where all communities have asymptotically the same size, i.e. $\pi(i)\equiv 1/r$, zero overlap is also achieved by assigning types at random.

As conjectured in and proven in , in the setup of Example 2 with $r=2$, the best possible overlap is $o(1)$ with high probability when $r_{0}=1$, i.e. when $\mu_{2}\leq\sqrt{\mu_{1}}$. Conversely, adapting the argument in , when $r_{0}>1$, we have the following

The reason for the existence of the signing $\omega\in\{-1,1\}^{V}$ in the above statement is that we do not know a priori whether the vector $\xi_{k}$ or $-\xi_{k}$ is asymptotically close to (15). In the simplest case, we will be able to estimate this sign and the vector $\omega$ will be equal to $-1\!\!{\sf I}$ or $1\!\!{\sf I}$ and $I^{+}=\{i\in[r]:\phi_{k}(i)>0\}$, $I^{-}=[r]\backslash I^{+}$.

3 Notation

We denote by $C^{*}$ the transpose of $C$.

Given a (non-oriented) graph $G=(V,E)$, we denote by $\gamma=(\gamma_{0},\dots,\gamma_{k})$ a walk of length $k$ where each $\gamma_{i}\in V$ and $\{\gamma_{i},\gamma_{i+1}\}\in E$ for all $i\in\{0,\dot{k}-1\}$. We also denote the concatenation of two walks $\gamma$ and $\gamma^{\prime}$ by $(\gamma,\gamma^{\prime})$. A walk is non-backtracking if for all $i\in\{0,\dots,k-2\}$, $\gamma_{i}\neq\gamma_{i+2}$. A walk contains a cycle if there exists $i\neq j$ with $\gamma_{i}=\gamma_{j}$.

Algebraic tools: Perturbation of Eigenvalues and Eigenvectors

One main tool in our analysis is the Bauer-Fike Theorem. The form given below elaborates on the usual statement of the Theorem which in general omits the second half.

(Bauer-Fike Theorem; see [4, Theorem VI.5.1]). Let $D$ be a diagonalizable matrix such that for some invertible matrix $V$ and diagonal matrix $\Lambda$ one has $D=V^{-1}\Lambda V$. Let $E$ be a perturbation matrix.

Then any eigenvalue $\mu$ of $D+E$ verifies

where $\lambda_{i}$ is the $i$-th diagonal entry of $\Lambda$.

Denote by $R$ the right-hand side of (17) and $C_{i}:={\mathcal{B}}(\lambda_{i},R)$ the ball centered at $\lambda_{i}$ with radius $R$. Let ${\mathcal{I}}$ be a set of indices such that

Then the number of eigenvalues of $D+E$ in $\cup_{i\in{\mathcal{I}}}C_{i}$ is exactly $|{\mathcal{I}}|$.

The following proposition on perturbation of rank one matrices will be a basic ingredient to deduce from expressions like (3) quantitative versions of (5). It relies on the stability of eigenvalues and eigenvectors of matrices which are not too far from being normal ($A$ is normal if and only if $A^{*}A=AA^{*}$; see ), and with a well separated spectrum.

with $\langle y_{k},x_{k}\rangle\geq c_{0}$, $\|x_{k}\|\|y_{k}\|\leq c_{1}$ and

Let $(\lambda_{i})$, $1\leq i\leq n$ be the eigenvalues of $A$, with $|\lambda_{n}|\leq\ldots\leq|\lambda_{1}|$. Then, $\lambda_{1}$ has multiplicity one and we have

with $C=\pi/2+2\sqrt{c_{1}\vee 1}\log(2(c_{1}\vee c_{0}^{-1}))$. Moreover, there exists a unit eigenvector $\psi$ of $A$ with eigenvalue $\lambda_{1}$ such that

The eigenvalues of $WW^{*}$ are $1\pm|b|$. We deduce that

In particular, the eigenvalue $\lambda_{1}^{k}$ has multiplicity one in $A^{k}$ and thus $\lambda_{1}$ has multiplicity one in $A$. We now bound the difference between $\lambda_{1}$ and $\theta=1$. First, by assumption,

with $c_{2}=\sqrt{(2c_{1})\vee 1}\log(2(c_{1}\vee c_{0}^{-1}))$.

Since $|x|\leq(\pi/2)|\sin(x)|$ for $x\in[-\pi/2,\pi/2]$, we obtain from (19) that

where $c$ is some scalar and we have used $|\lambda_{1}|^{k}\geq c_{0}/2$. We now use the following general inequality

From the trianle inequality, $\|z_{0}\|\geq 1-\|z^{\perp}\|$. We then have

Finally, since $\lambda=\lambda^{k}_{1}$ has multiplicity one in $A^{k}$, the eigenspace of $\lambda_{1}$ for $A$ coincides with the eigenspace of $\lambda_{1}^{k}$ for $A^{k}$. This concludes the proof of Proposition 7. ∎

Assume there exist $c_{0},c_{1}>0$ such that for all $i\neq j\in[r]$, $\langle y_{k,j},x_{k,j}\rangle\geq c_{0}$, $\|x_{k,j}\|\|y_{k,j}\|\leq c_{1}$, $\langle x_{k,j},y_{k,i}\rangle=\langle x_{k,j},x_{k,i}\rangle=\langle y_{k,j},y_{k,i}\rangle=0$ and

where $\vartheta=\min_{i}|\theta_{i}|$, $\gamma=\min\{\theta_{i}/\theta_{j}:\theta_{i}>\theta_{j}>0\hbox{ or }\theta_{i}<\theta_{j}<0\}$ (the minimum over the empty set being $+\infty$). Let $(\lambda_{i})$, $1\leq i\leq n$, be the eigenvalues of $A$ with $|\lambda_{n}|\leq\ldots\leq|\lambda_{1}|$. Then, there exists a permutation $\sigma\in S_{r}$ such that for all $i\in[r]$,

with $C=\pi/2+2\sqrt{c_{1}\vee 1}\log(2(c_{1}\vee c_{0}^{-1}))$. Moreover, if $\theta_{\sigma(i)}$ has multiplicity one in $\theta$, $\lambda_{i}$ is a simple eigenvalue and there exists a unit eigenvector $\psi_{i}$ of $A$ with eigenvalue $\lambda_{i}$ such that

with $C^{\prime}=24c_{1}c_{0}^{-1}/(1\wedge(c_{0}\gamma^{k}-c_{1})_{+}\wedge c_{0})$.

Now, by assumption, $2\kappa\|R_{k}\|<c_{0}\wedge(c_{0}\gamma^{k}-c_{1})_{+}$ is less than the minimal distance between the distinct eigenvalues of $D$. We deduce from Theorem 6 applied to $D+U^{-1}R_{k}U$ that there is a permutation $s\in S_{r}$ such that

We now bound the difference between $\lambda_{i}$ and $\theta_{s(i)}$. By assumption, $c_{0}|\theta_{j}|\leq|\nu_{j}|\leq c_{1}|\theta_{j}|.$ Hence, arguing as in the proof of Proposition 7,

It now remains to control the eigenvector of $\lambda_{i}$ such that $\theta_{\sigma(i)}$ has multiplicity one. First from (22), $\lambda_{i}$ is a simple eigenvalue of $A$. Let $z$ be a corresponding normed eigenvector of $A$. Applying $A^{k}$ yields

Applying $A^{k}$ once more to (23) yields

Multiplying (23) by $\lambda_{i}^{k}$ and subracting it to the previous display yields

Moreover, this implies upon dividing (24) by $\lambda_{i}^{k}$:

We conclude this paragraph with an elementary lemma on Gram-Schmidt orthonormalization process. It will be used to obtain vectors which are exactly orthogonal as in the assumptions of Proposition 8.

We prove the statement by induction. For $k=1$, $\bar{u}_{1}=u_{1}$. For $k\geq 1$, we denote by $v_{k+1}$ the orthonormal projection of $u_{k+1}$ on the span of $(u_{1},\cdots,u_{k})$. We have

It is easy to check that $\sqrt{2k(1+k^{k})}\leq 2^{-1}(k+1)^{k+1}$ for all $k\geq 1$. In particular, if $\delta<(k+1)^{-(k+1)}$, $v_{k+1}\neq u_{k+1}$ and then from (21), $\|u_{k+1}-\bar{u}_{k+1}\|\leq 2\|v_{k+1}\|\leq\delta(k+1)^{k+1}$. ∎

Erdős-Rényi graph: proof strategy for Theorem 3

(if $\theta=0$, we set $\zeta=0$). The proof relies on the following two propositions.

Hence, Proposition 11 implies that w.h.p.

We may now apply Proposition 7. If $\lambda_{i}=\lambda_{i}(B)$, we find that w.h.p.

and the normalized Perron eigenvector $\xi$ of $B$ satisfies w.h.p.

We note that from [15, Theorem 3.3.16], we get that in (4),

The proof of Proposition 11 relies crucially on a matrix expansion given in Proposition 13, which extends the argument introduced in for matrices counting self-avoiding walks to the present setup where non-backtracking walks instead are considered. We now introduce some notation to state it.

where $A$ is the graph’s adjacency matrix. For integer $k\geq 1$, $e,f\in\vec{E}(V)$, we define $\Gamma^{k}_{ef}$ as the set of non-backtracking walks $\gamma=(\gamma_{0},\ldots,\gamma_{k})$ of length $k$ starting from $(\gamma_{0},\gamma_{1})=e$ and ending at $(\gamma_{k-1},\gamma_{k})=f$ in the complete graph on the vertex set $V$. We have that

and $F^{k+1}_{ef}$ is the subset of tangle-free paths in $\Gamma^{k+1}_{ef}$. For $u\neq v$, we set

The matrix $\Delta^{(k)}$ can be thought of as an attempt to center the non-backtracking matrix $B^{k}$ when the underlying graph is tangle-free. We use the convention that a product over an empty set is equal to $1$. We also set

Notably, $B^{(0)}$ is the projection on $\vec{E}$. We have the following telescopic sum decomposition.

3 Norm bounds

The following proposition will be established in Section 6 using path counting combinatorial arguments.

4 Proof of Proposition 11

Together with Propositions 13 and 14, we shall also need the next two results, established by local analysis in Section 9. In particular the forthcoming Lemma 30 implies that

For the Erdős-Rényi graph, Corollary 34 states the following.

Also, from (2), since $\check{\chi}=\chi$,

Hence, from Proposition 16 and norm bound (31), w.h.p.

Proof of Proposition 14: path count combinatorics

The proof will use a version of the trace method. For $n\geq 3$, we set

The symmetry (2) implies that $\Delta^{(k)}_{ef}=\Delta^{(k)}_{f^{-1}e^{-1}}$. With the convention that $e_{2m+1}=e_{1}$, we get

where $W_{k,m}$ is the set of sequence of paths $\gamma=(\gamma_{1},\ldots,\gamma_{2m})$ such that $\gamma_{i}=(\gamma_{i,0},\cdots,\gamma_{i,k})\in V^{k+1}$ is non-backtracking tangle-free of length $k$ and for all $i=1,\ldots,2m$,

with the convention that $\gamma_{0}=\gamma_{2m}$.

where $W^{\prime}_{k,m}$ is the subset of $W_{k,m}$ where each non-oriented edge is visited at least twice. For each $\gamma\in W_{k,m}$ we associate the graph $G(\gamma)=(V(\gamma),E(\gamma))$ of visited vertices and edges. We set

We say that a path $\gamma$ is canonical if $V(\gamma)=\{1,\cdots,v(\gamma)\}$ and the vertices are first visited in order. $\mathcal{W}_{k,m}$ will denote the set of canonical paths in $W_{k,m}$. Every canonical path is isomorphic to ${n\choose v(\gamma)}v(\gamma)!$ paths in $W_{k,m}$. We also have the following

Let $\mathcal{W}_{k,m}(v,e)$ be the set of canonical paths with $v(\gamma)=v$ and $e(\gamma)=e$. We have

In order to upper bound $|\mathcal{W}_{k,m}(v,e)|$ we need to find an injective way to encode the canonical paths $x\in\mathcal{W}_{k,m}(v,e)$.

Let $x=(x_{i,t})_{1\leq i\leq 2m,0\leq t\leq k}\in\mathcal{W}_{k,m}(v,e)$. We set $y_{i,t}=\{x_{i,t},x_{i,t+1}\}$, $y_{i,t}$ will be called an edge of $x$. We explore the sequence $(x_{i,t})$ in lexicographic order denoted by $\preceq$ (that is $(i,t)\preceq(i+1,t^{\prime})$ and $(i,t)\preceq(i,t+1)$). We think of the index $(i,t)$ as a time. For $0\leq t\leq k-1$, we say that $(i,t)$ is a first time, if $x_{i,t+1}$ has not been seen before (that is $x_{i,t+1}\neq x_{i^{\prime},t^{\prime}}$ for all $(i^{\prime},t^{\prime})\preceq(i,t)$). If $(i,t)$ is a first time the edge $y_{i,t}$ is called a tree edge. By construction, the set of tree edges forms a tree $T$ with vertex set $\{1,\ldots,v\}$. The edges which are not in $T$ are called the excess edges of $x$. Any vertex different from $1$ has its associated tree edge. It follows that the cardinal of excess edges is $\epsilon=e-v+1$.

We build a first encoding of $\mathcal{W}_{k,m}(v,e)$. If $(i,t)$ is not a first time, we say that $(i,t)$ is an important time and we mark the time $(i,t)$ by the vector $(x_{i,t+1},x_{i,\tau})$, where $(i,\tau)$ is the next time that $y_{i,\tau}$ will not be a tree edge (by convention $\tau=k$ if $x_{i,s}$ remains on the tree for all $t+1\leq s\leq k$). Since there is a unique non-backtracking path between two vertices of a tree, we can reconstruct $x\in\mathcal{W}_{k,m}$ from the position of the important times and their mark. It gives rise to our first encoding.

The main issue with this encoding is that the number of important times could be large. We have however not used so far the hypothesis that each path $x_{i}$ is tangle free. To this end, we are going to partition important times into three categories, short cycling, long cycling and superfluous times. First consider the case where the $i$-th path $x_{i}$ contains a cycle. For each $i$, the first time $(i,t)$ such that $x_{i,t+1}\in\{x_{i,0},\ldots,x_{i,t}\}$ is called a short cycling time. Let $0\leq\sigma\leq t$ be such that $x_{i,t+1}=x_{i,\sigma}$. By the assumption of tangle-freeness, $C:=(x_{i,\sigma},\cdots,x_{i,t+1})$ is the only cycle visited by $x_{i}$. We denote by $(i,\tau)$ the first time after $(i,t)$ that $y_{i,\tau}$ in not an edge of $C$ (by convention $\tau=k$ if $x_{i}$ remains on $C$). We add the extra mark $\tau$ to the short cycling time. Important times $(i,t)$ with $1\leq t<\sigma$ or $\tau<t\leq k$ are called long cycling times. The other important times are called superfluous. The key observation is that for each $1\leq i\leq 2m$, the number of long cycling times $(i,t)$ is bounded by $\epsilon-1$ (since there is at most one cycle, no edge of $x$ can be seen twice outside those of $C$, the $-1$ coming from the fact that the short cycling time is an excess edge). Now consider the case where the $i$-th path does not contain a cycle, then all important times are called long cycling times and their number is bounded by $\epsilon$.

We now have our second encoding. We can reconstruct $x$ from the positions of the long cycling and the short cycling times and their marks. For each $1\leq i\leq 2m$, there are at most $1$ short cycling time and $\epsilon-1$ long cycling times within $x_{i}$ if $x_{i}$ contains a cycle and short cycling time and $\epsilon$ long cycling times if $x_{i}$ does not contain a cycle. There are at most $k^{2m\epsilon}$ ways to position them (in time). There are at most $v^{2}$ different possible marks for a long cycling time and $v^{2}k$ possible marks for a short cycling time. We deduce that

We use $v\leq 2km$ to obtain the announced bound. ∎

From (37) and Markov inequality, it suffices to prove that

For our choice of $m$ in (35), we have, for $n$ large enough,

In particular, the above geometric series converges and (38) follows. ∎

The bound (31) on $\|\Delta^{(k)}\chi\|$ we will now establish improves by a factor $\sqrt{n}$ on the trivial estimate $\|\Delta^{(k)}\chi\|\leq\|\chi\|\|\Delta^{(k)}\|$. Its proof parallels the argument used to show (30). We have

where $W^{\prime\prime}_{k,1}$ is the set of pairs of paths $(\gamma_{1},\gamma_{2})$ such $\gamma_{i}=(\gamma_{i,0},\ldots,\gamma_{i,k})$ is non-backtracking and $(\gamma_{1,k-1},\gamma_{1,k})=(\gamma_{2,1},\gamma_{2,0})$ and each edge is visited at least twice. The only difference with $W_{k,1}$ defined above is that we do not require that $(\gamma_{1,0},\gamma_{1,1})=(\gamma_{2,k},\gamma_{2,k-1})$. However, this last condition $(\gamma_{1,0},\gamma_{1,1})=(\gamma_{2m,k},\gamma_{2m,k-1})$ was not used in the proof of Lemma 17. It follows that the set of canonical paths in $W^{\prime\prime}_{k,1}$ with $v$ distinct vertices and $e$ distinct edges has cardinal bounded by $k^{2}(2k)^{6(e-v+1)}$. Since the paths are connected and each edge appears at least twice, we have $v-1\leq e\leq k$. As in the proof of (30), we get from (40) with $m=1$

We conclude with Markov inequality and the union bound. ∎

with the convention that $\gamma_{0}=\gamma_{2m}$.

We define $G(\gamma)=(V(\gamma),E(\gamma))$ as the union of the graph $G(\gamma_{i}^{z})$, $1\leq i\leq 2m$, $z\in\{1,2\}$. Note that the edges $(\gamma_{i,k},\gamma_{i,k+1})$ are not taken into account in $G(\gamma)$. As usual, we set $v(\gamma)=|V(\gamma)|$ and $e(\gamma)=|E(\gamma)|\geq v(\gamma)$. Since $\gamma_{i}$ is tangled either (a) $G(\gamma_{i})$ contains a cycle and is connected or (b) both $G(\gamma_{i}^{1})$ and $G(\gamma_{i}^{2})$ contain a cycle. In particular, all connected components of $G(\gamma)$ contain a cycle and it follows that

Taking the expectation in (42), we find that

Since $\|K\|$ is of order $n$, we observe that the second statement in (33) improves by a factor $\sqrt{n}$ the crude bound $\|KB^{(k)}\|\leq\|K\|\|B^{(k)}\|$.

We only prove the second statement. The first statement is proved similarly. The argument again parallels that used to show (30). We take $m$ as in (35). We have

where $W_{k,m}$ is the set of sequence of paths $\gamma=(\gamma_{1},\ldots,\gamma_{2m})$ defined below (36). From (47) and Markov inequality, it suffices to prove that

If $\gamma\in\mathcal{W}_{k,m}$ is a canonical element of $W_{k,m}$ then $v(\gamma)-1\leq e(\gamma)\leq 2km$ and $v(\gamma)\geq 3$. Also, any $\gamma\in\mathcal{W}_{k,m}$ is isomorphic to less that $n^{v(\gamma)}$ elements in $W_{k,m}$. Moreover, we have that

For our choice of $m$ in (35), the above geometric series converges and (48) follows. ∎

Observe that $L_{ef}=0$ unless $e=f$, $K_{ef}=1$, $K_{f^{-1}e}=1$ or $K_{ef^{-1}}=1$ in which cases $L_{ef}=-1$. We may thus decompose

where $I$ is the identity, and the non-zero entries of $K^{\prime}$ are equal $1$ and are the pairs $(e,f)$ such that $K_{ef}=1$, $K_{f^{-1}e}=1$ or $K_{ef^{-1}}=1$. Thus

Stochastic Block Model : proof of Theorem 4

(in the above, if $\theta_{k}=0$, we set $\zeta_{k}=0$). We also define

Proposition 19 will follow from the local analysis done in Section 9. The next Proposition will be established in Section 10 using a matrix expansion together with norm bounds derived by combinatorial arguments parallel to the proof of Proposition 11 for the Erdős-Rényi graph.

We now check that the two preceding propositions imply Theorem 4. We consider $(\bar{\varphi}_{1},\cdots,\bar{\varphi}_{r^{\prime}})$ obtained by the Gram-Schmidt orthonormalization of $(\check{\varphi}_{1},\cdots,\check{\varphi}_{r})$. By Lemma 9 and Proposition 19(iv), w.h.p. $r^{\prime}=r$ and for all $k\in[r]$,

Since $\|\check{\varphi}_{k}-\bar{\varphi}_{k}\|=o(1)$, from Proposition 19(i)-(iii), we find by induction on $k\in[r]$, w.h.p. for all $k\in[r]$,

Consequently, from Proposition 20, we have w.h.p.

Hence, Proposition 20 and (53)-(54) imply that w.h.p.

We are now in position to apply Proposition 8. From (52), the statement of Proposition 19(ii) also holds with $\zeta_{k}$ replaced by $\bar{\zeta}_{k}$. It readily implies Theorem 4.

Controls on the growth of Poisson multi-type branching processes

In this section we derive results for multi-type Galton-Watson branching processes with Poisson offspring that will be crucial for the local analysis of Section 9. We refer to Section 3.2 for the notation used below.

We include the proof for later use. For $0\leq s<t$, we have

so that, as $\phi_{k}^{*}M=\mu_{k}\phi_{k}^{*}$,

It follows easily that $(X_{k}(t))$ is an $\mathcal{F}_{t}$-martingale with mean . From Doob’s martingale convergence Theorem, the statement will follow if we prove that for some $C>0$ and all integer $t\geq 0$,

To this end, we denote by $Z_{s+1}(i,j)$ the number of individuals of type $i$ in the $s+1$-th generation which descend from a particle of type $j$ in the $s$-th generation. Thus $\sum_{j\in[r]}Z_{s+1}(i,j)=Z_{s+1}(i)$. We then have

where in the penultimate equality we used the fact that the variance of a Poisson random variable equals its mean. It follows that

The Perron-Frobenius Theorem implies that the matrix $(M/\mu_{1})^{s}$ converges elementwise to $\psi_{1}\phi_{1}^{*}/\phi_{1}^{*}\psi_{1}$ as $s\to\infty$. In our case, $\phi_{1}=1\!\!{\sf I}$, $\psi_{1}=\pi^{*}$ and $\langle 1\!\!{\sf I},\psi_{1}\rangle=1$. Consequently, for some $C\geq 1$,

Since $\mu_{k}^{2}>\mu_{1}$ the above series is convergent. ∎

We also need to control the behavior of $\langle\phi_{k},Z_{t}\rangle$ for $k\in[r]\backslash[r_{0}]$. The next result is contained in Kesten and Stigum [17, Theorem 2.4].

Assume $Z_{0}=x$. For $k\in[r]\backslash[r_{0}]$ define

Then $X_{k}(t)$ converges weakly to a random variable $X_{k}$ with finite positive variance.

Note that Theorem 2.4 in expresses $X_{k}$ as a mixture of Gaussian variables. The normalization in the case $\mu_{k}^{2}=\mu_{1}$ comes from the fact that $M$ is diagonalizable, and hence all its Jordan blocks are of size $1$.

2 Quantitative versions of the Kesten-Stigum Theorems

We will also need probabilistic bounds on the growth of the total population at generation $t$ defined as

Assume $S_{0}=1$. There exist $c_{0},c_{1}>0$ such that for all $s\geq 0$,

It is straightforward to check that $f_{k}$ converges, hence there exist constants $c_{0},c_{1}>0$ such that for all $k\geq 1$,

where we have set $\gamma(s)=s\log s-s+1$. In particular, on the event $\{S_{k}\leq sf_{k}\mu_{1}^{k}\}\in\mathcal{F}_{k}$, we have

where we have used the existence of some $\theta>0$ such that for $x\in[0,c_{1}]$, one has $\gamma(1+x)\geq\theta x^{2}$. Finally by our choice of $\varepsilon_{k}$ and (57), if $s\geq\max(1/c^{\prime}_{0},1/c_{1})$,

Hence we deduce the statement of the lemma for some (suitably redefined) constants $c_{0},c_{1}>0$. ∎