# Characterization of $U$-statistics on RCE matrices

Tâm Le Minh

Characterization of the asymptotic behavior of $U$-statistics on row-column
exchangeable matrices

Tâm Le Minh 1,2

1 Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France
2 Université Paris-Saclay, AgroParisTech, INRAE, UMR MIA Paris-Saclay, 91120,
Palaiseau, France

##### Abstract.

We consider $U$-statistics on row-column exchangeable matrices. We derive a
decomposition for them, based on orthogonal projections on probability spaces
generated by sets of Aldous-Hoover-Kallenberg variables. The specificity of
these sets is that they are indexed by bipartite graphs, which allows for the
use of concepts from graph theory to describe this decomposition. The
decomposition is used to investigate the asymptotic behavior of $U$-statistics
of row-column exchangeable matrices, including in degenerate cases. In
particular, it depends only on a few terms of the decomposition, corresponding
to the non-zero elements that are indexed by the smallest graphs, named
principal support graphs, after an analogous concept suggested by Janson and
Nowicki [19]. Hence, we show that the asymptotic behavior of a $U$-statistic
and its degeneracy are characterized by the properties of their principal
support graphs. Indeed, their number of nodes gives the convergence rate of a
$U$-statistic to its limit distribution. Specifically, the latter is
degenerate if and only if this number is strictly greater than 1. Also, when
the principal support graphs are connected, we find that the limit
distribution is Gaussian, even in degenerate cases.

##### Keywords.

degenerate $U$-statistics, row-column exchangeability, Hoeffding
decomposition, central limit theorem, asymptotic distribution, network
statistics

## Introduction

$U$-statistics are the generalization of the empirical mean to functions of
subsamples. Given a sample of $n$ observations $(X_{1},...,X_{n})$, a
$U$-statistic is defined by

$U_{n}=\binom{n}{k}^{-1}\sum_{1\leq i_{1}<...<i_{k}\leq
n}h(X_{i_{1}},...,X_{i_{k}}),$

where the kernel $h:\mathbb{R}^{k}\rightarrow\mathbb{R}$ is a measurable
symmetric function. $U$-statistics are a broad class of statistics
encompassing many well-known statistics, such as the empirical variance, the
Wilcoxon one-sample statistic or Kendall’s $\tau$. When the observations
$(X_{1},...,X_{n})$ are i.i.d., the properties of $U$-statistics are already
well-known. Notably, their limit distribution has been identified by Central
Limit Theorem (CLT)-type results, even for so-called degenerate cases. Indeed,
in the general case, the CLT for $U$-statistics [16] ensures that the
distribution of $\sqrt{n}(U_{n}-\theta)$ converges to a Gaussian distribution
with known variance given by a quantity $V$. In some situations, corresponding
to degenerate cases, it is observed that $V=0$ which renders the previous CLT
trivial. However, [36] showed that there exists an integer $2\leq d\leq k$
such that the distribution of $n^{d/2}(U_{n}-\theta)$ converges to some non-
trivial distribution which can be identified. One important tool used to
derive this result is an orthogonal decomposition of $U_{n}$ called the
Hoeffding decomposition [17].

In this paper, we propose to tackle the problem of the asymptotic behavior of
$U$-statistics on row-column exchangeable (RCE) matrices. An infinite matrix
$Y$ is said to be RCE if its probability distribution is unchanged by separate
permutations of its rows and columns [1], i.e. for any couple of permutations
$(\sigma_{1},\sigma_{2})$ of $\mathbb{N}$,

$(Y_{\sigma_{1}(i)\sigma_{2}(j)})_{i,j}\overset{\mathcal{D}}{=}Y.$

For some integer $n>0$, let $\llbracket n\rrbracket:=\\{1,\dots,n\\}$ and
$\mathbb{S}_{n}$ denote the group of permutations of $\llbracket n\rrbracket$.
The kernels considered are functions of a matrix of size $p\times q$ with the
following symmetry property: the function
$h:\mathcal{M}_{p,q}(\mathbb{R})\rightarrow\mathbb{R}$ is symmetric if for all
$(\sigma_{1},\sigma_{2})\in\mathbb{S}_{p}\times\mathbb{S}_{q}$,

$h(Y_{(i_{\sigma_{1}(1)},...,i_{\sigma_{1}(p)};j_{\sigma_{2}(1)},...,j_{\sigma_{2}(q)})})=h(Y_{(i_{1},i_{2},...,i_{p};j_{1},j_{2},...,j_{q})}),$

where $Y_{(i_{1},...,i_{p};j_{1},...,j_{q})}$ is the $p\times q$ submatrix of
$Y$ consisting of the rows and columns of $Y$ indexed by $i_{1},...,i_{p}$ and
$j_{1},...,j_{q}$ respectively. Using such symmetric functions, the order of
the indices of the submatrix does not matter, so we will be denoting

$h(Y_{\\{i_{1},...,i_{p}\\};\\{j_{1},...,j_{q}\\}}):=h(Y_{(i_{1},i_{2},...,i_{p};j_{1},j_{2},...,j_{q})}).$

The associated $U$-statistic $U_{m,n}$ computed on the first $m$ rows and $n$
columns of an infinite matrix $Y$ is

$U_{m,n}=\binom{m}{p}^{-1}\binom{n}{q}^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}h(Y_{\mathbf{i},\mathbf{j}}),$ (1)

where for a set $A$ and an integer $k$, $\mathcal{P}_{k}(A)$ denotes the set
of all the subsets of $A$ with cardinal $k$, for an integer $\ell$,
$\llbracket\ell\rrbracket$ denotes the set $\\{1,\dots,\ell\\}$ and the matrix
$Y_{\mathbf{i},\mathbf{j}}$ is the submatrix of $Y$ generated by the row
indices elements of $\mathbf{i}$ and the column indices elements of
$\mathbf{j}$. A Hoeffding-type decomposition for these $U$-statistics has been
suggested in [24]. This decomposition has been used to derive the CLT, as well
as a generic estimator for the asymptotic variance, for these network
$U$-statistics. However, this decomposition is insufficient to identify their
limit distribution in the degenerate case.

The motivation behind the use of RCE matrices lies in network analysis. A
considerable number of real-world datasets consist of relational data between
entities, which finds a natural representation in a network format. In
networks, the entities correspond to nodes, and their connections are
indicated by links. Many networks are bipartite, i.e. they have two distinct
sets of nodes, and edges exclusively connect nodes from different sets.
Typical examples of bipartite network-structured data include recommender
systems [41], scientific authorship networks [30] or ecological pollination
networks [11]. The most straightforward way to depict these networks is
through their rectangular adjacency matrices. In an adjacency matrix $Y$, the
rows and columns correspond to the two distinct types of nodes of the
bipartite network, and each matrix entry $Y_{ij}$ encodes the relation between
the entities associated to row $i$ and column $j$. For binary data, $Y_{ij}$
equals 1 if nodes $i$ and $j$ are linked and 0 otherwise. In the case of
weighted data, $Y_{ij}$ represents the weight of the edge connecting nodes $i$
and $j$.

Exchangeability of the nodes is a common assumption in probabilistic network
analysis. Many random network models are exchangeable, including the
stochastic block models [38], the expected degree distribution models [32],
the graphon model [27] and their bipartite counterparts [15, 31, 10]. This
assumption means that the probability distribution of a network remains
invariant if its nodes are shuffled. In a bipartite network, since there are
two sets of nodes, exchangeability refers to the invariance of its
distribution when the nodes of each set are separately shuffled. Therefore,
the adjacency matrix of an exchangeable bipartite network consists of the
leading rows and columns of an infinite RCE matrix, and $U$-statistics on such
matrices define a class of network statistics. Among the network statistics
that can be written as $U$-statistics, motif (or subgraph) counts have been
well-studied and characterize the topology of networks [39, 32, 35, 7, 6, 9,
14, 26, 28, 29, 31]. They have been widely used to analyze networks in many
areas of science, including biology [37, 33, 34], ecology [3, 40, 2, 22] and
sociology [4, 13, 12, 8].

The aim of this paper is to define a new Hoeffding-type orthogonal
decomposition for $U$-statistics on RCE matrices. This new decomposition share
some similarities with that of the generalized $U$-statistics studied by [19],
used in the recent works of [21] and [5]. However, these two studies mainly
deal with motif counts in unipartite binary exchangeable networks. More
precisely, [21] studied the asymptotic distribution of so-called "centered"
motif counts, which are not proper $U$-statistics directly computed on the
observed data as defined by (1). They obtained a normal approximation theorem
through Stein’s method, but they did not consider degenerate cases. In
contrast, [5] focused on usual motif counts and their limit distribution in
degenerate cases, depending on the properties of the network model. However,
many other interesting statistics can also be expressed as network
$U$-statistics, notably when the networks are weighted [23, 24]. In addition,
the bipartite setup of our network data induces a different dependence
structure.

Our main contribution is the derivation of a decomposition in the more generic
framework of network $U$-statistics and bipartite exchangeable models. The key
to this decomposition lies in the Aldous-Hoover-Kallenberg (AHK)
representation of RCE matrices [18, 1, 20], which links the decomposition to
the theory of bipartite exchangeable networks. We show that this decomposition
identifies the limit distribution for $U$-statistics on RCE matrices,
therefore offering a characterization for them. Section 1.1 presents the AHK
representation of RCE matrices and Section 1.2 introduces a new tool, namely
the graph sets of AHK variables. These graph sets are used in Section 2.1,
which defines the probability spaces establishing the basis for an orthogonal
decomposition of $U$-statistics on RCE matrices. This decomposition is
formally given in Section 2.2, and Section 2.3 uses it to derive a
decomposition for the variance of $U$-statistics on RCE matrices. Section 3.1
links the decomposition to the limit distribution of $U$-statistics through
the lens of the principal support graphs, which will be defined there. We show
that the limit distribution is given by the leading terms of the decomposition
which are generated by these principal support graphs. As an example, Section
3.2 gives a sufficient condition on the principal support graphs to have a
Gaussian limit. Finally, Section 3.3 discusses other asymptotic regimes and
their consequences on the principal support graphs.

##  1 Sets of Aldous-Hoover-Kallenberg variables

###  1.1 Aldous-Hoover-Kallenberg representation of RCE matrices

We use the Aldous-Hoover-Kallenberg (AHK) representation for RCE matrices [18,
1, 20]. If $Y$ is a dissociated RCE matrix, then there exist $(\xi_{i})_{i\geq
1}$, $(\eta_{j})_{j\geq 1}$ and $(\zeta_{ij})_{i,j\geq 1}$ arrays of i.i.d.
random variables with uniform distribution over $[0,1]$ and a real measurable
function $\phi$ such that for all $1\leq i,j<\infty$,

$Y_{ij}\overset{a.s.}{=}\phi(\xi_{i},\eta_{j},\zeta_{ij}).$

A function of entries of $Y$ can be written with the AHK variables. In
particular, the kernel $h(Y_{\mathbf{i},\mathbf{j}})$, where
$\mathbf{i}\in\mathcal{P}_{p}(\mathbb{N})$ and
$\mathbf{j}\in\mathcal{P}_{q}(\mathbb{N})$, can be written as

$h(Y_{\mathbf{i},\mathbf{j}})=h\Big{(}\big{(}\phi(\xi_{i},\eta_{j},\zeta_{ij})\big{)}_{i\in\mathbf{i},j\in\mathbf{j}}\Big{)}=:h_{\phi}\big{(}(\xi_{i})_{i\in\mathbf{i}},(\eta_{j})_{j\in\mathbf{j}},(\zeta_{ij})_{i\in\mathbf{i},j\in\mathbf{j}}\big{)},$

and $h_{\phi}:[0,1]^{p+q+pq}\rightarrow\mathbb{R}$ is a symmetric function.
The $U$-statistic with kernel $h$ defined by (1) can be rewritten with
$h_{\phi}$ as follows

$U_{m,n}=\left[\binom{m}{p}\binom{n}{q}\right]^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}h_{\phi}\big{(}(\xi_{i})_{i\in\mathbf{i}},(\eta_{j})_{j\in\mathbf{j}},(\zeta_{ij})_{i\in\mathbf{i},j\in\mathbf{j}}\big{)}.$

With this formula, it becomes apparent that $U_{m,n}$ shares some similarities
with the generalized $U$-statistics defined by [19]. Their generalized
$U$-statistics are averages of random variables of the form
$f((\xi_{i})_{i\in\mathbf{i}};(\zeta_{ij})_{(i,j)\in\mathbf{i}^{2},i\neq j})$.
Thus, although generalized $U$-statistics are adapted to unipartite random
graphs, our bipartite setup changes the structure of the variables averaged in
the $U$-statistics, which will lead to a different characterization.

For simplification, we will now write
$h_{\mathbf{i},\mathbf{j}}:=h_{\phi}\big{(}(\xi_{i})_{i\in\mathbf{i}},(\eta_{j})_{j\in\mathbf{j}},(\zeta_{ij})_{i\in\mathbf{i},j\in\mathbf{j}}\big{)}$,
so that

$U_{m,n}=\left[\binom{m}{p}\binom{n}{q}\right]^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}h_{\mathbf{i},\mathbf{j}}.$

###  1.2 Graph sets of Aldous-Hoover-Kallenberg variables

The idea behind the new decomposition of a $U$-statistic is to find orthogonal
projections first for $h_{\mathbf{i},\mathbf{j}}$, for all $\mathbf{i}$ and
$\mathbf{j}$, and then use the previous expression to derive the decomposition
for $U_{m,n}$. In order to define the projections for
$h_{\mathbf{i},\mathbf{j}}$, we have to define the relevant subspaces for
these projections. These subspaces, defined in the next section, are generated
by subsets of AHK variables. In order to denote these subsets, we will be
using a notation involving bipartite graphs. These graphs have no direct link
with the network data, they are just a formalism to define subsets of AHK
variables.

####  1.2.1 Notations for bipartite graphs

A bipartite graph $G$ is denoted $G=\big{(}V_{1}(G),V_{2}(G),E(G)\big{)}$,
where $V_{1}(G)$ and $V_{2}(G)$ are the two sets of vertices and
$E(G)\subseteq V_{1}(G)\times V_{2}(G)$ is the set of edges of $G$. We denote
$v_{1}(G)=\mathrm{Card}\big{(}V_{1}(G)\big{)}$ and
$v_{2}(G)=\mathrm{Card}\big{(}V_{2}(G)\big{)}$. A subgraph $F\subseteq G$ is
such that $V_{1}(F)\subseteq V_{1}(G)$, $V_{2}(F)\subseteq V_{2}(G)$ and
$E(F)\subseteq\big{(}V_{1}(F)\times V_{2}(F)\big{)}\cap E(G)$. We write
$F\subset G$ if we have both $F\subseteq G$ and $F\neq G$.

Let $E=\\{e_{i}:i\in I\\}$ be a countable set indexed by $I$ and $\sigma$ some
mapping $\sigma:I\rightarrow I$. We denote the action of $\sigma$ on $E$ by
$\sigma E=\\{e_{\sigma(i)}:i\in I\\}$. Let $G$ be a bipartite graph. Suppose
that $V_{1}(G)$ is indexed by the set $I$ and $V_{2}(G)$ by the set $J$. The
action of a couple of mappings $\Phi=(\sigma_{1},\sigma_{2})$ on $G$, where
$\sigma_{1}:I\rightarrow I$ and $\sigma_{1}:J\rightarrow J$, is denoted

$\Phi G:=\big{(}\sigma_{1}V_{1}(G),\sigma_{2}V_{2}(G),\Phi E(G)\big{)},$ (2)

where $\Phi
E(G)=\big{\\{}(x_{\sigma_{1}(i)},y_{\sigma_{2}(j)}):(x_{i},y_{j})\in
E(G),(i,j)\in I\times J\big{\\}}$. Among these mappings, the bijective ones
are called permutations.

For two bipartite graphs $G_{1}$ and $G_{2}$ with same number of row nodes
$r=v_{1}(G_{1})=v_{1}(G_{2})$ and column nodes $c=v_{2}(G_{1})=v_{2}(G_{2})$,
we say that they are isomorphic if and only if there exists a couple of
permutations
$\Phi=(\sigma_{1},\sigma_{2})\in\mathbb{S}_{r}\times\mathbb{S}_{c}$ such that
$\Phi G_{1}=G_{2}$. In this case, we write $G_{1}\sim G_{2}$. The number of
elements $\Phi$ of $\mathbb{S}_{r}\times\mathbb{S}_{c}$ such that $\Phi G=G$
is the number of automorphisms of $G$, denoted $\lvert\mathrm{Aut}(G)\rvert$.

We define
$K_{\mathbf{i},\mathbf{j}}=(\mathbf{i},\mathbf{j},\mathbf{i}\times\mathbf{j})$
the fully connected bipartite graph with row node set $\mathbf{i}$ and column
node set $\mathbf{j}$. For $p\geq 0$ and $q\geq 0$, we denote
$K_{p,q}=K_{\llbracket p\rrbracket,\llbracket q\rrbracket}$.

For $r\geq 0$ and $c\geq 0$, we can define a minimal set $\Gamma_{r,c}$ of all
subgraphs of $K_{r,c}$ with $r$ row nodes and $c$ column nodes, such that
every graph $G$ with the same numbers of nodes is isomorphic to exactly one
element of $\Gamma_{r,c}$. Denote
$\Gamma^{-}_{p,q}=\bigcup_{(0,0)<(r,c)\leq(p,q)}\Gamma_{r,c}$. As a reminder,
$(0,0)<(r,c)\leq(p,q)$ means $0\leq r\leq p$, $0\leq c\leq q$ and
$(r,c)\neq(0,0)$. Every non-empty graph $G$ with $v_{1}(G)\leq p$ and
$v_{2}(G)\leq q$ is isomorphic to exactly one element of $\Gamma^{-}_{p,q}$.

####  1.2.2 Definition of graph sets

Let $G$ be a bipartite graph. We can define the set $H(G)$ of AHK variables
associated to $G$ as

$H(G)=\big{(}(\xi_{i})_{i\in V_{1}(G)},(\eta_{j})_{j\in
V_{2}(G)},(\zeta_{ij})_{(i,j)\in E(G)}\big{)}.$

We see that
$h_{\mathbf{i},\mathbf{j}}=h_{\phi}\big{(}(\xi_{i})_{i\in\mathbf{i}},(\eta_{j})_{j\in\mathbf{j}},(\zeta_{ij})_{i\in\mathbf{i},j\in\mathbf{j}}\big{)}=h_{\phi}\big{(}H(K_{\mathbf{i},\mathbf{j}})\big{)}$.
In other words, $h_{\mathbf{i},\mathbf{j}}$ belongs to some functional
probability space generated by the AHK variables
$H(K_{\mathbf{i},\mathbf{j}})$. The subspaces on which
$h_{\mathbf{i},\mathbf{j}}$ will be decomposed are generated by subsets of
$H(K_{\mathbf{i},\mathbf{j}})$, which are of the form $H(G)$, where $G\subset
K_{\mathbf{i},\mathbf{j}}$, as shown in Figure 1.

Figure 1: A bipartite graph and one subgraph. For each graph, the row nodes
are on the right and the column nodes are on the left. Left: the graph
$K_{3,2}$. Right: a subgraph $G$ extracted from the row nodes $\\{2,3\\}$ and
the column nodes $\\{1,2\\}$ of $K_{3,2}$. Here, $G$ only keeps one edge among
the four allowed between the row nodes $\\{2,3\\}$ and the column nodes
$\\{1,2\\}$. $G$ defines the subset
$H(G)=\big{(}\\{\xi_{2},\xi_{3}\\},\\{\eta_{1},\eta_{2}\\},\\{\zeta_{13}\\}\big{)}$.

In the following section, we define rigorously these subspaces and we exhibit
some of their properties. This enables us to define a decomposition for
$U$-statistics on RCE matrices.

##  2 Orthogonal decomposition of $U$-statistics on RCE matrices

###  2.1 Decomposition of the probability space

Let $G$ be a bipartite graph and denote $L_{2}(G)$ the space of all square-
integrable random variables measurable with respect to $\sigma(H(G))$.
$L_{2}(G)$ is an Hilbert space with inner product
$\left<X,Y\right>=\mathbb{E}[XY]$. We investigate the following decomposition
for $X\in L_{2}(G)$

$X=\sum_{F\subseteq G}p^{F}(X),$ (3)

where the $p^{F}(X)$ are defined by recursion with
$p^{\emptyset}(X)=\mathbb{E}[X]$ and for all $F$,

$p^{F}(X)=\mathbb{E}[X\mid H(F)]-\sum_{F^{\prime}\subset F}p^{F^{\prime}}(X).$

Now, we define $L_{2}^{*}(G)\subset L_{2}(G)$ as follows

$L_{2}^{*}(G)=\left\\{X\in L_{2}(G):\mathbb{E}[X\mid H(F)]=0,\forall F\subset
G\right\\}.$ (4)

These subspaces are linked to the decomposition (3). First, we show that each
term of the decomposition belongs indeed to one of these spaces, which shows
that the decomposition is a decomposition on these subspaces. The following
proposition can be shown by induction, as indicated in Appendix A.

######  Proposition 2.1.

For two bipartite graphs $F\subseteq G$ and $X\in L_{2}(G)$, $p^{F}(X)\in
L_{2}^{*}(F)$.

Now, we prove the most important property of this decomposition. An Hoeffding-
type decomposition is an orthogonal decomposition. The following proposition
shows that it is the case.

######  Proposition 2.2.

For all bipartite graph $G$, $L_{2}(G)$ is the orthogonal direct sum
$L_{2}(G)\bigoplus^{\perp}_{F\subseteq G}L_{2}^{*}(F)$.

###### Proof.

Equation (3) and Proposition 2.1 already show that
$L_{2}(G)\bigoplus_{F\subseteq G}L_{2}^{*}(F)$. We only have to show that for
any two distinct bipartite graphs $G_{1}$ and $G_{2}$, we have
$L_{2}^{*}(G_{1})\perp L_{2}^{*}(G_{2})$. Let $X_{1}\in L_{2}^{*}(G_{1})$ and
$X_{2}\in L_{2}^{*}(G_{2})$. Let $\overline{G}=G_{1}\cap G_{2}$. Since $G_{1}$
and $G_{2}$ are distinct, then at least one of the affirmations
$\overline{G}\subset G_{1}$ and $\overline{G}\subset G_{2}$ is true. Assume
that $\overline{G}\subset G_{1}$, then
$\mathbb{E}[X_{1}X_{2}]=\mathbb{E}[\mathbb{E}[X_{1}X_{2}\mid
H(G_{1})]]=\mathbb{E}[X_{1}\mathbb{E}[X_{2}\mid H(\overline{G})]]=0$, so
$L_{2}^{*}(G_{1})\perp L_{2}^{*}(G_{2})$. ∎

######  Remark 1.

From this proof, we can see that $L_{2}^{*}(G)$ can also be characterized by
the expression $L_{2}^{*}(G)=L_{2}(G)\cap(\cup_{F\subset G}L_{2}(F)^{\perp})$.

###  2.2 Decomposition of $U$-statistics

For all $(0,0)\leq(p,q)\leq(m,n)$,
$(\mathbf{i},\mathbf{j})\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\times\mathcal{P}_{q}(\llbracket n\rrbracket)$, $G\subseteq
K_{\mathbf{i},\mathbf{j}}$, we can apply the decomposition (3) on
$h_{\mathbf{i},\mathbf{j}}\in L_{2}(K_{\mathbf{i},\mathbf{j}})$.

$p^{G}(h_{\mathbf{i},\mathbf{j}})=\mathbb{E}[h_{\mathbf{i},\mathbf{j}}\mid
H(G)]-\sum_{F\subset G}p^{F}(h_{\mathbf{i},\mathbf{j}}),$

where
$p^{\emptyset}(h_{\mathbf{i},\mathbf{j}})=\mathbb{E}[h_{\mathbf{i},\mathbf{j}}]=\mathbb{E}[h_{\llbracket
p\rrbracket,\llbracket q\rrbracket}]$.

For all $G\subseteq K_{\mathbf{i},\mathbf{j}}$, we remind that
$V_{1}(G)\subseteq\mathbf{i}$ and $V_{2}(G)\subseteq\mathbf{j}$. Define
$\overline{V_{1}(G)}$ and $\overline{V_{2}(G)}$ the complements of
respectively $V_{1}(G)$ and $V_{2}(G)$ in respectively $\mathbf{i}$ and
$\mathbf{j}$. In fact, the term $p^{G}(h_{\mathbf{i},\mathbf{j}})$ does not
depend on the elements of $\overline{V_{1}(G)}$ and $\overline{V_{2}(G)}$,
i.e. even if
$(\mathbf{i}_{1},\mathbf{j}_{1})\neq(\mathbf{i}_{2},\mathbf{j}_{2})$, as long
as $G\subset K_{\mathbf{i}_{1},\mathbf{j}_{1}}\cap
K_{\mathbf{i}_{2},\mathbf{j}_{2}}$, we have
$p^{G}(h_{\mathbf{i}_{1},\mathbf{j}_{1}})=p^{G}(h_{\mathbf{i}_{2},\mathbf{j}_{2}})$.
Therefore, we use the notation $p^{G}:=p^{G}(h_{\mathbf{i},\mathbf{j}})$, for
all $G\in K_{\mathbf{i},\mathbf{j}}$. From Equation (3), we can write

$h_{\mathbf{i},\mathbf{j}}=\sum_{G\subseteq K_{\mathbf{i},\mathbf{j}}}p^{G},$

and the $U$-statistic $U_{m,n}$ can be rewritten

$\begin{split}U_{m,n}&=\binom{m}{p}^{-1}\binom{n}{q}^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{G\subseteq K_{\mathbf{i},\mathbf{j}}}p^{G}\\\
&=\binom{m}{p}^{-1}\binom{n}{q}^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{(0,0)\leq(r,c)\leq(p,q)}\sum_{\begin{subarray}{c}G\subseteq
K_{\mathbf{i},\mathbf{j}}\\\ (v_{1}(G),v_{2}(G))=(r,c)\end{subarray}}p^{G}\\\
&=\sum_{(0,0)\leq(r,c)\leq(p,q)}P^{r,c}_{m,n},\end{split}$

where
$P^{r,c}_{m,n}=\binom{m}{p}^{-1}\binom{n}{q}^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{\begin{subarray}{c}G\subseteq
K_{\mathbf{i},\mathbf{j}}\\\ (v_{1}(G),v_{2}(G))=(r,c)\end{subarray}}p^{G}$.

Note that in general, for $G\subseteq K_{\mathbf{i},\mathbf{j}}$, $p^{G}$ is
not symmetric, that means
$p^{G}(h_{\sigma_{1}\mathbf{i},\sigma_{2}\mathbf{j}})\neq
p^{G}(h_{\mathbf{i},\mathbf{j}})$ for a couple of permutations
$(\sigma_{1},\sigma_{2})\in\mathbb{S}_{p}\times\mathbb{S}_{q}$. We define
$\bar{p}^{G}$ the symmetrized version of $p^{G}$ as

$\bar{p}^{G}=\sum_{(\sigma_{1},\sigma_{2})\in\mathbb{S}_{p}\times\mathbb{S}_{q}}p^{G}(h_{\sigma_{1}\mathbf{i},\sigma_{2}\mathbf{j}})=\sum_{\Phi\in\mathbb{S}_{p}\times\mathbb{S}_{q}}p^{\Phi
G}=\sum_{\begin{subarray}{c}G^{\prime}\subseteq K_{\mathbf{i},\mathbf{j}}\\\
G^{\prime}\sim G\end{subarray}}p^{G^{\prime}}.$

For two isomorphic subgraphs $G_{1}$ and $G_{2}$ of
$K_{\mathbf{i},\mathbf{j}}$, we have $\bar{p}^{G_{1}}=\bar{p}^{G_{2}}$ by
symmetry. There is exactly one element $G\in\Gamma_{r,c}$, where
$r=v_{1}(G_{1})=v_{1}(G_{2})$ and $c=v_{2}(G_{1})=v_{2}(G_{2})$, which is
isomorphic to both $G_{1}$ and $G_{2}$. Therefore, for all
$(\mathbf{i},\mathbf{j})\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\times\mathcal{P}_{q}(\llbracket n\rrbracket)$, we can index these
quantities with the graph $G\in\Gamma_{r,c}$ instead of $G\in
K_{\mathbf{i},\mathbf{j}}$. Then, we denote

$\tilde{p}^{G}_{\mathbf{i},\mathbf{j}}:=\bar{p}^{G^{\prime}},$

where $G\in\Gamma_{r,c}$ and $G^{\prime}$ is any subgraph of
$K_{\mathbf{i},\mathbf{j}}$ which is isomorphic to $G$. We can also denote
$\tilde{p}^{G}$ the function
$\tilde{p}^{G}:(\mathbf{i},\mathbf{j})\longmapsto\tilde{p}^{G}_{\mathbf{i},\mathbf{j}}$.

Because there are
$r!\binom{p}{r}c!\binom{q}{c}\lvert\mathrm{Aut}(G)\rvert^{-1}$ distinct
subgraphs of $K_{\mathbf{i},\mathbf{j}}$ that are isomorphic to
$G\in\Gamma_{r,c}$, we obtain the following alternative decomposition

$h_{\mathbf{i},\mathbf{j}}=(p!q!)^{-1}\sum_{G\subseteq
K_{\mathbf{i},\mathbf{j}}}\bar{p}^{G}=\sum_{0\leq(r,c)\leq(p,q)}\sum_{G\in\Gamma_{r,c}}\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\tilde{p}^{G}_{\mathbf{i},\mathbf{j}}$

and

$P^{r,c}_{m,n}=\sum_{G\in\Gamma_{r,c}}\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\tilde{P}^{G}_{m,n},$

where for all $G\in\Gamma_{r,c}$,
$\tilde{P}^{G}_{m,n}=\binom{m}{p}^{-1}\binom{n}{q}^{-1}\sum_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\tilde{p}^{G}_{\mathbf{i},\mathbf{j}}$ is the
$U$-statistic of kernel $\tilde{p}^{G}$. Finally, the $U_{m,n}$ can be
rewritten as

$U_{m,n}=\sum_{0\leq(r,c)\leq(p,q)}\sum_{G\in\Gamma_{r,c}}\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\tilde{P}^{G}_{m,n}.$
(5)

######  Remark 2.

This decomposition is related to the one defined by [24]. The latter consists
of an orthogonal projection of $h_{\mathbf{i},\mathbf{j}}\in
L_{2}(K_{\mathbf{i},\mathbf{j}})$ on the subspaces
$(\underline{L}_{2}(K_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}))_{\mathbf{i}^{\prime}\subseteq\mathbf{i},\mathbf{j}^{\prime}\subseteq\mathbf{j}}$,
where

$\underline{L}_{2}(K_{\mathbf{i},\mathbf{j}})=\\{X\in
L_{2}(K_{\mathbf{i},\mathbf{j}}):\mathbb{E}[X\mid
H(K_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}})]=0,\forall\mathbf{i}^{\prime}\subseteq\mathbf{i},\mathbf{j}^{\prime}\subseteq\mathbf{j}\\}.$
(6)

Comparing this with the subspaces (4), we see that the decomposition on the
subspaces of the form (6) is coarser, as they only consist in subspaces
generated by graphs of the form $K_{\mathbf{i},\mathbf{j}}$. For this reason,
it does not capture the subtleties determining the limit distribution of
degenerate $U$-statistics. We will see that the decomposition given by
equation (5) is able to fill this gap, at the cost of being more complex.

###  2.3 Decomposition of the variance of $U$-statistics

Just like the classic Hoeffding decomposition of $U$-statistics of i.i.d.
observations [17], the decomposition (5) is convenient to decompose the
variance of $U$-statistics on row-column exchangeable matrices. The following
two results come from the orthogonality of the projections. For a random
variable $X$, $\mathbb{V}[X]$ denotes its variance.

The first expression links $\mathbb{V}[U_{m,n}]$ to the variance of the
projections $\mathbb{V}[p^{G}]=\mathbb{E}[(p^{G})^{2}]$. It is obtained by
direct calculation, as shown in Appendix B.

######  Proposition 2.3.

$\mathbb{V}[U_{m,n}]=\sum_{(0,0)<(r,c)\leq(p,q)}\frac{(m-r)!}{m!}\frac{(n-c)!}{n!}V^{(r,c)},$

where for all $(0,0)<(r,c)\leq(p,q)$,

$V^{(r,c)}=\frac{p!^{2}q!^{2}}{(p-r)!^{2}(q-c)!^{2}}\sum_{G\in\Gamma_{r,c}}\lvert\mathrm{Aut}(G)\rvert^{-1}\mathbb{E}[(p^{G})^{2}].$

The second expression links $\mathbb{V}[U_{m,n}]$ to the variance of the
$U$-statistics $\tilde{P}^{G}_{m,n}$ associated to the symmetrized projections
$\tilde{p}^{G}$.

######  Corollary 2.4.

$\begin{split}\mathbb{V}[U_{m,n}]&=\sum_{0<(r,c)\leq(p,q)}\sum_{G\in\Gamma_{r,c}}\left(\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\right)^{2}\mathbb{V}[\tilde{P}^{G}_{m,n}]\\\
\end{split}$

It can actually be naturally obtained from Proposition 2.3 using the following
lemma.

######  Lemma 2.5.

$\mathbb{V}[\tilde{P}^{G}_{m,n}]=\frac{(m-r)!}{m!}\frac{(n-c)!}{n!}p!^{2}q!^{2}\rvert\mathrm{Aut}(G)\lvert\mathbb{E}[(p^{G})^{2}].$

The proof of this lemma requires to handle the symmetrized projections, which
can be tricky. In this regard, the next lemma is particularly helpful. For
this reason, it will also be used several times later. The proofs of both
lemmas are given in Appendix B.

######  Lemma 2.6.

Let $G$ subgraph of $K_{p,q}$. Let
$(G^{1}_{\mathbf{i},\mathbf{j}})_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}$ and
$(G^{2}_{\mathbf{i},\mathbf{j}})_{\begin{subarray}{c}\mathbf{i}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}$ two families of graphs such that for all
$(\mathbf{i},\mathbf{j})\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\times\mathcal{P}_{q}(\llbracket n\rrbracket)$, both
$G^{1}_{\mathbf{i},\mathbf{j}},G^{2}_{\mathbf{i},\mathbf{j}}\subseteq
K_{\mathbf{i},\mathbf{j}}$ and are isomorphic to $G$. We have

$\sum_{\begin{subarray}{c}\mathbf{i}_{1},\mathbf{i}_{2}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}_{1},\mathbf{j}_{2}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{\Phi_{1},\Phi_{2}\in\mathbb{S}_{p}\times\mathbb{S}_{q}}\mathds{1}(\Phi_{1}G^{1}_{\mathbf{i}_{1},\mathbf{j}_{1}}=\Phi_{2}G^{2}_{\mathbf{i}_{2},\mathbf{j}_{2}})=\frac{m!(m-r)!}{(m-p)!^{2}}\frac{n!(n-c)!}{(n-q)!^{2}}\lvert\mathrm{Aut}(G)\rvert.$

##  3 Asymptotic behavior

###  3.1 Principal part and support graphs

Let us define a sequence for network sizes $(m_{N},n_{N})$ such that
$m_{N}+n_{N}=N$ and $m_{N}/N\xrightarrow[N\rightarrow\infty]{}\rho$, for some
$\rho\in]0,1[$. We denote $U_{N}:=U_{m_{N},n_{N}}$,
$P^{r,c}_{N}:=P^{r,c}_{m_{N},n_{N}}$ and
$\tilde{P}^{G}_{N}:=\tilde{P}^{G}_{m_{N},n_{N}}$. The kernel $h$ is still a
symmetric function of a matrix of size $p\times q$. Other regimes for $m_{N}$
and $n_{N}$ are considered in Section 3.3. In this asymptotic framework, we
give the following definitions.

######  Definition 3.1.

Let

$p^{(k)}:=\sum_{\begin{subarray}{c}G\in K_{p,q}\\\
v_{1}(G)+v_{2}(G)=k\end{subarray}}p^{G},$

for $1\leq k\leq p+q$. Let $d$ be the smallest integer such that $p^{(d)}\neq
0$. We call $d-1$ the degree of degeneracy of $U_{N}$. Then we have
$P^{r,c}_{N}=0$ for all $(r,c)$ such that $r+c<d$. By analogy with the theory
of generalized $U$-statistics [19], we call
$\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}$ the principal part of $U_{N}$ and the couples
$(r,c)$ such that $r+c=d$ are the principal degrees of $U_{N}$. We call the
principal support graphs of $U_{N}$ the graphs $G\subseteq K_{m,n}$ such that

  * •

$v_{1}(G)+v_{2}(G)=d$,

  * •

$p^{G}\neq 0$.

######  Example 1.

Let $Y$ be a random matrix such that
$Y_{ij}\overset{i.i.d.}{\sim}\mathcal{N}(0,1)$. Let $h_{1}$ and $h_{2}$ be the
kernel functions defined by $h_{1}(Y_{\\{1\\},\\{1,2\\}})=Y_{11}Y_{12}$ and
$h_{2}(Y_{\\{1,2\\},\\{1,2\\}})=(Y_{11}Y_{22}+Y_{12}Y_{21})/2$, and
$U^{h_{1}}_{N}$ and $U^{h_{2}}_{N}$ are the $U$-statistics associated to these
kernels.
$Y$ admits a natural AHK representation, which is
$Y_{ij}\overset{a.s.}{=}\phi(\xi_{i},\eta_{j},\zeta_{ij})=\Phi^{-1}(\zeta_{ij})$,
where $\Phi^{-1}$ is the inverse c.d.f. of the standard Gaussian distribution.
Remarkably, $Y_{ij}$ does not depend on the AHK variables $\xi_{i}$ and
$\eta_{j}$. We have
$\mathbb{E}[Y_{ij}]=\mathbb{E}[Y_{ij}\mid\xi_{i}]=\mathbb{E}[Y_{ij}\mid\eta_{j}]=\mathbb{E}[Y_{ij}\mid\xi_{i},\eta_{j}]=0$
and $\mathbb{E}[Y_{ij}\mid\xi_{i},\eta_{j},\zeta_{ij}]=Y_{ij}$.

  * •

For $U^{h_{1}}_{N}$, $\mathbb{E}[h_{1}(Y_{\\{1,2\\},\\{1,2\\}})\mid H(G)]\neq
0$ if and only if

$H(K_{1,2})=(\xi_{1},\eta_{1},\eta_{2},\zeta_{11},\zeta_{12})\subseteq H(G).$

Indeed, we have for all $G\subset K_{1,2}$,
$\mathbb{E}[h_{1}(Y_{\\{1\\},\\{1,2\\}})\mid H(G)]=0$ and
$\mathbb{E}[h_{1}(Y_{\\{1\\},\\{1,2\\}})\mid H(K_{1,2})]=Y_{11}Y_{12}$.
Therefore, the only graph $G\subseteq K_{1,2}$ such that $p^{G}\neq 0$ is
$G=K_{1,2}$. Thus, $U^{h_{1}}_{N}$ is degenerate of order $2$ and the family
of principal support graphs of $U^{h_{1}}_{N}$ is
$(K_{\mathbf{i},\mathbf{j}})_{\mathbf{i}\in\mathcal{P}_{1}(\llbracket
m_{N}\rrbracket),\mathbf{j}\in\mathcal{P}_{2}(\llbracket n_{N}\rrbracket)}$
(Fig. 2).

  * •

For $U^{h_{2}}_{N}$, $\mathbb{E}[h_{2}(Y_{\\{1,2\\},\\{1,2\\}})\mid H(G)]\neq
0$ if and only if

$(\xi_{1},\xi_{2},\eta_{1},\eta_{2},\zeta_{11},\zeta_{22})\subseteq
H(G)\text{\quad or
\quad}(\xi_{1},\xi_{2},\eta_{1},\eta_{2},\zeta_{12},\zeta_{21})\subseteq
H(G).$

Therefore, if $\mathbb{E}[h_{2}(Y_{\\{1,2\\},\\{1,2\\}})\mid H(G)]\neq 0$,
then $v_{1}(G)=2$ or $v_{2}(G)=2$, so $U^{h_{2}}_{N}$ is degenerate of order
3. The principal support graphs are the graphs which are isomorphic to one
graph $G\subseteq\Gamma_{2,2}$ such that
$\mathbb{E}[h_{2}(Y_{\\{1,2\\},\\{1,2\\}})\mid H(G)]\neq 0$ (Fig. 2).

Figure 2: Examples of principal support graphs for $U^{h_{1}}_{N}$ (left) and
$U^{h_{2}}_{N}$ (right). The principal support graphs of $U^{h_{1}}_{N}$ are
the graphs that are isomorphic to the left one. The principal support graphs
of $U^{h_{2}}_{N}$ are the $2\times 2$ graphs containing graphs that are
isomorphic to the right one.

From Proposition 2.3,

$\begin{split}\mathbb{V}[U_{N}]&=\sum_{(0,0)<(r,c)\leq(p,q)}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}\end{split}$

We see that $\mathbb{V}[U_{N}]$ is the sum of the $p\times q$ terms of the
form $\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}$. Each term
behaves like
$\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}\asymp N^{-r-c}$.
If for some $(r,c)$, $\sum_{\begin{subarray}{c}G\in K_{p,q}\\\
(v_{1}(G),v_{2}(G))=(r,c)\end{subarray}}p^{G}=0$, then $V^{(r,c)}=0$.
Therefore,

$\begin{split}\mathbb{V}[U_{N}]&=N^{-d}\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}\rho^{-r}(1-\rho)^{-c}V^{(r,c)}+o(N^{-d})\\\
&=N^{-d}\sum_{r=0}^{d}\rho^{-r}(1-\rho)^{-d-r}V^{(r,d-r)}+o(N^{-d})\\\
\end{split}$

This is a hint that the right normalization for the convergence in
distribution of $U_{N}$ is given by its principal degrees. The following
theorem, proven in Appendix C, confirms it.

######  Theorem 3.2.

There is a random variable $W$ such that
$N^{d/2}(U_{N}-p^{\emptyset})\xrightarrow[]{\mathcal{D}}W$ if and only if

$N^{d/2}\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}\xrightarrow[]{\mathcal{D}}W.$

This theorem says that the limit distribution of $U_{N}-p^{\emptyset}$
renormalized by $N^{d/2}$ is the same as that of its principal part
$\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}$, renormalized by the same quantity.
Therefore, the principal support graphs of $U_{N}$ characterizes the limit
distribution of $U_{N}$. More specifically, the limit distribution depends on
the form of the principal support graphs of $U_{N}$.

###  3.2 Asymptotic Gaussian distribution

Now, we identify a sufficient condition for the principal support graphs to
have a Gaussian limit distribution for $N^{d/2}(U_{N}-p^{\emptyset})$, using
the properties of the principal part of $U_{N}$.

######  Theorem 3.3.

If all principal support graphs of $U_{N}$ are connected, then

$N^{d/2}(U_{N}-p^{\emptyset})\xrightarrow[N\rightarrow\infty]{\mathcal{D}}\mathcal{N}(0,\sigma^{2}),$

where

$\sigma^{2}=\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}\rho^{-r}(1-\rho)^{-c}V^{(r,c)}.$

###### Sketch of proof.

The proof of this theorem uses the fact that from Theorem 3.2,
$N^{d/2}(U_{N}-p^{\emptyset})$ has the same limit as

$N^{d/2}\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N},$

where

$P^{r,c}_{N}=\sum_{G\in\Gamma_{r,c}}\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\tilde{P}^{G}_{N}.$

Two lemmas are further needed. The convergence of the terms
$N^{d/2}\tilde{P}^{G}_{N}$ is proved by the methods of moments (Lem. 3.5). The
calculation of the moments involve sums of terms of the form
$\mathbb{E}[\prod_{k=1}^{K}p^{G_{k}}]$, the values of which depend on the
configuration of the sequence of graphs $G_{1},...,G_{k}$ (Lem. 3.4).
Therefore, the moments are obtained by counting the frequency of the relevant
configurations in these sums.

Below, Lemmas 3.4 and 3.5 are given before the full proof of Theorem 3.3. The
proofs for these lemmas can be found in Appendix D.

######  Lemma 3.4.

Let $G_{1},...,G_{K}$ be subgraphs of $K_{m_{N},n_{N}}$. If
$\mathbb{E}[\prod_{k=1}^{K}p^{G_{k}}]\neq 0$, then for all $G_{k}$, $1\leq
k\leq K$, each vertex of $V_{1}(G_{k})$ or $V_{2}(G_{k})$ or edge of
$E(G_{k})$ must also appear in another $G_{\ell}$, $\ell\neq k$.

Furthermore, if $G_{1},...,G_{K}$ are connected and non-empty, then either
$G_{1},...,G_{K}$ coincide in $K/2$ pairs (and $K$ is necessarily even), or
some vertex belongs to at least three of them.

######  Lemma 3.5.

Let $(G_{k})_{1\leq k\leq K}$ be a sequence of distinct connected graphs of
$\Gamma^{-}_{p,q}$, with $v_{1}(G_{k})=r_{k}$ and $v_{2}(G_{k})=c_{k}$ for
$1\leq k\leq K$. We have that

$(m_{N}^{r_{k}/2}n_{N}^{c_{k}/2}\tilde{P}^{G_{k}}_{N})_{1\leq k\leq
K}\xrightarrow[]{\mathcal{D}}(W_{k})_{1\leq k\leq K},$ (7)

where $W_{k}$ are independent variables with respective distribution
$\mathcal{N}(0,p!^{2}q!^{2}\lvert\mathrm{Aut}(G_{k})\rvert\mathbb{E}[(p^{G_{k}})^{2}])$.

∎

###### Proof of Theorem 3.3.

Theorem 3.2 states that $N^{d/2}(U_{N}-p^{\emptyset})$ has the same limit as

$N^{d/2}\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}.$

For all $(0,0)<(r,c)\leq(p,q)$,

$P^{r,c}_{N}=\sum_{G\in\Gamma_{r,c}}\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\tilde{P}^{G}_{N}.$

So

$N^{d/2}\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}=\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}N^{d/2}m_{N}^{-r/2}n_{N}^{-c/2}\sum_{G\in\Gamma_{r,c}}\frac{m_{N}^{r/2}n_{N}^{c/2}\tilde{P}^{G}_{N}}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}.$

By construction,
$N^{d/2}m_{N}^{-r/2}n_{N}^{-c/2}\xrightarrow[N\rightarrow\infty]{}\rho^{-r/2}(1-\rho)^{-c/2}$.
Therefore, by Lemma 3.5,

$N^{d/2}\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}$

converges in distribution to

$Z=\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}\rho^{-r/2}(1-\rho)^{-c/2}\sum_{G\in\Gamma_{r,c}}W_{G},$

where for all $(r,c)$, $G\in\Gamma_{r,c}$, $W_{G}$ are independent gaussian
variables with mean $0$ and variance

$\frac{p!^{2}q!^{2}}{(p-r)!^{2}(q-c)!^{2}\lvert\mathrm{Aut}(G)\rvert}\mathbb{E}[(p^{G})^{2}].$

Finally, it follows that $Z$ is a gaussian variable with mean $0$ and variance
$\sum_{\begin{subarray}{c}(0,0)<(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}\rho^{-r}(1-\rho)^{-c}V^{(r,c)}$ where

$V^{(r,c)}=\frac{p!^{2}q!^{2}}{(p-r)!^{2}(q-c)!^{2}}\sum_{G\in\Gamma_{r,c}}\lvert\mathrm{Aut}(G)\rvert^{-1}\mathbb{E}[(p^{G})^{2}].$

∎

######  Remark 3.

If $Y$ and $h$ are such that the principal support graphs of $U_{N}$ include
$K_{1,0}$ and $K_{0,1}$, then the principal degree of $U_{N}$ is $1$ and the
limit distribution is Gaussian. Then, Theorem 3.3 yields the non-degenerate
Central Limit Theorem for $U$-statistics on RCE matrices proved by [23] and
[24]. We have

$\sqrt{N}(U_{N}-p^{\emptyset})\xrightarrow[N\rightarrow\infty]{\mathcal{D}}\mathcal{N}(0,\sigma^{2}),$

where $\sigma^{2}=\rho^{-1}V^{(1,0)}+(1-\rho)^{-1}V^{(0,1)}$, with Proposition
2.3 giving $V^{(1,0)}=p^{2}\mathbb{V}[\mathbb{E}[h(Y_{\llbracket
p\rrbracket,\llbracket q\rrbracket})\mid\xi_{1}]]$ and
$V^{(0,0)}=q^{2}\mathbb{V}[\mathbb{E}[h(Y_{\llbracket p\rrbracket,\llbracket
q\rrbracket})\mid\eta_{1}]]$.
This also gives a characterization of the degeneracy of $U_{N}$. $U_{N}$ is
degenerate if and only if $V=0$, which means both $\mathbb{E}[h(Y_{\llbracket
p\rrbracket,\llbracket q\rrbracket})\mid\xi_{1}]=0$ and
$\mathbb{E}[h(Y_{\llbracket p\rrbracket,\llbracket
q\rrbracket})\mid\eta_{1}]=0$. This also only happens when neither $K_{1,0}$
nor $K_{0,1}$ are principal support graphs, i.e. when the principal degree of
$U_{N}$ is larger than $1$.
We deduce that there is no hope to obtain a faster rate of convergence than
$\sqrt{N}$ in non-degenerate cases and that it is always greater in degenerate
cases. This is in accordance with the discussion of [23], but it shows how the
principal support graphs and the principal degree of $U_{N}$ characterize the
degeneracy of $U_{N}$.

######  Example 1 (continued).

Let $Y$ be a random matrix such that
$Y_{ij}\overset{i.i.d.}{\sim}\mathcal{N}(0,1)$. Let $h_{1}$ be the kernel
function defined by $h_{1}(Y_{\\{1\\},\\{1,2\\}})=Y_{11}Y_{12}$ and
$U^{h_{1}}_{N}$ the $U$-statistic associated to this kernel. In Section 3.1,
we have seen that $U^{h_{1}}_{N}$ is degenerate of order $2$ and the family of
principal support graphs of $U^{h_{1}}_{N}$ is
$(K_{\mathbf{i},\mathbf{j}})_{\mathbf{i}\in\mathcal{P}_{1}(\llbracket
m_{N}\rrbracket),\mathbf{j}\in\mathcal{P}_{2}(\llbracket n_{N}\rrbracket)}$,
which are all connected.
Therefore, Theorem 3.3 implies

$N^{3/2}U^{h_{1}}_{N}\xrightarrow[N\rightarrow\infty]{\mathcal{D}}\mathcal{N}(0,\sigma_{1}^{2}),$

where
$\sigma_{1}^{2}=V^{(1,2)}=\frac{4}{\rho(1-\rho)^{2}}\lvert\mathrm{Aut}(K_{1,2})\rvert^{-1}\mathbb{E}[(p^{K_{1,2}})^{2}]=\frac{4}{\rho(1-\rho)^{2}}\frac{1}{2}\mathbb{E}[Y_{11}^{2}Y_{12}^{2}]=\frac{2}{\rho(1-\rho)^{2}}$.

###  3.3 Other asymptotic frameworks

In previous sections, we have assumed that $m_{N}+n_{N}=N$ and
$m_{N}/N\rightarrow\rho\in]0,1[$. It is in fact possible to extend all our
results to any asymptotic behavior. In this section, let us only assume that
$m_{N}\xrightarrow[N\rightarrow\infty]{}\infty$ and
$n_{N}\xrightarrow[N\rightarrow\infty]{}\infty$ and see how it affects the
limit distribution of $U_{N}$.

The principal part of $U_{N}$ should be the dominant part of the variance.
Remember that Proposition 2.3 states that

$\mathbb{V}[U_{N}]=\sum_{(0,0)<(r,c)\leq(p,q)}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}.$

We see that $\mathbb{V}[U_{N}]$ is the sum of the $p\times q$ terms of the
form $\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}$. Each term
behaves like
$\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}\asymp
m_{N}^{-r}n_{N}^{-c}$. The dominant part of $\mathbb{V}[U_{N}]$ is consist of
the terms $m_{N}^{-r}n_{N}^{-c}$ decreasing the slowest such that
$V^{(r,c)}\neq 0$.

There is no equivalent to the previously defined degree of degeneracy, but we
can redefine principal degrees. Let the family of couples
$((r_{\ell},c_{\ell}))_{1\leq\ell\leq L}$ be such that
$m_{N}^{r_{1}}n_{N}^{c_{1}}\asymp...\asymp m_{N}^{r_{L}}n_{N}^{c_{L}}$ and
$\mathbb{V}[U_{N}]\asymp\sum_{\ell=1}^{L}\frac{V^{(r_{\ell},c_{\ell})}}{m_{N}^{r_{\ell}}n_{N}^{c_{\ell}}}$.
We can call these couples the principal degrees of $U_{N}$, by analogy with
the previous case. The quantity $\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}$
is called the principal part of $U_{N}$. We call the principal support graphs
of $U_{N}$ the graphs $G$ such that

  * •

$(v_{1}(G),v_{2}(G))\in\\{(r_{\ell},c_{\ell}):1\leq\ell\leq L\\}$,

  * •

$p^{G}\neq 0$.

######  Example 2.

Suppose $(m_{N},n_{N})=(N,\sqrt{N})$ and $V^{(0,1)}=0$ but $V^{(0,2)}\neq 0$
and $V^{(1,0)}\neq 0$, then the principal degrees are $(1,0)$ and $(0,2)$
because $m_{N}=n_{N}^{2}=N$ and
$\mathbb{V}[U_{N}]=N^{-1}(V^{(1,0)}+V^{(0,2)})$. In this case, one valid
choice of $\gamma(N)$ is $\gamma(N)=N$.

######  Example 3.

Suppose again that $(m_{N},n_{N})=(N,\sqrt{N})$, but this time
$V^{(0,1)}=V^{(0,2)}=V^{(1,0)}=0$. If $V^{(1,1)}\neq 0$ and $V^{(0,3)}\neq 0$,
then the principal degrees are $(1,1)$ and $(0,3)$ because
$m_{N}n_{N}=n_{N}^{3}=N^{3/2}$. In this case, one valid choice of $\gamma(N)$
is $\gamma(N)=N^{3/2}$.

In this asymptotic framework, there is no reason that $N^{d/2}$ is the right
normalization for the weak convergence of $U$-statistics. If the elements of
$((r_{\ell},c_{\ell}))_{1\leq\ell\leq L}$ are the principal degrees of
$U_{N}$, then there is a function $\gamma$ such that
$m_{N}^{-r_{\ell}}n_{N}^{-c_{\ell}}\gamma(N)\xrightarrow[N\rightarrow\infty]{}\alpha_{\ell}$,
where $\alpha_{\ell}>0$ for all $1\leq\ell\leq L$ and
$\gamma(N)\mathbb{V}[U_{N}]=\sum_{1\leq\ell\leq
L}\alpha_{\ell}V^{(r_{\ell},c_{\ell})}+o(1)$. Next, we state the equivalent
result to Theorem 3.2 in the new framework. The proof for this theorem is
given in E.1.

######  Theorem 3.6.

There is a random variable $W$ such that
$\sqrt{\gamma(N)}\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}\xrightarrow[]{\mathcal{D}}W$
if and only if
$\sqrt{\gamma(N)}(U_{N}-p^{\emptyset})\xrightarrow[]{\mathcal{D}}W$.

This theorem says that the limit distribution of $U_{N}-p^{\emptyset}$
renormalized by $\sqrt{\gamma(N)}$ is the same as that of its principal part
$\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}$, renormalized by the same
quantity. Therefore, similar as in the initial framework, we shall investigate
the asymptotic behavior of $U_{N}$ by studying its principal part.

In practice, one has to identify the principal part by finding the principal
degrees of $U_{N}$. The principal degrees depend both on the kernel $h$ and
the asymptotic behavior of $(m_{N},n_{N})$. After finding the principal
degrees, then a function $\gamma(N)$ can be found. With $\gamma(N)$ and the
principal degrees, the coefficients $\alpha_{\ell}$ can be calculated to yield
an expression for the variance. We will illustrate this in examples later.

Now, we derive the equivalent to Theorem 3.3, i.e. the convergence result when
the principal support graphs of $U_{N}$ are connected. The proof of this
theorem is given in Appendix E.2.

######  Theorem 3.7.

If all principal support graphs of $U_{N}$ are connected, then

$\sqrt{\gamma(N)}(U_{N}-p^{\emptyset})\xrightarrow[N\rightarrow\infty]{\mathcal{D}}\mathcal{N}(0,\sigma^{2}),$

where

$\sigma^{2}=\sum_{\ell=1}^{L}\alpha_{\ell}V^{(r_{\ell},c_{\ell})}.$

Unsurprisingly, this theorem states that the limit distribution for
$\sqrt{\gamma(N)}(U_{N}-p^{\emptyset})$ is still a Gaussian like in Theorem
3.3, but with a different expression for the variance. The new variance
consists of terms associated of the principal degrees of $U_{N}$, depending on
the behavior of $m_{N}$ and $n_{N}$.

##  4 Conclusion

In this paper, we have derived a new orthogonal decomposition for
$U$-statistics on RCE matrices, which can be used to characterize their
asymptotic behavior. This decomposition is defined with respect to a
decomposition of the probability space into orthogonal subspaces generated by
particular sets, called graph sets, of AHK variables. The asymptotic behavior
of a $U$-statistic is determined by its principal part, which consists of the
leading non-zero terms of the decomposition. The graphs associated to these
terms are called the principal support graphs.

Therefore, principal support graphs characterize the asymptotic behavior of
$U$-statistics. We have shown that the principal support graphs of a
$U$-statistic all have the same number of nodes, which defines the principal
degree. The principal degree of a $U$-statistic is equivalent to the degree of
degeneracy of usual $U$-statistics of i.i.d. variables, determining the rate
of convergence to their limit distribution. For that reason, degeneracy seems
to be a desirable property of $U$-statistics for statistical applications. For
data (here, an RCE matrix) of fixed size, a faster rate of convergence of
$U$-statistics as estimators leads to tighter confidence intervals, and
therefore, to more powerful tests.

However, the identification of the limit distributions in degenerate cases is
often tedious, even for $U$-statistics of i.i.d. random variables. In the case
of RCE matrices, we have shown that a simple assumption on the topology of
principal support graphs, connectedness, ensures that the limit distribution
is Gaussian. When this assumption holds, we obtain a simple limit
distribution, and furthermore, in degenerate cases, a rate of convergence
larger than $\sqrt{N}$. Whereas a similar result has been exhibited in [19],
this highlights a major difference with $U$-statistics of i.i.d. variables.
For the latter, there is no hope that the limit distributions are simple
Gaussians in degenerate cases. Instead, they are polynomials of Gaussians with
degree larger than one, with no straightforward expression [36, 25]. Future
studies may focus on identifying the limit distributions of $U$-statistics on
RCE matrices under different assumptions, when the principal support graphs do
not only have one, but several connected components, although we expect that
their form is more complex.

## Acknowledgements

The author thanks Sophie Donnet, François Massol and Stéphane Robin for many
fruitful discussions and insights. This work was funded by the grant
ANR-18-CE02-0010-01 of the French National Research Agency ANR (project
EcoNet) and a grant from Région Île-de-France.

##  Appendix A Proofs for Section 2.1

###### Proof of Proposition 2.1.

We show that for all $F$ and $F^{\prime}$ such that $F^{\prime}\subset F$, we
have that $\mathbb{E}[p^{F}(X)\mid H(F^{\prime})]=0$ by induction on $F$.
First, notice that $p^{\emptyset}(X)=\mathbb{E}[X]\in L_{2}^{*}(\emptyset)$
being the space of constant variables. Next, fix $F$ and suppose that the
induction hypothesis is true for all $\overline{F}\subset F$, i.e. for all
$\overline{F}$ and $F^{\prime}$ such that
$F^{\prime}\subseteq\overline{F}\subset F$, we have that
$\mathbb{E}[p^{\overline{F}}(X)\mid H(F^{\prime})]=0$. Now we can calculate
for all $F^{\prime}\subset F$,

$\begin{split}\mathbb{E}[p^{F}(X)\mid
H(F^{\prime})]&=\mathbb{E}[\mathbb{E}[X\mid H(F)]\mid
H(F^{\prime})]-\sum_{\overline{F}\subset F}\mathbb{E}[p^{\overline{F}}(X)\mid
H(F^{\prime})]\\\ &=\mathbb{E}[X\mid
H(F^{\prime})]-p^{F^{\prime}}(X)-\sum_{\begin{subarray}{c}\overline{F}\subset
F\\\ \overline{F}\neq
F^{\prime}\end{subarray}}\mathbb{E}[p^{\overline{F}}(X)\mid H(F^{\prime})]\\\
&=\sum_{\overline{F}\subset F^{\prime}}\mathbb{E}[p^{\overline{F}}(X)\mid
H(F^{\prime})]-\sum_{\begin{subarray}{c}\overline{F}\subset F\\\
\overline{F}\neq F^{\prime}\end{subarray}}\mathbb{E}[p^{\overline{F}}(X)\mid
H(F^{\prime})]\\\ &=-\sum_{\begin{subarray}{c}\overline{F}\subset F\\\
\overline{F}\not\subset
F^{\prime}\end{subarray}}\mathbb{E}[p^{\overline{F}}(X)\mid H(F^{\prime})]\\\
&=-\sum_{\begin{subarray}{c}\overline{F}\subset F\\\ \overline{F}\not\subset
F^{\prime}\end{subarray}}\mathbb{E}[p^{\overline{F}}(X)\mid
H(F^{\prime}\cap\overline{F})].\end{split}$

By the induction hypothesis, all the terms of this sum are equal to 0, which
concludes the proof by induction. ∎

##  Appendix B Proofs for Section 2.3

###### Proof of Proposition 2.3.

$\begin{split}\mathbb{V}[U_{m,n}]&=\sum_{(0,0)<(r,c)\leq(p,q)}\mathbb{V}[P^{r,c}_{m,n}]\\\
&=\sum_{(0,0)<(r,c)\leq(p,q)}\binom{m}{p}^{-2}\binom{n}{q}^{-2}\sum_{\begin{subarray}{c}\mathbf{i},\mathbf{i}^{\prime}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j},\mathbf{j}^{\prime}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{\begin{subarray}{c}G\subseteq
K_{\mathbf{i},\mathbf{j}},G^{\prime}\subseteq
K_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}\\\ (v_{1}(G),v_{2}(G))=(r,c)\\\
(v_{1}(G^{\prime}),v_{2}(G^{\prime}))=(r,c)\end{subarray}}\mathrm{Cov}(p^{G},p^{G^{\prime}})\\\
&=\sum_{(0,0)<(r,c)\leq(p,q)}\binom{m}{p}^{-1}\binom{n}{q}^{-1}\binom{m-r}{p-r}\binom{n-c}{q-c}r!\binom{p}{r}c!\binom{q}{c}\sum_{G\in\Gamma_{r,c}}\lvert\mathrm{Aut}(G)\rvert^{-1}\mathbb{V}[p^{G}]\\\
&=\sum_{(0,0)<(r,c)\leq(p,q)}\binom{m}{r}^{-1}\binom{n}{c}^{-1}r!\binom{p}{r}^{2}c!\binom{q}{c}^{2}\sum_{G\in\Gamma_{r,c}}\lvert\mathrm{Aut}(G)\rvert^{-1}\mathbb{E}[(p^{G})^{2}]\\\
&=\sum_{(0,0)<(r,c)\leq(p,q)}\frac{(m-r)!}{m!}\frac{(n-c)!}{n!}V^{(r,c)}\\\
\end{split}$

∎

###### Proof of Lemma 2.5.

Let $G\in\Gamma_{r,c}$.

$\begin{split}\mathbb{V}[\tilde{P}^{G}_{m,n}]&=\binom{m}{p}^{-2}\binom{n}{q}^{-2}\sum_{\begin{subarray}{c}\mathbf{i},\mathbf{i}^{\prime}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j},\mathbf{j}^{\prime}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\mathrm{Cov}(\tilde{p}^{G}_{\mathbf{i},\mathbf{j}},\tilde{p}^{G}_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}})\\\
&=\binom{m}{p}^{-2}\binom{n}{q}^{-2}\sum_{\begin{subarray}{c}\mathbf{i},\mathbf{i}^{\prime}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j},\mathbf{j}^{\prime}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{\Phi,\Phi^{\prime}\in\mathbb{S}_{p}\times\mathbb{S}_{q}}\mathrm{Cov}(p^{\Phi
G_{\mathbf{i},\mathbf{j}}},p^{\Phi^{\prime}G_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}})\\\
\end{split}$

where for all $(\mathbf{i},\mathbf{j})\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\times\mathcal{P}_{q}(\llbracket n\rrbracket)$,
$G_{\mathbf{i},\mathbf{j}}$ is any graph of $K_{\mathbf{i},\mathbf{j}}$ which
is isomorphic to $G$.

Now see that if $\Phi
G_{\mathbf{i},\mathbf{j}}\neq\Phi^{\prime}G_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}$,
then $\mathrm{Cov}(p^{\Phi
G_{\mathbf{i},\mathbf{j}}},p^{\Phi^{\prime}G_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}})=0$.
Otherwise $\Phi
G_{\mathbf{i},\mathbf{j}}=\Phi^{\prime}G_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}$,
then $\mathrm{Cov}(p^{\Phi
G_{\mathbf{i},\mathbf{j}}},p^{\Phi^{\prime}G_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}}})=\mathbb{V}[p^{G}]=\mathbb{E}[(p^{G})^{2}]$.
So, it follows that

$\mathbb{V}[\tilde{P}^{G}_{m,n}]=\binom{m}{p}^{-2}\binom{n}{q}^{-2}\sum_{\begin{subarray}{c}\mathbf{i},\mathbf{i}^{\prime}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j},\mathbf{j}^{\prime}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{\Phi,\Phi^{\prime}\in\mathbb{S}_{p}\times\mathbb{S}_{q}}\mathds{1}(\Phi
G_{\mathbf{i},\mathbf{j}}=\Phi^{\prime}G_{\mathbf{i}^{\prime},\mathbf{j}^{\prime}})\mathbb{E}[(p^{G})^{2}].$

Finally, applying Lemma 2.6, we have

$\begin{split}\mathbb{V}[\tilde{P}^{G}_{m,n}]&=\binom{m}{p}^{-2}\binom{n}{q}^{-2}\frac{m!(m-r)!}{(m-p)!^{2}}\frac{n!(n-c)!}{(n-q)!^{2}}\lvert\mathrm{Aut}(G)\rvert\mathbb{E}[(p^{G})^{2}]\\\
&=\frac{(m-r)!}{m!}\frac{(n-c)!}{n!}p!^{2}q!^{2}\rvert\mathrm{Aut}(G)\lvert\mathbb{E}[(p^{G})^{2}].\end{split}$

∎

###### Proof of Lemma 2.6.

First, fix $\mathbf{i}_{1},\mathbf{j}_{1},\Phi_{1}$. Write
$G^{1}:=\Phi_{1}G^{1}_{\mathbf{i}_{1},\mathbf{j}_{1}}$. We count the number of
picks for $\mathbf{i}_{2},\mathbf{j}_{2},\Phi_{2}$ such that
$\Phi_{2}G^{2}_{\mathbf{i}_{2},\mathbf{j}_{2}}=G^{1}$.

$\mathbf{i}_{2}$ and $\mathbf{j}_{2}$ must contain the $r$ row nodes and the
$c$ column nodes of $G^{1}$ and $\Phi_{2}$ must place these nodes in the same
order than in $G^{1}$, or belong to its automorphism group. This happens for
$\binom{m-r}{p-r}\binom{n-c}{q-c}$ picks for $(\mathbf{i}_{2},\mathbf{j}_{2})$
and for each, there are $(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert$ valid picks
for $\Phi_{2}$.

This happens for all $\binom{m}{p}\binom{n}{q}$ picks of
$(\mathbf{i}_{1},\mathbf{j}_{1})$ and $p!q!$ picks of $\Phi_{1}$. Therefore,

$\begin{split}\sum_{\begin{subarray}{c}\mathbf{i}_{1},\mathbf{i}_{2}\in\mathcal{P}_{p}(\llbracket
m\rrbracket)\\\ \mathbf{j}_{1},\mathbf{j}_{2}\in\mathcal{P}_{q}(\llbracket
n\rrbracket)\end{subarray}}\sum_{\Phi_{1},\Phi_{2}\in\mathbb{S}_{p}\times\mathbb{S}_{q}}&\mathds{1}(\Phi_{1}G^{1}_{\mathbf{i}_{1},\mathbf{j}_{1}}=\Phi_{2}G^{2}_{\mathbf{i}_{2},\mathbf{j}_{2}})\\\
&=\binom{m}{p}\binom{n}{q}\binom{m-r}{p-r}\binom{n-c}{q-c}p!q!(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert,\end{split}$

which develops to the form given by this lemma. ∎

##  Appendix C Proofs for Section 3.1

###### Proof of Theorem 3.2.

Since, $d-1$ is the order of degeneracy, we have $P^{r,c}_{N}=0$ for all
$(r,c)$ such that $r+c<d$. Therefore, we have
$U_{N}-p^{\emptyset}-\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}=\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c>d\end{subarray}}P^{r,c}_{N}$. So

$\begin{split}\mathbb{V}\left[N^{d/2}\left(U_{N}-p^{\emptyset}-\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}\right)\right]&=N^{d}\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c>d\end{subarray}}\mathbb{V}[P^{r,c}_{N}]\\\
&=N^{d}\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c>d\end{subarray}}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}.\\\
\end{split}$

But for all $(r,c)$, we have
$\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}=O(N^{-r-c})$, therefore

$\begin{split}\mathbb{V}\left[N^{d/2}\left(U_{N}-p^{\emptyset}-\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}\right)\right]&=N^{d}\times
O\left(\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c>d\end{subarray}}N^{-r-c}\right)\\\ &=N^{d}\times o(N^{-d})\\\
&=o(1).\end{split}$

Finally, this implies that
$N^{d/2}(U_{N}-p^{\emptyset})=N^{d/2}\sum_{\begin{subarray}{c}(0,0)\leq(r,c)\leq(p,q)\\\
r+c=d\end{subarray}}P^{r,c}_{N}+o_{P}(1)$, which proves the theorem. ∎

##  Appendix D Proofs for Section 3.2

###### Proof of Lemma 3.4.

For some $\ell\in\llbracket K\rrbracket$, denote
$G_{1:k}^{(-\ell)}=\cup_{\begin{subarray}{c}i=1\\\
i\neq\ell\end{subarray}}^{k}G_{i}$. We have

$\begin{split}\mathbb{E}[\prod_{k=1}^{K}p^{G_{k}}]&=\mathbb{E}[\mathbb{E}[\prod_{k=1}^{K}p^{G_{k}}\mid
H(G_{1:K}^{(-\ell)})]]\\\ &=\prod_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}^{K}p^{G_{k}}\mathbb{E}[\mathbb{E}[p^{G_{\ell}}\mid
H(G_{1:K}^{(-\ell)})]]\\\ &=\prod_{\begin{subarray}{c}k=1\\\
k\neq\ell\end{subarray}}^{K}p^{G_{k}}\mathbb{E}[\mathbb{E}[p^{G_{\ell}}\mid
H(G_{\ell}\cap G_{1:K}^{(-\ell)})]].\end{split}$

Suppose there is a vertex or edge of a $G_{\ell}$ that does not belong to any
other $G_{k}$, $k\neq\ell$. In this case, $G_{\ell}\cap
G_{1:K}^{(-\ell)}\subset G_{\ell}$, so $\mathbb{E}[p^{G_{\ell}}\mid
H(G_{\ell}\cap G_{1:K}^{(-\ell)})]=0$, which proves the first result.

From that result, if $\mathbb{E}[\prod_{k=1}^{K}p^{G_{k}}]\neq 0$ and no
vertex belongs to more than two of $G_{1},...,G_{K}$, then each vertex and
edge belong to exactly two of them. This also means that every connected
component must belong to exactly two of them. Therefore, if all graphs are
connected, then these graphs coincide in pairs. ∎

###### Proof of Lemma 3.5.

Let $a_{k}$ be nonnegative integers. For all
$(\mathbf{i},\mathbf{j})\in\mathcal{P}_{p}(\llbracket
m_{N}\rrbracket)\times\mathcal{P}_{q}(\llbracket n_{N}\rrbracket)$, let
$G_{k,\mathbf{i},\mathbf{j}}$ be a graph of $K_{\mathbf{i},\mathbf{j}}$ which
is isomorphic to $G_{k}$. Then

$\begin{split}\mathbb{E}\Big{[}\prod_{k=1}^{K}(&m_{N}^{r_{k}/2}n_{N}^{c_{k}/2}\tilde{P}^{G_{k}}_{N})^{a_{k}}\Big{]}\\\
&=m_{N}^{\sum_{k=1}^{K}a_{k}r_{k}/2}\binom{m_{N}}{p}^{-\sum_{k=1}^{K}a_{k}}n_{N}^{\sum_{k=1}^{K}a_{k}c_{k}/2}\binom{n_{N}}{q}^{-\sum_{k=1}^{K}a_{k}}\mathbb{E}\left[\prod_{k=1}^{K}\left(\sum_{\begin{subarray}{c}\mathbf{i}_{k}\in\mathcal{P}_{p}(\llbracket
m_{N}\rrbracket)\\\ \mathbf{j}_{k}\in\mathcal{P}_{q}(\llbracket
n_{N}\rrbracket)\end{subarray}}\tilde{p}^{G_{k}}_{\mathbf{i}_{k},\mathbf{j}_{k}}\right)^{a_{k}}\right],\end{split}$

where we can develop

$\begin{split}\mathbb{E}\left[\prod_{k=1}^{K}\left(\sum_{\begin{subarray}{c}\mathbf{i}_{k}\in\mathcal{P}_{p}(\llbracket
m_{N}\rrbracket)\\\ \mathbf{j}_{k}\in\mathcal{P}_{q}(\llbracket
n_{N}\rrbracket)\end{subarray}}\tilde{p}^{G_{k}}_{\mathbf{i}_{k},\mathbf{j}_{k}}\right)^{a_{k}}\right]&=\sum_{\begin{subarray}{c}\mathbf{i}^{\ell}_{k}\in\mathcal{P}_{p}(\llbracket
m_{N}\rrbracket)\\\ \mathbf{j}^{\ell}_{k}\in\mathcal{P}_{q}(\llbracket
n_{N}\rrbracket)\end{subarray}}\mathbb{E}\left[\prod_{k=1}^{K}\prod_{\ell=1}^{a_{k}}\tilde{p}^{G_{k}}_{\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}\right]\\\
&=\sum_{\begin{subarray}{c}\mathbf{i}^{\ell}_{k}\in\mathcal{P}_{p}(\llbracket
m_{N}\rrbracket)\\\ \mathbf{j}^{\ell}_{k}\in\mathcal{P}_{q}(\llbracket
n_{N}\rrbracket)\end{subarray}}\sum_{\Phi^{k}_{\ell}\in\mathbb{S}_{p}\times\mathbb{S}_{q}}\mathbb{E}\left[\prod_{k=1}^{K}\prod_{\ell=1}^{a_{k}}p^{\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}}\right].\\\
\end{split}$

Lemma 3.4 states that
$\mathbb{E}[\prod_{k=1}^{K}\prod_{\ell=1}^{a_{k}}p^{\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}}]\neq
0$ if and only if either all the
$\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}$ coincide in
pairs (and only in pairs), or no vertex appears in exactly one of these graphs
and at least one vertex appears in at least three.

In the second case, assume without loss of generality that a row node appears
in three graphs. Then
$G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})}:=\cup_{k=1}^{K}\cup_{j=1}^{a_{k}}\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}$
has $v_{1}(G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})})$ row nodes
and $v_{2}(G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})})$ column
nodes, where $\max r_{k}\leq
v_{1}(G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})})\leq\sum_{k=1}^{K}a_{k}r_{k}/2-1$
and $\max c_{k}\leq
v_{2}(G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})})\leq\sum_{k=1}^{K}a_{k}c_{k}/2-1$
(we have $\max r_{k}\leq\sum_{k=1}^{K}a_{k}r_{k}/2-1$ and $\max
c_{k}\leq\sum_{k=1}^{K}a_{k}c_{k}/2-1$, else
$\mathbb{E}[\prod_{k=1}^{K}\prod_{\ell=1}^{a_{k}}p^{\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}}]=0$).

Let $(\max r_{k},\max c_{k})\leq(r*,c*)\leq(p,q)$. Let us count the number of
terms of the sum such that
$v_{1}(G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})})=r^{*}$ and
$v_{2}(G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})})=c^{*}$. There
are exactly $\binom{m_{N}}{r^{*}}\binom{n_{N}}{c^{*}}$ ways to pick $r^{*}$
row nodes and $c^{*}$ nodes for
$G^{*}_{(\mathbf{i}^{\ell}_{k}),(\mathbf{j}^{\ell}_{k})}$. Now, for a specific
set of $r^{*}$ row nodes and $c^{*}$ column nodes, for each $1\leq k\leq K$,
$1\leq\ell\leq a_{k}$, there are
$\binom{r^{*}}{r_{k}}\binom{c^{*}}{c_{k}}\binom{m_{N}-r^{*}}{p-r_{k}}\binom{n_{N}-c^{*}}{q-c_{k}}$
ways to pick $(\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k})$ such that the
nodes of $G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}$ are contained in
the $r^{*}$ specific row nodes and $c^{*}$ specific column nodes. Therefore,
there are at most
$p!q!\binom{r^{*}}{r_{k}}\binom{c^{*}}{c_{k}}\binom{m_{N}-r^{*}}{p-r_{k}}\binom{n_{N}-c^{*}}{q-c_{k}}$
picks for $(\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k})$ and
$\Phi_{k}^{\ell}$. Finally, the number of terms is smaller than

$\begin{split}B^{r^{*},c^{*}}_{N}&:=\binom{m_{N}}{r^{*}}\binom{n_{N}}{c^{*}}\prod_{k=1}^{K}\prod_{\ell=1}^{a_{k}}p!q!\binom{r^{*}}{r_{k}}\binom{m_{N}-r^{*}}{p-r_{k}}\binom{n_{N}-c^{*}}{q-c_{k}}\\\
&=\binom{m_{N}}{r^{*}}\binom{n_{N}}{c^{*}}\prod_{k=1}^{K}\left[p!q!\binom{r^{*}}{r_{k}}\binom{m_{N}-r^{*}}{p-r_{k}}\binom{n_{N}-c^{*}}{q-c_{k}}\right]^{a_{k}}\\\
&=O\left(m_{N}^{r^{*}}n_{N}^{c^{*}}\prod_{k=1}^{K}\left[m_{N}^{p-r_{k}}n_{N}^{q-c_{k}}\right]^{a_{k}}\right)\\\
&=O\left(m_{N}^{r^{*}+\sum_{k=1}^{K}a_{k}(p-r_{k})}n_{N}^{c^{*}+\sum_{k=1}^{K}a_{k}(q-c_{k})}\right).\\\
\end{split}$

The total number of these terms is

$\begin{split}B_{N}&\leq\sum_{(\max r_{k},\max
c_{k})\leq(r^{*},c^{*})\leq(\sum_{k=1}^{K}a_{k}r_{k}/2-1,\sum_{k=1}^{K}a_{k}c_{k}/2)}B^{r^{*},c^{*}}_{N}\\\
&=O(B^{\sum_{k=1}^{K}a_{k}r_{k}/2-1,\sum_{k=1}^{K}a_{k}c_{k}/2}_{N})\\\
&=O\left(m_{N}^{\sum_{k=1}^{K}a_{k}(p-r_{k}/2)-1}n_{N}^{\sum_{k=1}^{K}a_{k}(q-c_{k}/2)}\right)\\\
&=o\left(m_{N}^{\sum_{k=1}^{K}a_{k}(p-r_{k}/2)}n_{N}^{\sum_{k=1}^{K}a_{k}(q-c_{k}/2)}\right).\end{split}$

We notice that the contribution of these terms are $o(1)$ in equation (D).

Now, there remains the terms of the first case, where the
$\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}$ coincide in
pairs. Note that since the $G_{k}$ are non-isomorphic, only graphs arising for
the permutations of a same graph $G_{k}$ can coincide. Therefore, the $a_{k}$
are necessarily even. Furthermore, for each $k$, there are $a_{k}/2$ different
pairs of coinciding graphs
$\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}$. There are
$\frac{a_{k}!}{2^{a_{k}/2}(a_{k}/2)!}$ ways to partition a set of $a_{k}$
graphs into $a_{k}/2$ pairs.

Fix $k,\ell_{1},\ell_{2}$. The number of picks for
$\mathbf{i}^{\ell_{1}}_{k},\mathbf{j}^{\ell_{1}}_{k},\mathbf{i}^{\ell_{2}}_{k},\mathbf{j}^{\ell_{2}}_{k},\Phi^{\ell_{1}},\Phi^{\ell_{2}}$
such that
$\Phi^{\ell_{1}}_{k}G_{k,\mathbf{i}^{\ell_{1}}_{k},\mathbf{j}^{\ell_{1}}_{k}}=\Phi^{\ell_{2}}_{k}G_{k,\mathbf{i}^{\ell_{2}}_{k},\mathbf{j}^{\ell_{2}}_{k}}$
is given by Lemma 2.6. Accounting for all $a_{k}/2$ pairs of the type
$(\ell_{1},\ell_{2})$, there are

$\frac{m_{N}!(m_{N}-r_{k})!}{(m_{N}-p)!^{2}}\frac{n_{N}!(n_{N}-c_{k})!}{(n_{N}-q)!^{2}}\lvert\mathrm{Aut}(G)\rvert.$

Therefore, taking into account the number of possible pairings and the picks
for all $1\leq k\leq K$, $1\leq\ell\leq a_{k}$, there are

$\begin{split}A_{N}&=\prod_{k=1}^{K}\frac{a_{k}!}{2^{a_{k}/2}(a_{k}/2)!}\left(\frac{m_{N}!(m_{N}-r_{k})!}{(m_{N}-p)!^{2}}\frac{n_{N}!(n_{N}-c_{k})!}{(n_{N}-q)!^{2}}\lvert\mathrm{Aut}(G_{k})\rvert\right)^{a_{k}/2}\\\
&=m_{N}^{\sum_{k=1}^{K}a_{k}(r_{k}/2-p)}n_{N}^{\sum_{k=1}^{K}a_{k}(c_{k}/2-q)}\prod_{k=1}^{K}\frac{a_{k}!}{2^{a_{k}/2}(a_{k}/2)!}\lvert\mathrm{Aut}(G_{k})\rvert^{a_{k}/2}\\\
&\quad+o\left(m_{N}^{\sum_{k=1}^{K}a_{k}(r_{k}/2-p)}n_{N}^{\sum_{k=1}^{K}a_{k}(c_{k}/2-q)}\right).\\\
\end{split}$

Each of these $A_{N}$ terms is equal to
$\mathbb{E}\left[\prod_{k=1}^{K}\prod_{\ell=1}^{a_{k}}p^{\Phi^{\ell}_{k}G_{k,\mathbf{i}^{\ell}_{k},\mathbf{j}^{\ell}_{k}}}\right]=\prod_{k=1}^{K}\mathbb{E}[(p^{G_{k}})^{2}]^{a_{k}/2}$.

In conclusion, if all the $a_{k}$ are even, then

$\begin{split}\mathbb{E}\left[\prod_{k=1}^{K}(m_{N}^{r_{k}/2}n_{N}^{c_{k}/2}\tilde{P}^{G_{k}}_{N})^{a_{k}}\right]&=m_{N}^{\sum_{k=1}^{K}a_{k}r_{k}/2}\binom{m_{N}}{p}^{-\sum_{k=1}^{K}a_{k}}n_{N}^{\sum_{k=1}^{K}a_{k}c_{k}/2}\binom{n_{N}}{q}^{-\sum_{k=1}^{K}a_{k}}\\\
&\quad\times A_{N}\prod_{k=1}^{K}\mathbb{E}[(p^{G_{k}})^{2}]^{a_{k}/2}\\\
&=(p!q!)^{\sum_{k=1}^{K}a_{k}}\prod_{k=1}^{K}\frac{a_{k}!}{2^{a_{k}/2}(a_{k}/2)!}\lvert\mathrm{Aut}(G_{k})\rvert^{a_{k}/2}\mathbb{E}[(p^{G_{k}})^{2}]^{a_{k}/2}\\\
&=\prod_{k=1}^{K}\frac{a_{k}!}{2^{a_{k}/2}(a_{k}/2)!}\left(p!^{2}q!^{2}\lvert\mathrm{Aut}(G_{k})\rvert\mathbb{E}[(p^{G_{k}})^{2}]\right)^{a_{k}/2},\end{split}$

and in the general case,

$\begin{split}\mathbb{E}\Big{[}\prod_{k=1}^{K}(&m_{N}^{r_{k}/2}n_{N}^{c_{k}/2}\tilde{P}^{G_{k}}_{N})^{a_{k}}\Big{]}\\\
&=\begin{cases}\prod_{k=1}^{K}\frac{a_{k}!}{2^{a_{k}/2}(a_{k}/2)!}\left(p!^{2}q!^{2}\lvert\mathrm{Aut}(G_{k})\rvert\mathbb{E}[(p^{G_{k}})^{2}]\right)^{a_{k}/2}&\text{if
all $a_{k}$ are even,}\\\ 0&\text{if at least one $a_{k}$ is
odd.}\end{cases}\end{split}$ (8)

Else, if there is at least one odd $a_{k}$, we have
$\mathbb{E}[\prod_{k=1}^{K}(m_{N}^{r_{k}/2}n_{N}^{c_{k}/2}\tilde{P}^{G_{k}}_{N})^{a_{k}}]=0$.

We remind that the moment of order $a$ of a gaussian variable $X$ with mean
$0$ and variance $\sigma^{2}$ is

$\mathbb{E}[X^{a}]=\begin{cases}\frac{a!}{2^{a/2}(a/2)!}\sigma^{a}&\text{if
$a$ is even,}\\\ 0&\text{if $a$ is odd.}\\\ \end{cases}$

So the application of the methods of moments to equation (8) concludes the
proof of this lemma. ∎

##  Appendix E Proofs for Section 3.3

###  E.1 Proof of Theorem 3.6

In order to prove Theorem 3.6, define
$\mathcal{S}=\\{(r_{\ell},c_{\ell}):1\leq\ell\leq L\\}$ the set of principal
degrees of $h$. We may define $\mathcal{S}_{0}$ the set of couples
$(0,0)<(r_{0},c_{0})\leq(p,q)$ such that
$\gamma(N)^{-1}=o(m_{N}^{-r_{0}}n_{N}^{-c_{0}})$, for any
$(r,c)\in\mathcal{S}$. We may also define $\mathcal{S}_{+}$, the set of
couples $(0,0)<(r_{+},c_{+})\leq(p,q)$ such that
$m_{N}^{-r_{+}}n_{N}^{-c_{+}}=o(\gamma(N)^{-1})$, for any
$(r,c)\in\mathcal{S}$. We need the following lemma.

######  Lemma E.1.

For all $(r,c)\in\mathcal{S}_{0}$, for all graphs $G$ such that
$(v_{1}(G),v_{2}(G))=(r,c)$, we have $p^{G}=0$.

###### Proof.

We have

$\begin{split}\mathbb{V}[U_{N}]&=\sum_{(0,0)<(r,c)\leq(p,q)}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}\\\
&=\sum_{(r,c)\in\mathcal{S}_{0}}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}+\sum_{(r,c)\in\mathcal{S}}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}\\\
&\quad+\sum_{(r,c)\in\mathcal{S}_{+}}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}.\end{split}$

By definition, $(r,c)\in\mathcal{S}_{+}$,
$m_{N}^{-r}n_{N}^{-c}=o(\gamma(N)^{-1})$ and

$\mathbb{V}[U_{N}]=\gamma(N)^{-1}\sum_{1\leq\ell\leq
L}\alpha_{\ell}V^{(r_{\ell},c_{\ell})}+o(\gamma(N)^{-1}).$

Therefore,

$\begin{split}\sum_{(r,c)\in\mathcal{S}_{0}}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}&=\sum_{l=1}^{L}\left(\frac{\alpha_{\ell}}{\gamma(N)}-\frac{(m_{N}-r_{\ell})!}{m_{N}!}\frac{(n_{N}-c_{\ell})!}{n_{N}!}\right)V^{(r_{\ell},c_{\ell})}+o(\gamma(N)^{-1}).\end{split}$

Again, by definition, we have for all $1\leq\ell\leq L$,
$\gamma(N)\frac{(m_{N}-r_{\ell})!}{m_{N}!}\frac{(n_{N}-c_{\ell})!}{n_{N}!}\xrightarrow[N\rightarrow\infty]{}\alpha_{\ell}$.
Therefore, the previous equation yields

$\begin{split}\gamma(N)\sum_{(r,c)\in\mathcal{S}_{0}}\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}V^{(r,c)}=o(1).\end{split}$

But for all $(r,c)\in\mathcal{S}_{0}$,
$\gamma(N)\frac{(m_{N}-r)!}{m_{N}!}\frac{(n_{N}-c)!}{n_{N}!}\xrightarrow[N\rightarrow\infty]{}\infty$.
Since $V^{(r,c)}\geq 0$ for all $(0,0)\leq(r,c)\leq(p,q)$, this means that for
all $(r,c)\in\mathcal{S}_{0}$, we have $V^{(r,c)}=0$. Thus,

$V^{(r,c)}=\frac{p!}{(p-r)!}\frac{q!}{(q-r)!}\sum_{G\in\Gamma_{r,c}}\lvert\mathrm{Aut}(G)\rvert^{-1}\mathbb{V}[p^{G}],$

this means $\mathbb{V}[p^{G}]=0$ for all $G\in\Gamma_{r,c}$.

Finally, let $G$ be any graph such that $(v_{1}(G),v_{2}(G))=(r,c)$. Then
there exists a graph $G^{*}\in\Gamma_{r,c}$ such that
$\mathbb{V}[p^{G}]=\mathbb{V}[p^{G^{*}}]$. We have already shown that
$\mathbb{V}[p^{G^{*}}]=0$ for all $(r,c)\in\mathcal{S}_{0}$, so adding the
fact that $\mathbb{E}[p^{G}]=0$ for all graphs $G\neq\emptyset$, it means that
$p^{G}=0$, for all graphs $G$ such that
$(v_{1}(G),v_{2}(G))=(r,c)\in\mathcal{S}_{0}$.

∎

###### Proof of Theorem 3.6.

$\sqrt{\gamma(N)}\left[U_{N}-p^{\emptyset}-\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}\right]=\sqrt{\gamma(N)}\left[\sum_{(r,c)\in\mathcal{S}_{0}}P^{r,c}_{N}+\sum_{(r,c)\in\mathcal{S}_{+}}P^{r,c}_{N}\right].$

By Lemma E.1, $P^{r,c}_{N}=0$ for all $(r,c)\in\mathcal{S}_{0}$.

$\begin{split}\mathbb{V}\left[\sqrt{\gamma(N)}\sum_{(r,c)\in\mathcal{S}_{+}}P^{r,c}_{N}\right]&=\gamma(N)\sum_{(r,c)\in\mathcal{S}_{+}}\frac{(m-r)!}{m!}\frac{(n-c)!}{n!}V^{(r,c)}\\\
&=o(1).\end{split}$

That means
$\sqrt{\gamma(N)}(U_{N}-p^{\emptyset})=\sqrt{\gamma(N)}\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}+o_{P}(1)$,
which concludes the proof. ∎

###  E.2 Proof of Theorem 3.7

###### Proof.

Theorem 3.6 states that $\sqrt{\gamma(N)}(U_{N}-p^{\emptyset})$ has the same
limit as $\sqrt{\gamma(N)}\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}$.

For all $(0,0)<(r,c)\leq(p,q)$,

$P^{r,c}_{N}=\sum_{G\in\Gamma_{r,c}}\frac{1}{(p-r)!(q-c)!\lvert\mathrm{Aut}(G)\rvert}\tilde{P}^{G}_{N}.$

So

$\sqrt{\gamma(N)}\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}=\sum_{\ell=1}^{L}\sqrt{\gamma(N)}m_{N}^{-r_{\ell}/2}n_{N}^{-c_{\ell}/2}\sum_{G\in\Gamma_{r_{\ell},c_{\ell}}}\frac{m_{N}^{r_{\ell}/2}n_{N}^{c_{\ell}/2}\tilde{P}^{G}_{N}}{(p-r_{\ell})!(q-c_{\ell})!\lvert\mathrm{Aut}(G)\rvert}.$

By definition,
$\gamma(N)m_{N}^{-r_{\ell}}n_{N}^{-c_{\ell}}\xrightarrow[N\rightarrow\infty]{}\alpha_{\ell}$.
Therefore, by Lemma 3.5,
$\sqrt{\gamma(N)}\sum_{\ell=1}^{L}P^{r_{\ell},c_{\ell}}_{N}$ converges in
distribution to
$Z=\sum_{\ell=1}^{L}\sqrt{\alpha_{\ell}}\sum_{G\in\Gamma_{r_{\ell},c_{\ell}}}W_{G}$,
where all $W_{G}$ are independent gaussian variables with mean $0$ and
variance
$\frac{(p!)^{2}(q!)^{2}}{((p-r_{\ell})!)^{2}((q-c_{\ell})!)^{2}\lvert\mathrm{Aut}(G)\rvert}\mathbb{V}[p^{G}]$.

Finally, it follows that $Z$ is a gaussian variable with mean $0$ and variance
$\sum_{\ell=1}^{L}\sqrt{\alpha_{\ell}}V^{(r_{\ell},c_{\ell})}$ where

$V^{(r_{\ell},c_{\ell})}=\sum_{G\in\Gamma_{r_{\ell},c_{\ell}}}\frac{(p!)^{2}(q!)^{2}}{((p-r_{\ell})!)^{2}((q-c_{\ell})!)^{2}\lvert\mathrm{Aut}(G)\rvert}\mathbb{V}[p^{G}]$

∎

## References

  * [1] David J Aldous.  Representations for partially exchangeable arrays of random variables.  Journal of Multivariate Analysis, 11(4):581–598, 1981.
  * [2] Nick J Baker, Riikka Kaartinen, Tomas Roslin, and Daniel B Stouffer.  Species’ roles in food webs show fidelity across a highly variable oak forest.  Ecography, 38(2):130–139, 2015.
  * [3] Jordi Bascompte and Carlos J Melián.  Simple trophic modules for complex food webs.  Ecology, 86(11):2868–2873, 2005.
  * [4] Peter S Bearman, James Moody, and Katherine Stovel.  Chains of affection: The structure of adolescent romantic and sexual networks.  American journal of sociology, 110(1):44–91, 2004.
  * [5] Bhaswar B Bhattacharya, Anirban Chatterjee, and Svante Janson.  Fluctuations of subgraph counts in graphon based random graphs.  Combinatorics, Probability and Computing, 32(3):428–464, 2023.
  * [6] Sharmodeep Bhattacharyya and Peter J Bickel.  Subsampling bootstrap of count features of networks.  The Annals of Statistics, 43(6):2384–2411, 2015.
  * [7] Peter J Bickel, Aiyou Chen, and Elizaveta Levina.  The method of moments and degree distributions for network models.  The Annals of Statistics, 39(5):2280–2301, 2011.
  * [8] Sarvenaz Choobdar, Pedro Ribeiro, Sylwia Bugla, and Fernando Silva.  Comparison of co-authorship networks across scientific fields using motifs.  In 2012 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 147–152. IEEE, 2012.
  * [9] Matthew Coulson, Robert E Gaunt, and Gesine Reinert.  Poisson approximation of subgraph counts in stochastic block models and a graphon model.  ESAIM: Probability and Statistics, 20:131–142, 2016.
  * [10] Persi Diaconis and Svante Janson.  Graph limits and exchangeable random graphs.  Rendiconti di Matematica e delle sue Applicazioni. Serie VII, 28(1):33–61, 2008.
  * [11] Carsten F Dormann, Jochen Fründ, Nico Blüthgen, and Bernd Gruber.  Indices, graphs and null models: analyzing bipartite ecological networks.  The Open Ecology Journal, 2(1), 2009.
  * [12] Alexandra Duma and Alexandru Topirceanu.  A network motif based approach for classifying online social networks.  In 2014 IEEE 9th IEEE International Symposium on Applied Computational Intelligence and Informatics (SACI), pages 311–315. IEEE, 2014.
  * [13] Katherine Faust.  Comparing social networks: size, density, and local structure.  Advances in Methodology and Statistics, 3(2):185–216, 2006.
  * [14] Chao Gao and John Lafferty.  Testing network structure using relations between small subgraph probabilities.  arXiv preprint arXiv:1704.06742, 2017.
  * [15] Gérard Govaert and Mohamed Nadif.  Clustering with block mixture models.  Pattern Recognition, 36(2):463–473, 2003.
  * [16] Wassily Hoeffding.  A class of statistics with asymptotically normal distribution.  The Annals of Mathematical Statistics, 19(3):293–325, 1948.
  * [17] Wassily Hoeffding.  The strong law of large numbers for $U$-statistics.  Technical report, North Carolina State University. Dept. of Statistics, 1961.
  * [18] Douglas N Hoover.  Relations on probability spaces and arrays of random variables.  Preprint, Institute for Advanced Study, Princeton, NJ, 2:275, 1979.
  * [19] Svante Janson and Krzysztof Nowicki.  The asymptotic distributions of generalized $u$-statistics with applications to random graphs.  Probability theory and related fields, 90:341–375, 1991.
  * [20] Olav Kallenberg.  Probabilistic symmetries and invariance principles, volume 9.  Springer, 2005.
  * [21] Gursharn Kaur and Adrian Röllin.  Higher-order fluctuations in dense random graph models.  Electronic Journal of Probability, 26:1–36, 2021.
  * [22] Jose B Lanuza, Alfonso Allen-Perkins, and Ignasi Bartomeus.  The non-random assembly of network motifs in plant–pollinator networks.  Journal of Animal Ecology, 92(3):760–773, 2023.
  * [23] Tâm Le Minh.  U-statistics on bipartite exchangeable networks.  ESAIM: Probability and Statistics, 27:576–620, 2023.
  * [24] Tâm Le Minh, Sophie Donnet, François Massol, and Stéphane Robin.  Hoeffding-type decomposition for $u$-statistics on bipartite networks.  arXiv preprint arXiv:2308.14518, 2023.
  * [25] A J Lee.  U-statistics: Theory and Practice.  Routledge, 1990.
  * [26] Keith Levin and Elizaveta Levina.  Bootstrapping networks with latent space structure.  arXiv preprint arXiv:1907.10821, 2019.
  * [27] László Lovász and Balázs Szegedy.  Limits of dense graph sequences.  Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006.
  * [28] P-AG Maugis, SC Olhede, CE Priebe, and PJ Wolfe.  Testing for equivalence of network distribution using subgraph counts.  Journal of Computational and Graphical Statistics, 29(3):455–465, 2020.
  * [29] Zacharie Naulet, Daniel M Roy, Ekansh Sharma, and Victor Veitch.  Bootstrap estimators for the tail-index and for the count statistics of graphex processes.  Electronic Journal of Statistics, 15:282–325, 2021.
  * [30] Mark EJ Newman.  The structure of scientific collaboration networks.  Proceedings of the national academy of sciences, 98(2):404–409, 2001.
  * [31] Sarah Ouadah, Pierre Latouche, and Stéphane Robin.  Motif-based tests for bipartite networks.  Electronic Journal of Statistics, 16(1):293–330, 2022.
  * [32] Franck Picard, J-J Daudin, Michel Koskas, Sophie Schbath, and Stephane Robin.  Assessing the exceptionality of network motifs.  Journal of Computational Biology, 15(1):1–20, 2008.
  * [33] Natasa Pržulj, Derek G Corneil, and Igor Jurisica.  Modeling interactome: scale-free or geometric?  Bioinformatics, 20(18):3508–3515, 2004.
  * [34] Teresa M Przytycka.  An important connection between network motifs and parsimony models.  In Annual International Conference on Research in Computational Molecular Biology, pages 321–335. Springer, 2006.
  * [35] Gesine Reinert and Adrian Röllin.  Random subgraph counts and u-statistics: multivariate normal approximation via exchangeable pairs and embedding.  Journal of applied probability, 47(2):378–393, 2010.
  * [36] Herman Rubin and RA Vitale.  Asymptotic distribution of symmetric statistics.  The Annals of Statistics, pages 165–170, 1980.
  * [37] Shai S Shen-Orr, Ron Milo, Shmoolik Mangan, and Uri Alon.  Network motifs in the transcriptional regulation network of escherichia coli.  Nature genetics, 31(1):64–68, 2002.
  * [38] Tom AB Snijders and Krzysztof Nowicki.  Estimation and prediction for stochastic blockmodels for graphs with latent block structure.  Journal of classification, 14(1):75–100, 1997.
  * [39] Dudley Stark.  Compound poisson approximations of subgraph counts in random graphs.  Random Structures & Algorithms, 18(1):39–60, 2001.
  * [40] Daniel B Stouffer, Juan Camacho, Wenxin Jiang, and Luís A Nunes Amaral.  Evidence for the existence of a robust pattern of prey selection in food webs.  Proceedings of the Royal Society B: Biological Sciences, 274(1621):1931–1940, 2007.
  * [41] Tao Zhou, Jie Ren, Matúš Medo, and Yi-Cheng Zhang.  Bipartite network projection and personal recommendation.  Physical review E, 76(4):046115, 2007.