Original Article Journal Section Jonathan Flossdorf, Department of Statistics,
TU Dortmund University, Vogelpothsweg 87, 44221 Dortmund, Germany
<EMAIL_ADDRESS>Mercator Research Center Ruhr (MERCUR),
Grant Number: PR-2019-0019

# Goodness-of-fit testing based on graph functionals for homogeneous Erdös-
Rényi graphs

Barbara Brune  Institute of Statistics and Mathematical Methods in Economics,
TU Wien, Vienna, Austria  Jonathan Flossdorf  Department of Statistics, TU
Dortmund University, Dortmund, Germany  Carsten Jentsch  Department of
Statistics, TU Dortmund University, Dortmund, Germany

###### Abstract

The Erdös-Rényi graph is a popular choice to model network data as it is
parsimoniously parametrized, straightforward to interpret and easy to
estimate. However, it has limited suitability in practice, since it often
fails to capture crucial characteristics of real-world networks. To check its
adequacy, we propose a novel class of goodness-of-fit tests for homogeneous
Erdös-Rényi models against heterogeneous alternatives that permit non-constant
edge probabilities. In this context, we allow for both asymptotically dense
and sparse networks. The tests are based on graph functionals that cover a
broad class of network statistics for which we derive limiting distributions
in a unified manner. The resulting class of asymptotic tests includes several
existing tests as special cases. Further, we propose a parametric bootstrap
and prove its consistency, which enables performance improvements particularly
for small network sizes and avoids the often tedious variance estimation for
asymptotic tests. Moreover, we analyse the sensitivity of different goodness-
of-fit test statistics that rely on popular choices of subgraphs. We evaluate
the proposed class of tests and illustrate our theoretical findings by
extensive simulations.

###### keywords:

Stochastic networks; asymptotic theory; parametric bootstrap; random graphs;
subgraph counts; bootstrap consistency

##  1 Introduction

Due to the technical progress in recent decades, not only the amount of data
is growing but also its complexity. Hence, the analysis of statistical network
data has become a popular research objective with applications ranging from
social sciences [27, 5] or biology [1, 25] to logistics and transportation
processes [16]. Various mathematical and computational methods have been
developed to analyze, model, and understand the behaviour of networks. As
network data is rather complex by nature, it is a typical first step to find
suitable complexity reduction methods. A common approach is to calculate
various sorts of summary statistics from the observed network such as matrix
norms or centrality measures that may describe the network structure from
different perspectives. However, the general difficulty is to be aware of the
limited information that those statistics are able to capture [8, 7], since
they reduce the information of a whole network to a few scalar values. Another
approach is to fit a suitable network model to the observed data in order to
analyze graphs in a simplified and controlled setup and to perform statistical
inference. One of the simplest network models is the Erdös-Rényi model [10] in
which the edges are considered as independent Bernoulli variables with a
common probability parameter $p$. Obviously, this model may have substantial
shortcomings in modeling real world networks. Due to the assumption that all
edges form independently with the same probability, it usually fails to
capture many of their features, e.g. in social networks two people are more
likely to know each other if they have a common friend. This yields clusters
of vertices that have a higher edge probability between each other than to
other vertices. A solution for this is to fit more general random graph models
that allow for varying edge probabilities leading to the class of heterogenous
Erdös-Rényi models [24] with the stochastic block model (SBM) [12] as a
popular special case. Whereas these heterogenous models might match the
features of real world networks noticeably better than their homogenous
counterparts, their rigorous analysis is much more cumbersome from a graph
theory point of view. From a practitioner’s perspective, it is desirable to
choose the most parsimonious model with as few parameters as possible in order
to simplify the estimation process which is why the homogenous Erdös-Rényi
model with only one probability parameter is still a popular benchmark model.
Therefore, it is a crucial question if the usage of a parsimonious model is
justified or if a more complex model achieves a significantly better fit. This
leads to the field of goodness-of-fit procedures that aims to decide whether a
specified model fits the underlying data adaquately or if another alternative
would be a better choice.

Several approaches for goodness-of-fit testing for random graphs have been
proposed in the literature. This involves tests for the number of communities
in stochastic block models which are based on the largest singular value of a
residual matrix that is obtained by the difference of the estimated block mean
effect and the adjacency matrix [17]. Similarly, the principal eigenvalue [3]
or the maximum entry [13] of a centered and scaled adjacency matrix is used to
test whether a random graph is generated by a homogenous Erdös-Rényi model or
a stochastic block model. For the same hypotheses, [9] developed an asymptotic
test based on specific subgraph counts. Subgraph counts as a test statistic
are also used in [19] under the rather restrictive and often unrealistic
assumption that multiple independent and identically distributed samples of
graphs of the same size are available, and in [23] within a Monte-Carlo
framework. A more general goodness-of-fit method is proposed in [6], where the
goal is to test whether the probability matrix of independent samples of a
heterogenous graph matches a specified reference matrix that has to be assumed
to be known. To do so, optimal minimax sample complexities in various matrix
norms such as e.g. the Frobenius norm are derived. In [24], goodness-of-fit
tests for Erdös-Rényi-type models have been derived based on the degree
variance statistic that serves as an heterogeneity index of a graph [28]. A
statistical test for exponential random graph models [26] is proposed in [31]
with test statistics that are derived from a kernel Stein discrepancy.
Furthermore, a goodness-of-fit method for stochastic actor oriented models
[29] is presented in [18].

We investigate a unified approach for goodness-of-fit testing for homogeneous
Erdös-Rényi models. Precisely, we propose tests that aim to tell whether an
observed network was either generated by some homogenous Erdös-Rényi model or
by some other, more heterogenous model. Contrary to the related literature, we
do not limit our analysis to a particular test statistic, but use the concept
of graph functionals which allows for a unified treatment in theory and
practice. Precisely, we propose a class of test statistics that covers a wide
range of popular network metrics such as the degree variance statistic,
average centrality metrics, as well as subgraph counts of arbitrary order and
shape. Hence, our approach is very flexible and contains various already
proposed tests [9, 24] as special cases. Following this approach, we derive
general asymptotic theory for the whole proposed class of test statistics in a
unified manner. This particularly avoids the tedious derivation of the
individual asymptotics for newly proposed test statistics that fall into our
framework in a case by case manner. Furthermore, while the implementation of
asymptotic tests is often tedious as their variances are highly case-
dependent, we also propose a parametric bootstrap approach and prove a general
bootstrap consistency result in order to develop bootstrap versions of the
goodness-of-fit tests. These enable us to gain finite sample improvements and
to circumvent the tedious variance estimation.

The paper is organized as follows. It starts off with the necessary graph
theory concepts in Section 2, including theory on graph functionals and random
graphs. Particularly, we recap important traits of graph functionals and
extend them in order to enable the derivation of general asymptotic theory and
the development of asymptotic goodness-of-fit tests for these class of
statistics. In Section 3, we derive the required theory for enabling the
construction of parametric bootstrap versions of this test. Based on this
theory, we construct the novel class of goodness-of-fit tests both in an
asymptotic and a bootstrap manner in Section 4. We give detailed examples and
investigate the suitability of several specific graph functionals for
goodness-of-fit testing in the case of SBM alternatives. Subsequently, we
evaluate the performance of the proposed procedure in an extensive simulation
study in Section 5. The final Section 6 consists of some concluding remarks.
Most proofs and additional results are deferred to the Appendix.

##  2 Random Graphs and Graph Functionals

In this chapter, we give an overview of the used network generating models and
the concept of graph functionals. Particularly, we gather and extend existing
limiting distribution theory for this class of statistics in order to enable
the development of unified asymptotic and bootstrap goodness-of-fit tests
based on graph functionals.

###  2.1 Settings

Suppose we observe a random graph $G$ that is defined by a vertex set
$V=V(G)$, and edge set $E=E(G)$. The edge set consists of pairs of vertices
$\\{v_{1},v_{2}\\}$, where $v_{1},v_{2}\in V(G)$. We denote by
$n:=n(G)=|V(G)|$ the number of vertices, and by $m:=m(G)=|E(G)|$ the number of
edges of the graph $G$, respectively. The vertex set is denoted by
$V(G)=\\{v_{1},...,v_{n}\\}$, and each edge in $E(G)$ connects two of the
vertices. The network can alternatively be represented by an adjacency matrix
$A=(A_{ij})$ of dimension $(n\times n)$. In this paper, we concentrate on
unweighted and undirected networks without self-loops, which are often called
simple graphs. Their adjacency matrices are binary and symmetric such that
$A_{ij}=1$ indicates the presence of an edge between two vertices $i$ and $j$,
and $A_{ij}=0$ if there is no edge between the respective vertices. As self-
loops are not allowed, we have $A_{ii}=0$ for all $i$. Throughout the paper,
we focus on goodness-of-fit testing for random graphs. As mentioned, we use
the well-established Erdös-Rényi graph as the benchmark model.

######  Definition 2.1 (Definition 1).

[Erdös-Rényi (ER) graph] Let $G=(V,E)$ be a random graph on $n$ vertices with
adjacency matrix $A$ and let $p\in[0,1]$ be the connection probability. Then,
we call $G$ an Erdös-Rényi graph $\mathcal{G}(n,p)$, if the edges are
realizations of stochastically independent and identically Bernoulli
distributed random variables. That is, for $1\leq i<j\leq n$, we have
$A_{ij}\sim\mathnormal{\textup{Bin}}(1,p)$ with $A_{ji}:=A_{ij}$, and
$A_{ii}:=0$ for all $i$. We denote the resulting ER model class by

$\displaystyle\mathcal{G}_{ER}(n)=\\{\mathcal{G}(n,p),p\in[0,1]\\}.$

As the ER-model has quite restrictive assumptions, various generalizations
have been studied. A quite flexible alternative is the heterogenous Erdös-
Rényi model [24].

######  Definition 2.2 (Definition 2.).

[Heterogenous Erdös-Rényi (HER) graph] Let $G=(V,E)$ be a random graph on $n$
vertices with adjacency matrix $A$ and let $\bm{P}=(p_{ij})_{i,j=1,...,n}$ be
the symmetric $(n\times n)$ matrix of connection probabilities. Then, we call
$G$ a heterogenous Erdös-Rényi graph $\mathcal{G}(n,\bm{P})$, if the edges are
realizations of stochastically independent Bernoulli random variables. That
is, for $1\leq i<j\leq n$, we have
$A_{ij}\sim\mathnormal{\textup{Bin}}(1,p_{ij})$ with $A_{ji}:=A_{ij}$, and
$A_{ii}:=0$ for all $i$. We denote the resulting HER model class by

$\displaystyle\mathcal{G}_{HER}(n)=\\{\mathcal{G}(n,\bm{P}),\bm{P}=(p_{ij}),p_{ii}=0,p_{ij}=p_{ji},p_{ij}\in[0,1]\
\forall\ i,j\\}.$

In a nutshell, the HER-model expands the classical ER-model by offering the
opportunity for individual link probabilities for each edge. This expansion is
helpful for the modeling of more flexible scenarios, but also increases the
complexity, e.g. regarding parameter estimation, which might even become
infeasible without further restrictions. Hence, we are interested in testing
whether a parsimonious homogenous ER-model is already sufficient to model the
underlying data or whether a HER-model achieves a significantly better fit.
Consequently, having observed a simple graph $G$ of size $n$, we consider the
testing problem

$\displaystyle\text{H}_{0}:~{}G\in\mathcal{G}_{ER}(n)\qquad\text{vs.}\qquad\text{H}_{1}:~{}G\in\mathcal{G}_{HER}(n)\backslash\mathcal{G}_{ER}(n).$
(1)

Note that $\mathcal{G}_{ER}(n)\subset\mathcal{G}_{HER}(n)$ and, although
$\mathcal{G}_{HER}(n)$ can be decomposed into disjoint sets, that is, in
$\mathcal{G}_{ER}(n)$ and $\mathcal{G}_{HER}(n)\backslash\mathcal{G}_{ER}(n)$
as above, it will not be possible to consistently detect arbitrary
alternatives, when testing $H_{0}$ against $H_{1}$. This is because a
heterogenous ER model has to deviate sufficiently enough from the homogenous
model to be able to detect it, since we only rely on a single network
observation in the goodness-of-fit context.

###  2.2 Graph Functionals

In our work, we use the concept of graph functionals for the development of a
general and rich class of goodness-of-fit tests. In this subsection, we gather
classical existing theory for graph functionals and discuss extensions
suitable for the derivation of general asymptotic theory for these goodness-
of-fit tests.

####  2.2.1 General Concept

Graph functionals cover a wide range of network statistics, which might be
favorable for goodness of fit testing as they can capture various structural
patterns of the rather complex nature of network data.

######  Definition 2.3 (Definition 3.).

[Graph isomorphism and graph functional] Let $G$ and $H$ be two simple graphs.
An isomorphism of graph $G$ onto $H$ is a bijection $\varphi:V(G)\to V(H)$
such that any two vertices $v_{1},\,v_{2}\in V(G)$ are adjacent in $G$ if and
only if the vertices $\varphi(v_{1}),\,\varphi(v_{2})\in V(H)$ are adjacent in
$H$. If there exist an isomorphism between $G$ and $H$, we call $G$ and $H$
isomorphic. Furthermore, we denote by $\text{iso}_{n}(H)$ the set of
isomorphisms on $n\geq n(H)$ vertices. A real-valued random variable
$X_{n}=X_{n}(G)$ is called a graph functional if it only depends on the
isomorphism type of a graph $G$ of size $n$, i.e. if $X_{n}(G)=X_{n}(H)$ holds
for all $G$ and $H$ that are isomorphic.

In other words, a graph functional is a function that does not hinge on the
vertex labels. Although our proposed procedure in this paper is applicable to
any kind of graph functional, we apply two special use cases throughout for
illustration purposes.

######  Example 2.4 (Example 1.).

[Degree Variance] The degree variance $V_{n}$ of a (simple) graph $G=(V,E)$ is
defined as

$\displaystyle V_{n}:=\frac{1}{n}\sum_{i=1}^{n}(D_{i}-\overline{D}_{n})^{2},$

where $D_{i}$ is the degree of vertex $v_{i}$ and
$\overline{D}_{n}=\frac{1}{n}\sum_{i=1}^{n}D_{i}$ denotes the average degree
of the underlying network $G$. Note that the individual degrees $D_{i}$ do
actually hinge on the vertex labels. However, it is easy to see that the sum
of (squared) degrees as well as the average degree do not change by relabeling
the graph. Hence, the degree variance $V_{n}$ is invariant under isomorphism
change and, consequently, it is a graph functional. The degree variance is
quite popular as it is an intuitive metric that can handily be computed. It is
also used for goodness-of-fit testing in [24] and particularly serves as a
heterogeneity index of a graph as pointed out by [28]. In [8], it is further
investigated with the result that $V_{n}$ performs reasonable in capturing
local structures of the graph (e.g. centraility traits), but has weaknesses
when it comes to capturing global characteristics like the overall amount of
links.

######  Example 2.5 (Example 2).

[(Centered) Subgraph counts] Let $G$ be a graph on $n$ vertices, and $H$ be
another graph with $n(H)\leq n$. Then, the raw subgraph count of $H$ in $G$ is
defined by

$\displaystyle T_{n}(H):=\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\prod_{e\in
E(\widetilde{H})}\mathbbm{1}\\{e\in E(G)\\},$ (2)

The centered subgraph count of $H$ in $G$ is defined by

$\displaystyle S_{n}(H):=\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\prod_{e\in
E(\widetilde{H})}\Big{(}\mathbbm{1}\\{e\in E(G)\\}-\mathbb{P}(e\in
E(G))\Big{)}.$ (3)

By construction, $S_{n}(H)$ is a random variable with expectation 0 for models
with independently formed edges, as $\mathbb{P}(e\in
E(G))=\mathbb{E}(\mathbbm{1}\\{e\in E(G)\\})$.

Note that in a relabeled graph, the subgraph of interest may be existent
between different node combinations than in the observed graph. However, the
sum of this type of subgraph stays the same over the whole network which is
why those statistics also belong to the class of graph functionals. Subgraph
counts are popular metrics for characterizing networks and are used for
various inferential approaches [20, 9, 2]. However, these methods typically
make use of subgraph counts having a specified simple shape and small order
which makes them quite restrictive in their practical application. However,
already for simple subgraph structures, the computational effort quickly
becomes large in comparison e.g. to the degree variance. Their usage as a
graph functional, however, enables us to derive asymptotics in a unified way
for flexible shapes and orders as we will show throughout the paper.

####  2.2.2 Unified Representation

The key foundation of our unified procedure lies in a fundamental relationship
between centered subgraph counts and graph functionals: Any graph functional
can be written as a linear combination of (possibly infinitely many) centered
subgraph counts $S_{n}(H_{i})$, $i=1,2,...$ . This expansion enables the
unified derivation of the asymptotic distributions of graph functionals
$X_{n}$. This method is referred to as the method of higher projections.

######  Proposition 2.6 (Janson et al, 2011, Lemma 6.42).

A graph functional $X_{n}$ of a $\mathcal{G}(n,p)$ graph has a unique
decomposition into variables $S_{n}(H),~{}H\in\mathcal{H}$, where
$\mathcal{H}$ is a family of subgraphs without isolated vertices:

$\displaystyle X_{n}=\sum_{H\in\mathcal{H}}a_{n}(H)S_{n}(H).$

The $a_{n}(H)$’s are real-valued coefficients depending on $n,p,H$. The terms
in the sum are orthogonal, hence

$\displaystyle\mathbb{V}\text{ar}(X_{n})=\sum_{H\in\mathcal{H}}a_{n}^{2}(H)\mathbb{V}\text{ar}(S_{n}(H)).$

The coefficients $a_{n}(H)$ are uniquely determined by

$\displaystyle
a_{n}(H)=\frac{\mathbb{E}(X_{n}S_{n}(H))}{\mathbb{E}(S_{n}^{2}(H))}.$

For a given sequence of connection probabilities
$p=p(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1]$, we call $X_{n}$ dominated by
a family of connected graphs $\mathcal{H}_{0}$, i.e.
$|\mathcal{H}_{0}|<\infty$, if

$\displaystyle\frac{\mathbb{V}\text{ar}(X_{n})}{\sum_{H\in\mathcal{H}_{0}}a_{n}^{2}(H)\mathbb{V}\text{ar}(S_{n}(H))}=\frac{\sum_{H\in\mathcal{H}}a_{n}^{2}(H)\mathbb{V}\text{ar}(S_{n}(H))}{\sum_{H\in\mathcal{H}_{0}}a_{n}^{2}(H)\mathbb{V}\text{ar}(S_{n}(H))}\xrightarrow[n\to\infty]{}1.$

Note that the expectation of $X_{n}$ is represented solely by the coefficient
$a_{n}(\emptyset)$, i.e. $E(X_{n})=a_{n}(\emptyset)$. This is because the
count of null graphs is deterministic and given by $S_{n}(\emptyset)=1$ and
all other terms $S_{n}(H)$, $H\not=\emptyset$, are centered by construction.
Being dominated by a family of connected graphs $\mathcal{H}_{0}$ means that
asymptotically all the variance of the graph functional $X_{n}$ is explained
by information contained in a finite set of connected subgraphs. In
particular, any disconnected subgraph in $\mathcal{H}$ will asymptotically not
contribute to the variance as we will later see for the example of the degree
variance below.

####  2.2.3 Asymptotics

This representation of graph functionals as a linear combination of centered
subgraph counts enables the unified derivation of asymptotics for the whole
class of graph functionals as we can use asymptotic results for $S_{n}(H)$ for
this task. For deriving these asymptotics, it is convenient to slightly
reformulate $S_{n}(H)$. To this purpose, let the $m=\binom{n}{2}$ possible
edges of a graph $G$ be associated with independent random variables
$Y_{1},...,Y_{m}$ such that $Y_{i}$ has a Bernoulli distribution, i.e.

$\displaystyle Y_{i}\sim\text{Bin}(1,p),\text{ where }p\in(0,1)\text{ for
}i=1,...,m.$

Thus, the edge set of a $\mathcal{G}_{ER}(n)$ graph $G$ can be equivalently
written as $E(G)\,=\,\\{Y_{1},...,Y_{m}\\}$. Alternatively to the
representation in Example 2, subgraph counts can then be expressed in terms of
the variables $Y_{1},...,Y_{m}$. Replacing the indicators $\mathbbm{1}\\{e\in
E(G)\\}$ by the respective random variables $Y_{i}$ leads to the
representations

$\displaystyle
T_{n}(H)=\sum_{\tilde{H}\in\text{iso}_{n}(H)}\prod_{i:\,Y_{i}\in
E(\widetilde{H})}Y_{i}.$ (4)

and

$\displaystyle
S_{n}(H)=\sum_{\tilde{H}\in\text{iso}_{n}(H)}\prod_{i:\,Y_{i}\in
E(\widetilde{H})}(Y_{i}-p)$ (5)

for the raw and centered subgraph counts, respectively. Asymptotic
distributions of raw subgraph counts $T_{n}(H)$ in $\mathcal{G}_{ER}(n)$
setups have been investigated in [22] and [21]. Precisely, they showed that
the subgraph counts of form $T_{n}(H)$ follow an asymptotic normal
distribution if the underlying model is $\mathcal{G}_{ER}(n)$. In our setup,
however, we are interested in finding the asymptotic distributions for
centered subgraph counts $S_{n}(H)$ in order to get also asymptotic results
for graph functionals via Proposition 2.6. In this context, it is helpful
that, for fixed $n$, we can calculate the expectation and variance of the
statistics $S_{n}(H)$ as well as the covariance of two different counts
$S_{n}(H)$ and $S_{n}(J)$.

######  Proposition 2.7 (Janson et al., 2011, Lemma 6.41).

Let $H$ and $J$, $H,J\neq\emptyset$, be graphs without isolated vertices, let
$|\text{aut}(H)|$ denote the cardinality of automorphisms of $H$, i.e. the
number of isomorphisms from $H$ to itself, and
$(x)_{y}=x(x-1)(x-2)\cdots(x-y+1)$ denotes the descending factorials. Then, we
have

  * (a)

$\mathbb{E}(S_{n}(H))=0$.

  * (b)

$\mathbb{V}\text{ar}(S_{n}(H))=|\text{aut}(H)|(n)_{n(H)}(p(1-p))^{m(H)}$

  * (c)

If $H$ and $J$ are non-isomorphic, then $S_{n}(H)$ and $S_{n}(J)$ are
orthogonal, that is, $\mathbb{C}\text{ov}(S_{n}(H),S_{n}(J))=0.$

The closed and rather simple form of the variance of $S_{n}(H)$ stated in
Proposition 2.7(b) is a clear advantage opposed to raw subgraph count
statistics $T_{n}(H)$. It results from the orthogonality of the different
terms of the sum representing $S_{n}(H)$. Namely, we have

$\displaystyle\mathbb{C}\text{ov}(Y_{i}-p,Y_{j}-p)=\mathbb{E}\Big{(}(Y_{i}-p)\cdot(Y_{j}-p)\Big{)}=0\quad\forall\,i\neq
j$

due to the pairwise independence of the variables $Y_{i}$, $i=1,...,m$. The
orthogonality of $S_{n}(H)$ and $S_{n}(J)$ stated in Proposition 2.7(c)
follows in a similar manner. This property is particularly helpful in deriving
the joint distribution of multiple subgraph counts. Under mild conditions, the
statistics $S_{n}(H)$ with connected structures $H$ have an asymptotic normal
distribution.

######  Proposition 2.8 (Janson et al., 2011, Theorem 6.43).

Let $p=p(n)\xrightarrow[n\to\infty]{}p_{0}$ with $p_{0}\in[0,1]$. Then, for
each unlabelled graph $H$ without isolated vertices with

$\displaystyle np^{r(H)}\xrightarrow[n\to\infty]{}\infty,$ (6)

with $r(H)=\max_{J\subseteq H}d(J)$, where $d(J)=m(J)/n(J)$, denotes the
density of $J$, there exists a random variable $U(H)$ such that

$\displaystyle n^{-n(H)/2}p^{-m(H)/2}S_{n}(H)\xrightarrow{~{}d~{}}U(H).$ (7)

The convergence also holds jointly for any finite number of graphs $H$
satisfying the above condition $np^{r(H)}\xrightarrow[n\to\infty]{}\infty$.
The limiting variables are determined by the following properties:

  * (a)

If $H$ is connected and $m(H)>0$, then

$\displaystyle U(H)\sim\mathcal{N}(0,|\text{aut}(H)|(1-p_{0})^{m(H)})$

  * (b)

If $H_{1},...,H_{m}$ are different (i.e. non-isomorphic) connected unlabelled
graphs, then the random variables $U(H_{1}),...,U(H_{m})$ are independent.

Furthermore, we have

$\displaystyle\mathbb{E}(U(H)^{2})=|\text{aut}(H)|(1-p_{0})^{m(H)}\quad\text{
for every }H$

and for two different unlabelled graphs without isolated vertices $H_{1}$ and
$H_{2}$, we have

$\displaystyle\mathbb{E}(U(H_{1})U(H_{2}))=0.$

Note that Proposition 2.8 generally allows for connection probabilities $p$
that remain fixed with increasing $n$, but also for sequences of connection
probabilities $p=p(n)$ converging to zero at a certain rate. In this context,
for a given subgraph $H$, the additional condition (6) restricts the possible
rates for $p(n)$. Precisely, this condition can be seen as a sparsity
assumption and prevents $p(n)$ converging to 0 too fast.

From Proposition 2.6, and the normality of the statistics $S_{n}(H)$ as stated
in Proposition 2.8, we can obtain results on the asymptotic normality of graph
functionals $X_{n}$.

######  Theorem 2.9 (Janson et al., 2011, Theorem 6.49).

Let $X_{n}$ be a graph functional of $\mathcal{G}(n,p)$ with
$p=p(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1]$. Suppose $X_{n}$ is dominated
by a family of connected graphs $\mathcal{H}_{0}$ such that, for all
$H\in\mathcal{H}_{0}$ and $np^{r(H)}\xrightarrow[n\to\infty]{}\infty$ with
$r(H)=\max_{J\subseteq H}d(J)$, where $d(J)=m(J)/n(J)$ denotes the density of
$J$, the coefficients

$\displaystyle
b(H)=\sup_{n}\frac{n^{n(H)/2}p^{m(H)/2}a_{n}(H)}{\sqrt{\mathbb{V}\text{ar}(X_{n})}}$

are finite and satisfy

$\displaystyle\sum_{H\in\mathcal{H}_{0}}b(H)^{2}|\text{aut}(H)|<\infty.$

Then, as $n\rightarrow\infty$, it holds

$\displaystyle\frac{X_{n}-\mathbb{E}(X_{n})}{\sqrt{\mathbb{V}\text{ar}(X_{n})}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1).$

In particular, there exists a sequence $(c_{n})_{n\in\mathbb{N}}$ such that
$c_{n}^{2}\mathbb{V}\text{ar}(X_{n})\rightarrow V^{2}>0$ leading to
$c_{n}(X_{n}-\mathbb{E}(X_{n}))\xrightarrow{~{}d~{}}\mathcal{N}(0,V^{2})$.

The general representation of graph functionals as a linear combination of
(possibly infinite) centered subgraph counts in Proposition 2.6 and the
limiting distributions derived in Theorem 2.9 form together a powerful tool
that enables the flexible construction of a wide range of test statistics for
goodness-of-fit testing for simple random graphs.

##  3 Bootstrap theory for graph functionals

While knowledge of the presented limiting distributions for the class of graph
functionals generally allows the construction and implementation of a powerful
testing procedure, such asymptotic tests might have issues when it comes to
small sample sizes, i.e. small network sizes $n$. Additionally, the derivation
of the centered subgraph representation following Proposition 2.6 is not
trivial and can be tedious. In order to provide a more flexible solution and
to gain finite sample improvements, we propose to use bootstrapping to
approximate the distribution of the test under the null.

###  3.1 Bootstrap Scheme

Having observed a simple random graph $G$, the bootstrap algorithm to estimate
the distribution of a graph functional $X_{n}$ under the null of an ER-graph
is defined as follows:

  1. Step 1.

Estimate the connection probability $p$ by
$\widehat{p}=\binom{n}{2}^{-1}\sum\limits_{1\leq i<j\leq n}A_{ij}$.

  2. Step 2.

Conditional on $\bm{A}=(A_{ij})_{1\leq i,j\leq n}$, generate an ER graph
$G^{*}$ by drawing a symmetric adjacency matrix
$\bm{A}^{*}=(A^{*}_{ij})_{1\leq i,j\leq n}$ from $\mathcal{G}(n,\hat{p})$.
That is, conditional on $\bm{A}=(A_{ij})_{1\leq i,j\leq n}$, we
$A_{ij}^{*}\sim\mathnormal{\textup{Bin}}(1,\widehat{p})$ for $1\leq i<j\leq n$
with $A_{ji}^{*}:=A_{ij}^{*}$, and $A_{ii}^{*}:=0$ for all $i$.

  3. Step 3.

Calculate the bootstrap graph functional $X_{n}^{*}=X_{n}(G^{*})$.

  4. Step 4.

Repeat Steps 2 and 3 $B$ times, where $B$ is large, to obtain $X_{n}^{*(b)}$,
$b=1,...,B$.

  5. Step 5.

Approximate the distribution of graph functional $X_{n}$ by the empirical
distribution of the bootstrap graph functionals
$X_{n}^{*(1)},\ldots,X_{n}^{*(B)}$ (percentile bootstrap) or, alternatively,
the distribution of the centered graph functional $X_{n}-\mathbb{E}(X_{n})$ by
the empirical distribution of the centered bootstrap graph functionals
$X_{n}^{*(1)}-\mathbb{E}^{*}(X_{n}^{*}),\ldots,X_{n}^{*(B)}-\mathbb{E}^{*}(X_{n}^{*})$
(Hall bootstrap), where $\mathbb{E}^{*}(\cdot)$ denotes the bootstrap
expectation conditional on the original network.

###  3.2 Bootstrap Theory

In the following theorem, we provide asymptotic theory for the bootstrap
procedure and prove its consistency in the framework of Theorem 2.9.

######  Theorem 3.1.

Suppose $G\in\mathcal{G}_{HER}$ with mean connectivity
$p_{\text{mean}}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}p_{ij}$ such that
$p_{\text{mean}}=p_{\text{mean}}(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1]$.
Further, let $X_{n}$ be a graph functional $X_{n}=X_{n}(G)$ computed from $G$.
Suppose that, under the null hypothesis of a homogeneous ER graph, i.e. when
$G\in\mathcal{G}_{ER}\subset\mathcal{G}_{HER}$, we have the representation
$X_{n}=\sum_{H\in\mathcal{H}}a_{n}(H)S_{n}(H)$ with $a_{n}(H)=a_{n}(H,p)$ that
is dominated by a family of connected graphs $\mathcal{H}_{0}$. For all
$H\in\mathcal{H}_{0}$, we suppose that
$np_{\text{mean}}^{r(H)}\xrightarrow[n\to\infty]{}\infty$ with
$r(H)=\max_{J\subseteq H}d(J)$, where $d(J)=m(J)/n(J)$ denotes the density of
$J$, the coefficients

$\displaystyle
b_{mean}(H)=\sup_{n}\frac{n^{n(H)/2}p_{\text{mean}}^{m(H)/2}a_{n}(H)}{\sqrt{\mathbb{V}\text{ar}(X_{n})}}$
(8)

are finite and satisfy

$\displaystyle\sum_{H\in\mathcal{H}_{0}}b_{mean}^{2}(H)|\text{aut}(H)|<\infty.$
(9)

Further, let $X_{n}^{*}=X_{n}(G^{*})$ denote the bootstrap version of the
graph functional $X_{n}$ of $G^{*}$ generated according to the bootstrap
scheme in Section 3.1. Then, we have
$X_{n}^{*}=\sum_{H\in\mathcal{H}}a_{n}^{*}(H)S_{n}^{*}(H)$ with
$a_{n}^{*}(H)=a_{n}(H,\widehat{p})$ and, as $n\rightarrow\infty$, it holds

$\displaystyle\frac{X_{n}^{*}-\mathbb{E}^{*}(X_{n}^{*})}{\sqrt{\mathbb{V}\text{ar}^{*}(X_{n}^{*})}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1)\quad\text{in
probability.}$

Additionally, with $(c_{n})_{n\in\mathbb{N}}$ and $V^{2}$ as defined in
Theorem 2.9, we have $c_{n}^{2}\mathbb{V}\text{ar}^{*}(X_{n}^{*})\rightarrow
V^{2}>0$ in probability.

As a direct consequence of Theorems 2.9 and 3.1, under the stated assumptions,
we get bootstrap consistency for the bootstrap procedure from Section 3.1 in
the sense that

$\displaystyle\sup_{x\in\mathbb{R}}\left|P_{H_{0}}(c_{n}(X_{n}-\mathbb{E}(X_{n}))),P^{*}(c_{n}(X_{n}^{*}-\mathbb{E}^{*}(X_{n}^{*})))\right|\rightarrow
0$ (10)

and
$c_{n}^{2}(\mathbb{V}\text{ar}(X_{n})-\mathbb{V}\text{ar}^{*}(X_{n}^{*}))\rightarrow
0$ in probability, respectively, where $P_{H_{0}}$ denotes the probability
under the null hypothesis of a homogeneous ER graph. The bootstrap consistency
result for the parametric bootstrap procedure in (10) enables the possibility
to construct goodness-of-fit tests based on graph functionals not only in an
asymptotic but also in a bootstrap manner. This has the great advantage that
we do not rely anymore on finding the explicit centered subgraph
representation of a graph functional as in Proposition 2.6 leading to a
handily applicable class of goodness-of-fit procedures.

##  4 Goodness-of-fit Testing for Erdös-Renyi Models

In this section, we formulate our unified approach for goodness-of-fit testing
for ER graphs. Precisely, we derive asymptotic level-$\alpha$ tests making use
of the general asymptotic theory from Section 2 and corresponding bootstrap
tests based on the theory from Section 3. Additionally, we give further
insights on the general use of centered and raw subgraph counts for goodness-
of-fit testing. Furthermore, we investigate the sensitivity of several test
statistics based on subgraph counts for certain SBM alternatives.

###  4.1 A deep example: Degree variance goodness-of-fit testing

As our derived theory enables the construction of novel goodness-of-fit tests
for a whole class of network metrics, let us first give a concrete example
from the literature for our procedure. We consider the already mentioned
degree variance statistic $V_{n}$ for which a goodness-of-fit test has been
proposed by [24]. Eventually, we will see that - although using a different
concept of proof - we come to the same result for our asymptotic version of
the test which underlines the unified characteristic of our approach that
contains this test as a special case.

Firstly, we consider the asymptotic version of the test. In Section 2.2.1, we
already argued that $V_{n}$ is a graph functional. In order to find its
representation following Proposition 2.6, we consider the centered version
$V_{n}-\mathbb{E}(V_{n})$, where $\mathbb{E}(V_{n})=n^{-1}(n-1)(n-2)p(1-p)$,
and use the Hoeffding decomposition [11, 15] as in [24]. Then, under the null
of a homogeneous ER graph, we get

$\displaystyle V_{n}-\mathbb{E}(V_{n})~{}=~{}$
$\displaystyle\frac{2(n-2)}{n^{2}}(1-2p)\sum_{1\leq i<j\leq
n}\widetilde{A}_{ij}+\frac{2(n-4)}{n^{2}}\sum_{1\leq i<j<k\leq
n}\left(\widetilde{A}_{ij}\widetilde{A}_{ik}+\widetilde{A}_{ij}\widetilde{A}_{jk}+\widetilde{A}_{ik}\widetilde{A}_{jk}\right)$
$\displaystyle-\frac{8}{n^{2}}\sum_{1\leq i<j<k<l\leq
n}\left(\widetilde{A}_{ij}\widetilde{A}_{kl}+\widetilde{A}_{ik}\widetilde{A}_{jl}+\widetilde{A}_{il}\widetilde{A}_{jk}\right)$
(11) $\displaystyle=:~{}$ $\displaystyle V_{n}^{(A)}+V_{n}^{(B)}+V_{n}^{(C)},$

where $\widetilde{A}_{ij}=A_{ij}-p$ are the centered entries of the adjacency
matrix. As the true parameter $p$ is usually not known in practice, the
consistent estimator $\widehat{p}$ can be used instead leading to the same
asymptotics. This is guaranteed by Corollary 4.1 below. The components of the
above decomposition are uncorrelated. This simplifies the derivation of the
moments of $V_{n}$, especially of its variance leading to

$\displaystyle\mathbb{V}\text{ar}(V_{n})=\mathbb{V}\text{ar}\Big{(}V_{n}^{(A)}\Big{)}+\mathbb{V}\text{ar}\Big{(}V_{n}^{(B)}\Big{)}+\mathbb{V}\text{ar}\Big{(}V_{n}^{(C)}\Big{)}.$

Consequently, the variance $\mathbb{V}\text{ar}(V_{n})$ decomposes into three
parts $\mathbb{V}\text{ar}(V_{n}^{(A)})$, $\mathbb{V}\text{ar}(V_{n}^{(B)})$
and $\mathbb{V}\text{ar}(V_{n}^{(C)})$ that correspond to the components that
are depicted in Figure 1 and can be calculated by

$\displaystyle\mathbb{V}\text{ar}(V_{n})~{}=~{}$
$\displaystyle\frac{2(n-1)(n-2)^{2}}{n^{3}}\,(1-2p)^{2}\,p(1-p)+\frac{2(n-1)(n-2)(n-4)^{2}}{n^{3}}\,\Big{(}p(1-p)\Big{)}^{2}$
(12) $\displaystyle+\frac{8(n-1)(n-2)(n-3)}{n^{3}}\,\Big{(}p(1-p)\Big{)}^{2}.$
(13)

Contrary to the presentations in [24], we argue that it is not $V_{n}^{(A)}$,
but the second part $V_{n}^{(B)}$, that makes the main contribution to the
variance of $V_{n}$, if $np\xrightarrow[n\to\infty]{}\infty$. In particular,
as $r(H)\geq 1$, the latter follows from

$\displaystyle np^{r(H)}\xrightarrow[n\to\infty]{}\infty,$ (14)

which is already assumed in Theorem 2.9. Intuitively, this allocation of the
variances makes sense. The information contained in part $V_{n}^{(A)}$ is the
centered number of edges in the observed network. This does not tell us much
about the structure of the graph. However, part $V_{n}^{(B)}$ counts the
number of edges that share a common node and are active – it is a rescaled
version of the centered count of two-stars (paths on three vertices with
length two). We will also denote this subgraph as $P_{3}$ in the remainder of
this paper. This part of the decomposition contains information on the local
structure of the observed network. Part $V_{n}^{(C)}$ counts the number of
pairs of _disjoint_ edges that are both active, again an information that does
not tell us much about the global or local structure. Hence, it seems
reasonable that $V_{n}^{(B)}$ contains most of the information of the network
and for that explains most of the variance.

$H_{1}:$ $H_{2}:$ $H_{3}:$

Figure 1: Subgraphs in the decomposition of the degree variance statistic.

The decomposition into $V_{n}^{(A)}$, $V_{n}^{(B)}$ and $V_{n}^{(C)}$ is the
linear combination of centered counts of the substructures $H_{1}$, $H_{2}$
and $H_{3}$, illustrated in Figure 1. It can be embedded into Proposition 2.6
by setting

$\displaystyle
a_{n}(H_{1})=\frac{2(n-2)}{n^{2}}(1-2p),~{}a_{n}(H_{2})=\frac{2(n-4)}{n^{2}},\text{
~{}and~{} }a_{n}(H_{3})=-\frac{8}{n^{2}}.$ (15)
$\displaystyle\mathbb{V}\text{ar}(S_{n}(H_{1}))=p(1-p)\frac{n^{2}-n}{2},~{}\mathbb{V}\text{ar}(S_{n}(H_{2}))=(p(1-p))^{2}\frac{(n-1)(n-2)n}{2},\text{
~{}and~{} }$ (16)
$\displaystyle\mathbb{V}\text{ar}(S_{n}(H_{3}))=(p(1-p))^{2}\frac{(n-1)(n-2)(n-3)n}{8}.$
(17)

Without loss of generality, we set $a_{n}(H_{i})=0$ if $n<m(H_{i})$ for any
$i\in\\{1,2,3\\}$. Eventually, Theorem 2.9 can be applied. For this, we need
to check if its assumptions are fulfilled. Firstly, a dominating family of
connected graphs is required. As $H_{3}$ is not connected and the variance
contribution of $H_{1}$ is negligible, we set $\mathcal{H}_{0}:=\\{H_{2}\\}$.
Then, we can verify that $\mathcal{H}_{0}$ is a dominating family of connected
graphs for $V_{n}$ by checking the corresponding condition. Indeed, we have

$\displaystyle\frac{\mathbb{V}\text{ar}(V_{n})}{\sum\limits_{H\in\mathcal{H}}a_{n}^{2}(H)\,\mathbb{V}\text{ar}(S_{n}(H))}=$
$\displaystyle\frac{\frac{2(n-1)(n-2)^{2}}{n^{3}}p(1-p)(1+(n-6)p(1-p))}{\frac{4(n-4)^{2}}{n^{4}}\frac{n(n-1)(n-2)}{6}3(p(1-p))^{2}}=\frac{n-2+(n^{2}-8n+12)}{(n^{2}-8n+16)}\xrightarrow[n\to\infty]{}\,\,1.$
(18)

Consequently, the variance of $V_{n}$ is explained by the dominating family
$\mathcal{H}_{0}$. Asymptotically it is solely driven by part $V_{n}^{(B)}$ of
the Hoeffding decomposition. As a second step, we need to check whether the
coefficient $b(H_{2})$ is finite for any $n\geq 4$. This yields

$\displaystyle b(H_{2})=$ $\displaystyle\sup_{n\geq
4}\frac{n^{3/2}p\,\,\frac{2(n-4)}{n^{2}}}{\sqrt{\frac{2(n-1)(n-2)^{2}}{n^{3}}p(1-p)(1+(n-6)p(1-p))}}$
(19)

The finiteness of the supremum above is implied by

$\displaystyle\lim_{n\to\infty}\sqrt{\frac{2(n^{2}-8n+16)n^{2}p}{(n-1)(n^{2}-4n+4)(1-p)(1+(n-6)p(1-p))}}=\sqrt{\frac{2}{(1-p_{0})^{2}}}<\infty\quad\forall\,p_{0}\in[0,1),$

Furthermore, as the dominating family $\mathcal{H}_{0}$ is finite, this
obviously leads to

$\displaystyle
b^{2}(H_{2})|\text{aut}(H_{2})|=6\cdot\frac{2}{(1-p_{0})^{2}}<\infty\quad\forall\,p_{0}\in[0,1).$
(21)

Thus, from (11) - (21), all conditions of Theorem 2.9 are fulfilled yielding
the asymptotic normality of $V_{n}-\mathbb{E}(V_{n})$. That is, for
$n\rightarrow\infty$, we have

$\displaystyle\frac{V_{n}-\mathbb{E}(V_{n})}{\sqrt{\mathbb{V}\text{ar}(V_{n})}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1).$
(22)

In particular, for $c_{n}^{2}=(np^{2}(1-p)^{2})^{-1}$, we have
$c_{n}^{2}\mathbb{V}\text{ar}(X_{n})\rightarrow 2$ and
$c_{n}(X_{n}-\mathbb{E}(X_{n}))\xrightarrow{~{}d~{}}\mathcal{N}(0,2)$. As
mentioned above, the true underlying parameter $p$ is usually not known in
practice. In order to enable an implementable result for the shown
asymptotics, we can make use of the following corollary.

######  Corollary 4.1.

  * (i)

Let $G\in\mathcal{G}_{ER}$ be a homogeneous ER graph $\mathcal{G}(n,p)$ with
$p=p(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1)$ such that
$np^{r(H_{2})}\xrightarrow[n\to\infty]{}\infty$. Then, the degree variance
$V_{n}$ standardized by its estimated moments is asymptotically standard
normal. That is, we have

$\displaystyle\frac{V_{n}-\mathbb{E}_{\widehat{p}}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{\widehat{p}}(V_{n})}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1),$

where
$\mathbb{E}_{\widehat{p}}(V_{n})=n^{-1}(n-1)(n-2)\widehat{p}(1-\widehat{p})$
and
$\mathbb{V}\text{ar}_{\widehat{p}}(V_{n})=n^{-3}2(n-1)(n-2)^{2}\widehat{p}(1-\widehat{p})(1+(n-6)\widehat{p}(1-\widehat{p}))$.

  * (ii)

Let $G\in\mathcal{G}_{HER}$ be a heterogeneous ER graph $\mathcal{G}(n,P)$
with mean connectivity $p_{\text{mean}}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq
n}p_{ij}$ such that
$p_{\text{mean}}=p_{\text{mean}}(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1)$
with $np_{\text{mean}}^{r(H_{2})}\xrightarrow[n\to\infty]{}\infty$. Then, the
bootstrap degree variance $V_{n}^{*}$ standardized by its estimated bootstrap
moments is asymptotically standard normal. That is, we have

$\displaystyle\frac{V_{n}^{*}-\mathbb{E}_{\widehat{p}^{*}}(V_{n}^{*})}{\sqrt{\mathbb{V}\text{ar}_{\widehat{p}^{*}}(V_{n}^{*})}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1),$

where
$\mathbb{E}_{\widehat{p}^{*}}(V_{n}^{*})=n^{-1}(n-1)(n-2)\widehat{p}^{*}(1-\widehat{p}^{*})$
and
$\mathbb{V}\text{ar}_{\widehat{p}^{*}}(V_{n}^{*})=n^{-3}2(n-1)(n-2)^{2}\widehat{p}^{*}(1-\widehat{p}^{*})(1+(n-6)\widehat{p}^{*}(1-\widehat{p}^{*}))$.

The proof of Corollary 4.1 can be found in Appendix A. An implementable
asymptotic level$-\alpha$ test is thus given by the decision rule

$\displaystyle\phi_{\alpha}(V_{n})=\begin{cases}1,&\text{ if
}\left|\frac{V_{n}-\mathbb{E}_{\hat{p}}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{\hat{p}}(V_{n})}}\right|>z_{1-\nicefrac{{\alpha}}{{2}}},\\\
0,&\text{ else,}\end{cases}$

where $z_{1-\nicefrac{{\alpha}}{{2}}}$ is the $(1-\nicefrac{{\alpha}}{{2}})$
quantile of the standard normal distribution. Following the procedure
explained in Section 3, a bootstrap version of the asymptotic level$-\alpha$
test is thus given by

$\displaystyle\phi_{\alpha}^{*}(V_{n})=\begin{cases}1,&\text{ if
}\left|\frac{V_{n}-\mathbb{E}_{\hat{p}}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{\hat{p}}(V_{n})}}\right|>z^{*}_{1-\nicefrac{{\alpha}}{{2}}},\\\
0,&\text{ else,}\end{cases}$

where $z^{*}_{1-\nicefrac{{\alpha}}{{2}}}$ is the
$(1-\nicefrac{{\alpha}}{{2}})$ quantile of the empirical distribution of the
resampled statistic
$\frac{V_{n}^{*}-\mathbb{E}_{\widehat{p}^{*}}(V_{n}^{*})}{\sqrt{\mathbb{V}\text{ar}_{\widehat{p}^{*}}(V_{n}^{*})}}$.
An alternative bootstrap test of asymptotic level$-\alpha$ is given by

$\displaystyle\widetilde{\phi}_{\alpha}^{*}(V_{n})=\begin{cases}1,&\text{ if
}\left|V_{n}-\mathbb{E}_{\hat{p}}(V_{n})\right|>z^{*}_{1-\nicefrac{{\alpha}}{{2}}},\\\
0,&\text{ else,}\end{cases}$

where $\widetilde{z}^{*}_{1-\nicefrac{{\alpha}}{{2}}}$ is the
$(1-\nicefrac{{\alpha}}{{2}})$ quantile of the empirical distribution of the
resampled statistic $V_{n}^{*}-\mathbb{E}_{\widehat{p}^{*}}(V_{n}^{*})$.

###  4.2 Goodness-of-fit testing based on subgraph counts

The studied example underlines the applicability of our proposed class of
tests both for the asymptotic as well as for the bootstrap version. Generally,
this procedure can be performed for an arbitrary graph functional fulfilling
the assumptions of Theorem 2.9. Thus, we now move on to investigate further
traits of test statistics that are based on subgraph counts. In this context,
we especially give a general result of Corollary 4.1 for arbitrary shapes of
$S_{n}(H)$. Additionally, we study to which extent our derived theory can also
be applied to raw subgraph counts of shape $T_{n}(H)$.

####  4.2.1 Centered Subgraph Counts

For general statistics $S_{n}(H)$ that are the foundation of our unified
testing procedure, the construction of asymptotic tests is analogous to the
example of the degree variance considered in detail in Section 4.1 as the
theory gathered in Section 2 can be applied. For the final formulation of an
implementable test, we can extend Corollary 4.1 to a more generalized version.

######  Theorem 4.2.

Let $G\in\mathcal{G}_{ER}$ be a homogeneous ER graph $\mathcal{G}(n,p)$ with
$p=p(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1)$. Further, let $H$ be a
connected subgraph and assume $np^{r(H)}\xrightarrow[n\to\infty]{}\infty$. We
define

$\displaystyle\widehat{S}_{n}(H):=\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\prod_{e\in
E(\widetilde{H})}(\mathbbm{1}\\{e\in E(G)\\}-\widehat{p}),$

where $\hat{p}=\binom{n}{2}^{-1}\sum\limits_{1\leq i<j\leq n}A_{ij}$ such that
$\widehat{p}-p=O_{P}(\frac{p}{n})$. Then, we have

$\displaystyle\frac{\widehat{S}_{n}(H)}{\sqrt{|\text{aut}(H)|(n)_{n(H)}(\widehat{p}(1-\widehat{p}))^{m(H)}}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1).$

That is, standardizing statistics $S_{n}(H)$ with their estimated moments does
not change the asymptotic distribution.

Thus, an asymptotic level-$\alpha$ tests for hypotheses (1) based on the
centered subgraph counts $S_{n}(H)$ are given by decision rules

$\displaystyle\phi_{\alpha}(S_{n}(H)):=\begin{cases}1,&\text{if~{}
}\left|\frac{\widehat{S}_{n}(H)}{\sqrt{|\text{aut}(H)|(n)_{n(H)}(\widehat{p}(1-\widehat{p}))^{m(H)}}}\right|>z_{1-\nicefrac{{\alpha}}{{2}}},\\\
0,&\text{else},\end{cases}$

where $z_{1-\nicefrac{{\alpha}}{{2}}}$ is the $(1-\nicefrac{{\alpha}}{{2}})$
quantile of the standard normal distribution. The proof of Theorem 4.2 can be
found in Appendix A. A bootstrap version can be easily implemened with the
usage of Theorem 3.1 analogously to the ones at the end of Section 4.1 above.

####  4.2.2 Raw Subgraph Counts

Although we mostly focus on the behaviour of centered subgraph counts
$S_{n}(H)$, it is a logical question whether the derived theory can be
extended to the more intuitive concept of raw subgraph counts $T_{n}(H)$. For
illustration, we will focus on $T_{n}(C_{3})$, i.e. the count of triangles.

[22] and [21] prove that subgraph counts of shape $T_{n}(H)$ follow an
asymptotic normal distribution if the underlying model is
$\mathcal{G}_{ER}(n)$. The crux in their derivation is an approximation based
on conditional expectations to avoid the heavy calculations for the variance
which result from the correlated terms in the raw subgraph counts. The proof
relies on advanced techniques for U-statistics.

For $T_{n}(C_{3})$, Theorem 4 from [22] gives

$\displaystyle\frac{T_{n}(C_{3})-\binom{n}{3}p^{3}}{(n-2)\sqrt{\binom{n}{2}p^{5}(1-p)}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1).$
(23)

Since $T_{n}(C_{3})$ is a graph functional, we can also apply the method of
higher projections to obtain this result. It can easily be shown that

$\displaystyle
T_{n}(C_{3})=S_{n}(C_{3})+pS_{n}(P_{3})+p^{2}(n-2)S_{n}(P_{2})+p^{3}|aut(C_{3})|.$
(24)

The closed form variance of $T_{n}(C_{3})$ can thus handily be derived as

$\displaystyle\mathbb{V}\text{ar}\left(T_{n}(C_{3})\right)=\binom{n}{3}\left(p(1-p)\right)^{3}+3\binom{n}{3}p^{2}\left(p(1-p)\right)^{2}+\binom{n}{2}(n-2)^{2}p^{5}(1-p).$
(25)

It can be shown that the variance is dominated by the contribution of
$S_{n}(P_{2})$, which is exactly the term used for standardization in (23).
This directly proves (23) by applying Proposition 2.6 and Theorem 2.9 with
dominating family $\mathcal{H}_{0}=\\{P_{2}\\}$.

In the manner of the previous subsection, one could try to construct a test
for hypotheses (1) based on the count of triangles $T_{n}(C_{3})$: In order to
be able to use this representation for a test of hypotheses (1), we need to
plug in estimates of the expectation and variance based on $\hat{p}$. However,
in this case the standardized test statistic, given as

$\displaystyle\widetilde{T}=\frac{T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}}{(n-2)\sqrt{\binom{n}{2}\widehat{p}^{5}(1-\widehat{p})}}$
(26)

no longer follows a standard normal distribution. This is because we obtain

$\displaystyle\frac{T_{n}(C_{3})-\mathbb{E}_{\widehat{p}}(T_{n}(C_{3}))}{\sqrt{\mathbb{V}\text{ar}_{\widehat{p}}(T_{n}(C_{3}))}}$
$\displaystyle=\frac{T_{n}(C_{3})-\mathbb{E}_{\widehat{p}}(T_{n}(C_{3}))-\mathbb{E}_{p}(T_{n}(C_{3}))+\mathbb{E}_{p}(T_{n}(C_{3}))}{\sqrt{\mathbb{V}\text{ar}_{\widehat{p}}(T_{n}(C_{3}))}}\frac{\sqrt{\mathbb{V}\text{ar}_{p}(T_{n}(C_{3}))}}{\sqrt{\mathbb{V}\text{ar}_{p}(T_{n}(C_{3}))}}$
(27)
$\displaystyle=\underbrace{\frac{\sqrt{\mathbb{V}\text{ar}_{p}(T_{n}(C_{3}))}}{\sqrt{\mathbb{V}\text{ar}_{\widehat{p}}(T_{n}(C_{3}))}}}_{\xrightarrow{n\to\infty}1}\left(\underbrace{\frac{T_{n}(C_{3})-\mathbb{E}_{p}(T_{n}(C_{3}))}{\sqrt{\mathbb{V}\text{ar}_{p}(T_{n}(C_{3}))}}}_{\xrightarrow{~{}d~{}}\mathcal{N}(0,1)}+\underbrace{\frac{\mathbb{E}_{p}(T_{n}(C_{3}))-\mathbb{E}_{\widehat{p}}(T_{n}(C_{3}))}{\sqrt{\mathbb{V}\text{ar}_{p}(T_{n}(C_{3})n)}}}_{=:T}\right)$
(28)

For the second term in brackets, one can also show with an application of the
delta method [30] that

$\displaystyle
T=\frac{\mathbb{E}_{p}(T_{n}(C_{3}))-\mathbb{E}_{\widehat{p}}(T_{n}(C_{3}))}{\sqrt{\mathbb{V}\text{ar}_{p}(T_{n}(C_{3}))}}\xrightarrow{~{}d~{}}\mathcal{N}(0,1).$
(29)

Thus, the limiting distribution of the potential test statistic changes if we
plug in estimated moments.

Since $\widehat{p}^{3}$ is a graph functional itself and, consequently, also
$T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}$, we again need to determine the
dominating family, but now for the centered raw subgraph count
$T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}$. Interestingly, the main variance
contribution no longer comes from $S_{n}(P_{2})$, but instead is explained by
the other two terms in the decomposition (24), i.e. $C_{3}$ and $P_{3}$.

The following lemma derives the dominating family for $\widehat{p}^{3}$, the
term used for centering in (26).

######  Lemma 4.3 (Dominating family for $\widehat{p}^{3}$).

Let $\widehat{p}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}A_{ij}$ be an estimate
for the parameter $p$ of an Erdös-Renyi graph. As $\hat{p}$ is a graph
functional, it we can be expressed in terms of centered subgraph counts. That
is, we have

$\displaystyle\widehat{p}=\binom{n}{2}^{-1}S_{n}(P_{2})+p.$ (30)

Obviously, the statistic $\widehat{p}^{3}$ has dominating family
$\mathcal{H}_{0}=\\{P_{2}\\}$ and, by using the method of higher projections,
we can write

$\displaystyle\widehat{p}^{3}=3\binom{n}{2}^{-1}p^{2}S_{n}(P_{2})+p^{3}+\mathcal{O}(n^{-2}).$
(31)

From Lemma 4.3, we can conclude that

$\displaystyle\binom{n}{3}\hat{p}^{3}=(n-2)p^{2}S_{n}(P_{2})+\binom{n}{3}p^{3}+\mathcal{O}(n).$
(32)

Combining (32) and (24), we get

$\displaystyle T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}=S_{n}(C_{3})+p\cdot
S_{n}(P_{3})+\mathcal{O}(n)$ (33)

and the leading term of the variance of
$T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}$ becomes

$\displaystyle\binom{n}{3}p^{3}(1-p)^{3}+3\binom{n}{3}p^{3}(1-p)^{2},$ (34)

which is the contribution to the variance are made by $C_{3}$ and $P_{3}$,
while the effect of $P_{2}$ is canceled out through subtraction of
$\widehat{p}^{3}$ from the raw subgraph count $T_{n}(C_{3})$. The findings are
summarized in the following Corollary 4.4. The obtained variance is exactly
the one reported in Theorem 2.2 in [9] for the same test statistic. This shows
how the unifying theory for the graph functionals pays off: It allows to
directly derive limiting distributions without further knowledge about the
statistic.

######  Corollary 4.4 (Dominating family and asymptotic distribution of
$\widetilde{T}$ in (26)).

Given the model $\mathcal{G}_{ER}(n)$ with $p\in(0,1)$. The raw count of
triangles centered with its estimated mean, that is,

$\displaystyle T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3},$ (35)

is a graph functional. It is dominated by $\mathcal{H}_{0}=\\{C_{3},P_{3}\\}$
where $a_{n}(C_{3})=1$ and $a_{n}(P_{3})=p$. Theorem 2.9 is applicable and
yields

$\displaystyle\frac{T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}}{\sqrt{\binom{n}{3}\widehat{p}^{3}(1-\widehat{p})^{3}+3\binom{n}{3}\widehat{p}^{4}(1-\widehat{p})^{2}}}\xrightarrow{d}\mathcal{N}(0,1).$
(36)

Thus, an asymptotic level-$\alpha$ tests for hypotheses (1) based on the test
statistic (36) are given by decision rules

$\displaystyle\phi_{\alpha}(\widehat{T}_{n}(C_{3})):=\begin{cases}1,&\text{if~{}
}\left\lvert\frac{T_{n}(C_{3})-\binom{n}{3}\widehat{p}^{3}}{\sqrt{\binom{n}{3}\widehat{p}^{3}(1-\widehat{p})^{3}+3\binom{n}{3}\widehat{p}^{4}(1-\widehat{p})^{2}}}\right\rvert>z_{1-\nicefrac{{\alpha}}{{2}}},\\\
0,&\text{else},\end{cases}$

where $z_{1-\nicefrac{{\alpha}}{{2}}}$ is the $(1-\nicefrac{{\alpha}}{{2}})$
quantile of the standard normal distribution.

Another option for a test of hypotheses (1) is offered by the bootstrap
methodology presented in Section 3.2. We can avoid having to standardize by
applying the bootstrap scheme presented in Section 3.1. We can directly use
$T_{n}(C_{3})$ as the tests statistic and approximate its distribution by the
resampling distribution of the statistics $T_{n}^{*}(C_{3})$, $b=1,...,B$. A
test for the null hypotheses $H_{0}$ in (1) can be performed using the
following decision rule

$\displaystyle\phi_{\alpha}(T_{n}(C_{3}))^{*}:=\begin{cases}1,&\text{ if
}{T}_{n}(C_{3})<q^{*}_{\nicefrac{{\alpha}}{{2}}}\text{ or
}{T}_{n}(C_{3})>q^{*}_{1-\nicefrac{{\alpha}}{{2}}},\\\ 0,&\text{
else,}\end{cases}$

where $q^{*}_{\nicefrac{{\alpha}}{{2}}}$ and
$q^{*}_{1-\nicefrac{{\alpha}}{{2}}}$ are the $\nicefrac{{\alpha}}{{2}}$ and
the $(1-\nicefrac{{\alpha}}{{2}})$ quantile of the bootstrap distribution of
the $T_{n}^{*}(C_{3})$.

###  4.3 Power Analysis for SBM alternatives

The main advantage of our unified goodness-of-fit testing procedure is that it
enables the user to use an arbitrary graph functional that fulfills the
assumptions of Theorem 2.9 for the construction of the test statistic without
tediously deriving the necessary asymptotics for each single case. A further
valuable aspect is that the class of graph functionals is quite broad, i.e.
there are a lot of different test statistics to choose from resulting in a
large flexibility for various application fields. However, as this class is
quite broad, it is crucial to choose an appropriate graph functional for a
succesful application and implementation in the underlying situation.
Obviously, each possible graph functional might be sensitive to different
network information and thus might be more or less suitable for a particular
data setup. This raises the question of which graph functional to use in which
situation. Because general statements are obviously very difficult to derive,
in the following, we give a concrete theory-driven analysis for a specific
example based on triangles, denoted as $C_{3}$, and two-stars, denoted as
$P_{3}$. Further examples are then investigated in an extensive simulation
study in Section 5.

For now, we consider the popular case of Stochastic Block Models (SBM) that
particularly plays an important role in modeling social network behaviours and
patterns. It assumes that the set of $n$ nodes can be divided into $K$ blocks.
Typically, nodes of the same block then have a higher probability to share an
edge than nodes of different blocks. SBMs of size $n$ are thus low-
parametrized special cases of $\mathcal{G}_{HER}(n)$ models. We restrict our
following power analysis to SBMs with $K=2$ blocks, equal block sizes (i.e.
$\nicefrac{{n}}{{2}}$) and equal intra-group probabilities $p_{\text{intra}}$
for both blocks. The edge probability between the groups are denoted by
$p_{\text{inter}}$ such that $p_{\text{intra}}\geq p_{\text{inter}}$. For
$p_{\text{intra}}=p_{\text{inter}}$, the SBM becomes a $\mathcal{G}_{ER}(n)$
model. To rule out detection just based on the total number of edges, we
generate models from both model classes such that their mean connectivity
parameters $p_{\text{mean}}$ (which is allowed to depend on $n$) coincide.
Note that, obviously, $p_{\text{mean}}=p$ for the $\mathcal{G}_{ER}(n)$ model
class.

####  4.3.1 Triangles $C_{3}$

Let us first focus on the performance of $C_{3}$. Therefore, we need to have a
closer look into the expectation of centered triangle counts for ER and SBM
models. In general, that is for both model classes, $\mathbb{E}(S_{n}(C_{3}))$
can be decomposed as follows

$\displaystyle\mathbb{E}(S_{n}(C_{3}))=(1-p)^{3}\mathbb{E}(I_{n}(C_{3}))+(1-p)^{2}(-p)\mathbb{E}(I_{n}(P_{3}))+(1-p)p^{2}\mathbb{E}(I_{n}(D_{3}))+(-p)^{3}\mathbb{E}(I_{n}(E_{3})),$

where the terms $I_{n}(H)$ denote counts of induced subgraphs. Furthermore,
$D_{3}$ is a subgraph consisting of three nodes and one edge and $E_{3}$ a
subgraph consisting of three nodes and no edges. Thus,
$\mathbb{E}(S_{n}(C_{3}))$ can be divided into a linear combination of
expected values of all possible subgraph shapes consisting of three nodes. The
coefficients represent the probabilities for the occurence of the
corresponding subgraph. In case of a homogenous ER-model, by construction,
these terms can be handily determined to get

$\displaystyle\mathbb{E}_{\text{ER}}(S_{n}(C_{3}))$
$\displaystyle=(1-p)^{3}\binom{n}{3}p^{3}+(1-p)^{2}(-p)3\binom{n}{3}(1-p)p^{2}+(1-p)p^{2}3\binom{n}{3}(1-p)^{2}p+\binom{n}{3}(1-p)^{3}(-p)^{3}$
$\displaystyle=(1-p)^{3}\binom{n}{3}p^{3}-p^{3}\binom{n}{3}(1-p)^{3}+(1-p)^{3}p^{3}3\binom{n}{3}-(1-p)^{3}p^{3}3\binom{n}{3}$
$\displaystyle=0.$

In case of an SBM, the situation is more complicated. While the corresponding
formulas for $\mathbb{E}_{\text{SBM}}(I_{n}(C_{3}))$ and
$\mathbb{E}_{\text{SBM}}(I_{n}(E_{3}))$ are rather straightforward to derive,
the derivation of the formulas for $\mathbb{E}_{\text{SBM}}(I_{n}(P_{3}))$ and
$\mathbb{E}_{\text{SBM}}(I_{n}(D_{3}))$ are more complicated and can be found
in the Appendix. Altogether, we obtain

$\displaystyle\begin{split}\mathbb{E}_{\text{SBM}}(S_{n}(C_{3}))&=(1-p_{\text{mean}})^{3}\left[2\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right){\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\right]\right]\\\
&+(1-p_{\text{mean}})^{2}(-p_{\text{mean}})\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})+2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})\right]\\\
&+(1-p_{\text{mean}})p_{\text{mean}}^{2}\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}(1-{\rm
Phys.~{}Rev.~{}A})^{2}+2n\binom{\nicefrac{{n}}{{2}}}{2}(1-{\rm
Phys.~{}Rev.~{}A})p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}(1-p_{\text{inter}})^{2}\right]\\\
&+(-p_{\text{mean}})^{3}\left[2\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A}^{3})+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)(1-{\rm
Phys.~{}Rev.~{}A})(1-p_{\text{inter}})^{2}\right]\right].\end{split}$ (37)

These results lead to the following useful Theorem.

######  Theorem 4.5.

Consider a homogenous ER-model and a Stochastic Block model (SBM) with two
blocks, equal block sizes and equal intra-group probability. Suppose that the
mean connectivity of both networks is the same, that is $p$ for the
$\mathcal{G}_{ER}$ model and $p_{\text{mean}}$ for the SBM model coincide.
Then, for the centered subgraph count $S_{n}(C_{3})$ and the raw subgraph
count $T_{n}(C_{3})$, respectively, we get

  * (a)

$\lim\limits_{n\rightarrow\infty}\mathbb{E}_{\text{ER}}(T_{n}(C_{3}))-\mathbb{E}_{\text{SBM}}(T_{n}(C_{3}))<0,\text{
if }p_{\text{intra}}>p_{\text{inter}}$,

  * (b)

$\lim\limits_{n\rightarrow\infty}\mathbb{E}_{\text{ER}}(S_{n}(C_{3}))-\mathbb{E}_{\text{SBM}}(S_{n}(C_{3}))<0,\text{
if }p_{\text{intra}}>p_{\text{inter}}$.

The proof of both statements can be found in the Appendix. In the context of
our work, we are more interested in statement (b) about the behaviour of the
centered subgraph count $S_{n}(C_{3})$. However, in both cases, the Theorem
guarantees that the expectation for an ER-model differs (asymptotically) from
the expectation computed from an SBM model. Thus, $C_{3}$ is sensitive to
distinguishing between both models. However, to give a reliable answer for the
suitability of $S_{n}(C_{3})$ for goodness-of-fit testing, we need to evaluate
to which extent this sensitivity exists. Before we analyze this in more
details, let us first concentrate on similar derivations for subgraph counts
based on $P_{3}$.

####  4.3.2 Two-stars $P_{3}$

Similar to the derivation above for triangles $C_{3}$, we can derive a
corresponding result also for two-stars. In the end, it yields
$\mathbb{E}_{\text{ER}}(S_{n}(C_{3}))=0$ and

$\displaystyle\begin{split}&\mathbb{E}_{\text{SBM}}(S_{n}(P_{3}))=3(1-p_{\text{mean}})^{2}\left[2\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right){\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\right]\right]\\\
&+\left[(1-p_{\text{mean}})^{2}+2(-p_{\text{mean}})(1-p_{\text{mean}})\right]\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})+2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})\right]\\\
&+\left[(-p_{\text{mean}})^{2}+2(-p_{\text{mean}})(1-p_{\text{mean}})\right]\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}(1-{\rm
Phys.~{}Rev.~{}A})^{2}+2n\binom{\nicefrac{{n}}{{2}}}{2}(1-{\rm
Phys.~{}Rev.~{}A})p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}(1-p_{\text{inter}})^{2}\right]\\\
&+3(-p_{\text{mean}})^{2}\left[2\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A}^{3})+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)(1-{\rm
Phys.~{}Rev.~{}A})(1-p_{\text{inter}})^{2}\right]\right]\end{split}$ (38)

leading to the following result.

######  Theorem 4.6.

Consider a homogenous ER-model and a Stochastic Block model (SBM) with two
blocks, equal block sizes and equal intra-group probability. Suppose that the
mean connectivity of both networks is the same, that is $p$ for the
$\mathcal{G}_{ER}$ model and $p_{\text{mean}}$ for the SBM model coincide.
Then, for the centered subgraph count $S_{n}(C_{3})$ and the raw subgraph
count $T_{n}(C_{3})$, respectively, we get

  * (a)

$\lim\limits_{n\rightarrow\infty}\mathbb{E}_{\text{ER}}(T_{n}(P_{3}))-\mathbb{E}_{\text{SBM}}(T_{n}(P_{3}))>0,\text{
if }p_{\text{intra}}>p_{\text{inter}}$,

  * (b)

$\lim\limits_{n\rightarrow\infty}\mathbb{E}_{\text{ER}}(S_{n}(P_{3}))-\mathbb{E}_{\text{SBM}}(S_{n}(P_{3}))>0,\text{
if }p_{\text{intra}}>p_{\text{inter}}$.

The derivations and proofs are analogous to before and can be found in the
Appendix.

####  4.3.3 Discussion

An investigation of the presented results for
$\mathbb{E}_{\text{SBM}}(S_{n}(P_{3}))$ and
$\mathbb{E}_{\text{SBM}}(S_{n}(C_{3}))$ enables us to analyze to which extent
the sensitivity for distinguishing SBMs from ER-models is pronounced for both
subgraph counts. Note that the analysis of the expected value in the SBM case
is sufficient in this context, since the expected value for ER-models is 0 as
shown. In this context, Figure 2 illustrates the behaviour of both derived
functions (absolute values) for different parameters $\epsilon={\rm
Phys.~{}Rev.~{}A}-p_{\text{inter}}$.

Figure 2: Expected absolute values of centered subgraph counts in the SBM case
with $p_{\text{mean}}=0.3$ and $n=100$.

Since we are in the situation of centered subgraph counts, the expected value
only depends on $\epsilon$. Particularly, the mean connectivity
$p_{\text{mean}}$ does not have direct influence. It has only indirect
influence on how large $\epsilon$ can be chosen, e.g. for
$p_{\text{mean}}=0.5$ there are more values of $\epsilon$ possible than for
$p_{\text{mean}}=0.1$ or $p_{\text{mean}}=0.9$ as ${\rm
Phys.~{}Rev.~{}A},p_{\text{inter}}\in[0,1]$ is required. Hence, Figure 2 that
is constructed for an $p_{\text{mean}}=0.3$ and $n=100$ stands representative
for arbitrary mean connectivity parameter $p_{\text{mean}}\in[0,1]$. It is
clearly visible that the absolute value of $\mathbb{E}(S_{n}(C_{3}))$ for SBMs
is larger than $\mathbb{E}(S_{n}(P_{3}))$. This behaviour is even more
pronounced for larger values of $\epsilon$. Consequently, the triangle
structure is way more sensitive to detecting these types of SBMs. Intuitively,
this makes sense as the condition for triangles are more restrictive than for
two-stars, since all links between the three involved nodes have to exist.
Obviously, this is easier to achieve in the dense blocks of a SBM than in an
ER-graph due to $p_{\text{intra}}>p_{\text{mean}}$. These results are
confirmed by the simulation study in Section 5, where we also evaluate the
behaviour for more flexible SBM setups with different parameters.

##  5 Simulation Study

To underline our findings and to gain further evidence for the proposed class
of tests, we execute a simulation study for different parameter setups and
various alternatives. We analyze the power of the tests and illustrate
performance differences depending on the chosen graph functional.

###  5.1 General Setting

We investigate three different graph functionals for the construction of the
test statistics. Namely, these are the degree variance statistic $V_{n}$,
centered triangle counts $S_{n}(C_{3})$ and centered two-star counts
$S_{n}(P_{3})$. For all three, we analyze their performances for the
asymptotic version and for the boostrap version of the testing procedure. To
investigate the power of these test statistics, we have to generate networks
from the alternative, i.e from the $\mathcal{G}_{HER}(n)$ model. In order to
be able to detect the alternative, the generated networks have to deviate from
the homogeneous null model by an increasing amount with increasing
heterogenity. To generate random graphs under the alternative, we set a mean
connectivity $p_{\text{mean}}$ such that the null model is a
$\mathcal{G}(n,p_{\text{mean}})$ model. This is to ensure that the power of
the tests is not due to differences in the mean connectivity (thus differing
degrees and mean degrees), but actually due to the rising heterogeneity of the
connection probabilities. Hence, we make the requirement:

$\displaystyle\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}p_{ij}=p_{\text{mean}}.$

This preserves the mean connectivity over all scenarios and settings. Although
this limits the possible alternatives, it is not a big constraint. Having an
observed network $G$, we can directly calculate its mean connectivity
$p_{\text{mean}}$. In order to study the performances in various network size
and density conditions, we use different values of $n=\\{16,32,64,128\\}$ and
$p_{\text{mean}}=p_{\text{mean}}(n)=\left\\{\frac{\log{n}}{n},\frac{1}{\sqrt{n}},\frac{\log{n}}{\sqrt{n}}\right\\}$.
Note that for these combinations of $n$ and $p_{\text{mean}}$ we have
$\frac{\log{n}}{n}<\frac{1}{\sqrt{n}}<\frac{\log{n}}{\sqrt{n}}$.

As the $\mathcal{G}_{HER}(n)$ model class is very broad, we limit the
simulation study to a few relevant scenarios for the alternative that serve as
representatives for different possible ways the matrix $\bm{P}$ can be set up.
These include the popular use case of SBMs and covariate models. For the SBMs,
we use two different setup versions including the usage of two blocks with
equal block sizes as in our analysis of Section 4.3 and the extension to three
blocks with random block sizes and varying intra-group probabilities. The
exact setup of each alternative will be explained in the corresponding
subsections below.

We calculate the power of the tests by the application of 1000 replications
for each setting. For the bootstrap version, we use $B=500$ bootstrap
replications. We set the test level as $\alpha=0.05$ for all tests.

###  5.2 Performances

With the consideration of all described parameter variations, we investigate
the power of 72 different scenarios. The main results and important insights
are presented in the following.

####  5.2.1 Stochastic block models

As mentioned above, we construct two different versions of SBMs. The first one
is characterized by two blocks of equal block sizes and is constructed as
follows. We assign weights to the nodes with

$\displaystyle\bm{w}=(w_{1},...,w_{n})=\bigg{(}\underbrace{-\frac{1}{2},...,-\frac{1}{2}}_{\nicefrac{{n}}{{2}}\text{
times}},\underbrace{\frac{1}{2},...,\frac{1}{2}}_{\nicefrac{{n}}{{2}}\text{
times}}\bigg{)}.$

By premultiplying the weights with a factor $\lambda>0$, we can achieve
different degrees of heterogeneity. Concretely, the weights are transformed
into connection probabilities $p_{ij}$ using a logit link. We set

$\displaystyle
p_{ij}(a,\lambda)=\begin{cases}\frac{\exp(a+\lambda^{2}w_{i}w_{j})}{1+\exp(a+\lambda^{2}w_{i}w_{j})},&\text{for
}i\neq j\\\ 0&\text{ else. }\end{cases}$ (39)

The constant $a$ is set to preserve the mean connectivity $p_{\text{mean}}$
through the different heterogeneity levels. This is achieved by (numerically)
minimizing the function

$\displaystyle f(a)=\left|p_{\text{mean}}-\binom{n}{2}^{-1}\sum_{1\leq i<j\leq
n}p_{ij}(a,\sigma^{2})\right|.$

In the end, the resulting probabilities have two values, one if $w_{i}=w_{j}$,
and another one if $w_{i}\neq w_{j}$. Thus, the resulting models are two-
community stochastic block models with two equally sized communities. We set
$p_{\text{mean}}=0.3$ and use $\lambda\in\\{0,0.5,1,1.5,...,4\\}$. Thus,
$\lambda=0$ represents the null model. Here, all edge probabilities are
$p_{ij}=p_{\text{mean}}$, $i<j=1,...,n$. Increasing values of $\lambda$ yield
models with rising heterogeneity: The intra-community connection probabilities
increase, whereas the probabilities for inter-community edges decrease.

Performance results for $p_{\text{mean}}=\frac{1}{\sqrt{n}}$ are illustrated
in Figure 3.

Figure 3: Power of the tests $V_{n}$, $S_{n}(C_{3})$ and $S_{n}(P_{3})$ for
the alternative of an SBM with two blocks and
$p_{\text{mean}}=\frac{1}{\sqrt{n}}$ for various values for $n$ and $\lambda$.

Note that these results stand representative for all other values of
$p_{\text{mean}}$, since the power of the tests is not directly influenced by
the density of the underlying network as explained in Section 4.3. Overall,
the results are in accordance with our analysis of this mentioned section. It
is clearly visible that the tests based on $C_{3}$ have a superior performance
in the underlying SBM cases as it is able to react way more sensitive than
both other tests that are mainly based on $P_{3}$. Whereas $C_{3}$ is able to
detect differences even for low values of the heterogeneity parameter
$\lambda$, the two other tests require a rather large deviation from the null
model. In this context, the performances get more reliable for all tests with
an increasing amount of nodes. For the case of $n=16$, $P_{3}$ and $V_{n}$ are
even not at all sensitive for all investigated values of $\lambda$. On a
further note, the similar results of these two tests in all situations
underline our derivations that $P_{3}$ is the decisive component of the
centered subgraph count representation of $V_{n}$.

For our second SBM setup, we construct an SBM with more flexible assumptions
to its parameters. Compared to before, it consists of three blocks with random
block sizes and varying intra-block probabilities. Formally, we set this up by
assigning the weight vector $\bm{w^{\prime}}$ to the nodes with

$\displaystyle\bm{w^{\prime}}=(w^{\prime}_{1},...,w^{\prime}_{n})=\bigg{(}\underbrace{-\frac{1}{2},...,-\frac{1}{2}}_{b_{1}\text{
times}},\underbrace{0,...,0}_{b_{2}\text{
times}},\underbrace{\frac{1}{4},...,\frac{1}{4}}_{b_{3}\text{
times}}\bigg{)}.$

In this context, $b_{k}$ with $k=\\{1,2,3\\}$ denotes the block size of the
corresponding block. Each $b_{k}$ is randomly chosen with the constraint that
$b_{1}+b_{2}+b_{3}=n$ and $b_{k}\geq 2$ for each $k$. The probabilities
$p_{ij}$ are then determined analogously to the two-block SBM case explained
above.

The resulting performances are depicted in Figure 4 for
$p_{\text{mean}}=\frac{\log{n}}{n}$.

Figure 4: Power of the tests $V_{n}$, $S_{n}(C_{3})$ and $S_{n}(P_{3})$ for
the alternative of an SBM with three blocks and
$p_{\text{mean}}=\frac{\log{n}}{n}$. The asymptotic versions of the tests are
represented by solid lines and the bootstrap version by dashed lines.

Regarding the performance under the null, all tests stick to the desired level
$\alpha=0.05$. Apart from this, the results are, interestingly, quite
different to before as both tests based on $P_{3}$ perform superior compared
to the test $C_{3}$. Apparently, the two-star structure is more sensitive to
an increased number of blocks, varying block sizes and varying intra-block
probabilities. The bootstrap versions of the tests confirm this behaviour by
achieving very similar results to their asymptotic counterparts. The improved
performance of $P_{3}$ and $V_{n}$ seems quite plausible. As shown in Section
4.3, subgraph counts of $P_{3}$ are, in theory, sensitive to detecting SBMs
with the assumptions of Theorem 4.6. Although they are sensitive to a lesser
extent compared to $C_{3}$ for the two block case, they might profit from
dividing the graph into more blocks as this can be interpreted as a further
increase of heterogeneity compared to the ER-model. Furthermore, the varying
block sizes and intra-block probabilities might influence this behaviour as
well. Interestingly, the test based on $C_{3}$ performs superior again for
denser setups which can be seen in Figure 6 in Appendix B. In these denser
networks, an increased $\lambda$ enables the possibility of larger deviations
between the intra-group probabilities and inter-group probabilities which
could support the sensitivity of $C_{3}$.

####  5.2.2 Covariate models

As a further heterogenous alternative, we study covariate models for which the
connection probabilities are generated in a way such that vertices with
similar properties are more likely to connect than others. This charateristic
seems to be a realistic setting for modeling real world networks. Especially
in social networks, we expect variables such as the age or the social status
to affect whether people know each other or not.

Figure 5: Power of the tests $V_{n}$, $S_{n}(C_{3})$ and $S_{n}(P_{3})$ for
the alternative of a covariate model setup with
$p_{\text{mean}}=\frac{1}{\sqrt{n}}$. The asymptotic versions of the tests are
represented by solid lines and the bootstrap version by dashed lines.

To achieve a setting like this, we associate each vertex
$v_{i}\in\\{v_{1},...,v_{n}\\}$ with a bivariate covariate

$\displaystyle\begin{pmatrix}x_{i1}\\\
x_{i2}\end{pmatrix}\sim\mathcal{N}_{2}\left(\begin{pmatrix}0\\\
0\end{pmatrix},\begin{pmatrix}1&0\\\ 0&1\end{pmatrix}\right),$

drawn independently from a bivariate standard normal distribution. The
covariates are then multiplied by a sequence of variances
$\sigma^{2}\in\\{0,0.5,1,1.5,2\\}$. This yields versions of the same dataset
with different degrees of heterogeneity. The connection probabilities (for
given $\sigma^{2}$ and covariate set) are then calculated according to a
logistic model:

$\displaystyle
p_{ij}(a,\sigma^{2})=\begin{cases}\frac{\exp(a-\sigma^{2}|x_{i1}-x_{j1}|-\sigma^{2}|x_{i2}-x_{j2}|)}{1+\exp(a-\sigma^{2}|x_{i1}-x_{j1}|-\sigma^{2}|x_{i2}-x_{j2}|)},&\text{
for }i\neq j,\\\ 0,&\text{ else. }\end{cases}$

The constant $a$ is again set to preserve the mean connectivity
$p_{\text{mean}}$ and can be determined as before. In this model,
$\sigma^{2}=0$ represents the null hypothesis, each vertex has the same
covariate value and the resulting connection probabilities are all equal to
$p_{\text{mean}}$. The bigger the variance $\sigma^{2}$, the more the model
deviates from the null model due to the increasing heterogeneity of the
covariates. In general, the vertices have a higher probability to connect if
their covariates have similar values. Especially, vertices that have unusually
large or small covariate values will only be able to draw few connections. The
described procedure yields a series of connection probability matrices with
increasing heterogeneity.
Results are illustrated in Figure 5 for $p_{\text{mean}}=\frac{1}{\sqrt{n}}$.
First of all, the tests reliably stick to the desired level $\alpha=0.05$.
Regarding the performance under the alternative, the performance is overall
quite good for all tests with advantages for $V_{n}$ and $P_{3}$. For larger
network sizes, the tests have no problems with detecting the deviation from
the null model - even for the smallest investigated value of the heterogeneity
parameter $\sigma^{2}$. Another result is that the bootstrap versions are able
to outperform the asymptotic versions for small $n$ and perform equally for
larger $n$. This behaviour is also confirmed by the results of most of the
other investigated parameter setups that are not reported in the paper. As
expected, the derived parametric bootstrap procedure is a promising
alternative to the asymptotic version of the proposed class of tests –
particularly for small network sizes.

##  6 Conclusion

Network data is quite complex and its handling is challenging from a
statistical point of view. An important aspect is the complexity-reduction
achieved by using a suitable network model. For a reliable analysis, however,
the fitted model should be an adequate representation of the underlying data.
In this context, we derived a class of goodness-of-fit tests for networks that
serves as a unified approach and contains various formerly proposed tests as
special cases. To do so, we used the broad class of graph functionals as test
statistics and expand existing theory in order to derive novel asymptotic
tests for evaluating if an underlying graph is generated by a homogenous
Erdös-Renyi model or some heterogenous alternative. Moreover, we proposed a
parametric bootstrap approach that particularly performs favorable in small
network size situations compared to the asymptotic tests. We enriched our
analysis by the application of our general procedure to three types of test
statistics and derived power analysis results for the subgraphs of triangles
and two-stars for the popular use case of stochastic block models. We
underlined our findings with an extensive simulation study in which we
investigated multiple network parameter setups and also studied covariate
models as a further heterogenous alternative.

A possible topic for future research is to construct tests for which a
heterogenous model $\mathcal{G}_{HER}(n)$ represents the null model in the
spirit of [24], who exclusively considered the degree variance and without any
resampling-based inference. A possible approach could be to try to extend the
proof technique for the $\mathcal{G}_{ER}(n)$ case [14], that is based on a
continuos time martingale theorem, to the heterogenous case yielding a
heterogenous equivalent to the method of higher projections.

## Acknowledgements

This work was financially supported by the Mercator Research Center Ruhr
(MERCUR) with project number PR-2019-0019.

## References

  * Bassett and Sporns [2017] Bassett, D. S. and Sporns, O. (2017) Network neuroscience.  Nature neuroscience, 20, 353–364.
  * Bhattacharyya and Bickel [2015] Bhattacharyya, S. and Bickel, P. J. (2015) Subsampling bootstrap of count features of networks.  The Annals of Statistics, 43, 2384–2411.
  * Bickel and Sarkar [2016] Bickel, P. J. and Sarkar, P. (2016) Hypothesis testing for automated community detection in networks.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 78, 253–273.
  * Billingsley [2013] Billingsley, P. (2013) Convergence of probability measures.  John Wiley & Sons.
  * Carrington et al. [2005] Carrington, P. J., Scott, J. and Wasserman, S. (2005) Models and methods in social network analysis, vol. 28.  Cambridge university press.
  * Dan and Bhattacharya [2020] Dan, S. and Bhattacharya, B. B. (2020) Goodness-of-fit tests for inhomogeneous random graphs.  In International Conference on Machine Learning, 2335–2344. PMLR.
  * Flossdorf et al. [2023] Flossdorf, J., Fried, R. and Jentsch, C. (2023) Online monitoring of dynamic networks using flexible multivariate control charts.  Social Network Analysis and Mining, 13.
  * Flossdorf and Jentsch [2021] Flossdorf, J. and Jentsch, C. (2021) Change detection in dynamic networks using network characteristics.  IEEE Transactions on Signal and Information Processing over Networks, 7, 451–464.
  * Gao and Lafferty [2017] Gao, C. and Lafferty, J. (2017) Testing network structure using relations between small subgraph probabilities.  arXiv preprint arXiv:1704.06742.
  * Gilbert [1959] Gilbert, E. N. (1959) Random graphs.  The Annals of Mathematical Statistics, 30, 1141–1144.
  * Hoeffding [1992] Hoeffding, W. (1992) A class of statistics with asymptotically normal distribution.  In Breakthroughs in statistics, 308–334. Springer.
  * Holland et al. [1983] Holland, P. W., Laskey, K. B. and Leinhardt, S. (1983) Stochastic blockmodels: First steps.  Social networks, 5, 109–137.
  * Hu et al. [2021] Hu, J., Zhang, J., Qin, H., Yan, T. and Zhu, J. (2021) Using maximum entry-wise deviation to test the goodness of fit for stochastic block models.  Journal of the American Statistical Association, 116, 1373–1382.
  * Janson et al. [2011] Janson, S., Rucinski, A. and Luczak, T. (2011) Random graphs.  John Wiley & Sons.
  * Lee [2019] Lee, A. J. (2019) U-statistics: Theory and Practice.  Routledge.
  * Lee and Dong [2009] Lee, D.-H. and Dong, M. (2009) Dynamic network design for reverse logistics operations under uncertainty.  Transportation research part E: logistics and transportation review, 45, 61–71.
  * Lei [2016] Lei, J. (2016) A goodness-of-fit test for stochastic block models.  The Annals of Statistics, 44, 401–424.
  * Lospinoso and Snijders [2019] Lospinoso, J. and Snijders, T. A. (2019) Goodness of fit for stochastic actor-oriented models.  Methodological Innovations, 12, 2059799119884282.
  * Maugis et al. [2017] Maugis, P., Priebe, C. E., Olhede, S. C. and Wolfe, P. J. (2017) Statistical inference for network samples using subgraph counts.  arXiv preprint arXiv:1701.00505.
  * Maugis et al. [2020] Maugis, P.-A., Olhede, S., Priebe, C. and Wolfe, P. (2020) Testing for equivalence of network distribution using subgraph counts.  Journal of Computational and Graphical Statistics, 29, 455–465.
  * Nowicki [1989] Nowicki, K. (1989) Asymptotic normality of graph statistics.  Journal of statistical planning and inference, 21, 209–222.
  * Nowicki and Wierman [1988] Nowicki, K. and Wierman, J. C. (1988) Subgraph counts in random graphs using incomplete u-statistics methods.  Discrete Mathematics, 72, 299–310.
  * Ospina-Forero et al. [2019] Ospina-Forero, L., Deane, C. M. and Reinert, G. (2019) Assessment of model fit via network comparison methods based on subgraph counts.  Journal of Complex Networks, 7, 226–253.
  * Ouadah et al. [2020] Ouadah, S., Robin, S. and Latouche, P. (2020) Degree-based goodness-of-fit tests for heterogeneous random graph models: Independent and exchangeable cases.  Scandinavian Journal of Statistics, 47, 156–181.
  * Prill et al. [2005] Prill, R. J., Iglesias, P. A. and Levchenko, A. (2005) Dynamic properties of network motifs contribute to biological network organization.  PLoS biology, 3, e343.
  * Robins et al. [2007] Robins, G., Pattison, P., Kalish, Y. and Lusher, D. (2007) An introduction to exponential random graph (p*) models for social networks.  Social networks, 29, 173–191.
  * Sarkar and Moore [2005] Sarkar, P. and Moore, A. W. (2005) Dynamic social network analysis using latent space models.  Acm Sigkdd Explorations Newsletter, 7, 31–40.
  * Snijders [1981] Snijders, T. A. (1981) The degree variance: an index of graph heterogeneity.  Social networks, 3, 163–174.
  * Snijders [1996] — (1996) Stochastic actor-oriented models for network change.  Journal of mathematical sociology, 21, 149–172.
  * Van der Vaart [2000] Van der Vaart, A. W. (2000) Asymptotic statistics, vol. 3.  Cambridge university press.
  * Xu and Reinert [2021] Xu, W. and Reinert, G. (2021) A stein goodness-of-test for exponential random graph models.  In International Conference on Artificial Intelligence and Statistics, 415–423. PMLR.

## Appendix A: Proofs

### Proof of Theorem 3.1

By assumption, $G\in\mathcal{G}_{HER}$, that is, $G$ is generated by a
heterogeneous ER-graph $\mathcal{G}(n,\bm{P})$ with some $\bm{P}=(p_{ij})$,
$p_{ij}=p_{ji}$, $p_{ij}\in[0,1]$ for all $i,j$ such that its mean
connectivity $p_{\text{mean}}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}p_{n,ij}$
satisfies
$p_{\text{mean}}=p_{\text{mean}}(n)\xrightarrow[n\to\infty]{}p_{0}\in[0,1]$.
Then, conditional on $\bm{A}=(A_{ij})_{1\leq i,j\leq n}$, $G^{*}$ is generated
by a homogeneous ER-graph $\mathcal{G}(n,\widehat{p})$, where
$\widehat{p}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}A_{ij}$. Furthermore, we
have that, under the null, $X_{n}=\sum_{H\in\mathcal{H}}a_{n}(H)S_{n}(H)$,
which is dominated by some family of connected graphs $\mathcal{H}_{0}$ such
that for all $H\in\mathcal{H}_{0}$, it holds
$np_{\text{mean}}^{r(H)}\xrightarrow[n\to\infty]{}\infty$. Hence, under both
the null and the alternative, we immediately get
$X_{n}^{*}=\sum_{H\in\mathcal{H}_{0}}a_{n}^{*}(H)S_{n}^{*}(H)$, which is
dominated by the same family of connected graphs $\mathcal{H}_{0}$, and where
$a_{n}^{*}(H)=a_{n}(H;\widehat{p})$ for $a_{n}(H)=a_{n}(H;p)$.

Hence, in view of Theorem 2.9, we have to check, whether for all
$H\in\mathcal{H}_{0}$, we have that
$n\widehat{p}^{r(H)}\xrightarrow[n\to\infty]{}\infty$, the coefficients

$\displaystyle\widehat{b}(H)=\sup_{n}\frac{n^{n(H)/2}\widehat{p}^{m(H)/2}a_{n}^{*}(H)}{\sqrt{\mathbb{V}\text{ar}^{*}(X_{n}^{*})}}$
(40)

are finite and satisfy

$\displaystyle\sum_{H\in\mathcal{H}_{0}}\widehat{b}^{2}(H)|\text{aut}(H)|<\infty.$
(41)

in probability, respectively. For this purpose, let us consider
$\widehat{p}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq n}A_{ij}$ in more detail. To
be more precise, as $p_{ij}$, and consequently also the distribution of
$A_{ij}$, are allowed to depend on $n$, we will write $A_{n,ij}$ and
$p_{n,ij}$ in the following. For the expectation, we get

$\displaystyle\mathbb{E}(\widehat{p})=\mathbb{E}\left(\binom{n}{2}^{-1}\sum\limits_{1\leq
i<j\leq n}A_{n,ij}\right)=\binom{n}{2}^{-1}\sum\limits_{1\leq i<j\leq
n}\mathbb{E}(A_{n,ij})=\binom{n}{2}^{-1}\sum\limits_{1\leq i<j\leq
n}p_{n,ij}=p_{\text{mean}}.$ (42)

For the variance, as the edges are formed independently according to Bernoulli
distributions with connection probabilities $p_{n,ij}$, we have

$\displaystyle\mathbb{V}\text{ar}(\widehat{p})=\binom{n}{2}^{-2}\sum\limits_{1\leq
i<j\leq n}\mathbb{V}\text{ar}(A_{n,ij})=\binom{n}{2}^{-2}\sum\limits_{1\leq
i<j\leq n}p_{n,ij}(1-p_{n,ij}).$ (43)

Hence, to prove that $n\widehat{p}^{r(H)}\xrightarrow[n\to\infty]{}\infty$
holds in probability, using $1\leq r(h)<\infty$, we get

$\displaystyle
n\widehat{p}^{r(H)}=n\left(\widehat{p}-p_{mean}+p_{mean}\right)^{r(H)}=np_{mean}^{r(H)}+n\sum_{j=1}^{r(H)}\binom{r(H)}{j}(\widehat{p}-p_{mean})^{j}p_{mean}^{r(H)-j}$

As $np^{r(H)}\xrightarrow[n\to\infty]{}\infty$ by assumption, it remains to
argue that all other terms on the last right-hand side are bounded in
probability. This follows easily from (43) leading to

$\displaystyle\widehat{p}-p_{mean}=O_{P}\left(\sqrt{\binom{n}{2}^{-2}\sum\limits_{1\leq
i<j\leq n}p_{n,ij}(1-p_{n,ij})}\right)\leq
O_{P}\left(\frac{\min\\{p_{mean},1-p_{mean}\\}}{n}\right)\leq
O_{P}\left(\frac{1}{n}\right)$ (44)

due to $\binom{n}{2}=n^{2}$ and $1-p_{n,ij}\leq 1$ and $p_{n,ij}\leq 1$. As
$p_{mean}\in[0,1]$, we have also $p_{mean}^{r(H)-j}\in[0,1]$ for all
$j=1,\ldots,r(H)$ such that

$\displaystyle
n\sum_{j=1}^{r(H)}\binom{r(H)}{j}(\widehat{p}-p_{mean})^{j}p_{mean}^{r(H)-j}=O_{P}(1).$

To show that (40) is bounded in probability, note that
$X_{n}^{*}=\sum_{H\in\mathcal{H}_{0}}a_{n}^{*}(H)S_{n}^{*}(H)$ with
$a_{n}^{*}(H)=a_{n}(H;\widehat{p})$ and

$\displaystyle\mathbb{V}\text{ar}^{*}(X_{n}^{*})=\sum_{H\in\mathcal{H}_{0}}a_{n}^{*2}(H)\mathbb{V}\text{ar}(S_{n}^{*}(H)),$

where, according to Proposition 2.7,

$\displaystyle\mathbb{V}\text{ar}^{*}(S_{n}^{*}(H))=|\text{aut}(H)|(n)_{n(H)}(\widehat{p}(1-\widehat{p}))^{m(H)}.$

By plugging-in, we get

$\displaystyle\widehat{b}(H)=\sup_{n}\frac{n^{n(H)/2}\widehat{p}^{m(H)/2}a_{n}(H)}{\sqrt{\mathbb{V}\text{ar}^{*}(X_{n}^{*})}}=\sup_{n}\frac{n^{n(H)/2}\widehat{p}^{m(H)/2}a_{n}(H)}{\sqrt{|\text{aut}(H)|(n)_{n(H)}(\widehat{p}(1-\widehat{p}))^{m(H)}}}$

which remains bounded in probability by similar arguments as above due to (8)
and making use of (44). Finally, using the same arguments, (41) follows from
(9). $\square$

### Proof of Corollary 4.1

(i) Making use of (42) and (43) under the null of a homogeneous ER graph, from
(44), we get the rate

$\displaystyle\widehat{p}-p=O_{P}\left(\frac{p}{n}\right).$ (45)

Consequently, we also have

$\displaystyle\hat{p}(1-\hat{p})-p(1-p)=$
$\displaystyle\hat{p}(1-\hat{p})-\hat{p}(1-p)+\hat{p}(1-p)-p(1-p)=\hat{p}(p-\hat{p})+(\hat{p}-p)(1-p)$
$\displaystyle=$
$\displaystyle(\hat{p}-p+p)(p-\hat{p})+(\hat{p}-p)(1-p)=p(p-\hat{p})-(\hat{p}-p)^{2}+(\hat{p}-p)(1-p)$
$\displaystyle=$
$\displaystyle\mathcal{O}_{\mathbb{P}}\left(\frac{p^{2}}{n}\right)+\mathcal{O}_{\mathbb{P}}\left(\frac{p^{2}}{n^{2}}\right)+\mathcal{O}_{\mathbb{P}}\left(\frac{p}{n}\right)=\mathcal{O}_{\mathbb{P}}\left(\frac{p}{n}\right)$

We then consider the following expansion:

$\displaystyle\frac{V_{n}-\mathbb{E}_{\hat{p}}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{\hat{p}}(V_{n})}}$
$\displaystyle=\frac{\sqrt{\mathbb{V}\text{ar}_{p}(V_{n})}}{\sqrt{\mathbb{V}\text{ar}_{\hat{p}}(V_{n})}}\left(\frac{V_{n}-\mathbb{E}_{p}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{p}(V_{n})}}-\frac{\mathbb{E}_{\hat{p}}(V_{n})-\mathbb{E}_{p}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{p}(V_{n})}}\right).$

The difference of the expectations in the numerator of the second term in
brackets is bounded in probability due to

$\displaystyle\mathbb{E}_{\hat{p}}(V_{n})-\mathbb{E}_{p}(V_{n})\,=\,$
$\displaystyle\frac{(n-1)(n-2)}{n}\Big{(}\hat{p}(1-\hat{p})-p(1-p)\Big{)}=\mathcal{O}(n)\cdot\mathcal{O}_{\mathbb{P}}\left(\frac{p}{n}\right)=\mathcal{O}_{\mathbb{P}}(p).$

As the variance $\mathbb{V}\text{ar}_{p}(V_{n})$ has order $np^{2}$, and
$np\rightarrow\infty$ by assumption, we obtain

$\displaystyle\frac{\mathbb{E}_{\hat{p}}(V_{n})-\mathbb{E}_{p}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{p}(V_{n})}}\xrightarrow{~{}P~{}}0,~{}\text{
as well as
}~{}\frac{\sqrt{\mathbb{V}\text{ar}_{p}(V_{n})}}{\sqrt{\mathbb{V}\text{ar}_{\hat{p}}(V_{n})}}\xrightarrow{~{}P~{}}1,$

by similar arguments using $\widehat{p}-p=O_{P}(\frac{p}{n})$. Combining these
two convergence results and applying Slutzky’s lemma, we get that
$\frac{V_{n}-\mathbb{E}_{\hat{p}}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{\hat{p}}(V_{n})}}$
has the same asymptotic distribution as
$\frac{V_{n}-\mathbb{E}_{p}(V_{n})}{\sqrt{\mathbb{V}\text{ar}_{p}(V_{n})}}$
stated in (22). (ii) By the same arguments as above and used to obtain (11),
(12), (14), (15), (18), (19) and (21), all conditions of Theorem 3.1 can be
shown. Exemplarily, we have

$\displaystyle\widehat{b}(H_{2})=\sqrt{\frac{2}{(1-\hat{p})^{2}}},$

which is finite in probability, because $\hat{p}\rightarrow p_{0}\in[0,1)$ by
assumption such that $(1-\hat{p})^{2}$ is bounded away from zero with
probability tending to one. In particular, we have for all $p=p_{n}\rightarrow
p_{0}\in[0,1)$. $\square$

### Proof of Theorem 4.2

For readability purposes let $|\text{aut}_{n}(H)|:=|\text{aut}(H)|(n)_{n(H)}$
From Proposition 2.8 and due to the representation

$\displaystyle\frac{\hat{S}_{n}(H)}{\sqrt{|\text{aut}_{n}(H)|(\hat{p}(1-\hat{p}))^{m(H)}}}=\sqrt{\frac{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}{|\text{aut}_{n}(H)|(\hat{p}(1-\hat{p}))^{m(H)}}}\left(\frac{S_{n}(H)}{\sqrt{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}}+\frac{\hat{S}_{n}(H)-S_{n}(H)}{\sqrt{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}}\right),$

to prove the claimed result, it remains to show

$\displaystyle\textnormal{(I)}\quad\frac{\hat{S}_{n}(H)-S_{n}(H)}{\sqrt{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}}\xrightarrow{~{}P~{}}0,\quad\text{and}\quad\textnormal{(II)}\quad\frac{({p}(1-{p}))^{m(H)}}{(\hat{p}(1-\hat{p}))^{m(H)}}\xrightarrow{~{}P~{}}1.$

For condition (I), note that $\hat{S}_{n}(H)$ is obtained from $S_{n}(H)$ by
replacing $\mathbb{P}(e\in E(G))$ in (3) by $\widehat{p}$, which is a
consistent estimator of $p=\mathbb{P}(e\in E(G))$ under the null of an ER
graph. Hence, for deriving the asymptotic properties of
$\hat{S}_{n}(H)-S_{n}(H)$ under the null, it is natural to re-write
$\hat{S}_{n}(H)$ in terms of centered subgraph counts. We have

$\displaystyle\widehat{S}_{n}(H)=$
$\displaystyle\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\prod_{e\in
E(\widetilde{H})}(\mathbbm{1}\\{e\in
E(G)\\}-\widehat{p})=\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\prod_{e\in
E(\widetilde{H})}(\mathbbm{1}\\{e\in E(G)\\}-p+p-\widehat{p})$
$\displaystyle=$
$\displaystyle\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\prod_{e\in
E(\widetilde{H})}\left\\{(\mathbbm{1}\\{e\in
E(G)\\}-p)+(p-\widehat{p})\right\\}$ $\displaystyle=$
$\displaystyle\sum_{\widetilde{H}\in\text{iso}_{n}(H)}\sum_{\widetilde{J}\subseteq\widetilde{H}:E(\widetilde{J})\in\mathcal{P}(E(\widetilde{H}))}\left\\{\left(\prod_{e\in
E(J)}(\mathbbm{1}\\{e\in
E(G)\\}-p)\right)(p-\widehat{p})^{m(\widetilde{H})-m(\widetilde{J})}\right\\}$
$\displaystyle=$ $\displaystyle\sum_{J\subseteq
H:E(J)\in\mathcal{P}(E(H))}\left(\sum_{\widetilde{J}\in\text{iso}_{n}(J)}\prod_{e\in
E(\widetilde{J})}(\mathbbm{1}\\{e\in
E(G)\\}-p)\right)(p-\widehat{p})^{m(H)-m(J)}$ $\displaystyle=$
$\displaystyle\sum_{J\subseteq
H:E(J)\in\mathcal{P}(E(H))}S_{n}(J)(p-\widehat{p})^{m(H)-m(J)}$
$\displaystyle=$ $\displaystyle S_{n}(H)+\sum_{J\subsetneq
H:E(J)\in\mathcal{P}(E(H))}S_{n}(J)(p-\widehat{p})^{m(H)-m(J)}$

where $\mathcal{P}(E(\widetilde{H}))$ denotes the power set of
$E(\widetilde{H})$, that is, the set of all subsets of $E(\widetilde{H})$.
Hence, altogether, we get

$\displaystyle\frac{\hat{S}_{n}(H)-S_{n}(H)}{\sqrt{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}}=\frac{\sum_{J\subsetneq
H:E(J)\in\mathcal{P}(E(H))}S_{n}(J)(p-\widehat{p})^{m(H)-m(J)}}{\sqrt{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}}.$
(46)

Then, making use of (7) for all $J\subsetneq H$ and (45), the last right-hand
side becomes a term of order

$\displaystyle O_{P}\left(\frac{\sum_{J\subsetneq
H:E(J)\in\mathcal{P}(E(H))}\left(n^{n(J)/2}p^{m(J)/2}\right)\left((\frac{p}{n})^{m(H)-m(J)}\right)}{\sqrt{|\text{aut}_{n}(H)|(p(1-p))^{m(H)}}}.\right)=o_{P}(1)$
(47)

as $\sum_{J\subsetneq H:E(J)\in\mathcal{P}(E(H))}$ is a finite sum and
$m(H)>m(J)$. Condition (II) follows directly from the consistency of
$\hat{p}$. $\square$

### Proof of Lemma 4.3

First, Equation (30) is obtained due to

$\displaystyle\widehat{p}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq
n}A_{ij}=\binom{n}{2}^{-1}\sum_{1\leq i<j\leq
n}(A_{ij}-p)+p=\binom{n}{2}^{-1}S_{n}(P_{2})+p,$

where $P_{2}$ is a graph with two nodes and one edge. In order to obtain the
dominating family for $\hat{p}^{3}$, we have

$\displaystyle\widehat{p}^{3}=\left(\binom{n}{2}^{-1}S_{n}(P_{2})+p\right)^{3}=\left(\binom{n}{2}^{-1}S_{n}(P_{2})\right)^{3}+3\left(\binom{n}{2}^{-1}S_{n}(P_{2})\right)^{2}p+3\binom{n}{2}^{-1}S_{n}(P_{2})p^{2}+p^{3}$
(48)

As can be seen, $\widehat{p}^{3}$ decomposes into four summands, where the
first two terms

$\displaystyle(A):=\left(\binom{n}{2}^{-1}S_{n}(P_{2})\right)^{3}\quad\text{
and}\quad(B):=3p\left(\binom{n}{2}^{-1}S_{n}(P_{2})\right)^{2}$

are of lower order than the third term
$(C):=3\binom{n}{2}^{-1}S_{n}(P_{2})p^{2}$ due to the following. From
Proposition 2.8, we have

$\displaystyle\left(p(1-p)\right)^{-1/2}n^{-1}S_{n}(P_{2})\xrightarrow{~{}d~{}}N(0,1)$

and thus, we can directly conclude that
$\left(p(1-p)\right)^{-1/2}n^{-1}S_{n}(P_{2})=\mathcal{O}(1)$ holds such that
$S_{n}(P_{2})=\mathcal{O}(\left(p(1-p)\right)^{1/2}n)$. Thus, we have
$\binom{n}{2}^{-1}\binom{n}{2}^{-1}S_{n}(P_{2})=\mathcal{O}(\left(p(1-p)\right)^{1/2}n^{-1})$,
which yields $(A)=\mathcal{O}(\left(p(1-p)\right)^{3/2}n^{-3})$ and
$(B)=\mathcal{O}(p^{2}(1-p)n^{-2})$ as well as
$(C)=\mathcal{O}(p^{5/2}(1-p)^{1/2}n^{-1})$. Hence, $(C)$ becomes the leading
term of $\widehat{p}^{3}$ in (48). Similarly, it is possible to show that the
variances of $(A)$ and $(B)$ are of lower order than the variance of $(C)$
such that we have

$\displaystyle\frac{\mathbb{V}\text{ar}(\widehat{p}^{3}))}{\mathbb{V}\text{ar}\left(3\binom{n}{2}^{-1}p^{2}S_{n}(P_{2})\right)}\xrightarrow[n\to\infty]{}1$

and the dominating family for $\widehat{p}^{3}$ is indeed formed by
$\mathcal{H}_{0}=\\{P_{2}\\}$, which proves Lemma 4.3. $\square$

### Proof of Corollary 4.4

We are interested in the asymptotic distribution of the graph functional

$\displaystyle T_{n}(C_{3})-\binom{n}{3}\hat{p}^{3}.$ (49)

Equation (33) follows by plugging in the decomposition (48) into (24).
Calculation of its variance then directly yields (34). Thus, the dominating
family for the graph functional (49) is

$\displaystyle\mathcal{H}_{0}=\\{C_{3},P_{3}\\},\text{ with coefficients
}a_{n}(C_{3})=1\text{ and }a_{n}(P_{3})=p$

The corresponding coefficients $b(H)$ are given by

$\displaystyle
b(C_{3})=\sup_{n}\frac{n^{3/2}p^{3/2}}{\sqrt{\mathbb{V}\text{ar}(T_{n}(C_{3})-\binom{n}{3}\hat{p}^{3})}}.$

As the leading term of the variance in the denominator is
$\frac{1}{6}\left(1-\frac{3}{n}+\frac{2}{n^{2}}\right)((1-p)^{3}+3p(1-p)^{2})$,
the finiteness of the supremum above is implied by

$\displaystyle\lim_{n\to\infty}\frac{1}{\sqrt{\frac{1}{6}\left(1-\frac{3}{n}+\frac{2}{n^{2}}\right)((1-p)^{3}+3p(1-p)^{2})+\frac{const.}{n}}}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{\frac{1}{6}((1-p_{0})^{3}+3p_{0}(1-p_{0})^{2})}},$

which is finite for $p_{0}\in(0,1)$. Analogously, we get

$\displaystyle b(P_{3})=$
$\displaystyle\sup_{n}\frac{n^{3/2}p}{\sqrt{\mathbb{V}\text{ar}(T_{n}(C_{3})-\binom{n}{3}\hat{p}^{3})}}=\frac{1}{\sqrt{\frac{1}{6}(p_{0}(1-p_{0})^{3}+3p_{0}^{2}(1-p_{0})^{2})}}$

Thus,

$\displaystyle\sum_{H\in\mathcal{H}_{0}}b(H)^{2}|\text{aut}(H)|=b(C_{3})^{2}+3b(P_{3})<\infty$

and Theorem 2.9 is applicable. Corollary 4.4 directly follows from this.
$\square$

### Proof of Theorem 4.5

Following is the proof for statement (a).
It is $\mathbb{E}_{\text{ER}}(T_{n}(C_{3}))=\binom{n}{3}p^{3}$ and
$\mathbb{E}_{\text{SBM}}(T_{n}(C_{3}))=\left[2\binom{\nicefrac{{n}}{{2}}}{3}p^{3}_{\text{intra}}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)p_{\text{intra}}p_{\text{inter}}^{2}\right]\right]$.
Hence, it yields

$\displaystyle\mathbb{E}_{\text{ER}}(T_{n}(C_{3}))-\mathbb{E}_{\text{SBM}}(T_{n}(C_{3}))=\binom{n}{3}p^{3}-\left[2\binom{\nicefrac{{n}}{{2}}}{3}p^{3}_{\text{intra}}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)p_{\text{intra}}p_{\text{inter}}^{2}\right]\right]$
$\displaystyle=\binom{n}{3}p^{3}-\binom{n}{3}p_{\text{intra}}p_{\text{inter}}^{2}-2\binom{\nicefrac{{n}}{{2}}}{3}p^{3}_{\text{intra}}+2\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}p_{\text{inter}}^{2}$
$\displaystyle=\binom{n}{3}(p^{3}-p_{\text{intra}}p_{\text{inter}}^{2})+2\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{intra}}p_{\text{inter}}^{2}-p_{\text{intra}}^{3})$
$\displaystyle=\binom{n}{3}\left(\left(\frac{1}{2}\frac{n-2}{n-1}(p_{\text{intra}}+p_{\text{inter}})\right)^{3}-p_{\text{intra}}p_{\text{inter}}^{2}\right)+2\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{intra}}p_{\text{inter}}^{2}-p_{\text{intra}}^{3})$
$\displaystyle=\binom{n}{3}\frac{1}{8}\left(\frac{n-2}{n-1}\right)^{3}(p_{\text{intra}}^{3}+3p_{\text{intra}}^{2}p_{\text{inter}}+3p_{\text{intra}}p_{\text{inter}}^{2}+p_{\text{inter}}^{3})-\binom{n}{3}p_{\text{intra}}p_{\text{inter}}^{2}+2\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{intra}}p_{\text{inter}}^{2}-p_{\text{intra}}^{3})$
$\displaystyle=\binom{n}{3}\frac{1}{8}\left(\frac{n-2}{n-1}\right)^{3}(p_{\text{intra}}^{3}+3p_{\text{intra}}^{2}p_{\text{inter}}+p_{\text{inter}}^{3})+\binom{n}{3}\frac{1}{8}\frac{n-2}{n-1}3p_{\text{intra}}p_{\text{inter}}^{2}-\binom{n}{3}p_{\text{intra}}p_{\text{inter}}^{2}+2\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{intra}}p_{\text{inter}}^{2}-p_{\text{intra}}^{3})$

The last right-hand side is asymptotically equivalent to

$\displaystyle\binom{n}{3}\frac{1}{8}(p_{\text{intra}}^{3}+3p_{\text{intra}}^{2}p_{\text{inter}}+p_{\text{inter}}^{3})-\frac{5}{8}p_{\text{intra}}p_{\text{inter}}^{2}+2\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{intra}}p_{\text{inter}}^{2}-p_{\text{intra}}^{3})$
$\displaystyle=\frac{1}{8}\binom{n}{3}(p_{\text{intra}}^{3}+3p_{\text{intra}}^{2}p_{\text{inter}}+p_{\text{inter}}^{3}-5p_{\text{intra}}p_{\text{inter}}^{2})+2\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{intra}}p_{\text{inter}}^{2}-p_{\text{intra}}^{3})$
$\displaystyle=\frac{1}{8}\binom{n}{3}p_{\text{intra}}^{3}+\frac{3}{8}\binom{n}{3}p_{\text{intra}}^{2}p_{\text{inter}}+\frac{1}{8}\binom{n}{3}p_{\text{inter}}^{3}-\frac{5}{8}\binom{n}{3}p_{\text{intra}}p_{\text{inter}}^{2}+2\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}p_{\text{inter}}^{2}-2\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}^{3}$
$\displaystyle=\left(\frac{1}{8}\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)p_{\text{intra}}^{3}+\frac{3}{8}\binom{n}{3}p_{\text{intra}}^{2}p_{\text{inter}}+\frac{1}{8}\binom{n}{3}p_{\text{inter}}^{3}+\left(2\binom{\nicefrac{{n}}{{2}}}{3}-\frac{5}{8}\binom{n}{3}\right)p_{\text{intra}}p_{\text{inter}}^{2},$

which, using (50), is asymptotically equivalent to

$\displaystyle\xrightarrow{}\left(\binom{\nicefrac{{n}}{{2}}}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)p_{\text{intra}}^{3}+\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}^{2}p_{\text{inter}}+\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{inter}}^{3}+\left(2\binom{\nicefrac{{n}}{{2}}}{3}-5\binom{\nicefrac{{n}}{{2}}}{3}\right)p_{\text{intra}}p_{\text{inter}}^{2}$
$\displaystyle=-\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}^{3}+\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{inter}}^{3}+3\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}^{2}p_{\text{inter}}-3\binom{\nicefrac{{n}}{{2}}}{3}p_{\text{intra}}p_{\text{inter}}^{2}$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{3}(p_{\text{inter}}-p_{\text{intra}})^{3}<0$

with $p_{\text{intra}}\geq p_{\text{inter}}$ and

$\displaystyle\frac{\binom{n}{3}}{\binom{\nicefrac{{n}}{{2}}}{3}}$
$\displaystyle=\frac{n!}{\nicefrac{{n}}{{2}}!}\frac{(\nicefrac{{n}}{{2}}-3)!}{(n-3)!}=\frac{n(n-1)(n-2)}{\nicefrac{{n}}{{2}}(\nicefrac{{n}}{{2}}-1)(\nicefrac{{n}}{{2}}-1)(\nicefrac{{n}}{{2}}-2)}=\frac{(n-1)(n-2)}{(\nicefrac{{n}}{{4}}-\nicefrac{{1}}{{2}})(\nicefrac{{n}}{{2}}-2)}$
(50)
$\displaystyle=\frac{(n-1)(n-2)}{\nicefrac{{1}}{{4}}(n-2)\nicefrac{{1}}{{2}}(n-4)}=\frac{n-1}{\nicefrac{{1}}{{8}}(n-4)}=8\frac{n-1}{n-4}\xrightarrow[n\to\infty]{}8$
(51)

Under the assumed conditions, the amount of expected triangles in a SBM is
larger than in a homogenous ER-model. The difference in expectation increases
for larger values of $p_{\text{intra}}$.

Now let us move to the proof of statement (b). The end result was already
shown in the main text and the derivations for the homogenous ER-model case as
well. Still missing are the derivations for the SBM case. In this context, we
have: For $I_{n}(C_{3})$ and $I_{n}(E_{3})$, we have analogously to the proof
of statement (a)

$\displaystyle\mathbb{E}_{\text{SBM}}(I_{n}(C_{3}))$
$\displaystyle=2\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right){\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\right]$
$\displaystyle\mathbb{E}_{\text{SBM}}(I_{n}(E_{3}))$
$\displaystyle=2\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A}^{3})+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)(1-{\rm
Phys.~{}Rev.~{}A})(1-p_{\text{inter}})^{2}\right].$

For $I_{n}(P_{3})$ and $I_{n}(D_{3})$ it becomes more difficult as the present
edges can exist between the blocks and/or in the blocks. This results in the
possibilities

$\displaystyle I_{n}(P_{3})_{\text{SBM}}$
$\displaystyle=\begin{cases}3\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A}){\rm Phys.~{}Rev.~{}A}^{2},&\text{all corresponding nodes in
the same block}\\\ (*),&\text{corresponding nodes from two different
blocks.}\end{cases}$ $\displaystyle\text{with}(*)$
$\displaystyle=\begin{cases}2\binom{\nicefrac{{n}}{{2}}}{2}\frac{n}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}}),&\text{missing link
between nodes of different blocks}\\\
\binom{\nicefrac{{n}}{{2}}}{2}\frac{n}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A}),&\text{missing link between the nodes of the same
block.}\end{cases}$ $\displaystyle I_{n}(D_{3})_{\text{SBM}}$
$\displaystyle=\begin{cases}3\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A})^{2}{\rm Phys.~{}Rev.~{}A},&\text{all corresponding nodes in
the same block}\\\ (**),&\text{corresponding nodes from two different
blocks.}\end{cases}$ $\displaystyle\text{with}(**)$
$\displaystyle=\begin{cases}2\binom{\nicefrac{{n}}{{2}}}{2}\frac{n}{2}(1-{\rm
Phys.~{}Rev.~{}A})p_{\text{inter}}(1-p_{\text{inter}}),&\text{existing link
between nodes of different blocks}\\\
\binom{\nicefrac{{n}}{{2}}}{2}\frac{n}{2}{\rm
Phys.~{}Rev.~{}A}(1-p_{\text{inter}})^{2},&\text{existing link between nodes
of the same block,}\end{cases}$

yielding

$\displaystyle\mathbb{E}_{\text{SBM}}(I_{n}(P_{3}))$
$\displaystyle=6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})+2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A}).$ $\displaystyle\mathbb{E}_{\text{SBM}}(I_{n}(D_{3}))$
$\displaystyle=6\binom{\nicefrac{{n}}{{2}}}{3}{\rm Phys.~{}Rev.~{}A}(1-{\rm
Phys.~{}Rev.~{}A})^{2}+2n\binom{\nicefrac{{n}}{{2}}}{2}(1-{\rm
Phys.~{}Rev.~{}A})p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}(1-p_{\text{inter}})^{2}.$

Hence, we have

$\displaystyle\mathbb{E}_{\text{SBM}}(S_{n}(C_{3}))$
$\displaystyle=(1-p_{\text{mean}})^{3}\left[2\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right){\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\right]\right]$
$\displaystyle+(1-p_{\text{mean}})^{2}(-p_{\text{mean}})\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})+2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})\right]$
$\displaystyle+(1-p_{\text{mean}})p_{\text{mean}}^{2}\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}(1-{\rm
Phys.~{}Rev.~{}A})^{2}+2n\binom{\nicefrac{{n}}{{2}}}{2}(1-{\rm
Phys.~{}Rev.~{}A})p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}(1-p_{\text{inter}})^{2}\right]$
$\displaystyle+(-p_{\text{mean}})^{3}\left[2\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A}^{3})+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)(1-{\rm
Phys.~{}Rev.~{}A})(1-p_{\text{inter}})^{2}\right]\right].$

$\square$

### Proof of Theorem 4.6

Let us start with the proof of statement (b). The procedure is similar to the
proof of statement (b) of Theorem 4.5 that is presented in the main text. We
can again use the decomposition of $E(S_{n}(H))$ into the linear combination
of the expected values of induced subgraphs for all possible subgraph shapes
consisting of the same node amount as $H$. Compared to before, only the
coefficients change resulting in

$\displaystyle\mathbb{E}(S_{n}(P_{3}))=$
$\displaystyle\mathbb{E}(I_{n}(C_{3})3(1-p)^{2})+\mathbb{E}(I_{n}(P_{3})[(1-p)^{2}+2(1-p)(-p)])+\mathbb{E}(I_{n}(D_{3})[(-p)^{2}+2(1-p)(-p)])$
$\displaystyle+\mathbb{E}(I_{n}(E_{3})3(-p)^{2})$ $\displaystyle=$
$\displaystyle
3(1-p)^{2}\mathbb{E}(I_{n}(C_{3}))+[(1-p)^{2}+2(1-p)(-p)]\mathbb{E}(I_{n}(P_{3}))$
$\displaystyle+[(-p)^{2}+2(1-p)(-p)]\mathbb{E}(I_{n}(D_{3}))+3(-p)^{2}\mathbb{E}(I_{n}(E_{3})).$

It is again $\mathbb{E}_{\text{ER}}(S_{n}(P_{3})=0$, since we considered
centered (!) subgraph counts. Plugging in the derivations from the proof of
Theorem 4.5 in the formula above, it yields for the SBM case

$\displaystyle\mathbb{E}_{\text{SBM}}(S_{n}(P_{3}))=3(1-p_{\text{mean}})^{2}\left[2\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right){\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\right]\right]$
$\displaystyle+\left[(1-p_{\text{mean}})^{2}+2(-p_{\text{mean}})(1-p_{\text{mean}})\right]\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})+2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})\right]$
$\displaystyle+\left[(-p_{\text{mean}})^{2}+2(-p_{\text{mean}})(1-p_{\text{mean}})\right]\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}(1-{\rm
Phys.~{}Rev.~{}A})^{2}+2n\binom{\nicefrac{{n}}{{2}}}{2}(1-{\rm
Phys.~{}Rev.~{}A})p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}(1-p_{\text{inter}})^{2}\right]$
$\displaystyle+3(-p_{\text{mean}})^{2}\left[2\binom{\nicefrac{{n}}{{2}}}{3}(1-{\rm
Phys.~{}Rev.~{}A}^{3})+\left[\left(\binom{n}{3}-2\binom{\nicefrac{{n}}{{2}}}{3}\right)(1-{\rm
Phys.~{}Rev.~{}A})(1-p_{\text{inter}})^{2}\right]\right].$

Now, let us move on to the proof of statement (a). As for the proof of Theorem
4.5, we investigate the difference of the expected values of $T_{n}(P_{3})$
for the ER-model and the SBM model with the mentioned assumptions. It is

$\displaystyle\mathbb{E}_{\text{ER}}(T_{n}(P_{3}))-\mathbb{E}_{\text{SBM}}(T_{n}(P_{3}))$
$\displaystyle=3\binom{n}{3}(1-p)p^{2}-\left[6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})+2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})+n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})\right]$
$\displaystyle=3\binom{n}{3}(1-p)p^{2}-6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})-2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})-n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A}).$

Let us first have a look at the first term that comes from the ER-model. We
reformulate $p$ in dependence of ${\rm Phys.~{}Rev.~{}A}$ and
$p_{\text{inter}}$ with $p={\rm Phys.~{}Rev.~{}A}=p_{\text{inter}}$ which
results in $p=\frac{1}{2}({\rm Phys.~{}Rev.~{}A}+p_{\text{inter}})$. Note that
this connection is also asymptotically (!) valid for the SBM case. It
therefore is

$\displaystyle\mathbb{E}_{\text{ER}}(T_{n}(P_{3}))-\mathbb{E}_{\text{SBM}}(T_{n}(P_{3}))=$
$\displaystyle=3\binom{n}{3}\left[\left(1-\frac{1}{2}{\rm
Phys.~{}Rev.~{}A}-\frac{1}{2}p_{\text{inter}}\right)\frac{1}{4}({\rm
Phys.~{}Rev.~{}A}^{2}+2{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}+p_{\text{inter}}^{2})\right]$
$\displaystyle-6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})-2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})-n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})$ $\displaystyle=\frac{3}{4}\binom{n}{3}\left[{\rm
Phys.~{}Rev.~{}A}^{2}+2{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}+p_{\text{inter}}^{2}-\frac{1}{2}{\rm
Phys.~{}Rev.~{}A}^{3}-{\rm
Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}-\frac{1}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}-\frac{1}{2}{\rm
Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}-{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}-\frac{1}{2}p_{\text{inter}}^{3}\right]$
$\displaystyle-6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})-2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})-n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})$

The last right-hand side can be written as

$\displaystyle=6\binom{\nicefrac{{n}}{{2}}}{3}\frac{n-1}{n-4}\left[{\rm
Phys.~{}Rev.~{}A}^{2}+2{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}+p_{\text{inter}}^{2}-\frac{1}{2}{\rm
Phys.~{}Rev.~{}A}^{3}-\frac{1}{2}p_{\text{inter}}^{3}-\frac{3}{2}{\rm
Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}-\frac{3}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\right]$
$\displaystyle-6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}(1-{\rm
Phys.~{}Rev.~{}A})-2n\binom{\nicefrac{{n}}{{2}}}{2}{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}(1-p_{\text{inter}})-n\binom{\nicefrac{{n}}{{2}}}{2}p_{\text{inter}}^{2}(1-{\rm
Phys.~{}Rev.~{}A})$
$\displaystyle=6\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}\left(-\frac{1}{2}p_{\text{inter}}^{3}-\frac{3}{2}{\rm
Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}\right)+6\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}-6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}+6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}$
$\displaystyle-3\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}\left(12\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}-2n\binom{\nicefrac{{n}}{{2}}}{2}\right)$
$\displaystyle+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\left(-9\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}+3n\binom{\nicefrac{{n}}{{2}}}{2}\right)+p_{\text{inter}}^{2}\left(6\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}-n\binom{\nicefrac{{n}}{{2}}}{2}\right)$
$\displaystyle=6\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}\left(-\frac{1}{2}p_{\text{inter}}^{3}-\frac{3}{2}{\rm
Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}\right)+6\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}-6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{2}+6\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}$
$\displaystyle-3\frac{n-1}{n-4}\binom{\nicefrac{{n}}{{2}}}{3}{\rm
Phys.~{}Rev.~{}A}^{3}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}\left(12\frac{n-1}{n-4}\frac{\nicefrac{{n}}{{2}}-2}{3}\binom{\nicefrac{{n}}{{2}}}{2}-2n\binom{\nicefrac{{n}}{{2}}}{2}\right)$
$\displaystyle+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\left(-9\frac{n-1}{n-4}\frac{\nicefrac{{n}}{{2}}-2}{3}\binom{\nicefrac{{n}}{{2}}}{2}+3n\binom{\nicefrac{{n}}{{2}}}{2}\right)+p_{\text{inter}}^{2}\left(6\frac{n-1}{n-4}\frac{\nicefrac{{n}}{{2}}-2}{3}\binom{\nicefrac{{n}}{{2}}}{2}-n\binom{\nicefrac{{n}}{{2}}}{2}\right)$

This results in

$\displaystyle{\rm Phys.~{}Rev.~{}A}^{2}\cdot
6\binom{\nicefrac{{n}}{{2}}}{2}\frac{\nicefrac{{n}}{{2}}-2}{3}\left(\frac{n-1}{n-4}-1\right)+{\rm
Phys.~{}Rev.~{}A}^{3}\cdot
6\binom{\nicefrac{{n}}{{2}}}{2}\frac{\nicefrac{{n}}{{2}}-2}{3}\left(1-\frac{1}{2}\frac{n-1}{n-4}\right)$
$\displaystyle-{\rm Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}\cdot
9\binom{\nicefrac{{n}}{{2}}}{2}\frac{\nicefrac{{n}}{{2}}-2}{3}\frac{n-1}{n-4}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}\cdot\left(\frac{n-1}{n-4}(2n-8)\binom{\nicefrac{{n}}{{2}}}{2}-2n\binom{\nicefrac{{n}}{{2}}}{2}\right)$
$\displaystyle-p_{\text{inter}}^{3}\cdot
3\frac{\nicefrac{{n}}{{2}}-2}{3}\binom{\nicefrac{{n}}{{2}}}{2}\frac{n-1}{n-4}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\left(-\frac{n-1}{n-4}\left(\frac{3n}{2}-6\right)\binom{\nicefrac{{n}}{{2}}}{2}+3n\binom{\nicefrac{{n}}{{2}}}{2}\right)+p_{\text{inter}}^{2}\left(\frac{n-1}{n-4}(n-4)\binom{\nicefrac{{n}}{{2}}}{2}-n\binom{\nicefrac{{n}}{{2}}}{2}\right)$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[{\rm
Phys.~{}Rev.~{}A}^{2}\cdot
6\frac{\nicefrac{{n}}{{2}}-2}{3}\left(\frac{n-1}{n-4}-1\right)\right.+{\rm
Phys.~{}Rev.~{}A}^{3}\cdot
6\frac{\nicefrac{{n}}{{2}}-2}{3}\left(1-\frac{1}{2}\frac{n-1}{n-4}\right)$
$\displaystyle-{\rm Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}\cdot
9\frac{\nicefrac{{n}}{{2}}-2}{3}\frac{n-1}{n-4}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}\cdot\left(\frac{n-1}{n-4}(2n-8)-2n\right)$
$\displaystyle-p_{\text{inter}}^{3}\cdot
3\frac{\nicefrac{{n}}{{2}}-2}{3}\frac{n-1}{n-4}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\left(-\frac{n-1}{n-4}\left(\frac{3n}{2}-6\right)+3n\right)+\left.p_{\text{inter}}^{2}\left(\frac{n-1}{n-4}(n-4)-n\right)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[{\rm
Phys.~{}Rev.~{}A}^{2}\cdot
2(\frac{n}{2}-2)\left(\frac{3}{n-4}\right)\right.+{\rm
Phys.~{}Rev.~{}A}^{3}\cdot 2(\frac{n}{2}-2)\left(\frac{n-7}{2(n-4)}\right)$
$\displaystyle-{\rm Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}\cdot
3(\frac{n}{2}-2)\frac{n-1}{n-4}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}\cdot\left(2(n-1)-2n\right)$ $\displaystyle-
p_{\text{inter}}^{3}\cdot\left(\frac{n}{2}-2\right)\frac{n-1}{n-4}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\cdot\left(-\frac{3(n-1)}{2}+3n\right)+\left.p_{\text{inter}}^{2}\cdot(-1)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[{\rm
Phys.~{}Rev.~{}A}^{2}\cdot 3+{\rm Phys.~{}Rev.~{}A}^{3}\cdot\frac{n-7}{2}+{\rm
Phys.~{}Rev.~{}A}^{2}p_{\text{inter}}\cdot\frac{3-3n}{2}+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}\cdot(-2)\right.$
$\displaystyle+\left.p_{\text{inter}}^{3}\cdot\left(\frac{1-n}{2}\right)+{\rm
Phys.~{}Rev.~{}A}p_{\text{inter}}^{2}\cdot\left(\frac{3n+3}{2}\right)+p_{\text{inter}}^{2}\cdot(-1)\right]$

For interpretation purposes, we set ${\rm Phys.~{}Rev.~{}A}=x\cdot
p_{\text{inter}}$ w.l.o.g. resulting in

$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[(x\cdot
p_{\text{inter}})^{2}\cdot 3+(x\cdot
p_{\text{inter}})^{3}\cdot\frac{n-7}{2}+(x\cdot
p_{\text{inter}})^{2}p_{\text{inter}}\cdot\frac{3-3n}{2}+(x\cdot
p_{\text{inter}})p_{\text{inter}}\cdot(-2)\right.$
$\displaystyle+\left.p_{\text{inter}}^{3}\cdot\left(\frac{1-n}{2}\right)+(x\cdot
p_{\text{inter}})p_{\text{inter}}^{2}\cdot\left(\frac{3n+3}{2}\right)+p_{\text{inter}}^{2}\cdot(-1)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[x^{2}\cdot
p_{\text{inter}}^{2}\cdot 3+x^{3}\cdot
p_{\text{inter}}^{3}\cdot\frac{n-7}{2}+x^{2}\cdot
p_{\text{inter}}^{3}\cdot\frac{3-3n}{2}+x\cdot
p_{\text{inter}}^{2}\cdot(-2)\right.$
$\displaystyle+\left.p_{\text{inter}}^{3}\cdot\left(\frac{1-n}{2}\right)+x\cdot
p_{\text{inter}}^{3}\cdot\left(\frac{3n+3}{2}\right)+p_{\text{inter}}^{2}\cdot(-1)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[p_{\text{inter}}^{3}(x^{3}\cdot\frac{n-7}{2}+x^{2}\cdot\frac{3-3n}{2}+x\cdot\frac{3n+3}{2}+\frac{1-n}{2})+p_{\text{inter}}^{2}(3x^{2}-2x-1)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[p_{\text{inter}}^{3}\left(\frac{n}{2}(x^{3}-3x^{2}+3x-1)-\frac{1}{2}(x-1)(7x^{2}+4x+1)\right)+p_{\text{inter}}^{2}(x-1)(3x+1)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}\left[\frac{1}{2}p_{\text{inter}}^{3}(n(x-1)^{3}-(x-1)(7x^{2}+4x+1))+p_{\text{inter}}^{2}(x-1)(3x+1)\right]$
$\displaystyle=\binom{\nicefrac{{n}}{{2}}}{2}(x-1)\left[\frac{1}{2}p_{\text{inter}}^{3}(n(x-1)^{2}-(7x^{2}+4x+1))+p_{\text{inter}}^{2}(3x+1)\right].$

Our general assumption in SBMs is ${\rm Phys.~{}Rev.~{}A}>p_{\text{inter}}$
which in this case is equivalent to $x>1$. Obviously, the coefficient
$\binom{\nicefrac{{n}}{{2}}}{2}(x-1)$ is larger than 0 in this case as is the
last term in the bracket, i.e. $p_{\text{inter}}^{2}(3x+1)$. Remaining is the
term $\frac{1}{2}p_{\text{inter}}^{3}(n(x-1)^{2}-(7x^{2}+4x+1))$. This term
can be negative for a few setups with small $n$. However, for most realistic
network setups and particularly for $n\to\infty$ this term is also larger than
0 because $(n-7)x^{2}$ increases larger than $(-2n-4)x$ decreases. Thus, we
have

$\displaystyle\mathbb{E}_{\text{ER}}(T_{n}(P_{3}))-\mathbb{E}_{\text{SBM}}(T_{n}(P_{3}))=\underbrace{\binom{\nicefrac{{n}}{{2}}}{2}(x-1)}_{>0}\left[\frac{1}{2}p_{\text{inter}}^{3}(\underbrace{n(x-1)^{2}-(7x^{2}+4x+1))}_{>0\text{
for }n\to\infty}+\underbrace{p_{\text{inter}}^{2}(3x+1)}_{>0}\right]$

$\square$

## Appendix B: Additional tables and figures

Figure 6: Power of the tests $V_{n}$, $S_{n}(C_{3})$ and $S_{n}(P_{3})$ for
the alternative of a SBM setup with three blocks with
$p_{\text{mean}}=\frac{\log{n}}{\sqrt{n}}$. The asymptotic versions of the
tests are represented by solid lines and the bootstrap version by dashed
lines.