# Uncertainty quantification in the stochastic block model with an unknown
number of classes

J. van Waaij The first author is supported by the University of Padova under
the STARS Grant<EMAIL_ADDRESS>B.J.K. Kleijn<EMAIL_ADDRESS>
###### Abstract

We study the frequentist properties of Bayesian statistical inference for the
stochastic block model, with an unknown number of classes of varying sizes. We
equip the space of vertex labellings with a prior on the number of classes
and, conditionally, a prior on the labels. The number of classes may grow to
infinity as a function of the number of vertices, depending on the sparsity of
the graph. We derive non-asymptotic posterior contraction rates of the form
$P_{\theta_{0,n}}\Pi_{n}(B_{n}\mid X^{n})\leq{\varepsilon}_{n}$, where $X^{n}$
is the observed graph, generated according to $P_{\theta_{0,n}}$, $B_{n}$ is
either $\left\\{\theta_{0,n}\right\\}$ or, in the very sparse case, a ball
around $\theta_{0,n}$ of known extent, and ${\varepsilon}_{n}$ is an explicit
rate of convergence.

These results enable conversion of credible sets to confidence sets. In the
sparse case, credible tests are shown to be confidence sets. In the very
sparse case, credible sets are enlarged to form confidence sets. Confidence
levels are explicit, for each $n$, as a function of the credible level and the
rate of convergence. Hypothesis testing between the number of classes is
considered with the help of posterior odds, and is shown to be consistent.
Explicit upper bounds on errors of the first and second type and an explicit
lower bound on the power of the tests are given.

##  1 Communities in random graphs

Networks are more present than ever in history. The emergence of the Internet,
which is only about 30 years old, is clearly one of the most eye-catching
examples, but also developments in biology giving rise to enormous networks,
all waiting for the statistician to be analysed.

Under a network or graph we understand a collection of vertices (also called
nodes) and edges between vertices, which can be directed or undirected. Very
often data is associated with the vertices and edges. For example in the
Facebook network, the vertices are users and edges are formed when two users
are friends. With the vertex the user’s name, age, etc. are associated, and
with the edges for example the date that the connected users became friends
could be stored.

There are many things that can be measured from a network, however, the most
intrinsic to a graph is its geometric form, emerging from the connections
between the vertices. One interesting question that may arise is, are there
communities in a graph? Communities are generally understood to be sets of
vertices that are more densily connected among each other, than to vertices
outside the set. Communities are an indication of shared common properties,
for example in the yeast protein-protein interaction network, communities (so-
called “functional modules”) are “cellular entities that perform certain
biological functions, which are relative independent of each other” ([5]).

We use the stochastic block model (SBM), as a mathematical model for
communities in a network. The SBM was first considered in [11]. In the SBM we
observe a graph $X^{n}$ with $n$ vertices, in which vertices belong to one of
a finite number of classes, while edges occur independently, with
probabilities that depend on the classes of the vertices they connect.

SBMs have many applications in science and machine learning applications. One
interesting example is modelling gene expression ([6]). Another example is the
already mentioned yeast protein-protein interaction network studied in [5].
More examples and references of applications are provided in the first section
of [1].

There is now a substantial body of literature on the SBM that deals with
recovery of communities in a network. Transition phases for the SBM for
different number of blocks are studied in [2], [3], and [18]. Rates of
posterior convergence for SBMs are examined in [15], [17], [10], and [9]. A
Bayesian framework for estimating the parameters of a SBM (number of classes,
connecting probabilities) is considered in [8]. For a comprehensive overview
one consults [1].

Recent work mainly considers the SBM under the assumption that the number of
blocks is known, or unknown but bounded. For example [18], allows the number
of blocks to be as large as $\operatorname{\mathcal{O}}(n/\log n)$, but still
assumes it to be known. [9] allows the unknown number to be two or three, but
state that the general problem (four or more classes) is unsolved.

In the non-Bayesian approach this is less a problem, as one can first estimate
the parameters of the SBM (using for instance one of the algorithms mentioned
in [1, sec. 7]), and then recover the clustering. From a Bayesian perspective
this is unnatural (unless one uses an empirical Bayes approach). Here we give
a partial answer to this problem. We allow the number of blocks to be unknown
and even as large as $n^{\alpha},$ for some $0<\alpha<1/2$ (in the dense
phase, see example 3.4).

This also gives a partial answer to the open problem in [1, sec. 8], to
whether exact recovery is possible in classes of sub-linear size, in this case
of size $n^{1-\alpha}$. Another question that he raises (p. 4) and tries to
find an answer to is:

> Are there really communities? Algorithms may output community structures,
> but are these meaningful or artefacts?

We do this here in several ways. One is by providing confidence sets for our
estimators, and another is by providing frequentist guarantees for testing
with posterior odds, whether the data comes from a Erdős-Renì graph model
(there are no communities), or a SBM (there are communities).

#### Outline of our results

We study posterior rates of convergence for large classes of priors. Posterior
rates of convergence are balls $B_{n}$ of labellings centred around the true
labelling $\theta_{0,n}$ of a certain radius $r_{n}$ (in a metric to be
specified) and a sequence $({\varepsilon}_{n})$ such that

$P_{\theta_{0,n}}\Pi^{n}(B_{n}\mid X_{n})\geq 1-{\varepsilon}_{n}.$

For graphs that are not too sparse, we take
$B_{n}=\left\\{\theta_{0,n}\right\\}$, which leads to exact detection.

This unusual precise description of the posterior convergence rates with
${\varepsilon}_{n}$ and $r_{n}$ allows us to construct confidence sets from
the credible sets and to derive explicit bounds on the errors for testing with
posterior odds.

In the sparse and dense cases, credible sets are shown to be confidence sets
with an exact confidence level, which is a function of the credible level and
the posterior rate of convergence. In the very sparse case, credible sets are
enlarged to convert them into confidence sets.

For symmetric testing with posterior odds, we show that posterior convergence
in a parameter set $A_{n}$ allows us to consistently test between $A_{n}$ and
another disjoint set $B_{n}$. This enables us for instance to test for the
number of classes and in particular to test between the SBM and the Erdős-
Rényi graph model (basically the SBM with one class).

In the next section we describe our model. In sections 3 and 4 we derive
posterior convergence and apply that to some interesting examples. Confidence
sets are examined in section 5 and symmetric testing in section 6. Proofs are
mostly defered to appendices B and C. A brief review of the most relevant
Bayesian theory can found in appendix A. Notation and conventions are also
explained in this appendix.

##  2 The stochastic block model

In a SBM for a random graph $X^{n}$ of order $n$, each vertex is assigned to a
class through an unobserved _class assignment vector_ $\theta^{\prime}_{n}$.
The space in which the random graph $X^{n}$ takes its values is denoted
${\mathscr{X}}_{n}$ (e.g. represented by its (random) adjacency matrix with
entries $\\{X_{ij}:1\leq i<j\leq n\\}$). Each vertex belongs to a class and
any edge occurs (independently of others) with a probability depending on the
classes of the vertices that it connects. We study the _planted multi-section
model_ , in which the vertices are divided into $\ell\geq 1$ groups of $1\leq
m_{n,1,1}\leq\ldots\leq m_{n,\ell,\ell}$ vertices, for a total of
$n=m_{n,\ell,1}+\ldots+m_{n,\ell,\ell}$ vertices (with labels
$1,\ldots,\ell$). The corresponding $\ell$-vector is denoted by
$\bm{m}_{n,\ell}=(m_{n,\ell,1},\ldots,m_{n,\ell,\ell})$. We define the set
$\Theta^{\prime}_{\bm{m}_{n,\ell}}$ to be the subset of
$\\{1,\ldots,\ell\\}^{n}$ consisting of all class assignment vectors
$\theta^{\prime}=(\theta_{1}^{\prime},\ldots,\theta_{n}^{\prime}),$ with
labels $\theta_{i}^{\prime}\in\\{1,\ldots,\ell\\},i=1,\ldots,n$, that have
exactly $m_{n,\ell,1}$ elements of one label, and $m_{n,\ell,2}$ elements of
another label, etcetera.

In the SBM for a graph $X^{n}$ with class assignment vector
$\theta^{\prime}_{n}\in\Theta_{n}^{\prime}$, the probability of an edge
occurring between vertices $1\leq i,j\leq n,i\neq j$ is denoted $Q_{i,j;n}$
and depends on $n$, $\theta^{\prime}_{n,i}$ and $\theta^{\prime}_{n,j}$ only.
If edge probabilities vary (that is, if edge probabilities within different
classes vary or if, for example, the edge probability between classes one and
two is different from that between three and four) vertices are classified
correctly by analysis of their asymptotic degrees [4]. In the planted multi-
section model it is assumed that the probability that an edge occurs, depends
only on whether the vertices it connects belong to the same class or to
different classes: the probability of an edge _within the same class_ is
denoted $p_{n}\in(0,1)$; the probability of an edge _between classes_ is
denoted $q_{n}\in(0,1)$,

$Q_{i,j;n}(\theta^{\prime})=\begin{cases}\,\,p_{n},&\quad\text{if
$\theta_{i}^{\prime}=\theta_{j}^{\prime}$,}\\\ \,\,q_{n},&\quad\text{if
$\theta_{i}^{\prime}\neq\theta_{j}^{\prime}$.}\end{cases}$ (1)

Note that if $p_{n}=q_{n}$, $X^{n}$ is a Erdős-Rényi graph and the class
assignment $\theta^{\prime}_{n}\in\Theta^{\prime}_{n}$ is not identifiable.
Indeed asymptotic proximity to the Erdős-Rényi graph (in the sense that the
difference between $p_{n}$ and $q_{n}$ decreases too fast to zero as
$n\to\infty$) can make consistent community detection impossible, see [16] for
example in the case of two blocks. We distinguish between the following three
cases:

Dense phase:

The average degree is proportional to $n$, so $\liminf_{n\to\infty}p_{n}>0$
and $\liminf_{n\to\infty}q_{n}>0$.

Chernoff-Hellinger phase:

The average degrees grows logarithmically. So $p_{n}=\frac{a_{n}\log n}{n}$
and $q_{n}=\frac{b_{n}\log n}{n}$ for certain bounded positive sequences so
that $\liminf_{n\to\infty}a_{n}>0$ and $\liminf_{n\to\infty}b_{n}>0$.

Kesten-Stigum phase:

The average degree is bounded from below, so $p_{n}=c_{n}/n$ and
$q_{n}=d_{n}/n$, for bounded sequences of positive numbers so that
$\liminf_{n\to\infty}c_{n}>0$ and $\liminf_{n\to\infty}d_{n}>0$.

The ability to detect the correct labelling, depends of course on the
differences between $p_{n},q_{n},$ and $a_{n},b_{n}$ and $c_{n},d_{n}$,
respectively. Exact tresholds for these are studied in [2], and [3].

Identifiability is also lost due to invariance of the model under permutation
of class labels: for example with $\ell=3$, the class assignment vectors
$\theta^{\prime}_{1}=(112233)$, $\theta^{\prime}_{2}=(223311)$ and
$\theta^{\prime}_{3}=(331122)$ all give rise to the same distribution for
$X^{6}$. This is expressed via an equivalence relation $\sim$ on
${\Theta}^{\prime}_{n,\ell}.$ Two labels
$\theta_{n}^{\prime},\theta_{n}^{\prime\prime}$ are said to be equivalent, if
there is a permutation $\pi$ of the labels $\left\\{1,\ldots,\ell\right\\}$
such that for all $1\leq i\leq n$,

$\theta^{\prime}_{1,i}=\theta^{\prime\prime}_{2,\pi(i)}.$

We define for an $\ell$-vector of class sizes
$\bm{m}_{n,\ell}=(m_{n,\ell,1},\ldots,m_{n,\ell,\ell})$ satisfying, $1\leq
m_{n,\ell,1}\leq\ldots\leq m_{n,\ell,\ell}$ and
$\sum_{i=1}^{\ell}m_{n,\ell,i}=n$, the model
${\Theta}_{\bm{m}_{n,\ell}}={\Theta}^{\prime}_{\bm{m}_{n,\ell}}/\sim$, which
can be identified with the space of all partitions of $n$ elements into $\ell$
sets of sizes $m_{n,\ell,1},\ldots,m_{n,\ell,\ell}$. One can see that eq. 1
does not depend on the chosen representation $\theta^{\prime}$ of $\theta,$
hence we may define

$Q_{i,j,n}(\theta)=Q_{i,j,n}(\theta^{\prime}).$ (2)

In our set-up, we have to put some constraints on the $\bm{m}_{n,\ell}$.
Hence, for given $\ell$, we let $M_{n,\ell}$ be the set of all allowed
$\ell$-vectors $\bm{m}_{n,\ell}$. By $\operatorname{\mathcal{L}}_{n}$ we
denote all $\ell$ for which $M_{n,\ell}$ is not empty. We define
$M_{n}=\bigcup_{\ell=1}^{n}M_{n,\ell}$. We set

$\Theta_{n,\ell}=\bigcup_{\bm{m}_{n,\ell}\in
M_{n,\ell}}\Theta_{\bm{m}_{n,\ell}}.$

The full parameter space is denoted

$\Theta_{n}=\bigcup_{\bm{m}_{n}\in
M_{n}}\Theta_{\bm{m}_{n}}=\bigcup_{\ell\in\operatorname{\mathcal{L}}_{n}}\Theta_{n,\ell}.$

For $\ell\in\operatorname{\mathcal{L}}_{n}$, we define

$m_{n,\ell,\min}=\min_{\bm{m}_{n,\ell}\in
M_{n,\ell}}m_{n,\ell,1},\quad\text{and}\quad
m_{n,\ell,\max}=\max_{\bm{m}_{n,\ell}\in M_{n,\ell}}m_{n,\ell,\ell}.$

(Recall that $m_{n,\ell,1}=\min_{1\leq i\leq\ell}m_{n,\ell,i}$ and
$m_{n,\ell,\ell}=\max_{1\leq i\leq\ell}m_{n,\ell,i}$.)

It is noted explicitly that $\ell=1$ and $\bm{m}_{n,1}=(n)$ is also allowed,
which allows us to test between the Erdős-Rényi graph model and a SBM with at
least two classes. In case $\ell=1$, $\Theta_{\bm{m}_{n,1}}^{\prime}$ consist
of only one element: the $n$-vector $(1,\ldots,1)$.

In order to distinguish between the number of classes, in our approach, the
minimum and maximum sizes of the classes are required to adhere to the
following assumption:

###### Assumption 2.1

For all $\ell_{1},\ell_{2}\in\operatorname{\mathcal{L}}_{n}$, whenever
$\ell_{1}<\ell_{2}$, $m_{n,\ell_{1},\min}\geq m_{n,\ell_{2},\max}$.

This assumption organises class sizes for decreasing number of classes in
consecutive intervals, concentrated around the mean number of elements
$m:=n/\ell$ per class. For instance, if we impose an upper bound $L_{n}$ for
$\ell$ given $n$, then any vector $\bm{m}_{n,\ell}$ that satisfies
$n/\ell-\frac{1}{4}\frac{n}{L_{n}^{2}}\leq m_{n,\ell,i}\leq
n/\ell+\frac{1}{4}\frac{n}{L_{n}^{2}}$, satisfies 2.1, see eq. 10. A condition
like this is quite common in the literature, see for instance [18, p. 2254] or
the consistency results in [9, assumption (A1), p. 897]. The difference
$m_{n,\ell_{1},\min}-m_{n,\ell_{2},\max}$ determines the power to test between
$\Theta_{n,\ell_{1}}$ and $\Theta_{n,\ell_{2}}$, see theorem 6.1 in
combination with proposition 3.1.

In the planted multi-section model one observes a sequence of graphs $X^{n}$
of order $n$ and the statistical question is to reconstruct the unobserved
class assignment vectors $\theta_{n}$ _consistently_ , that is, correctly with
probability growing to one as $n\to\infty$.

###### Definition 2.2

Let $\theta_{0,n}\in\Theta_{n}$ for all $n\geq 1$ be given. An estimator
sequence $\hat{\theta}_{n}:{\mathscr{X}}_{n}\to\Theta_{n}$ is said to _recover
the class assignment $\theta_{0,n}$ exactly_ if,

$P_{\theta_{0,n}}\bigl{(}\hat{\theta}_{n}(X^{n})=\theta_{0,n}\bigr{)}\longrightarrow
1,$

as $n\to\infty$. That is, $\hat{\theta}_{n}$ is the true class assignment (up
to a permutation) with high probability.

In the very sparse regime where the average degree is large enough, or grows
arbitrarily slowly to infinity, exact recovery is not possible, however weaker
forms of recovery are still possible, for which we define:

###### Definition 2.3

Let $\theta_{0,n}\in\Theta_{n}$ for all $n\geq 1$ be given. Let
$\hat{\theta}_{n}:{\mathscr{X}}_{n}\to\Theta_{n}$ be an estimator and $s_{n}$
be an integer such that there are representations $\theta_{0,n}^{\prime}$ of
$\theta_{0,n}$ and $\hat{\theta}_{n}^{\prime}$ of $\hat{\theta}_{n}$ such that

$P_{\theta_{0,n}}\left(\\#\left\\{i:\hat{\theta}_{n,i}^{\prime}=\theta_{0,n,i}^{\prime}\right\\}\geq
s_{n}\right)\to 1,\quad\text{as}\quad n\to\infty.$

that is, if $\hat{\theta}_{n}$ recovers $s_{n}$ labels correctly, with high
probability. When $s_{n}/n\to 1$, we say that $\hat{\theta}_{n}$ _recovers the
class assignment $\theta_{0,n}$ almost exactly_, that is, the estimator
recovers the labelling correct, up to an arbitrarily small fraction and up to
a permutation of the labels. When $s_{n}/n\geq a_{n}>1/L_{n}$, for some
deterministic sequence $a_{n}$, where $L_{n}$ is the maximum number of classes
in $\Theta_{n}$, then we say that $\hat{\theta}_{n}$ recovers the labelling
partially. Which means that $\hat{\theta}_{n}$ performs on average better than
a random guess.

Below we specialize to the Bayesian approach in the planted multi-section
model: with given $n\geq 1$, $\theta_{n}\in{\Theta}_{n}$ and random $X^{n}$,
the likelihood is given by,

$p_{\theta_{n}}(X^{n})=\prod_{1\leq i<j\leq
n}Q_{i,j;n}(\theta_{n})^{X_{ij}}(1-Q_{i,j;n}(\theta_{n}))^{1-X_{ij}},$

where $Q_{i,j,n}$ is defined in eq. 2.

We make the following convenient assumption on the prior (which always holds
after removing parameters with zero prior mass from the parameter space).

###### Assumption 2.4

The prior mass function $\pi_{n}$ of the prior $\Pi_{n}$ on $\Theta_{n}$
satisfies $\pi_{n}(\theta_{n})>0$, for all $\theta_{n}\in\Theta_{n}$.

The posterior distribution of a subset $S_{n}\subseteq\Theta_{n}$ is given by

$\Pi_{n}(S_{n}\mid X^{n})=\frac{\sum_{\theta_{n}\in
S_{n}}\pi_{n}(\theta_{n})p_{\theta_{n}}(X^{n})}{\sum_{\theta_{n}\in\Theta_{n}}\pi_{n}(\theta_{n})p_{\theta_{n}}(X^{n})}.$

###### Proposition 2.5

For fixed $n$, consider an prior probability mass function $\pi_{n}$ on
$\Theta_{n}$ satisfying 2.4. Suppose that for some
$\theta_{0,n}\in\Theta_{n}$, we observe a graph $X^{n}$ with $n$ vertices,
distributed according to $P_{\theta_{0,n}}.$ Let
$S_{n}\subseteq\Theta_{n}\operatorname{\backslash}\left\\{\theta_{0,n}\right\\}$
be non-empty. For $\theta_{n}\in S_{n}$, and representations
$\theta_{0,n}^{\prime}\in\theta_{0,n}$ and $\theta_{n}^{\prime}\in\theta_{n}$
define

$\begin{split}D_{1,n}(\theta_{n})&=\\{(i,j)\in\\{1,\ldots,n\\}^{2}:\,i<j,\,\theta_{0,n,i}^{\prime}=\theta_{0,n,j}^{\prime},\,\theta_{n,i}^{\prime}\neq\theta_{n,j}^{\prime}\\},\\\
D_{2,n}(\theta_{n})&=\\{(i,j)\in\\{1,\ldots,n\\}^{2}:\,i<j,\,\theta_{0,n,i}^{\prime}\neq\theta_{0,n,j}^{\prime},\,\theta_{n,i}^{\prime}=\theta_{n,j}^{\prime}\\}.\end{split}$

Then $D_{1,n}(\theta_{n})$ and $D_{2,n}(\theta_{n})$ are well-defined and
disjoint, and if

$0<B_{n}\leq\inf_{\theta_{n}\in S_{n}}|D_{1,n}(\theta_{n})\cup
D_{2,n}(\theta_{n})|,$

then

$P_{\theta_{0,n}}\Pi_{n}\bigl{(}S_{n}\bigm{|}X^{n}\bigr{)}\leq
2\left(\frac{\pi_{n}(S_{n})}{\pi_{n}(\theta_{0,n})}\bigvee|S_{n}|\right)\rho(p_{n},q_{n})^{B_{n}}.$
(3)

Proof Obviously, $D_{1,n}(\theta_{n})$ and $D_{2,n}(\theta_{n})$ are disjoint
and do not depend on the chosen representations. According to lemma A.3 (with
$B_{n}=\\{\theta_{0}\\}$), for any tests
$\phi_{S_{n}}:{\mathscr{X}}_{N}\to[0,1]$, we have,

$P_{\theta_{0,n}}\Pi_{n}(S_{n}|X^{n})\leq
P_{\theta_{0,n}}\phi_{S_{n}}(X^{n})+\frac{1}{\pi^{n}_{\theta_{0,n}}}\sum_{\theta_{n}\in
S_{n}}\pi_{n}(\theta_{n})P_{\theta_{n}}(1-\phi_{S_{n}}(X^{n})).$

Lemma B.1 proves that for any $\theta_{n}\in S$ there is a test function
$\phi_{\theta_{n}}$ that distinguishes $\theta_{0,n}$ from $\theta_{n}$ as
follows,

$P_{\theta_{0,n}}\phi_{\theta_{n}}(X^{n})+P_{\theta_{n}}(1-\phi_{\theta_{n}}(X^{n}))\leq\rho(p_{n},q_{n})^{|D_{1,n}(\theta_{n})\cup
D_{2,n}(\theta_{n})|}\leq\rho(p_{n},q_{n})^{B_{n}},$

where the last inequality follows from the fact that $\rho(p_{n},q_{n})\leq 1$
and the assumption $|D_{1,n}(\theta_{n})\cup D_{2,n}(\theta_{n})|\geq B_{n}$,
for all $\theta_{n}\in S_{n}$. Then using test functions
$\phi_{S_{n}}(X^{n})=\max\\{\phi_{\theta_{n}}(X^{n}):\theta_{n}\in S_{n}\\}$,
we have,

$P_{\theta_{0,n}}\phi_{S_{n}}(X^{n})\leq\sum_{\theta_{n}\in
S_{n}}P_{\theta_{0,n}}\phi_{\theta_{n}}(X^{n}),$

so that,

$\displaystyle P_{\theta_{0,n}}\Pi_{n}(S_{n}|X^{n})\leq$
$\displaystyle\sum_{\theta_{n}\in
S_{n}}\left(\frac{\pi_{n}(\theta_{n})}{\pi_{\theta_{0,n}}^{n}}\bigvee
1\right)\left(P_{\theta_{0,n}}\phi_{\theta_{n}}(X^{n})+P_{\theta_{n}}(1-\phi_{\theta_{n}}(X^{n}))\right)$
$\displaystyle\leq$ $\displaystyle
2\left(\frac{\pi_{n}(S_{n})}{\pi_{n}(\theta_{0,n})}\bigvee|S_{n}|\right)\rho(p_{n},q_{n})^{B_{n}},$

where we use that for a finite index set $I$ and a sequence of non-negative
numbers $(x_{i}:i\in I)$, $\sum_{i\in I}(x_{i}\vee 1)\leq
2\left(|I|\vee\sum_{i\in I}x_{i}\right).$ $\Box$

##  3 Selection of the number of classes

Consider the sequence of experiments in which we observe random graphs
$X^{n}\in{\mathscr{X}}^{n}$ generated by the SBM of eq. 1. We first provide a
general condition under which the posterior selects the true model
$\Theta_{n,\ell}$ consistently. Next we apply this to several interesting
examples. The Hellinger-affinity between two Bernoulli-distributions with
parameters $p$ and $q$, is given by

$\rho(p,q)=p^{1/2}q^{1/2}+(1-p)^{1/2}(1-q)^{1/2}.$

This quantity determines the power of our tests, lemma B.1, similar as in
[13]. (See also [18, equation 1.2 and theorem 1.1] where minus the log of this
quantity (i.e. the Rényi divergence of order 1/2) emerges in the minimax rate
of convergence.)

###### Proposition 3.1

For fixed $n$, let the set of models $M_{n}$ satisfy 2.1 and let $\Pi_{n}$ a
prior on $\Theta_{n}$ satisfying 2.4. Suppose that for some
$\ell_{0}\in\operatorname{\mathcal{L}}_{n}$, we observe a graph $X^{n}$ with
$n$ vertices, distributed according to $P_{\theta_{0,n}}$ for some class
assignment $\theta_{0,n}\in\Theta_{n,\ell_{0}}$. For
$\ell\in\operatorname{\mathcal{L}}_{n}$ unequal to $\ell_{0}$, we have,

$P_{\theta_{0,n}}\Pi\bigl{(}{\Theta}_{n,\ell}\bigm{|}X^{n}\bigr{)}\leq
2\left(\frac{\pi_{n}(\Theta_{n,\ell})}{\pi_{n}(\theta_{0,n})}\bigvee|\Theta_{n,\ell}|\right)\rho(p_{n},q_{n})^{\frac{1}{2}n(m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max})}.$
(4)

Proof This follows from propositions 2.5 and B.2. $\Box$

The number of elements in $\Theta_{n,\ell}$ is bounded by the number of
partitions of $\left\\{1,\ldots,n\right\\}$ into $\ell$ sets, which is known
as the Stirling number $V(n,\ell)$ of second kind, which satisfies

$V(n,\ell)\leq\frac{1}{2}\binom{n}{\ell}\ell^{n-\ell}\leq\frac{1}{2}e^{\ell}n^{\ell}\ell^{n-2\ell}.$
(5)

###  3.1 Examples: convergence to the true model

We consider several examples of posterior contraction in one model
$\Theta_{n,\ell_{0}}$, whose priors and models are defined below.

######  Example 3.2 (Priors)

The first prior is defined hierarchically by taking the uniform prior on
$\operatorname{\mathcal{L}}_{n}$, and conditionally on $\ell$, we choose the
uniform prior on $\Theta_{n,\ell}$. So

$\begin{split}\ell\sim&\frac{1}{|\operatorname{\mathcal{L}}_{n}|},\\\
\theta_{0,n}\mid\ell\sim&\frac{1}{|\Theta_{n,\ell}|}.\end{split}$ (6)

A second option for a prior is the uniform prior on $\Theta_{n}$, so

$\theta_{0,n}\sim\frac{1}{|\Theta_{n}|}.$ (7)

In both cases, applying proposition 3.1 gives, for
$\ell\in\operatorname{\mathcal{L}}_{n},\ell\neq\ell_{0}$, the upper bound,

$P_{\theta_{0,n}}\Pi_{n}(\Theta_{n,\ell}|X^{n})\leq
2\left(\max_{\ell\in\operatorname{\mathcal{L}}_{n}}|\Theta_{n,\ell}|\right)\rho(p_{n},q_{n})^{\frac{1}{2}n(m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max})}.$
(8)

######  Example 3.3 (Models)

We take $\operatorname{\mathcal{L}}_{n}=\left\\{1,\ldots,L_{n}\right\\},$
where $2\leq L_{n}\leq n$ depends on the degree of sparsity and is specified
in the examples. We let $\Theta_{n,\ell}$ be all parameters with $\ell$
classes and satisfying

$m_{n,\ell,\min}\geq
n/\ell-\frac{1}{4}\frac{n}{L_{n}^{2}}\operatorname{\quad\text{and}\quad}m_{n,\ell,\max}\leq
n/\ell+\frac{1}{4}\frac{n}{L_{n}^{2}}.$ (9)

One verifies easily that 2.1 is satisfied and that for
$\ell,\ell_{0}\in\operatorname{\mathcal{L}}_{n},\ell\neq\ell_{0}$,

$m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max}\geq\frac{1}{2}\frac{n}{L_{n}^{2}}.$
(10)

Using eq. 5, the number of elements of $\Theta_{n,\ell}$ is upper bounded by
$\frac{1}{2}e^{2n\log L_{n}},$ which is trivial for $\ell=1$, and when
$\ell\geq 2$ and $n\geq 4$, we have,

$\frac{1}{2}e^{\ell}n^{\ell}\ell^{n-2\ell}\leq\frac{1}{2}n^{\ell}\ell^{n}\leq\frac{1}{2}\ell^{2n}\leq\frac{1}{2}e^{2n\log
L_{n}},$ (11)

using that for integers $2\leq x\leq y$ with either $x\geq 3$ or $y\geq 4$,
$y^{x}\leq x^{y}$ and using that $\ell\leq L_{n}\leq n$. It follows that,

$P_{\theta_{0,n}}\Pi_{n}\bigl{(}{\Theta}_{n,\ell}\bigm{|}X^{n}\bigr{)}\leq
e^{2n\log L_{n}}\rho(p_{n},q_{n})^{\frac{1}{4}n^{2}/(L_{n}^{2})}$ (12)

###### Example 3.4

(Dense phase) Define $b_{n}=-\log\rho(p_{n},q_{n})>0$. Let
$L_{n}=\bm{o}(\sqrt{n/\log n})$, for example $L_{n}=\left\lfloor
n^{\alpha}\right\rfloor,$ for some $\alpha<1/2$. When
$\frac{nb_{n}}{L_{n}^{2}\log L_{n}}\geq 12$,
$P_{\theta_{0,n}}\Pi(\Theta_{n,\ell}\mid X^{n})\leq
e^{-b_{n}n^{2}/(12L_{n}^{2})}.$ It follows that
$P_{\theta_{0,n}}\Pi(\Theta_{n,\ell_{0}}^{c}\mid X^{n})\leq
L_{n}e^{-b_{n}n^{2}/(12L_{n}^{2})}\leq L_{n}^{1-n}\to 0,$ as $n\to\infty.$
$\Box$

In the sparse regimes another approximation strategy is needed.

###### Example 3.5

(Chernoff-Hellinger phase) Recall that in the Chernoff-Hellinger phase, we
assume that the edge probabilities satisfy $np_{n}=a_{n}\log(n)$ and
$nq_{n}=b_{n}\log(n)$ for sequences $a_{n},b_{n}$ bounded away from $zero$.
Suppose $L_{n}$ satisfies

$48L_{n}^{2}\log L_{n}\leq(\sqrt{a_{n}}-\sqrt{b_{n}})^{2}\log n.$ (13)

Equation 13 is satisfied for sufficiently large $n$, when $L_{n}\leq(\log
n)^{a}$ with $a<1/2$.

Using lemma C.2, we find $\sqrt{1-p}\sqrt{1-q}\leq
1-\frac{1}{2}(p+q)+\frac{1}{4}pq$, and using the fact that $(1+x/r)^{r}\leq
e^{x}$ (see lemma C.3), for all positive integers $r$ and $x>-r$, we obtain

$\displaystyle\rho(p_{n},q_{n})^{\frac{1}{2}n|m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max}|}$
$\displaystyle\leq$
$\displaystyle\left[1-\frac{1}{2}\left(\sqrt{p_{n}}-\sqrt{q_{n}}\right)^{2}+p_{n}q_{n}/4\right]^{\frac{1}{2}n|m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max}|}$
$\displaystyle=$ $\displaystyle\left[1-\frac{\log
n}{n}\left\\{\frac{1}{2}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}-\frac{a_{n}b_{n}\log
n}{4n}\right\\}\right]^{\frac{1}{2}n(m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max})}$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{1}{2}(m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max})\left\\{\frac{1}{2}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}-\frac{a_{n}b_{n}\log
n}{4n}\right\\}\log n\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\frac{1}{16}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{n\log
n}{L_{n}^{2}}\right),$

for $n$ sufficiently large. It follows from eq. 12 that

$\displaystyle
P_{\theta_{0,n}}\Pi(\Theta_{n,\ell}|X^{n})\leq\exp\left(-n\left(\frac{1}{16}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{\log
n}{L_{n}^{2}}-2\log L_{n}\right)\right)$ $\displaystyle\leq$
$\displaystyle\exp\left(-\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{n\log
n}{48L_{n}^{2}}\right),$

using eq. 13 in the last inequality. It follows that

$P_{\theta_{0,n}}\Pi(\Theta_{\bm{m}_{n,\ell_{0}}}^{c}\mid X^{n})\leq
L_{n}\exp\left(-\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{n\log
n}{48L_{n}^{2}}\right)\leq L_{n}^{1-n}\to 0,$

as $n\to\infty.$ $\Box$

Even in the Kesten-Stigum phase, there is testing power enough to decide
between the classes.

###### Example 3.6

(Kesten-Stigum phase) Recall that in the Kesten-Stigum phase, $np_{n}=c_{n}$
and $nq_{n}=d_{n}$ for sequences of positive numbers $c_{n}$ and $d_{n}$
bounded away from zero. We obtain in similar manner as in example 3.5 that,

$(c_{n}^{1/2}-d_{n}^{1/2})^{2}\geq 48L_{n}^{2}\log L_{n},$

guarantees that,

$P_{\theta_{0,n}}\Pi(\Theta_{n,\ell_{0}}^{c}\mid X^{n})\leq
L_{n}\exp\left(-\left(\sqrt{c_{n}}-\sqrt{d_{n}}\right)^{2}\frac{n}{48L_{n}^{2}}\right)\leq
L_{n}^{1-n}\to 0,$

as $n\to\infty$. $\Box$

##  4 Posterior concentration at the parameter

Posterior convergence at the true parameter
$\theta_{0,n}\in\Theta_{n,\ell_{0}}$, where $\ell_{0}$ is the true number of
classes, is derived in the following way. Noting that

$P_{\theta_{0}}\Pi(\left\\{\theta_{n,0}\right\\}^{c}\mid
X^{n})=P_{\theta_{0}}\Pi(\Theta_{n,\ell_{0}}^{c}\mid
X^{n})+P_{\theta_{n,0}}\Pi(\Theta_{n,\ell_{0}}\backslash\left\\{\theta_{0,n}\right\\}\mid
X^{n}),$

posterior consistency is established once both expectations on the right
converge to zero as $n\to\infty$. The first was the content of the previous
section, the second we treat here. Obviously, when $\ell_{0}=1$, then
$\Theta_{n,\ell_{0}}=\left\\{\theta_{n,0}\right\\}$ and convergence at the
true parameter follows from section 3. Hence, we assume that $\ell_{0}>1.$ In
the previous section posterior convergence in a set $\Theta_{n,\ell_{0}}$ was
established by showing that there was enough testing power between
$\Theta_{n,\ell_{0}}$ and $\Theta_{n,\ell}$, for $\ell\neq\ell_{0}$. Here we
do something similar within $\Theta_{n,\ell_{0}}$, by constructing tests
between $\theta_{0,n}$ (in the dense and sparse case) and rings
$V_{n,k}\subseteq\Theta_{n,\ell_{0}}$ of radius $k$ around $\theta_{0,n}$ in
the distance $r_{n}$.

Define the distance $r_{n}$ on $\Theta_{n}$ as follows: first define
$r_{n}^{\prime}$ on $\Theta_{n}^{\prime}$ by

$r_{n}^{\prime}(\theta^{\prime},\eta^{\prime})=\max_{a\neq
b}\\#\left\\{i:\theta_{i}^{\prime}=a,\eta_{i}^{\prime}=b\right\\}.$

This does depend on the particular choice of the representation. So we define
for $\theta,\eta\in\Theta_{n}$,

$r_{n}(\theta,\eta)=\min_{\theta^{\prime}\in\theta,\eta^{\prime}\in\eta}r_{n}^{\prime}(\theta^{\prime},\eta^{\prime}).$
(14)

The function $r_{n}$ takes values in $\left\\{0,\ldots,\left\lfloor
n/2\right\rfloor\right\\}$ and according to lemma B.5, when
$\theta,\eta\in\Theta_{n,\ell}$, $r_{n}(\theta,\eta)\leq m_{n,\ell,\max}/2$.
The function $r_{n}$ is symmetric and $r_{n}(\theta,\eta)=0$ if and only if
$\theta=\eta$.

For a given $\ell_{0}\in\operatorname{\mathcal{L}}_{n}$ and
$\theta_{0,n}\in\Theta_{n,\ell_{0}}$ define subsets of $\Theta_{n,\ell_{0}}$,
by

$V_{n,\ell_{0},k}=\left\\{\theta_{n}\in\Theta_{n,\ell_{0}}:r_{n}(\theta_{n},\theta_{0,n})=k\right\\}.$

These sets resemble the sets $V_{n,k}$ in [13] and are rings of radius $k$
around $\theta_{0,n}$ in $\Theta_{n,\ell_{0}}$. When $k\leq
m_{n,\ell_{0},\min},$ lemma B.6 bounds the number of elements in
$V_{n,\ell_{0},k}$ by
$2^{k\ell_{0}(\ell_{0}-1)}\binom{n(\ell_{0}-1)}{\ell_{0}(\ell_{0}-1)k}$, which
in turn is bounded by
$\left(\frac{2en}{\ell_{0}k}\right)^{\ell_{0}(\ell_{0}-1)k}.$

###### Proposition 4.1

Consider a prior on $\Theta_{n}$ satisfying 2.4. Suppose that for some
$\ell_{0}\in\operatorname{\mathcal{L}}_{n}$, $\ell_{0}>1$, we observe a graph
$X^{n}$ with $n$ vertices, distributed according to $P_{\theta_{0,n}}$, where
$\theta_{0,n}\in\Theta_{n,\ell_{0}}$. For all
$k\in\left\\{0,\ldots,\left\lfloor
m_{n,\ell_{0},\max}/2\right\rfloor\right\\}$, we have,

$P_{\theta_{0,n}}\Pi\bigl{(}V_{n,\ell_{0},k}\bigm{|}X^{n}\bigr{)}\leq
2\left(|V_{n,\ell_{0},k}|\vee\frac{\pi_{n}(V_{n,\ell_{0},k})}{\pi_{n}(\theta_{0,n})}\right)\rho(p_{n},q_{n})^{2k(m_{n,\ell_{0},\min}-k)^{+}}.$
(15)

Proof This follows from proposition 2.5 and the lower bound on
$|D_{1,n}(\theta_{n})\cup D_{2,n}(\theta_{n})|$ in lemma B.4. $\Box$

Define

$W_{n,\ell_{0},k_{n}}=\bigcup_{k=k_{n}}^{\left\lfloor
m_{n,\ell\wedge\ell_{0},\max}/2\right\rfloor}V_{n,\ell_{0},k},$

to be the set of all elements with $r_{n}$ distance at least $k_{n}$ from
$\theta_{0,n}$. Taking $k_{n}=1$,
$W_{n,\ell_{0},1}=\Theta_{n,\ell_{0}}\backslash\left\\{\theta_{0,n}\right\\}$.

Applying proposition 4.1 to $W_{n,\ell_{0},k_{n}}$ gives

$\displaystyle
P_{\theta_{0,n}}\Pi(W_{n,k_{n}}|X^{n})\leq\sum_{k=k_{n}}^{\left\lfloor
m_{n,\ell_{0},\max}/2\right\rfloor}2\left(|V_{n,\ell_{0},k}|\vee\frac{\pi_{n}(V_{n,\ell_{0},k})}{\pi_{n}(\theta_{0,n})}\right)\rho(p_{n},q_{n})^{2k(m_{n,\ell_{0},\min}-k)^{+}}$

For the next corollary we need the following assumption

###### Assumption 4.2

For all $\ell\in\operatorname{\mathcal{L}}_{n}$, $m_{n,\ell,\min}\geq
m_{n,\ell,\max}/2$.

###### Corollary 4.3

Assume 4.2. Suppose that for some $\ell_{0}\in\operatorname{\mathcal{L}}_{n}$,
$\ell_{0}>1$, and $\theta_{0,n}\in\Theta_{n,\ell_{0}}$, we observe a graph
$X^{n}$ with $n$ vertices, distributed according to $P_{\theta_{0,n}}.$
Futhermore, assume that the prior $\pi_{n}$ gives positive mass to every
element of $\Theta_{n,\ell_{0}}$ and satisfies

$\max_{\theta_{n},\eta_{n}\in\Theta_{n,\ell_{0}}}\frac{\pi_{n}(\theta_{n})}{\pi_{n}(\eta_{n})}\leq
K_{n,\ell_{0}}.$

Define

$B_{n}=2n\rho(p_{n},q_{n})^{\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}},$

then

$P_{\theta_{n,0}}\Pi_{n}(\Theta_{n,\ell_{0}}\backslash\left\\{\theta_{n,0}\right\\}\mid
X^{n})\leq 2K_{n,\ell_{0}}B_{n}^{\ell_{0}(\ell_{0}-1)}e^{(\ell_{0}-1)B_{n}}.$
(16)

Proof Take $k_{n}\equiv 1$ for all $n$ in proposition 4.1. Using proposition
4.1, the upper bound on the number of elements in $V_{n,\ell,k}$ eq. 27 and
the condition on the prior mass function $\pi_{n}$ we have the bound

$\displaystyle
P_{\theta_{n,0}}\Pi(\Theta_{n,\ell_{0}}\backslash\left\\{\theta_{n,0}\right\\}\mid
X^{n})$ $\displaystyle\leq$ $\displaystyle
2K_{n,\ell_{0}}\sum_{k=1}^{\left\lfloor
m_{n,\ell_{0},\max}/2\right\rfloor}2^{k\ell_{0}(\ell_{0}-1)}\binom{n(\ell_{0}-1)}{\ell_{0}(\ell_{0}-1)k}\rho(p_{n},q_{n})^{2k(m_{n,\ell_{0},\min}-k)}$
$\displaystyle\leq$ $\displaystyle 2K_{n,\ell_{0}}\sum_{k=1}^{\left\lfloor
m_{n,\ell_{0},\max}/2\right\rfloor}\frac{(2n(\ell_{0}-1))^{\ell_{0}(\ell_{0}-1)k}}{(\ell_{0}(\ell_{0}-1)k)!}\rho(p_{n},q_{n})^{2k(m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}/2)}$
$\displaystyle\leq$ $\displaystyle
2K_{n,\ell_{0}}\sum_{k=\ell_{0}(\ell_{0}-1)}^{\infty}\frac{(2n(\ell_{0}-1))^{k}}{k!}\rho(p_{n},q_{n})^{k\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}}$
$\displaystyle\leq$ $\displaystyle
2K_{n,\ell_{0}}\frac{(2n(\ell_{0}-1))^{\ell_{0}(\ell_{0}-1)}}{(\ell_{0}(\ell_{0}-1))!}\rho(p_{n},q_{n})^{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}$
$\displaystyle\times\sum_{k=0}^{\infty}\frac{(2n(\ell_{0}-1))^{k}}{k!}\rho(p_{n},q_{n})^{k\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}}$
$\displaystyle=$ $\displaystyle
2K_{n,\ell_{0}}\frac{1}{(\ell_{0}(\ell_{0}-1))!}\left((2n(\ell_{0}-1))\rho(p_{n},q_{n})^{\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}}\right)^{\ell_{0}(\ell_{0}-1)}$
$\displaystyle\times\exp\left(2n(\ell_{0}-1)\rho(p_{n},q_{n})^{\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}}\right)$
$\displaystyle=$
$\displaystyle\frac{2K_{n,\ell_{0}}}{(\ell_{0}(\ell_{0}-1))!}\big{(}(\ell_{0}-1)B_{n}\big{)}^{\ell_{0}(\ell_{0}-1)}e^{(\ell_{0}-1)B_{n}}.$

With the lower bound $k!\geq\sqrt{2\pi}k^{k+1/2}e^{-k}$ one can easily see
that for $\ell_{0}\geq 3$,
$\frac{(\ell_{0}-1)^{\ell_{0}(\ell_{0}-1)}}{(\ell_{0}(\ell_{0}-1))!}\leq 1$,
but it also holds for $\ell_{0}=2$. Hence
$P_{\theta_{n,0}}\Pi(\Theta_{n,\ell_{0}}\backslash\left\\{\theta_{n,0}\right\\}\mid
X^{n})\leq 2K_{n,\ell_{0}}B_{n}^{\ell_{0}(\ell_{0}-1)}e^{(\ell_{0}-1)B_{n}}$.
$\Box$

###  4.1 Examples: recovery of the parameters

In this section we are interested in exact and almost exact recovery for some
interesting examples. We consider the same priors and models as in examples
3.2 and 3.3. Note that in this case

$m_{n,\ell,\min}-m_{n,\ell,\max}/2\geq\frac{n}{8\ell},$ (17)

so 4.2 is satisfied for all $\ell\in\operatorname{\mathcal{L}}_{n}$.

###### Example 4.4

(Dense phase, continuation of example 3.4)

Recall that $b_{n}=-\log\rho(p_{n},q_{n})$. The quantity $B_{n}$ in corollary
4.3 is bounded as follows

$\displaystyle
B_{n}=2n\rho(p_{n},q_{n})^{\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}}\leq
2n\rho(p_{n},q_{n})^{\frac{n}{4\ell_{0}^{2}(\ell_{0}-1)}}=e^{-\frac{nb_{n}}{4\ell_{0}^{2}(\ell_{0}-1)}+\log(2n)}.$

So with corollary 4.3 and the result of example 3.4, when
$L_{n}=\bm{o}(\sqrt{n/\log n})$ and

$nb_{n}\geq 8L_{n}^{2}(L_{n}-1)\log(2n),$

we obtain

$P_{\theta_{0,n}}\Pi_{n}(\theta_{0}\mid X^{n})\geq
1-L_{n}e^{-b_{n}n^{2}/(12L_{n}^{2})}-2\sqrt{e}e^{-nb_{n}/(8L_{n})}.$

In particular $P_{\theta_{0,n}}\Pi_{n}(\theta_{0}\mid X^{n})\to 1,$ as
$n\to\infty$. $\Box$

So in the dense phase we have exponentially fast convergence of the expected
posterior mass of $\theta_{0,n}$ to one, under the true distribution. In the
sparse phases we get only a polynomial rate of convergence.

###### Example 4.5

(Chernoff-Hellinger phase, continuation of example 3.5) With a similar
calculation as in example 3.5, we find,

$\displaystyle\rho(p_{n},q_{n})^{\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)}}$
$\displaystyle=$ $\displaystyle\left[1-\frac{\log
n}{n}\left(\frac{1}{2}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}-\frac{a_{n}b_{n}\log
n}{4n}\right)\right]^{n\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)n}}$
$\displaystyle\leq$
$\displaystyle\exp\left(-\frac{2m_{n,\ell_{0},\min}-m_{n,\ell_{0},\max}}{\ell_{0}(\ell_{0}-1)n}\left(\frac{1}{2}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}-\frac{a_{n}b_{n}\log
n}{4n}\right)\log n\right).$

It follows that

$B_{n}\leq
e^{\log(2n)-\frac{(a_{n}^{1/2}-b_{n}^{1/2})^{2}}{16\ell_{0}^{2}(\ell_{0}-1)}\log
n}.$

So when $(a_{n}^{1/2}-b_{n}^{1/2})^{2}\geq
32L_{n}^{2}(L_{n}-1)\frac{\log(2n)}{\log n}$,

$\displaystyle
P_{\theta_{n,0}}\Pi_{n}(\Theta_{n,\ell_{0}}\backslash\left\\{\theta_{n,0}\right\\}\mid
X^{n})\leq 2\sqrt{e}n^{-(a_{n}^{1/2}-b_{n}^{1/2})^{2}/(32L_{n})}.$

It follows that when $(a_{n}^{1/2}-b_{n}^{1/2})^{2}\geq 48L_{n}^{2}(L_{n}-1)$,
then with the result of example 3.5

$\displaystyle P_{\theta_{0,n}}\Pi_{n}(\theta_{0}\mid X^{n})\geq
1-L_{n}\exp\left(-n{\frac{1}{48}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{\log
n}{L_{n}^{2}}}\right)-2\sqrt{e}n^{-(a_{n}^{1/2}-b_{n}^{1/2})^{2}/(32L_{n})}.$

In particular $P_{\theta_{0,n}}\Pi_{n}(\theta_{0,n}\mid X^{n})\to 1,$ as
$n\to\infty.$ $\Box$

In the even sparser Kesten-Stigum phase exact recovery is not possible anymore
([2, 3]). Instead we obtain weak recovery, in which all but a small fraction
of the labels is recovered.

###### Example 4.6

(Kesten-Stigum phase, continuation of example 3.6) With a calculation similar
to that of example 3.5, we find that,

$\rho(p_{n},q_{n})^{2k(m_{n,\ell_{0},\min}-k)}\leq
e^{-k(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0})}.$

Using the bound
$2^{\ell_{0}(\ell_{0}-1)k}\binom{n(\ell_{0}-1)}{\ell_{0}(\ell_{0}-1)k}\leq\left(\frac{2en}{\ell_{0}k}\right)^{\ell_{0}(\ell_{0}-1)k}$,
we see that the posterior

$\displaystyle P_{\theta_{0,n}}\Pi_{n}(W_{n,\ell_{0},k_{n}}\mid X^{n})\leq$
$\displaystyle 2\sum_{k=k_{n}}^{\left\lfloor
m_{n,\ell_{0},\max}/2\right\rfloor}\left(\frac{2en}{\ell_{0}k}e^{-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))}\right)^{\ell_{0}(\ell_{0}-1)k}$
$\displaystyle\leq$ $\displaystyle
2\frac{\left(\frac{2en}{\ell_{0}k_{n}}e^{-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))}\right)^{\ell_{0}(\ell_{0}-1)k_{n}}}{1-\left(\frac{2en}{\ell_{0}k_{n}}e^{-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))}\right)^{\ell_{0}(\ell_{0}-1)}}.$

Let $(\delta_{n})_{n\geq 1}$ a sequence in $(0,1)$, such that $\delta_{n}n$ is
an integer and $\delta_{n}$ converges to a number $\delta\in[0,1)$. For
$k_{n}=\delta_{n}n$, we see

$P_{\theta_{0,n}}\Pi_{n}(W_{n,\ell_{0},k_{n}}\mid X^{n})\leq
2\frac{\left(2e\delta_{n}^{-1}\ell_{0}^{-1}e^{-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))}\right)^{\delta_{n}\ell_{0}(\ell_{0}-1)n}}{1-\left(2e\delta_{n}^{-1}\ell_{0}^{-1}e^{-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))}\right)^{\ell_{0}(\ell_{0}-1)}}.$

It follows from lemma C.1 that when $\delta_{n}n\geq 2$, and

$\ell_{0}(\ell_{0}-1)\left[-1-\log
2+\log\delta_{n}+\log\ell_{0}+(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))\right]\geq\sqrt{\frac{2}{\delta_{n}n}},$
$P_{\theta_{0,n}}\Pi_{n}(W_{n,\ell_{0},k_{n}}\mid X^{n})\leq
2e^{-\delta_{n}\ell_{0}(\ell_{0}-1)\left[-1-\log
2+\log\delta_{n}+\log\ell_{0}+(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))\right]n/4}.$

We define the Hamming metric $m_{n}$, closely related to $r_{n}$, on the
parameter space, again stepwise via a metric $m_{n}^{\prime}$ on
$\Theta_{n}^{\prime}$. Define $m_{n}^{\prime}$ on $\Theta_{n}^{\prime}$, by

$m_{n}^{\prime}(\theta^{\prime},\eta^{\prime})=\sum_{i=1}^{n}\mathbb{I}_{\theta_{i}^{\prime}\neq\eta_{i}^{\prime}},$

and next we define

$m_{n}(\theta,\eta)=\min_{\theta^{\prime}\in\theta,\eta^{\prime}\in\eta}m_{n}^{\prime}(\theta^{\prime},\eta^{\prime})$
(18)

on $\Theta_{n}$. The quantity $m_{n}(\hat{\theta}_{n},\theta_{0,n})$ counts
the number of misspecified labels of an estimator $\hat{\theta}_{n}$. Let

$\bar{B}_{n,k_{n}}(\theta_{n})=\left\\{\eta_{n}\in\Theta_{n,\ell_{0}}:r_{n}(\theta_{n},\eta_{n})\leq
k_{n}\right\\}$

and

$B_{n,k_{n}}(\theta_{n})=\left\\{\eta_{n}\in\Theta_{n}:m_{n}(\theta_{n},\eta_{n})\leq
k_{n}\right\\}.$ (19)

It follows from lemma B.7 that

$\bar{B}_{n,k_{n}/(\ell_{0}(\ell_{0}-1))}(\theta_{n})\subseteq
B_{n,k_{n}}(\theta_{n})\quad\text{and clearly}\quad
W_{n,\ell_{0},k_{n}}=\Theta_{n,\ell_{0}}\operatorname{\backslash}\bar{B}_{n,k_{n}-1}(\theta_{0,n}).$
(20)

Let now $\delta_{n}$ be a sequence of positive numbers such that
$\delta_{n}n/[\ell_{0}(\ell_{0}-1)]$ are integers,
$\delta_{n}/[\ell_{0}(\ell_{0}-1)]\in(0,1)$ and decreases to a number $\delta$
in $[0,1)$, then

$\displaystyle
P_{\theta_{0,n}}\Pi_{n}(\Theta_{m_{n,\ell_{0}}}\operatorname{\backslash}B_{n,\delta
n}\mid X^{n})$ $\displaystyle\leq$ $\displaystyle
P_{\theta_{0,n}}\Pi_{n}(\Theta_{m_{n,\ell_{0}}}\operatorname{\backslash}\bar{B}_{n,\delta_{n}n/[\ell_{0}(\ell_{0}-1)]-1}\mid
X^{n})$ $\displaystyle=$ $\displaystyle
P_{\theta_{0,n}}\Pi_{n}(W_{n,\ell_{0},\delta_{n}n/[\ell_{0}(\ell_{0}-1)]}\mid
X^{n})$ $\displaystyle\leq$ $\displaystyle 2e^{-\delta_{n}\left[-1-\log
2+\log\delta_{n}-\log(\ell_{0}-1)+(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16\ell_{0}^{2}(\ell_{0}-1))\right]n/4}.$

When $\delta_{n}\to 0$, $-\log\delta_{n}\to\infty$, so with the result of
example 3.6 almost exact convergence is achieved once
$(c_{n}^{1/2}-d_{n}^{1/2})^{2}\to\infty$ (however slowly). To be exact, for
$(c_{n}^{1/2}-d_{n}^{1/2})^{2}\geq 48L^{2}\log L$,
$\frac{\delta_{n}n}{L(L-1)}\geq 2$, and

$-1-\log
2+\log\delta_{n}-\log(L-1)+(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16L^{2}(L-1))\geq\sqrt{\frac{2L(L-1)}{\delta_{n}n}},$
(21)

$\displaystyle P_{\theta_{0,n}}\Pi_{n}(B_{n,\delta n})\mid X^{n})\leq
1-L_{n}\exp\left(-n{\frac{1}{48L^{2}}(\sqrt{c_{n}}-\sqrt{d_{n}})^{2}}\right)$
$\displaystyle-2e^{-\delta_{n}\left(-1-\log
2+\log\delta_{n}-\log(L-1)+(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16L^{2}(L-1))\right)n/4}.$

Note that condition eq. 21 is in particular satisfied when

$\delta_{n}:=2(L-1)e^{2-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16L^{2}(L-1))}$

and $(c_{n}^{1/2}-d_{n}^{1/2})^{2}$ converges to infinity. Then $\delta_{n}\to
0$ and

$P_{\theta_{0,n}}\Pi_{n}(B_{n,\delta n}\mid X^{n})\geq
1-L_{n}\exp\left(-n{\frac{1}{48L^{2}}\left(\sqrt{c_{n}}-\sqrt{d_{n}}\right)^{2}}\right)-2e^{-\delta_{n}n/4}.$

For fixed $\delta_{0}<1/L$, setting $(c_{n}^{1/2}-d_{n}^{1/2})^{2}$ so that
$\delta_{0}=2(L-1)e^{2-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16L^{2}(L-1))}$, and
$\delta_{n}=\left\lfloor
2(L-1)ne^{2-(c_{n}^{1/2}-d_{n}^{1/2})^{2}/(16L^{2}(L-1))}\right\rfloor/n$
gives concentration in a ball of radius $\delta_{0}n$. $\Box$

##  5 Coverage of credible sets with examples

Conditionally on an observation $X^{n}$, a credible set of credible level
$1-\alpha_{n}$ is a measurable subset $D_{n}(X^{n})$ of the parameter set with
posterior mass at least $1-\alpha_{n}$:

$\Pi_{n}(D_{n}(X^{n})\mid X^{n})\geq 1-\alpha_{n}.$

In our (discrete, finite) setting any set-valued map $x^{n}\mapsto
B_{n}(x^{n})\subseteq\Theta_{n}$, the corresponding map
$x^{n}\mapsto\Pi_{n}(B_{n}(x^{n})\mid x^{n})$ is measurable and positive, and
hence the integral $P_{\theta_{0}}\Pi_{n}(B_{n}(X^{n})\mid X^{n})$ is well-
defined, see appendix A for details. From this perspective, a credible set (of
confidence level $1-\alpha_{n}$) is a set-valued map $x^{n}\mapsto
D_{n}(x^{n})$ satisfying $\Pi_{n}(D_{n}(x^{n})\mid x^{n})\geq 1-\alpha_{n},$
for every $x^{n}\in{\mathscr{X}}_{n}$. In nonparametric setting, credible sets
can have bad coverage: [7] provides us with examples. However in this section
we show that in the case of exact recovery credible sets cover $\theta_{0,n}$
with high probability. In case of almost exact recovery we make the credible
sets larger in order to guarantee asymptotic coverage, using ideas of [12] and
[13].

###### Lemma 5.1

Let $n\geq 1$. Let $x^{n}\to B_{n}(x^{n})\subset\Theta_{n}$ be a set valued
map, such that $P_{\theta_{0}}\Pi_{n}(B_{n}(X^{n})\mid X^{n})\geq 1-a_{n}$,
with $0<a_{n}<1$. Then, for every $0<r_{n}<1$,

$P_{\theta_{0}}\left[\Pi_{n}(B_{n}(X^{n})\mid X^{n})\geq 1-r_{n}\right]\geq
1-\frac{1}{r_{n}}a_{n}.$

Proof Let $E_{n}=\left\\{\omega:\Pi_{n}(B_{n}\mid X^{n}(\omega))\geq
1-r_{n}\right\\}$ be the event that the posterior mass of $B_{n}(X^{n})$ is at
least $1-r_{n}$. Let $\delta>0$. Suppose that $P_{\theta_{0}}(E_{n})\leq
1-\frac{1}{r_{n}}a_{n}-\delta$. Then

$\displaystyle P_{\theta_{0}}\Pi_{n}(B_{n}(X^{n})\mid X^{n})\leq
P_{\theta_{0}}(E_{n})+(1-r_{n})P_{\theta_{0}}(E_{n}^{c})=P_{\theta_{0}}(E_{n})+(1-r_{n})(1-P_{\theta_{0}}(E_{n}))$
$\displaystyle=r_{n}P_{\theta_{0}}(E_{n})+1-r_{n}\leq
r_{n}\left(1-\frac{1}{r_{n}}a_{n}-\delta\right)+1-r_{n}=1-a_{n}-\delta
r_{n}<1-a_{n},$

which contradicts with our assumption that
$P_{\theta_{0}}\Pi_{n}(B_{n}(X^{n})\mid X^{n})\geq 1-a_{n}$. Hence
$P_{\theta_{0}}(E_{n})>1-\frac{1}{r_{n}}a_{n}-\delta$. As this holds for every
$\delta>0$, it follows that $P_{\theta_{0}}(E_{n})\geq
1-\frac{1}{r_{n}}a_{n}$. $\Box$

###### Lemma 5.2

Suppose $P_{\theta_{0}}\Pi_{n}(\left\\{\theta_{0,n}\right\\}\mid X^{n})\geq
1-x_{n}$, where $0<x_{n}<1$. Let $\alpha_{n}\in(0,1)$ and $D_{n}(X^{n})$ a
$1-\alpha_{n}$ credible set, i.e. $\Pi_{n}(D_{n}(X^{n})\mid X^{n})\geq
1-\alpha_{n}$. Then

$P_{\theta_{0,n}}(\theta_{0,n}\in D_{n}(X^{n}))\geq
1-\frac{1}{1-\alpha_{n}}x_{n}.$

Proof Let $E_{n}=\left\\{\Pi(\left\\{\theta_{0}\right\\}\mid X^{n})\geq
r\right\\}$ be the event that $\left\\{\theta_{0}\right\\}$ has posterior mass
at least $r$, $r>\alpha_{n}$. It follows from lemma 5.1 that
$P_{\theta_{0,n}}(E_{n})\geq 1-\frac{1}{1-r}x_{n}$. As $D_{n}(X^{n})$ has at
least $1-\alpha_{n}$ posterior mass, $D_{n}(X^{n})$ and
$\left\\{\theta_{0}\right\\}$ cannot be disjoint on the event $E_{n}$, as
$1-\alpha_{n}+r>1$. In other words, $\theta_{0}\in D_{n}(X^{n})$ on $E_{n}$.
So $P_{\theta_{0}}(\theta_{0}\in D_{n}(X^{n}))\geq P_{\theta_{0}}(E_{n})\geq
1-\frac{1}{1-r}x_{n}$. As this holds for any $r>\alpha_{n}$ we have
$P_{\theta_{0}}(\theta_{0}\in D_{n}(X^{n}))\geq
1-\frac{1}{1-\alpha_{n}}x_{n}$. $\Box$

###### Example 5.3

(Dense phase, continuation of examples 3.4 and 4.4) Let $D_{n}(X^{n})$ be a
$1-\alpha_{n}$ credible set, $0<\alpha_{n}<1$. With example 4.4 and lemma 5.2
we get

$\displaystyle P_{\theta_{0}}(\theta_{0,n}\in D_{n}(X^{n}))\geq
1-\frac{1}{1-\alpha_{n}}\left(L_{n}e^{-b_{n}n^{2}/(12L_{n}^{2})}+2\sqrt{e}e^{-nb_{n}/(8L_{n})}\right).$

$\Box$

###### Example 5.4

(Chernoff-Hellinger phase, continuation of examples 3.5 and 4.5) Let
$D_{n}(X^{n})$ be a $1-\alpha_{n}$ credible set, $0<\alpha_{n}<1$. With
example 4.5 and lemma 5.2 we get

$\displaystyle P_{\theta_{0}}(\theta_{0,n}\in D_{n}(X^{n}))\geq
1-\frac{1}{1-\alpha_{n}}\bigg{[}L_{n}\exp\left(-n{\frac{1}{48}(\sqrt{a_{n}}+\sqrt{b_{n}})^{2}\frac{\log
n}{L_{n}^{2}}}\right)$
$\displaystyle+2\sqrt{e}n^{-(a_{n}^{1/2}-b_{n}^{1/2})^{2}/(32L_{n})}\bigg{]}$
.

$\Box$

###  5.1 Enlarged credible sets

In the case of almost exact convergence, credible sets need to be enlarged, in
order to make them asymptotic confidence sets.

Let $n\geq 1$, let $D_{n}(X^{n})$ be a credible set. For a nonnegative integer
$k_{n}$, we define the $k_{n}$-enlargement of $D_{n}(X^{n})$ to be the set

$C_{n}(X^{n})=\left\\{\theta_{n}\in\Theta_{n}:\exists\eta_{n}\in
D_{n}(X^{n}),m_{n}(\theta_{n},\eta_{n})\leq k_{n}\right\\}.$

Recall the definition of $B_{n,k_{n}}(\theta_{0,n})$ in eq. 19,

$B_{n,k_{n}}(\theta_{n})=\left\\{\eta_{n}\in\Theta_{n}:m_{n}(\theta_{n},\eta_{n})\leq
k_{n}\right\\}.$

We have the following result

###### Lemma 5.5

Suppose $P_{\theta_{0}}\Pi_{n}(B_{n,k_{n}}(\theta_{0,n})\mid X^{n})\geq
1-x_{n}$, $0<x_{n}<1$. Let $\alpha_{n}\in(0,1)$ and $D_{n}(X^{n})$ a
$1-\alpha_{n}$-credible set, with $k_{n}$-enlargement $C_{n}$, then

$P_{\theta_{0,n}}(\theta_{0,n}\in C_{n}(X^{n}))\geq
1-\frac{1}{1-\alpha_{n}}x_{n}.$

.

Proof Let $E_{n}=\left\\{\Pi(B_{n,k_{n}}(\theta_{0,n})\mid X^{n})\geq
r\right\\}$ be the event that $B_{n,k_{n}}(\theta_{0,n})$ has posterior mass
at least $r$, $r>\alpha_{n}$. It follows from lemma 5.1 that
$P_{\theta_{0,n}}(E_{n})\geq 1-\frac{1}{1-r}x_{n}$. As $D_{n}(X^{n})$ has at
least $1-\alpha_{n}$ posterior mass, $D_{n}(X^{n})$ and
$B_{n,k_{n}}(\theta_{0,n})$ cannot be disjoint on the event $E_{n}$, as
$1-\alpha_{n}+r>1$. Hence $\theta_{0}\in C_{n}(X^{n})$ on $E_{n}$. So
$P_{\theta_{0}}(\theta_{0}\in C_{n}(X^{n}))\geq P_{\theta_{0}}(E_{n})\geq
1-\frac{1}{1-r}x_{n}$. As this holds for any $r>\alpha_{n}$ we have
$P_{\theta_{0}}(\theta_{0}\in C_{n}(X^{n}))\geq
1-\frac{1}{1-\alpha_{n}}x_{n}$. $\Box$

###### Example 5.6

(Kesten-Stigum phase, continuation of examples 3.6 and 4.6.) Let
$D_{n}(X^{n})$ a $1-\alpha_{n}$-credible set and $C_{n}(X^{n})$ the $a_{n}n$
enlargement of $D_{n}(X^{n})$, with
$a_{n}:=2(L-1)e^{2-\frac{1}{4L}(c_{n}^{1/2}-d_{n}^{1/2})^{2}}.$ With example
4.6 and lemma 5.5 we get

$P_{\theta_{0,n}}(\theta_{0,n}\in C_{n})\geq
1-\frac{1}{1-\alpha_{n}}\left(L_{n}\exp\left(-n{\frac{1}{48L^{2}}\left(\sqrt{c_{n}}-\sqrt{d_{n}}\right)^{2}}\right)+2e^{-a_{n}n/4}\right).$

$\Box$

##  6 Consistent hypothesis testing with posterior odds

Besides parameter estimation, an interesting question is testing between two
alternatives, whether the true parameter $\theta_{0,n}$ is in the set $A_{n}$
or in the set $B_{n}$, where $A_{n},B_{n}\subseteq\Theta_{n}$ are disjoint
non-random sets. In particular we consider symmetric testing between two
alternatives

$H_{0}:\theta_{0,n}\in A_{n}\quad\text{versus}\quad H_{1}:\theta_{0,n}\in
B_{n}.$

Taking, for example, $A_{n}=\Theta_{n,\ell_{0}}$ and
$B_{n}=\Theta_{n}\operatorname{\backslash}\Theta_{n,\ell_{0}}$ allows us to
test whether the true parameter has $\ell_{0}$ classes or not. The case
$\ell_{0}=1$ is testing between the Erdős-Rényi model and the stochastic block
model. We establish frequentist results for posterior odds testing between
$A_{n}$ and $B_{n}$.

We use posterior odds to test between the models, which is defined by

$F_{n}=\frac{\Pi_{n}(B_{n}\mid X^{n})}{\Pi_{n}(A_{n}\mid X^{n})}.$

Obviously, $F_{n}<1$ counts as evidence in favour of $H_{0}$ and $F_{n}>1$ as
evidence in favour of $H_{1}$. In the following theorem we give sufficient
conditions for this Bayesian test to be valid in a frequentist sense.

###### Theorem 6.1

Let $\theta_{0,n}\in\Theta_{n}$. When $P_{\theta_{0,n}}\Pi_{n}(A_{n}\mid
X^{n})\geq 1-a_{n}$, with $0<a_{n}<1$, then

$P_{\theta_{0,n}}(F_{n}>r_{n})\leq 2a_{n}\left(1+\frac{1}{r_{n}}\right).$

If, in addition, $P_{\theta_{0,n}}\Pi_{n}(B_{n}\mid X^{n})\leq b_{n}$, then

$P_{\theta_{0,n}}(F_{n}>r_{n})\leq 2a_{n}+\frac{2b_{n}}{r_{n}}.$

Proof From the posterior convergence condition on $A_{n}$ it follows that
$P_{\theta_{0,n}}\Pi_{n}(B_{n}\mid X^{n})\leq a_{n}$. Hence the first result
follows from the second, so we assume $P_{\theta_{0,n}}\Pi_{n}(B_{n}\mid
X^{n})\leq b_{n}$ in what follows. Let $E_{n}=\left\\{\Pi_{n}(A_{n}\mid
X_{n})\geq 1/2\right\\}$ be the event that the posterior gives at least mass
$1/2$ to $A_{n}$. It follows from lemma 5.1 that $P_{\theta_{0,n}}(E_{n})\geq
1-2a_{n}.$ So

$\displaystyle P_{\theta_{0,n}}(F_{n}>r_{n})\leq$ $\displaystyle
P_{\theta_{0,n}}\left(\Pi_{n}(B_{n}\mid X_{n})\geq r_{n}/2\right)+2a_{n}.$

The probability on the right is by the Markov inequality bounded by

$\frac{2}{r_{n}}P_{\theta_{0,n}}\Pi_{n}(B_{n}\mid
X_{n})\leq\frac{2b_{n}}{r_{n}}.$

We thus arrive at the result

$P_{\theta_{0,n}}(F_{n}>r_{n})\leq 2a_{n}+\frac{2b_{n}}{r_{n}}.$

$\Box$

Suppose one rejects the null-hypothesis when $F_{n}>r_{n}$, for some
$r_{n}>0$. The first order error is when $H_{0}$ is true, so $\theta_{0,n}$ is
in fact in $A_{n}$, but $H_{0}$ is rejected (so $F_{n}>r_{n}$). The
probability of this error is bounded by the theorem above. The error of second
kind is when in fact $H_{1}$ is true, but $H_{0}$ is not rejected. This
probability is given by $P_{\theta_{0,n}}(F_{n}<r_{n}),$ $\theta_{0,n}\in
B_{n}$. As
$P_{\theta_{0,n}}(F_{n}<r_{n})=P_{\theta_{0,n}}(F_{n}^{-1}>1/r_{n}),$ and
reversing the roles of $A_{n}$ and $B_{n}$ in theorem 6.1, the probability of
this event is also covered by the theorem, using posterior convergence results
for $\theta_{0,n}\in B_{n}$. The power of the test is defined as the
probability of rejecting the null hypothesis when $H_{1}$ is true. As
$P_{\theta_{0,n}}(F_{n}>r_{n})=P_{\theta_{0,n}}(F_{n}^{-1}<1/r_{n})=1-P_{\theta_{0,n}}(F_{n}^{-1}\geq
1/r_{n})$, this probability can be lower bounded with the theorem above.

###  6.1 Examples: consistent Bayesian testing

In this section we determine conditions for Bayesian testing for different
sparsity regimes. We consider the same priors and models as in example section
3.1.

We consider testing

$H_{0}:\theta_{0,n}\in\Theta_{n,\ell_{0}}\quad\text{versus}\quad
H_{1}:\theta_{0,n}\in\Theta_{n}\operatorname{\backslash}\Theta_{n,\ell_{0}}.$

So we consider testing whether the true parameter has $\ell_{0}$ classes or
not. The case $\ell_{0}=1$ is testing between the Erdős-Rényi graph and the
stochastic block model.

###### Example 6.2

(Dense phase, continuation of example 3.4) It follows from example 3.4 and
theorem 6.1 that

$P_{\theta_{0,n}}(F_{n}>r_{n})\leq
2L_{n}\left(1+\frac{1}{r_{n}}\right)e^{-b_{n}n^{2}/(12L_{n}^{2})}.$

Taking $r_{n}\equiv 1$, the error of first kind is bounded by
$4L_{n}e^{-b_{n}n^{2}/(12L_{n}^{2})}$. Reversing the roles of $A_{n}$ and
$B_{n}$ in theorem 6.1 gives the error of second kind is bounded by
$4e^{-b_{n}n^{2}/(12L_{n}^{2})}.$ and the power of the test is lower bounded
by $1-4e^{-b_{n}n^{2}/(12L_{n}^{2})}$. $\Box$

###### Example 6.3

(Chernoff-Hellinger phase, continuation of example 3.5) With example 3.5 and
theorem 6.1 we get for $\theta_{0,n}\in\Theta_{n,\ell_{0}}$

$P_{\theta_{0,n}}(F_{n}>r_{n})\leq
2L_{n}\left(1+\frac{1}{r_{n}}\right)\exp\left(-\frac{n}{48}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{\log
n}{L_{n}^{2}}\right)$

and for
$\theta_{0,n}\in\Theta_{n}\operatorname{\backslash}\Theta_{n,\ell_{0}}$,

$P_{\theta_{0,n}}(F_{n}^{-1}>r_{n}^{-1})\leq
2\left(1+r_{n}\right)\exp\left(-\frac{n}{48}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{\log
n}{L_{n}^{2}}\right),$

which is the bound for the second order error. The power for the test is lower
bounded by

$1-2\left(1+r_{n}\right)\exp\left(-{\frac{n}{48}\left(\sqrt{a_{n}}-\sqrt{b_{n}}\right)^{2}\frac{\log
n}{L_{n}^{2}}}\right).$

$\Box$

###### Example 6.4

(Kesten-Stigum phase, continuation example 3.6) It follow from example 3.6 and
theorem 6.1 that

$P_{\theta_{0,n}}(F_{n}>r_{n})\leq
2L\left(1+\frac{1}{r_{n}}\right)\exp\left(-{\frac{n}{48L^{2}}\left(\sqrt{c_{n}}-\sqrt{d_{n}}\right)^{2}}\right).$

And similar results as in the example above hold for the second order error
and the power of the test. $\Box$

##  Appendix A Definitions and conventions

#### Notation

When $S$ is a set, $|S|$ denotes the cardinality of $S$.

We assume for every $n\geq 1$, a random graph ${X^{n}}$ taking values in the
(finite) space ${\mathscr{X}}_{n}$ of all undirected simple graphs (i.e. no
self-loops or multiple edges) with $n$ vertices. Let ${\mathscr{B}}_{n}$ be
the powerset of ${\mathscr{X}}_{n}$, be the $\sigma$-algebra corresponding to
${\mathscr{X}}_{n}$ and let ${\mathscr{P}}_{n}$ be the set of all probability
distributions $P_{n}:{\mathscr{B}}_{n}\to[0,1].$ A model is a subset
$\operatorname{\mathcal{P}}_{n}$ of ${\mathscr{P}}_{n}$, which is parametrized
by an bijective mapping
$\Theta_{n}\rightarrow\operatorname{\mathcal{P}}_{n}:\theta\mapsto
P_{\theta_{n}}.$ We equip $\Theta_{n}$ with a $\sigma$-algebra
${\mathscr{G}}_{n}$ and a probability measure
$\Pi_{n}:{\mathscr{G}}_{n}\to[0,1]$ (the so-called prior). As we only consider
finite parameters sets $\Theta_{n}$, we set ${\mathscr{G}}_{n}$ to be the
powerset of $\Theta_{n}$. As frequentists, we assume that there exists a
‘true, underlying distribution for the data’; that means that for every $n\geq
1$, the $n$-th graph ${X^{n}}$ is drawn from $P_{{\theta}_{0,n}}$, for some
${\theta}_{0,n}\in{\Theta}_{n}$. We call ${\theta}_{0,n}$ the ‘true
parameter’.

###### Definition A.1

Given $n\geq 1$ and a prior probability measure $\Pi_{n}$ on ${\Theta}_{n}$,
define the _$n$ -th prior predictive distribution_ as:

$P_{n}^{\Pi_{n}}(A)=\int_{\Theta}P_{\theta_{n}}(A)\,d\Pi_{n}(\theta),$ (22)

for all $A\in{\mathscr{B}}_{n}$.

The prior predictive distribution $P_{n}^{\Pi_{n}}$ is the marginal
distribution for ${X^{n}}$ in the Bayesian perspective that considers
parameter and sample jointly
$(\theta,{X^{n}})\in\Theta\times{\mathscr{X}}_{n}$ as the random quantity of
interest.

###### Definition A.2

Given $n\geq 1$, a _(version of) the posterior_ is any map
$\Pi_{n}(\,\cdot\,|{X^{n}}=\,\cdot\,):{\mathscr{G}}_{n}\times{\mathscr{X}}_{n}\rightarrow[0,1]$
such that,

  1. 1.

for every $B_{n}\in{\mathscr{G}}_{n}$, the map
${\mathscr{X}}_{n}\rightarrow[0,1]:{x^{n}}\mapsto\Pi(B_{n}|{X^{n}}={x^{n}})$
is ${\mathscr{B}}_{n}$-measurable,

  2. 2.

for all $A_{n}\in{\mathscr{B}}_{n}$ and $V_{n}\in{\mathscr{G}}_{n}$,

$\int_{A_{n}}\Pi_{n}(V_{n}|{X^{n}})\,dP_{n}^{\Pi_{n}}=\int_{V_{n}}P_{\theta_{n}}(A_{n})\,d\Pi_{n}(\theta_{n}).$
(23)

Bayes’s Rule is expressed through equality (23) and is sometimes referred to
as a ‘disintegration’ (of the joint distribution of $(\theta_{n},X^{n})$).
Because the models ${\mathscr{P}}_{n}$ are dominated (denote the density of
$P_{\theta_{n}}$ by $p_{\theta_{n}}$), the fraction of integrated likelihoods,

$\Pi(V_{n}|{X^{n}})={\displaystyle{\int_{V_{n}}p_{\theta_{n}}({X^{n}})\,d\Pi_{n}(\theta_{n})}}\biggm{/}{\displaystyle{\int_{\Theta_{n}}p_{\theta_{n}}({X^{n}})\,d\Pi_{n}(\theta_{n})}},$
(24)

for all $V_{n}\in{\mathscr{G}}_{n}$, $n\geq 1$.

For completeness sake, we include [12, lemma 2.2], which plays an essential
role in our theorems on posterior consistency.

###### Lemma A.3

For any $B_{n},V_{n}\in{\mathscr{G}}_{n}$ with $\Pi_{n}(B_{n})>0$ and any
measurable map $\phi_{n}:{\mathscr{X}}_{n}\to[0,1]$,

$\displaystyle\int P_{\theta_{n}}\Pi_{n}(V_{n}\mid
X^{n})d\Pi_{n}(\theta_{n}\mid B_{n})\leq$ $\displaystyle\int
P_{\theta_{n}}[\phi_{n}(X^{n})]d\Pi_{n}(\theta_{n}\mid B_{n})$
$\displaystyle+\frac{1}{\Pi_{n}(B_{n})}\int_{V_{n}}P_{\theta_{n}}[1-\phi_{n}(X^{n})]d\Pi_{n}(\theta_{n}).$

##  Appendix B Existence of suitable tests

Given $n\geq 1$, and two class assignment vectors
$\theta_{0,n},\theta_{n}\in\Theta_{n}$, we are interested in determining
testing power, for which we need the likelihood ratio
$dP_{\theta_{n}}/dP_{\theta_{0,n}}$.

Fix $n\geq 1$, and let $X^{n}$ denote the random graph associated with
$\theta_{0,n}\in\Theta_{n}$, and let $\ell_{0}$ be the number of different
labels of $\theta_{0,n}$, so $\theta_{0,n}\in\Theta_{n,\ell_{0}}$. Let
$\theta_{n}$ denote another element of $\Theta_{n}$ and suppose
$\theta_{n}\in\Theta_{n,\ell}$, for some
$\ell\in\operatorname{\mathcal{L}}_{n}$ (which might or might not be equal to
$\ell_{0}$). Compare $p_{\theta_{0,n}}(X^{n})$ with $p_{\theta_{n}}(X^{n})$ in
the likelihood ratio. Recall that the likelihood of $\theta_{n}$ is given by,

$p_{\theta_{n}}(X^{n})=\prod_{i<j}Q_{i,j;n}(\theta_{n}^{\prime})^{X_{ij}}(1-Q_{i,j;n}(\theta_{n}^{\prime}))^{1-X_{ij}},$

where $\theta_{n}^{\prime}$ is a representation of $\theta_{n}$ and

$Q_{i,j;n}(\theta_{n}^{\prime})=\begin{cases}\,\,p_{n},&\quad\text{if
$\theta_{i}^{\prime}=\theta_{j}^{\prime}$,}\\\ \,\,q_{n},&\quad\text{if
$\theta_{i}^{\prime}\neq\theta_{j}^{\prime}$.}\end{cases}$

Let $\theta_{0,n}^{\prime}$ be a representation of $\theta_{0,n}$ and
$\theta_{n}^{\prime}$ a representation of $\theta_{n}$. Define two sets of
edges, one consisting of all edges that connect within a class under
$\theta_{0,n}^{\prime}$ and between classes under $\theta_{n}^{\prime}$, and
another consisting of all edges that connect between classes under
$\theta_{0,n}^{\prime}$ and within a class under $\theta_{n}^{\prime}$:

$\begin{split}D_{1,n}&=\\{(i,j)\in\\{1,\ldots,n\\}^{2}:\,i<j,\,\theta_{0,n,i}^{\prime}=\theta_{0,n,j}^{\prime},\,\theta_{n,i}^{\prime}\neq\theta_{n,j}^{\prime}\\},\\\
D_{2,n}&=\\{(i,j)\in\\{1,\ldots,n\\}^{2}:\,i<j,\,\theta_{0,n,i}^{\prime}\neq\theta_{0,n,j}^{\prime},\,\theta_{n,i}^{\prime}=\theta_{n,j}^{\prime}\\}.\end{split}$

Note that $D_{1,n}$ and $D_{2,n}$ do not depend on the chosen representations
of $\theta_{0,n}$ and $\theta_{n}$. Also define,

$(S_{n},T_{n}):=\Bigl{(}\sum\\{X_{ij}:(i,j)\in
D_{1,n}\\},\sum\\{X_{ij}:(i,j)\in D_{2,n}\\}\Bigr{)},$

and note that, under $P_{\theta_{0,n}}$ and $P_{\theta_{n}}$,

$(S_{n},T_{n})\sim\begin{cases}\text{Bin}(|D_{1,n}|,p_{n})\times\text{Bin}(|D_{2,n}|,q_{n}),\quad\text{if
$X^{n}\sim P_{\theta_{0,n}}$},\\\
\text{Bin}(|D_{1,n}|,q_{n})\times\text{Bin}(|D_{2,n}|,p_{n}),\quad\text{if
$X^{n}\sim P_{\theta_{n}}$}.\end{cases}$ (25)

Since $S_{n}$ and $T_{n}$ are independent, the likelihood ratio is fixed as a
product two exponentiated binomial random variables:

$\frac{p_{\theta_{n}}}{p_{\theta_{0,n}}}(X^{n})=\biggl{(}\frac{1-p_{n}}{p_{n}}\,\frac{q_{n}}{1-q_{n}}\biggr{)}^{S_{n}-T_{n}}\biggl{(}\frac{1-q_{n}}{1-p_{n}}\biggr{)}^{|D_{1,n}|-|D_{2,n}|}$
(26)

This gives rise to the following lemma:

###### Lemma B.1

Let $n\geq 1$, $\theta_{0,n},\theta_{n}\in\Theta_{n}$ be given. Then there
exists a test function $\phi_{n}:{\mathscr{X}}_{n}\to[0,1]$ such that,

$P_{\theta_{0,n}}\phi_{n}(X^{n})+P_{\theta_{n}}(1-\phi_{n}(X^{n}))\leq\rho(p_{n},q_{n})^{|D_{1,n}|+|D_{2,n}|}.$

Proof The likelihood ratio test $\phi_{n}(X^{n})$ has testing power bounded by
the Hellinger transform,

$P_{\theta_{0,n}}\phi_{n}(X^{n})+P_{\theta_{n}}(1-\phi_{n}(X^{n}))\leq
P_{\theta_{0,n}}\Bigl{(}\frac{p_{\theta_{n}}}{p_{\theta_{0,n}}}(X^{n})\Bigr{)}^{1/2},$

(see, e.g. [14] and [12, lemma 2.7]). Then

$\begin{split}P_{\theta_{0,n}}\biggl{(}\frac{p_{\theta_{n}}}{p_{\theta_{0,n}}}(X^{n})\biggr{)}^{1/2}&=P_{\theta_{0,n}}\biggl{(}\frac{p_{n}}{1-p_{n}}\,\frac{1-q_{n}}{q_{n}}\biggr{)}^{{\textstyle{\frac{1}{2}}}(T_{n}-S_{n})}\biggl{(}\frac{1-q_{n}}{1-p_{n}}\biggr{)}^{{\textstyle{\frac{1}{2}}}(|D_{1,n}|-|D_{2,n}|)}\\\
&=Pe^{{\textstyle{\frac{1}{2}}}\lambda_{n}S_{n}}\,Pe^{-{\textstyle{\frac{1}{2}}}\lambda_{n}T_{n}}\biggl{(}\frac{1-q_{n}}{1-p_{n}}\biggr{)}^{{\textstyle{\frac{1}{2}}}(|D_{1,n}|-|D_{2,n}|)},\end{split}$

where $\lambda_{n}:=\log(1-p_{n})-\log(p_{n})+\log(q_{n})-\log(1-q_{n})$ and
$(S_{n},T_{n})$ are distributed binomially, as in the first part of (25).
Using the moment-generating function of the binomial distribution, we conclude
that,

$\begin{split}&P_{\theta_{0,n}}\biggl{(}\frac{p_{\theta_{n}}}{p_{\theta_{0,n}}}(X^{n})\biggr{)}^{1/2}=\Bigl{(}1-p_{n}+p_{n}\Bigl{(}\frac{1-p_{n}}{p_{n}}\,\frac{q_{n}}{1-q_{n}}\Bigr{)}^{1/2}\Bigr{)}^{|D_{1,n}|}\\\
&\qquad\times\Bigl{(}1-q_{n}+q_{n}\Bigl{(}\frac{p_{n}}{1-p_{n}}\,\frac{1-q_{n}}{q_{n}}\Bigr{)}^{1/2}\Bigr{)}^{|D_{2,n}|}\biggl{(}\frac{1-q_{n}}{1-p_{n}}\biggr{)}^{{\textstyle{\frac{1}{2}}}(|D_{1,n}|-|D_{2,n}|)}\\\
&=\rho(p_{n},q_{n})^{|D_{1,n}|+|D_{2,n}|},\end{split}$

which proves the assertion. $\Box$

###  B.1 The sizes of $D_{1,n}$ and $D_{2,n}$

Let $\theta_{n}\in\Theta_{\bm{m}_{n,\ell}}$. There are
$\frac{1}{2}\sum_{i=1}^{\ell}m_{n,\ell,i}(m_{n,\ell,i}-1)$ pairs $(i,j),i<j$
with $\theta_{n,i}=\theta_{n,j}$.

We have

$\displaystyle\frac{1}{2}n(m_{n,\ell,\min}-1)\leq\frac{1}{2}\sum_{i=1}^{\ell}m_{n,\ell,i}(m_{n,\ell,i}-1)\leq\frac{1}{2}n(m_{n,\ell,\max}-1).$

###### Lemma B.2

Under 2.1,

$|D_{1,n}\cup
D_{2,n}|\geq\frac{1}{2}n(m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max}).$

Proof As there are at least $\frac{1}{2}n(m_{n,\ell_{0},\min}-1)$ elements
$(i,j),i<j$ for which $\theta_{0,n,i}=\theta_{0,n,j}$ and at most
$\frac{1}{2}n(m_{n,\ell,\max}-1)$ elements $(i,j),i<j$ for which
$\theta_{n,i}=\theta_{n,j}$, in case
$\frac{1}{2}n(m_{n,\ell_{0},\min}-1)>\frac{1}{2}n(m_{n,\ell,\max}-1)$ going
from $\theta_{0,n}$ to $\theta_{n}$ there are at least

$\displaystyle\frac{1}{2}n(m_{n,\ell_{0},\min}-1)-\frac{1}{2}n(m_{n,\ell,\max}-1)=\frac{1}{2}n(m_{n,\ell_{0},\min}-m_{n,\ell,\max})$

elements contributed to $D_{1,n}$.

In case
$\frac{1}{2}n(m_{n,\ell,\min}-1)\geq\frac{1}{2}n(m_{n,\ell_{0},\max}-1)$ going
from $\theta_{n}$ to $\theta_{0,n}$ there are at least

$\displaystyle\frac{1}{2}n(m_{n,\ell,\min}-1)-\frac{1}{2}n(m_{n,\ell_{0},\max}-1)=\frac{1}{2}n(m_{n,\ell,\min}-m_{n,\ell_{0},\max}).$

elements contributed to $D_{2,n}$. It follows from 2.1 that exactly one of
these two options occurs. Hence we have that $D_{1,n}\cup D_{2,n}$ consist of
at least

$\frac{1}{2}n(m_{n,\ell_{0}\wedge\ell,\min}-m_{n,\ell_{0}\vee\ell,\max})$

elements. $\Box$

###### Remark B.3

The lower bound may be obtained. (Let
$1^{k_{1}}2^{k_{2}}\ldots\ell^{k_{\ell}}$ denote the label vector with $k_{1}$
consecutive 1’s, followed by $k_{2}$ consecutive 2’s, etc.) Consider an even
$\ell_{0}$ and let $\ell=\ell_{0}/2$ and $m=2m_{0}$, $\bm{m}_{n,\ell_{0}}$ is
the $\ell_{0}$-vector $(m_{0},\ldots,m_{0})$ and $\bm{m}_{n,\ell}$ is the
$\ell$-vector $(m,\ldots,m)$. Let
$\theta_{0,n}=(1^{m_{0}}2^{m_{0}}\ldots\ell_{0}^{m_{0}})\in\Theta_{\bm{m}_{n,\ell_{0}}}$
and
$\theta_{n}=(1^{2m_{0}}2^{2m_{0}}\ldots(\ell_{0}/2)^{2m_{0}})\in\Theta_{\bm{m}_{n,\ell}}$.
Note that when $\theta_{0,n,i}=k$, then $\theta_{n,i}=\left\lceil
k/2\right\rceil$. It follows that $D_{1,n}$ is an empty set in this case. On
the other hand, if $\theta_{0,n,i}=2k+1$ and $\theta_{0,n,j}=2k+2$ with
$k\in\left\\{0,\ldots,\ell_{0}/2-1\right\\}$, then
$\theta_{n,i}=\theta_{n,j}=k+1$. There are
$\frac{1}{2}\ell_{0}m_{0}^{2}=\frac{1}{2}nm_{0}=\frac{1}{2}n|m_{0}-m|$ of such
combinations. Hence $\\#D_{2,n}=\frac{1}{2}n|m_{0}-m|$ and the lower bound is
actually achieved.

Obviously, the bound above is useless when $\theta_{n}$ and $\theta_{0,n}$
both belong to the same set $\Theta_{n,\ell}$.

The following lemma relates the number of elements in $D_{1,n}\cup D_{2,n}$ to
the $r_{n}$-distance (eq. 14) between $\theta_{0,n}$ and $\theta_{n}$.

###### Lemma B.4

For $\theta_{0,n},\theta_{n}\in\Theta_{n,\ell_{0}}$ with
$r=r_{n}(\theta_{0,n},\theta_{n})$, we have

$|D_{1,n}\cup D_{2,n}|\geq 2r(m_{n,\ell_{0},\min}-r)^{+},$

where for a real number $x,x^{+}=\max\left\\{0,x\right\\}$.

Proof Let $\theta_{0,n}^{\prime}$ and $\theta_{n}^{\prime}$ be representations
of $\theta_{0,n}$ and $\theta_{n}$, respectively, so that
$r_{n}^{\prime}(\theta_{0,n}^{\prime},\theta_{n}^{\prime})=r$. There are
$s,t\in\left\\{1,\ldots,\ell_{0}\right\\}$, $s\neq t$ so that there are
exactly $r$ vertices with $\theta_{0,n}^{\prime}$-label $s$ and
$\theta_{n}^{\prime}$-label $t$. Clearly, when this happens,
$m_{n,\ell_{0},s}\geq r$, and trivially, $m_{n,\ell_{0},s}\geq
m_{n,\ell_{0},1}\geq m_{n,\ell_{0},\min}$. It follows that $D_{1,n}$ has at
least $r(m_{n,\ell_{0},s}-r)\geq r(m_{n,\ell_{0},\min}-r)^{+}$ elements. Using
that $D_{1,n}$ and $D_{2,n}$ are disjoint and reversing the role of
$\theta_{0,n}$ and $\theta_{n}$ and $D_{1,n}$ and $D_{2,n}$ gives
$|D_{1,n}\cup D_{2,n}|\geq 2r(m_{n,\ell_{0},\min}-r)^{+}.$ $\Box$

###  B.2 The distance $r_{n}$ and the sets $V_{n,\ell,k}$

###### Lemma B.5

Let $\ell\leq\ell^{\prime}$. Let $\theta\in\Theta_{\bm{m}_{n,\ell}}$ and
$\eta\in\Theta_{\bm{\tilde{m}}_{n,\ell^{\prime}}}$. The distance
$r_{n}(\theta,\eta)$ is bounded by $m_{n,\ell,\ell}/2$, which in turn is
bounded by $m_{n,\ell,\max}/2$.

Proof Note that $\theta$ ($\eta$, resp.) is characterised by the partition of
$\left\\{1,\ldots,n\right\\}$ in $\ell$ ($\ell^{\prime}$, resp.) sets of sizes
$m_{n,\ell,1},\ldots,m_{n,\ell,\ell}$
($\tilde{m}_{n,\ell^{\prime},1},\ldots,\tilde{m}_{n,\ell^{\prime},\ell^{\prime}}$,
resp.). Vice versa, for such a partition, one can define a labelling, by
assigning a label to each set in the partition, and giving each element of the
set that label. Define

$\displaystyle\Xi_{\theta}=\left\\{\left\\{i:\theta_{i}^{\prime}=a\right\\}:a\in\left\\{1,\ldots,\ell\right\\}\right\\},$

note that $\Xi_{\theta}$ is independent of the representation, and define
$\Xi_{\eta}$ similarly. Now note that there are at most $\ell$ pairs of sets
$(A,B),A\in\Xi_{\theta},B\in\Xi_{\eta}$ with $|A\cap B|>m_{n,\ell,\ell}/2$,
because $\Xi_{\theta}$ consists of $\ell$ elements and $\Xi_{\eta}$ consists
of $\ell^{\prime}\geq\ell$ elements, and if there are more than $\ell$ such
pairs, then there is an $A$ in $\Xi_{\theta}$ and two different $B_{1},B_{2}$
in $\Xi_{\eta}$ such that $A\cap B_{1}$ and $A\cap B_{2}$ have more than
$m_{n,\ell,\ell}/2$ elements. But $B_{1}$ and $B_{2}$ are disjoint, so $A$ has
more than $m_{n,\ell,\ell}$ elements, which is a contradiction.

Let $(A_{1},B_{1}),\ldots,(A_{k},B_{k})$ the pairs with $|A_{i}\cap
B_{i}|>m_{n,\ell,\ell}/2$, with $k\leq\ell$($\leq\ell^{\prime}$). Define a
label $\theta^{\prime}\in\theta$ by assigning label $i$ to the sets $A_{i},$
$i\in\left\\{1,\ldots,k\right\\}$ and the remaining $\ell-k$ labels to the
remaining sets in the partition $\Xi_{\theta}$ and define
$\eta^{\prime}\in\eta$ similarly by assigning label $i$ to the sets $B_{i},$
$i\in\left\\{1,\ldots,k\right\\}$ and the remaining $\ell^{\prime}-k$ labels
to the remaining sets in $\Xi_{\eta}$. It follows that $r(\theta,\eta)\leq
r(\theta^{\prime},\eta^{\prime})\leq m_{n,\ell,\ell}/2$. By the definition of
$m_{n,\ell,\max}$, $m_{n,\ell,\ell}\leq m_{n,\ell,\max}$. $\Box$

Let $\theta\in\Theta_{\bm{m}_{n,\ell}}$ and define
$V_{n,\ell,k}(\theta)=\left\\{\eta\in\Theta_{n,\ell}:r_{n}(\theta,\eta)=k\right\\}.$

###### Lemma B.6

Let $\theta\in\Theta_{\bm{m}_{n,\ell}}$, and $k\leq m_{n,\ell,1}$. Then

$|V_{n,\ell,k}(\theta)|\leq
2^{k\ell(\ell-1)}\binom{n(\ell-1)}{\ell(\ell-1)k}\leq\left(\frac{2en}{k\ell}\right)^{\ell(\ell-1)k}.$
(27)

Note that eq. 27 is well defined when $k\ell\leq n$, which is the case when
$k\leq m_{n,\ell,1}$.

Proof When $\ell=1$, the lemma is trivial. Let $\ell>1$. Choose a
representation $\theta^{\prime}$ of $\theta$ so that exactly $m_{n,\ell,i}$
labels of $\theta^{\prime}$ are $i$, $i\in\left\\{1,\ldots,\ell\right\\}$. Let
us count the number of ways in which we can change the labelling
$\theta^{\prime}$ into a label $\eta^{\prime}$, while keeping
$r_{n}(\theta^{\prime},\eta^{\prime})\leq k$. Let
$i,j\in\left\\{1,\ldots,\ell\right\\},i\neq j$. We can choose
$\binom{m_{n,\ell,i}}{k}$ vertices with $\theta^{\prime}$-label $i$ and either
retain the label $i$ or give them them the label $j$. This is possible in
$2^{k}$ ways. There are $\ell-1$ labels $j\neq i$, and there are $\ell$ labels
$i$. Hence $V_{n,\ell,k}$ has at most

$2^{k\ell(\ell-1)}\prod_{i=1}^{\ell}\binom{m_{n,\ell,i}}{k}^{\ell-1}$

elements.

Using $\binom{a}{b}\binom{c}{d}\leq\binom{a+c}{b+d}$, the number of elements
in $V_{n,\ell,k}$ is bounded by

$2^{k\ell(\ell-1)}\binom{n(\ell-1)}{\ell(\ell-1)k}.$

Equation 27 is in turn bounded by

$\left(\frac{2en}{k\ell}\right)^{\ell(\ell-1)k}.$

$\Box$

###  B.3 The distance $m_{n}$

The distance $m_{n}$, restricted to $\Theta_{n,\ell}$ has the following
relationship with $r_{n}$:

###### Lemma B.7

For all $\theta,\eta\in\Theta_{n,\ell}$,

$r_{n}(\theta,\eta)\leq m(\theta,\eta)\leq\ell(\ell-1)r_{n}(\theta,\eta).$
(28)

Proof When $\ell=1$, $\Theta_{n,\ell}$ consist of only one element, and eq. 28
is trivial. Now suppose $\ell>1$. Every representation $\theta^{\prime}$ of
$\theta$ and $\eta^{\prime}$ of $\eta$ statifies
$r^{\prime}_{n}(\theta^{\prime},\eta^{\prime})\geq r_{n}(\theta,\eta)=:r$.
Hence, for fixed representations $\theta^{\prime}$ and $\eta^{\prime}$, there
are at least $r$ vertices with $\theta^{\prime}$ label $a$ have
$\eta^{\prime}$ label $b$, for some
$a,b\in\left\\{1,\ldots,\ell\right\\},a\neq b$. Hence
$m_{n}^{\prime}(\theta^{\prime},\eta^{\prime})\geq r$. So
$m_{n}(\theta,\eta)\geq r$. On the other hand, if $\theta^{\prime}$ and
$\eta^{\prime}$ are representations of $\theta$ and $\eta$, respectively, such
that
$r^{\prime}_{n,\ell}(\theta^{\prime},\eta^{\prime})=r_{n,\ell}(\theta,\eta)=:r$,
then there are at most $r$ vertices with $\theta^{\prime}$ label 1, that have
$\eta^{\prime}$ label 2, and at most $r$ vertices with $\theta^{\prime}$ label
$1$ that have $\eta^{\prime}$ label 3, etc. As there are $\ell-1$ labels not
equal to 1, and $\theta^{\prime}$ has $\ell$ labels, $m(\theta,\eta)\leq
m^{\prime}(\theta^{\prime},\eta^{\prime})\leq\ell(\ell-1)r$. $\Box$

##  Appendix C Auxiliary lemmas

###### Lemma C.1

Let $C\geq 2$. For all $x\geq\sqrt{2/C}$,

$\displaystyle\frac{e^{-Cx}}{1-e^{-x}}\leq e^{-Cx/4}.$

Proof Note that

$\displaystyle 1-e^{-x}$ $\displaystyle=\int_{0}^{x}e^{-y}dy$
$\displaystyle\geq xe^{-x}.$

Using this and the fact that $C-1\geq C/2$, we see that

$\displaystyle\frac{e^{-Cx}}{1-e^{-x}}\leq$
$\displaystyle\frac{e^{-Cx}}{xe^{-x}}=\frac{e^{-(C-1)x}}{x}\leq\frac{e^{-Cx/2}}{x}=\frac{e^{-Cx/4}}{x}e^{-Cx/4}.$

As $x\geq\sqrt{2/C}$ is equivalent to $Cx/4\geq x^{-1}/2$ and $x>0$, we have

$\displaystyle\frac{e^{-Cx}}{1-e^{-x}}\leq$ $\displaystyle
x^{-1}e^{-x^{-1}/2}e^{-Cx/4}.$

One verifies that $f(y)=ye^{-y/2}$ attains its maximum on ${\mathbb{R}}$ at
$y=2$ and $f(2)=2/e<1$. It now follows that

$\frac{e^{-Cx}}{1-e^{-x}}\leq e^{-Cx/4}.$

$\Box$

###### Lemma C.2

For $x\in[0,1]$, $\sqrt{1-x}\leq 1-x/2$.

Proof Define $f(x)=\sqrt{1-x}$ and $g(x)=1-x/2$. Note that $f(0)=g(0)$ and
$f^{\prime}(x)=-\frac{1}{2\sqrt{1-x}}\leq-\frac{1}{2}=g^{\prime}(x)$, for all
$x\in[0,1]$. It follows that $g(x)\geq f(x)$ for all $x\in[0,1]$. $\Box$

###### Lemma C.3

For all positive integers $r$ and real numbers $x>-r,$ $(1+x/r)^{r}\leq
e^{x}$.

Proof Let for $x>-r$, $f(x)=r\log(1+x/r)$ and $g(x)=x$. Then
$f^{\prime}(x)=\frac{1}{1+x/r}$ and $g^{\prime}(x)=1$. It follows that
$f^{\prime}(x)\leq g^{\prime}(x)$, when $x\geq 0$,
$f^{\prime}(x)>g^{\prime}(x)$ when $-n<x<0$ and $f(0)=g(0)$. It follows that
$f(x)\leq g(x)$ for all $x>-r$. As $y\to e^{y}$ is increasing, for all real
$y$, it follows that for all $x>-n$, $(1+x/r)^{r}=e^{f(x)}\leq
e^{g(x)}=e^{x}$. $\Box$

## References

  * [1] E. Abbe  “Community Detection and Stochastic Block Models: Recent Developments”  In _Journal of Machine Learning Research_ 18.177, 2018, pp. 1–86  URL: http://jmlr.org/papers/v18/16-480.html
  * [2] E. Abbe and C. 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  DOI: 10.1109/FOCS.2015.47
  * [3] 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, 2018, pp. 1334–1406  DOI: 10.1002/cpa.21719
  * [4] A. Channarond, J.-J. Daudin and S. Robin  “Classification and estimation in the Stochastic Blockmodel based on the empirical degrees”  In _Electron. J. Statist._ 6 The Institute of Mathematical Statisticsthe Bernoulli Society, 2012, pp. 2574–2601  DOI: 10.1214/12-EJS753
  * [5] Jingchun Chen and Bo Yuan  “Detecting functional modules in the yeast protein–protein interaction network”  In _Bioinformatics_ 22.18, 2006, pp. 2283–2290  DOI: 10.1093/bioinformatics/btl370
  * [6] M.S. Cline et al.  “Integration of biological networks and gene expression data using Cytoscape”  In _Nature protocols_ 2.10, 2007, pp. 2366–2382  DOI: 10.1038/nprot.2007.324
  * [7] D. Freedman  “On the Bernstein-Von Mises Theorem with Infinite-Dimensional Parameters”  In _The Annals of Statistics_ 27.4 Institute of Mathematical Statistics, 1999, pp. 1119–1140  URL: http://www.jstor.org/stable/120155
  * [8] C. Gao, A.W. van der Vaart and H.H. Zhou  “A General Framework for Bayes Structured Linear Models”  In _Annals of Statistics (accepted)_ , 2019  URL: https://www.e-publications.org/ims/submission/AOS/user/submissionFile/27372?confirm=67ba2787
  * [9] J. Geng, A. Bhattacharya and D. Pati  “Probabilistic Community Detection With Unknown Number of Communities”  In _Journal of the American Statistical Association_ 114.526 Taylor & Francis, 2019, pp. 893–905  DOI: 10.1080/01621459.2018.1458618
  * [10] P. Ghosh, D. Pati and A. Bhattacharya  “Posterior Contraction Rates for Stochastic Block Models”  In _Sankhya A_ , 2019  DOI: 10.1007/s13171-019-00180-5
  * [11] P. W. Holland, K. B. Laskey and S. Leinhardt  “Stochastic blockmodels: First steps”  In _Social Networks_ 5.2, 1983, pp. 109–137  DOI: https://doi.org/10.1016/0378-8733(83)90021-7
  * [12] B… Kleijn  “Frequentist validity of Bayesian limits”  In _Annals of Statistics (accepted)_ , 2020  URL: https://www.e-publications.org/ims/submission/AOS/user/submissionFile/34072?confirm=0095591e
  * [13] B… Kleijn and J. van Waaij  “Recovery, detection and confidence sets of communities in a sparse stochastic block model”  In _arXiv e-prints_ , 2018  arXiv:1810.09533
  * [14] L. Le Cam  “Asymptotic methods in statistical decision theory”  Springer-Verlag New York, 1986  DOI: 10.1007/978-1-4612-4946-7
  * [15] M. Mariadassou and C. Matias  “Convergence of the groups posterior distribution in latent or stochastic block models”  In _Bernoulli_ 21.1 Bernoulli Society for Mathematical StatisticsProbability, 2015, pp. 537–573  DOI: 10.3150/13-BEJ579
  * [16] E. Mossel, J. Neeman and A. Sly  “Consistency thresholds for the planted bisection model”  In _Electron. J. Probab._ 21 The Institute of Mathematical Statisticsthe Bernoulli Society, 2016, pp. 24 pp.  DOI: 10.1214/16-EJP4185
  * [17] S.L. van der Pas and A.W. van der Vaart  “Bayesian Community Detection”  In _Bayesian Anal._ 13.3 International Society for Bayesian Analysis, 2018, pp. 767–796  DOI: 10.1214/17-BA1078
  * [18] A.Y. Zhang and H.H. Zhou  “Minimax rates of community detection in stochastic block models”  In _Ann. Statist._ 44.5 The Institute of Mathematical Statistics, 2016, pp. 2252–2280  DOI: 10.1214/15-AOS1428