# Learning Sparse Graphons and the Generalized Kesten-Stigum Threshold

Emmanuel Abbe 111EPFL and Princeton University Shuangping Li 222Princeton
University Allan Sly 333Princeton University

###### Abstract

The problem of learning graphons has attracted considerable attention across
several scientific communities, with significant progress over the recent
years in sparser regimes. Yet, the current techniques still require diverging
degrees in order to succeed with efficient algorithms in the challenging cases
where the local structure of the graph is homogeneous. This paper provides an
efficient algorithm to learn graphons in the constant expected degree regime.
The algorithm is shown to succeed in estimating the rank-$k$ projection of a
graphon in the $L_{2}$ metric if the top $k$ eigenvalues of the graphon
satisfy a generalized Kesten-Stigum condition.

##  1 Introduction

The problem of estimating graphons has been extensively studied in the
statistics, mathematics, machine learning and network science literature [20,
33, 22, 25, 18, 15, 6, 30, 10, 11, 24, 31, 4, 28, 34, 7, 35, 9, 8, 36, 5, 21].
The term graphon is used here to designate the non-parametric function that
governs the edge probabilities in an inhomogeneous or exchangeable random
graph model. Namely, for a nonnegative symmetric measurable function $f$ on
$[0,1]\times[0,1]$, a random graph $G=([n],E)$ is drawn by generating
$X_{1},\cdots,X_{n}$ i.i.d. Uniform on $[0,1]$, and by drawing the edges in
$E$ independently conditionally on $X_{1},\cdots,X_{n}$ such that

$\displaystyle\mathbb{P}(E_{ij}=1|X_{1}=x_{1},\cdots,X_{n}=x_{n})=\mathbb{P}(E_{ij}=1|X_{i}=x_{i},X_{j}=x_{j})=f(x_{i},x_{j}).$
(1)

The original works focused on the regime where the function $f$ is constant
(i.e., not decaying with $n$), called the dense regime, which corresponds to
the regime where the graphon admits a topological interpretation in terms of
graph limits [16, 17]. The “sparse graphon” setting has been used to refer to
the case where

$\displaystyle f=f_{n}=\rho_{n}Q,\quad Q:[0,1]\times[0,1]\to\mathbb{R}_{+},$
(2)

where $\rho_{n}$ is called the scale parameter or sparsity parameter, as it
can be thought of as the probability with which one keeps edges independently
in the graph (deleting others). A special case of interest is when the
function $Q$ is piecewise constant, i.e,. stochastic block models (SBMs) [23,
19, 29, 13, 12, 3], in which case the function $Q$ is equivalently defined by
a $k\times k$ symmetric matrix where $k$ is the number of flats in $Q$.

The main question studied in the context of ‘learning’ or ‘estimating’
graphons at a scale $\rho_{n}$ is to estimate $Q$ up to some level of
accuracy444E.g., in the $L_{2}$ metric and up to measure preserving maps.
given a single sample of the random graph $G$.

Most of the papers focus on the regime where $\rho_{n}=d_{n}/n$ with diverging
degrees $d_{n}$, and in particular on the statistical point of view, i.e.,
obtaining consistent estimators for $Q$ (up to measure-preserving maps) and
convergence rates, without taking necessarily the computational efficiency
into consideration. In particular, this is investigated by [20] for SBMs and
by [33, 22] under Hölder smoothness assumption and also SBMs, where [33] shows
the consistency and convergence rate of the maximum likelihood estimator in
the regime where $\rho_{n}=\log^{3}(n)/n$. [22] also considers Hölder
smoothness and SBMs and shows that a histogram approximation with least
squares criterion achieves an optimal rate of convergence in the dense case
where $\rho_{n}=1$. These results are further extended and improved in [25],
which obtains oracle inequalities for the moderately sparse regime where
$\log(k)/n\wedge(k/n)^{2}\leq\rho_{n}\leq\log(k)/{\sqrt{kn}}\wedge(k/n)^{3/2}$,
where $k$ is the number of blocks for the block constant oracle. A similar
result is also obtained in [18] for the case where the degrees diverge, with
in addition a node-differentially private procedure to estimate the graphon.
Further, [15] manages to remove the boundedness assumption when studying the
least-square estimator for arbitrary integrable graphons with possibly long
tails in their degree distribution (and more general latent spaces), showing
also that the efficient algorithm based on degree sorting works whenever the
underlying degree distribution is atomless. Finally, some papers show that in
regimes of diverging degrees and diverging signal-to-noise ratio, it is
possible to estimate efficiently and consistently the SBM parameters for two
communities [8], certain degree-corrected SBMs [36], and any identifiable SBM
with diverging degrees and a finite number of communities [6].

To the best of our knowledge, none of the above approaches either work or have
been proved to succeed in non-trivial cases where $\rho_{n}=1/n$, in
particular for efficient algorithms. There are a few exceptions to that. In
[11], it is shown that for SBMs with different expected degrees across
communities, it is possible to estimate the parameters of the graph using
moments. This is however a regime where the local structure of the graph is
non-homogeneous, i.e., dependent on the community membership, and where moment
methods can be applied directly (see Section 2 for further discussion). A new
line of work has then been initiated in the homogeneous case, where the
expected degrees are both constant in magnitude and across communities. In
this case, [30] shows that the parameters can be estimated for the special
case of two symmetric communities, extended in [5] for $k$ symmetric
communities, as long as the model parameters are above the so-called Kesten-
Stigum threshold (see Section 2). In particular, this is the regime subject to
a sharp phase transition phenomenon since below the KS threshold, [30] shows
that a consistent estimator cannot be obtained for two symmetric communities.
A similar picture is conjectured for SBMs with several symmetric communities
[21], although it was shown in [5] that non-efficient estimators could be
devised below the KS threshold starting from 4 communities. More generally,
the question of estimating SBMs in the constant-degree regime with general
(non-symmetric) $Q$’s remained open in this line of work, let alone the case
of non-piecewise constant graphons.

This paper tackles this open problem, providing an efficient algorithm to
learn constant-degree graphons (and SBMs) under a generalized KS threshold
condition. We next describe the results and algorithm.

##  2 Main Results

Because we have no information about the vertex indices, we can only hope to
learn the graphon $Q$ up to a measure preserving map. The following is a
classical distance used in this context.

######  Definition 2.1.

Let $\phi:[0,1]\rightarrow[0,1]$ be a measure preserving map, and for a
function $W$ on $[0,1]\times[0,1]$, define $W^{\phi}(x,y)=W(\phi(x),\phi(y))$.
We define the distance
$\delta_{2}(W,W^{\prime})=\inf\limits_{\phi_{1},\phi_{2}}\|W^{\phi_{1}}-W^{\prime\phi_{2}}\|_{2}$,
where we take the infimum over measure-preserving maps
$\phi_{i}:[0,1]\rightarrow[0,1]$, $i=1,2$.

To formulate our theorem, we make the following assumptions.

Assumption 1. The graphon $Q$ is bounded, i.e., we assume that
$M:=\sup\limits_{(x,y)\in[0,1]^{2}}|Q(x,y)|$ is finite.

Since $Q$ is bounded and symmetric, it admits an eigenvalue decomposition. We
denote the eigenvalues in a descending order in absolute value:
$\mu_{1}\geq|\mu_{2}|\geq|\mu_{3}|\geq\cdots$. Let $f_{i}$ be the
corresponding eigenfunctions. Denote $Q_{K}$ to be a rank $K$ approximation of
$Q$. In particular, $Q_{K}(x,y)=\sum\limits_{i=1}^{K}\mu_{i}f_{i}(x)f_{i}(y)$
is unique when $\mu_{K}\neq\mu_{K+1}$.

Assumption 2. We assume that $\int_{0}^{1}Q(x,y)dy$ takes the same constant
value $q$ for every $x\in[0,1]$. This is the constant expected degree
condition.

We are now ready to present our results.

######  Theorem 2.1.

Let $Q$ satisfy Assumptions $1$ and $2$, let $r_{0}$ be such that
$|\mu_{r_{0}}|>\sqrt{\mu_{1}}\geq|\mu_{r_{0}+1}|$, and assume that $\mu_{i}$
is simple for all $i\in[r_{0}]$. Then Algorithm $1$ produces an estimator
$\hat{Q}$ such that555We use $\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}$
for the convergence in probability as $n\to\infty$.

$\displaystyle\delta_{2}(\hat{Q},Q_{r_{0}})\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}0.$

In other words, if there are $r_{0}$ eigenvalues that lie outside the
graphon’s bulk and are simple, one can estimate efficiently and consistently
the rank-$r_{0}$ projection of the graphon.

######  Remark.

Algorithm 1 runs with high probability in time $O(n\log n)$.

######  Corollary 2.1.

Let $Q$ be low-rank and satisfy Assumptions $1$ and $2$. Assume that all
nonzero $\mu_{i}$’s are simple and satisfy $|\mu_{i}|>\sqrt{\mu_{1}}$. Then
Algorithm $1$ produces an estimator $\hat{Q}$ such that

$\displaystyle\delta_{2}(\hat{Q},Q)\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}0.$

In other words, for a low-rank graphon $Q$, if all nonzero eigenvalues lie
outside of the graphon’s bulk and are simple, one can estimate $Q$ efficiently
and consistently. In particular, this holds for constant expected degree
stochastic block model when all nonzero eigenvalues are simple and satisfy
$|\mu_{i}|>\sqrt{\mu_{1}}$.

For a graphon $Q$, and $h\in\mathbb{R}^{+}$, we define $\mathcal{Q}_{h}$ to be
a scaled graphon such that $\mathcal{Q}_{h}(x,y)=h\cdot Q(x,y)$.

######  Corollary 2.2.

Let $Q$ satisfy Assumptions $1$ and $2$ and assume that all nonzero
$\mu_{i}$’s are simple. Then Algorithm $1$ produces an estimator
$\widehat{\mathcal{Q}_{h}}$ such that

$\displaystyle\delta_{2}(\frac{1}{h}\widehat{\mathcal{Q}_{h}},Q)\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}o_{h}(1).$

Discussions of assumptions. The condition $\int_{0}^{1}Q(x,y)dy=q$ means that
the random graph $G$ has a constant expected degree. This has been the most
challenging regime in learning or community detection problems because in this
case, degree of vertices or any simple acyclic subgraph counts yield no
information towards communities. Moreover, the Benjamini-Schramm limit of the
graph is a Galton-Watson branching process independent of the vertex label at
the root.

For a low rank graphon $Q$, the assumption that all nonzero eigenvalues
satisfy $|\mu_{i}|>\sqrt{\mu_{1}}$ is a natural generalization of the Kesten-
Stigum condition that requires a single eigenvalue to satisfy this inequality.
First studied in the context of multi-type branching processes, it has played
a central role in the study of the SBM. In particular in the symmetric 2-block
cases it determines the threshold for consistent estimation of the model and
for weakly recovering the communities. The threshold is equivalent to the
eigenvalues of the non-backtracking matrix lying outside the bulk spectrum.

For the assumption of the simple eigenvalues, we believe that our algorithm
can still generate a good estimator even if the eigenvalues are not simple. We
have the assumption here for technical purposes. Proving the more general
results requires more detailed analysis of the non-backtracking matrix.

##  3 Algorithm

Our algorithm makes use of the non-backtracking matrix $B$. The matrix has
been used in various network problems including community detection of
stochastic block models [27, 14]. The non-backtracking walk on a graph avoids
returning to the vertex visited in the previous step, and can be viewed as the
operator resulting from a linearization of the belief propagation algorithm
[27, 1]. This additional requirement of ‘non-backtracking’ makes its spectrum
behave well: in certain sparse cases, when $\rho_{n}=O(1/n)$, top eigenvalues
of $B$ approximate top eigenvalues of $Q$. This is in contrast to the top
eigenvectors of the adjacency matrix that concentrate around high degree
vertices in the sparse regime, and top eigenvalue of order $(\log n/\log\log
n)^{1/2}$ [26]. Therefore classical spectral clustering algorithms using the
adjacency matrix are not helpful in the sparse regime. In our problem, the
non-backtracking matrix $B$ will be important in approximating eigenvalues and
extracting moments of the eigenfunctions of $Q$. For a graph $G=(V,E)$, the
non-backtracking matrix is indexed by the set of oriented edges
$\vec{E}=\\{(u,v):\\{u,v\\}\in E\\}$, where each entry equals

$\displaystyle B_{ef}=\mathbbm{1}(e_{2}=f_{1})\mathbbm{1}(e_{1}\neq
f_{2})=\mathbbm{1}(e_{2}=f_{1})\mathbbm{1}(e\neq f^{-1}).$

Here for any $e=(u,v)\in\vec{E}$, we define $e_{1}=u$, $e_{2}=v$,
$e^{-1}=(v,u)$. We define $\lambda_{k}$ to be the $k$-th eigenvalue of $B$ and
$\xi_{k}$ to be the $k$-th normalized eigenvector of $B$. We order eigenvalues
in descending order in magnitude and define $B_{k}(v)=\sum\limits_{e\in
E_{1}:e_{2}=v}\xi_{k}(e)$.

Our algorithm consists of several steps:
1\. We compute top eigenvalues of the non-backtracking matrix $B$. We then
determine the approximate number of eigenvalues that have a magnitude larger
than $\sqrt{\lambda_{1}}$. We call this number $K$.
2\. We extract joint moments of $f_{i}$ through subgraph counts. For a vector
$(i_{1},\cdots,i_{k})\in[K]^{k}$, we count a weighted sum of $k$-leaves stars
in $G$, where the weight of each star is defined as
$\prod_{j=1}^{k}B_{i_{j}}(v_{j})$, where $v_{i}$ are leaves. This gives us an
estimate of $\int_{[0,1]}f_{i_{1}}(x)\cdots f_{i_{k}}(x)dx$.
3\. We consider the random variables $f_{1}(U),\cdots,f_{K}(U)$ where $U$ is
Uniform on $[0,1]$. We use Lengendre polynomials to approximate their joint
distribution function and compute the coefficients of the polynomials to match
up the moment information from step 2.
4\. We sample according to the approximated joint distribution of
$f_{1}(U),\cdots,f_{K}(U)$. From there we obtain a piecewise constant
approximation of $Q$.

Some Discussions. In our algorithm, we utilize the spectrum of the non-
backtracking matrix to approximate eigenvalues of $Q$. There are actually a
few other ways to do this. One of them is using cycle counts similarly to
[30], but stabilizing the counts to account for the different magnitudes of
eigenvalues as in [2]. We use here the spectrum of $B$ in our algorithm
because we can get good controls of the error terms and because we anyway need
eigenvectors of $B$.

To see why the subgraph counts gives us an estimate of the moment, we consider
the inner product $\mathcal{C}_{ij}:=\sum_{v\in
V}\frac{1}{\sqrt{n}}B_{i}(v)f_{j}(X_{v})$. We will show that
$\mathcal{C}_{ij}$ is asymptotically $\delta_{ij}$ after some normalization.
We define $Q^{X}$ as the matrix such that $Q^{X}(u,v)=Q(X_{u},X_{v})$. Let
$Q^{X}_{u}$ be the $u$-th column vector of $Q^{X}$. Similarly we define
$f_{i}^{X}$ as the vector such that $f_{i}^{X}(v)=f_{i}(X_{v})$. So the sum of
$k$-leaf stars with weight $\prod_{j=1}^{k}B_{i_{j}}(v_{j})$ is approximately

$\displaystyle\sum_{u\in
V}\prod_{j=1}^{k}B_{i_{j}}^{t}\frac{Q^{X}_{u}}{n}=n^{-k/2}\sum_{u\in
V}\prod_{j=1}^{k}\frac{B_{i_{j}}^{t}}{\sqrt{n}}\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}^{X}f_{\ell}^{X}(u)\approx
Cn^{-k/2}\sum_{u\in V}\prod_{j=1}^{k}\mu_{i_{j}}f_{i_{j}}(X_{u})$
$\displaystyle\approx
Cn^{-k/2+1}\prod_{j=1}^{k}\mu_{i_{j}}\int_{[0,1]}f_{i_{1}}\cdots f_{i_{k}}dx.$

This allows us to estimate the joint moments of eigenfunctions of $Q$.

We pick Legendre polynomials to approximate our functions because they work
well in modelling bounded support functions. See [32] for a one dimensional
example of estimating functions with given moments. In our polynomial
approximation step, there is one caveat in the computation. The joint
distribution of $(f_{1}(U),\cdots,f_{K}(U))$ is degenerate: it is supported on
a one dimensional curve. So we convolve it with a mollifier to make the
distribution function well-defined on $\mathbb{R}^{K}$ and smooth. When the
mollifier is small enough, the convolved distribution approximates the
original function well.

In the following chart, we summarize our algorithm steps. We use $e_{0}$ to
denote the error tolerance, i.e., with probability tending to $1$,
$\delta_{2}(\hat{Q}-Q_{r_{0}})\leq e_{0}$ as $n$ goes to infinity.

Algorithm 1 Sparse Graphon Estimation

1:$G$ (graph), $e_{0}>0$ (error tolerance), $M>0$ (bound on $Q$)

2:$\hat{Q}$ (estimator)

3:$\epsilon\leftarrow\frac{1}{\log(\log(n))}$

4:function Sample_Splitting($\epsilon$,$E$)

5: return $E_{1}$,$E_{2}$

6:end function

7:

8:function Non_Backtracking_Matrix($V,E_{1}$)

9: return $K,\lambda_{1},\cdots,\lambda_{K}$, $B_{1}\cdots,B_{K}$

10:end function

11:

12:$N\leftarrow(\frac{2KM}{e_{0}})^{6K+30}$

13:function
Sub_Graph_Count($E_{2},K,\lambda_{1},\cdots,\lambda_{K},B_{1}\cdots,B_{K},N$)

14: return $P_{\alpha}$ ($0\leq\alpha\leq\mathbf{N}$)

15:end function

16:

17:$\delta\leftarrow\sqrt{\frac{e_{0}}{64K\lambda_{1}M^{2}}}$

18:function Polynomial_Approximation($P_{\alpha},\delta,N$)

19: return $\hat{h}_{N}^{+}$

20:end function

21:

22:function
Graphon_Estimation($\hat{h}_{N}^{+},K,\lambda_{1},\cdots,\lambda_{K}$)

23: return $\hat{Q}$

24:end function

The following are detailed definitions of the functions.

Function Sample_Splitting($\epsilon$,$E$)
For each edge $e\in E$, mutually independently, with probability $1-\epsilon$,
we assign it into $E_{1}$. Assign all the remaining edges to
$E_{2}=E\backslash E_{1}$. We define $G_{1}=(V,E_{1})$ and $G_{2}=(V,E_{2})$.

Function Non_Backtracking_Matrix($V,E_{1}$)
We compute the non-backtracking matrix of $G_{1}$, call it $B$. Take
$e_{1}(n)=\frac{1}{\sqrt{\log n}}$. Define $K\in\mathbb{Z}_{+}$ to be such
that $|\lambda_{i}|>\sqrt{\lambda_{1}}+e_{1}(n)$ for all $i\in[K]$ and
$|\lambda_{K+1}|\leq\sqrt{\lambda_{1}}+e_{1}(n)$. We compute eigenvalues
$\lambda_{k}$ of $B$ in a descending order of magnitude, until we reach
$\lambda_{K}$. Compute the corresponding eigenvectors $\xi_{k}$. For
$k\in[K]$, compute $B_{k}(v)=\sum\limits_{e\in E_{1}:e_{2}=v}\xi_{k}(e)$.

Function
Sub_Graph_Count($E_{2},K,\lambda_{1},\cdots,\lambda_{K},B_{1}\cdots,B_{K},N$)
For $1\leq i,j\leq n$, we write $i\sim j$ whenever there is an edge in $E_{2}$
that connects $i$ and $j$. For $k\in[K]$, define

$\displaystyle A_{kk}:=\sum\limits_{1\leq i,j\leq
n}B_{k}(i)B_{k}(j)\mathbbm{1}[i\sim j],$ $\displaystyle
P_{kk}:=\frac{A_{kk}}{\epsilon\lambda_{k}}.$

For any multi-index $\alpha\in\mathbb{N}^{K}$, i.e.
$\alpha=(\alpha_{1},\alpha_{2},\cdots,\alpha_{K})$, where each
$\alpha_{i}\in\mathbb{N}$, we define $|\alpha|=\sum_{i=1}^{K}\alpha_{i}$. We
use $[n]^{k}_{\leq}$ to denote the set consisting of all ordered $k$-tuples
from the set $[n]$. More precisely, we define

$\displaystyle[n]^{k}_{\leq}=\\{(i_{1},\cdots,i_{k})\in[n]^{k}:1\leq
i_{1}\leq\cdots\leq i_{k}\leq n\\}.$

For a multi-index $\alpha$, we define
$I^{\alpha}=(I^{\alpha}_{1},\cdots,I^{\alpha}_{|\alpha|})\in[K]^{|\alpha|}_{\leq}$
such that $|\\{1\leq j\leq|\alpha|:I^{\alpha}_{j}=i\\}|=\alpha_{i}$ for any
$1\leq i\leq K$. We define

$\displaystyle A_{\alpha}:=\sum_{1\leq i_{1},\cdots,i_{|\alpha|},w\leq
n}\prod_{\ell=1}^{|\alpha|}B_{I^{\alpha}_{\ell}}(i_{\ell})\mathbbm{1}[i_{\ell}\sim
w],$

where all $i_{\ell}$ are disjoint. Define

$\displaystyle
P_{\alpha}:=\frac{A_{\alpha}n^{|\alpha|/2-1}}{\epsilon^{|\alpha|}\prod_{i=1}^{K}(\sqrt{P_{ii}}\lambda_{i})^{\alpha_{i}}},$

when $P_{ii}>0$, for all $i\in[K]$. Otherwise, set all $P_{\alpha}=0$. Define
a multi-index $\mathbf{N}=(N,N,\cdots,N).$ For any multi-index
$0\leq\alpha\leq\mathbf{N}$, we compute $P_{\alpha}$.

Function Polynomial_Approximation($P_{\alpha},\delta,N$)
We use the following bump function as our mollifier. Define a bump function
$\Psi_{\delta}:\mathbb{R}\rightarrow\mathbb{R}$ to be

$\displaystyle\Psi_{\delta}(x)=\begin{cases}\exp(-\frac{1}{\delta^{2}-x^{2}}),&x\in(-\delta,\delta)\\\
0,&\text{otherwise}.\end{cases}$

For any multi-index $0\leq\alpha\leq\mathbf{N}$, we compute

$\displaystyle
M_{\alpha}(\delta)=\sum\limits_{0\leq\beta\leq\alpha}P_{\beta}\prod_{i=1}^{K}{\alpha_{i}\choose\beta_{i}}\mathbb{E}[N_{\delta}^{\alpha_{i}-\beta_{i}}],$

where $N_{\delta}$ is a random variable whose density function is proportional
to $\Psi_{\delta}(x)$.

We use Legendre polynomials to approximate our mollified distribution. Let
$L_{0}(x),L_{1}(x),\cdots,L_{i}(x),\cdots$ be Legendre polynomials, normalized
by $\int_{-1}^{1}(L_{i}(x))^{2}dx=1$. Recall that these polynomials are
defined uniquely (apart from sign) by the following requirements:

$\displaystyle L_{i}(x)\text{ is a polynomial }$ $\displaystyle
deg(L_{i}(x))=i$ $\displaystyle\int_{-1}^{1}L_{i}(x)L_{j}(x)dx=\delta_{ij}.$

We also define Legendre polynomials in dimension $K$ as follows. For a multi-
index $\alpha$, define

$\displaystyle
L_{\alpha}(x_{1},\cdots,x_{K})=\prod_{i=1}^{K}L_{\alpha_{i}}(x_{i}).$

They are polynomials of degree $|\alpha|$ and satisfy

$\displaystyle\int_{[-1,1]^{K}}L_{\alpha}(x_{1},\cdots,x_{K})L_{\beta}(x_{1},\cdots,x_{K})d\mathbf{x}=\delta_{\alpha,\beta}.$

Define $C_{ij}$ to be the coefficients of Legendre polynomials:

$\displaystyle\sum\limits_{j=0}^{i}C_{ij}x^{j}=L_{i}(x).$

Define $C^{\otimes K}$ to be the Kronecker product of $K$ copies of $C$, i.e.,
$C^{\otimes K}_{\alpha,\beta}=\prod_{i=1}^{K}C_{\alpha_{i},\beta_{i}}$. Now,
we consider scaled Legendre polynomials on
$[-\frac{2M}{\sqrt{\lambda_{1}}},\frac{2M}{\sqrt{\lambda_{1}}}]$, satisfying
the same conditions as above except the integration is over
$[-\frac{2M}{\sqrt{\lambda_{1}}},\frac{2M}{\sqrt{\lambda_{1}}}]$. Denote them
as $\tilde{L}$. Write $\kappa=\frac{2M}{\sqrt{\lambda_{1}}}$. Then,

$\displaystyle\tilde{L}_{\alpha}(x_{1},\cdots,x_{K})=\frac{1}{\kappa^{K/2}}L_{\alpha}(x_{1}/\kappa,\cdots,x_{K}/\kappa).$

Define $\tilde{C}$ such that $\tilde{C}_{ij}=C_{ij}/\kappa^{j+1/2}$. Define
$\tilde{C}^{\otimes K}$ to be the Kronecker product of $K$ copies of
$\tilde{C}$. Now we compute

$\displaystyle\hat{\rho}_{\alpha}(\delta)=\sum\limits_{0\leq\beta\leq\alpha}\tilde{C}^{\otimes
K}_{\beta}M_{\beta}(\delta).$

Finally, for a given $N\in\mathbb{N}_{+}$, compute

$\displaystyle\hat{h}_{N}(x_{1},\cdots,x_{K})=\sum\limits_{0\leq\alpha\leq\mathbf{N}}\hat{\rho}_{\alpha}(\delta)\tilde{L}_{\alpha}(x_{1},\cdots,x_{K}).$

Define $\hat{h}_{N}^{+}:=\hat{h}_{N}\mathbbm{1}[\hat{h}_{N}\geq 0]$.

Function
Graphon_Estimation($\hat{h}_{N}^{+},K,\lambda_{1},\cdots,\lambda_{K}$)
Take $m=n$. We sample vectors $Z_{1},\cdots,Z_{m}$ from a distribution
proportional to $\hat{h}_{N}^{+}$ mutually independently. For any $1\leq i\leq
K$, compute

$\displaystyle\hat{f}_{i}(x)=Z_{\lceil xm\rceil}(i).$

We compute

$\displaystyle\hat{Q}(x,y)=\sum\limits_{i=1}^{K}\lambda_{i}\hat{f}_{i}(x)\hat{f}_{i}(y).$

Complexity. With high probability, the running time of our algorithm is
$O(n\log n)$. The non-backtracking matrix $B$ is typically sparse with $O(n)$
non-zero entries. Therefore, extracting $K$ largest magnitude eigenvalues and
corresponding eigenvectors takes time $O(n\log n)$ by the power algorithm.
This implies that the complexity of Non_Backtracking_Matrix is with high
probability $O(n\log n)$. The rest of the algorithm runs in time $O(n)$.

##  4 Proof Outline

In this section, we list a few key lemmas for the proof of our main result.
The auxiliary lemmas and the proof of the key lemmas are deferred to later
sections.

######  Lemma 4.1.

Let $Q$ satisfy Assumptions $1$ and $2$. Then with probability tending to $1$
as $n\rightarrow\infty$,

$\displaystyle\lambda_{k}(B)=\mu_{k}+O(\frac{1}{\log n}),\text{ for
}k\in[r_{0}]\text{, and for
}k>r_{0},|\lambda_{k}(B)|\leq\sqrt{\mu_{1}}+O(\frac{1}{\log n}).$

Recall that
$\mathcal{C}_{ij}:=\frac{1}{\sqrt{n}}\sum\limits_{\ell=1}^{n}B_{i}(\ell)f_{j}(X_{\ell}).$
We also have that for $i\in[r_{0}]$,

$\displaystyle\mathcal{C}_{ii}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\theta_{i},$

and

$\displaystyle\sum_{\ell=1}^{\infty}\mu_{\ell}\mathcal{C}_{i\ell}^{2}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\mu_{i}\theta_{i}^{2},$

where $\theta_{i}$ is a nonzero constant.

The result on eigenvalues is a direct generalization of Theorem $4$ in [14].
To prove the convergence of $\mathcal{C}_{ij}$, we also need to use results in
[14] and generalized versions for graphons. More specifically, we need results
that relate the eigenvectors of the nonbacktracking matrix $B$ to some local
statistics of the random graph. This is then related to certain functionals on
branching processes via coupling.

In particular, Lemma 4.1 immediately implies that

######  Lemma 4.2.

With probability tending to $1$ as $n\rightarrow\infty$,

$\displaystyle K=r_{0}.$

The next few lemmas are about counting the weighted stars described in Section
3.

######  Lemma 4.3.

For $i\in[r_{0}]$,

$\displaystyle
P_{ii}=\frac{A_{ii}}{\epsilon\lambda_{i}}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\theta_{i}^{2}.$

Through a second moment argument, we can show that $A_{ii}\approx\epsilon
B_{i}^{t}Q^{X}B_{i}$. Then the proof of this lemma follows by combining the
estimation on $\mathcal{C}_{ij}$ and $\lambda_{i}$.

######  Lemma 4.4.

For $0\leq\alpha\leq\mathbf{N}$, we have that

$\displaystyle
P_{\alpha}=\frac{A_{\alpha}n^{|\alpha|/2-1}}{\epsilon^{|\alpha|}\prod_{i=1}^{K}(\sqrt{P_{ii}}\lambda_{i})^{\alpha_{i}}}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\int_{[0,1]}f_{\alpha}dx.$

Similar to the above, by a second moment argument, we can show that
$A_{\alpha}\approx\sum_{w=1}^{n}\prod_{\ell=1}^{|\alpha|}\epsilon
B_{I^{\alpha}_{\ell}}^{t}Q^{X}(w)$. So the lemma follows by combining
estimation on $\mathcal{C}_{ij}$, $P_{ii}$ and $\lambda_{i}$.

Let $U$ be Uniform on $[0,1]$ and let $N_{i}$ be a series of iid random
variables whose distribution function is proportional to $\Psi_{\delta}(x)$.
Define $Y_{i}=f_{i}(U)+N_{i}$. Then the joint distribution of
$(Y_{1},\cdots,Y_{K})$ is the same as
$(f_{1}(U)+N_{1},\cdots,f_{K}(U)+N_{K})$. For each multi-index
$\alpha=(\alpha_{1},\cdots,\alpha_{K})$, we write
$f_{\alpha}=\prod_{i=1}^{|\alpha|}f_{i}^{\alpha_{i}}.$ Therefore,

$\displaystyle\int f_{\alpha}dx$
$\displaystyle=\mathbb{E}[f_{1}(U)^{\alpha_{1}}\cdots
f_{K}(U)^{\alpha_{K}}]=\mathbb{E}[f_{\alpha}(U)].$

We can also relate this term to the joint moments of the $Y_{i}$’s.

$\displaystyle\mathbb{E}[Y_{1}^{\alpha_{1}}\cdots Y_{K}^{\alpha_{K}}]$
$\displaystyle=\mathbb{E}[(f_{1}(U)+N_{1})^{\alpha_{1}}\cdots(f_{K}(U)+N_{K})^{\alpha_{K}}]$
$\displaystyle=\sum\limits_{0\leq\beta\leq\alpha}\mathbb{E}[f_{\beta}(U)]\prod_{i=1}^{K}{\alpha_{i}\choose\beta_{i}}\mathbb{E}[N_{\delta}^{\alpha_{i}-\beta_{i}}]$
$\displaystyle=:\mu_{\alpha}(\delta),$

where $N_{\delta}$ is a random variable whose distribution function is
proportional to $\Psi_{\delta}(x)$. Lemma 4.4 makes sure that the function
Sub_Graph_Count($E_{2},K,\lambda_{1},\cdots,\lambda_{K},B_{1}\cdots,B_{K},N$)
outputs a good estimation of $\mathbb{E}[f_{\alpha}(U)]$. This implies that
$\mu_{\alpha}(\delta)\approx M_{\alpha}(\delta)$. Further, we have the lemma
below.

Let $u$ be the joint distribution function of
$(f_{1}(U)+N_{1},\cdots,f_{K}(U)+N_{K})$.

######  Lemma 4.5.

With probability tending to $1$ as $n\rightarrow\infty$,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}\left|\frac{\hat{h}_{N}^{+}}{\|\hat{h}_{N}^{+}\|_{1}}-u\right|d\mathbf{x}\leq\frac{e_{0}}{2^{5}K\lambda_{1}^{2}\kappa^{4}}.$

This lemma shows that given approximate moments, multivariate polynomials up
to degree $\mathbf{N}$ can form good estimates of the joint distribution
function. This is proved by controlling the tail terms when the joint
distribution is expanded in the Legendre polynomial basis. This term is
related to the smoothness properties of $u$, which is why the mollifying step
is necessary in our algorithm.

######  Lemma 4.6.

Let $Z_{1},\cdots,Z_{m}$ be iid random vectors following the distribution
proportional to $\hat{h}_{N}^{+}$. Then there exists a measure preserving map
$\phi:[0,1]\rightarrow[0,1]$, such that

$\displaystyle\int_{[0,1]}|Z_{\lceil\phi(x)m\rceil}(i)-f_{i}(x)|^{2}dx\leq\frac{e_{0}}{4K\lambda_{1}^{2}\kappa^{2}}$

with probability tending to $1$ and $m\rightarrow\infty$.

This lemma together with our estimation on $\lambda_{i}$ gives the desired
result: with probability tending to $1$ and $n\rightarrow\infty$,
$\delta_{2}(\hat{Q},Q_{r_{0}})\leq e_{0}$.

##  5 Proofs

###  5.1 Spectrum of the Non-backtracking Matrix

######  Theorem 5.1 (Theorem $4$ in [14]).

Let $Q$ be an SBM satisfying the constant expected degree condition. Then with
probability tending to $1$ as $n\rightarrow\infty$,

$\displaystyle\lambda_{k}(B)=\mu_{k}+o(1),\text{ for }k\in[r_{0}]\text{, and
for }k>r_{0},|\lambda_{k}(B)|\leq\sqrt{\mu_{1}}+o(1).$

Actually, from Proposition $8$, $19$ and $20$ in the text, we have that

$\displaystyle\lambda_{k}(B)=\mu_{k}+O(\frac{1}{\log n}),\text{ for
}k\in[r_{0}]\text{, and for
}k>r_{0},|\lambda_{k}(B)|\leq\sqrt{\mu_{1}}+O(\frac{1}{\log n}).$

######  Theorem 5.2.

Let $Q$ be a graphon satisfying Assumptions $1$ and $2$. Then with probability
tending to $1$ as $n\rightarrow\infty$,

$\displaystyle\lambda_{k}(B)=\mu_{k}+O(\frac{1}{\log n}),\text{ for
}k\in[r_{0}]\text{, and for
}k>r_{0},|\lambda_{k}(B)|\leq\sqrt{\mu_{1}}+O(\frac{1}{\log n}).$

The proof is a direct generalization of Theorem 5.1. So we omit it here. This
theorem immediately implies the following lemma.

######  Lemma 5.3.

With probability tending to $1$ as $n\rightarrow\infty$,

$\displaystyle K=r_{0}.$

###  5.2 Subgraph Counts

Recall that

$\displaystyle\mathcal{C}_{ij}:=\frac{1}{\sqrt{n}}\sum\limits_{\ell=1}^{n}B_{i}(V_{\ell})f_{j}(X_{\ell}).$

######  Lemma 5.4.

For $i\in[r_{0}]$,

$\displaystyle\mathcal{C}_{ii}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\theta_{i},$

and

$\displaystyle\sum_{\ell=1}^{\infty}\mu_{\ell}\mathcal{C}_{i\ell}^{2}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\mu_{i}\theta_{i}^{2}.$

as $n$ goes to infinity, where $\theta_{i}$ is a nonzero constant.

We will prove this lemma in later sections. As all $\mu_{i}$’s are simple for
$i\in[r_{0}]$, corresponding eigenfunctions are unique up to signs. Notice
that if we reverse the sign of $f_{i}$, then the sign of $\theta_{i}$ is also
reversed. So there is an orientation of $f_{1},\cdots,f_{r_{0}}$ such that all
the corresponding $\theta_{i}$’s are positive. From now on, without loss of
generality, we fix such orientation.

From now on, we work in the case when $K=r_{0}$. Recall from our definition
that for $k\in[K]$,

$\displaystyle A_{kk}:=\sum\limits_{1\leq i,j\leq
n}B_{k}(i)B_{k}(j)\mathbbm{1}[i\sim j].$

Given $X_{1},\cdots,X_{n}$, denote $Q^{X}$ as a matrix where its $(i,j)$-th
entry equals to $Q(X_{i},X_{j})$.

######  Lemma 5.5.

Fix $E_{1}$. For $k\in[K]$ and $0<\gamma<\frac{1}{2}$, with probability larger
than $1-2\|B_{k}\|_{2}^{4}\epsilon Mn^{-2\gamma}$,

$\displaystyle|A_{kk}-\epsilon B_{k}^{t}Q^{X}B_{k}|\leq
2n^{-\frac{1}{2}+\gamma}.$

###### Proof.

Recall that vertices $i$ and $j$ are connected by an edge with probability
$\epsilon Q^{X}(i,j)/n$. Define $D_{ij}=B_{k}(i)B_{k}(j)\mathbbm{1}[i\sim j]$.
Then $D_{ij}$ and $D_{i^{\prime}j^{\prime}}$ are independent whenever $i\sim
j$ and ${i^{\prime}}\sim{j^{\prime}}$ are different edges. Thus

$\displaystyle{\mathrm{Var}}(A_{kk})$
$\displaystyle={\mathrm{Var}}\left(2\sum\limits_{1\leq i<j\leq
n}B_{k}(i)B_{k}(j)\mathbbm{1}[i\sim j]\right)$ $\displaystyle\leq
4\sum\limits_{1\leq i<j\leq n}B_{k}(i)^{2}B_{k}(j)^{2}\frac{\epsilon M}{n}$
$\displaystyle\leq 2\|B_{k}\|_{2}^{4}\frac{\epsilon M}{n}.$

So by a second moment estimate,

$\displaystyle\mathbb{P}[|A_{kk}-\mathbb{E}[A_{kk}]|\geq
n^{-\frac{1}{2}+\gamma}]\leq\frac{{\mathrm{Var}}(A_{kk})}{n^{-1+2\gamma}}\leq
2\|B_{k}\|_{2}^{4}\epsilon Mn^{-2\gamma}.$

As $|\mathbb{E}[A_{kk}]-\epsilon
B_{k}^{t}Q^{X}B_{k}|=o(n^{-\frac{1}{2}+\gamma})$, the statement follows. ∎

By Lemma 5.4, we have

$\displaystyle B_{k}^{t}Q^{X}B_{k}$
$\displaystyle=\sum_{i,j=1}^{n}B_{k}(i)Q^{X}(i,j)B_{k}(j)$
$\displaystyle=\sum_{i,j=1}^{n}B_{k}(i)\left(\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}(X_{i})f_{\ell}(X_{j})\right)B_{k}(j)$
$\displaystyle=\sum_{\ell=1}^{\infty}\mu_{\ell}\mathcal{C}^{2}_{k\ell}$
$\displaystyle\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\mu_{k}\theta_{k}^{2},$

as $n$ goes to infinity. We define $d_{1}$ as the maximum degree of vertices
in $G_{1}$. Then $d_{1}=O(\log n)$ with high probability. This implies that
$\|B_{i}\|_{2}=O(\log n)$. So $\epsilon^{-1}A_{kk}$ converges to
$\mu_{k}\theta_{k}^{2}$ in probability. By Theorem 5.2, $P_{kk}$ converges to
$\theta_{k}^{2}$ in probability. Recall that we use $Q^{X}_{w}$ to denote the
$w$-th column of $Q^{X}$.

######  Lemma 5.6.

Fix $E_{1}$. For any multi-index $\alpha$ and $0<\gamma<\frac{1}{2}$, with
probability larger than $1-2|\alpha|!(\epsilon
M)^{|\alpha|}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{2}^{2\alpha_{i}}n^{-2\gamma}$,
we have that

$\displaystyle|A_{\alpha}-\sum_{w=1}^{n}\prod_{\ell=1}^{|\alpha|}\epsilon
B_{I^{\alpha}_{\ell}}^{t}Q^{X}(w)|\leq 2n^{-\frac{|\alpha|-1}{2}+\gamma}.$

###### Proof.

Recall that

$\displaystyle A_{\alpha}:=\sum_{1\leq i_{1},\cdots,i_{|\alpha|},w\leq
n}\prod_{\ell=1}^{|\alpha|}B_{I^{\alpha}_{\ell}}({i_{\ell}})\mathbbm{1}[{i_{\ell}}\sim
w],$

where all $i_{\ell}$ are disjoint. Define
$D_{i,w}:=\prod_{\ell=1}^{|\alpha|}B_{I^{\alpha}_{\ell}}({i_{\ell}})\mathbbm{1}[{i_{\ell}}\sim
w]$. Define $E(D_{i,w})$ to be the set of all edges ${i_{\ell}}\sim w$. We use
$[n]^{k}_{<}$ to denote the set consisting of all strictly ordered $k$-tuples
from the set $[n]$. More precisely, we define

$\displaystyle[n]^{k}_{<}=\\{(i_{1},\cdots,i_{k})\in[n]^{k}:1\leq
i_{1}<\cdots<i_{k}\leq n\\}.$

Thus we can also write $A_{\alpha}$ as

$\displaystyle A_{\alpha}$
$\displaystyle=|\alpha|!\sum_{i\in[n]^{|\alpha|}_{<},w\in[n]}\prod_{\ell=1}^{|\alpha|}B_{I^{\alpha}_{\ell}}({i_{\ell}})\mathbbm{1}[{i_{\ell}}\sim
w]$ $\displaystyle=|\alpha|!\sum_{i\in[n]^{|\alpha|}_{<},w\in[n]}D_{i,w}$

Note that $\prod_{\ell=1}^{|\alpha|}\mathbbm{1}[{i_{\ell}}\sim w]$ follows
Bernoulli $(\prod_{\ell=1}^{|\alpha|}\frac{\epsilon Q^{X}(i_{\ell},w)}{n})$
distribution. So variance of $D_{i,w}$ is bounded by
$\prod_{\ell=1}^{|\alpha|}B_{I_{\ell}^{\alpha}}({i_{\ell}})^{2}\frac{\epsilon
M}{n}$. Also, we notice that $D_{i,w}$ and $D_{i^{\prime},w^{\prime}}$ are
independent whenever $E(D_{i,w})$ and $E(D_{i^{\prime},w^{\prime}})$ are
disjoint. When they are not, we write $(i,w)\sim^{a}(i^{\prime},w^{\prime})$,
if $E(D_{i,w})$ and $E(D_{i^{\prime},w^{\prime}})$ have $a$ edges in common.
If $(i,w)\sim^{a}(i^{\prime},w^{\prime})$, then
$|\mathrm{Cov}(D_{i,w},D_{i^{\prime},w^{\prime}})|\leq(\frac{\epsilon
M}{n})^{2|\alpha|-a}\prod_{\ell=1}^{|\alpha|}|B_{I^{\alpha}_{\ell}}({i_{\ell}})B_{I^{\alpha}_{\ell}}({i^{\prime}_{\ell}})|$.
Then we have that

$\displaystyle{\mathrm{Var}}(A_{\alpha})$
$\displaystyle=(|\alpha|!)^{2}\sum_{i\in[n]^{|\alpha|}_{<},w\in[n]}{\mathrm{Var}}(D_{i,w})+(|\alpha|!)^{2}\sum_{i,i^{\prime}\in[n]^{|\alpha|}_{<},w,w^{\prime}\in[n],(i,w)\sim(i^{\prime},w^{\prime})}\mathrm{Cov}(D_{i,w},D_{i^{\prime},w^{\prime}})$
$\displaystyle\leq|\alpha|!\sum_{i\in[n]^{|\alpha|},w\in[n]}\prod_{\ell=1}^{|\alpha|}B_{I_{\ell}^{\alpha}}({i_{\ell}})^{2}\frac{\epsilon
M}{n}$
$\displaystyle\quad+\sum_{a=1}^{|\alpha|-1}\sum_{i,i^{\prime}\in[n]^{|\alpha|},w,w^{\prime}\in[n],(i,w)\sim^{a}(i^{\prime},w^{\prime})}(\frac{\epsilon
M}{n})^{2|\alpha|-a}\prod_{\ell=1}^{|\alpha|}|B_{I^{\alpha}_{\ell}}({i_{\ell}})B_{I^{\alpha}_{\ell}}({i^{\prime}_{\ell}})|$
$\displaystyle\leq|\alpha|!\frac{(\epsilon
M)^{|\alpha|}}{n^{|\alpha|-1}}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{2}^{2\alpha_{\ell}}+\sum_{a=1}^{|\alpha|-1}C_{a}\frac{(\epsilon
M)^{2|\alpha|-a}}{n^{|\alpha|-1}}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{2}^{2\alpha_{\ell}}+C\frac{(\epsilon
M)^{2|\alpha|-1}}{n^{2|\alpha|-1}}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{1}^{2\alpha_{\ell}}$
$\displaystyle\leq 2|\alpha|!\frac{(\epsilon
M)^{|\alpha|}}{n^{|\alpha|-1}}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{2}^{2\alpha_{\ell}},$

where $C_{a}$ and $C$ are some constants. The second last inequality follows
by separating cases into whether $w=w^{\prime}$ and that
$\|B_{i}\|_{1}^{2}\leq n\|B_{i}\|_{2}^{2}$. So by a second moment estimate, we
have that

$\displaystyle\mathbb{P}[|A_{\alpha}-\mathbb{E}[A_{\alpha}]|\geq
n^{-\frac{|\alpha|-1}{2}+\gamma}]$
$\displaystyle\leq\frac{2|\alpha|!\frac{(\epsilon
M)^{|\alpha|}}{n^{|\alpha|-1}}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{2}^{2\alpha_{\ell}}}{n^{-|\alpha|+1+2\gamma}}$
$\displaystyle\leq 2|\alpha|!(\epsilon
M)^{|\alpha|}\prod_{\ell=1}^{K}\|B_{I_{\ell}^{\alpha}}\|_{2}^{2\alpha_{\ell}}n^{-2\gamma}.$

As $|\mathbb{E}[A_{\alpha}]-\sum_{w=1}^{n}\prod_{\ell=1}^{|\alpha|}\epsilon
B_{I^{\alpha}_{\ell}}^{t}Q^{X}(w)|=o(n^{-\frac{|\alpha|-1}{2}+\gamma})$, the
statement follows. ∎

This lemma implies that with probability larger than $1-O(n^{-\gamma})$, we
have that, for any $0\leq\alpha\leq\mathbf{N}$,

$\displaystyle|n^{\frac{|\alpha|}{2}-1}\epsilon^{-|\alpha|}A_{\alpha}-n^{\frac{|\alpha|}{2}-1}\sum_{w=1}^{n}\prod_{\ell=1}^{|\alpha|}B_{I^{\alpha}_{\ell}}^{t}Q^{X}(w)|\leq
2n^{-\frac{1}{2}+\gamma}\epsilon^{-|\alpha|}.$

Therefore, for any $0\leq\alpha\leq\mathbf{N}$,

$\displaystyle
n^{\frac{|\alpha|}{2}-1}\epsilon^{-|\alpha|}A_{\alpha}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}n^{\frac{|\alpha|}{2}-1}\sum_{w=1}^{n}\prod_{\ell=1}^{|\alpha|}B_{I^{\alpha}_{\ell}}^{t}Q^{X}(w),$

as $n$ goes to infinity.

Recall that, for each multi-index $\alpha=(\alpha_{1},\cdots,\alpha_{K})$, we
write $f_{\alpha}=\prod_{i=1}^{|\alpha|}f_{i}^{\alpha_{i}}.$

######  Lemma 5.7.

For $0\leq\alpha\leq\mathbf{N}$, we have that

$\displaystyle
n^{\frac{|\alpha|}{2}-1}\epsilon^{-|\alpha|}A_{\alpha}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\prod_{i=1}^{K}(\theta_{i}\mu_{i})^{\alpha_{i}}\int_{[0,1]}f_{\alpha}(x)dx,$

as $n$ goes to infinity.

###### Proof.

Define
$A_{j}(X_{w})=\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}(X_{w})\mathcal{C}_{j\ell}$
and $B_{j}(X_{w})=\mu_{{}_{j}}f_{j}(X_{w})\theta_{j}$. By Lemma 5.4, we have
that for $j\in[K]$,

$\displaystyle|A_{j}(X_{w})-B_{j}(X_{w})|$
$\displaystyle\leq\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}(X_{w})|\mathcal{C}_{j\ell}-\delta_{j,\ell}\theta_{j}|$
$\displaystyle\leq\left(M\sum_{\ell=1}^{\infty}\mu_{\ell}|\mathcal{C}_{j\ell}-\delta_{j,\ell}\theta_{j}|^{2}\right)^{\frac{1}{2}}$
$\displaystyle\leq\left(M|\sum_{\ell=1}^{\infty}\mu_{\ell}\mathcal{C}_{j\ell}^{2}-\mu_{j}\theta_{j}^{2}|+M\mu_{j}|\mathcal{C}_{jj}-\theta_{j}|^{2}\right)^{\frac{1}{2}},$

which goes to zero in probability. We also note that with high probability,

$\displaystyle|A_{j}(X_{w})|^{2}\leq
K\sum_{\ell=1}^{\infty}\mu_{\ell}\mathcal{C}_{I^{\alpha}_{j},\ell}^{2}\leq
2K\mu_{\ell}\theta_{I^{\alpha}_{j},\ell}.$

Therefore,

$\displaystyle\left|\frac{1}{n}\sum_{w=1}^{n}\prod_{j=1}^{|\alpha|}\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}(X_{w})\mathcal{C}_{I^{\alpha}_{j},\ell}-\frac{1}{n}\sum_{w=1}^{n}\prod_{j=1}^{|\alpha|}\mu_{I^{\alpha}_{j}}f_{I^{\alpha}_{j}}(X_{w})\theta_{I^{\alpha}_{j}}\right|$
$\displaystyle\leq\frac{1}{n}\sum_{w=1}^{n}\left|\prod_{j=1}^{|\alpha|}A_{I^{\alpha}_{j}}(X_{w})-\prod_{j=1}^{|\alpha|}B_{I^{\alpha}_{j}}(X_{w})\right|$
$\displaystyle\leq|\alpha|(2K\mu_{\ell}\theta_{I^{\alpha}_{j},\ell})^{|\alpha|}\sup_{j\in[K]}|A_{j}-B_{j}|$
$\displaystyle\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}0,$

as $n$ goes to infinity. This implies that

$\displaystyle
n^{\frac{|\alpha|}{2}-1}\sum_{w=1}^{n}\prod_{j=1}^{|\alpha|}B_{I^{\alpha}_{j}}^{t}Q^{X}(w)$
$\displaystyle=\frac{1}{n}\sum_{w=1}^{n}\prod_{j=1}^{|\alpha|}\sum_{i=1}^{n}\sqrt{n}B_{I^{\alpha}_{j}}(i)\left(\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}(X_{i})f_{\ell}(X_{w})\right)$
$\displaystyle=\frac{1}{n}\sum_{w=1}^{n}\prod_{j=1}^{|\alpha|}\sum_{\ell=1}^{\infty}\mu_{\ell}f_{\ell}(X_{w})\mathcal{C}_{I^{\alpha}_{j},\ell}$
$\displaystyle\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\frac{1}{n}\sum_{w=1}^{n}\prod_{j=1}^{|\alpha|}\mu_{I^{\alpha}_{j}}f_{I^{\alpha}_{j}}(X_{w})\theta_{I^{\alpha}_{j}}$
$\displaystyle=\prod_{i=1}^{K}(\theta_{i}\mu_{i})^{\alpha_{i}}\frac{1}{n}\sum_{w=1}^{n}f_{\alpha}(X_{w}),$

as $n$ goes to infinity. We also notice that, by law of large number,

$\displaystyle\frac{1}{n}\sum_{w=1}^{n}f_{\alpha}(X_{w})\rightarrow\int_{[0,1]}f(x)dx,a.s.$

Therefore, the lemma follows. ∎

Consequently,

######  Lemma 5.8.

For $0\leq\alpha\leq\mathbf{N}$, we have that

$\displaystyle
P_{\alpha}=\frac{A_{\alpha}n^{|\alpha|/2-1}}{\epsilon^{|\alpha|}\prod_{i=1}^{K}(\sqrt{P_{ii}}\lambda_{i})^{\alpha_{i}}}\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}\int_{[0,1]}f_{\alpha}dx,$

as $n$ goes to infinity.

###  5.3 Polynomial Approximation

Let $U$ be Uniform on $[0,1]$ and let $N_{i}$ be a series of iid random
variables whose distribution function is proportional to $\Psi_{\delta}(x)$.
Define $Y_{i}=f_{i}(U)+N_{i}$. Then the joint distribution of
$(Y_{1},\cdots,Y_{K})$ is the same as
$(f_{1}(U)+N_{1},\cdots,f_{K}(U)+N_{K})$. Therefore,

$\displaystyle\int f_{\alpha}dx$
$\displaystyle=\mathbb{E}[f_{1}(U)^{\alpha_{1}}\cdots
f_{K}(U)^{\alpha_{K}}]=\mathbb{E}[f_{\alpha}(U)].$

We can also relate this term to the joint moments of the $Y_{i}$’s.

$\displaystyle\mathbb{E}[Y_{1}^{\alpha_{1}}\cdots Y_{K}^{\alpha_{K}}]$
$\displaystyle=\mathbb{E}[(f_{1}(U)+N_{1})^{\alpha_{1}}\cdots(f_{K}(U)+N_{K})^{\alpha_{K}}]$
$\displaystyle=\sum\limits_{0\leq\beta\leq\alpha}\mathbb{E}[f_{\beta}(U)]\prod_{i=1}^{K}{\alpha_{i}\choose\beta_{i}}\mathbb{E}[N_{\delta}^{\alpha_{i}-\beta_{i}}]$
$\displaystyle=:\mu_{\alpha}(\delta),$

where $N_{\delta}$ is a random variable whose distribution function is
proportional to $\Psi_{\delta}(x)$.

######  Lemma 5.9.

If $|P_{\alpha}-\int_{[0,1]}f_{\alpha}dx|\leq e_{2}$ for any
$0\leq\alpha\leq\mathbf{N}$, then

$\displaystyle\sum_{0\leq\alpha\leq
N}|M_{\alpha}(\delta)-\mu_{\alpha}(\delta)|^{2}\leq
e_{3}^{2}:=e_{2}^{2}\left(\sum_{i=0}^{N}\mathbb{E}[(1+N_{\delta})^{i}]^{2}\right)^{K}.$

###### Proof.

Recall that in the function Mollifier_Convolution, we defined

$\displaystyle
M_{\alpha}(\delta)=\sum\limits_{0\leq\beta\leq\alpha}P_{\beta}\prod_{i=1}^{K}{\alpha_{i}\choose\beta_{i}}\mathbb{E}[N^{\alpha_{i}-\beta_{i}}].$

So by our assumption,

$\displaystyle\sum_{0\leq\alpha\leq
N}|M_{\alpha}(\delta)-\mu_{\alpha}(\delta)|^{2}$
$\displaystyle\leq\sum_{0\leq\alpha\leq\mathbf{N}}\left(e_{2}\sum\limits_{0\leq\beta\leq\alpha}\prod_{i=1}^{K}{\alpha_{i}\choose\beta_{i}}\mathbb{E}[N_{\delta}^{\alpha_{i}-\beta_{i}}]\right)^{2}$
$\displaystyle=e_{2}^{2}\sum_{0\leq\alpha\leq\mathbf{N}}\mathbb{E}[(1+N_{\delta})^{\alpha_{1}}]^{2}\cdots\mathbb{E}[(1+N_{\delta})^{\alpha_{K}}]^{2}$
$\displaystyle=e_{2}^{2}\left(\sum_{i=0}^{N}\mathbb{E}[(1+N_{\delta})^{i}]^{2}\right)^{K}.$

∎

We note that being the $i$-th eigenfunction of $Q$,

$\displaystyle|\mu_{i}f_{i}(x)|=|\int_{0}^{1}Q(x,y)f_{i}(y)dy|\leq(\int_{0}^{1}Q(x,y)^{2}dy)^{1/2}\leq
M$

So,

$\displaystyle|f_{i}(x)|\leq\frac{M}{|\mu_{i}|}\leq\frac{M}{\sqrt{\mu_{1}}},$

for $i\in[r_{0}]$. With high probability, as $|\lambda_{1}-\mu_{1}|\leq
e_{1}(n)\leq 1\leq\mu_{1}$, we have that $\sqrt{\lambda_{1}}\leq
3\sqrt{\mu_{1}}/2$. So $|f_{i}(x)|\leq\frac{3M}{2\sqrt{\lambda_{1}}}$.
Further, as $\delta\leq\frac{1}{2}\leq\frac{M}{2\sqrt{\lambda_{1}}}$, we have
$|Y_{i}|\leq\frac{2M}{\sqrt{\lambda_{1}}}=\kappa$ with high probability. Write
$u(x_{1},\cdots,x_{K})$ as the distribution function of
$(Y_{1},\cdots,Y_{K})$. So with high probability, $u$ is identically zero
outside the box $[-\kappa,\kappa]^{K}$. Moreover, $u$ is a smooth function as
$\Psi$ is smooth. Now, we use Legendre polynomials in $[-\kappa,\kappa]^{K}$
to approximate $u$. Write

$\displaystyle\rho_{\alpha}=\int_{[-\kappa,\kappa]^{K}}u(x_{1},\cdots,x_{K})\tilde{L}_{\alpha}(x_{1},\cdots,x_{K})d\mathbf{x}.$

Therefore,

$\displaystyle\rho_{\alpha}=\sum\limits_{0\leq\beta\leq\alpha}\tilde{C}^{\otimes
K}_{\beta}\mu_{\alpha}.$

One way to approximate $u$ is to consider the following term

$\displaystyle
h_{N}(x_{1},\cdots,x_{K}):=\sum\limits_{0\leq\beta\leq\mathbf{N}}\rho_{\beta}\tilde{L}_{\beta}(x_{1},\cdots,x_{K}).$

Define

$\displaystyle
t_{N}(x_{1},\cdots,x_{K}):=\sum\limits_{\cup_{i}\\{\beta:\beta_{i}>N\\}}\rho_{\beta}\tilde{L}_{\beta}(x_{1},\cdots,x_{K}),$
$\displaystyle
t_{i,N}(x_{1},\cdots,x_{K}):=\sum\limits_{\beta:\beta_{i}>N}\rho_{\beta}\tilde{L}_{\beta}(x_{1},\cdots,x_{K}).$

We define $H_{N}$ to be a $(N+1)$ by $(N+1)$ matrix such that its $(i,j)$-th
entry equals to $\frac{2}{i+j-1}$, when $i+j$ is even and $0$ elsewhere. Write
$\mathrm{Cond}(H_{N})$ as its condition number.

######  Lemma 5.10.

If

$\displaystyle\sum_{0\leq\alpha\leq
N}|M_{\alpha}(\delta)-\mu_{\alpha}(\delta)|^{2}\leq e_{3}^{2},$

then

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\hat{h}_{N}(x_{1},\cdots,x_{K})-h_{N}(x_{1},\cdots,x_{K})|^{2}d\mathbf{x}\leq
e_{3}^{2}\kappa^{2N+1}(\mathrm{Cond}(H_{N}))^{K}.$

###### Proof.

Recall that $\tilde{C}_{ij}$ are scaled Legendre polynomial coefficients.
Define $\tilde{C}$ to be a $(N+1)$ by $(N+1)$ matrix such that its
$(i+1,j+1)$-th entry equals to $\tilde{C}_{ij}$. Define a matrix
$\tilde{H}_{N}=(\tilde{C}^{T}\tilde{C})^{-1}$. Note that the $(i,j)$-th entry
of $\tilde{H}_{N}$ equals to $\frac{2\kappa^{i+j-1}}{i+j-1}$, when $i+j$ is
even and $0$ elsewhere. The reason is as follows. Define
$\tilde{M}=\tilde{C}^{-1}$. Write $\tilde{M}_{ij}$ as $(i+1,j+1)$-th entry of
$\tilde{M}$. Then

$\displaystyle x^{i}=\sum_{j=0}^{i}\tilde{M}_{ij}\tilde{L}_{j}(x).$

Thus

$\displaystyle\int_{[-\kappa,\kappa]}x^{i}\sum_{j=0}^{k}\tilde{C}_{kj}x^{j}dx=\sum_{j=0}^{k}\tilde{C}_{kj}\frac{(1-(-1)^{i+j+1})\kappa^{i+j+1}}{i+j+1}=\tilde{M}_{ik}.$

Therefore,
$\lambda_{\min}(\tilde{H}_{N})\geq\kappa^{-2N-1}\lambda_{\min}(H_{N}).$ We
write $\tilde{H}_{N}^{\otimes K}$ as the Kronecker product of $K$ copies of
$\tilde{H}_{N}$. Write $M(\delta)$ and $\mu(\delta)$ as vector of
$M_{\alpha}(\delta)$ and $\mu_{\alpha}(\delta)$ respectively. Then

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\hat{h}_{N}(x_{1},\cdots,x_{K})-h_{N}(x_{1},\cdots,x_{K})|^{2}d\mathbf{x}$
$\displaystyle=\langle(H_{N}^{\otimes
K})^{-1}(M(\delta)-\mu(\delta)),M(\delta)-\mu(\delta)\rangle$
$\displaystyle\leq e_{3}^{2}\kappa^{2N+1}(\mathrm{Cond}(H_{N}))^{K}.$

The last inequality follows from the fact that the largest eigenvalue of
$\lambda_{\max}(H_{N})\geq 1$. ∎

In order to control the tail terms, we need to have the following inequality
first.

######  Lemma 5.11.

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\frac{d}{dx_{i}}u(x)|^{2}d\mathbf{x}\leq(2\kappa)^{K}\delta^{-2K-8}.$

###### Proof.

We denote by $T$ the distribution of $(f_{1}(U),\cdots,f_{K}(U))$. We consider
it as a continuous linear functional on $C^{\infty}([-\kappa,\kappa]^{K})$. We
also define $\Psi_{\delta}^{\otimes
K}(x_{1},\cdots,x_{K})=\Psi_{\delta}(x_{1})\cdots\Psi_{\delta}(x_{K})$. Then

$\displaystyle u(x_{1},\cdots,x_{K})=(T*C_{\delta}\Psi_{\delta}^{\otimes
K})(x_{1},\cdots,x_{K}),$

where $C_{\delta}$ is the normalization constant of $\Psi_{\delta}^{\otimes
K}$ such that $\|C_{\delta}\Psi_{\delta}^{\otimes K}\|_{1}=1$. Thus

$\displaystyle\|\frac{d}{dx_{i}}u(x)\|_{L_{\infty}([-\kappa,\kappa]^{K})}$
$\displaystyle=C_{\delta}\|T*\frac{d}{dx_{i}}\Psi_{\delta}^{\otimes
K}\|_{L_{\infty}([-\kappa,\kappa]^{K})}$ $\displaystyle\leq
C_{\delta}\|\frac{d}{dx_{i}}\Psi_{\delta}^{\otimes
K}\|_{L_{\infty}([-\kappa,\kappa]^{K})}$
$\displaystyle=C_{\delta}\|\frac{-2x_{i}}{(\delta^{2}-x_{i}^{2})^{2}}\Psi_{\delta}^{\otimes
K}\|_{L_{\infty}([-\kappa,\kappa]^{K})}$ $\displaystyle\leq\delta^{-K-4}.$

Therefore,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\frac{d}{dx_{i}}u(x)|^{2}d\mathbf{x}\leq(2\kappa)^{K}\delta^{-2K-8}.$

∎

######  Lemma 5.12.

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|t_{N}(x_{1},\cdots,x_{K})|^{2}d\mathbf{x}\leq\frac{K^{2}2^{K}\kappa^{K+2}\delta^{-2K-8}}{(N+1)^{2}}.$

###### Proof.

Recall that

$\displaystyle-\frac{d}{dx}[(1-x)(1+x)L_{i}^{\prime}(x)]=i(i+1)L_{i}(x),$

the differential equation for Legendre polynomials. So

$\displaystyle-\frac{d}{dx_{i}}[(1-x_{i})(1+x_{i})\frac{d}{dx_{i}}L_{\alpha}(x)]=\alpha_{i}(\alpha_{i}+1)L_{\alpha}(x).$

and

$\displaystyle-\frac{d}{dx_{i}}[(\kappa-
x_{i})(\kappa+x_{i})\frac{d}{dx_{i}}\tilde{L}_{\alpha}(x)]=\alpha_{i}(\alpha_{i}+1)\tilde{L}_{\alpha}(x).$

We multiply both sides by $u$ and do integration by parts twice,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}\tilde{L}_{\alpha}(x)\frac{d}{dx_{i}}[-(\kappa-
x_{i})(\kappa+x_{i})\frac{d}{dx_{i}}u(x)]d\mathbf{x}$ $\displaystyle=$
$\displaystyle\alpha_{i}(\alpha_{i}+1)\int_{[-\kappa,\kappa]^{K}}\tilde{L}_{\alpha}(x)u(x)d\mathbf{x}=\alpha_{i}(\alpha_{i}+1)\rho_{\alpha}.$

By Parseval’s theorem and integration by parts,

$\displaystyle\sum_{\alpha}\alpha_{i}(\alpha_{i}+1)|\rho_{\alpha}|^{2}$
$\displaystyle=\int_{[-\kappa,\kappa]^{K}}u(x)\frac{d}{dx_{i}}[-(\kappa-
x_{i})(\kappa+x_{i})\frac{d}{dx_{i}}u(x)]d\mathbf{x}$
$\displaystyle=\int_{[-\kappa,\kappa]^{K}}(\kappa-
x_{i})(\kappa+x_{i})|\frac{d}{dx_{i}}u(x)|^{2}d\mathbf{x}.$

By Pareval’s theorem and the definition of $t_{i,N}$,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|t_{i,N}|^{2}d\mathbf{x}$
$\displaystyle=\sum_{\alpha:\alpha_{i}>N}\rho_{\alpha}^{2}$
$\displaystyle\leq\frac{1}{(N+1)^{2}}\sum_{\alpha:\alpha_{i}>N}\alpha_{i}(\alpha_{i}+1)\rho_{\alpha}^{2}$
$\displaystyle\leq\frac{1}{(N+1)^{2}}\int_{[-\kappa,\kappa]^{K}}(\kappa-
x_{i})(\kappa+x_{i})|\frac{d}{dx_{i}}u(x)|^{2}d\mathbf{x}$
$\displaystyle\leq\frac{2^{K}\kappa^{K+2}\delta^{-2K-8}}{(N+1)^{2}}.$

This implies that

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|t_{N}(x_{1},\cdots,x_{K})|^{2}d\mathbf{x}\leq
K\sum_{i=1}^{K}\int_{[-\kappa,\kappa]^{K}}|t_{i,N}(x_{1},\cdots,x_{K})|^{2}d\mathbf{x}\leq\frac{K^{2}2^{K}\kappa^{K+2}\delta^{-2K-8}}{(N+1)^{2}}.$

∎

Combining Lemma 5.8, Lemma 5.9, Lemma 5.10, Lemma 5.12 and our definition of
$N$ and $\delta$, we have that with high probability,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\hat{h}_{N}-u|^{2}d\mathbf{x}$
$\displaystyle\leq
e_{2}^{2}\left(\sum_{i=0}^{N}\mathbb{E}[(1+N_{\delta})^{i}]^{2}\right)^{K}\kappa^{2N+1}(\mathrm{Cond}(H_{N}))^{K}+\frac{K^{2}2^{K}\kappa^{K+2}\delta^{-2K-8}}{(N+1)^{2}}$
$\displaystyle\leq 2^{-K-14}e_{0}^{2}K^{-2}\lambda_{1}^{-4}\kappa^{-K-8},$

as $n$ goes to infinity. Therefore,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\hat{h}_{N}-u|d\mathbf{x}\leq\frac{e_{0}}{2^{7}K\lambda_{1}^{2}\kappa^{4}}.$

Notice that this also implies that

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\hat{h}_{N}^{+}-\hat{h}_{N}|d\mathbf{x}\leq\frac{e_{0}}{2^{7}K\lambda_{1}^{2}\kappa^{4}}.$

Thus

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\hat{h}_{N}^{+}-u|d\mathbf{x}\leq\frac{e_{0}}{2^{6}K\lambda_{1}^{2}\kappa^{4}}.$

Further,

$\displaystyle\int_{[-\kappa,\kappa]^{K}}|\frac{\hat{h}_{N}^{+}}{\|\hat{h}_{N}^{+}\|_{1}}-u|d\mathbf{x}\leq\frac{e_{0}}{2^{5}K\lambda_{1}^{2}\kappa^{4}},$

as $n$ goes to infinity with high probability.

###  5.4 Graphon Estimation

Recall that in Graphon_Estimation, we sampled $Z_{1},\cdots,Z_{m}$ according
$\hat{h}_{N}^{+}$ mutually independently. For any $1\leq i\leq K$, we defined

$\displaystyle\hat{f}_{i}(x)=Z_{\lceil xm\rceil}(i).$

and set

$\displaystyle\hat{Q}(x,y)=\sum\limits_{i=1}^{K}\lambda_{i}\hat{f}_{i}(x)\hat{f}_{i}(y).$

######  Lemma 5.13.

Let $U_{1},\cdots,U_{m}$ be iid random variables following Uniform $[0,1]$
distribution. Then there exists a measure preserving map
$\phi:[0,1]\rightarrow[0,1]$, such that

$\displaystyle\int_{[0,1]}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}0,$

as $m$ goes to infinity.

###### Proof.

Define a permutation $\sigma\in S_{m}$ such that $U_{\sigma(1)}\leq
U_{\sigma(2)}\leq\cdots\leq U_{\sigma(m)}$. For $i\in[m]$, define

$\displaystyle\phi(x)=\frac{\sigma(i)-i}{m}+x,\ \
x\in(\frac{i-1}{m},\frac{i}{m}].$

Then $U_{\lceil\phi(x)m\rceil}$ is a piecewise constant monotone function in
$(0,1]$. For any $x\in(0,1]$, we can write down the distribution of
$U_{\lceil\phi(x)m\rceil}$ explicitly. For $\frac{i-1}{m}<x\leq\frac{i}{m}$,
$U_{\lceil\phi(x)m\rceil}$ follows Beta $(i,m-i+1)$ distribution. We will show
that, for any $\alpha>0$,

$\displaystyle\mathbb{P}[\int_{[0,1]}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx>\alpha]\rightarrow
0.$

As $f_{k}$ is a bounded function, it is in $L_{2}([0,1])$. Fix
$0<\epsilon<\alpha/3$. Using the density of continuous functions in
$L_{2}([0,1])$, we find a continuous function $g:[0,1]\rightarrow\mathbb{R}$
such that $\|f_{k}-g\|_{2}<\epsilon$. Thus

$\displaystyle\mathbb{P}[\int_{[0,1]}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx>\alpha]$
$\displaystyle=$
$\displaystyle\mathbb{P}[\sum_{i=1}^{m}\int_{\frac{i-1}{m}}^{\frac{i}{m}}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx>\alpha].$

Notice that

$\displaystyle\sum_{i=1}^{m}\int_{\frac{i-1}{m}}^{\frac{i}{m}}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx$
$\displaystyle\leq\frac{1}{m}\sum_{i=1}^{m}|f_{k}(U_{\sigma(i)})-g(U_{\sigma(i)})|^{2}dx$
$\displaystyle+\sum_{i=1}^{m}\int_{\frac{i-1}{m}}^{\frac{i}{m}}|g(U_{\lceil\phi(x)m\rceil})-g(x)|^{2}dx+\int_{0}^{1}|g(x)-f_{k}(x)|^{2}dx$

In order for the left hand side to be larger than $\alpha$, at least one of
terms on the right hand side should be larger than $\alpha/3$. The third term
is not possible by definition. So we have

$\displaystyle\mathbb{P}[\sum_{i=1}^{m}\int_{\frac{i-1}{m}}^{\frac{i}{m}}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx>\alpha]$
$\displaystyle\leq$
$\displaystyle\mathbb{P}[\frac{1}{m}\sum_{i=1}^{m}|f_{k}(U_{\sigma(i)})-g(U_{\sigma(i)})|^{2}dx>\alpha/3]+\mathbb{P}[\sum_{i=1}^{m}\int_{\frac{i-1}{m}}^{\frac{i}{m}}|g(U_{\lceil\phi(x)m\rceil})-g(x)|^{2}dx>\alpha/3].$

The first term equals

$\displaystyle\mathbb{P}[\frac{1}{m}\sum_{i=1}^{m}|f_{k}(U_{i})-g(U_{i})|^{2}dx>\alpha]\leq\frac{\epsilon^{2}}{\alpha}.$

To control the second term, consider the event
$A_{i}:=\\{|U_{\lceil\phi(x)m\rceil}-\frac{i}{m}|\leq m^{-\frac{1}{4}}\\}$.
Then

$\displaystyle\mathbb{P}[U_{\lceil\phi(x)m\rceil}-\frac{i}{m}\geq
m^{-\frac{1}{4}}]=\mathbb{P}[Y_{i}\leq i]\leq e^{-\frac{1}{4}\sqrt{m}},$

by Chernoff bound, where $Y_{i}$ follows
Binomial$(m,\frac{i}{m}+m^{-\frac{1}{4}})$ distribution. Similarly, when
$\frac{i}{m}-m^{-\frac{1}{4}}\geq 0$,

$\displaystyle\mathbb{P}[U_{\lceil\phi(x)m\rceil}\leq\frac{i}{m}-m^{-\frac{1}{4}}]=\mathbb{P}[Y_{i}\geq
i]\leq e^{-\frac{1}{2}\sqrt{m}},$

by Chernoff bound, where $Y_{i}$ follows
Binomial$(m,\frac{i}{m}-m^{-\frac{1}{4}})$ distribution. Therefore, if we
define $A:=\\{\forall i:|U_{\lceil\phi(x)m\rceil}-\frac{i}{m}|\leq
m^{-\frac{1}{4}}\\}$, then $\mathbb{P}[A]\geq 1-2me^{-\frac{1}{4}\sqrt{m}}$.
Note that there exists $\delta$, such that $|g(x)-g(y)|<\alpha/3$, whenever
$|x-y|<\delta$. So when $m$ is large,

$\displaystyle\mathbb{P}[\sum_{i=1}^{m}\int_{\frac{i-1}{m}}^{\frac{i}{m}}|g(U_{\lceil\phi(x)m\rceil})-g(x)|^{2}dx>\alpha/3]\leq\mathbb{P}[A^{c}]\leq
2me^{-\frac{1}{4}\sqrt{m}}.$

Therefore, by taking arbitrarily small $\epsilon$, we have that for any
$\alpha>0$,

$\displaystyle\mathbb{P}[\int_{[0,1]}|f_{k}(U_{\lceil\phi(x)m\rceil})-f_{k}(x)|^{2}dx>\alpha]\rightarrow
0.$

∎

######  Lemma 5.14.

Let $Z_{1},\cdots,Z_{m}$ be iid random vectors following the distribution
proportional to $\hat{h}_{N}^{+}$. Then there exists a measure preserving map
$\phi:[0,1]\rightarrow[0,1]$, such that

$\displaystyle\int_{[0,1]}|Z_{\lceil\phi(x)m\rceil}(i)-f_{i}(x)|^{2}dx\leq\frac{e_{0}}{4K\lambda_{1}^{2}\kappa^{2}}$

with high probability.

###### Proof.

Let $U_{1},\cdots,U_{m}$ be iid random variables following Uniform $[0,1]$
distribution. Define $W_{i}=(f_{1}(U_{i}),\cdots,f_{K}(U_{i}))$. Define
$Y_{i}=(f_{1}(U_{i})+N_{1,i},\cdots,f_{K}(U_{i})+N_{K,i})$, where $N_{j,i}$
follows a distribution proportional to $\Psi_{\delta}$ jointly independently.
We consider a coupling of $(Z_{1},\cdots,Z_{m})$ and $(Y_{1},\cdots,Y_{m})$
such that $Z_{i}\neq Y_{i}$ with probability
$1-\|\frac{\hat{h}_{N}^{+}}{\|\hat{h}_{N}^{+}\|_{1}}-u\|_{TV}$. Take $\phi$ as
in the previous lemma. Then

$\displaystyle\int_{[0,1]}|Z_{\lceil\phi(x)m\rceil}(i)-f_{i}(x)|^{2}dx$
$\displaystyle\leq$
$\displaystyle\int_{[0,1]}|W_{\lceil\phi(x)m\rceil}(i)-f_{i}(x)|^{2}dx+\int_{[0,1]}|Y_{\lceil\phi(x)m\rceil}(i)-W_{\lceil\phi(x)m\rceil}(i)|^{2}dx$
$\displaystyle+\int_{[0,1]}|Z_{\lceil\phi(x)m\rceil}(i)-Y_{\lceil\phi(x)m\rceil}(i)|^{2}dx$
$\displaystyle=$
$\displaystyle\int_{[0,1]}|W_{\lceil\phi(x)m\rceil}(i)-f_{i}(x)|^{2}dx+\frac{1}{m}\sum_{j=1}^{m}|N_{i,j}|^{2}+\frac{1}{m}\sum_{j=1}^{m}|Z_{j}(i)-Y_{j}(i)|^{2}.$

The first term is controlled by the previous lemma. For the second term, note
that each term in the summation is independent and each term satisfies
$|N_{i,j}|^{2}\leq\delta^{2}\leq\frac{e_{0}}{2^{4}K\lambda_{1}^{2}\kappa^{2}}$.
For the third term, note that with high probability,

$\displaystyle\mathbb{E}[|Z_{j}(i)-Y_{j}(i)|^{2}]\leq
4\kappa^{2}\|\frac{\hat{h}_{N}^{+}}{\|\hat{h}_{N}^{+}\|_{1}}-u\|_{TV}\leq
4\kappa^{2}\frac{e_{0}}{2^{5}K\lambda_{1}^{2}\kappa^{4}}=\frac{e_{0}}{2^{3}K\lambda_{1}^{2}\kappa^{2}}.$

All together, the statement follows. ∎

######  Lemma 5.15.

There is a measure preserving map $\phi:[0,1]\rightarrow[0,1]$, such that

$\displaystyle\int_{[0,1]^{2}}|\sum\limits_{i=1}^{K}\mu_{i}f_{i}(x)f_{i}(y)-\sum\limits_{i=1}^{K}\lambda_{i}\hat{f}_{i}(\phi(x))\hat{f}_{i}(\phi(y))|^{2}dxdy<e_{0},$

with high probability as n goes to infinity.

###### Proof.

We separate the left hand side into two terms,

$\displaystyle\int_{[0,1]^{2}}|\sum\limits_{i=1}^{K}\mu_{i}f_{i}(x)f_{i}(y)-\sum\limits_{i=1}^{K}\lambda_{i}\hat{f}_{i}(\phi(x))\hat{f}_{i}(\phi(y))|^{2}dxdy$
$\displaystyle\leq$
$\displaystyle\int_{[0,1]^{2}}|\sum\limits_{i=1}^{K}\mu_{i}f_{i}(x)f_{i}(y)-\sum\limits_{i=1}^{K}\lambda_{i}f_{i}(x)f_{i}(y)|^{2}dxdy$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{K}\int_{[0,1]^{2}}|\lambda_{i}f_{i}(x)f_{i}(y)-\lambda_{i}\hat{f}_{i}(\phi(x))\hat{f}_{i}(\phi(y))|^{2}dxdy.$

Note that with high probability the first term is bounded by
$O(\frac{1}{\log(n)})$. With high probability, the second term is bounded by

$\displaystyle\sum_{i=1}^{K}\lambda_{i}^{2}\int_{[0,1]}|f_{i}(x)|^{2}dx\int_{[0,1]}|f_{i}(y)-\hat{f}_{i}(\phi(y))|^{2}dy$
$\displaystyle+$
$\displaystyle\sum_{i=1}^{K}\lambda_{i}^{2}\int_{[0,1]}|\hat{f}_{i}(\phi(y))|^{2}dy\int_{[0,1]}|f_{i}(x)-\hat{f}_{i}(\phi(x))|^{2}dx$
$\displaystyle\leq$ $\displaystyle
2K\lambda_{1}^{2}\kappa^{2}\sup_{i\in[K]}\int_{[0,1]}|f_{i}(x)-\hat{f}_{i}(\phi(x))|^{2}dx$
$\displaystyle\leq$ $\displaystyle\frac{e_{0}}{2}.$

Therefore, the statement follows. ∎

###  5.5 Proof of the Corollary

We recall the corollary: Let $Q$ satisfy Assumptions $1$ and $2$ and assume
that all nonzero $\mu_{i}$’s are simple, then Algorithm $1$ produces an
estimator $\widehat{\mathcal{Q}_{h}}$ such that

$\displaystyle\delta_{2}(\frac{1}{h}\widehat{\mathcal{Q}_{h}},Q)\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}o_{h}(1).$

###### Proof.

Note that $\|Q_{k}-Q\|_{2}\rightarrow 0$ as $k$ goes to infinity. For any
$\epsilon>0$, take $k_{0}$ large enough such that $\|Q_{k}-Q\|_{2}<\epsilon$
for any $k\geq k_{0}$. We also know that $|\mu_{i}|\rightarrow 0$ as $i$ goes
to infinity. Take $H>\max\\{1,\frac{\mu_{1}}{\mu_{k_{0}}^{2}}\\}$. Then for
any $h\geq H$, the top $k_{0}$ eigenvalues of $\mathcal{Q}_{h}$ have
magnitudes larger than the square root of the top eigenvalue. This implies
that

$\displaystyle\delta_{2}(\frac{1}{h}\widehat{\mathcal{Q}_{h}},Q_{k_{0}})\stackrel{{\scriptstyle(P)}}{{\longrightarrow}}0,$

as $n$ goes to infinity. We also note that

$\displaystyle\delta_{2}(\frac{1}{h}\widehat{\mathcal{Q}_{h}},Q)$
$\displaystyle\leq\delta_{2}(\frac{1}{h}\widehat{\mathcal{Q}_{h}},Q_{k_{0}})+\|Q_{k_{0}}-Q\|_{2}$
$\displaystyle<\delta_{2}(\frac{1}{h}\widehat{\mathcal{Q}_{h}},Q_{k_{0}})+\epsilon.$

Therefore, the statement follows. ∎

##  6 Proof of Lemma 5.4

To prove the convergence of $\mathcal{C}_{ij}$, we need to use results in [14]
and generalized versions for graphons. In the following subsection, we cite
necessary definitions and results.

###  6.1 Some Results from [14]

In [14], the model is for constant expected degree stochastic block model.
Here are some notations that the authors use. Let $\pi=(\pi(1),\cdots,\pi(r))$
be a probability vector. Each vertex $v\in[n]$ is given a type
$\sigma(v)\in[r]$ independently according to $\pi$. The probability that two
vertices $u$ and $v$ are connected is $W(\sigma(u),\sigma(v))/n$. Set
$\Pi=diag(\pi(1),\cdots,\pi(r))$ independently. Define $M=\Pi W$. Denote
$\alpha=\sum_{i=1}^{r}\pi(i)W_{ij}=\sum_{i=1}^{r}M_{ij}$. Let $\phi_{i}$ be
normalized left eigenvectors of $M$.

######  Definition 6.1.

We consider a multi-type branching process where a particle of type $j\in[r]$
has a $\mathrm{Poi}(M_{ij})$ number of children with type $i$. We denote by
$Z_{t}=(Z_{t}(1),\dots,Z_{t}(r))$ the population at generation $t$, where
$Z_{t}(i)$ is the number of particles at generation $t$ with type $i$.

######  Definition 6.2.

We consider a functional of the multi-type branching process which depends on
particles in more than one generation. More precisely, assuming that
$\|Z_{0}\|_{1}=1$, we denote by $V$ the particles of the random tree and $o\in
V$ the starting particle. Particle $v\in V$ has type $\sigma(v)\in[r]$ and
generation $|v|$ from $o\in V$. For $v\in V$ and integer $t\geq 0$, let
$Y^{v}_{t}$ denote the set of particles of generation $t$ from $v$ in the
subtree of particles with common ancestor $v\in V$. Finally,
$Z^{v}_{t}=(Z^{v}_{t}(1),\cdots,Z^{v}_{t}(r))$ is the vector of population at
generation $t$ from $v$, i.e. $Z_{t}^{v}(i)=\sum_{u\in
Y^{v}_{t}}\mathbbm{1}(\sigma(u)=i)$. We set

$\displaystyle S^{v}_{t}=\|Z^{v}_{t}\|_{1}=\langle\phi_{1},Z^{v}_{t}\rangle.$

We fix an integer $k\in[r]$, $\ell\geq 1$ and set

$Q_{k,\ell}=\sum_{(u_{0},\ldots,u_{2\ell+1})\in{\mathcal{P}}_{2\ell+1}}\phi_{k}(\sigma(u_{2\ell+1})),$

where the sum is over $(u_{0},\ldots,u_{2\ell+1})\in{\mathcal{P}}_{2\ell+1}$,
the set of paths in the tree starting from $u_{0}=o$ of length $2\ell+1$ with
$(u_{0},\ldots,u_{\ell})$ and $(u_{\ell},\ldots,u_{2\ell+1})$ non-backtracking
and $u_{\ell-1}=u_{\ell+1}$ (i.e. $(u_{0},\ldots,u_{2\ell+1})$ backtracks
exactly once at the $\ell+1$-th step).

The following alternative representation of $Q_{k,\ell}$ will prove useful. By
distinguishing paths $(u_{0},\ldots,u_{2\ell+1})$ according to the smallest
depth $t\in\\{0,\ldots,\ell-1\\}$ to which they climb back after visiting
$u_{\ell+1}$ and the node $u_{2\ell-t}$ they then visit at level $t$ we have
that

$Q_{k,\ell}=\sum_{t=0}^{\ell-1}\sum_{u\in Y^{o}_{t}}L_{k,\ell}^{u},$

where we let for $|u|=t\geq 0$,

$\displaystyle L^{u}_{k,\ell}=\sum_{w\in
Y^{u}_{1}}S^{w}_{\ell-t-1}\left(\sum_{v\in
Y^{u}_{1}\backslash\\{w\\}}\langle\phi_{k},Z^{v}_{t}\rangle\right).$

######  Definition 6.3.

Let $Z_{t}$, $t\geq 0$, be the Galton-Watson branching process defined above
started from $Z_{0}=\delta_{\iota}$. We denote by $(T,o)$ the associated
random rooted tree. Let $D$ be the number of offspring of the root and for
$1\leq x\leq D$, let $Q_{k,\ell}(x)$ be the random variable $Q_{k,\ell}$
defined on the tree $T^{x}$ where the subtree attached to $x$ is removed and
set

$\displaystyle J_{k,\ell}=\sum_{x=1}^{D}Q_{k,\ell}(x).$

######  Lemma 6.1 (Lemma 41 in [14]).

We have
$J_{k,\ell}\mu_{k}^{-2\ell}-\alpha\mu_{k}\phi_{k}(\iota)/(\mu_{k}^{2}/\alpha-1)$
converges in $L^{2}$ to a centered variable $Y_{k}$ satisfying
$\mathbb{E}|Y_{k}|\leq C$.

This lemma is proved by applying the following theorem.

######  Theorem 6.2 (Theorem 25 in [14]).

Assume $Z_{0}=\delta_{x}$. For $k\in[r_{0}]$, $Q_{k,\ell}/\mu_{k}^{2\ell}$
converges in $L^{2}$ as $\ell$ tends to infinity to a random variable with
mean $\mu_{k}\phi_{k}(x)/(\mu_{k}^{2}/\alpha-1)$. For
$k\in[r]\backslash[r_{0}]$, there exists a constant $C$ such that
$\mathbb{E}Q_{k,\ell}^{2}\leq C\alpha^{2\ell}\ell^{5}$.

######  Definition 6.4.

For $e,f\in\vec{E}(V)$, we define the ”oriented” distance

$\displaystyle\vec{d}(e,f)=\min_{\gamma}\ell(\gamma)$

where the minimum is taken over all self-avoiding paths
$\gamma=(\gamma_{0},\gamma_{1},\cdots,\gamma_{\ell+1})$ in $G$ such that
$(\gamma_{0},\gamma_{1})=e$, $(\gamma_{\ell},\gamma_{\ell+1})=f$ and for all
$1\leq k\leq\ell+1$, $\\{\gamma_{k},\gamma_{k+1}\\}\in E$ (we do not require
that $e\in\vec{E}$). Observe that $\vec{d}$ is not symmetric, we have instead
$\vec{d}(e,f)=\vec{d}(f^{-1},e^{-1})$.

Then, for integer $t\geq 0$, we introduce the vector
$Y_{t}(e)=(Y_{t}(e)(i))_{i\in[r]}$ where, for $i\in[r]$,

$Y_{t}(e)(i)={{\left|\left\\{f\in\vec{E}:\vec{d}(e,f)=t,\sigma(f_{2})=i\right\\}\right|}}.$

We also set

$\displaystyle
S_{t}(e)=\|Y_{t}(e)\|_{1}={{\left|\left\\{f\in\vec{E}:\vec{d}(e,f)=t\right\\}\right|}}.$

The vector $Y_{t}(e)$ counts the types at oriented distance $t$ from $e$.

######  Definition 6.5.

For $e\in\vec{E}(V)$, we define for $t\geq 0$,
$\mathcal{Y}_{t}(e)=\\{f\in\vec{E}:\vec{d}(e,f)=t\\}$. For $k\in[r]$, we set

$P_{k,\ell}(e)=\sum_{t=0}^{\ell-1}\sum_{f\in\mathcal{Y}_{t}(e)}L_{k}(f).$

where

$\displaystyle
L_{k}(f)=\sum_{(g,h)\in\mathcal{Y}_{1}(f)\backslash\mathcal{Y}_{t}(e);g\neq
h}\langle\phi_{k},\tilde{Y}_{t}(g)\rangle\tilde{S}_{\ell-t-1}(h),$

and $\tilde{Y}_{t}(g)$,
$\tilde{S}_{\ell-t-1}(h)=\|\tilde{Y}_{\ell-t-1}(h)\|_{1}$ are the variables
$Y_{t}(g)$, $S_{\ell-t-1}(h)$ defined on the graph $G$ where all edges in
$(G,e_{2})_{t}$ have been removed. In particular, if $(G,e)_{2\ell}$ is a
tree, $\tilde{Y}_{s}(g)$ and $Y_{s}(g)$ coincide for $s\leq 2\ell-t$.

######  Definition 6.6.

We introduce a new random variable, for $v\in V$,

$\displaystyle I_{k,\ell}(v)=\sum_{e\in\vec{E}:e_{2}=v}P_{k,\ell}(e),$

where $P_{k,\ell}$ was defined above.

######  Proposition 6.3 (Proposition 36 in [14]).

Let $\ell\sim\kappa\log_{\alpha}n$ with $0<\kappa<1/2$. There exists $c>0$,
such that if $\tau,\varphi:\mathcal{G}^{*}\to\mathbb{R}$ are $\ell$-local,
$|\tau(G,o)|\leq\varphi(G,o)$ and $\varphi$ is non-decreasing by the addition
of edges, then if $\mathbb{E}\varphi(T,o)$ is finite,

$\displaystyle\mathbb{E}{{\left|\frac{1}{n}\sum_{v=1}^{n}\tau(G,v)-\mathbb{E}\tau(T,o)\right|}}$
$\displaystyle\leq$ $\displaystyle c\frac{\alpha^{\ell/2}\sqrt{\log
n}}{n^{\gamma/2}}{{\left({{\left(\mathbb{E}\max_{v\in[n]}\varphi^{4}(G,v)\right)}}^{1/4}\vee{{\left(\mathbb{E}\varphi^{2}(T,o)\right)}}^{1/2}\right)}},$

where $(T,o)$ is the random rooted tree associated to the Galton-Watson
branching process defined previously started from $Z_{0}=\delta_{\iota}$ and
$\iota$ has distribution $(\pi(1),\ldots,\pi(r))$. Here
$0<\gamma<\frac{1}{2}$.

Below are two lemmas to control the growth of $S$. Recall that $S_{t}$ is a
Galton-Walton branching process with offspring distribution
$\mathrm{Poi}(\mu_{1})$.

######  Lemma 6.4 (Lemma 23 in [14]).

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

$\displaystyle\mathbb{P}(\forall k\geq 1,S_{k}\leq s\mu_{1}^{k})\geq
1-c_{1}e^{-c_{0}s}.$

We shall denote by $S_{t}(v)$ the set of vertices at distance $t$ from $v$. We
introduce

$\displaystyle
n(i)=\sum_{v=1}^{n}\mathbbm{1}(\sigma(v)=i),\quad\quad\pi_{n}(i)=\frac{n(i)}{n},$
$\displaystyle\alpha_{n}(i)=\sum_{j=1}^{r}\pi_{n}(i)W_{ij},\quad\quad\bar{\alpha}_{n}=\max_{i\in[r]}\alpha_{n}(i)=\alpha+O(n^{-\gamma}),$

######  Lemma 6.5 (Lemma 29 in [14]).

There exist $c_{0},c_{1}>0$ such that for all $s\geq 0$ and for any
$w\in[n]\cup\vec{E}(V)$,

$\displaystyle\mathbb{P}\left(\forall t\geq 0:S_{t}(w)\leq
s\bar{\alpha}_{n}^{t}\right)\geq 1-c_{1}e^{-c_{0}s}.$

Consequently, for any $p\geq 1$, there exists $c>0$ such that

$\displaystyle\mathbb{E}\max_{v\in[n],t\geq
0}\left(\frac{S_{t}(v)}{\bar{\alpha}^{t}_{n}}\right)^{p}\leq c(\log n)^{p}.$

######  Proposition 6.6 (Proposition 38 in [14]).

Let $\ell\sim\kappa\log_{\alpha}n$ with $0<\kappa<\gamma/5$. For any
$k\in[r_{0}]$, there exists $\rho^{\prime}_{k}>0$ such that w.h.p.

$\displaystyle\frac{1}{\alpha
n}\sum_{e\in\vec{E}}\frac{P^{2}_{k,\ell}(e)}{\mu_{k}^{4\ell}}\to\rho^{\prime}_{k}.$

######  Definition 6.7.

We set

$\displaystyle I_{k}(v)=\sum_{e:e_{2}=v}s\sqrt{n}\xi_{k}^{\prime}(e),$

where $s=\sqrt{\alpha\rho^{\prime}_{k}}$ and $\rho^{\prime}_{k}$ was defined
above and $\xi^{\prime}$ is an orientation of $\xi$.

######  Lemma 6.7 (Lemma 42 in [14]).

We have that w.h.p.

$\displaystyle\frac{1}{n}\sum_{v=1}^{n}{{\left|I_{k}(v)-\frac{I_{k,\ell}(v)}{\mu_{k}^{2\ell}}\right|}}=o(1).$

###  6.2 Corresponding Results for Graphon

This subsection contains corresponding definitions and results for graphons.
The proofs are similar as in [14], so we omit it here. For a vertex $v$, we
use $X_{v}$ or $X(v)\in[0,1]$ to denote its type. We denote $\alpha=\mu_{1}$.

######  Definition 6.8.

We consider a branching process where a particle of type $x\in[0,1]$ has
$\mathrm{Poi}(\mu_{1})$ number of children, where their types follow the
distribution $Q(x,\cdot)/\mu_{1}$ independently.

######  Definition 6.9.

We consider a functional of the branching process which depends on particles
in more than one generation. We denote by $V$ the particles of the random tree
and $o\in V$ the starting particle. Particle $v\in V$ has type $X_{v}\in[0,1]$
and generation $|v|$ from $o\in V$. For $v\in V$ and integer $t\geq 0$, let
$Y^{v}_{t}$ denote the set of particles of generation $t$ from $v$ in the
subtree of particles with common ancestor $v\in V$. We set
$S^{v}_{t}=|Y_{t}^{v}|$. We fix an integer $k\in[r_{0}]$, $\ell\geq 1$ and set

$Q_{k,\ell}=\sum_{(u_{0},\ldots,u_{2\ell+1})\in{\mathcal{P}}_{2\ell+1}}f_{k}(X(u_{2\ell+1})),$

where the sum is over $(u_{0},\ldots,u_{2\ell+1})\in{\mathcal{P}}_{2\ell+1}$,
the set of paths in the tree starting from $u_{0}=o$ of length $2\ell+1$ with
$(u_{0},\ldots,u_{\ell})$ and $(u_{\ell},\ldots,u_{2\ell+1})$ non-backtracking
and $u_{\ell-1}=u_{\ell+1}$ (i.e. $(u_{0},\ldots,u_{2\ell+1})$ backtracks
exactly once at the $\ell+1$-th step).

The following alternative representation of $Q_{k,\ell}$ will prove useful. By
distinguishing paths $(u_{0},\ldots,u_{2\ell+1})$ according to the smallest
depth $t\in\\{0,\ldots,\ell-1\\}$ to which they climb back after visiting
$u_{\ell+1}$ and the node $u_{2\ell-t}$ they then visit at level $t$ we have
that

$Q_{k,\ell}=\sum_{t=0}^{\ell-1}\sum_{u\in Y^{o}_{t}}L_{k,\ell}^{u},$

where we let for $|u|=t\geq 0$,

$\displaystyle L^{u}_{k,\ell}=\sum_{w\in
Y^{u}_{1}}S^{w}_{\ell-t-1}\left(\sum_{v\in
Y^{u}_{1}\backslash\\{w\\}}\sum_{w^{\prime}\in
Y_{t}^{v}}f_{k}(X_{w^{\prime}})\right).$

######  Definition 6.10.

Consider the branching process defined above started from $X(o)=x$. We denote
by $(T,o)$ the associated random rooted tree. Let $D$ be the number of
offspring of the root and for $1\leq y\leq D$, let $Q_{k,\ell}(y)$ be the
random variable $Q_{k,\ell}$ defined on the tree $T^{y}$ where the subtree
attached to $y$ is removed and set

$\displaystyle J_{k,\ell}=\sum_{x=1}^{D}Q_{k,\ell}(y).$

######  Lemma 6.8.

Consider the branching process defined above started from $X(o)=x$. For
$k\in[r_{0}]$, we have
$J_{k,\ell}\mu_{k}^{-2\ell}-\alpha\mu_{k}f_{k}(x)/(\mu_{k}^{2}/\alpha-1)$
converges in $L^{2}$ to a centered variable $Y_{k,x}$ satisfying
$\mathbb{E}|Y_{k,x}|\leq C$ uniformly for $x\in[0,1]$.

This lemma is proved by applying the following theorem.

######  Theorem 6.9.

Consider the branching process defined above started from $X(o)=x$. For
$k\in[r_{0}]$, $Q_{k,\ell}/\mu_{k}^{2\ell}$ converges in $L^{2}$ as $\ell$
tends to infinity to a random variable with mean
$\mu_{k}\phi_{k}(x)/(\mu_{k}^{2}/\alpha-1)$.

######  Definition 6.11.

For $e,f\in\vec{E}(V)$, we define the ”oriented” distance

$\displaystyle\vec{d}(e,f)=\min_{\gamma}\ell(\gamma)$

where the minimum is taken over all self-avoiding paths
$\gamma=(\gamma_{0},\gamma_{1},\cdots,\gamma_{\ell+1})$ in $G$ such that
$(\gamma_{0},\gamma_{1})=e$, $(\gamma_{\ell},\gamma_{\ell+1})=f$ and for all
$1\leq k\leq\ell+1$, $\\{\gamma_{k},\gamma_{k+1}\\}\in E$ (we do not require
that $e\in\vec{E}$). Observe that $\vec{d}$ is not symmetric, we have instead
$\vec{d}(e,f)=\vec{d}(f^{-1},e^{-1})$.

Then, for integer $t\geq 0$, we set

$\displaystyle
S_{t}(e)={{\left|\left\\{f\in\vec{E}:\vec{d}(e,f)=t\right\\}\right|}}.$

######  Definition 6.12.

For $e\in\vec{E}(V)$, we define for $t\geq 0$,
$\mathcal{Y}_{t}(e)=\\{f\in\vec{E}:\vec{d}(e,f)=t\\}$. For $k\in[r_{0}]$, we
set

$P_{k,\ell}(e)=\sum_{t=0}^{\ell-1}\sum_{e^{\prime}\in\mathcal{Y}_{t}(e)}L_{k}(e^{\prime}).$
(3)

where

$\displaystyle
L_{k}(e^{\prime})=\sum_{(g,h)\in\mathcal{Y}_{1}(e^{\prime})\backslash\mathcal{Y}_{t}(e);g\neq
h}\sum_{e^{\prime\prime}\in\tilde{\mathcal{Y}}_{t}(g)}f_{k}(X_{e^{\prime\prime}_{2}})\tilde{S}_{\ell-t-1}(h),$

and $\tilde{\mathcal{Y}}_{t}(g)$, $\tilde{S}_{\ell-t-1}(h)$ are the variables
$\mathcal{Y}_{t}(g)$, $S_{\ell-t-1}(h)$ defined on the graph $G$ where all
edges in $(G,e_{2})_{t}$ have been removed.

######  Definition 6.13.

We introduce a new random variable, for $v\in V$,

$\displaystyle I_{k,\ell}(v)=\sum_{e\in\vec{E}:e_{2}=v}P_{k,\ell}(e),$

where $P_{k,\ell}$ was defined above.

######  Proposition 6.10.

Let $\ell\sim\kappa\log_{\alpha}n$ with $0<\kappa<1/2$. There exists $c>0$,
such that if $\tau,\varphi:\mathcal{G}^{*}\to\mathbb{R}$ are $\ell$-local,
$|\tau(G,o)|\leq\varphi(G,o)$ and $\varphi$ is non-decreasing by the addition
of edges, then if $\mathbb{E}\varphi(T,o)$ is finite,

$\displaystyle\mathbb{E}{{\left|\frac{1}{n}\sum_{v=1}^{n}\tau(G,v)-\mathbb{E}\tau(T,o)\right|}}$
$\displaystyle\leq$ $\displaystyle c\frac{\alpha^{\ell/2}\sqrt{\log
n}}{n^{\gamma/2}}{{\left({{\left(\mathbb{E}\max_{v\in[n]}\varphi^{4}(G,v)\right)}}^{1/4}\vee{{\left(\mathbb{E}\varphi^{2}(T,o)\right)}}^{1/2}\right)}},$

where $(T,o)$ is the random rooted tree associated to the Galton-Watson
branching process defined previously started from $X(o)=\iota$ and $\iota$ has
distribution Uniform $[0,1]$. Here $0<\gamma<\frac{1}{2}$.

Recall that $S_{t}$ is a Galton-Walton branching process with offspring
distribution $\mathrm{Poi}(\mu_{1})$.

######  Lemma 6.11.

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

$\displaystyle\mathbb{P}(\forall k\geq 1,S_{k}\leq s\mu_{1}^{k})\geq
1-c_{1}e^{-c_{0}s}.$

We shall denote by $S_{t}(v)$ the set of vertices at distance $t$ from $v$. We
introduce

$\displaystyle\bar{\alpha}_{n}=\frac{1}{n}\max_{i\in[n]}\sum_{j=1}^{n}Q(X_{i},X_{j})=\alpha+O(n^{-\gamma}).$
(4)

######  Lemma 6.12.

There exist $c_{0},c_{1}>0$ such that for all $s\geq 0$ and for any
$w\in[n]\cup\vec{E}(V)$,

$\displaystyle\mathbb{P}\left(\forall t\geq 0:S_{t}(w)\leq
s\bar{\alpha}_{n}^{t}\right)\geq 1-c_{1}e^{-c_{0}s}.$

Consequently, for any $p\geq 1$, there exists $c>0$ such that

$\displaystyle\mathbb{E}\max_{v\in[n],t\geq
0}\left(\frac{S_{t}(v)}{\bar{\alpha}^{t}_{n}}\right)^{p}\leq c(\log n)^{p}.$

######  Proposition 6.13.

Let $\ell\sim\kappa\log_{\alpha}n$ with $0<\kappa<\gamma/5$. For any
$k\in[r_{0}]$, there exists $\rho^{\prime}_{k}>0$ such that w.h.p.

$\displaystyle\frac{1}{\alpha
n}\sum_{e\in\vec{E}}\frac{P^{2}_{k,\ell}(e)}{\mu_{k}^{4\ell}}\to\rho^{\prime}_{k}.$

######  Definition 6.14.

We set

$\displaystyle I_{k}(v)=\sum_{e:e_{2}=v}s\sqrt{n}\xi_{k}^{\prime}(e),$

where $s=\sqrt{\alpha\rho^{\prime}_{k}}$ and $\rho^{\prime}_{k}$ was defined
above and $\xi^{\prime}$ is an orientation of $\xi$.

######  Lemma 6.14.

We have that w.h.p.

$\displaystyle\frac{1}{n}\sum_{v=1}^{n}{{\left|I_{k}(v)-\frac{I_{k,\ell}(v)}{\mu_{k}^{2\ell}}\right|}}=o(1).$

###  6.3 Proof of Lemma 5.4

Recall that

$\displaystyle\mathcal{C}_{ij}:=\frac{1}{\sqrt{n}}\sum\limits_{\ell=1}^{n}B_{i}(V_{\ell})f_{j}(X_{\ell}).$

Define $J_{k,\ell}$ as before with the transition kernel being
$(1-\epsilon)Q$. We use $J_{k,\ell}(x)$ to emphasize that the branching
process starts at $X(o)=x$. By Lemma 6.8, we have that
$J_{k,\ell}(x)\mu_{k}^{-2\ell}-\alpha\mu_{k}f_{k}(x)/(\mu_{k}^{2}/\alpha-1)$
converges in $L_{2}$ to a centered variable $Y_{k,x}$ satisfying
$\mathbb{E}|Y_{k,x}|\leq C$ uniformly for $x\in[0,1]$. Define

$\displaystyle
H_{k,\ell}=\mu_{k}^{-2\ell}\int_{0}^{1}J_{k,\ell}(x)f_{k}(x)dx,$

and

$\displaystyle H_{k,\ell,2}$
$\displaystyle=\mu_{k}^{-4\ell}\int_{[0,1]^{2}}J_{k,\ell}(x)J_{k,\ell}(y)Q(x,y)dxdy.$

Then $\mathbb{E}[H_{k,\ell}]\rightarrow\alpha\mu_{k}/(\mu_{k}^{2}/\alpha-1)$
and
$\mathbb{E}[H_{k,\ell,2}]\rightarrow\mu_{k}(\alpha\mu_{k}/(\mu_{k}^{2}/\alpha-1))^{2}$.
Recall the definition of $P_{k,\ell}(e)$ above. Recall that

$\displaystyle I_{k,\ell}(v)=\sum_{e\in\vec{E}:e_{2}=v}P_{k,\ell}(e).$

We define

$\displaystyle G_{k,\ell}=\mu_{k}^{-2\ell}\frac{1}{n}\sum_{v\in
V}I_{k,\ell}(v)f_{k}(X_{v}),$

and

$\displaystyle G_{k,\ell,2}$
$\displaystyle=\mu_{k}^{-4\ell}\frac{1}{n^{2}}\sum_{u,v\in
V}I_{k,\ell}(u)I_{k,\ell}(v)Q(X_{u},X_{v}).$

Now, we apply Proposition 6.10. Take $\tau(G,v)$ as
$\mu_{k}^{-2\ell}I_{k,\ell}(v)f_{k}(X_{v})$. Let

$\displaystyle N(v)=\max_{0\leq t\leq\ell}\max_{u\in(G,v)_{t}}\max_{s\leq
2\ell-t}(S_{s}(u)/\alpha^{s}).$

As we have $\mu_{k}^{2}>\alpha$, by definition of $I_{k,\ell}$,

$\displaystyle\tau(G,v)$
$\displaystyle\leq\alpha^{-\ell}\frac{M}{\sqrt{\alpha}}\sum_{e\in\vec{E},e_{2}=v}\left(\sum_{t=0}^{\ell-1}\sum_{f\in\mathcal{Y}_{t}(e)}N^{2}(v)\alpha^{t+1}\alpha^{\ell-t}\right)$
$\displaystyle=N^{2}(v)\alpha\frac{M}{\sqrt{\alpha}}\sum_{e\in\vec{E},e_{2}=v}\left(\sum_{t=0}^{\ell-1}\sum_{f\in\mathcal{Y}_{t}(e)}1\right).$

Hence $\tau(G,v)\leq CN(v)^{3}\alpha^{\ell}=:\varphi(G,v)$. Then by Lemma
6.12, we have
$\mathbb{E}[\max_{v}\varphi(G,v)^{4}]=O(\log(n)^{12}\alpha^{4\ell})$. By Lemma
6.11 the same holds for $\varphi(T,o)$. Therefore, by Proposition 6.10, we
have that

$\displaystyle\mathbb{E}|G_{k,\ell}-\mathbb{E}H_{k,\ell}|=o(1).$

Similarly, we consider $|G_{k,\ell,2}-\mathbb{E}H_{k,\ell,2}|$, which equals

$\displaystyle\left|\mu_{k}^{-4\ell}\frac{1}{n^{2}}\sum_{u,v\in
V}I_{k,\ell}(u)I_{k,\ell}(v)Q(X_{u},X_{v})-\mathbb{E}H_{k,\ell,2}\right|$
$\displaystyle\leq$ $\displaystyle\mu_{k}^{-2\ell}\frac{1}{n}\sum_{u\in
V}I_{k,\ell}(u)\left|\left(\mu_{k}^{-2\ell}\frac{1}{n}\sum_{v\in
V}I_{k,\ell}(v)Q(X_{u},X_{v})-\mathbb{E}[\mu_{k}^{-2\ell}\int_{[0,1]}J_{k,\ell}Q(X_{u},y)dy]\right)\right|$
$\displaystyle+$ $\displaystyle\left|\mu_{k}^{-2\ell}\frac{1}{n}\sum_{u\in
V}I_{k,\ell}(u)\mathbb{E}[\mu_{k}^{-2\ell}\int_{[0,1]}J_{k,\ell}Q(X_{u},y)dy]-\mathbb{E}[\mu_{k}^{-4\ell}\int_{[0,1]^{2}}J_{k,\ell}(x)J_{k,\ell}(y)Q(x,y)dxdy]\right|.$

We apply Proposition 6.10 to both terms and take $\varphi$ similarly as above.
So we have that

$\displaystyle\mathbb{E}|G_{k,\ell,2}-\mathbb{E}H_{k,\ell,2}|\rightarrow 0,$

as $n$ goes to infinity. This implies that $G_{k,\ell}$ converges to
$\alpha\mu_{k}/(\mu_{k}^{2}/\alpha-1)$ in probability. Further, $G_{k,\ell,2}$
converges to $\mu_{k}(\alpha\mu_{k}/(\mu_{k}^{2}/\alpha-1))^{2}$ in
probability. Recall the definition of

$\displaystyle I_{k}(v)=\sum_{e:e_{2}=v}s\sqrt{n}\xi^{\prime}_{k}(e),$

where $s=\sqrt{\alpha\rho_{k}^{\prime}}$ and $\rho_{k}^{\prime}$ was defined
above, and $\xi^{\prime}_{k}$ being an orientation of $\xi_{k}$. Let
$O_{k}\in\\{-1,1\\}$ such that $\xi^{\prime}_{k}(e)=O_{k}\xi_{k}(e)$. By Lemma
6.14, we have that

$\displaystyle\frac{1}{n}\sum_{v=1}^{n}|I_{k}(v)-\frac{I_{k,\ell}}{\mu_{k}^{2\ell}}|=o(1).$

This implies that

$\displaystyle\left|O_{k}\mathcal{C}_{kk}-\frac{G_{k,\ell}}{s}\right|$
$\displaystyle=\left|O_{k}\mathcal{C}_{kk}-\frac{1}{sn}\sum_{v\in
V}f_{k}(X_{v})\frac{I_{k,\ell}}{\mu_{k}^{2\ell}}\right|$
$\displaystyle=\left|\frac{1}{n}\sum_{v\in
V}f_{k}(X_{v})\sum_{e:e_{2}=v}\sqrt{n}\xi^{\prime}_{k}(e)-\frac{1}{sn}\sum_{v\in
V}f_{k}(X_{v})\frac{I_{k,\ell}}{\mu_{k}^{2\ell}}\right|$
$\displaystyle=\left|\frac{1}{sn}\sum_{v\in
V}f_{k}(X_{v})I_{k}(v)-\frac{1}{sn}\sum_{v\in
V}f_{k}(X_{v})\frac{I_{k,\ell}}{\mu_{k}^{2\ell}}\right|$
$\displaystyle\leq\sup f_{k}\frac{1}{sn}\sum_{v\in
V}\left|I_{k}(v)-\frac{I_{k,\ell}}{\mu_{k}^{2\ell}}\right|=o(1).$

Further,

$\displaystyle\left|\sum_{i=1}^{\infty}\mu_{i}\mathcal{C}_{ki}^{2}-\frac{G_{k,\ell,2}}{s}\right|$
$\displaystyle=\left|\frac{1}{s^{2}n^{2}}\sum_{u,v\in
V}Q(X_{v},X_{u})(I_{k}(v)-\frac{I_{k,\ell}(v)}{\mu_{k}^{2\ell}})(I_{k}(u)+\frac{I_{k,\ell}(u)}{\mu_{k}^{2\ell}})\right|$
$\displaystyle\leq\frac{M}{s^{2}n^{2}}\sum_{u,v\in
V}\left|I_{k}(v)-\frac{I_{k,\ell}(v)}{\mu_{k}^{2\ell}}\right|\left|I_{k}(u)+\frac{I_{k,\ell}(u)}{\mu_{k}^{2\ell}}\right|=o(1).$

Therefore, the statement follows.

## References

  * [1] E. Abbe, E. Boix, P. Ralli and C. Sandon  “Graph powering and spectral robustness”  In _SIAM Journal on Mathematics of Data Science_ , 2019
  * [2] E. Abbe and C. Sandon  “Recovering Communities in the General Stochastic Block Model Without Knowing the Parameters”  In _Advances in Neural Information Processing Systems (NIPS) 28_ Curran Associates, Inc., 2015, pp. 676–684
  * [3] Emmanuel Abbe  “Community detection and stochastic block models: recent developments”  In _The Journal of Machine Learning Research_ 18.1 JMLR. org, 2017, pp. 6446–6531
  * [4] Emmanuel Abbe and Colin Sandon  “Community detection in general stochastic block models: Fundamental limits and efficient algorithms for recovery”  In _2015 IEEE 56th Annual Symposium on Foundations of Computer Science_ , 2015, pp. 670–688  IEEE
  * [5] Emmanuel Abbe and Colin Sandon  “Proof of the Achievability Conjectures for the General Stochastic Block Model”  In _Communications on Pure and Applied Mathematics_ 71.7, 2017, pp. 1334–1406  DOI: 10.1002/cpa.21719
  * [6] Emmanuel Abbe and Colin Sandon  “Recovering communities in the general stochastic block model without knowing the parameters”  In _Advances in neural information processing systems_ , 2015, pp. 676–684
  * [7] Edo M Airoldi, Thiago B Costa and Stanley H Chan  “Stochastic blockmodel approximation of a graphon: Theory and consistent estimation”  In _Advances in Neural Information Processing Systems_ , 2013, pp. 692–700
  * [8] Arash A. Amini, Aiyou Chen, Peter J. Bickel and Elizaveta Levina  “Pseudo-likelihood methods for community detection in large sparse networks”  In _Ann. Statist._ 41.4 The Institute of Mathematical Statistics, 2013, pp. 2097–2122  DOI: 10.1214/13-AOS1138
  * [9] Animashree Anandkumar, Rong Ge, Daniel Hsu and Sham M Kakade  “A tensor approach to learning mixed membership community models”  In _The Journal of Machine Learning Research_ 15.1 JMLR. org, 2014, pp. 2239–2312
  * [10] Peter J Bickel and Aiyou Chen  “A nonparametric view of network models and Newman–Girvan and other modularities”  In _Proceedings of the National Academy of Sciences_ 106.50 National Acad Sciences, 2009, pp. 21068–21073
  * [11] Peter J Bickel, Aiyou Chen and Elizaveta Levina  “The method of moments and degree distributions for network models”  In _The Annals of Statistics_ 39.5 Institute of Mathematical Statistics, 2011, pp. 2280–2301
  * [12] Béla Bollobás, Svante Janson and Oliver Riordan  “The Phase Transition in Inhomogeneous Random Graphs”  In _Random Struct. Algorithms_ 31.1 New York, NY, USA: John Wiley & Sons, Inc., 2007, pp. 3–122  DOI: 10.1002/rsa.v31:1
  * [13] R.B. Boppana  “Eigenvalues and graph bisection: An average-case analysis”  In _In 28th Annual Symposium on Foundations of Computer Science_ , 1987, pp. 280–285
  * [14] Charles Bordenave, Marc Lelarge and Laurent Massoulié  “Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs”  In _The Annals of Probability_ 46.1 Institute of Mathematical Statistics, 2018, pp. 1–71
  * [15] Christian Borgs, Jennifer T Chayes, Henry Cohn and Shirshendu Ganguly  “Consistent nonparametric estimation for heavy-tailed sparse graphs”  In _arXiv preprint arXiv:1508.06675_ , 2015
  * [16] Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós and Katalin Vesztergombi  “Convergent sequences of dense graphs I: Subgraph frequencies, metric properties and testing”  In _Advances in Mathematics_ 219.6 Elsevier, 2008, pp. 1801–1851
  * [17] Christian Borgs, Jennifer T Chayes, László Lovász, Vera T Sós and Katalin Vesztergombi  “Convergent sequences of dense graphs II. Multiway cuts and statistical physics”  In _Annals of Mathematics_ JSTOR, 2012, pp. 151–219
  * [18] Christian Borgs, Jennifer Chayes and Adam Smith  “Private graphon estimation for sparse graphs”  In _Advances in Neural Information Processing Systems_ , 2015, pp. 1369–1377
  * [19] T.N. Bui, S. Chaudhuri, F.T. Leighton and M. Sipser  “Graph bisection algorithms with good average case behavior”  In _Combinatorica_ 7.2 Springer-Verlag, 1987, pp. 171–191  DOI: 10.1007/BF02579448
  * [20] David S Choi, Patrick J Wolfe and Edoardo M Airoldi  “Stochastic blockmodels with a growing number of classes”  In _Biometrika_ 99.2 Oxford University Press, 2012, pp. 273–284
  * [21] Aurelien Decelle, Florent Krzakala, Cristopher Moore and Lenka Zdeborová  “Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications”  In _Physical Review E_ 84.6 APS, 2011, pp. 066106
  * [22] Chao Gao, Yu Lu and Harrison H Zhou  “Rate-optimal graphon estimation”  In _The Annals of Statistics_ 43.6 Institute of Mathematical Statistics, 2015, pp. 2624–2652
  * [23] P.. Holland, K. Laskey and S. Leinhardt  “Stochastic blockmodels: First steps”  In _Social Networks_ 5.2, 1983, pp. 109–137  URL: http://d.wanfangdata.com.cn/NSTLQK%5C_10.1016-0378-8733(83)90021-7.aspx
  * [24] Olav Kallenberg  “Multivariate sampling and the estimation problem for exchangeable arrays”  In _Journal of Theoretical Probability_ 12.3 Springer, 1999, pp. 859–883
  * [25] Olga Klopp, Alexandre B Tsybakov and Nicolas Verzelen  “Oracle inequalities for network models and sparse graphon estimation”  In _The Annals of Statistics_ 45.1 Institute of Mathematical Statistics, 2017, pp. 316–354
  * [26] Michael Krivelevich and Benny Sudakov  “The largest eigenvalue of sparse random graphs”  In _Combinatorics, Probability and Computing_ 12.1 Cambridge University Press, 2003, pp. 61–72
  * [27] Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborova and Pan Zhang  “Spectral redemption in clustering sparse networks”  In _Proceedings of the National Academy of Sciences_ 110.52, 2013, pp. 20935–20940  DOI: 10.1073/pnas.1312486110
  * [28] Laurent Massoulié  “Community detection thresholds and the weak Ramanujan property”  In _Proceedings of the forty-sixth annual ACM symposium on Theory of computing_ , 2014, pp. 694–703
  * [29] M.E. and A.M.  “The solution of some random NP-hard problems in polynomial expected time”  In _Journal of Algorithms_ 10.4, 1989, pp. 451–489  DOI: 10.1016/0196-6774(89)90001-1
  * [30] Elchanan Mossel, Joe Neeman and Allan Sly  “Reconstruction and estimation in the planted partition model”  In _Probability Theory and Related Fields_ 162.3-4 Springer, 2015, pp. 431–461
  * [31] Karl Rohe, Sourav Chatterjee and Bin Yu  “Spectral clustering and the high-dimensional stochastic blockmodel”  In _The Annals of Statistics_ 39.4 Institute of Mathematical Statistics, 2011, pp. 1878–1915
  * [32] Giorgio Talenti  “Recovering a function from a finite number of moments”  In _Inverse problems_ 3.3 IOP Publishing, 1987, pp. 501
  * [33] Patrick J Wolfe and Sofia C Olhede  “Nonparametric graphon estimation”  In _arXiv preprint arXiv:1309.5936_ , 2013
  * [34] Jiaming Xu, Laurent Massoulié and Marc Lelarge  “Edge label inference in generalized stochastic block models: from spectral theory to impossibility results”  In _Conference on Learning Theory_ , 2014, pp. 903–920
  * [35] Yuan Zhang, Elizaveta Levina and Ji Zhu  “Estimating network edge probabilities by neighbourhood smoothing”  In _Biometrika_ 104.4 Oxford University Press, 2017, pp. 771–783
  * [36] Yunpeng Zhao, Elizaveta Levina and Ji Zhu  “Consistency of community detection in networks under degree-corrected stochastic block models”  In _Ann. Statist._ 40.4 The Institute of Mathematical Statistics, 2012, pp. 2266–2292  DOI: 10.1214/12-AOS1036