Introduction
The stochastic block model is a canonical test case for partitioning algorithms. Vertices are assigned planted community labels, and edges are generated independently with probabilities based on the relationship between communities [16 ] . Studying recovery of the different communities has a rich history, with applications in many areas, including social network analysis, computational biology, and neuroscience [3 , 15 , 16 ] .
In the sparse regime, a central question has been when the planted communities can be detected at fixed expected degree. Here we focus on weak recovery , that is, having a strictly non-negligible advantage over random guessing. Exact recovery is information-theoretically impossible, as, for example, some vertices are isolated. A natural benchmark is given by the Kesten–Stigum threshold (see Theorem 2.1), above which linear estimators using the planted labels on distant generations of the limiting tree retain nonvanishing correlation with a label statistic at the root [21 ] . This threshold is information-theoretically sharp for weak recovery in the symmetric two-community model [19 , 21 , 22 ] , and it is conjectured to be tight for efficient algorithms for any fixed number of symmetric communities [1 , 11 , 21 ] , although information-theoretic recovery can be possible below it [2 , 10 ] .
Following predictions from statistical physics [11 ] , efficient algorithms for weak recovery were developed that reach the Kesten–Stigum threshold in the symmetric two-community model [19 , 22 ] . In parallel, the idea of spectral redemption showed how the non-backtracking operator could overcome the limitations of standard spectral methods in sparse graphs, and planted communities could be recovered from its eigenvectors [18 ] . Its ability to reach the Kesten–Stigum threshold was subsequently established rigorously [9 ] .
The non-backtracking operator is non-Hermitian, however, and is indexed by directed edges rather than vertices, meaning it can be much larger. These features motivated the study of a smaller Hermitian alternative, the Bethe Hessian, coming from statistical physics [24 ] .
For a graph G G G with adjacency matrix A A A and degree matrix D D D , the Bethe Hessian is
H ( t , G ) : = ( t 2 − 1 ) I + D − t A . H(t,G) := (t^2 - 1)I + D - tA. H ( t , G ) := ( t 2 − 1 ) I + D − t A .
From a physical perspective, the Bethe Hessian describes the change in the Bethe free energy when we add a small bias to the random variables. Negative eigenvalues therefore give directions in which adding a bias decreases the Bethe free energy [24 ] . Moreover, the Ihara–Bass formula gives a relationship between the determinants of the non-backtracking operator and the Bethe Hessian [7 ] .
Early numerical experiments suggested that the negative eigenvalues and corresponding eigenvectors of the Bethe Hessian reveal the latent structure of the stochastic block model [24 ] . Rigorous analysis subsequently established that the negative outliers count the informative directions when the common expected degree satisfies d ≥ 2 d \ge2 d ≥ 2 , and that their eigenvectors yield weak recovery for sufficiently large d d d [26 ] . The outlier count was later extended to every fixed d > 1 d > 1 d > 1 , while weak recovery from the corresponding eigenvectors remained open throughout this full range [12 ] . Bethe Hessian methods have also been used to obtain robust recovery above the Kesten–Stigum threshold [20 ] , through a method combining degree truncation with a “boosted” version of the Bethe Hessian given by multiplying the Bethe Hessian on both sides by a matrix counting non-backtracking walks, and additional subspace processing. In comparison, our result concerns the informative eigenspaces of the matrices H ( d , G ) H(\sqrt{d},G) H ( d , G ) and H ( − d , G ) H(-\sqrt{d},G) H ( − d , G ) themselves.
In this work, we identify the Bethe Hessian’s limiting outlier eigenvalue locations and prove that their eigenvectors retain the planted signal. We describe the informative eigenvectors and use them to prove weak recovery throughout the fixed-degree regime. Consider a stochastic block model with fixed parameters, common expected degree d > 1 d > 1 d > 1 , and mean offspring matrix Q Q Q . A planted eigenvalue μ \mu μ is called informative when ∣ μ ∣ > d |\mu| > \sqrt{d} ∣ μ ∣ > d ; positive and negative informative directions correspond to H ( d , G ) H(\sqrt{d},G) H ( d , G ) and H ( − d , G ) H(-\sqrt{d},G) H ( − d , G ) , respectively. The following is an informal version of what we are able to show; the full versions are given as Theorem 2.2 and Theorem 2.3 .
Theorem 1.1 (Informal). For every fixed d > 1 d > 1 d > 1 , informative Bethe Hessian eigenspaces have nonvanishing overlap with the corresponding planted eigenspaces. Whenever a nonconstant planted direction is informative, a randomized rounding of the informative spectral coordinates achieves weak recovery.
The construction also gives a recursive formula for the limiting outlier locations. This closes the gap between counting informative outliers and using their eigenvectors for recovery, showing that a spectral algorithm based on n × n n \times n n × n Hermitian matrices reaches the Kesten–Stigum threshold without requiring the expected degree to tend to infinity. Weak recovery is only information theoretically possible when d > 1 d > 1 d > 1 [21 , 23 ] , as otherwise the local limit Poisson tree is finite almost surely.
The main difficulty in passing to the sparse regime is that large fluctuations cause the eigenvector to have highly irregular structure. Previous works found well-behaved test vectors that identified negative quadratic forms, but still relied on some level of local approximation [12 , 26 ] . Such approximations were too rough to guarantee the structure of true eigenvectors. We instead construct approximate eigenvectors with vanishing residual and nonvanishing planted correlation. Together with the outlier count, these properties identify the informative eigenspaces throughout the fixed-degree regime.
The key point is that a planted direction above the Kesten–Stigum threshold gives rise to a negative outlier of the finite-graph Bethe Hessian. Therefore, we are looking for a solution to
( H ( t , G ) + δ I ) ϕ = 0 , δ > 0. (H(t,G) + \delta I)\phi= 0,\qquad\delta> 0. ( H ( t , G ) + δ I ) ϕ = 0 , δ > 0.
Because this outlier is created by the global planted structure, it is absent from the spectrum of the operator on the local limit. Rather than inverting the singular finite-graph matrix at this eigenvalue, we create weights using the well-defined limiting resolvent ( H ( t , T ) + δ I ) − 1 (H(t,T) + \delta I)^{-1} ( H ( t , T ) + δ I ) − 1 . For the equal-expected-degree model considered here, the unmarked local limit T T T is a Poisson Galton–Watson tree with mean offspring d d d .
The second insight is that these Green’s function weights, together with the planted label field on the tree, can be used to identify the informative eigenspace. The tree resolvent supplies weights adapted to the local geometry, while the label field supplies the planted direction. Iterating this construction gives approximations that are consistent across neighboring vertices and satisfy the eigenvector equation in the limit.
To explain the weights, suppose ϕ \phi ϕ is an eigenvector of H ( t , G ) H(t,G) H ( t , G ) with eigenvalue − δ -\delta − δ . Then, for every u ∈ V ( G ) u \in V(G) u ∈ V ( G ) ,
( t 2 − 1 + deg ( u ) + δ ) ϕ ( u ) = t ∑ w ∼ u ϕ ( w ) . (t^2 - 1 + \operatorname{deg}(u) + \delta)\phi(u) = t \sum_{w \sim u} \phi(w). ( t 2 − 1 + deg ( u ) + δ ) ϕ ( u ) = t w ∼ u ∑ ϕ ( w ) .
For every v ∼ u v \sim u v ∼ u , whenever the relevant entries are nonzero, writing formally Γ u ( v ) = ϕ ( u ) / ϕ ( v ) \Gamma_u^{(v)} = \phi(u)/\phi(v) Γ u ( v ) = ϕ ( u ) / ϕ ( v ) gives
Γ u ( v ) = 1 t + t − 1 ( deg ( u ) − 1 + δ ) − ∑ w ∼ u w ≠ v Γ w ( u ) . (1) \Gamma_u^{(v)} = \frac{1}{t + t^{-1}(\operatorname{deg}(u) - 1 + \delta) - \sum_{\substack{w \sim u \\ w \ne v}} \Gamma_w^{(u)}}. \tag*{(1)} Γ u ( v ) = t + t − 1 ( deg ( u ) − 1 + δ ) − ∑ w ∼ u w = v Γ w ( u ) 1 . (1)
We then perform this same recursion on the infinite local limit. There, the weights are defined by the Green’s function rather than by ratios of a pre-existing eigenvector:
Γ u ( v ) = t ⟨ e u , ( H ( t , T u ( v ) ) + δ I ) − 1 e u ⟩ , \Gamma_u^{(v)} = t \left\langle e_u, \left(H(t,T_u^{(v)}) + \delta I\right)^{-1} e_u \right\rangle, Γ u ( v ) = t ⟨ e u , ( H ( t , T u ( v ) ) + δ I ) − 1 e u ⟩ ,
where T u ( v ) T_u^{(v)} T u ( v ) is the branch containing u u u after removing the edge { u , v } \{u,v\} { u , v } . Here H ( t , T u ( v ) ) H(t,T_u^{(v)}) H ( t , T u ( v ) ) denotes the restriction of H ( t , T ) H(t,T) H ( t , T ) to that branch, so its diagonal retains the degrees in T T T . With this convention, (1) is exactly the Schur complement formula. Starting with Γ u ( v ) = 0 \Gamma_u^{(v)} = 0 Γ u ( v ) = 0 at a finite-depth boundary and recursively updating gives finite-neighborhood approximations to these weights.
The local limit is a Poisson tree, which has branching structure and independence properties we can exploit. The independence between forward subtrees makes the Green’s function recursion a closed distributional system, known as a recursive distributional equation (RDE). Such equations have been used to characterize limiting Stieltjes transforms and prove convergence of empirical spectral measures for locally convergent random graphs [8 ] . Related Green’s function methods have also been developed to study absolutely continuous spectrum on trees [4 , 6 , 17 ] . Here we use individual Green’s function entries to construct approximate eigenvectors, with decay estimates allowing the weights to be approximated from finite neighborhoods.
Another advantage of considering the infinite tree is that H ( t , T ) H(t,T) H ( t , T ) is positive semidefinite for t ∈ ( − ∞ , − 1 ] ∪ [ 1 , ∞ ) t \in(-\infty,-1] \cup[1,\infty) t ∈ ( − ∞ , − 1 ] ∪ [ 1 , ∞ ) . Therefore, for δ > 0 \delta> 0 δ > 0 , its shifted inverse is well defined and bounded. This provides a canonical choice of weights; the further decay and approximation estimates are what allow us to use them on the finite graph.
Given the weights Γ u ( v ) \Gamma_u^{(v)} Γ u ( v ) , we want to convert them into an eigenvector induced by the graph. To do this, we consider the planted labels as a Markov random field on the limiting tree. We go to some fixed depth L L L and take a weighted sum of the planted values that we see there, with each weight given by a product of weights along the path to that vertex. Our goal is to show that this estimation is stable. We therefore introduce an operator L \mathcal{L} L , which describes the change in the weighted construction when we pass from level L L L to level L + 1 L+1 L + 1 . For a suitable δ \delta δ , the relevant weighted average is preserved across levels. This stability allows the local approximations to satisfy the eigenvector equation in the limit.
In terms of the correct δ \delta δ , we have two conflicting parts that must balance out. The first is the rate of decay of covariance in the planted label field. Specifically, for a normalized planted label function associated with an eigenvalue μ \mu μ , the covariance on the broadcast tree is ( μ / d ) dist ( x , y ) (\mu/d)^{\operatorname{dist}(x,y)} ( μ / d ) dist ( x , y ) . To counteract this, we choose the Green’s function weights so that the weighted signal remains at a stable scale. Heuristically, if the geometric average of edge weights is g g g , then the d ℓ d^\ell d ℓ vertices in expectation at depth ℓ \ell ℓ would contribute a signal of order
d ℓ ( μ d ) ℓ g ℓ = ( μ g ) ℓ . d^\ell\left(\frac{\mu}{d}\right)^\ell g^\ell= (\mu g)^\ell. d ℓ ( d μ ) ℓ g ℓ = ( μg ) ℓ .
Thus the matching weight would be g = 1 / μ g = 1/\mu g = 1/ μ . If δ \delta δ were smaller, the positive Green’s function weights would be larger and the local formula for the eigenvector would not converge. If δ \delta δ were larger, the Green’s function would decay too quickly and the planted signal would disappear in the limit. At the correct δ \delta δ , the signal survives at a stable scale, allowing the approximations at neighboring vertices to describe the same eigenvector.
Previous analyses have used vectors derived from the Ihara-Bass formula and known structure of outlier eigenvectors of the non-backtracking operator, either directly [26 ] or adapted to the outlier eigenvalue [12 ] . In this work, we allow the weights to depend on both the local geometry and the spectral shift δ \delta δ . An appealing part of this approach is that it suggests a route to other models: construct the Green’s function weights on the local limit, and the outlier eigenvalue corresponds to the shift that matches the planted signal.
AI Acknowledgment: OpenAI’s GPT-6 introduced the key analytic tools used in this argument. Specifically, the authors recently wrote a paper [12 ] that recovered the number of outlier eigenvalues using a test function based on the local Markov random field. They gave this paper to GPT 6-Astra and asked whether these ideas could be used to achieve eigenvector recovery. The response was a version of the general argument suggested here: to build a recursion based on the eigenvector equation and build test vectors based on this recursion. The authors realized that this was a Green’s function recursion and, taking the GPT-6 argument as a preliminary draft, substantially restructured the paper with the relevant history and techniques given this interpretation. GPT-6 was further used to provide feedback on the manuscript and simplify explication.
Main Results
The Stochastic Block Model
Given a symmetric nonnegative matrix P ∈ R r × r P \in\mathbb{R}^{r \times r} P ∈ R r × r and a distribution π \pi π over [ r ] [r] [ r ] for r ≥ 2 r \ge2 r ≥ 2 fixed, the stochastic block model S B M n ( P , π ) \mathrm{SBM}_n(P,\pi) SBM n ( P , π ) generates a random graph G G G on n n n vertices as follows:
Fix a label map σ : [ n ] → [ r ] \sigma: [n] \to[r] σ : [ n ] → [ r ] such that ∣ σ − 1 ( i ) ∣ = π i n |\sigma^{-1}(i)| = \pi_i n ∣ σ − 1 ( i ) ∣ = π i n for every i ∈ [ r ] i \in[r] i ∈ [ r ] .
For every pair of vertices u , v ∈ [ n ] u,v \in[n] u , v ∈ [ n ] , include the edge u v uv uv independently with probability 1 n P σ ( u ) , σ ( v ) \frac{1}{n}P_{\sigma(u),\sigma(v)} n 1 P σ ( u ) , σ ( v ) .
The goal is to show when it is possible to detect the original communities. Specifically, we will focus on the sparse regime, where the expected degree of each vertex is constant.
Throughout, we assume that all vertices in G G G have the same expected degree d > 1 d > 1 d > 1 , i.e.,
d : = ∑ j = 1 r P i j π j > 1 is the same for all i ∈ [ r ] . (2) d := \sum_{j=1}^{r} P_{ij}\pi_j > 1 \qquad\text{is the same for all } i \in[r]. \tag*{(2)} d := j = 1 ∑ r P ij π j > 1 is the same for all i ∈ [ r ] . (2)
The restriction d > 1 d > 1 d > 1 is necessary, as the weak-recovery threshold is at least 1.
Informative eigenvalues
Given S B M n ( P , π ) \mathrm{SBM}_n(P,\pi) SBM n ( P , π ) , define the signal matrix Q : = P Π Q := P\Pi Q := P Π , where Π : = diag ( π 1 , … , π r ) \Pi:= \operatorname{diag}(\pi_1,\ldots,\pi_r) Π := diag ( π 1 , … , π r ) . Note that Q i j = P i j π j Q_{ij} = P_{ij}\pi_j Q ij = P ij π j represents the expected number of neighbors in community j j j of a vertex in community i i i .
As Q Q Q is similar to Π 1 / 2 P Π 1 / 2 \Pi^{1/2}P\Pi^{1/2} Π 1/2 P Π 1/2 , it has real eigenvalues. We order the eigenvalues of Q Q Q by absolute value as
d = μ 1 ≥ ∣ μ 2 ∣ ≥ ⋯ ≥ ∣ μ r ∣ . (3) d = \mu_1 \ge|\mu_2| \ge\cdots\ge|\mu_r|. \tag*{(3)} d = μ 1 ≥ ∣ μ 2 ∣ ≥ ⋯ ≥ ∣ μ r ∣. (3)
Definition 2.1. An eigenvalue μ \mu μ of the signal matrix Q Q Q is informative if μ 2 > d \mu^2 > d μ 2 > d . The model is above the Kesten–Stigum threshold if there is an informative eigenfunction orthogonal to the constant function in L 2 ( π ) L^2(\pi) L 2 ( π ) .
This is the natural threshold for linear reconstruction on the local Galton–Watson tree. For a nonzero eigenvalue μ i \mu_i μ i , the corresponding eigenfunction sums at depth ℓ \ell ℓ , normalized by μ i ℓ \mu_i^\ell μ i ℓ , form a martingale whose increment variances are proportional to ( d / μ i 2 ) ℓ (d/\mu_i^2)^\ell ( d / μ i 2 ) ℓ . These variances are summable precisely when μ i 2 > d \mu_i^2>d μ i 2 > d , so the normalized signal has bounded second moment exactly above this threshold. Thus, r + r_+ r + and r − r_- r − are the numbers of positive and negative informative eigenvalues, respectively.
Our result
Let G n ∼ S B M n ( P , π ) G_n\sim\mathrm{SBM}_n(P,\pi) G n ∼ SBM n ( P , π ) , where the fixed parameters satisfy (2) . Let Q Q Q be the mean offspring matrix, and choose real eigenfunctions Q φ i = μ i φ i Q\varphi_i=\mu_i\varphi_i Q φ i = μ i φ i orthonormal in L 2 ( π ) L^2(\pi) L 2 ( π ) , with φ 1 ∝ 1 \varphi_1\propto1 φ 1 ∝ 1 . Write
X i ( u ) : = φ i ( σ ( u ) ) . X_i(u):=\varphi_i(\sigma(u)). X i ( u ) := φ i ( σ ( u )) .
Thus ⟨ X i , X j ⟩ = n 1 { i = j } \langle X_i,X_j\rangle=n\mathbf{1}_{\{i=j\}} ⟨ X i , X j ⟩ = n 1 { i = j } under our deterministic community-size convention. Positive and negative planted eigenvalues are treated using H ( d , G n ) H(\sqrt{d},G_n) H ( d , G n ) and H ( − d , G n ) H(-\sqrt{d},G_n) H ( − d , G n ) , respectively.
The number of negative outliers is known throughout the fixed-degree regime d > 1 d>1 d > 1 [12 ] , while weak recovery from the eigenvectors was previously established for sufficiently large d d d [26 ] . Our first result identifies the corresponding eigenspaces throughout the fixed-degree regime. We construct vectors from the planted labels in local neighborhoods, with weights given by the Green’s function on the limiting tree, and show that these vectors approximate the actual Bethe-Hessian eigenspaces. This also gives the limiting outlier locations and the overlap with the planted directions.
Theorem 2.2 (Outlier eigenvalues and eigenspaces). Let G n ∼ S B M n ( P , π ) G_n\sim\mathrm{SBM}_n(P,\pi) G n ∼ SBM n ( P , π ) have fixed parameters and common expected degree d > 1 d>1 d > 1 . List the informative planted eigenvalues, counted with multiplicity, as
μ 1 + ≥ ⋯ ≥ μ r + + > d , μ 1 − ≤ ⋯ ≤ μ r − − < − d . \mu_1^+\ge\cdots\ge\mu_{r_+}^+>\sqrt{d},\qquad\mu_1^-\le\cdots\le\mu_{r_-}^-<-\sqrt{d}. μ 1 + ≥ ⋯ ≥ μ r + + > d , μ 1 − ≤ ⋯ ≤ μ r − − < − d . Order the eigenvalues of each Bethe Hessian increasingly. There is a deterministic strictly increasing function δ : ( d , d ] → ( 0 , ∞ ) \delta:(\sqrt{d},d]\to(0,\infty) δ : ( d , d ] → ( 0 , ∞ ) such that, as n → ∞ n\to\infty n → ∞ and ordering eigenvalues from most negative to most positive,
λ i ( H ( d , G n ) ) ⟶ P − δ ( μ i + ) , i ∈ [ r + ] , \lambda_i(H(\sqrt{d},G_n))\overset{\mathrm P}{\longrightarrow}-\delta(\mu_i^+),\qquad i\in[r_+], λ i ( H ( d , G n )) ⟶ P − δ ( μ i + ) , i ∈ [ r + ] , λ j ( H ( − d , G n ) ) ⟶ P − δ ( ∣ μ j − ∣ ) , j ∈ [ r − ] . \lambda_j(H(-\sqrt{d},G_n))\overset{\mathrm P}{\longrightarrow}-\delta(|\mu_j^-|),\qquad j\in[r_-]. λ j ( H ( − d , G n )) ⟶ P − δ ( ∣ μ j − ∣ ) , j ∈ [ r − ] . For each distinct informative eigenvalue μ \mu μ , let E μ , n E_{\mu,n} E μ , n be the span of the corresponding outlier eigenvectors. There exists c μ > 0 c_\mu>0 c μ > 0 , depending only on Q Q Q and μ \mu μ , such that, with probability tending to one,
∥ Proj E μ , n x ∥ 2 ≥ c μ ∥ x ∥ 2 for every x ∈ span { X i : μ i = μ } . \|\operatorname{Proj}_{E_{\mu,n}}x\|_2\ge c_\mu\|x\|_2\qquad\text{for every }x\in\operatorname{span}\{X_i:\mu_i=\mu\}. ∥ Proj E μ , n x ∥ 2 ≥ c μ ∥ x ∥ 2 for every x ∈ span { X i : μ i = μ } . In particular, if μ i \mu_i μ i is simple and v i , n v_{i,n} v i , n is its unit outlier eigenvector, then there exists a deterministic q μ i > 0 q_{\mu_i}>0 q μ i > 0 such that
∣ ⟨ v i , n , X i ⟩ ∣ n = q μ i + o P ( 1 ) . (4) \frac{|\langle v_{i,n},X_i\rangle|}{\sqrt{n}}=q_{\mu_i}+o_{\mathrm P}(1). \tag*{(4)} n ∣ ⟨ v i , n , X i ⟩ ∣ = q μ i + o P ( 1 ) . (4)
This says that each true eigenvector has nontrivial inner product with the planted eigenspace. Given this, we can use standard arguments to achieve weak recovery.
For labelings σ , σ ^ : [ n ] → [ r ] \sigma,\widehat{\sigma}:[n]\to[r] σ , σ : [ n ] → [ r ] , define the centered overlap
ov ( σ , σ ^ ) : = max τ ∈ S r 1 n ∑ u = 1 n [ 1 { σ ( u ) = τ ( σ ^ ( u ) ) } − π τ ( σ ^ ( u ) ) ] . \operatorname{ov}(\sigma,\widehat{\sigma}):=\max_{\tau\in S_r}\frac{1}{n}\sum_{u=1}^{n}\left[\mathbf{1}\{\sigma(u)=\tau(\widehat{\sigma}(u))\}-\pi_{\tau(\widehat{\sigma}(u))}\right]. ov ( σ , σ ) := τ ∈ S r max n 1 u = 1 ∑ n [ 1 { σ ( u ) = τ ( σ ( u ))} − π τ ( σ ( u )) ] .
For a fixed permutation τ \tau τ , the subtracted term is the agreement expected from independent planted labels with proportions π \pi π , keeping the predicted labels fixed. We say that an algorithm achieves weak recovery if its centered overlap is bounded below by a positive constant with probability tending to one. For balanced communities, this is the usual agreement after relabeling, minus 1 / r 1/r 1/ r .
Theorem 2.3 (Weak recovery). Assume that the SBM parameters are fixed and satisfy (2) . Let c μ > 0 c_\mu> 0 c μ > 0 be the constants in Theorem 2.2 , and set π min : = min a ∈ [ r ] π a \pi_{\min} := \min_{a\in[r]} \pi_a π m i n := min a ∈ [ r ] π a . For every fixed choice of the SBM parameters, there is a randomized polynomial-time algorithm, with constants depending on those parameters, that rounds the informative Bethe-Hessian embedding to an output σ ^ n \widehat{\sigma}_n σ n satisfying, with probability 1 − o n ( 1 ) 1-o_n(1) 1 − o n ( 1 ) ,
ov ( σ , σ ^ n ) ≥ π min 64 r 2 ( r − 1 ) ∑ i ≥ 2 ∣ μ i ∣ > d c μ i 2 . \operatorname{ov}(\sigma,\widehat{\sigma}_n) \ge\frac{\pi_{\min}}{64r^2(r-1)} \sum_{\substack{i\ge2\\ |\mu_i|>\sqrt{d}}} c_{\mu_i}^2. ov ( σ , σ n ) ≥ 64 r 2 ( r − 1 ) π m i n i ≥ 2 ∣ μ i ∣ > d ∑ c μ i 2 . In particular, weak recovery is possible whenever
max i ≥ 2 ∣ μ i ∣ > d . \max_{i\ge2}|\mu_i|>\sqrt{d}. i ≥ 2 max ∣ μ i ∣ > d .
Remark 2.4. For the symmetric two-community model with
π = ( 1 / 2 , 1 / 2 ) , P = ( a b b a ) , \pi=(1/2,1/2), \qquad P=\begin{pmatrix}a&b\\b&a\end{pmatrix}, π = ( 1/2 , 1/2 ) , P = ( a b b a ) ,
the expected degree is d = ( a + b ) / 2 d=(a+b)/2 d = ( a + b ) /2 , and the nonconstant planted eigenvalue is μ 2 = ( a − b ) / 2 \mu_2=(a-b)/2 μ 2 = ( a − b ) /2 . Thus Theorem 2.3 gives weak recovery by randomized rounding of Bethe-Hessian eigenvectors whenever
( a − b ) 2 > 2 ( a + b ) . (a-b)^2>2(a+b). ( a − b ) 2 > 2 ( a + b ) .
This achieves the information-theoretically optimal weak-recovery threshold, predicted in [11 ] and established rigorously in [21 ] .
The theorem reaches the Kesten–Stigum threshold throughout the fixed degree regime d > 1 d>1 d > 1 . The proof comes in three parts. First, we construct the Green’s function weights and study their transfer operator. Proposition 4.9 identifies the shift δ ( μ ) \delta(\mu) δ ( μ ) associated with each informative planted eigenvalue. We then construct the corresponding fields on the limiting tree and approximate them using finite neighborhoods. Propositions 7.2 and 7.3 transfer these fields to the finite graph and identify the informative eigenspaces, completing the proof of Theorem 2.2 . Finally, § 9 proves Theorem 2.3 by a randomized rounding of the spectral coordinates.
Green’s function weights
In this section, we will consider the set of weights that work for the local limit of the SBM, the Poisson tree. Take G G G to be any graph which may be finite or infinite, and let E : = { ( u , v ) : u ∼ v } E:=\{(u,v):u\sim v\} E := {( u , v ) : u ∼ v } denote the set of directed edges in G G G . Let t ≥ d > 1 t\ge\sqrt{d}>1 t ≥ d > 1 , δ > 0 \delta>0 δ > 0 , and c δ : = t t 2 + δ c_\delta:=\frac{t}{t^2+\delta} c δ := t 2 + δ t . For ( T , o ) (T,o) ( T , o ) a rooted tree, for any u ∈ V ( T ) ∖ { o } u\in V(T)\setminus\{o\} u ∈ V ( T ) ∖ { o } , let p ( u ) p(u) p ( u ) denote the parent of u u u . For any u ∈ V ( T ) u\in V(T) u ∈ V ( T ) let ch ( u ) \operatorname{ch}(u) ch ( u ) denote the set of children of u u u .
We will build our resolvent recursively, starting from 0 0 0 .
Definition 3.1. Given graph G G G , for every M ∈ Z ≥ 0 M \in\mathbb{Z}_{\geq0} M ∈ Z ≥ 0 and ( u , v ) ∈ E (u,v) \in E ( u , v ) ∈ E , define the quantity ( Γ u ( v ) ) ( M ) (\Gamma_u^{(v)})^{(M)} ( Γ u ( v ) ) ( M ) by
( Γ u ( v ) ) ( 0 ) : = 0 , ( Γ u ( v ) ) ( M + 1 ) : = t t 2 + deg ( u ) − 1 + δ − t ∑ w ∼ u w ≠ v ( Γ w ( u ) ) ( M ) . (5) (\Gamma_u^{(v)})^{(0)} := 0,\qquad(\Gamma_u^{(v)})^{(M+1)} := \frac{t}{t^2+\deg(u)-1+\delta-t\sum_{\substack{w\sim u\\w\ne v}}(\Gamma_w^{(u)})^{(M)}}. \tag*{(5)} ( Γ u ( v ) ) ( 0 ) := 0 , ( Γ u ( v ) ) ( M + 1 ) := t 2 + deg ( u ) − 1 + δ − t ∑ w ∼ u w = v ( Γ w ( u ) ) ( M ) t . (5)
Our goal is to show that by passing to this iteration, (5) becomes a self-consistent equation. To do this, we note some properties of the recursion.
Lemma 3.2. For every ( u , v ) ∈ E (u,v) \in E ( u , v ) ∈ E , 0 = ( Γ u ( v ) ) ( 0 ) ≤ ( Γ u ( v ) ) ( 1 ) ≤ ⋯ ≤ c δ 0=(\Gamma_u^{(v)})^{(0)}\leq(\Gamma_u^{(v)})^{(1)}\leq\cdots\leq c_\delta 0 = ( Γ u ( v ) ) ( 0 ) ≤ ( Γ u ( v ) ) ( 1 ) ≤ ⋯ ≤ c δ .
Proof. We show by induction that 0 = ( Γ u ( v ) ) ( 0 ) ≤ ( Γ u ( v ) ) ( 1 ) ≤ ⋯ 0=(\Gamma_u^{(v)})^{(0)}\leq(\Gamma_u^{(v)})^{(1)}\leq\cdots 0 = ( Γ u ( v ) ) ( 0 ) ≤ ( Γ u ( v ) ) ( 1 ) ≤ ⋯ . Indeed, we have ( Γ u ( v ) ) ( 0 ) = 0 < ( Γ u ( v ) ) ( 1 ) (\Gamma_u^{(v)})^{(0)}=0<(\Gamma_u^{(v)})^{(1)} ( Γ u ( v ) ) ( 0 ) = 0 < ( Γ u ( v ) ) ( 1 ) for all ( u , v ) ∈ E (u,v)\in E ( u , v ) ∈ E . Inductively, if ( Γ u ( v ) ) ( M − 1 ) ≤ ( Γ u ( v ) ) ( M ) (\Gamma_u^{(v)})^{(M-1)}\leq(\Gamma_u^{(v)})^{(M)} ( Γ u ( v ) ) ( M − 1 ) ≤ ( Γ u ( v ) ) ( M ) for all ( u , v ) ∈ E (u,v)\in E ( u , v ) ∈ E , then
∑ w ∼ u w ≠ v ( Γ w ( u ) ) ( M − 1 ) ≤ ∑ w ∼ u w ≠ v ( Γ w ( u ) ) ( M ) , \sum_{\substack{w\sim u\\w\ne v}}(\Gamma_w^{(u)})^{(M-1)}
\leq
\sum_{\substack{w\sim u\\w\ne v}}(\Gamma_w^{(u)})^{(M)}, w ∼ u w = v ∑ ( Γ w ( u ) ) ( M − 1 ) ≤ w ∼ u w = v ∑ ( Γ w ( u ) ) ( M ) ,
which gives ( Γ u ( v ) ) ( M ) ≤ ( Γ u ( v ) ) ( M + 1 ) (\Gamma_u^{(v)})^{(M)}\leq(\Gamma_u^{(v)})^{(M+1)} ( Γ u ( v ) ) ( M ) ≤ ( Γ u ( v ) ) ( M + 1 ) . Furthermore, if 0 ≤ ( Γ u ( v ) ) ( M ) ≤ 1 / t 0\leq(\Gamma_u^{(v)})^{(M)}\leq1/t 0 ≤ ( Γ u ( v ) ) ( M ) ≤ 1/ t for all ( u , v ) ∈ E (u,v)\in E ( u , v ) ∈ E (which is true for M = 0 M=0 M = 0 ), then we have
t 2 + deg ( u ) − 1 + δ − t ∑ w ∼ u w ≠ v ( Γ w ( u ) ) ( M ) ≥ t 2 + δ , t^2+\deg(u)-1+\delta-t\sum_{\substack{w\sim u\\w\ne v}}(\Gamma_w^{(u)})^{(M)}\geq t^2+\delta, t 2 + deg ( u ) − 1 + δ − t w ∼ u w = v ∑ ( Γ w ( u ) ) ( M ) ≥ t 2 + δ ,
which gives ( Γ u ( v ) ) ( M + 1 ) ≤ t t 2 + δ = c δ < 1 / t (\Gamma_u^{(v)})^{(M+1)}\leq\frac{t}{t^2+\delta}=c_\delta<1/t ( Γ u ( v ) ) ( M + 1 ) ≤ t 2 + δ t = c δ < 1/ t . Hence 0 ≤ ( Γ u ( v ) ) ( M ) ≤ c δ 0\leq(\Gamma_u^{(v)})^{(M)}\leq c_\delta 0 ≤ ( Γ u ( v ) ) ( M ) ≤ c δ for all M ≥ 0 M\geq0 M ≥ 0 .
The above lemma allows us to define the following.
Definition 3.3. For every ( u , v ) ∈ E (u,v)\in E ( u , v ) ∈ E , define Γ u ( v ) : = lim M → ∞ ( Γ u ( v ) ) ( M ) \Gamma_u^{(v)}:=\lim_{M\to\infty}(\Gamma_u^{(v)})^{(M)} Γ u ( v ) := lim M → ∞ ( Γ u ( v ) ) ( M ) . We know from Lemma 3.2 and (5) that
Γ u ( v ) = t t 2 + deg ( u ) − 1 + δ − t ∑ w ∼ u w ≠ v Γ w ( u ) , 0 ≤ Γ u ( v ) ≤ c δ . (6) \Gamma_u^{(v)}=\frac{t}{t^2+\deg(u)-1+\delta-t\sum_{\substack{w\sim u\\w\ne v}}\Gamma_w^{(u)}},\qquad0\leq\Gamma_u^{(v)}\leq c_\delta. \tag*{(6)} Γ u ( v ) = t 2 + deg ( u ) − 1 + δ − t ∑ w ∼ u w = v Γ w ( u ) t , 0 ≤ Γ u ( v ) ≤ c δ . (6)
When G G G is a rooted tree and u u u is a non-root vertex, we will simply use Γ u \Gamma_u Γ u to denote Γ u ( p ( u ) ) \Gamma_u^{(p(u))} Γ u ( p ( u )) and use Γ u ( M ) \Gamma_u^{(M)} Γ u ( M ) to denote ( Γ u ( p ( u ) ) ) ( M ) (\Gamma_u^{(p(u))})^{(M)} ( Γ u ( p ( u )) ) ( M ) . For the root o o o , we define Γ o ( M ) \Gamma_o^{(M)} Γ o ( M ) analogously without excluding any neighbor, and set Γ o : = lim M → ∞ Γ o ( M ) \Gamma_o:=\lim_{M\to\infty}\Gamma_o^{(M)} Γ o := lim M → ∞ Γ o ( M ) . In particular,
Γ o = t t 2 + deg ( o ) + δ − t ∑ w ∼ o Γ w . (7) \Gamma_o=\frac{t}{t^2+\deg(o)+\delta-t\sum_{w\sim o}\Gamma_w}. \tag*{(7)} Γ o = t 2 + deg ( o ) + δ − t ∑ w ∼ o Γ w t . (7)
The transfer operator
Given the definition of these Green’s function random variables Γ u \Gamma_u Γ u , we now introduce an operator that gives the value ϕ ( u ) / ϕ ( v ) \phi(u)/\phi(v) ϕ ( u ) / ϕ ( v ) in terms of a ratio at distance L L L rather than L − 1 L-1 L − 1 . This is the straightforward fact that on any graph, we can write the Green’s function as a sum over neighbors (see, e.g. [13 Lemma 8.3] ). From now on, we restrict to t ≥ d > 1 t\geq\sqrt{d}>1 t ≥ d > 1 .
Rooted trees
Definition 4.1. Let Ω \Omega Ω denote the collection of all locally finite rooted trees with root o o o . For every such tree T ∈ Ω T \in\Omega T ∈ Ω , let T 1 , … , T K T_1,\ldots,T_K T 1 , … , T K be the deg ( o ) \operatorname{deg}(o) deg ( o ) forward subtrees rooted at children of o o o . Also, define the map Γ : Ω → ( 0 , c δ ] \Gamma:\Omega\to(0,c_\delta] Γ : Ω → ( 0 , c δ ] by Γ ( T ) : = Γ o \Gamma(T):=\Gamma_o Γ ( T ) := Γ o , with Γ o \Gamma_o Γ o as in Definition 3.3 .
We associate with Ω \Omega Ω the probability measure given by the Poisson Galton–Watson tree.
Definition 4.2. Let ν \nu ν be the law on Ω \Omega Ω of a Galton–Watson tree with offspring distribution Poi ( d ) \operatorname{Poi}(d) Poi ( d ) . Write L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) for the space of measurable functions f : Ω → C f:\Omega\to\mathbb{C} f : Ω → C satisfying
∫ Ω ∣ f ( T ) ∣ 2 d ν ( T ) < ∞ , \int_{\Omega} |f(T)|^2\,d\nu(T)<\infty, ∫ Ω ∣ f ( T ) ∣ 2 d ν ( T ) < ∞ , where functions that are equal ν \nu ν -almost surely are identified. Equip this space with the inner product
⟨ f , g ⟩ : = ∫ Ω f ( T ) ‾ g ( T ) d ν ( T ) = E T ∼ ν [ f ( T ) ‾ g ( T ) ] . \langle f,g\rangle:=\int_{\Omega}\overline{f(T)}g(T)\,d\nu(T)=\mathbb{E}_{T\sim\nu}\left[\overline{f(T)}g(T)\right]. ⟨ f , g ⟩ := ∫ Ω f ( T ) g ( T ) d ν ( T ) = E T ∼ ν [ f ( T ) g ( T ) ] .
We first show the uniqueness and continuity of the function Γ \Gamma Γ on Ω \Omega Ω .
Lemma 4.3. Fix t ≥ d > 1 t\ge\sqrt{d}>1 t ≥ d > 1 . For each δ > 0 \delta>0 δ > 0 , there is a unique, up to ν \nu ν -almost-sure equality, measurable function Γ δ : Ω → [ 0 , c δ ] \Gamma_\delta:\Omega\to[0,c_\delta] Γ δ : Ω → [ 0 , c δ ] satisfying (7) . Moreover, δ ↦ Γ δ \delta\mapsto\Gamma_\delta δ ↦ Γ δ is continuous in L 1 ( ν ) L^1(\nu) L 1 ( ν ) on ( 0 , ∞ ) (0,\infty) ( 0 , ∞ ) .
Proof. Suppose Γ \Gamma Γ and Γ ′ \Gamma' Γ ′ are two different functions that satisfy (7) . Then we have
Γ ( T ) = t t 2 + K + δ − t ∑ j = 1 K Γ ( T j ) , Γ ′ ( T ) = t t 2 + K + δ − t ∑ j = 1 K Γ ′ ( T j ) . \Gamma(T)=\frac{t}{t^2+K+\delta-t\sum_{j=1}^{K}\Gamma(T_j)},\qquad
\Gamma'(T)=\frac{t}{t^2+K+\delta-t\sum_{j=1}^{K}\Gamma'(T_j)}. Γ ( T ) = t 2 + K + δ − t ∑ j = 1 K Γ ( T j ) t , Γ ′ ( T ) = t 2 + K + δ − t ∑ j = 1 K Γ ′ ( T j ) t . Write Γ = Γ ( T ) , Γ j = Γ ( T j ) , K = K ( T ) \Gamma=\Gamma(T),\Gamma_j=\Gamma(T_j),K=K(T) Γ = Γ ( T ) , Γ j = Γ ( T j ) , K = K ( T ) . Then
∣ Γ − Γ ′ ∣ = Γ Γ ′ ∣ ∑ j = 1 K ( Γ j − Γ j ′ ) ∣ ≤ c δ 2 ∑ j = 1 K ∣ Γ j − Γ j ′ ∣ . |\Gamma-\Gamma'|=\Gamma\Gamma'\left|\sum_{j=1}^{K}(\Gamma_j-\Gamma'_j)\right|\le c_\delta^2\sum_{j=1}^{K}|\Gamma_j-\Gamma'_j|. ∣Γ − Γ ′ ∣ = Γ Γ ′ j = 1 ∑ K ( Γ j − Γ j ′ ) ≤ c δ 2 j = 1 ∑ K ∣ Γ j − Γ j ′ ∣. Since T , T j T,T_j T , T j have the same law, we get that E ∣ Γ − Γ ′ ∣ ≤ d c δ 2 E ∣ Γ − Γ ′ ∣ \mathbb{E}|\Gamma-\Gamma'|\le dc_\delta^2\mathbb{E}|\Gamma-\Gamma'| E ∣Γ − Γ ′ ∣ ≤ d c δ 2 E ∣Γ − Γ ′ ∣ , so E ∣ Γ − Γ ′ ∣ = 0 \mathbb{E}|\Gamma-\Gamma'|=0 E ∣Γ − Γ ′ ∣ = 0 . This shows uniqueness of Γ \Gamma Γ .
Similarly, for the obtained Γ \Gamma Γ , we get that
∣ Γ δ − Γ δ 0 ∣ = Γ δ Γ δ 0 ∣ δ 0 − δ t + ∑ j = 1 K ( Γ δ ( T j ) − Γ δ 0 ( T j ) ) ∣ ≤ c δ c δ 0 ∣ δ 0 − δ t + ∑ j = 1 K ( Γ δ ( T j ) − Γ δ 0 ( T j ) ) ∣ . |\Gamma_\delta-\Gamma_{\delta_0}|=\Gamma_\delta\Gamma_{\delta_0}\left|\frac{\delta_0-\delta}{t}+\sum_{j=1}^{K}\left(\Gamma_\delta(T_j)-\Gamma_{\delta_0}(T_j)\right)\right|
\le c_\delta c_{\delta_0}\left|\frac{\delta_0-\delta}{t}+\sum_{j=1}^{K}\left(\Gamma_\delta(T_j)-\Gamma_{\delta_0}(T_j)\right)\right|. ∣ Γ δ − Γ δ 0 ∣ = Γ δ Γ δ 0 t δ 0 − δ + j = 1 ∑ K ( Γ δ ( T j ) − Γ δ 0 ( T j ) ) ≤ c δ c δ 0 t δ 0 − δ + j = 1 ∑ K ( Γ δ ( T j ) − Γ δ 0 ( T j ) ) . We obtain that
E ∣ Γ δ − Γ δ 0 ∣ ≤ c δ c δ 0 t ∣ δ 0 − δ ∣ + c δ c δ 0 d E ∣ Γ δ − Γ δ 0 ∣ , \mathbb{E}|\Gamma_\delta-\Gamma_{\delta_0}|
\le\frac{c_\delta c_{\delta_0}}{t}|\delta_0-\delta|+c_\delta c_{\delta_0}d\mathbb{E}|\Gamma_\delta-\Gamma_{\delta_0}|, E ∣ Γ δ − Γ δ 0 ∣ ≤ t c δ c δ 0 ∣ δ 0 − δ ∣ + c δ c δ 0 d E ∣ Γ δ − Γ δ 0 ∣ , ≤ c δ c δ 0 t 1 − d c δ c δ 0 ∣ δ 0 − δ ∣ ⟶ 0 as δ → δ 0 . \le\frac{\frac{c_\delta c_{\delta_0}}{t}}{1-dc_\delta c_{\delta_0}}|\delta_0-\delta|\longrightarrow0\text{ as }\delta\to\delta_0. ≤ 1 − d c δ c δ 0 t c δ c δ 0 ∣ δ 0 − δ ∣ ⟶ 0 as δ → δ 0 .
We then have the following relation from perturbing δ \delta δ .
Lemma 4.4. Γ δ \Gamma_\delta Γ δ is strictly decreasing in δ \delta δ . Moreover Γ δ ↑ 1 / t \Gamma_\delta\uparrow1/t Γ δ ↑ 1/ t as δ ↓ 0 \delta\downarrow0 δ ↓ 0 , almost surely.
Proof. We first show that Γ δ \Gamma_\delta Γ δ is nonincreasing. Let δ 1 < δ 2 \delta_1 < \delta_2 δ 1 < δ 2 . Recall that Γ δ 1 ( 0 ) = Γ δ 2 ( 0 ) = 0 \Gamma_{\delta_1}^{(0)} = \Gamma_{\delta_2}^{(0)} = 0 Γ δ 1 ( 0 ) = Γ δ 2 ( 0 ) = 0 . It is also easy to check from the recursion that if Γ δ 1 ( m ) ≥ Γ δ 2 ( m ) \Gamma_{\delta_1}^{(m)} \ge\Gamma_{\delta_2}^{(m)} Γ δ 1 ( m ) ≥ Γ δ 2 ( m ) , then Γ δ 1 ( m + 1 ) ≥ Γ δ 2 ( m + 1 ) \Gamma_{\delta_1}^{(m+1)} \ge\Gamma_{\delta_2}^{(m+1)} Γ δ 1 ( m + 1 ) ≥ Γ δ 2 ( m + 1 ) .
Now observe that
Γ δ 1 ( T ) − Γ δ 2 ( T ) = Γ δ 1 ( T ) Γ δ 2 ( T ) ( δ 2 − δ 1 t + ∑ j = 1 K ( Γ δ 1 ( T j ) − Γ δ 2 ( T j ) ) ) . \Gamma_{\delta_1}(T)-\Gamma_{\delta_2}(T)=\Gamma_{\delta_1}(T)\Gamma_{\delta_2}(T)\left(\frac{\delta_2-\delta_1}{t}+\sum_{j=1}^{K}\left(\Gamma_{\delta_1}(T_j)-\Gamma_{\delta_2}(T_j)\right)\right). Γ δ 1 ( T ) − Γ δ 2 ( T ) = Γ δ 1 ( T ) Γ δ 2 ( T ) ( t δ 2 − δ 1 + j = 1 ∑ K ( Γ δ 1 ( T j ) − Γ δ 2 ( T j ) ) ) . Since Γ δ 1 ( T ) Γ δ 2 ( T ) > 0 \Gamma_{\delta_1}(T)\Gamma_{\delta_2}(T)>0 Γ δ 1 ( T ) Γ δ 2 ( T ) > 0 , the above is > 0 >0 > 0 .
Since all Γ δ < 1 / t \Gamma_\delta<1/t Γ δ < 1/ t , let Γ 0 : = lim δ ↓ 0 Γ δ \Gamma_0:=\lim_{\delta\downarrow0}\Gamma_\delta Γ 0 := lim δ ↓ 0 Γ δ (the pointwise limit function). Letting e : = 1 − t Γ 0 e:=1-t\Gamma_0 e := 1 − t Γ 0 , we know from the recursion formula that
e = 1 − t 2 t 2 + ∑ j = 1 K e j = ∑ j = 1 K e j t 2 + ∑ j = 1 K e j . e=1-\frac{t^2}{t^2+\sum_{j=1}^{K}e_j}=\frac{\sum_{j=1}^{K}e_j}{t^2+\sum_{j=1}^{K}e_j}. e = 1 − t 2 + ∑ j = 1 K e j t 2 = t 2 + ∑ j = 1 K e j ∑ j = 1 K e j . If E e > 0 \mathbb{E}e>0 E e > 0 , then we have E e < E ( t − 2 ∑ j = 1 K e j ) = t − 2 d E e ≤ E e \mathbb{E}e<\mathbb{E}\left(t^{-2}\sum_{j=1}^{K}e_j\right)=t^{-2}d\mathbb{E}e\le\mathbb{E}e E e < E ( t − 2 ∑ j = 1 K e j ) = t − 2 d E e ≤ E e , a contradiction. Hence E e = 0 \mathbb{E}e=0 E e = 0 and Γ 0 = 1 / t \Gamma_0=1/t Γ 0 = 1/ t almost surely.
All future stated (in)equalities in L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) occur with probability 1.
Introducing the transfer operator
Definition 4.5. On L 2 ( Ω ) L^2(\Omega) L 2 ( Ω ) , define the operator L : L 2 ( Ω ) → L 2 ( Ω ) \mathcal{L}:L^2(\Omega)\to L^2(\Omega) L : L 2 ( Ω ) → L 2 ( Ω ) by
( L f ) ( T ) : = Γ ( T ) ∑ j = 1 K f ( T j ) . (\mathcal{L}f)(T):=\Gamma(T)\sum_{j=1}^{K}f(T_j). ( L f ) ( T ) := Γ ( T ) j = 1 ∑ K f ( T j ) .
Observation 4.6. The above map is well-defined. In other words, ∥ L ∥ < ∞ \|\mathcal{L}\|<\infty ∥ L ∥ < ∞ .
Proof. Recall from the previous section that Γ ( T ) ≤ c δ \Gamma(T)\le c_\delta Γ ( T ) ≤ c δ for all T T T . Thus
∥ L f ∥ 2 2 = E T ∼ ν [ Γ ( T ) 2 ∣ ∑ j = 1 deg ( o ) f ( T j ) ∣ 2 ] ≤ c δ 2 ( d ∥ f ∥ 2 2 + d 2 ∣ E f ∣ 2 ) ≤ c δ 2 ( d 2 + d ) ∥ f ∥ 2 2 . (8) \|\mathcal{L}f\|_2^2=\mathbb{E}_{T\sim\nu}\left[\Gamma(T)^2\left|\sum_{j=1}^{\deg(o)}f(T_j)\right|^2\right]\le c_\delta^2\left(d\|f\|_2^2+d^2|\mathbb{E}f|^2\right)\le c_\delta^2(d^2+d)\|f\|_2^2. \tag*{(8)} ∥ L f ∥ 2 2 = E T ∼ ν Γ ( T ) 2 j = 1 ∑ d e g ( o ) f ( T j ) 2 ≤ c δ 2 ( d ∥ f ∥ 2 2 + d 2 ∣ E f ∣ 2 ) ≤ c δ 2 ( d 2 + d ) ∥ f ∥ 2 2 . (8)
Our next goal will be to show that this transfer operator has a spectral gap. Therefore iterating it sufficiently will cause convergence to the top eigenspace.
Definition 4.7. Let κ \kappa κ denote the spectral radius of L \mathcal{L} L . That is, κ = sup { ∣ z ∣ : z ∈ σ ( L ) } \kappa=\sup\{|z|:z\in\sigma(\mathcal{L})\} κ = sup { ∣ z ∣ : z ∈ σ ( L )} where σ \sigma σ is the spectrum of L \mathcal{L} L . Of course, κ ≤ ∥ L ∥ < ∞ \kappa\le\|\mathcal{L}\|<\infty κ ≤ ∥ L ∥ < ∞ .
We now want to show in our regime of interest properties of the top eigenspace. Let Π \Pi Π be the one-dimensional projection operator, and define the operator L ^ \widehat{\mathcal{L}} L by
Π f : = ( E ν f ) 1 , L ^ : = L ( I − Π ) . \Pi f:=(\mathbb{E}_\nu f)1,\qquad\widehat{\mathcal{L}}:=\mathcal{L}(I-\Pi). Π f := ( E ν f ) 1 , L := L ( I − Π ) .
We first give an upper bound on ∥ L ^ ∥ \|\widehat{\mathcal{L}}\| ∥ L ∥ . Consider any f ∈ L 2 ( Ω ) f \in L^2(\Omega) f ∈ L 2 ( Ω ) and let g = f − E f g=f-\mathbb{E}f g = f − E f . Since E g = 0 \mathbb{E}g=0 E g = 0 , we know from the calculation of (8) that
∥ L g ∥ 2 2 ≤ c δ 2 E T ∼ ν ( ∣ ∑ j = 1 K g ( T j ) ∣ 2 ) = d c δ 2 ∥ g ∥ 2 2 . \|\mathcal{L}g\|_2^2 \le c_\delta^2\mathbb{E}_{T\sim\nu}\left(\left|\sum_{j=1}^{K}g(T_j)\right|^2\right)=dc_\delta^2\|g\|_2^2. ∥ L g ∥ 2 2 ≤ c δ 2 E T ∼ ν j = 1 ∑ K g ( T j ) 2 = d c δ 2 ∥ g ∥ 2 2 .
Hence ∥ L ^ ∥ ≤ d c δ \|\widehat{\mathcal{L}}\|\le\sqrt{d}c_\delta ∥ L ∥ ≤ d c δ . Note that d c δ = d t t 2 + δ < 1 \sqrt{d}c_\delta=\frac{\sqrt{d t}}{t^2+\delta}<1 d c δ = t 2 + δ d t < 1 . We can use this to give a spectral gap on L \mathcal{L} L .
Proposition 4.8. Suppose that the spectral radius κ \kappa κ of L \mathcal{L} L satisfies κ > d c δ \kappa>\sqrt{d}c_\delta κ > d c δ . Then:
There exist nonzero nonnegative right and left eigenfunctions h , ℓ ∈ L 2 ( Ω ) h,\ell\in L^2(\Omega) h , ℓ ∈ L 2 ( Ω ) satisfying
L h = κ h , L ∗ ℓ = κ ℓ . \mathcal{L}h=\kappa h,\qquad\mathcal{L}^{*}\ell=\kappa\ell. L h = κh , L ∗ ℓ = κ ℓ . Almost surely over T ∼ ν T\sim\nu T ∼ ν , we have ℓ ( T ) > 0 \ell(T)>0 ℓ ( T ) > 0 , while h ( T ) = 0 h(T)=0 h ( T ) = 0 on finite trees and h ( T ) > 0 h(T)>0 h ( T ) > 0 on infinite trees.
κ \kappa κ is an algebraically simple eigenvalue of L \mathcal{L} L .
κ \kappa κ is the only point of σ ( L ) \sigma(\mathcal{L}) σ ( L ) with absolute value κ \kappa κ .
There exist C < ∞ C<\infty C < ∞ and 0 < θ < 1 0<\theta<1 0 < θ < 1 such that, for every integer L ≥ 0 L\ge0 L ≥ 0 ,
∥ κ − L L L 1 − h ∥ 2 ≤ C θ L . \|\kappa^{-L}\mathcal{L}^{L}1-h\|_2\le C\theta^L. ∥ κ − L L L 1 − h ∥ 2 ≤ C θ L .
Proof. Proof of (1). Since
L f = L ^ f + ( E f ) L 1 , ∥ L ^ ∥ ≤ d c δ < κ , \mathcal{L}f=\widehat{\mathcal{L}}f+(\mathbb{E}f)\mathcal{L}1,\qquad\|\widehat{\mathcal{L}}\|\le\sqrt{d}c_\delta<\kappa, L f = L f + ( E f ) L 1 , ∥ L ∥ ≤ d c δ < κ ,
L \mathcal{L} L is a rank-one perturbation of an operator of norm at most d c δ \sqrt{d}c_\delta d c δ . Thus r e s s ( L ) ≤ d c δ r_{\mathrm{ess}}(\mathcal{L})\le\sqrt{d}c_\delta r ess ( L ) ≤ d c δ , and every spectral point outside { ∣ z ∣ ≤ d c δ } \{|z|\le\sqrt{d}c_\delta\} { ∣ z ∣ ≤ d c δ } is an isolated eigenvalue of finite algebraic multiplicity. The generalized Krein–Rutman theorem [25 Appendix Theorem 2.4 and Remark on p. 314] therefore gives nonzero h , ℓ ≥ 0 h,\ell\ge0 h , ℓ ≥ 0 satisfying
L h = κ h , L ∗ ℓ = κ ℓ . \mathcal{L}h=\kappa h,\qquad\mathcal{L}^{*}\ell=\kappa\ell. L h = κh , L ∗ ℓ = κ ℓ .
Let K ( T ) K(T) K ( T ) be the degree of the root of T T T . Then
κ h ( T ) = Γ ( T ) ∑ j = 1 K ( T ) h ( T j ) \kappa h(T)=\Gamma(T)\sum_{j=1}^{K(T)}h(T_j) κh ( T ) = Γ ( T ) j = 1 ∑ K ( T ) h ( T j )
shows by induction on height that h ( T ) = 0 h(T)=0 h ( T ) = 0 for finite T T T . Since Γ > 0 \Gamma>0 Γ > 0 , the probability p = ν ( h ( T ) = 0 ) p=\nu(h(T)=0) p = ν ( h ( T ) = 0 ) satisfies p = E [ p K ( T ) ] = e d ( p − 1 ) p=\mathbb{E}[p^{K(T)}]=e^{d(p-1)} p = E [ p K ( T ) ] = e d ( p − 1 ) . As h ≢ 0 h\not\equiv0 h ≡ 0 , p p p equals the extinction probability of the Galton-Watson tree. Hence h > 0 h>0 h > 0 almost surely on infinite trees.
We next show that ℓ \ell ℓ cannot be supported exclusively on finite trees. Let P f i n P_{\mathrm{fin}} P fin be multiplication by their indicator and consider L f i n : = P f i n L P f i n \mathcal{L}_{\mathrm{fin}}:=P_{\mathrm{fin}}\mathcal{L}P_{\mathrm{fin}} L fin := P fin L P fin . As above, L f i n \mathcal{L}_{\mathrm{fin}} L fin is a rank-one perturbation of an operator of norm at most d c δ \sqrt{d}c_\delta d c δ , so every spectral point outside { ∣ z ∣ ≤ d c δ } \{|z|\le\sqrt{d}c_\delta\} { ∣ z ∣ ≤ d c δ } is an eigenvalue. Induction on tree height shows that L f i n \mathcal{L}_{\mathrm{fin}} L fin has no nonzero eigenvalues. Consequently, σ ( L f i n ) ⊆ { ∣ z ∣ ≤ d c δ } \sigma(\mathcal{L}_{\mathrm{fin}})\subseteq\{|z|\le\sqrt{d}c_\delta\} σ ( L fin ) ⊆ { ∣ z ∣ ≤ d c δ } . If P f i n ℓ = ℓ P_{\mathrm{fin}}\ell=\ell P fin ℓ = ℓ , however, then
L f i n ∗ ℓ = P f i n L ∗ P f i n ℓ = κ ℓ , \mathcal{L}_{\mathrm{fin}}^{*}\ell=P_{\mathrm{fin}}\mathcal{L}^{*}P_{\mathrm{fin}}\ell=\kappa\ell, L fin ∗ ℓ = P fin L ∗ P fin ℓ = κ ℓ ,
contradicting κ > d c δ \kappa> \sqrt{d}\,c_{\delta} κ > d c δ .
Now let A : = { T : ℓ ( T ) = 0 } A := \{T : \ell(T) = 0\} A := { T : ℓ ( T ) = 0 } and suppose p = ν ( A ) > 0 p = \nu(A) > 0 p = ν ( A ) > 0 . Positivity and the fact that
⟨ ℓ , L m 1 A ⟩ = κ m ⟨ ℓ , 1 A ⟩ = 0 \langle\ell,\mathcal{L}^{m}\mathbf{1}_{A}\rangle= \kappa^{m}\langle\ell,\mathbf{1}_{A}\rangle= 0 ⟨ ℓ , L m 1 A ⟩ = κ m ⟨ ℓ , 1 A ⟩ = 0
imply that, almost surely, whenever ℓ ( T ) > 0 \ell(T) > 0 ℓ ( T ) > 0 , every depth-m m m subtree avoids A A A . Writing Z m Z_m Z m for the size of generation m m m , the branching property gives
ν ( ℓ > 0 , ∣ T ∣ = ∞ ) ≤ E [ ( 1 − p ) Z m 1 { Z m > 0 } ] ⟶ 0. \nu(\ell> 0,\ |T| = \infty) \leq\mathbb{E}\left[(1-p)^{Z_m}\mathbf{1}_{\{Z_m>0\}}\right] \longrightarrow0. ν ( ℓ > 0 , ∣ T ∣ = ∞ ) ≤ E [ ( 1 − p ) Z m 1 { Z m > 0 } ] ⟶ 0.
Indeed, Z m → ∞ Z_m \to\infty Z m → ∞ on survival and is eventually zero on extinction. This would force ℓ \ell ℓ to be supported on finite trees, contrary to the preceding paragraph. Thus ℓ ( T ) > 0 \ell(T) > 0 ℓ ( T ) > 0 almost surely.
Proof of (2). The κ \kappa κ -eigenspace is one-dimensional: otherwise it contains a nonzero g g g with E g = 0 \mathbb{E}g = 0 E g = 0 , giving a contradiction, as
κ ∥ g ∥ 2 = ∥ L g ∥ 2 = ∥ L ^ g ∥ 2 ≤ d c δ ∥ g ∥ 2 . \kappa\lVert g\rVert_2 = \lVert\mathcal{L}g\rVert_2 = \lVert\widehat{\mathcal{L}}g\rVert_2 \leq\sqrt{d}\,c_{\delta}\lVert g\rVert_2. κ ∥ g ∥ 2 = ∥ L g ∥ 2 = ∥ L g ∥ 2 ≤ d c δ ∥ g ∥ 2 .
A nontrivial Jordan chain would then give ( L − κ I ) g = h (\mathcal{L}-\kappa I)g = h ( L − κ I ) g = h after rescaling, whereas
0 < ⟨ ℓ , h ⟩ = ⟨ ℓ , ( L − κ I ) g ⟩ = 0. 0 < \langle\ell,h\rangle= \langle\ell,(\mathcal{L}-\kappa I)g\rangle= 0. 0 < ⟨ ℓ , h ⟩ = ⟨ ℓ , ( L − κ I ) g ⟩ = 0.
Hence κ \kappa κ is algebraically simple.
Proof of (3). Suppose λ ∈ σ ( L ) \lambda\in\sigma(\mathcal{L}) λ ∈ σ ( L ) and ∣ λ ∣ = κ |\lambda| = \kappa ∣ λ ∣ = κ . Since κ > d c δ \kappa> \sqrt{d}\,c_{\delta} κ > d c δ , λ \lambda λ is an eigenvalue; choose f ≠ 0 f \ne0 f = 0 with L f = λ f \mathcal{L}f = \lambda f L f = λ f . Then
( L − κ I ) ∣ f ∣ ≥ 0 , ⟨ ℓ , ( L − κ I ) ∣ f ∣ ⟩ = 0. (\mathcal{L}-\kappa I)|f| \geq0,\qquad\langle\ell,(\mathcal{L}-\kappa I)|f|\rangle= 0. ( L − κ I ) ∣ f ∣ ≥ 0 , ⟨ ℓ , ( L − κ I ) ∣ f ∣ ⟩ = 0.
Since ℓ > 0 \ell> 0 ℓ > 0 almost surely, ( L − κ I ) ∣ f ∣ = 0 (\mathcal{L}-\kappa I)|f| = 0 ( L − κ I ) ∣ f ∣ = 0 , and (2) means we can rescale f f f so that ∣ f ∣ = h |f| = h ∣ f ∣ = h . Write f = h ∘ ζ f = h \circ\zeta f = h ∘ ζ , where ∘ \circ ∘ is the entrywise product and ∣ ζ ∣ = 1 |\zeta| = 1 ∣ ζ ∣ = 1 on infinite trees. Now using the fact that f f f and h h h are eigenvectors of L \mathcal{L} L , we get that
Γ ( T ) ∣ ∑ j = 1 K ( T ) h ( T j ) ζ ( T j ) ∣ = κ h ( T ) = Γ ( T ) ∑ j = 1 K ( T ) h ( T j ) . \Gamma(T)\left|\sum_{j=1}^{K(T)}h(T_j)\zeta(T_j)\right| = \kappa h(T) = \Gamma(T)\sum_{j=1}^{K(T)}h(T_j). Γ ( T ) j = 1 ∑ K ( T ) h ( T j ) ζ ( T j ) = κh ( T ) = Γ ( T ) j = 1 ∑ K ( T ) h ( T j ) .
Whenever K ( T ) = 2 K(T) = 2 K ( T ) = 2 where the two child trees are infinite, their phases therefore agree almost surely. These phases are independent with the same law, so that law is a point mass. Thus f f f is a multiple of h h h , and λ = κ \lambda= \kappa λ = κ .
Proof of (4). By (2), the spectral projection at κ \kappa κ is
P : = ( ℓ ∗ h ) − 1 h ℓ ∗ . P := (\ell^{*}h)^{-1}h\ell^{*}. P := ( ℓ ∗ h ) − 1 h ℓ ∗ .
The spectral decomposition in (1) and (3) implies that the remaining spectrum lies in a strictly smaller disk. Thus, the spectral radius of ( L − κ P ) (\mathcal{L}-\kappa P) ( L − κ P ) is strictly less than κ \kappa κ . Also, P ( L − κ P ) = ( L − κ P ) P = 0 P(\mathcal{L}-\kappa P) = (\mathcal{L}-\kappa P)P = 0 P ( L − κ P ) = ( L − κ P ) P = 0 , and
κ − m L m − P = κ − m ( L − κ P ) m ( m ≥ 1 ) . \kappa^{-m}\mathcal{L}^{m}-P = \kappa^{-m}(\mathcal{L}-\kappa P)^{m}\qquad(m \geq1). κ − m L m − P = κ − m ( L − κ P ) m ( m ≥ 1 ) .
The spectral radius formula therefore gives, for some C < ∞ C < \infty C < ∞ and 0 < θ < 1 0 < \theta< 1 0 < θ < 1 ,
∥ κ − m L m − P ∥ ≤ C θ m . \left\|\kappa^{-m}\mathcal{L}^{m}-P\right\| \leq C\theta^{m}. κ − m L m − P ≤ C θ m .
We can normalize so that P 1 = h P\mathbf{1} = h P 1 = h , proving the asserted convergence.
Injectivity of the largest eigenvalue
Recall that κ : = κ ( δ ) \kappa:= \kappa(\delta) κ := κ ( δ ) is always associated with δ , t \delta,t δ , t . Throughout t t t is fixed. In this section we let δ \delta δ vary. We now have the following.
Proposition 4.9. κ ( δ ) \kappa(\delta) κ ( δ ) is continuous at all δ 0 \delta_0 δ 0 with κ ( δ 0 ) > d c δ 0 \kappa(\delta_0) > \sqrt{d}c_{\delta_0} κ ( δ 0 ) > d c δ 0 . For every t < μ ≤ d t < \mu\le d t < μ ≤ d , there is a unique δ = δ ( μ ) > 0 \delta= \delta(\mu) > 0 δ = δ ( μ ) > 0 such that κ ( δ ) = d / μ \kappa(\delta) = d/\mu κ ( δ ) = d / μ . The function δ ( μ ) \delta(\mu) δ ( μ ) is strictly increasing.
Proof. We extend Γ δ \Gamma_\delta Γ δ to δ = 0 \delta= 0 δ = 0 by setting Γ 0 = 1 / t \Gamma_0 = 1/t Γ 0 = 1/ t .
Continuity. The rank-one decomposition
L δ f = L ^ δ f + ( E f ) L δ 1 \mathcal{L}_\delta f = \widehat{\mathcal{L}}_\delta f + (\mathbb{E}f)\mathcal{L}_\delta1 L δ f = L δ f + ( E f ) L δ 1
gives, for ∣ z ∣ > ∥ L ^ δ ∥ |z| > \|\widehat{\mathcal{L}}_\delta\| ∣ z ∣ > ∥ L δ ∥ ,
z ∈ σ ( L δ ) ⟺ E [ ( z − L ^ δ ) − 1 L δ 1 ] = 1. z \in\sigma(\mathcal{L}_\delta) \Longleftrightarrow\mathbb{E}\left[(z-\widehat{\mathcal{L}}_\delta)^{-1}\mathcal{L}_\delta1\right] = 1. z ∈ σ ( L δ ) ⟺ E [ ( z − L δ ) − 1 L δ 1 ] = 1.
Dominated convergence gives
L δ 1 ⟶ L δ 0 1 in L 2 , L ^ δ ⟶ L ^ δ 0 strongly . \mathcal{L}_\delta1 \longrightarrow\mathcal{L}_{\delta_0}1 \text{ in } L^2,\qquad\widehat{\mathcal{L}}_\delta\longrightarrow\widehat{\mathcal{L}}_{\delta_0}\quad\text{strongly}. L δ 1 ⟶ L δ 0 1 in L 2 , L δ ⟶ L δ 0 strongly .
If for some b > 0 b>0 b > 0 , ∥ L ^ δ ∥ ≤ b \|\widehat{\mathcal{L}}_\delta\| \le b ∥ L δ ∥ ≤ b locally uniformly in δ \delta δ , the Neumann series ( z − L ^ δ ) − 1 = z − 1 + L ^ δ z − 2 + ⋯ (z-\widehat{\mathcal{L}}_\delta)^{-1}=z^{-1}+\widehat{\mathcal{L}}_\delta z^{-2}+\cdots ( z − L δ ) − 1 = z − 1 + L δ z − 2 + ⋯ therefore yields
E [ ( z − L ^ δ ) − 1 L δ 1 ] ⟶ E [ ( z − L ^ δ 0 ) − 1 L δ 0 1 ] \mathbb{E}\left[(z-\widehat{\mathcal{L}}_\delta)^{-1}\mathcal{L}_\delta1\right] \longrightarrow\mathbb{E}\left[(z-\widehat{\mathcal{L}}_{\delta_0})^{-1}\mathcal{L}_{\delta_0}1\right] E [ ( z − L δ ) − 1 L δ 1 ] ⟶ E [ ( z − L δ 0 ) − 1 L δ 0 1 ]
locally uniformly on { ∣ z ∣ > b } \{|z|>b\} { ∣ z ∣ > b } . Rouché's theorem, applied to these expressions minus 1 1 1 , shows that every spectral point of L δ 0 \mathcal{L}_{\delta_0} L δ 0 in this region persists nearby. Conversely, every limit in this region of spectral points of L δ \mathcal{L}_\delta L δ belongs to σ ( L δ 0 ) \sigma(\mathcal{L}_{\delta_0}) σ ( L δ 0 ) . Since the spectra are locally uniformly bounded, it follows that
max { κ ( δ ) , b } ⟶ max { κ ( δ 0 ) , b } . \max\{\kappa(\delta),b\} \longrightarrow\max\{\kappa(\delta_0),b\}. max { κ ( δ ) , b } ⟶ max { κ ( δ 0 ) , b } .
If κ ( δ 0 ) > d c δ 0 \kappa(\delta_0) > \sqrt{d}c_{\delta_0} κ ( δ 0 ) > d c δ 0 , continuity of c δ c_\delta c δ allows us to choose b b b such that, locally,
d c δ < b < κ ( δ 0 ) . \sqrt{d}c_\delta< b < \kappa(\delta_0). d c δ < b < κ ( δ 0 ) .
This proves continuity of κ \kappa κ at δ 0 \delta_0 δ 0 .
Endpoint limits. At δ = 0 \delta=0 δ = 0 ,
( L 0 f ) ( T ) = 1 t ∑ j = 1 K f ( T j ) , E [ L 0 f ] = d t E f . (\mathcal{L}_0f)(T)=\frac{1}{t}\sum_{j=1}^{K}f(T_j),\qquad\mathbb{E}[\mathcal{L}_0f]=\frac{d}{t}\mathbb{E}f. ( L 0 f ) ( T ) = t 1 j = 1 ∑ K f ( T j ) , E [ L 0 f ] = t d E f .
Thus E [ L ^ 0 f ] = 0 \mathbb{E}[\widehat{\mathcal{L}}_0f]=0 E [ L 0 f ] = 0 , and the Neumann series gives
E [ ( z − L ^ 0 ) − 1 L 0 1 ] = d t z , ∣ z ∣ > d t . \mathbb{E}\left[(z-\widehat{\mathcal{L}}_0)^{-1}\mathcal{L}_01\right]=\frac{d}{tz},\qquad|z|>\frac{\sqrt{d}}{t}. E [ ( z − L 0 ) − 1 L 0 1 ] = t z d , ∣ z ∣ > t d .
The spectral criterion above therefore shows that d / t d/t d / t is the only spectral point outside this disk. Hence κ ( 0 ) = d / t \kappa(0)=d/t κ ( 0 ) = d / t , and continuity at zero gives
lim δ ↓ 0 κ ( δ ) = d t . \lim_{\delta\downarrow0}\kappa(\delta)=\frac{d}{t}. δ ↓ 0 lim κ ( δ ) = t d .
At the other endpoint,
κ ( δ ) ≤ ∥ L δ ∥ ≤ c δ d + d 2 ⟶ 0 as δ → ∞ . \kappa(\delta)\le\|\mathcal{L}_\delta\|\le c_\delta\sqrt{d+d^2}\longrightarrow0\qquad\text{as }\delta\to\infty. κ ( δ ) ≤ ∥ L δ ∥ ≤ c δ d + d 2 ⟶ 0 as δ → ∞.
Existence and uniqueness. Positivity and the pointwise decrease of Γ δ \Gamma_\delta Γ δ give L δ 2 ≤ L δ 1 \mathcal{L}_{\delta_2} \le\mathcal{L}_{\delta_1} L δ 2 ≤ L δ 1 whenever δ 1 < δ 2 \delta_1 < \delta_2 δ 1 < δ 2 , so κ \kappa κ is nonincreasing.
Fix y ∈ [ 1 , d / t ) y \in[1,d/t) y ∈ [ 1 , d / t ) . By the limit at zero, choose η > 0 \eta> 0 η > 0 such that κ ( η ) > y \kappa(\eta) > y κ ( η ) > y . For every δ ≥ η \delta\ge\eta δ ≥ η ,
∥ L ~ δ ∥ ≤ b : = d c η < 1. \|\widetilde{\mathcal{L}}_\delta\| \le b := \sqrt{d}\,c_\eta< 1. ∥ L δ ∥ ≤ b := d c η < 1.
Thus max { κ ( δ ) , b } \max\{\kappa(\delta),b\} max { κ ( δ ) , b } is continuous on [ η , ∞ ) [\eta,\infty) [ η , ∞ ) , starts above y y y , and converges to b < y b < y b < y . It follows that κ \kappa κ attains every value in [ 1 , d / t ) [1,d/t) [ 1 , d / t ) at a positive parameter.
To prove uniqueness, suppose δ 1 < δ 2 \delta_1 < \delta_2 δ 1 < δ 2 and κ ( δ 1 ) , κ ( δ 2 ) ≥ 1 \kappa(\delta_1),\kappa(\delta_2) \ge1 κ ( δ 1 ) , κ ( δ 2 ) ≥ 1 . Both parameters satisfy the conditions of Theorem 4.8, so we take the corresponding left eigenfunction ℓ δ 1 \ell_{\delta_1} ℓ δ 1 and right eigenfunction h δ 2 h_{\delta_2} h δ 2 . Consequently,
( κ ( δ 1 ) − κ ( δ 2 ) ) ⟨ ℓ δ 1 , h δ 2 ⟩ = ⟨ ℓ δ 1 , ( L δ 1 − L δ 2 ) h δ 2 ⟩ > 0 , \bigl(\kappa(\delta_1)-\kappa(\delta_2)\bigr)\langle\ell_{\delta_1},h_{\delta_2}\rangle
= \langle\ell_{\delta_1},(\mathcal{L}_{\delta_1}-\mathcal{L}_{\delta_2})h_{\delta_2}\rangle> 0, ( κ ( δ 1 ) − κ ( δ 2 ) ) ⟨ ℓ δ 1 , h δ 2 ⟩ = ⟨ ℓ δ 1 , ( L δ 1 − L δ 2 ) h δ 2 ⟩ > 0 ,
because Γ δ 1 > Γ δ 2 \Gamma_{\delta_1} > \Gamma_{\delta_2} Γ δ 1 > Γ δ 2 and h δ 2 > 0 h_{\delta_2} > 0 h δ 2 > 0 on infinite trees. Thus κ \kappa κ is strictly decreasing wherever κ ≥ 1 \kappa\ge1 κ ≥ 1 .
For t < μ ≤ d t < \mu\le d t < μ ≤ d , we have d / μ ∈ [ 1 , d / t ) d/\mu\in[1,d/t) d / μ ∈ [ 1 , d / t ) , so there is a unique δ ( μ ) > 0 \delta(\mu) > 0 δ ( μ ) > 0 satisfying κ ( δ ( μ ) ) = d / μ \kappa(\delta(\mu)) = d/\mu κ ( δ ( μ )) = d / μ . Since d / μ d/\mu d / μ strictly decreases with μ \mu μ , δ ( μ ) \delta(\mu) δ ( μ ) strictly increases.
Boundary messages
Given the weights and the spectral properties of the transfer operator, we now want to consider the messages given by the tree with these weights. In the following two sections, let μ i > t \mu_i > t μ i > t be any eigenvalue of Q Q Q with eigenvector φ i \varphi_i φ i . Let ρ = ρ i : = μ i / d \rho= \rho_i := \mu_i/d ρ = ρ i := μ i / d , δ = δ i : = δ ( μ i ) > 0 \delta= \delta_i := \delta(\mu_i) > 0 δ = δ i := δ ( μ i ) > 0 .
Let G G G be a graph with vertex labeling σ : V ( G ) → [ r ] \sigma: V(G) \to[r] σ : V ( G ) → [ r ] . Define X = X i : V ( G ) → R X = X_i : V(G) \to\mathbb{R} X = X i : V ( G ) → R by ( X i ) v = φ i ( σ ( v ) ) (X_i)_v = \varphi_i(\sigma(v)) ( X i ) v = φ i ( σ ( v )) .
Observe that, if σ ( v ) ∼ π \sigma(v) \sim\pi σ ( v ) ∼ π , then we have
E [ ( X i ) v ( X j ) v ] = ∑ a = 1 r π a φ i ( a ) φ j ( a ) = 1 { i = j } . (9) \mathbb{E}[(X_i)_v(X_j)_v] = \sum_{a=1}^{r}\pi_a\varphi_i(a)\varphi_j(a) = \mathbf{1}_{\{i=j\}}. \tag*{(9)} E [( X i ) v ( X j ) v ] = a = 1 ∑ r π a φ i ( a ) φ j ( a ) = 1 { i = j } . (9)
We introduce the labelled analogues of Ω \Omega Ω and ν \nu ν defined in the previous section.
Definition 5.1. Let Ω ~ \widetilde{\Omega} Ω denote the collection of all vertex-labeled rooted trees with root o o o , with labels in [ r ] [r] [ r ] . Let ν ~ \widetilde{\nu} ν be the law on Ω ~ \widetilde{\Omega} Ω of a multi-type Galton–Watson tree, where the root o o o has type σ ( o ) ∼ π \sigma(o) \sim\pi σ ( o ) ∼ π , and each vertex of type i i i independently has Poi ( Π i j π j ) \operatorname{Poi}(\Pi_{ij}\pi_j) Poi ( Π ij π j ) children of type j j j for every j ∈ [ r ] j \in[r] j ∈ [ r ] .
Observe that, for any T ∼ ν ~ T \sim\widetilde{\nu} T ∼ ν , the underlying graph T 0 T_0 T 0 is distributed as ν \nu ν .
We now define the boundary weights associated with the eigenvector. To do this, we will do the usual Green’s function decomposition into a product of cavity roots (e.g. [5 Proposition 3.1] ). We also use ( Γ u ( v ) ) ( M ) (\Gamma_u^{(v)})^{(M)} ( Γ u ( v ) ) ( M ) and Γ u ( v ) \Gamma_u^{(v)} Γ u ( v ) defined in Definitions 3.1 and 3.3 .
Definition 5.2. For every ( u , v ) ∈ E (u,v) \in E ( u , v ) ∈ E and M , L ≥ 0 M,L \ge0 M , L ≥ 0 , define b u → v ( L , M ) b_{u\to v}^{(L,M)} b u → v ( L , M ) and b u → v ( L ) b_{u\to v}^{(L)} b u → v ( L ) by
b u → v ( 0 , M ) : = X u , b u → v ( L + 1 , M ) : = ( Γ u ( v ) ) ( M ) ∑ w ∼ u w ≠ v b w → u ( L , M ) ; b_{u\to v}^{(0,M)} := X_u,\qquad b_{u\to v}^{(L+1,M)} := \bigl(\Gamma_u^{(v)}\bigr)^{(M)} \sum_{\substack{w\sim u\\w\ne v}} b_{w\to u}^{(L,M)}; b u → v ( 0 , M ) := X u , b u → v ( L + 1 , M ) := ( Γ u ( v ) ) ( M ) w ∼ u w = v ∑ b w → u ( L , M ) ; b u → v ( 0 ) : = X u , b u → v ( L + 1 ) : = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u ( L ) . b_{u\to v}^{(0)} := X_u,\qquad b_{u\to v}^{(L+1)} := \Gamma_u^{(v)} \sum_{\substack{w\sim u\\w\ne v}} b_{w\to u}^{(L)}. b u → v ( 0 ) := X u , b u → v ( L + 1 ) := Γ u ( v ) w ∼ u w = v ∑ b w → u ( L ) .
When G G G is a rooted tree, we use b u ( L , M ) b_u^{(L,M)} b u ( L , M ) to denote b u → p ( u ) ( L , M ) b_{u\to p(u)}^{(L,M)} b u → p ( u ) ( L , M ) and use b u ( L ) b_u^{(L)} b u ( L ) to denote b u → p ( u ) ( L ) b_{u\to p(u)}^{(L)} b u → p ( u ) ( L ) .
Proposition 5.3. Suppose G ∼ ν ~ G \sim\widetilde{\nu} G ∼ ν is the multitype Galton–Watson tree. There is an L 2 L^2 L 2 function b u : Ω ~ → R b_u:\widetilde{\Omega}\to\mathbb{R} b u : Ω → R such that
lim L → ∞ b u ( L ) = b u , b u = Γ u ∑ w ∈ ch ( u ) b w . (10) \lim_{L\to\infty} b_u^{(L)}=b_u,\qquad b_u=\Gamma_u\sum_{w\in\operatorname{ch}(u)}b_w. \tag*{(10)} L → ∞ lim b u ( L ) = b u , b u = Γ u w ∈ ch ( u ) ∑ b w . (10)
Proof. Fix ρ : = ρ i = μ i / d \rho:=\rho_i=\mu_i/d ρ := ρ i = μ i / d . Set h L = ρ L L 1 h_L=\rho^L\mathcal{L}_1 h L = ρ L L 1 . Suppose x x x is a descendant of u u u with ∣ x ∣ : = dist ( x , u ) = L |x|:=\operatorname{dist}(x,u)=L ∣ x ∣ := dist ( x , u ) = L . Let u = x 0 , x 1 , … , x L = x u=x_0,x_1,\ldots,x_L=x u = x 0 , x 1 , … , x L = x denote the path from u u u to x x x . We then have
h L ( T ) = ρ L ∑ x : ∣ x ∣ = L ∏ j = 0 L − 1 Γ x j . h_L(T)=\rho^L\sum_{x:|x|=L}\prod_{j=0}^{L-1}\Gamma_{x_j}. h L ( T ) = ρ L x : ∣ x ∣ = L ∑ j = 0 ∏ L − 1 Γ x j .
Write P u ( x ) : = ∏ j = 0 L − 1 Γ x j P_u(x):=\prod_{j=0}^{L-1}\Gamma_{x_j} P u ( x ) := ∏ j = 0 L − 1 Γ x j . Then we have
b u ( L ) = ∑ ∣ x ∣ = L P u ( x ) X x . b_u^{(L)}=\sum_{|x|=L}P_u(x)X_x. b u ( L ) = ∣ x ∣ = L ∑ P u ( x ) X x .
Let T 0 T_0 T 0 denote the underlying unlabelled tree of T T T . Recall that E [ X x ∣ T 0 , σ ( u ) ] = ρ L X u \mathbb{E}[X_x\mid T_0,\sigma(u)]=\rho^L X_u E [ X x ∣ T 0 , σ ( u )] = ρ L X u . Thus,
E [ b u ( L ) ∣ T 0 , σ ( u ) ] = ρ L ∑ ∣ x ∣ = L P u ( x ) X u = h L ( T ) X u . \mathbb{E}\left[b_u^{(L)}\mid T_0,\sigma(u)\right]=\rho^L\sum_{|x|=L}P_u(x)X_u=h_L(T)X_u. E [ b u ( L ) ∣ T 0 , σ ( u ) ] = ρ L ∣ x ∣ = L ∑ P u ( x ) X u = h L ( T ) X u .
We now want to decompose b u ( L ) b_u^{(L)} b u ( L ) into an orthogonal family, as was done in [12 ] . For every descendant x x x of u u u , define ξ x : = ρ − 1 X x − X p ( x ) \xi_x:=\rho^{-1}X_x-X_{p(x)} ξ x := ρ − 1 X x − X p ( x ) , so that X x = ρ X p ( x ) + ρ ξ x X_x=\rho X_{p(x)}+\rho\xi_x X x = ρ X p ( x ) + ρ ξ x . Since E ( ξ x ∣ T 0 , labels above x ) = 0 \mathbb{E}(\xi_x\mid T_0,\text{ labels above }x)=0 E ( ξ x ∣ T 0 , labels above x ) = 0 ,
E ( X u ξ x ∣ T 0 ) = 0 , E ( ξ x ξ y ∣ T 0 ) = 0 for x ≠ y . (11) \mathbb{E}(X_u\xi_x\mid T_0)=0,\qquad\mathbb{E}(\xi_x\xi_y\mid T_0)=0\text{ for }x\ne y. \tag*{(11)} E ( X u ξ x ∣ T 0 ) = 0 , E ( ξ x ξ y ∣ T 0 ) = 0 for x = y . (11)
Meanwhile, we have E ( X u 2 ∣ T 0 ) = 1 \mathbb{E}(X_u^2\mid T_0)=1 E ( X u 2 ∣ T 0 ) = 1 and E ( ξ x 2 ∣ T 0 ) = ρ − 2 ⋅ 1 − 2 ρ − 1 ⋅ ρ + 1 = ρ − 2 − 1 \mathbb{E}(\xi_x^2\mid T_0)=\rho^{-2}\cdot1-2\rho^{-1}\cdot\rho+1=\rho^{-2}-1 E ( ξ x 2 ∣ T 0 ) = ρ − 2 ⋅ 1 − 2 ρ − 1 ⋅ ρ + 1 = ρ − 2 − 1 . Next, observe that for every path u = x 0 , x 1 , … , x L = x u=x_0,x_1,\ldots,x_L=x u = x 0 , x 1 , … , x L = x , we have
X x = ρ L X u + ∑ ℓ = 1 L ρ L − ℓ + 1 ξ x ℓ . X_x=\rho^L X_u+\sum_{\ell=1}^{L}\rho^{L-\ell+1}\xi_{x_\ell}. X x = ρ L X u + ℓ = 1 ∑ L ρ L − ℓ + 1 ξ x ℓ .
We can then decompose b u ( L ) b_u^{(L)} b u ( L ) into this basis as
b u ( L ) = ∑ ∣ x ∣ = L P u ( x ) ( ρ L X u + ∑ ℓ = 1 L ρ L − ℓ + 1 ξ x ℓ ) = ρ L ∑ ∣ x ∣ = L P u ( x ) X u + ∑ ℓ = 1 L ∑ ∣ y ∣ = ℓ ρ L − ℓ + 1 ξ y P u ( y ) ∑ ∣ x ∣ = L , y ⪯ x P y ( x ) = h L ( T ) X u + ∑ ℓ = 1 L ∑ ∣ y ∣ = ℓ ρ h L − ℓ ( T y ) P u ( y ) ξ y , \begin{aligned}
b_u^{(L)}
&=\sum_{|x|=L}P_u(x)\left(\rho^L X_u+\sum_{\ell=1}^{L}\rho^{L-\ell+1}\xi_{x_\ell}\right)\\
&=\rho^L\sum_{|x|=L}P_u(x)X_u+\sum_{\ell=1}^{L}\sum_{|y|=\ell}\rho^{L-\ell+1}\xi_yP_u(y)\sum_{\substack{|x|=L,y\preceq x}}P_y(x)\\
&=h_L(T)X_u+\sum_{\ell=1}^{L}\sum_{|y|=\ell}\rho h_{L-\ell}(T_y)P_u(y)\xi_y,
\end{aligned} b u ( L ) = ∣ x ∣ = L ∑ P u ( x ) ( ρ L X u + ℓ = 1 ∑ L ρ L − ℓ + 1 ξ x ℓ ) = ρ L ∣ x ∣ = L ∑ P u ( x ) X u + ℓ = 1 ∑ L ∣ y ∣ = ℓ ∑ ρ L − ℓ + 1 ξ y P u ( y ) ∣ x ∣ = L , y ⪯ x ∑ P y ( x ) = h L ( T ) X u + ℓ = 1 ∑ L ∣ y ∣ = ℓ ∑ ρ h L − ℓ ( T y ) P u ( y ) ξ y ,
where T y T_y T y is the subtree of T T T rooted at y y y , and y ⪯ x y\preceq x y ⪯ x denotes that y y y is an ancestor of x x x . We now define
b u ( T ) : = h ( T ) X u + ∑ ℓ = 1 ∞ ∑ ∣ y ∣ = ℓ ρ h ( T y ) P u ( y ) ξ y . b_u(T):=h(T)X_u+\sum_{\ell=1}^{\infty}\sum_{|y|=\ell}\rho h(T_y)P_u(y)\xi_y. b u ( T ) := h ( T ) X u + ℓ = 1 ∑ ∞ ∣ y ∣ = ℓ ∑ ρ h ( T y ) P u ( y ) ξ y .
We first show that b u ∈ L 2 ( Ω ~ ) b_u \in L^2(\widetilde{\Omega}) b u ∈ L 2 ( Ω ) . For every ℓ \ell ℓ , let
Y ℓ : = ∑ ∣ y ∣ = ℓ ρ h ( T y ) P u ( y ) ξ y . Y_\ell:= \sum_{|y|=\ell} \rho h(T_y)P_u(y)\xi_y. Y ℓ := ∣ y ∣ = ℓ ∑ ρ h ( T y ) P u ( y ) ξ y .
We know from orthogonality (11) that
E ( Y ℓ 2 ∣ T 0 ) = ρ 2 ∑ ∣ y ∣ = ℓ h ( T y ) 2 P u ( y ) 2 E ( ξ y 2 ∣ T 0 ) = ( 1 − ρ 2 ) ∑ ∣ y ∣ = ℓ h ( T y ) 2 P u ( y ) 2 . \mathbb{E}(Y_\ell^2 \mid T_0) = \rho^2 \sum_{|y|=\ell} h(T_y)^2P_u(y)^2\mathbb{E}(\xi_y^2 \mid T_0) = (1-\rho^2)\sum_{|y|=\ell} h(T_y)^2P_u(y)^2. E ( Y ℓ 2 ∣ T 0 ) = ρ 2 ∣ y ∣ = ℓ ∑ h ( T y ) 2 P u ( y ) 2 E ( ξ y 2 ∣ T 0 ) = ( 1 − ρ 2 ) ∣ y ∣ = ℓ ∑ h ( T y ) 2 P u ( y ) 2 .
Therefore,
E ( Y ℓ 2 ) ≤ ( 1 − ρ 2 ) c δ 2 ℓ E ∑ ∣ y ∣ = ℓ h ( T y ) 2 ≤ ( 1 − ρ 2 ) c δ 2 ℓ d ℓ ∥ h ∥ 2 2 . \mathbb{E}(Y_\ell^2) \le(1-\rho^2)c_\delta^{2\ell}\mathbb{E}\sum_{|y|=\ell} h(T_y)^2 \le(1-\rho^2)c_\delta^{2\ell}d^\ell\|h\|_2^2. E ( Y ℓ 2 ) ≤ ( 1 − ρ 2 ) c δ 2 ℓ E ∣ y ∣ = ℓ ∑ h ( T y ) 2 ≤ ( 1 − ρ 2 ) c δ 2 ℓ d ℓ ∥ h ∥ 2 2 .
Since the Y ℓ Y_\ell Y ℓ ’s are pairwise orthogonal in expectation, it follows that
E ∣ b u ∣ 2 ≤ ∥ h ∥ 2 2 ( 1 + ( 1 − ρ 2 ) ∑ ℓ = 1 ∞ c δ 2 ℓ d ℓ ) < ∞ . \mathbb{E}|b_u|^2 \le\|h\|_2^2\left(1+(1-\rho^2)\sum_{\ell=1}^{\infty}c_\delta^{2\ell}d^\ell\right)<\infty. E ∣ b u ∣ 2 ≤ ∥ h ∥ 2 2 ( 1 + ( 1 − ρ 2 ) ℓ = 1 ∑ ∞ c δ 2 ℓ d ℓ ) < ∞.
Next, we show that b ( L ) → b b^{(L)}\to b b ( L ) → b in L 2 L^2 L 2 . Indeed, we have
b ( L ) ( T ) − b ( T ) = ( h L ( T ) − h ( T ) ) X u + ∑ ℓ = 1 L ∑ ∣ y ∣ = ℓ ρ ( h L − ℓ ( T y ) − h ( T y ) ) P u ( y ) ξ y b^{(L)}(T)-b(T)=(h_L(T)-h(T))X_u+\sum_{\ell=1}^{L}\sum_{|y|=\ell}\rho(h_{L-\ell}(T_y)-h(T_y))P_u(y)\xi_y b ( L ) ( T ) − b ( T ) = ( h L ( T ) − h ( T )) X u + ℓ = 1 ∑ L ∣ y ∣ = ℓ ∑ ρ ( h L − ℓ ( T y ) − h ( T y )) P u ( y ) ξ y
− ∑ ℓ = L + 1 ∞ ∑ ∣ y ∣ = ℓ ρ h ( T y ) P u ( y ) ξ y . \qquad-\sum_{\ell=L+1}^{\infty}\sum_{|y|=\ell}\rho h(T_y)P_u(y)\xi_y. − ℓ = L + 1 ∑ ∞ ∣ y ∣ = ℓ ∑ ρ h ( T y ) P u ( y ) ξ y .
Using orthogonality of ξ y \xi_y ξ y , we get that
E ∣ b ( L ) − b ∣ 2 ≤ ∥ h L − h ∥ 2 2 + ( 1 − ρ 2 ) ∑ ℓ = 1 L c δ 2 ℓ d ℓ ∥ h L − ℓ − h ∥ 2 2 + ( 1 − ρ 2 ) ∑ ℓ = L + 1 ∞ c δ 2 ℓ d ℓ ∥ h ∥ 2 2 → 0 \mathbb{E}|b^{(L)}-b|^2\le\|h_L-h\|_2^2+(1-\rho^2)\sum_{\ell=1}^{L}c_\delta^{2\ell}d^\ell\|h_{L-\ell}-h\|_2^2+(1-\rho^2)\sum_{\ell=L+1}^{\infty}c_\delta^{2\ell}d^\ell\|h\|_2^2\to0 E ∣ b ( L ) − b ∣ 2 ≤ ∥ h L − h ∥ 2 2 + ( 1 − ρ 2 ) ℓ = 1 ∑ L c δ 2 ℓ d ℓ ∥ h L − ℓ − h ∥ 2 2 + ( 1 − ρ 2 ) ℓ = L + 1 ∑ ∞ c δ 2 ℓ d ℓ ∥ h ∥ 2 2 → 0
as L → ∞ L\to\infty L → ∞ .
We are left to show that b b b satisfies the desired recursion. Let K = ∣ ch ( u ) ∣ K=|\operatorname{ch}(u)| K = ∣ ch ( u ) ∣ . Indeed, since
b u ( L + 1 ) = Γ u ∑ w ∈ ch ( u ) b w ( L ) , b_u^{(L+1)}=\Gamma_u\sum_{w\in\operatorname{ch}(u)}b_w^{(L)}, b u ( L + 1 ) = Γ u w ∈ ch ( u ) ∑ b w ( L ) ,
E ∣ b u − b u ( L + 1 ) ∣ 2 → 0 , \mathbb{E}|b_u-b_u^{(L+1)}|^2\to0, E ∣ b u − b u ( L + 1 ) ∣ 2 → 0 ,
E ∣ Γ u ∑ w ∈ ch ( u ) ( b w ( L ) − b w ) ∣ 2 ≤ c δ 2 E ( K 2 ) E ∣ b w ( L ) − b w ∣ 2 → 0 , \mathbb{E}\left|\Gamma_u\sum_{w\in\operatorname{ch}(u)}(b_w^{(L)}-b_w)\right|^2\le c_\delta^2\mathbb{E}(K^2)\mathbb{E}|b_w^{(L)}-b_w|^2\to0, E Γ u w ∈ ch ( u ) ∑ ( b w ( L ) − b w ) 2 ≤ c δ 2 E ( K 2 ) E ∣ b w ( L ) − b w ∣ 2 → 0 ,
we know that b u = Γ u ∑ w ∈ ch ( u ) b w b_u=\Gamma_u\sum_{w\in\operatorname{ch}(u)}b_w b u = Γ u ∑ w ∈ ch ( u ) b w almost surely.
We extend the definitions of b u = b u → p ( u ) b_u=b_{u\to p(u)} b u = b u → p ( u ) to b u → v b_{u\to v} b u → v for all u ∼ v u\sim v u ∼ v in T T T .
Definition 5.4. For u ∼ v u\sim v u ∼ v in T T T , define b u → v b_{u\to v} b u → v by
b u → v = { b u v = p ( u ) , Γ o ( v ) ∑ w ∈ ch ( o ) w ≠ v b w → o u = o , o = p ( v ) , Γ u ( v ) ( b p ( u ) → u + ∑ w ∈ ch ( u ) w ≠ v b w → u ) u ≠ o , u = p ( v ) . b_{u\to v}=
\begin{cases}
b_u & v=p(u),\\
\Gamma_o^{(v)}\sum_{\substack{w\in\operatorname{ch}(o)\\w\ne v}}b_{w\to o} & u=o,\ o=p(v),\\
\Gamma_u^{(v)}\left(b_{p(u)\to u}+\sum_{\substack{w\in\operatorname{ch}(u)\\w\ne v}}b_{w\to u}\right) & u\ne o,\ u=p(v).
\end{cases} b u → v = ⎩ ⎨ ⎧ b u Γ o ( v ) ∑ w ∈ ch ( o ) w = v b w → o Γ u ( v ) ( b p ( u ) → u + ∑ w ∈ ch ( u ) w = v b w → u ) v = p ( u ) , u = o , o = p ( v ) , u = o , u = p ( v ) .
It is straightforward to check that, for every directed edge ( u , v ) (u,v) ( u , v ) , we have
b u → v = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u . b_{u\to v}=\Gamma_u^{(v)}\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}. b u → v = Γ u ( v ) w ∼ u w = v ∑ b w → u .
Moreover, for all sufficiently large L L L , each b u → v b_{u\to v} b u → v can be expressed as a finite linear combination of the messages ( b w → p ( w ) ) w ∈ T ∖ { o } (b_{w\to p(w)})_{w\in T\setminus\{o\}} ( b w → p ( w ) ) w ∈ T ∖ { o } in the same way that b u → v ( L ) b_{u\to v}^{(L)} b u → v ( L ) can be expressed in terms of ( b w → p ( w ) ( L − k ) ) w ∈ T ∖ { o } (b_{w\to p(w)}^{(L-k)})_{w\in T\setminus\{o\}} ( b w → p ( w ) ( L − k ) ) w ∈ T ∖ { o } , with k k k independent of L L L . Thus, we can deduce the following from Proposition 5.3.
Corollary 5.5. Suppose G G G is a rooted multitype Galton–Watson tree. There exist random variables ( b u → v ) ( u , v ) ∈ E (b_{u\to v})_{(u,v)\in E} ( b u → v ) ( u , v ) ∈ E such that, for every ( u , v ) (u,v) ( u , v ) ,
b u → v = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u . b_{u\to v}=\Gamma_u^{(v)}\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}. b u → v = Γ u ( v ) w ∼ u w = v ∑ b w → u . Moreover, b u → v ( L ) ⟶ b u → v b_{u\to v}^{(L)}\longrightarrow b_{u\to v} b u → v ( L ) ⟶ b u → v in L 2 L^2 L 2 as L → ∞ L\to\infty L → ∞ .
Vertex fields and their approximations
Given our set of messages b u → v b_{u\to v} b u → v , we can construct the eigenvector on the relevant graphs. We do this first on an arbitrary graph, and then highlight stronger recursive properties on trees.
General graphs
Our test eigenvector is a weighted linear combination of the above messages.
Definition 6.1. Let G G G be any graph with vertex labeling σ : V ( G ) → [ r ] \sigma:V(G)\to[r] σ : V ( G ) → [ r ] . For any u ∈ V ( G ) u\in V(G) u ∈ V ( G ) and L , M ≥ 0 L,M\ge0 L , M ≥ 0 , define
V ( L , M ) ( u ) : = t ∑ v ∼ u b v → u ( L , M ) t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u ( Γ v ( u ) ) ( M ) , V^{(L,M)}(u):=\frac{t\sum_{v\sim u}b_{v\to u}^{(L,M)}}{t^2+\deg(u)-1+\delta-t\sum_{v\sim u}(\Gamma_v^{(u)})^{(M)}}, V ( L , M ) ( u ) := t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u ( Γ v ( u ) ) ( M ) t ∑ v ∼ u b v → u ( L , M ) , V ( L ) ( u ) : = t ∑ v ∼ u b v → u ( L ) t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) . V^{(L)}(u):=\frac{t\sum_{v\sim u}b_{v\to u}^{(L)}}{t^2+\deg(u)-1+\delta-t\sum_{v\sim u}\Gamma_v^{(u)}}. V ( L ) ( u ) := t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) t ∑ v ∼ u b v → u ( L ) . Moreover, define the ball B k ( G , u ) B_k(G,u) B k ( G , u ) to be the subgraph of G G G induced by the set of vertices of distance at most k k k from u ∈ V ( G ) u\in V(G) u ∈ V ( G ) .
It is important to mention here that V ( L , M ) V^{(L,M)} V ( L , M ) can be decided by a finite neighborhood.
Lemma 6.2. Let G G G be any graph with vertex labeling σ : V ( G ) → [ r ] \sigma:V(G)\to[r] σ : V ( G ) → [ r ] . For fixed integers L , M ≥ 0 L,M\ge0 L , M ≥ 0 , the values V ( L , M ) ( u ) V^{(L,M)}(u) V ( L , M ) ( u ) and [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) [(H(t,G)+\delta I)V^{(L,M)}](u) [( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) are determined by the ball B M + L + 2 ( G , u ) B_{M+L+2}(G,u) B M + L + 2 ( G , u ) .
Proof. It is easy to check by induction that every ( Γ u ( v ) ) ( M ) (\Gamma_u^{(v)})^{(M)} ( Γ u ( v ) ) ( M ) is determined by B M ( G , u ) B_M(G,u) B M ( G , u ) . Since
b u → v ( 0 , M ) = X ( u ) , b u → v ( L + 1 , M ) = ( Γ u ( v ) ) ( M ) ∑ w ∼ u w ≠ v b w → u ( L , M ) , b_{u\to v}^{(0,M)}=X(u),\qquad
b_{u\to v}^{(L+1,M)}=(\Gamma_u^{(v)})^{(M)}
\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}^{(L,M)}, b u → v ( 0 , M ) = X ( u ) , b u → v ( L + 1 , M ) = ( Γ u ( v ) ) ( M ) w ∼ u w = v ∑ b w → u ( L , M ) ,
@page 16/28 starts_mid=1 ends_mid=1 It is straightforward to check that, for every directed edge ( u , v ) (u,v) ( u , v ) , we have
b u → v = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u . b_{u\to v}=\Gamma_u^{(v)}\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}. b u → v = Γ u ( v ) w ∼ u w = v ∑ b w → u .
Moreover, for all sufficiently large L L L , each b u → v b_{u\to v} b u → v can be expressed as a finite linear combination of the messages ( b w → p ( w ) ) w ∈ T ∖ { o } (b_{w\to p(w)})_{w\in T\setminus\{o\}} ( b w → p ( w ) ) w ∈ T ∖ { o } in the same way that b u → v ( L ) b_{u\to v}^{(L)} b u → v ( L ) can be expressed in terms of ( b w → p ( w ) ( L − k ) ) w ∈ T ∖ { o } (b_{w\to p(w)}^{(L-k)})_{w\in T\setminus\{o\}} ( b w → p ( w ) ( L − k ) ) w ∈ T ∖ { o } , with k k k independent of L L L . Thus, we can deduce the following from Proposition 5.3.
Corollary 5.5. Suppose G G G is a rooted multitype Galton–Watson tree. There exist random variables ( b u → v ) ( u , v ) ∈ E (b_{u\to v})_{(u,v)\in E} ( b u → v ) ( u , v ) ∈ E such that, for every ( u , v ) (u,v) ( u , v ) ,
b u → v = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u . b_{u\to v}=\Gamma_u^{(v)}\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}. b u → v = Γ u ( v ) w ∼ u w = v ∑ b w → u . Moreover, b u → v ( L ) ⟶ b u → v b_{u\to v}^{(L)}\longrightarrow b_{u\to v} b u → v ( L ) ⟶ b u → v in L 2 L^2 L 2 as L → ∞ L\to\infty L → ∞ .
Vertex fields and their approximations
Given our set of messages b u → v b_{u\to v} b u → v , we can construct the eigenvector on the relevant graphs. We do this first on an arbitrary graph, and then highlight stronger recursive properties on trees.
General graphs
Our test eigenvector is a weighted linear combination of the above messages.
Definition 6.1. Let G G G be any graph with vertex labeling σ : V ( G ) → [ r ] \sigma:V(G)\to[r] σ : V ( G ) → [ r ] . For any u ∈ V ( G ) u\in V(G) u ∈ V ( G ) and L , M ≥ 0 L,M\ge0 L , M ≥ 0 , define
V ( L , M ) ( u ) : = t ∑ v ∼ u b v → u ( L , M ) t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u ( Γ v ( u ) ) ( M ) , V^{(L,M)}(u):=\frac{t\sum_{v\sim u}b_{v\to u}^{(L,M)}}{t^2+\deg(u)-1+\delta-t\sum_{v\sim u}(\Gamma_v^{(u)})^{(M)}}, V ( L , M ) ( u ) := t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u ( Γ v ( u ) ) ( M ) t ∑ v ∼ u b v → u ( L , M ) , V ( L ) ( u ) : = t ∑ v ∼ u b v → u ( L ) t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) . V^{(L)}(u):=\frac{t\sum_{v\sim u}b_{v\to u}^{(L)}}{t^2+\deg(u)-1+\delta-t\sum_{v\sim u}\Gamma_v^{(u)}}. V ( L ) ( u ) := t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) t ∑ v ∼ u b v → u ( L ) . Moreover, define the ball B k ( G , u ) B_k(G,u) B k ( G , u ) to be the subgraph of G G G induced by the set of vertices of distance at most k k k from u ∈ V ( G ) u\in V(G) u ∈ V ( G ) .
It is important to mention here that V ( L , M ) V^{(L,M)} V ( L , M ) can be decided by a finite neighborhood.
Lemma 6.2. Let G G G be any graph with vertex labeling σ : V ( G ) → [ r ] \sigma:V(G)\to[r] σ : V ( G ) → [ r ] . For fixed integers L , M ≥ 0 L,M\ge0 L , M ≥ 0 , the values V ( L , M ) ( u ) V^{(L,M)}(u) V ( L , M ) ( u ) and [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) [(H(t,G)+\delta I)V^{(L,M)}](u) [( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) are determined by the ball B M + L + 2 ( G , u ) B_{M+L+2}(G,u) B M + L + 2 ( G , u ) .
Proof. It is easy to check by induction that every ( Γ u ( v ) ) ( M ) (\Gamma_u^{(v)})^{(M)} ( Γ u ( v ) ) ( M ) is determined by B M ( G , u ) B_M(G,u) B M ( G , u ) . Since
b u → v ( 0 , M ) = X ( u ) , b u → v ( L + 1 , M ) = ( Γ u ( v ) ) ( M ) ∑ w ∼ u w ≠ v b w → u ( L , M ) , b_{u\to v}^{(0,M)}=X(u),\qquad
b_{u\to v}^{(L+1,M)}=(\Gamma_u^{(v)})^{(M)}
\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}^{(L,M)}, b u → v ( 0 , M ) = X ( u ) , b u → v ( L + 1 , M ) = ( Γ u ( v ) ) ( M ) w ∼ u w = v ∑ b w → u ( L , M ) ,
induction on L L L then shows that b u → v ( L , M ) b^{(L,M)}_{u\to v} b u → v ( L , M ) is determined by B L + M ( G , u ) B_{L+M}(G,u) B L + M ( G , u ) . This gives that V ( L , M ) ( u ) V^{(L,M)}(u) V ( L , M ) ( u ) is determined by B L + M + 1 ( G , u ) B_{L+M+1}(G,u) B L + M + 1 ( G , u ) . Therefore,
[ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) = ( t 2 + deg ( u ) − 1 + δ ) V ( L , M ) ( u ) − t ∑ v ∼ u V ( L , M ) ( v ) \left[(H(t,G)+\delta I)V^{(L,M)}\right](u)=\left(t^2+\deg(u)-1+\delta\right)V^{(L,M)}(u)-t\sum_{v\sim u}V^{(L,M)}(v) [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) = ( t 2 + deg ( u ) − 1 + δ ) V ( L , M ) ( u ) − t v ∼ u ∑ V ( L , M ) ( v )
is determined by B L + M + 2 ( G , u ) B_{L+M+2}(G,u) B L + M + 2 ( G , u ) .
At this point, we write c : = c δ c:=c_\delta c := c δ for notational convenience. We now give a generic rough bound on these weights.
Lemma 6.3. Let G G G be any graph with vertex labeling σ : V ( G ) → [ r ] \sigma:V(G)\to[r] σ : V ( G ) → [ r ] . For every L , M ≥ 0 L,M\ge0 L , M ≥ 0 , ∣ b u → v ( L , M ) ∣ ≤ ∥ φ i ∥ ∞ c L ∣ B L ( G , u ) ∣ L \left|b^{(L,M)}_{u\to v}\right|\le\|\varphi_i\|_\infty c^L |B_L(G,u)|^L b u → v ( L , M ) ≤ ∥ φ i ∥ ∞ c L ∣ B L ( G , u ) ∣ L .
Proof. Write β : = ∥ φ i ∥ ∞ \beta:=\|\varphi_i\|_\infty β := ∥ φ i ∥ ∞ . When L = 0 L=0 L = 0 , we indeed have ∣ b u → v ( 0 , M ) ∣ ≤ β \left|b^{(0,M)}_{u\to v}\right|\le\beta b u → v ( 0 , M ) ≤ β . Inductively, we obtain
∣ b u → v ( L + 1 , M ) ∣ ≤ c ∑ w ∼ u w ≠ v β c L ∣ B L ( G , w ) ∣ L ≤ β c L + 1 deg ( u ) ∣ B L + 1 ( G , u ) ∣ L ≤ β c L + 1 ∣ B L + 1 ( G , u ) ∣ L + 1 . \left|b^{(L+1,M)}_{u\to v}\right|\le c\sum_{\substack{w\sim u\\w\ne v}}\beta c^L|B_L(G,w)|^L\le\beta c^{L+1}\deg(u)|B_{L+1}(G,u)|^L\le\beta c^{L+1}|B_{L+1}(G,u)|^{L+1}. b u → v ( L + 1 , M ) ≤ c w ∼ u w = v ∑ β c L ∣ B L ( G , w ) ∣ L ≤ β c L + 1 deg ( u ) ∣ B L + 1 ( G , u ) ∣ L ≤ β c L + 1 ∣ B L + 1 ( G , u ) ∣ L + 1 .
Lemma 6.4. Let G G G be any graph with vertex labeling σ : V ( G ) → [ r ] \sigma:V(G)\to[r] σ : V ( G ) → [ r ] . For each fixed L L L there is C L < ∞ C_L<\infty C L < ∞ , independent of M M M , such that
∣ V ( L , M ) ( u ) ∣ + ∣ [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) ∣ ≤ C L ∣ B L + 2 ( G , u ) ∣ L + 2 . |V^{(L,M)}(u)|+\left|\left[(H(t,G)+\delta I)V^{(L,M)}\right](u)\right|\le C_L|B_{L+2}(G,u)|^{L+2}. ∣ V ( L , M ) ( u ) ∣ + [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) ≤ C L ∣ B L + 2 ( G , u ) ∣ L + 2 . Proof. Let α : = t 2 − 1 + δ \alpha:=t^2-1+\delta α := t 2 − 1 + δ and recall that β = ∥ φ i ∥ ∞ \beta=\|\varphi_i\|_\infty β = ∥ φ i ∥ ∞ . By the previous observation, we have
∣ V ( L , M ) ( u ) ∣ ≤ t ∑ v ∼ u ∣ b v → u ( L , M ) ∣ α ≤ t β α ∑ v ∼ u c L ∣ B L ( G , v ) ∣ L |V^{(L,M)}(u)|\le\frac{t\sum_{v\sim u}|b^{(L,M)}_{v\to u}|}{\alpha}\le\frac{t\beta}{\alpha}\sum_{v\sim u}c^L|B_L(G,v)|^L ∣ V ( L , M ) ( u ) ∣ ≤ α t ∑ v ∼ u ∣ b v → u ( L , M ) ∣ ≤ α tβ v ∼ u ∑ c L ∣ B L ( G , v ) ∣ L ≤ t β c L α deg ( u ) ∣ B L + 1 ( G , u ) ∣ L ≤ t β c L α ∣ B L + 1 ( G , u ) ∣ L + 1 . \le\frac{t\beta c^L}{\alpha}\deg(u)|B_{L+1}(G,u)|^L\le\frac{t\beta c^L}{\alpha}|B_{L+1}(G,u)|^{L+1}. ≤ α tβ c L deg ( u ) ∣ B L + 1 ( G , u ) ∣ L ≤ α tβ c L ∣ B L + 1 ( G , u ) ∣ L + 1 . Using
[ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) = ( α + deg ( u ) ) V ( L , M ) ( u ) − t ∑ v ∼ u V ( L , M ) ( v ) , \left[(H(t,G)+\delta I)V^{(L,M)}\right](u)=(\alpha+\deg(u))V^{(L,M)}(u)-t\sum_{v\sim u}V^{(L,M)}(v), [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) = ( α + deg ( u )) V ( L , M ) ( u ) − t v ∼ u ∑ V ( L , M ) ( v ) , we conclude that
∣ V ( L , M ) ( u ) ∣ + ∣ [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) ∣ ≤ ( 1 + α + deg ( u ) ) ∣ V ( L , M ) ( u ) ∣ + t ∑ v ∼ u ∣ V ( L , M ) ( v ) ∣ |V^{(L,M)}(u)|+\left|\left[(H(t,G)+\delta I)V^{(L,M)}\right](u)\right|\le(1+\alpha+\deg(u))|V^{(L,M)}(u)|+t\sum_{v\sim u}|V^{(L,M)}(v)| ∣ V ( L , M ) ( u ) ∣ + [ ( H ( t , G ) + δ I ) V ( L , M ) ] ( u ) ≤ ( 1 + α + deg ( u )) ∣ V ( L , M ) ( u ) ∣ + t v ∼ u ∑ ∣ V ( L , M ) ( v ) ∣ ≤ t β c L α ( 1 + α + ( 1 + t ) deg ( u ) ) ∣ B L + 2 ( G , u ) ∣ L + 1 \le\frac{t\beta c^L}{\alpha}(1+\alpha+(1+t)\deg(u))|B_{L+2}(G,u)|^{L+1} ≤ α tβ c L ( 1 + α + ( 1 + t ) deg ( u )) ∣ B L + 2 ( G , u ) ∣ L + 1 ≤ t β c L α ( α + 2 + t ) ∣ B L + 2 ( G , u ) ∣ L + 2 . \le\frac{t\beta c^L}{\alpha}(\alpha+2+t)|B_{L+2}(G,u)|^{L+2}. ≤ α tβ c L ( α + 2 + t ) ∣ B L + 2 ( G , u ) ∣ L + 2 .
Trees
We now examine this candidate eigenvector on the infinite tree.
Definition 6.5. On the Galton–Watson tree T T T , recall b v → u b_{v\to u} b v → u defined in Definition 5.4. For every vertex u u u , define the vector V V V such that
V ( u ) ≔ t ∑ v ∼ u b v → u t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) . V(u) \coloneqq\frac{t\sum_{v\sim u} b_{v\to u}}{t^2+\deg(u)-1+\delta-t\sum_{v\sim u}\Gamma_v^{(u)}}. V ( u ) : = t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) t ∑ v ∼ u b v → u .
Lemma 6.6. On the labeled Galton–Watson tree ( T , o ) (T,o) ( T , o ) , we have E ∣ V ( o ) ∣ 2 < ∞ \mathbb{E}|V(o)|^2<\infty E ∣ V ( o ) ∣ 2 < ∞ and
E ∣ V ( L ) ( o ) − V ( o ) ∣ 2 ⟶ 0 as L → ∞ . \mathbb{E}\left|V^{(L)}(o)-V(o)\right|^2 \longrightarrow0 \qquad\text{as } L\to\infty. E V ( L ) ( o ) − V ( o ) 2 ⟶ 0 as L → ∞.
Proof. We know from the definitions of V ( L ) ( o ) V^{(L)}(o) V ( L ) ( o ) and V ( o ) V(o) V ( o ) that
∣ V ( L ) ( o ) − V ( o ) ∣ ≤ t α ∑ w ∼ o ∣ b w → o ( L ) − b w → o ∣ , ∣ V ( o ) ∣ ≤ t α ∑ w ∼ o ∣ b w → o ∣ . \left|V^{(L)}(o)-V(o)\right|\le\frac{t}{\alpha}\sum_{w\sim o}\left|b_{w\to o}^{(L)}-b_{w\to o}\right|,\qquad|V(o)|\le\frac{t}{\alpha}\sum_{w\sim o}|b_{w\to o}|. V ( L ) ( o ) − V ( o ) ≤ α t w ∼ o ∑ b w → o ( L ) − b w → o , ∣ V ( o ) ∣ ≤ α t w ∼ o ∑ ∣ b w → o ∣.
By Cauchy–Schwarz,
∣ V ( L ) ( o ) − V ( o ) ∣ 2 ≤ t 2 α 2 deg ( o ) ∑ w ∼ o ∣ b w → o ( L ) − b w → o ∣ 2 , ∣ V ( o ) ∣ 2 ≤ t 2 α 2 deg ( o ) ∑ w ∼ o ∣ b w → o ∣ 2 . \left|V^{(L)}(o)-V(o)\right|^2\le\frac{t^2}{\alpha^2}\deg(o)\sum_{w\sim o}\left|b_{w\to o}^{(L)}-b_{w\to o}\right|^2,\qquad|V(o)|^2\le\frac{t^2}{\alpha^2}\deg(o)\sum_{w\sim o}|b_{w\to o}|^2. V ( L ) ( o ) − V ( o ) 2 ≤ α 2 t 2 deg ( o ) w ∼ o ∑ b w → o ( L ) − b w → o 2 , ∣ V ( o ) ∣ 2 ≤ α 2 t 2 deg ( o ) w ∼ o ∑ ∣ b w → o ∣ 2 .
Observe that conditional on K = deg ( o ) K=\deg(o) K = deg ( o ) , each ( b w → o ( L ) , b w → o ) (b_{w\to o}^{(L)},b_{w\to o}) ( b w → o ( L ) , b w → o ) has the same marginal distribution as ( b ( L ) , b ) (b^{(L)},b) ( b ( L ) , b ) , independent of the value of K K K . By Proposition 5.3 , we have E ∣ b ( L ) − b ∣ 2 → 0 \mathbb{E}|b^{(L)}-b|^2\to0 E ∣ b ( L ) − b ∣ 2 → 0 and E ∣ b ∣ 2 < ∞ \mathbb{E}|b|^2<\infty E ∣ b ∣ 2 < ∞ . Since K ∼ Poi ( d ) K\sim\operatorname{Poi}(d) K ∼ Poi ( d ) , we get that
E ∣ V ( L ) ( o ) − V ( o ) ∣ 2 ≤ t 2 α 2 E ( K 2 ) E ∣ b ( L ) − b ∣ 2 → 0 , E ∣ V ( o ) ∣ 2 ≤ t 2 α 2 E ( K 2 ) E ∣ b ∣ 2 < ∞ . \mathbb{E}\left|V^{(L)}(o)-V(o)\right|^2\le\frac{t^2}{\alpha^2}\mathbb{E}(K^2)\mathbb{E}|b^{(L)}-b|^2\to0,\qquad\mathbb{E}|V(o)|^2\le\frac{t^2}{\alpha^2}\mathbb{E}(K^2)\mathbb{E}|b|^2<\infty. E V ( L ) ( o ) − V ( o ) 2 ≤ α 2 t 2 E ( K 2 ) E ∣ b ( L ) − b ∣ 2 → 0 , E ∣ V ( o ) ∣ 2 ≤ α 2 t 2 E ( K 2 ) E ∣ b ∣ 2 < ∞.
We show that the vector V V V satisfies the eigenvector equation on the infinite tree.
Proposition 6.7. We have
( H ( t , T ) V ) ( u ) = − δ V ( u ) . (H(t,T)V)(u)=-\delta V(u). ( H ( t , T ) V ) ( u ) = − δ V ( u ) .
Proof. We first assume that for each u ∼ v u\sim v u ∼ v ,
b u → v = V ( u ) − Γ u ( v ) V ( v ) . (12) b_{u\to v}=V(u)-\Gamma_u^{(v)}V(v). \tag*{(12)} b u → v = V ( u ) − Γ u ( v ) V ( v ) . (12)
If this is indeed the case, then we can write Definition 6.5 as
V ( u ) = t ∑ w ∼ u ( V ( w ) − Γ w ( u ) V ( u ) ) t 2 − 1 + δ + deg ( u ) − t ∑ w ∼ u Γ w ( u ) . V(u)=\frac{t\sum_{w\sim u}\left(V(w)-\Gamma_w^{(u)}V(u)\right)}{t^2-1+\delta+\deg(u)-t\sum_{w\sim u}\Gamma_w^{(u)}}. V ( u ) = t 2 − 1 + δ + deg ( u ) − t ∑ w ∼ u Γ w ( u ) t ∑ w ∼ u ( V ( w ) − Γ w ( u ) V ( u ) ) .
Cross-multiplying gives the relation
( t 2 − 1 + δ + deg ( u ) ) V ( u ) = t ∑ w ∼ u V ( w ) , \left(t^2-1+\delta+\deg(u)\right)V(u)=t\sum_{w\sim u}V(w), ( t 2 − 1 + δ + deg ( u ) ) V ( u ) = t w ∼ u ∑ V ( w ) ,
giving H ( t , T ) V = − δ V H(t,T)V=-\delta V H ( t , T ) V = − δ V .
We are left to show (12) . To do this, by (6) , we can rewrite Definition 6.5 as
V ( u ) = t ∑ w ∼ u b w → u t ( ( Γ u ( v ) ) − 1 − Γ v ( u ) ) = ∑ w ∼ u b w → u ( Γ u ( v ) ) − 1 − Γ v ( u ) . (13) V(u)=\frac{t\sum_{w\sim u}b_{w\to u}}{t((\Gamma_u^{(v)})^{-1}-\Gamma_v^{(u)})}=\frac{\sum_{w\sim u}b_{w\to u}}{(\Gamma_u^{(v)})^{-1}-\Gamma_v^{(u)}}. \tag*{(13)} V ( u ) = t (( Γ u ( v ) ) − 1 − Γ v ( u ) ) t ∑ w ∼ u b w → u = ( Γ u ( v ) ) − 1 − Γ v ( u ) ∑ w ∼ u b w → u . (13)
We know from Corollary 5.5 that b u → v = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u b_{u\to v}=\Gamma_u^{(v)}\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u} b u → v = Γ u ( v ) ∑ w ∼ u w = v b w → u , which gives
V ( u ) = ( Γ u ( v ) ) − 1 b u → v + b v → u ( Γ u ( v ) ) − 1 − Γ v ( u ) = b u → v + Γ u ( v ) b v → u 1 − Γ v ( u ) Γ u ( v ) . (14) V(u)=\frac{(\Gamma_u^{(v)})^{-1}b_{u\to v}+b_{v\to u}}{(\Gamma_u^{(v)})^{-1}-\Gamma_v^{(u)}}=\frac{b_{u\to v}+\Gamma_u^{(v)}b_{v\to u}}{1-\Gamma_v^{(u)}\Gamma_u^{(v)}}. \tag*{(14)} V ( u ) = ( Γ u ( v ) ) − 1 − Γ v ( u ) ( Γ u ( v ) ) − 1 b u → v + b v → u = 1 − Γ v ( u ) Γ u ( v ) b u → v + Γ u ( v ) b v → u . (14)
We then have
V ( u ) − Γ u ( v ) V ( v ) = b u → v + Γ u ( v ) b v → u 1 − Γ u ( v ) Γ v ( u ) − Γ u ( v ) b v → u + Γ v ( u ) b u → v 1 − Γ u ( v ) Γ v ( u ) = b u → v , V(u)-\Gamma_u^{(v)}V(v)=\frac{b_{u\to v}+\Gamma_u^{(v)}b_{v\to u}}{1-\Gamma_u^{(v)}\Gamma_v^{(u)}}-\Gamma_u^{(v)}\frac{b_{v\to u}+\Gamma_v^{(u)}b_{u\to v}}{1-\Gamma_u^{(v)}\Gamma_v^{(u)}}=b_{u\to v}, V ( u ) − Γ u ( v ) V ( v ) = 1 − Γ u ( v ) Γ v ( u ) b u → v + Γ u ( v ) b v → u − Γ u ( v ) 1 − Γ u ( v ) Γ v ( u ) b v → u + Γ v ( u ) b u → v = b u → v ,
giving (12) .
We now show that this equality is satisfied by the limit of V ( L ) V^{(L)} V ( L ) as well.
Lemma 6.8. We have E [ ∣ ( H ( t , T ) + δ I ) V ( L ) ( o ) ∣ 2 ] → 0 \mathbb{E}\left[\left|(H(t,T)+\delta I)V^{(L)}(o)\right|^2\right]\to0 E [ ( H ( t , T ) + δ I ) V ( L ) ( o ) 2 ] → 0 as L → ∞ L\to\infty L → ∞ . That is, we have
E [ ∣ ( t 2 − 1 + δ + deg ( o ) ) V ( L ) ( o ) − t ∑ w ∼ o V ( L ) ( w ) ∣ 2 ] ⟶ 0 as L → ∞ . (15) \mathbb{E}\left[\left|(t^2-1+\delta+\deg(o))V^{(L)}(o)-t\sum_{w\sim o}V^{(L)}(w)\right|^2\right]\longrightarrow0\qquad\text{as }L\to\infty. \tag*{(15)} E ( t 2 − 1 + δ + deg ( o )) V ( L ) ( o ) − t w ∼ o ∑ V ( L ) ( w ) 2 ⟶ 0 as L → ∞. (15) Proof. Set e u → v ( L ) : = b u → v ( L ) − b u → v ( L + 1 ) e_{u\to v}^{(L)}:=b_{u\to v}^{(L)}-b_{u\to v}^{(L+1)} e u → v ( L ) := b u → v ( L ) − b u → v ( L + 1 ) . We can expand Definition 5.2, then use the fact that (13) is also true between V ( L ) V^{(L)} V ( L ) and b ( L ) b^{(L)} b ( L ) , giving
b u → v ( L ) = Γ u ( v ) ∑ w ∼ u w ≠ v b w → u ( L ) + e u → v ( L ) = ( 1 − Γ u ( v ) Γ v ( u ) ) V ( L ) ( u ) − Γ u ( v ) b v → u ( L ) + e u → v ( L ) . b_{u\to v}^{(L)}=\Gamma_u^{(v)}\sum_{\substack{w\sim u\\w\ne v}}b_{w\to u}^{(L)}+e_{u\to v}^{(L)}=(1-\Gamma_u^{(v)}\Gamma_v^{(u)})V^{(L)}(u)-\Gamma_u^{(v)}b_{v\to u}^{(L)}+e_{u\to v}^{(L)}. b u → v ( L ) = Γ u ( v ) w ∼ u w = v ∑ b w → u ( L ) + e u → v ( L ) = ( 1 − Γ u ( v ) Γ v ( u ) ) V ( L ) ( u ) − Γ u ( v ) b v → u ( L ) + e u → v ( L ) . Interchanging u u u and v v v gives b v → u ( L ) = ( 1 − Γ v ( u ) Γ u ( v ) ) V ( L ) ( v ) − Γ v ( u ) b u → v ( L ) + e v → u ( L ) b_{v\to u}^{(L)}=(1-\Gamma_v^{(u)}\Gamma_u^{(v)})V^{(L)}(v)-\Gamma_v^{(u)}b_{u\to v}^{(L)}+e_{v\to u}^{(L)} b v → u ( L ) = ( 1 − Γ v ( u ) Γ u ( v ) ) V ( L ) ( v ) − Γ v ( u ) b u → v ( L ) + e v → u ( L ) . Substituting this into the preceding equation, we obtain
b u → v ( L ) = ( 1 − Γ u ( v ) Γ v ( u ) ) V ( L ) ( u ) − Γ u ( v ) ( ( 1 − Γ u ( v ) Γ v ( u ) ) V ( L ) ( v ) − Γ v ( u ) b u → v ( L ) + e v → u ( L ) ) + e u → v ( L ) = ( 1 − Γ u ( v ) Γ v ( u ) ) ( V ( L ) ( u ) − Γ u ( v ) V ( L ) ( v ) ) + Γ u ( v ) Γ v ( u ) b u → v ( L ) + e u → v ( L ) − Γ u ( v ) e v → u ( L ) = V ( L ) ( u ) − Γ u ( v ) V ( L ) ( v ) + e u → v ( L ) − Γ u ( v ) e v → u ( L ) 1 − Γ u ( v ) Γ v ( u ) . \begin{aligned}
b_{u\to v}^{(L)}&=(1-\Gamma_u^{(v)}\Gamma_v^{(u)})V^{(L)}(u)-\Gamma_u^{(v)}\left((1-\Gamma_u^{(v)}\Gamma_v^{(u)})V^{(L)}(v)-\Gamma_v^{(u)}b_{u\to v}^{(L)}+e_{v\to u}^{(L)}\right)+e_{u\to v}^{(L)}\\
&=(1-\Gamma_u^{(v)}\Gamma_v^{(u)})\left(V^{(L)}(u)-\Gamma_u^{(v)}V^{(L)}(v)\right)+\Gamma_u^{(v)}\Gamma_v^{(u)}b_{u\to v}^{(L)}+e_{u\to v}^{(L)}-\Gamma_u^{(v)}e_{v\to u}^{(L)}\\
&=V^{(L)}(u)-\Gamma_u^{(v)}V^{(L)}(v)+\frac{e_{u\to v}^{(L)}-\Gamma_u^{(v)}e_{v\to u}^{(L)}}{1-\Gamma_u^{(v)}\Gamma_v^{(u)}}.
\end{aligned} b u → v ( L ) = ( 1 − Γ u ( v ) Γ v ( u ) ) V ( L ) ( u ) − Γ u ( v ) ( ( 1 − Γ u ( v ) Γ v ( u ) ) V ( L ) ( v ) − Γ v ( u ) b u → v ( L ) + e v → u ( L ) ) + e u → v ( L ) = ( 1 − Γ u ( v ) Γ v ( u ) ) ( V ( L ) ( u ) − Γ u ( v ) V ( L ) ( v ) ) + Γ u ( v ) Γ v ( u ) b u → v ( L ) + e u → v ( L ) − Γ u ( v ) e v → u ( L ) = V ( L ) ( u ) − Γ u ( v ) V ( L ) ( v ) + 1 − Γ u ( v ) Γ v ( u ) e u → v ( L ) − Γ u ( v ) e v → u ( L ) . Substituting this into Definition 6.5 therefore yields
( t 2 − 1 + δ + deg ( o ) − t ∑ w ∼ o Γ w ( o ) ) V ( L ) ( o ) = t ∑ w ∼ o b w → o ( L ) = t ∑ w ∼ o V ( L ) ( w ) − t ( ∑ w ∼ o Γ w ( o ) ) V ( L ) ( o ) + t ∑ w ∼ o e w → o ( L ) − Γ w ( o ) e o → w ( L ) 1 − Γ w ( o ) Γ o ( w ) . \begin{aligned}
\left(t^2-1+\delta+\deg(o)-t\sum_{w\sim o}\Gamma_w^{(o)}\right)V^{(L)}(o)
&=t\sum_{w\sim o}b_{w\to o}^{(L)}\\
&=t\sum_{w\sim o}V^{(L)}(w)-t\left(\sum_{w\sim o}\Gamma_w^{(o)}\right)V^{(L)}(o)+t\sum_{w\sim o}\frac{e_{w\to o}^{(L)}-\Gamma_w^{(o)}e_{o\to w}^{(L)}}{1-\Gamma_w^{(o)}\Gamma_o^{(w)}}.
\end{aligned} ( t 2 − 1 + δ + deg ( o ) − t w ∼ o ∑ Γ w ( o ) ) V ( L ) ( o ) = t w ∼ o ∑ b w → o ( L ) = t w ∼ o ∑ V ( L ) ( w ) − t ( w ∼ o ∑ Γ w ( o ) ) V ( L ) ( o ) + t w ∼ o ∑ 1 − Γ w ( o ) Γ o ( w ) e w → o ( L ) − Γ w ( o ) e o → w ( L ) .
Since ∣ Γ u ( v ) ∣ ≤ c < 1 |\Gamma^{(v)}_u|\le c<1 ∣ Γ u ( v ) ∣ ≤ c < 1 , Cauchy–Schwarz gives
E ∣ t 2 − 1 + δ + deg ( o ) V ( L ) ( o ) − t ∑ w ∼ o V ( L ) ( w ) ∣ 2 ≤ C E [ deg ( o ) ∑ w ∼ o ( ∣ e o → w ( L ) ∣ 2 + ∣ e w → o ( L ) ∣ 2 ) ] (16) \mathbb{E}\left|t^2-1+\delta+\operatorname{deg}(o)V^{(L)}(o)-t\sum_{w\sim o}V^{(L)}(w)\right|^2\le C\mathbb{E}\left[\operatorname{deg}(o)\sum_{w\sim o}\left(|e^{(L)}_{o\to w}|^2+|e^{(L)}_{w\to o}|^2\right)\right] \tag*{(16)} E t 2 − 1 + δ + deg ( o ) V ( L ) ( o ) − t w ∼ o ∑ V ( L ) ( w ) 2 ≤ C E [ deg ( o ) w ∼ o ∑ ( ∣ e o → w ( L ) ∣ 2 + ∣ e w → o ( L ) ∣ 2 ) ] (16)
where C C C depends only on t , c t,c t , c . Since the incoming defects satisfy E ∣ e o → w ( L ) ∣ 2 = E ∣ e ( L ) ∣ 2 → 0 \mathbb{E}|e^{(L)}_{o\to w}|^2=\mathbb{E}|e^{(L)}|^2\to0 E ∣ e o → w ( L ) ∣ 2 = E ∣ e ( L ) ∣ 2 → 0 as L → ∞ L\to\infty L → ∞ , the outgoing defects satisfy
e o → w ( L ) = Γ o ( w ) ∑ w ′ ∼ o w ′ ≠ w e w ′ → o ( L − 1 ) . e^{(L)}_{o\to w}=\Gamma^{(w)}_o\sum_{\substack{w'\sim o\\w'\ne w}}e^{(L-1)}_{w'\to o}. e o → w ( L ) = Γ o ( w ) w ′ ∼ o w ′ = w ∑ e w ′ → o ( L − 1 ) .
∣ Γ o ( w ) ∣ ≤ c |\Gamma^{(w)}_o|\le c ∣ Γ o ( w ) ∣ ≤ c , and deg ( o ) ∼ Poi ( d ) \operatorname{deg}(o)\sim\operatorname{Poi}(d) deg ( o ) ∼ Poi ( d ) , we know that (16) tends to zero as L → ∞ L\to\infty L → ∞ .
We now obtain similar approximations for the variable V ( L , M ) V^{(L,M)} V ( L , M ) , which only depends on a finite neighborhood.
Lemma 6.9. On the Galton–Watson tree, for every L ≥ 0 L\ge0 L ≥ 0 , as M → ∞ M\to\infty M → ∞ , we have
V ( L , M ) ( o ) ⟶ V ( L ) ( o ) and [ ( H + δ I ) V ( L , M ) ] ( o ) ⟶ [ ( H + δ I ) V ( L ) ] ( o ) , V^{(L,M)}(o)\longrightarrow V^{(L)}(o)\qquad\text{and}\qquad[(H+\delta I)V^{(L,M)}](o)\longrightarrow[(H+\delta I)V^{(L)}](o), V ( L , M ) ( o ) ⟶ V ( L ) ( o ) and [( H + δ I ) V ( L , M ) ] ( o ) ⟶ [( H + δ I ) V ( L ) ] ( o ) , both in L 2 L^2 L 2 .
Proof. It is easy to check, using Definition 3.3 and induction on L L L , that lim M → ∞ b u → v ( L , M ) = b u → v ( L ) \lim_{M\to\infty}b^{(L,M)}_{u\to v}=b^{(L)}_{u\to v} lim M → ∞ b u → v ( L , M ) = b u → v ( L ) for every fixed L L L . It follows that, for every u u u with finitely many neighbors,
V ( L , M ) ( u ) = t ∑ v ∼ u b v → u ( L , M ) t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u ( Γ v ( u ) ) ( M ) V^{(L,M)}(u)=\frac{t\sum_{v\sim u}b^{(L,M)}_{v\to u}}{t^2+\operatorname{deg}(u)-1+\delta-t\sum_{v\sim u}(\Gamma^{(u)}_v)^{(M)}} V ( L , M ) ( u ) = t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u ( Γ v ( u ) ) ( M ) t ∑ v ∼ u b v → u ( L , M )
⟶ t ∑ v ∼ u b v → u ( L ) t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) = V ( L ) ( u ) . \longrightarrow\frac{t\sum_{v\sim u}b^{(L)}_{v\to u}}{t^2+\operatorname{deg}(u)-1+\delta-t\sum_{v\sim u}\Gamma^{(u)}_v}=V^{(L)}(u). ⟶ t 2 + deg ( u ) − 1 + δ − t ∑ v ∼ u Γ v ( u ) t ∑ v ∼ u b v → u ( L ) = V ( L ) ( u ) .
In particular, it holds almost surely at o o o and at each of its neighbors. Therefore,
[ ( H + δ I ) V ( L , M ) ] ( o ) = ( α + deg ( o ) ) V ( L , M ) ( o ) − t ∑ x ∼ o V ( L , M ) ( x ) [(H+\delta I)V^{(L,M)}](o)=(\alpha+\operatorname{deg}(o))V^{(L,M)}(o)-t\sum_{x\sim o}V^{(L,M)}(x) [( H + δ I ) V ( L , M ) ] ( o ) = ( α + deg ( o )) V ( L , M ) ( o ) − t x ∼ o ∑ V ( L , M ) ( x )
⟶ ( α + deg ( o ) ) V ( L ) ( o ) − t ∑ x ∼ o V ( L ) ( x ) = [ ( H + δ I ) V ( L ) ] ( o ) \longrightarrow(\alpha+\operatorname{deg}(o))V^{(L)}(o)-t\sum_{x\sim o}V^{(L)}(x)=[(H+\delta I)V^{(L)}](o) ⟶ ( α + deg ( o )) V ( L ) ( o ) − t x ∼ o ∑ V ( L ) ( x ) = [( H + δ I ) V ( L ) ] ( o )
almost surely.
By Theorem 6.4, there is a constant C L < ∞ C_L<\infty C L < ∞ , independent of M M M , such that
∣ V ( L , M ) ( o ) ∣ + ∣ [ ( H + δ I ) V ( L , M ) ] ( o ) ∣ ≤ C L ∣ B L + 2 ( T , o ) ∣ L + 2 . |V^{(L,M)}(o)|+\left|[(H+\delta I)V^{(L,M)}](o)\right|\le C_L|B_{L+2}(T,o)|^{L+2}. ∣ V ( L , M ) ( o ) ∣ + [( H + δ I ) V ( L , M ) ] ( o ) ≤ C L ∣ B L + 2 ( T , o ) ∣ L + 2 .
Taking M → ∞ M\to\infty M → ∞ in this inequality gives
∣ V ( L ) ( o ) ∣ + ∣ [ ( H + δ I ) V ( L ) ] ( o ) ∣ ≤ C L ∣ B L + 2 ( T , o ) ∣ L + 2 almost surely . |V^{(L)}(o)|+\left|[(H+\delta I)V^{(L)}](o)\right|\le C_L|B_{L+2}(T,o)|^{L+2}\qquad\text{almost surely}. ∣ V ( L ) ( o ) ∣ + [( H + δ I ) V ( L ) ] ( o ) ≤ C L ∣ B L + 2 ( T , o ) ∣ L + 2 almost surely .
The triangle inequality therefore gives
∣ V ( L , M ) ( o ) − V ( L ) ( o ) ∣ + ∣ [ ( H + δ I ) ( V ( L , M ) − V ( L ) ) ] ( o ) ∣ ≤ 2 C L ∣ B L + 2 ( T , o ) ∣ L + 2 , |V^{(L,M)}(o)-V^{(L)}(o)|+\left|[(H+\delta I)(V^{(L,M)}-V^{(L)})](o)\right|\le2C_L|B_{L+2}(T,o)|^{L+2}, ∣ V ( L , M ) ( o ) − V ( L ) ( o ) ∣ + [( H + δ I ) ( V ( L , M ) − V ( L ) )] ( o ) ≤ 2 C L ∣ B L + 2 ( T , o ) ∣ L + 2 ,
∣ V ( L , M ) ( o ) − V ( L ) ( o ) ∣ 2 + ∣ [ ( H + δ I ) ( V ( L , M ) − V ( L ) ) ] ( o ) ∣ 2 ≤ 4 C L 2 ∣ B L + 2 ( T , o ) ∣ 2 L + 4 . |V^{(L,M)}(o)-V^{(L)}(o)|^2+\left|[(H+\delta I)(V^{(L,M)}-V^{(L)})](o)\right|^2\le4C_L^2|B_{L+2}(T,o)|^{2L+4}. ∣ V ( L , M ) ( o ) − V ( L ) ( o ) ∣ 2 + [( H + δ I ) ( V ( L , M ) − V ( L ) )] ( o ) 2 ≤ 4 C L 2 ∣ B L + 2 ( T , o ) ∣ 2 L + 4 .
Since L L L is fixed, we have E ∣ B L + 2 ( T , o ) ∣ 2 L + 4 < ∞ \mathbb{E}|B_{L+2}(T,o)|^{2L+4}<\infty E ∣ B L + 2 ( T , o ) ∣ 2 L + 4 < ∞ . We know from the previous paragraph that both squared differences converge to zero almost surely. Dominated convergence therefore gives
E ∣ V ( L , M ) ( o ) − V ( L ) ( o ) ∣ 2 ⟶ 0 and E ∣ [ ( H + δ I ) ( V ( L , M ) − V ( L ) ) ] ( o ) ∣ 2 ⟶ 0. \mathbb{E}\left|V^{(L,M)}(o)-V^{(L)}(o)\right|^2\longrightarrow0
\quad\text{and}\quad
\mathbb{E}\left|\left[(H+\delta I)(V^{(L,M)}-V^{(L)})\right](o)\right|^2\longrightarrow0. E V ( L , M ) ( o ) − V ( L ) ( o ) 2 ⟶ 0 and E [ ( H + δ I ) ( V ( L , M ) − V ( L ) ) ] ( o ) 2 ⟶ 0.
Finite convergence
We now transfer the tree construction to the finite SBM. We will first truncate both recursions, obtaining fields determined by finite neighborhoods. Local convergence then transfers their moments and residuals to the finite graph. Then, an eigenvalue count identifies the resulting approximate eigenspaces with the actual spectral subspaces.
In this section, fix d ≤ t < μ r + + \sqrt{d}\leq t<\mu_{r_+}^+ d ≤ t < μ r + + . For notational convenience, relabel the positive informative eigenvalues and their associated eigenfunctions as μ 1 , … , μ r + \mu_1,\ldots,\mu_{r_+} μ 1 , … , μ r + and φ 1 , … , φ r + \varphi_1,\ldots,\varphi_{r_+} φ 1 , … , φ r + . Let G n G_n G n be an n n n -vertex SBM with vertex labeling σ : V ( G n ) → [ r ] \sigma:V(G_n)\to[r] σ : V ( G n ) → [ r ] , and let ( T , o ) (T,o) ( T , o ) be its limiting multi-type Galton–Watson tree. The following local averaging lemma is standard; see, for example, [9 Propositions 35–36] .
Lemma 7.1 (Local averaging). Fix R ≥ 0 R\geq0 R ≥ 0 . Let f f f be a real function on rooted graphs ( G , u ) (G,u) ( G , u ) with vertex labels in [ r ] [r] [ r ] . Suppose f f f only depends on B R ( G , u ) B_R(G,u) B R ( G , u ) and that for some fixed C C C , p < ∞ p<\infty p < ∞ , we have
∣ f ( G , u ) ∣ ≤ C ∣ B R ( G , u ) ∣ p |f(G,u)|\leq C|B_R(G,u)|^p ∣ f ( G , u ) ∣ ≤ C ∣ B R ( G , u ) ∣ p for all ( G , u ) (G,u) ( G , u ) .
Then we have
1 n ∑ u ∈ V ( G n ) f ( G n , u ) ⟶ E f ( T , o ) in L 2 . \frac{1}{n}\sum_{u\in V(G_n)}f(G_n,u)\longrightarrow\mathbb{E}f(T,o)
\quad\text{in }L^2. n 1 u ∈ V ( G n ) ∑ f ( G n , u ) ⟶ E f ( T , o ) in L 2 .
We previously fixed δ = δ i = δ ( μ i ) \delta=\delta_i=\delta(\mu_i) δ = δ i = δ ( μ i ) and X = X i X=X_i X = X i . In the following proposition, we will add the subscript i i i to emphasize the dependence on i ∈ [ r + ] i\in[r_+] i ∈ [ r + ] , and write V i V_i V i for the field V V V on T T T as in Definition 6.5 .
Proposition 7.2. Let δ i = δ ( μ i ) \delta_i=\delta(\mu_i) δ i = δ ( μ i ) , s i 2 : = E [ V i ( o ) 2 ] > 0 s_i^2:=\mathbb{E}[V_i(o)^2]>0 s i 2 := E [ V i ( o ) 2 ] > 0 , and a i : = E [ V i ( o ) X i ( o ) ] a_i:=\mathbb{E}[V_i(o)X_i(o)] a i := E [ V i ( o ) X i ( o )] . There are deterministic sequences L ( n ) , M ( n ) → ∞ L(n),M(n)\to\infty L ( n ) , M ( n ) → ∞ such that, for
V i , n ( u ) : = V i ( L ( n ) , M ( n ) ) ( G n , u ) , V_{i,n}(u):=V_i^{(L(n),M(n))}(G_n,u), V i , n ( u ) := V i ( L ( n ) , M ( n )) ( G n , u ) , we have:
1 n ⟨ V i , n , V j , n ⟩ ⟶ 1 { i = j } s i 2 \frac{1}{n}\langle V_{i,n},V_{j,n}\rangle\longrightarrow\mathbf{1}_{\{i=j\}}s_i^2 n 1 ⟨ V i , n , V j , n ⟩ ⟶ 1 { i = j } s i 2 and 1 n ⟨ V i , n , X j ⟩ ⟶ 1 { i = j } a i \frac{1}{n}\langle V_{i,n},X_j\rangle\longrightarrow\mathbf{1}_{\{i=j\}}a_i n 1 ⟨ V i , n , X j ⟩ ⟶ 1 { i = j } a i in L 2 L^2 L 2 ;
1 n ∥ ( H ( t , G n ) + δ i I ) V i , n ∥ 2 ⟶ 0 \frac{1}{n}\left\|(H(t,G_n)+\delta_i I)V_{i,n}\right\|^2\longrightarrow0 n 1 ∥ ( H ( t , G n ) + δ i I ) V i , n ∥ 2 ⟶ 0 ;
The empirical measure
1 n ∑ u ∈ V ( G n ) δ ( σ ( u ) , V 1 , n ( u ) , … , V r + , n ( u ) ) \frac{1}{n}\sum_{u\in V(G_n)}\delta_{(\sigma(u),V_{1,n}(u),\ldots,V_{r_+,n}(u))} n 1 u ∈ V ( G n ) ∑ δ ( σ ( u ) , V 1 , n ( u ) , … , V r + , n ( u )) converges weakly in probability to the law of ( σ ( o ) , V 1 ( o ) , … , V r + ( o ) ) (\sigma(o),V_1(o),\ldots,V_{r_+}(o)) ( σ ( o ) , V 1 ( o ) , … , V r + ( o )) .
Proof. We choose bounded Lipschitz functions Ψ m : [ r ] × R r + → [ − 1 , 1 ] \Psi_m : [r] \times\mathbb{R}^{r_+} \to[-1,1] Ψ m : [ r ] × R r + → [ − 1 , 1 ] such that, for probability measures ( ν ℓ ) ℓ ≥ 1 , ν (\nu_\ell)_{\ell\ge1},\nu ( ν ℓ ) ℓ ≥ 1 , ν on [ r ] × R r + [r] \times\mathbb{R}^{r_+} [ r ] × R r + , ν ℓ → ν \nu_\ell\to\nu ν ℓ → ν weakly if and only if ∫ Ψ m d ν ℓ → ∫ Ψ m d ν \int\Psi_m\,d\nu_\ell\to\int\Psi_m\,d\nu ∫ Ψ m d ν ℓ → ∫ Ψ m d ν for every m ≥ 1 m \ge1 m ≥ 1 . For example, let ( Ψ m ) m ≥ 1 (\Psi_m)_{m \ge1} ( Ψ m ) m ≥ 1 enumerate the functions
Ψ a , α ( b , x ) : = 1 { b = a } ∏ j = 1 r + ( tanh x j ) α j , a ∈ [ r ] , α ∈ Z ≥ 0 r + . \Psi_{a,\alpha}(b,x) := \mathbb{1}\{b=a\}\prod_{j=1}^{r_+}(\tanh x_j)^{\alpha_j}, \qquad a \in[r],\quad\alpha\in\mathbb{Z}_{\ge0}^{r_+}. Ψ a , α ( b , x ) := 1 { b = a } j = 1 ∏ r + ( tanh x j ) α j , a ∈ [ r ] , α ∈ Z ≥ 0 r + .
Each function is Lipschitz and takes values in [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] . The linear span of these functions is an algebra of bounded continuous functions that strongly separates points. Thus this family determines weak convergence by [14 Chapter 3, Theorem 4.5(b)] .
Write
η n , L , M : = 1 n ∑ u ∈ V ( G n ) δ ( σ ( u ) , V 1 ( L , M ) ( G n , u ) , … , V r + ( L , M ) ( G n , u ) ) \eta_{n,L,M}:=\frac{1}{n}\sum_{u\in V(G_n)}\delta_{(\sigma(u),V_1^{(L,M)}(G_n,u),\ldots,V_{r_+}^{(L,M)}(G_n,u))} η n , L , M := n 1 u ∈ V ( G n ) ∑ δ ( σ ( u ) , V 1 ( L , M ) ( G n , u ) , … , V r + ( L , M ) ( G n , u ))
and let η \eta η be the law of ( σ ( o ) , V 1 ( o ) , … , V r + ( o ) ) (\sigma(o),V_1(o),\ldots,V_{r_+}(o)) ( σ ( o ) , V 1 ( o ) , … , V r + ( o )) .
Recall (e.g., from [9 Lemma 27] ) that if T 0 T_0 T 0 is the underlying unlabelled tree, then we have E ( X i ( x ) X j ( y ) ∣ T 0 ) = 0 \mathbb{E}(X_i(x)X_j(y)\mid T_0)=0 E ( X i ( x ) X j ( y ) ∣ T 0 ) = 0 for i ≠ j i\ne j i = j . Thus, by Theorems 6.6 and 6.9 and Cauchy–Schwarz, we have
lim L → ∞ lim M → ∞ E [ V i ( L , M ) ( o ) V j ( L , M ) ( o ) ] = 1 { i = j } s i 2 , lim L → ∞ lim M → ∞ E [ V i ( L , M ) ( o ) X j ( o ) ] = 1 { i = j } a i . \lim_{L\to\infty}\lim_{M\to\infty}\mathbb{E}\left[V_i^{(L,M)}(o)V_j^{(L,M)}(o)\right]=\mathbb{1}_{\{i=j\}}s_i^2,\qquad
\lim_{L\to\infty}\lim_{M\to\infty}\mathbb{E}\left[V_i^{(L,M)}(o)X_j(o)\right]=\mathbb{1}_{\{i=j\}}a_i. L → ∞ lim M → ∞ lim E [ V i ( L , M ) ( o ) V j ( L , M ) ( o ) ] = 1 { i = j } s i 2 , L → ∞ lim M → ∞ lim E [ V i ( L , M ) ( o ) X j ( o ) ] = 1 { i = j } a i .
Similarly, Theorems 6.8 and 6.9 give
lim L → ∞ lim M → ∞ E [ ( ( H ( t , T ) + δ i I ) V i ( L , M ) ) ( o ) 2 ] = 0. \lim_{L\to\infty}\lim_{M\to\infty}\mathbb{E}\left[\left((H(t,T)+\delta_i I)V_i^{(L,M)}\right)(o)^2\right]=0. L → ∞ lim M → ∞ lim E [ ( ( H ( t , T ) + δ i I ) V i ( L , M ) ) ( o ) 2 ] = 0.
Since each Ψ m \Psi_m Ψ m is Lipschitz, Theorems 6.6 and 6.9 also give
lim L → ∞ lim M → ∞ E Ψ m ( σ ( o ) , V 1 ( L , M ) ( o ) , … , V r + ( L , M ) ( o ) ) = E Ψ m ( σ ( o ) , V 1 ( o ) , … , V r + ( o ) ) = ∫ Ψ m d η . \lim_{L\to\infty}\lim_{M\to\infty}\mathbb{E}\Psi_m\left(\sigma(o),V_1^{(L,M)}(o),\ldots,V_{r_+}^{(L,M)}(o)\right)=\mathbb{E}\Psi_m\left(\sigma(o),V_1(o),\ldots,V_{r_+}(o)\right)=\int\Psi_m\,d\eta. L → ∞ lim M → ∞ lim E Ψ m ( σ ( o ) , V 1 ( L , M ) ( o ) , … , V r + ( L , M ) ( o ) ) = E Ψ m ( σ ( o ) , V 1 ( o ) , … , V r + ( o ) ) = ∫ Ψ m d η .
For fixed L , M L,M L , M , Theorems 6.2 and 6.4 allow us to apply Theorem 7.1 to
V i ( L , M ) ( u ) V j ( L , M ) ( u ) , V i ( L , M ) ( u ) X j ( u ) , ∣ [ ( H ( t , G ) + δ i I ) V i ( L , M ) ] ( u ) ∣ 2 , V_i^{(L,M)}(u)V_j^{(L,M)}(u),\qquad V_i^{(L,M)}(u)X_j(u),\qquad\left|\left[(H(t,G)+\delta_i I)V_i^{(L,M)}\right](u)\right|^2, V i ( L , M ) ( u ) V j ( L , M ) ( u ) , V i ( L , M ) ( u ) X j ( u ) , [ ( H ( t , G ) + δ i I ) V i ( L , M ) ] ( u ) 2 ,
and
Ψ m ( σ ( u ) , V 1 ( L , M ) ( u ) , … , V r + ( L , M ) ( u ) ) . \Psi_m\left(\sigma(u),V_1^{(L,M)}(u),\ldots,V_{r_+}^{(L,M)}(u)\right). Ψ m ( σ ( u ) , V 1 ( L , M ) ( u ) , … , V r + ( L , M ) ( u ) ) .
For any integer k ≥ 1 k\ge1 k ≥ 1 , we can therefore choose integers L k , M k ≥ k L_k,M_k\ge k L k , M k ≥ k and n k n_k n k such that for any n ≥ n k n\ge n_k n ≥ n k ,
max i , j ∈ [ r + ] ∥ 1 n ∑ u ∈ V ( G n ) V i ( L k , M k ) ( G n , u ) V j ( L k , M k ) ( G n , u ) − 1 { i = j } s i 2 ∥ 2 ≤ 1 k , max i , j ∈ [ r + ] ∥ 1 n ∑ u ∈ V ( G n ) V i ( L k , M k ) ( G n , u ) X j ( u ) − 1 { i = j } a i ∥ 2 ≤ 1 k , max i ∈ [ r + ] ∥ 1 n ∑ u ∈ V ( G n ) ∣ [ ( H ( t , G n ) + δ i I ) V i ( L k , M k ) ] ( u ) ∣ 2 ∥ 2 ≤ 1 k , max 1 ≤ m ≤ k ∥ ∫ Ψ m d η n , L k , M k − ∫ Ψ m d η ∥ 2 ≤ 1 k . (17) \begin{aligned}
\max_{i,j\in[r_+]}\left\|\frac{1}{n}\sum_{u\in V(G_n)}V_i^{(L_k,M_k)}(G_n,u)V_j^{(L_k,M_k)}(G_n,u)-\mathbb{1}_{\{i=j\}}s_i^2\right\|_2&\le\frac{1}{k},\\
\max_{i,j\in[r_+]}\left\|\frac{1}{n}\sum_{u\in V(G_n)}V_i^{(L_k,M_k)}(G_n,u)X_j(u)-\mathbb{1}_{\{i=j\}}a_i\right\|_2&\le\frac{1}{k},\\
\max_{i\in[r_+]}\left\|\frac{1}{n}\sum_{u\in V(G_n)}\left|\left[(H(t,G_n)+\delta_i I)V_i^{(L_k,M_k)}\right](u)\right|^2\right\|_2&\le\frac{1}{k},\\
\max_{1\le m\le k}\left\|\int\Psi_m\,d\eta_{n,L_k,M_k}-\int\Psi_m\,d\eta\right\|_2&\le\frac{1}{k}. \tag*{(17)}
\end{aligned} i , j ∈ [ r + ] max n 1 u ∈ V ( G n ) ∑ V i ( L k , M k ) ( G n , u ) V j ( L k , M k ) ( G n , u ) − 1 { i = j } s i 2 2 i , j ∈ [ r + ] max n 1 u ∈ V ( G n ) ∑ V i ( L k , M k ) ( G n , u ) X j ( u ) − 1 { i = j } a i 2 i ∈ [ r + ] max n 1 u ∈ V ( G n ) ∑ [ ( H ( t , G n ) + δ i I ) V i ( L k , M k ) ] ( u ) 2 2 1 ≤ m ≤ k max ∫ Ψ m d η n , L k , M k − ∫ Ψ m d η 2 ≤ k 1 , ≤ k 1 , ≤ k 1 , ≤ k 1 . (17)
For every n ≥ n 1 n \ge n_1 n ≥ n 1 , choose k k k such that n k ≤ n < n k + 1 n_k \le n < n_{k+1} n k ≤ n < n k + 1 , and set ( L ( n ) , M ( n ) ) = ( L k , M k ) (L(n),M(n))=(L_k,M_k) ( L ( n ) , M ( n )) = ( L k , M k ) . Then L ( n ) , M ( n ) → ∞ L(n),M(n)\to\infty L ( n ) , M ( n ) → ∞ , and the first three inequalities above prove (1) and (2) in L 2 L^2 L 2 .
For (3), set η n = η n , L ( n ) , M ( n ) \eta_n=\eta_{n,L(n),M(n)} η n = η n , L ( n ) , M ( n ) and define
d ∗ ( α , β ) : = ∑ m = 1 ∞ 2 − m ∣ ∫ Ψ m d α − ∫ Ψ m d β ∣ . d_*(\alpha,\beta):=\sum_{m=1}^{\infty}2^{-m}\left|\int\Psi_m\,d\alpha-\int\Psi_m\,d\beta\right|. d ∗ ( α , β ) := m = 1 ∑ ∞ 2 − m ∫ Ψ m d α − ∫ Ψ m d β .
By the choice of ( Ψ m ) (\Psi_m) ( Ψ m ) , convergence in d ∗ d_* d ∗ is equivalent to weak convergence. For n k ≤ n < n k + 1 n_k\le n<n_{k+1} n k ≤ n < n k + 1 , the fourth inequality of (17) and ∣ Ψ m ∣ ≤ 1 |\Psi_m|\le1 ∣ Ψ m ∣ ≤ 1 give
∥ d ∗ ( η n , η ) ∥ L 2 ≤ ∑ m = 1 k 2 − m 1 k + 2 ∑ m > k 2 − m ≤ 1 k + 2 1 − k ⟶ 0. \|d_*(\eta_n,\eta)\|_{L^2}\le\sum_{m=1}^{k}2^{-m}\frac{1}{k}+2\sum_{m>k}2^{-m}\le\frac{1}{k}+2^{1-k}\longrightarrow0. ∥ d ∗ ( η n , η ) ∥ L 2 ≤ m = 1 ∑ k 2 − m k 1 + 2 m > k ∑ 2 − m ≤ k 1 + 2 1 − k ⟶ 0.
Thus d ∗ ( η n , η ) → 0 d_*(\eta_n,\eta)\to0 d ∗ ( η n , η ) → 0 in probability, proving (3).
It remains to identify these approximate eigenspaces with the spectral subspaces of H ( t , G n ) H(t,G_n) H ( t , G n ) .
Proposition 7.3. There exist orthonormal eigenvectors v 1 , n , … , v r + , n v_{1,n},\ldots,v_{r_+,n} v 1 , n , … , v r + , n of H ( t , G n ) H(t,G_n) H ( t , G n ) , with corresponding eigenvalues − δ 1 , n , … , − δ r + , n -\delta_{1,n},\ldots,-\delta_{r_+,n} − δ 1 , n , … , − δ r + , n , such that
δ i , n → P δ i ( 1 ≤ i ≤ r + ) . \delta_{i,n}\xrightarrow{\mathbb{P}}\delta_i\qquad(1\le i\le r_+). δ i , n P δ i ( 1 ≤ i ≤ r + ) . For each distinct μ ∈ { μ 1 , … , μ r + } \mu\in\{\mu_1,\ldots,\mu_{r_+}\} μ ∈ { μ 1 , … , μ r + } , write J μ = { i : μ i = μ } J_\mu=\{i:\mu_i=\mu\} J μ = { i : μ i = μ } . There is an orthogonal matrix O μ , n O_{\mu,n} O μ , n indexed by J μ J_\mu J μ such that
max i ∈ J μ ∥ ∑ j ∈ J μ ( O μ , n ) j i v j , n − V i , n ∥ V i , n ∥ 2 ∥ 2 → P 0. \max_{i\in J_\mu}\left\|\sum_{j\in J_\mu}(O_{\mu,n})_{ji}v_{j,n}-\frac{V_{i,n}}{\|V_{i,n}\|_2}\right\|_2\xrightarrow{\mathbb{P}}0. i ∈ J μ max j ∈ J μ ∑ ( O μ , n ) j i v j , n − ∥ V i , n ∥ 2 V i , n 2 P 0. In particular, if μ i \mu_i μ i is simple, the sign of v i , n v_{i,n} v i , n can be chosen so that
∥ v i , n − V i , n ∥ V i , n ∥ 2 ∥ 2 → P 0. \left\|v_{i,n}-\frac{V_{i,n}}{\|V_{i,n}\|_2}\right\|_2\xrightarrow{\mathbb{P}}0. v i , n − ∥ V i , n ∥ 2 V i , n 2 P 0.
Proof. Write H n = H ( t , G n ) H_n=H(t,G_n) H n = H ( t , G n ) , m μ = ∣ J μ ∣ m_\mu=|J_\mu| m μ = ∣ J μ ∣ , and δ μ = δ ( μ ) \delta_\mu=\delta(\mu) δ μ = δ ( μ ) . All matrix norms below are operator norms, and all limits are in probability.
Choose γ > 0 \gamma>0 γ > 0 so that the intervals
I μ = ( − δ μ − γ , − δ μ + γ ) I_\mu=(-\delta_\mu-\gamma,-\delta_\mu+\gamma) I μ = ( − δ μ − γ , − δ μ + γ )
are pairwise disjoint and negative. Let P μ , n P_{\mu,n} P μ , n be the spectral projection of H n H_n H n onto I μ I_\mu I μ , and let U μ , n U_{\mu,n} U μ , n have columns V i , n / ∥ V i , n ∥ 2 V_{i,n}/\|V_{i,n}\|_2 V i , n /∥ V i , n ∥ 2 , i ∈ J μ i\in J_\mu i ∈ J μ . Proposition 7.2 gives
U μ , n T U μ , n ⟶ I m μ , ∥ ( H n + δ μ I ) U μ , n ∥ ⟶ 0. U_{\mu,n}^{\mathsf T}U_{\mu,n}\longrightarrow I_{m_\mu},\qquad\|(H_n+\delta_\mu I)U_{\mu,n}\|\longrightarrow0. U μ , n T U μ , n ⟶ I m μ , ∥ ( H n + δ μ I ) U μ , n ∥ ⟶ 0.
By the spectral theorem,
∥ ( I − P μ , n ) U μ , n ∥ ≤ γ − 1 ∥ ( H n + δ μ I ) U μ , n ∥ ⟶ 0. \|(I-P_{\mu,n})U_{\mu,n}\|\le\gamma^{-1}\|(H_n+\delta_\mu I)U_{\mu,n}\|\longrightarrow0. ∥ ( I − P μ , n ) U μ , n ∥ ≤ γ − 1 ∥ ( H n + δ μ I ) U μ , n ∥ ⟶ 0.
Consequently,
U μ , n T P μ , n U μ , n ⟶ I m μ , U_{\mu,n}^{\mathsf T}P_{\mu,n}U_{\mu,n}\longrightarrow I_{m_\mu}, U μ , n T P μ , n U μ , n ⟶ I m μ ,
so rank P μ , n ≥ m μ \operatorname{rank}P_{\mu,n}\ge m_\mu rank P μ , n ≥ m μ with probability tending to one. Choose ε > 0 \varepsilon> 0 ε > 0 so that every I μ I_\mu I μ lies below − ε -\varepsilon − ε . The negative-outlier bound of [12 Corollary 3.4] gives, with probability tending to one,
∑ μ rank P μ , n ≤ # { λ ∈ σ ( H n ) : λ < − ε } ≤ r + . \sum_\mu\operatorname{rank} P_{\mu,n} \le\#\{\lambda\in\sigma(H_n) : \lambda< -\varepsilon\} \le r_+. μ ∑ rank P μ , n ≤ # { λ ∈ σ ( H n ) : λ < − ε } ≤ r + .
Since ∑ μ m μ = r + \sum_\mu m_\mu= r_+ ∑ μ m μ = r + , we obtain rank P μ , n = m μ \operatorname{rank} P_{\mu,n} = m_\mu rank P μ , n = m μ for every μ \mu μ .
On this event, set
W μ , n = P μ , n U μ , n ( U μ , n T P μ , n U μ , n ) − 1 / 2 . W_{\mu,n} = P_{\mu,n}U_{\mu,n}\left(U_{\mu,n}^{\mathsf T}P_{\mu,n}U_{\mu,n}\right)^{-1/2}. W μ , n = P μ , n U μ , n ( U μ , n T P μ , n U μ , n ) − 1/2 .
Its columns form an orthonormal basis of the range of P μ , n P_{\mu,n} P μ , n , and
∥ W μ , n − U μ , n ∥ ⟶ 0. \lVert W_{\mu,n} - U_{\mu,n}\rVert\longrightarrow0. ∥ W μ , n − U μ , n ∥ ⟶ 0.
Moreover, since P μ , n P_{\mu,n} P μ , n commutes with H n H_n H n ,
( H n + δ μ I ) W μ , n = P μ , n ( H n + δ μ I ) U μ , n ( U μ , n T P μ , n U μ , n ) − 1 / 2 ⟶ 0. (H_n+\delta_\mu I)W_{\mu,n}
=
P_{\mu,n}(H_n+\delta_\mu I)U_{\mu,n}
\left(U_{\mu,n}^{\mathsf T}P_{\mu,n}U_{\mu,n}\right)^{-1/2}
\longrightarrow0. ( H n + δ μ I ) W μ , n = P μ , n ( H n + δ μ I ) U μ , n ( U μ , n T P μ , n U μ , n ) − 1/2 ⟶ 0.
Thus all eigenvalues in I μ I_\mu I μ converge to − δ μ -\delta_\mu − δ μ .
Choose an orthonormal eigenbasis ( v i , n ) i ∈ J μ (v_{i,n})_{i\in J_\mu} ( v i , n ) i ∈ J μ of the range of P μ , n P_{\mu,n} P μ , n . An orthogonal change of basis takes these vectors to the columns of W μ , n W_{\mu,n} W μ , n , giving the asserted approximation. The eigenvectors from distinct intervals are orthogonal. When m μ = 1 m_\mu=1 m μ = 1 , the change of basis is simply a choice of sign.
Proof of Theorem 2.2 . Take t = d t=\sqrt{d} t = d . Proposition 4.9 gives the deterministic strictly increasing function δ \delta δ . Proposition 7.3 gives the outliers associated with each positive informative eigenvalue, with the correct multiplicities. The outlier count used in its proof shows that these are the first r + r_+ r + eigenvalues of H ( t , G n ) H(t,G_n) H ( t , G n ) . Their ordering follows from the strict increase of δ \delta δ .
For a negative planted eigenvalue μ < − t \mu<-t μ < − t , take δ = δ ( ∣ μ ∣ ) \delta=\delta(|\mu|) δ = δ ( ∣ μ ∣ ) . In the boundary-message and vertex-field constructions, use − Γ δ -\Gamma_\delta − Γ δ in place of Γ δ \Gamma_\delta Γ δ and − t -t − t in place of t t t . The denominator in the vertex-field formula is unchanged. Since ρ = μ / d < 0 \rho=\mu/d<0 ρ = μ / d < 0 , the conditional mean is propagated by
ρ ( − L δ ) = ∣ ρ ∣ L δ . \rho(-\mathcal{L}_\delta)=|\rho|\mathcal{L}_\delta. ρ ( − L δ ) = ∣ ρ ∣ L δ .
The same convergence estimates apply, and the resulting field satisfies
( H ( − t , T ) + δ I ) V = 0. (H(-t,T)+\delta I)V=0. ( H ( − t , T ) + δ I ) V = 0.
The local approximation, finite convergence, and corresponding negative-outlier count therefore give the asserted eigenvalue limits for H ( − t , G n ) H(-t,G_n) H ( − t , G n ) .
It remains to verify the overlap assertion. For either sign, write δ i = δ ( ∣ μ i ∣ ) \delta_i=\delta(|\mu_i|) δ i = δ ( ∣ μ i ∣ ) , and let Γ i \Gamma_i Γ i and h i h_i h i be the positive cavity weight and transfer eigenfunction at this shift. If K K K is the root degree and T 1 , … , T K T_1,\ldots,T_K T 1 , … , T K are its forward subtrees, taking conditional expectations in the vertex-field formula gives
a i = t ∣ μ i ∣ d E [ ∑ j = 1 K h i ( T j ) t 2 + K − 1 + δ i − t ∑ j = 1 K Γ i ( T j ) ] > 0. a_i=\frac{t|\mu_i|}{d}\mathbb{E}\left[\frac{\sum_{j=1}^{K}h_i(T_j)}{t^2+K-1+\delta_i-t\sum_{j=1}^{K}\Gamma_i(T_j)}\right]>0. a i = d t ∣ μ i ∣ E [ t 2 + K − 1 + δ i − t ∑ j = 1 K Γ i ( T j ) ∑ j = 1 K h i ( T j ) ] > 0.
The denominator is positive, and the numerator is positive whenever a forward subtree survives, by Proposition 4.8 . Thus a i > 0 a_i>0 a i > 0 , and Cauchy–Schwarz also gives s i ≥ a i > 0 s_i\ge a_i>0 s i ≥ a i > 0 .
Fix a distinct informative eigenvalue μ \mu μ and write J μ = { i : μ i = μ } J_\mu=\{i:\mu_i=\mu\} J μ = { i : μ i = μ } . Let ( w i , n ) i ∈ J μ (w_{i,n})_{i\in J_\mu} ( w i , n ) i ∈ J μ be the orthonormal basis of its outlier subspace constructed in Proposition 7.3 . By Proposition 7.2 ,
( ⟨ w i , n , X j ⟩ n ) i , j ∈ J μ → P diag ( a i / s i : i ∈ J μ ) . \left(\frac{\langle w_{i,n},X_j\rangle}{\sqrt{n}}\right)_{i,j\in J_\mu}\xrightarrow{\mathbb{P}}\operatorname{diag}(a_i/s_i:i\in J_\mu). ( n ⟨ w i , n , X j ⟩ ) i , j ∈ J μ P diag ( a i / s i : i ∈ J μ ) .
Consequently, with probability tending to one, the smallest singular value of this matrix is at least
c μ = 1 2 min i ∈ J μ a i s i > 0. c_\mu=\frac{1}{2}\min_{i\in J_\mu}\frac{a_i}{s_i}>0. c μ = 2 1 i ∈ J μ min s i a i > 0.
Since the vectors X i / n X_i/\sqrt{n} X i / n are orthonormal, this is precisely the claimed lower bound on the projection of every planted vector onto the outlier subspace. When μ i \mu_i μ i is simple, the preceding convergence gives (4) with q μ i = a i / s i > 0 q_{\mu_i}=a_i/s_i>0 q μ i = a i / s i > 0 .
Weak recovery
Given our convergence to nontrivial eigenvectors, we use standard arguments to perform weak recovery.
Proof of Theorem 2.3 . Let S : = ∑ μ i > d , i ≥ 2 c μ i 2 S:=\sum_{\mu_i>\sqrt{d},\,i\geq2}c_{\mu_i}^2 S := ∑ μ i > d , i ≥ 2 c μ i 2 . If S = 0 S=0 S = 0 we are done. Suppose S > 0 S>0 S > 0 , and let
m = ∣ { i ≥ 2 : ∣ μ i ∣ > d } ∣ . m=\left|\left\{i\geq2:|\mu_i|>\sqrt{d}\right\}\right|. m = { i ≥ 2 : ∣ μ i ∣ > d } .
Let E n E_n E n be the sum of all informative outlier subspaces of H ( d , G n ) H(\sqrt{d},G_n) H ( d , G n ) and H ( − d , G n ) H(-\sqrt{d},G_n) H ( − d , G n ) . Choose an orthonormal basis U n ∈ R n × m U_n\in\mathbb{R}^{n\times m} U n ∈ R n × m of E n ∩ 1 ⊥ E_n\cap\mathbf{1}^{\perp} E n ∩ 1 ⊥ , and write
x u : = n U n ( u , ⋅ ) T . x_u:=\sqrt{n}U_n(u,\cdot)^{\mathsf{T}}. x u := n U n ( u , ⋅ ) T .
The joint limits in Propositions 7.2 and 7.3 give
∑ i ≥ 2 ∣ μ i ∣ > d ∥ U n T X i n ∥ 2 2 ≥ S − o P ( 1 ) . \sum_{\substack{i\geq2\\|\mu_i|>\sqrt{d}}}\left\|\frac{U_n^{\mathsf{T}}X_i}{\sqrt{n}}\right\|_2^2\geq S-o_{\mathbb{P}}(1). i ≥ 2 ∣ μ i ∣ > d ∑ n U n T X i 2 2 ≥ S − o P ( 1 ) .
Indeed, the combined outlier basis has a diagonal limiting correlation matrix with the planted directions. Intersecting with 1 ⊥ \mathbf{1}^{\perp} 1 ⊥ removes only the constant planted direction asymptotically, including when d d d has multiplicity greater than one.
Put
L : = π min S , M : = 4 2 ( r − 1 ) L , f u : = x u max { M , ∥ x u ∥ 2 } . L:=\sqrt{\pi_{\min}S},\qquad M:=\frac{4\sqrt{2}(r-1)}{L},\qquad f_u:=\frac{x_u}{\max\{M,\|x_u\|_2\}}. L := π m i n S , M := L 4 2 ( r − 1 ) , f u := max { M , ∥ x u ∥ 2 } x u .
Fix any matrix R ∈ R r × m R\in\mathbb{R}^{r\times m} R ∈ R r × m satisfying R T R = I m R^{\mathsf{T}}R=I_m R T R = I m and R T 1 = 0 R^{\mathsf{T}}\mathbf{1}=0 R T 1 = 0 . Independently over vertices, sample
P ( σ ^ n ( u ) = b ∣ G n ) = 1 + ( R f u ) b r , b ∈ [ r ] . \mathbb{P}(\widehat{\sigma}_n(u)=b\mid G_n)=\frac{1+(Rf_u)_b}{r},\qquad b\in[r]. P ( σ n ( u ) = b ∣ G n ) = r 1 + ( R f u ) b , b ∈ [ r ] .
These are valid probabilities because ∥ f u ∥ 2 ≤ 1 \|f_u\|_2\leq1 ∥ f u ∥ 2 ≤ 1 .
To bound the overlap, define
C n = 1 n ∑ u ( e σ ( u ) − π ) x u T , C f , n = 1 n ∑ u ( e σ ( u ) − π ) f u T . C_n=\frac{1}{n}\sum_u(e_{\sigma(u)}-\pi)x_u^{\mathsf T},\qquad C_{f,n}=\frac{1}{n}\sum_u(e_{\sigma(u)}-\pi)f_u^{\mathsf T}. C n = n 1 u ∑ ( e σ ( u ) − π ) x u T , C f , n = n 1 u ∑ ( e σ ( u ) − π ) f u T .
where e a e_a e a is the a a a th coordinate vector. Orthonormality of the planted eigenfunctions gives
∥ C n ∥ F 2 ≥ π min ∑ i ≥ 2 ∣ μ i ∣ > d ∥ U n T X i n ∥ 2 2 . \lVert C_n\rVert_F^2\ge\pi_{\min}\sum_{\substack{i\ge2\\ \lvert\mu_i\rvert>\sqrt d}}\left\lVert\frac{U_n^{\mathsf T}X_i}{\sqrt n}\right\rVert_2^2. ∥ C n ∥ F 2 ≥ π m i n i ≥ 2 ∣ μ i ∣ > d ∑ n U n T X i 2 2 .
Thus ∥ C n ∥ F ≥ L / 2 \lVert C_n\rVert_F\ge L/2 ∥ C n ∥ F ≥ L /2 with probability tending to one. Since n − 1 ∑ u ∥ x u ∥ 2 2 = m n^{-1}\sum_u\lVert x_u\rVert_2^2=m n − 1 ∑ u ∥ x u ∥ 2 2 = m ,
∥ M C f , n − C n ∥ F ≤ 2 M n ∑ u ∥ x u ∥ 2 2 ≤ L 4 . \lVert MC_{f,n}-C_n\rVert_F\le\frac{\sqrt{2}}{Mn}\sum_u\lVert x_u\rVert_2^2\le\frac{L}{4}. ∥ M C f , n − C n ∥ F ≤ M n 2 u ∑ ∥ x u ∥ 2 2 ≤ 4 L .
Consequently,
∥ C f , n ∥ F ≥ L 4 M \lVert C_{f,n}\rVert_F\ge\frac{L}{4M} ∥ C f , n ∥ F ≥ 4 M L
with probability tending to one.
Condition on G n G_n G n and σ \sigma σ . The expected centered confusion matrix is
D n : = 1 r C f , n R . D_n:=\frac{1}{r}C_{f,n}R. D n := r 1 C f , n R .
It has zero row and column sums, and ∥ D n ∥ F = ∥ C f , n ∥ F / r \lVert D_n\rVert_F=\lVert C_{f,n}\rVert_F/r ∥ D n ∥ F = ∥ C f , n ∥ F / r . For any such nonzero matrix D D D ,
max τ ∈ S r ∑ b D τ ( b ) , b ≥ ∥ D ∥ F r . \max_{\tau\in S_r}\sum_b D_{\tau(b),b}\ge\frac{\lVert D\rVert_F}{r}. τ ∈ S r max b ∑ D τ ( b ) , b ≥ r ∥ D ∥ F .
Indeed, 1 1 T / r + D / ( r ∥ D ∥ F ) \boldsymbol{1}\boldsymbol{1}^{\mathsf T}/r+D/(r\lVert D\rVert_F) 1 1 T / r + D / ( r ∥ D ∥ F ) is doubly stochastic, so the inequality follows from Birkhoff’s theorem.
It follows that some permutation has conditional expected centered overlap at least
L 4 M r 2 = π min S 16 2 r 2 ( r − 1 ) . \frac{L}{4Mr^2}=\frac{\pi_{\min}S}{16\sqrt{2}r^2(r-1)}. 4 M r 2 L = 16 2 r 2 ( r − 1 ) π m i n S .
Conditional independence and Hoeffding’s inequality now give the claimed bound. When S = 0 S=0 S = 0 , the conclusion is immediate, since centered overlap is always nonnegative.