Low-degree lower bounds via almost orthonormal bases

Alexandra Carpentier,* Simone Maria Giancola,† Christophe Giraud‡ and Nicolas Verzelen§

Abstract

Low-degree polynomials have emerged as a powerful paradigm for providing evidence of statistical-
computational gaps across a variety of high-dimensional statistical models [Wei25]. For detection prob-
lems — where the goal is to test a planted distribution $\mathbb{P}'$ against a null distribution $\mathbb{P}$ with independent
components — the standard approach is to bound the advantage using an $L^2(\mathbb{P})$-orthonormal family of
polynomials. However, this method breaks down for estimation tasks or more complex testing problems
where $\mathbb{P}$ has some planted structure, so that no simple $L^2(\mathbb{P})$-orthogonal polynomial family is available.
To address this challenge, several technical workarounds have been proposed [SW22; SW25], though their
implementation can be delicate.

In this work, we propose a more direct proof strategy. Focusing on random graph models, we construct a basis of polynomials that is almost orthonormal under $\mathbb{P}$, in precisely those regimes where statistical-computational gaps arise. This almost orthonormal basis not only yields a direct route to establishing low-degree lower bounds, but also allows us to explicitly identify the polynomials that optimize the low-degree criterion. This, in turn, provides insights into the design of optimal polynomial-time algorithms. We illustrate the effectiveness of our approach by recovering known low-degree lower bounds, and establishing new ones for problems such as hidden subcliques, stochastic block models, and seriation models.

# 1 Introduction

In high-dimensional statistics, a central objective is to design computationally efficient estimation — or
test — procedures that achieve the best possible statistical performance. However, in many fundamen-
tal problems — such as sparse PCA, planted clique, or clustering — the best known polynomial-time
algorithms fail to attain the performance that is provably achievable by the optimal estimators. This
gap between the information-theoretic optimum and the best polynomial-time performance, known as a
statistical-computational gap, has been conjectured to occur broadly. From this perspective, the perfor-
mance of an efficient algorithm should be compared not to the information-theoretic optimum, but to the
best achievable by any polynomial-time method, leading naturally to the problem of proving lower bounds for
polynomial-time algorithms. Since statistical problems involve random instances, classical worst-case com-
plexity classes ($P, NP, \text{etc.}$) are not well suited for characterizing hardness. Instead, computational lower
bounds are typically established within specific models of computation, such as the sum-of-squares (SoS)
hierarchy [Hop+17; Bar+19], the overlap gap property [Gam21], the statistical query framework [Kea98;
Bre+21], and the low-degree polynomial model [Hop18; KWB19; SW22], sometimes in combination with
reductions between statistical problems [BB20; BR13; BBH18].

Among these, low-degree polynomial (LD) lower bounds have recently emerged as a powerful tool for
establishing state-of-the-art computational lower bounds in a variety of detection problems — including
community detection [HS17], spiked tensor models [HS17; KWB19], sparse PCA [Din+24] among oth-
ers — and estimation problems — including submatrix estimation [SW22], stochastic block models and
graphons [LG24; SW25], dense cycle recovery [MWZ23], and planted coloring [Kot+23] — see [Wei25] for a
recent survey. In the LD framework, we restrict our attention to estimators — or test statistics — that are

<footnote>*Institut für Mathematik — Universität Potsdam, Potsdam, Germany. Alexandra.Carpentier@uni-potsdam.de</footnote>

<footnote>†Laboratoire de Mathématiques d'Orsay, Université Paris - Saclay, CNRS, France. simonegiancola09@gmail.com</footnote>

<footnote>‡Laboratoire de Mathématiques d'Orsay, Université Paris - Saclay, CNRS, France. Christophe.Giraud@universite-paris-saclay.fr</footnote>

<footnote>§INRAE, Institut Agro, MISTEA, Univ. Montpellier, France. Nicolas.Verzelen@inrae.fr</footnote>
multivariate polynomials of degree at most *D* in the observations. The central conjecture in the LD literature is that, for many problems, degree-*O*(log *n*) polynomials are as powerful as any polynomial-time algorithm. Consequently, proving failure for all degree-*O*(log *n*) polynomials provides strong evidence [KWB19] of polynomial-time hardness. The LD framework connects to several other computational models, including statistical queries [Bre+21], free energy landscapes from statistical physics [Ban+22], and approximate message passing [MW25].

In this work, we consider testing and estimation problems on random graph models with latent structure. We observe an undirected graph with *n* nodes, encoded in the adjacency matrix $Y^* = (Y_{ij}^*)_{1\le i<j\le n} \in \mathbb{R}^{n(n-1)/2}$, where $Y_{ij}^*$ equals 1 when there is an edge between *i* and *j*, and 0 otherwise. We consider a latent structure model, where for some $q \in (0, 1)$, some symmetric matrix $\Theta \in \mathbb{R}^{n(n-1)/2}$, and some unobserved latent assignment $z \in [n]^n$, the $Y_{ij}^*$s are sampled independently conditionally on *z*, with conditional distribution

$$ \mathbb{P}[Y_{ij}^* = 1|z] = q + \Theta_{z_i z_j}; \quad \mathbb{P}[Y_{ij}^* = 0|z] = 1 - q - \Theta_{z_i z_j}. \qquad (1) $$

It is more standard to consider the matrix $\Theta^*$ defined by $\Theta_{ij}^* = q + \Theta_{ij}$ for $i \neq j$, but the parametrization with $\Theta$ will be more convenient for our purpose. We consider two different sampling schemes for this latent assignment vector *z*:

**Condition 1 (Independent sampling).** For $i = 1, \dots, n$, the $z_i$'s are sampled uniformly on $[n]$.

**Condition 2 (Permutation sampling).** The vector $z = (z_i)_{1=1, \dots, n}$ is distributed as the uniform permutation over $[n]$.

Under Permutation Sampling, $\mathbb{E}[Y^*|z]$ is distributed as a random permutation of $\Theta^*$ whereas, under Independent-Sampling, $\mathbb{E}[Y^*|z]$ corresponds to some sampling with replacement of $\Theta^*$. Importantly, the distribution of $Y^*$ is permutation-invariant in both cases. This model encompasses three classical random graph models that depend on some parameter $\lambda \in [0, 1-q]$ and some integer $k \in [n]$.

(HS) **Hidden subclique** Set $\Theta_{ij} = \lambda 1\{i \le k\} 1\{j \le k\}$. When two nodes belong to the hidden subclique (that is $z_i \le k$), then the connection probability equals $\lambda + q$. Under Independent-Sampling, each node belongs to the hidden subclique with probability $k/n$, whereas, under Permutation Sampling, the size of the hidden subclique is exactly *k*. We refer to the former model as (HS-I), and to the latter as (HS-P).

(SBM) **Stochastic Block Models.** Assume that $n/k$ is an integer. Then, we set $\Theta_{ij} = \lambda 1\{\lceil \frac{j}{k} \rceil = \lceil \frac{i}{k} \rceil\}$, where $\lceil x \rceil$ stands for the upper integer part. Under Independent-Sampling (SBM-I), $Y^*$ is sampled as a SBM with $K = n/k$ groups with random size. Under Permutation Sampling (SBM-P), $Y^*$ is sampled as a SBM with $K = n/k$ groups of size exactly *k*.

(TS) **Tœplitz Seriation.** For simplicity assume that *k* is even. We have $\Theta_{ij} = \lambda 1_{|i-j| \le k/2}$, where the label $z \in [n]^n$ is either sampled uniformly at random in $[n]^n$ (TS-I), or is sampled uniformly in the set of permutations (TS-P).

## Our contributions.

1. We present a novel approach for proving low-degree lower bounds for testing and estimation in random graph models with planted structure. Our method relies on constructing a new basis of low-degree polynomials invariant under vertex relabelling, which is almost orthonormal when the planted structure (i.e. $\Theta$) is small. Typically, this property holds as long as the signal is weak enough to prevent non-trivial recovery using degree-log(*n*) polynomials. The technique offers a simpler systematic framework for proving low-degree bounds, particularly effective when the latent vector *z* is not i.i.d., thereby opening the door to addressing previously unsolved and challenging settings. An additional advantage of this framework is that it allows us to explicitly identify the polynomials that optimize the low-degree criterion, providing insights for the design of optimal polynomial-time algorithms — see open problem #6 in [Wei25].
2. We establish two new low-degree lower bounds for testing and estimation in the general model (1), covering the three models (HS), (SBM), and (TS). These bounds yield new results for testing between different planted structures in these three models, as well as new results for estimation in the (TS-I), (TS-P), (HS-P) and (SBM-P) models. We also recover several known results for (HS-I) and (SBM-I), up to logarithmic factors. Note that in this paper, we throughout assume that $|\Theta|_{\infty}$ is of smaller order than $q$ up to a polynomial in $D$, which is not necessary, but which simplifies significantly our analysis as we want to have a generic analysis for all models.

**A glimpse at our technique for deriving LD bounds.** We now give a brief overview of our approach for deriving LD bounds; full details appear in Section 3. To simplify the forthcoming analysis, from now on, we work with the centered adjacency matrix $Y$ defined by

$$Y_{ij} = Y_{ij}^{*} - q, \text{ for any } 1 \le i < j \le n. \qquad (2)$$

Let $\mathbb{P}$ denote the distribution under the null hypothesis $H_0$ in the testing setting, or the distribution of the data in the estimation setting. Proving LD lower bounds amounts to establishing an upper bound of the form (see Section 2 for further details)

$$\sup_{f:\deg(f) \le D} \frac{\mathbb{E}[xf(Y)]^2}{\mathbb{E}[f(Y)^2]} \le \mathbb{E}[x]^2(1+o(1)), \qquad (3)$$

where $x$ is the likelihood ratio $x = \frac{d_{\mathbb{P}_{H_1}}}{d_{\mathbb{P}}}(Y)$ in testing $\mathbb{P}$ against $\mathbb{P}_{H_1}$, or the target quantity in estimation. The supremum ranges over all polynomial functions $f$ of degree at most $D$, and $\mathbb{E}[x]^2 = 1$ in testing problems. The value $\mathbb{E}[x]^2$ corresponds to the supremum for $D=0$, i.e. when restricting to trivial constant polynomials.

In a simple detection setting with $\Theta = 0$ under $H_0$, the supremum in (3) can be evaluated explicitly. Indeed, the monomials $\{\phi_S(Y) := \prod_{(i,j) \in S} Y_{ij} : S \in S_{\le D}\}$, indexed by $S_{\le D} = \{S \subset \{(i,j) : 1 \le i < j \le n\} : |S| \le D\}$, form an $L^2(\mathbb{P})$-orthonormal basis for degree-$D$ polynomials. Defining $\hat{x}_S := \mathbb{E}[x\phi_S(Y)]$, we obtain

$$\sup_{f:\deg(f) \le D} \frac{\mathbb{E}[xf(Y)]^2}{\mathbb{E}[f(Y)^2]} = \sup_{(\alpha_S)_{S \in S_{\le D}}} \frac{\left(\sum_{S \in S_{\le D}} \alpha_S \hat{x}_S\right)^2}{\sum_{S \in S_{\le D}} \alpha_S^2} = \|(\hat{x}_S)_{S \in S_{\le D}}\|^2, \qquad (4)$$

so the problem reduces to comparing $\|(\hat{x}_S)_{S \in S_{\le D}}\|^2$ with $\mathbb{E}[x]^2$. This is the classical approach first derived in [Hop+17; HS17; KWB19]. However, the convenient simplification fails for estimation problems or more complex testing settings with $\Theta \ne 0$ under $H_0$, where no simple explicit $L^2(\mathbb{P})$-orthonormal basis for low-degree polynomials is available. Two strategies have been proposed to address this issue:

1. The approach of [SW22] applies an affine transformation to $Y$, and then uses a partial Jensen inequality, integrating over the latent variable inside the square, i.e., schematically

$$\mathbb{E}[f(Y)^2] \ge \mathbb{E}[(\mathbb{E}_z[f(Y)])^2] := \|M^T\alpha\|^2, \qquad (5)$$

yielding an upper triangular matrix $M$ that can be simply inverted. The supremum (3) is then bounded above by $\|M^{-1}\hat{x}\|^2$, which can be evaluated thanks to the explicit inversion of $M$. This method has been successfully applied to certain estimation problems in stochastic block models, graphons [LG24], and dense cycle recovery [MWZ23]. However, the integration over $z$ within the square can cause cancellations between symmetric terms, significantly shrinking the $L^2$-norm and leading to suboptimal bounds, see e.g. [EGV25b].

2. The more powerful method of [SW25] bypasses the construction of an $L^2(\mathbb{P})$-orthonormal basis by instead building one in the extended space $L^2(\mathbb{P}^W)$, where $\mathbb{P}^W$ is the distribution of $W = (Y, z)$. The task then reduces to finding a minimal norm solution $u$ of an overcomplete system $Mu = \hat{x}$. This approach has yielded tight bounds in a variety of problems [SW25; Chi+25], but its applicability can be limited in complex settings, as it requires identifying special solutions of a large overcomplete system.
We propose a simpler and more direct method for evaluating the supremum (3). While constructing an explicit $L^2(\mathbb{P})$-orthonormal basis seems infeasible beyond basic detection problems, we relax the requirement to almost orthonormality. Our method is based on two key ideas:

1. Restrict attention to polynomials $f$ invariant under permutations of the vertex labels, i.e., $f(Y_\sigma) = f(Y)$ for any permutation $\sigma$ of $[n]$, where $[Y_\sigma]_{ij} = Y_{\sigma(i),\sigma(j)}$. Indeed, the supremum in (3) is achieved for $f$ invariant by permutations. Such symmetry property has been exploited in previous works [Sem24; KMW24; MW25] where the authors leverage some invariance by permutations or by orthogonal transformations.

2. Construct a basis of invariant low-degree polynomials that is almost $L^2(\mathbb{P})$-orthonormal in the weak signal regime, in the sense that

$$ \mathbb{E} \left[ \left( \sum_{S \in \mathcal{S}_{\le D}} \alpha_S \phi_S(Y) \right)^2 \right] = \| (\alpha_S)_{S \in \mathcal{S}_{\le D}} \|^2 (1 + o(1)) , \quad (6) $$

typically when $|\Theta|_\infty = \lambda$ is small.

To achieve the key property (6), we start from the basis $\{\phi_S : S \in \mathcal{S}_{\le D}\}$, adjust it to ensure $\mathbb{E}[\phi_S(Y)\phi_{S'}(Y)] = 0$ for many (but not all) distinct $S, S'$, and then average over permutations of the labels to enforce invariance. A central result is that the resulting basis is almost orthonormal for weak signals. Compared with [SW22], our method avoids the potentially suboptimal Jensen step (5). Compared with [SW25], computations are simpler, which may facilitate its application to more intricate problems. For example, problems where the latent vector $z$ is a permutation can be treated more directly, whereas earlier analyses were considerably more involved [EGV25a]. Another important advantage of our direct approach is that it allows us to identify the dominant polynomials in (3), thereby yielding optimal algorithms for the underlying testing or estimation task.

## 1.1 Related literature

**Low-Degree Polynomials in Hypothesis Testing and Estimation.** Historically, the low-degree method originated from the study of the sum-of-squares (SoS) semidefinite programming hierarchy [Bar+19]. The idea of capturing polynomial-time complexity via low-degree polynomials emerged in a sequence of works [Hop+17; HS17; Hop18; KWB19] on detection problems, namely hypothesis testing under a simple null distribution (typically with independent entries). The core strategy is to expand the likelihood ratio in a basis orthonormal under the null distribution, and then solve the resulting optimization problem explicitly. This approach has been successfully applied to a broad range of models, including community detection [HS17], spiked tensor models [HS17; KWB19], sparse PCA [Din+24], and planted subgraph problems [EH25], among many others.

In contrast, the literature on complex testing problems is relatively sparse. Two notable exceptions are [Rus+22] and [Kot+23], which study testing between two different “planted” distributions, each with a distinct type of hidden structure — for example, testing between stochastic block models with different number of communities, or between $q$-colorable and $(q + \ell)$-colorable random graphs. Their proofs adapt techniques from [SW22] originally developed for estimation.

Theory for estimation (or “recovery”) has been primarily developed in [SW22] and [SW25]. The framework of [SW22] has been successfully applied to submatrix estimation [SW22], stochastic block models and graphs [LG24], and Gaussian mixture models [EGV24]. It has also been extended to more complex latent variable models by exploiting conditional independence [EGV25b] and weighted dependency graph theory [EGV25a], yielding lower bounds for challenging settings such as sparse clustering, biclustering, and multiple feature matching. The more recent work [SW25] develops a technically further involved but sharper theory, providing exact constants for thresholds and establishing lower bounds for polynomials of degree $D$ as large as fractional powers of $n$. This approach has been applied to planted submatrix, planted subclique,
spiked Wigner, and stochastic block models [SW25; Chi+25]. When there is no detection-recovery gap — i.e., when recovery is as easy as detection — recovery lower bounds can be directly derived from detection bounds. For problems exhibiting a gap, more sophisticated detection-to-recovery reductions have recently been proposed [Li25; Din+25].

The ideas of leveraging symmetries in the data generating distribution and constructing a nearly orthogonal basis first appeared in [MW25] for the rank one matrix estimation problem, where the basis is derived from Hermite polynomials. This strategy was further developed in [KMW24] for tensor models such as the spiked tensor model, introducing the tensor cumulant basis of rotationally invariant polynomials, which is nearly orthogonal under the tensor-Wigner distribution. Beyond the difference between the statistical models, [KMW24; MW25] only establish the near orthogonality<fnref n="1" /> of their basis in specific regimes or asymptotics: the tensor Wigner distribution being a “pure noise” model, [KMW24] need to rely on a Jensen-type argument reminiscent of [SW22] to consider estimation problems. [MW25] also considered a specific asymptotic regime for their rank one matrix estimation problem. In both [MW25; KMW24], the spectrum of the associated Gram matrix is bounded away from zero and infinity, but does not approach 1 as the problem size grows — a key distinction from our setting. In comparison to those two works, we prove that our basis construction is a versatile and simple tool to establish near optimal LD lower and upper bounds. We further elaborate on the connection between our basis construction and [KMW24], [MW25] in Section 3.

Finally, beyond predicting computational thresholds for polynomial-time algorithms, low-degree polynomials can also provide insight into time complexity in the hard regime. The low-degree conjecture [Hop18] posits that degree-D polynomials can serve as a proxy for algorithms with runtime approximately $n^D$. Extensions of this framework address optimization problems [GJW24] and refutation tasks [Kot+23]. For a comprehensive overview of the low-degree method, its connections to other hardness frameworks, and a broader set of references, we refer to the recent survey [Wei25].

**Hidden subclique.** The planted clique problem, corresponding to $q = 1/2$ and $p := \lambda + q = 1$, is a canonical example of a problem exhibiting an information-computation gap. While the existence of a hidden clique can be detected as soon as $k > 2 \log_2(n)$ by exhaustively scanning all possible cliques, all known polynomial-time tests fail when $k = o(\sqrt{n})$. Low-degree hardness for detection in this regime was proven in [Hop18], adapting arguments from [Bar+19], and the corresponding hardness of estimation was established in [SW22].

For the planted subclique problem (i.e., $p < 1$), [SW22] showed low-degree hardness for recovery when

$$ \frac{\lambda}{\sqrt{q}} \left( 1 \vee \frac{k}{\sqrt{n}} \right) \le \log(n)^{-2}. \qquad (7) $$

This result was refined in [SW25], which proved low-degree hardness of recovery for

$$ \frac{\lambda k}{\sqrt{q(1-q)n}} < e^{-1/2}. \qquad (8) $$

By analogy with the planted submatrix problem, when $k \gg \sqrt{n}$, recovery is conjectured to be possible above this precise threshold using Approximate Message Passing [DM15].

For detection, [DMW25] showed low-degree failure roughly when $p = o(\sqrt{q}k^2/n)$ for $k \ge \sqrt{n}$, and when $p = o(q^{\log_n(k)})$ for $k = o(\sqrt{n})$. Finally, [EH25] studied the more general case where the hidden subclique is replaced by an arbitrary hidden subgraph. They found contrasting behaviors depending on the subgraph density: an statistical-computational gap appears only for dense subgraphs, specifically when the subgraph density exceeds the logarithm of its number of nodes.

**Stochastic Block Model.** The Stochastic Block Model with connection probabilities $p, q$ scaling as $1/n$ has attracted significant attention since the seminal paper of [Dec+11], which — using tools from statistical physics — conjectured computational hardness of recovery below the Kesten-Stigum (KS) threshold

$$ \frac{\lambda k}{\sqrt{\lambda k + nq}} < 1. \qquad (9) $$

<footnote n="1">¹Here, near orthogonality means that the eigenvalues of the corresponding Gram matrix are bounded away from 0 and from $\infty$, whereas almost-orthogonality ensures that its eigenvalues are asymptotically close to 1.</footnote>
Non-trivial recovery above this threshold was established in [Mas14; BLM15; AS15; Chi+25]. Low-degree hardness of detection below the KS threshold (9) was proven in [HS17]; see also [Ban+21; Kun24].

For recovery, [SW25; Chi+25; Din+25] proved low-degree hardness below the KS level (9) when $k \gg \sqrt{n}$ and the polynomial degree $D$ is a fractional power of $n$. This result was extended to the denser regime with $1/n \ll p, q \ll 1$ and $k \gg \sqrt{n}$ in [LG24; Chi+25]. For $p, q$ of constant order, the same conclusion holds at the modified KS threshold

$$ \frac{\lambda k}{\sqrt{\lambda k(1-p-q) + nq(1-q)}} < 1. \qquad (10) $$

When $k \le \sqrt{n}$, [LG24] established computational hardness for $\lambda = O(\sqrt{q}\log(n)^{-2})$, although this bound is believed to be suboptimal [Chi+25].

**Tœplitz seriation** Optimal statistical rates for various loss functions have been derived in [FMR19; CM23; BCV24]. However, the best known polynomial-time algorithms achieve significantly slower rates [CM23; BCV24]. For this reason, statistical-computational gaps have been conjectured, e.g., in [CM23; BCV24]. In particular, [BCV24] and [EGV25a] proved a low-degree lower bound for a Gaussian version of the (TS-I) and (TS-P) models, showing that low-degree polynomials fail when $\frac{k\lambda}{\sqrt{n}} \vee \lambda \le 1$ up to poly-logarithmic factors.

## 1.2 Organization of the manuscript

In Section 2, we introduce the two statistical problems studied in this paper, namely the problem of estimating an entry of $\Theta$, and a specific composite-composite testing problem, where we want to test a small alteration of our structure. We introduce our invariant basis for LD polynomials in Section 3, and we establish its almost orthonormality for all our models, when the signal is weak enough. In Section 4, we then rely on these almost orthonormal polynomials to establish LD lower bounds for the estimation and testing problems. Additional definitions, important for the proof, are introduced in Section 5. While the proof of the almost orthonormality property in the general case is technical — as we simultaneously handle different models — it becomes much simpler when instantiated to a specific model, like the hidden subclique model (HS-I). To provide insights, we convey in Section 6 the core ideas by detailing the proof for the specific hidden subclique model (HS-I). Finally, we present in Section 7 general conditions under which our basis is almost orthonormal, these conditions being satisfied for all models under consideration in this work.

# 2 Setting

Recall the six statistical models (HS-I), (SBM-I), (TS-I), (HS-P), (SBM-P), (TS-P) described in the introduction. Henceforth, we write $\mathbb{P}$ and $\mathbb{E}$ for the probability and expectation of $Y$.

In this manuscript, we tackle two statistical tasks: **estimation** and **complex testing**. In estimation, the goal is to recover the $\mathbb{E}[Y|z] = (\Theta_{z_i z_j})_{1 \le i < j \le n}$. In complex testing, the goal is to test some structural properties on the matrix $(\Theta_{z_i z_j})_{1 \le i < j \le n}$ — this is in sharp contrast with signal detection problems [KWB19] which test the nullity of $\Theta$.

## 2.1 Estimation

As is standard for LD lower bounds in estimation problems [SW22], we focus on estimating the functional

$$ x = \mathbb{1}\{\Theta_{z_1, z_2} \neq 0\}. \qquad (11) $$

Note that $\Theta_{z_1, z_2} = \mathbb{E}[Y_{1,2}|z] \in \{0, \lambda\}$ for the all six models (HS-I), (SBM-I), (TS-I), (HS-P), (SBM-P), and (TS-P) so that proving a LD lower bound for estimating $x$ readily allows, by linearity, to establish a LD lower bound for estimating the matrix $(\Theta_{z_i z_j})$ in Frobenius norm. We recall that

$$ \inf_{f:\deg(f) \le D} \mathbb{E}[(f-x)^2] = \mathbb{E}[x^2] - \text{Corr}_{\le D}^2, \qquad (12) $$
where

$$ \mathrm{Corr}_{\leq D} = \sup_{f:\mathrm{deg}(f)\leq D} \frac{\mathbb{E}[fx]}{\sqrt{\mathbb{E}[f^2]}} = \sup_{(\alpha_S)_{S\in S_{\leq D}}} \frac{\mathbb{E}[x\sum_{S\in S_{\leq D}} \alpha_S Y^S]}{\sqrt{\mathbb{E}\left[\left[\sum_{S\in S_{\leq D}} \alpha_S Y^S\right]^2\right]}} \quad (13) $$

is the minimum low-degree correlation criterion introduced in [SW22]. As explained in the introduction — see (3), proving that $\mathrm{Corr}_{\leq D}^2$ is no larger than $\mathbb{E}[x^2]$ for $D$ of the order of $\log(n)$ is a strong indication of the computational hardness of the estimation problem. Our aim is therefore to characterize the regimes of $(k, n, \lambda)$ such that $\mathrm{Corr}_{\leq D}^2 \leq \mathbb{E}[x^2](1 + o(1))$.

## 2.2 Complex Testing

Fix $\epsilon \in (0, 1)$. For all our six models, we define an alteration

1. **Alteration of (HS).** First sample $(\Theta_{z_i z_j})$ from (HS-I) (resp. (HS-P)). For all $i$ such that $z_i \leq k$, we set the $i$-th row and $i$-th column of $(\Theta_{z_i z_j})$ to zero with probability $\epsilon$. In plain words, under the alteration of (HS-I), the size of the hidden subclique is distributed as $\mathrm{Bin}(n, k(1 - \epsilon)/n)$ instead of $\mathrm{Bin}(n, k/n)$, whereas under the alteration of (HS-P), its size is distributed as $\mathrm{Bin}(k, (1 - \epsilon))$ instead of being equal to $k$.

2. **Alteration of (SBM).** First sample $(\Theta_{z_i z_j})$ from (SBM-I) (resp. (SBM-P)) and sample uniformly a group $\hat{l} \in [n/k]$. Then, for all $i$ such that $z_i \in [(\hat{l} - 1)n/k; (\hat{l} - 1)n/k + 1]$, we set the $i$-th row and $i$-th column of $(\Theta_{z_i z_j})$ to zero with probability $\epsilon$. In this alteration, we decrease the size of one of the $K = n/k$ groups of the SBM and we create a new group of size $\epsilon n/k$ (in expectation) whose probability of connection is always equal to $q$.

3. **Alteration of (TS).** First sample $(\Theta_{z_i z_j})$ from (TS-I) (resp. (TS-P)) and sample uniformly a position $\hat{l} \in [n]$. Then, for all $i$ such that $z_i \in [\hat{l} - k/2; \hat{l} + k/2]$, we set the $i$-th row and $i$-th column of $(\Theta_{z_i z_j})$ to zero with probability $\epsilon$. In the alteration of (TS-P), this amounts to erase some of the entries of the Tøplitz matrix.

We have defined these alterations as illustrative and unified examples of complex testing problems. We could adapt the methodology to other structural tests (e.g. number of groups in the SBM), as the main difficulty in establishing the LD lower bounds is to introduce a candidate basis and establish its almost orthonormality.

Henceforth, we write $\mathbb{P}_{H_1}$ and $\mathbb{E}_{H_1}$ for the probability and expectation in the altered model. For each of the models, we consider the testing problem

$$ H_0: Y \sim \mathbb{P} \quad \text{against} \quad H_1: Y \sim \mathbb{P}_{H_1}. \quad (14) $$

In the low-degree framework [Hop18; KWB19; Wei25], the difficulty of the testing problem is characterized by

$$ \mathrm{Adv}_{\leq D} = \sup_{f:\mathrm{deg}(f)\leq D} \frac{\mathbb{E}_{H_1}[f]}{\sqrt{\mathbb{E}[f^2]}} = \sup_{(\alpha_S)_{S\in S_{\leq D}}} \frac{\mathbb{E}_{H_1}[\sum_{S\in S_{\leq D}} \alpha_S Y^S]}{\sqrt{\mathbb{E}\left[\left[\sum_{S\in S_{\leq D}} \alpha_S Y^S\right]^2\right]}}. \quad (15) $$

As explained in (3), $\mathrm{Adv}_{\leq D} \leq 1 + o(1)$ for $D$ of the order of $\log(n)$ is a strong indication of the hardness of testing $\mathbb{P}$ against $\mathbb{P}_{H_1}$.

In order to control both $\mathrm{Adv}_{\leq D}$ and $\mathrm{Corr}_{\leq D}$, we introduce in the next section a basis of invariant polynomials. After having established its almost orthonormality under $\mathbb{P}$, tight bounds for $\mathrm{Adv}_{\leq D}$ and $\mathrm{Corr}_{\leq D}$ will easily follow.

## 3 Almost orthonormal invariant polynomials

In this section, we construct a specific basis of node-permutation invariant polynomials. As the construction for the testing problem is slightly simpler than for the estimation problem, we start with a dedicated basis for bounding $\mathrm{Adv}_{\leq D}$.
## 3.1 Basis for the complex testing problem

First, we exploit the permutation invariance of the distribution $\mathbb{P}$ to reduce the space of polynomials. A function $f: \mathbb{R}^{n \times n} \to \mathbb{R}$ is said to be invariant by permutations, if, for any matrix $Y$, and any bijection $\sigma: [n] \to [n]$, we have $f(Y) = f(Y_\sigma)$ where $Y_\sigma = (Y_{\sigma(i),\sigma(j)})$.

**Lemma 3.1.** Fix any any degree $D > 0$. If both $\mathbb{P}$ and $\mathbb{P}_{H_1}$ are permutation invariant, then the minimum low-degree advantage $\text{Adv}_{\le D}$ is achieved by a permutation invariant polynomial.

This reduction was already done in [Sem24; KMW24; MW25]. To introduce our basis of invariant polynomials, we consider simple undirected graphs $G = (V, E)$ where $V = \{v_1, \dots, v_r\}$ is the set of nodes and where $E$ is the set of edges. We write $\#CC_G$ for its number of connected components $G$.

**Definition 1** (Collection $G_{\le D}$). Let $G_{\le D}$ be any maximum collection of graphs $G = (V, E)$ such that (i) $G$ does not contain any isolated node, (ii) $|E| \le D$, and (iii) no graphs in $G_{\le D}$ are isomorphic.

In fact, $G_{\le D}$ corresponds to the collection of equivalence classes (with respect to isomorphism) of all graphs with at most $D$ edges, and without isolated nodes. Henceforth, we refer to $G_{\le D}$ as the collection of templates. Consider a template $G = (V, E) \in G_{\le D}$. We define $\Pi_V$ as the set of injective mappings from $V \to [n]$. An element $\pi \in \Pi_V$ corresponds to a labeling of the generic nodes in $V$ by elements in $[n]$. For $\pi \in \Pi_V$, we define the polynomials

$$P_{G,\pi}(Y) = \prod_{(u,v) \in E} Y_{\pi(u),\pi(v)}; \quad \text{and} \quad P_G = \sum_{\pi \in \Pi_V} P_{G,\pi} \qquad (16)$$

For short, we sometimes write $P_G$ for $P_G(Y)$, when there is no ambiguity. For the invariant polynomials $P_G$, we say that $G$ is the **template** (graph) that indexes the polynomial. The idea of indexing the invariant polynomials by templates is borrowed from [KMW24; MW25], although their basis are different to account for normal distributions.

Let us denote $\mathcal{P}_{\le D}^{\text{inv}}$ the subspace of permutation invariant polynomials $f$ with degree at most $D$. The next lemma states that, as expected, any permutation invariant polynomial can be expressed using polynomials $P_G$ indexed by $G \in G_{\le D}$.

**Lemma 3.2.** Assume that $D \le n$. For any $f$ in $\mathcal{P}_{\le D}^{\text{inv}}$, there exist unique numerical values $\alpha_\emptyset$ and $(\alpha_G)_{G \in G_{\le D}}$ such that $f(Y) = \alpha_\emptyset + \sum_{G \in G_{\le D}} \alpha_G P_G(Y)$.

**Correction of the monomials.** The family $(P_G)_{G \in G_{\le D}}$ is orthogonal under the distribution with null signal — namely $\Theta = 0$. However, it is far from being the case when $\Theta \ne 0$, and we have to adjust the basis.

The main ingredient is to tweak the polynomials $P_{G,\pi}$ involved in $P_G$. Consider a template $G \in G_{\le D}$ with $c$ connected components $(G_1, G_2, \dots, G_c)$. Then, we define

$$\bar{P}_G := \sum_{\pi \in \Pi_V} \bar{P}_{G,\pi}; \quad \text{with} \quad \bar{P}_{G,\pi} := \prod_{l=1}^{c} [P_{G_l,\pi} - \mathbb{E}[P_{G_l,\pi}]] . \qquad (17)$$

Note that $\mathbb{E}[P_{G_l,\pi}]$ does not depend on the choice of $\pi$. This correction centers the polynomial associated with each connected component of the template graph.

**Remark.** This correction, already implemented in [MW25], is instrumental to achieve near and almost orthogonality properties — see the comment on their difference in the literature review, subsection 1.1. To see that, let us consider the hidden subclique (HS-I) model. Given $G^{(1)}, G^{(2)}$, write $\pi^{(1)}[G^{(1)}], \pi^{(2)}[G^{(2)}]$ for the graphs $G^{(1)}, G^{(2)}$ with labeled nodes $\pi^{(1)}(V^{(1)}), \pi^{(2)}(V^{(2)})$. In the model (HS-I), $P_{G^{(1)},\pi^{(1)}}$ and $P_{G^{(2)},\pi^{(2)}}$ are independent as long as $\pi^{(1)}[G^{(1)}]$ and $\pi^{(2)}[G^{(2)}]$ do not intersect. Then, by definition of $\bar{P}_{G,\pi}$, one can check that $\mathbb{E}[\bar{P}_{G^{(1)},\pi^{(1)}} \bar{P}_{G^{(2)},\pi^{(2)}}] = 0$ as soon as one connected component of $\pi^{(1)}[G^{(1)}]$ does not intersect $\pi^{(2)}[G^{(2)}]$ or vice versa. As a consequence, the correlation between $\bar{P}_{G^{(1)}}$ and $\bar{P}_{G^{(2)}}$ will be quite small.
**Renormalisation of the polynomials.** It remains to normalize the polynomials $\overline{P}_G$. For this purpose, we need to compute the order of magnitude of $\mathbb{E}[\overline{P}_G^2] = \sum_{\pi^{(1)}, \pi^{(2)}} \mathbb{E}[\overline{P}_{G, \pi^{(1)}} \overline{P}_{G, \pi^{(2)}}]$. Thanks to the previous correction, most terms $\mathbb{E}[\overline{P}_{G, \pi^{(1)}} \overline{P}_{G, \pi^{(2)}}]$ are small, and the dominant term is achieved for $\pi^{(1)}$ and $\pi^{(2)}$ such that $\pi^{(1)}[G] = \pi^{(2)}[G]$. There are $|\Pi_V||\mathrm{Aut}(G)|$ such couples $(\pi^{(1)}, \pi^{(2)})$, where $\mathrm{Aut}(G)$ stands here for the automorphism group of $G$. All these $|\Pi_V||\mathrm{Aut}(G)|$ terms are identical. Also, it turns out that such terms $\mathbb{E}[\overline{P}_{G, \pi}^2]$ are of the order of $\mathbb{E}[P_{G, \pi}^2]$. If the matrix $\Theta$ had been equal to zero, we would readily get $\mathbb{E}[P_{G, \pi}^2] = \overline{q}^{|E|}$ where $\overline{q} := q(1-q)$. This approximation turns out to be sufficient for our purpose. In light of the above discussion, for any $G \in \mathcal{G}_{\le D}$, we define the variance proxy for $P_G$ by

$$ \mathbb{V}(G) = \frac{n!}{(n - |V|)!} |\mathrm{Aut}(G)| \overline{q}^{|E|}, \quad \text{with} \quad \overline{q} = q(1 - q). \qquad (18) $$

Finally, we define the normalized polynomial

$$ \Psi_G = \frac{\overline{P}_G}{\sqrt{\mathbb{V}(G)}}. \qquad (19) $$

Since $(1, (\Psi_G)_{G \in \mathcal{G}_{\le D}})$ span the same space as $(1, (P_G)_{G \in \mathcal{G}_{\le D}})$, we deduce from Lemmas 3.1 and 3.2, the following result.

**Lemma 3.3.** If both $\mathbb{P}$ and $\mathbb{P}_{H_1}$ are permutation invariant, then we have

$$ \mathrm{Adv}_{\le D} = \sup_{(\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}})} \frac{\mathbb{E}_{H_1} \left[ \alpha_\emptyset + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right]}{\sqrt{\mathbb{E} \left[ \left( \alpha_\emptyset + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right)^2 \right]}}. \qquad (20) $$

Our main result result is given in the next theorem. It states that, for all our six models, the basis $(1, (\Psi_G)_{G \in \mathcal{G}_{\le D}})$ is almost orthonormal as long as $\lambda$ is not too large.

**Theorem 3.4.** There exist positive numerical constants $c_0$ and $c$, such that the following holds for all $D \ge 2$ and all six models (HS-I), (SBM-I), (TS-I), (HS-P), (SBM-P), and (TS-P). If we assume that

$$ \left(\frac{k}{n}\right) \vee \left(\frac{\lambda k}{\sqrt{nq}}\right) \vee \left(\frac{\lambda}{q}\right) \le D^{-c_0}, \qquad (21) $$

then, for any vector $\alpha = (\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}})$ in $\mathbb{R}^{|\mathcal{G}_{\le D}|+1}$, we have

$$ (1 - cD^{-2}) \|\alpha\|_2^2 \le \mathbb{E} \left[ \left( \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right)^2 \right] \le (1 + cD^{-2}) \|\alpha\|_2^2. \qquad (22) $$

In fact, this theorem is a straightforward consequence of the more general results (Theorems 7.1 and 7.2 and Proposition 7.4) stated in Section 7. Note that under the assumptions of the theorem, we readily get the following upper bound for the advantage

$$ \mathrm{Adv}_{\le D}^2 \le (1 - cD^{-2})^{-1} \left[ 1 + \sum_{G \in \mathcal{G}_{\le D}} \mathbb{E}_{H_1} [\Psi_G]^2 \right]. \qquad (23) $$

So, we only need to bound the first moment of the basis elements under the alternative hypothesis to control the advantage, and establish a LD lower bound. This is done in the next section.

To the best of our knowledge, this is the first time that for general structured distributions, and under mild conditions on the parameters $(k, \lambda, q)$, such an almost orthonormal basis is constructed, although [MW25] established a similar result in a BBP-type asymptotic, for the rank one matrix estimation problem.

The conditions on Theorem 3.4 are indeed rather mild, except the last one:
* The first condition $\frac{k}{n} \le D^{-c_0}$ does not exclude interesting regimes. Indeed, when $k$ is of the order of $n$, no significant statistical-computational gaps arise in our models.

* As further discussed in the next section, when the condition $\lambda k/\sqrt{nq} \le D^{-c_0}$ is not fulfilled (up to a polynomial in $D$), in most interesting regimes, it is possible to reconstruct the signal matrix $(\Theta_{z_i z_j})$ with a LD polynomial estimator, so that the problem is computationally solvable.

* The last condition $\lambda \le qD^{-c_0}$ is more restrictive and is in fact not intrinsic — it entails that we only deal with the regimes where the two probabilities $q$ and $p = q + \lambda$ are of same order. Relaxing this condition to $\lambda = o(\sqrt{q})$ is technical but doable at least for the classical instances of the hidden subclique model (HS-I) and stochastic block model (SBM-I). However, this is beyond the scope of this paper, as our aim is to establish simple yet versatile results. In the regime where $\lambda \gg \sqrt{q}$, then the normalization $\mathbb{V}(G)$ defined in (18) ceased to be a good approximation of the second moment $\mathbb{E}[P_{G,\pi}^2]$ and one has to resort to a different normalization –see the subsequent work [CGV25a].

## 3.2 Basis for the estimation problem

We now turn to the basis for the estimation of $x = 1\{\Theta_{z_1,z_2} \neq 0\}$. If the distribution $\mathbb{P}$ is invariant under permutation, then the distribution of $(x, Y)$ is invariant under permutation of the node $\{3, \dots, n\}$, as the two first nodes play a specific role. As a consequence, we have to slightly adapt the definition of the $\Psi_G$'s.

Consider a template $G = (V, E)$ with $V = \{v_1, v_2, \dots, v_r\}$, without isolated nodes (except possibly $v_1, v_2$), with $|V| \ge 2$ and at least one edge. Let $\Pi_V^{(1,2)}$ be the set of injective mappings $\pi$ from $V \to [n]$ such that $\pi(v_1) = 1, \pi(v_2) = 2$. We then define the polynomial

$$P_G^{(1,2)} = \sum_{\pi \in \Pi_V^{(1,2)}} P_{G,\pi}.$$

For short, we sometimes write $P_G^{(1,2)}$ for $P_G^{(1,2)}(Y)$ when there is no ambiguity.

Let $G^{(1)} = (V^{(1)}, E^{(1)})$ and $G^{(2)} = (V^{(2)}, E^{(2)})$ be two templates. We say $G^{(1)}$ and $G^{(2)}$ are equivalent if there exist a bijection $\sigma: V^{(1)} \to V^{(2)}$ such that $\sigma(v_1^{(1)}) = v_1^{(2)}$, $\sigma(v_2^{(1)}) = v_2^{(2)}$, and $\sigma$ preserves the edges. In other words, the graphs $G^{(1)}$ and $G^{(2)}$ are isomorphic with the additional constraint that the corresponding bijection maps $v_1^{(1)}$ to $v_1^{(2)}$ and $v_2^{(1)}$ to $v_2^{(2)}$. Then, we define $\mathcal{G}_{\le D}^{(1,2)}$ as a maximum collection of non-equivalent templates with at most $D$ edges and at least one edge. Consider a template $G \in \mathcal{G}_{\le D}^{(1,2)}$ with $c$ non-trivial connected components $(G_1, G_2, \dots, G_c)$. We define

$$\bar{P}_G^{(1,2)} := \sum_{\pi \in \Pi_V^{(1,2)}} \bar{P}_{G,\pi}^{(1,2)}; \quad \text{with} \quad \bar{P}_{G,\pi}^{(1,2)} := \prod_{l=1}^c [P_{G_l,\pi} - \mathbb{E}[P_{G_l,\pi}]] .$$

Recall that $\bar{q} = q(1 - q)$. Define the variance proxy

$$\mathbb{V}^{(1,2)}(G) = \frac{(n-2)!}{(n-|V|)!} |\mathrm{Aut}^{(1,2)}(G)|^{\bar{q}} |E|, \qquad (24)$$

where $\mathrm{Aut}^{(1,2)}(G)$ is the set of automorphisms of the graph $G$ that let $v_1$ and $v_2$ fixed. Finally, we define the polynomials

$$\Psi_G^{(1,2)} = \frac{\bar{P}_G^{(1,2)}}{\sqrt{\mathbb{V}^{(1,2)}(G)}}. \qquad (25)$$

The following result is the counterpart of Lemma 3.3 for the estimation problem.

**Lemma 3.5.** As long as $\mathbb{P}$ is permutation invariant, we have

$$\mathrm{Corr}_{\le D} = \sup_{\alpha_{\emptyset}, (\alpha_G)_{G \in \mathcal{G}_{\le D}^{(1,2)}}} \frac{\mathbb{E}\left[x(\alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}^{(1,2)}} \alpha_G \Psi_G^{(1,2)})\right]}{\sqrt{\mathbb{E}\left[\left[\alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}^{(1,2)}} \alpha_G \Psi_G^{(1,2)}\right]^2\right]}}.$$
The following result is the analogue of Theorem 3.4 for the basis $(1, (\Psi_G^{(1,2)})_{G \in \mathcal{G}_{\le D}^{(1,2)}})$.

**Theorem 3.6.** There exist positive numerical constants $c_0$ and $c$, such that the following holds for any $D \ge 2$ and all six models (HS-I), (SBM-I), (TS-I), (HS-P), (SBM-P), and (TS-P). If we assume that

$$ \left(\frac{k}{n}\right) \vee \left(\frac{\lambda k}{\sqrt{nq}}\right) \vee \left(\frac{\lambda}{q}\right) \le D^{-c_0}, \qquad (26) $$

then, for any $\alpha = (\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}^{(1,2)}})$, we have

$$ (1 - cD^{-2}) \|\alpha\|_2^2 \le \mathbb{E} \left[ \left( \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}^{(1,2)}} \alpha_G \Psi_G^{(1,2)} \right)^2 \right] \le (1 + cD^{-2}) \|\alpha\|_2^2. \qquad (27) $$

Again, this theorem is a straightforward consequence of the more general theorem 7.3.

# 4 Main Low-degree Lower bounds

In this section, we deduce LD lower bounds from the almost orthornormality of the basis. We start with estimation problems as those are more classical.

## 4.1 Estimation problem

**Theorem 4.1.** There exist positive numerical constants $c$ and $c_0$ such that the following holds for any $D \ge 2$. Provided that

$$ \left(\frac{k}{n}\right) \vee \left(\frac{\lambda k}{\sqrt{nq}}\right) \vee \left(\frac{\lambda}{q}\right) \le D^{-c_0}, \qquad (28) $$

then, all six models (HS-I), (HS-P), (SBM-I), (SBM-P), (TS-I), and (TS-P) satisfy

$$ \mathrm{Corr}_{\le D} \le \mathbb{E}[x](1 + cD^{-1}). \qquad (29) $$

Note that $\mathbb{E}[x] = \mathrm{Corr}_{\le 0}$. This entails that, when (28) holds with $D$ of the order $\log(n)$, no polynomial of degree of order $\log(n)$ can perform significantly better than the constant prediction $\mathbb{E}[x]$ of degree 0 polynomials.

To discuss our results, let us focus on $D = \log(n)$ and regimes in $(q, k, n)$ such that $k \le \frac{n}{\log^{c_0}(n)}$ and $q \ge n/k^2$. Note that this forces $k$ to belong to $[\sqrt{n}; n \log^{-c_0}(n)]$. Then, Theorem 4.1 states that recovery is impossible by low-degree polynomials as soon as

$$ \frac{\lambda k}{\sqrt{nq}} \le \log^{-c_0}(n). \qquad (30) $$

For both hidden subclique ((HS-I) and (HS-P)) and stochastic blocks models ((SBM-I) and (SBM-P)), it is known that recovery is possible in polynomial time above this threshold [SW22; LG24; SW25]. In particular, we recover the impossibility results of [SW22; LG24; SW25] for (HS-I) and (SBM-I). In comparison to the tight bounds of [SW25], our results are less tight as we lose poly-logarithmic factors. Besides, our LD lower bounds are optimal when $q \ge n/k^2$ whereas [SW25] deal with the case where $k \gg \sqrt{n}$. As already alluded, we believe that the condition $q \ge n/k^2$, which arises because we require $\lambda \le q$, is an artefact of the proof and can be weakened to $k \gg \sqrt{n}$ using arguments that are more tailored to the models (HS-I) and (SBM-I). To the best of our knowledge, the LD lower bounds for the permutations models (HS-P) and (SBM-P) are novel.

For the Tœplitz seriation models ((TS-I) and (TS-P)), the Condition (30) matches that of [BCV24] for polynomial-time reconstruction in the dense regime ($q$ of the order of a constant). It is also similar to the LD lower bound in the Gaussian setting of [BCV24] for (TS-I) and [EGV25a] for (TS-P) when $k \gg \sqrt{n}$.
## 4.2 Complex testing problem

Recall the altered distributions $\mathbb{P}_{H_1}$ introduced in Section 2. Here, we deduce from Theorems 7.1 and 7.2 and in particular from (23) a bound for $\text{Adv}_{\le D}$.

**Theorem 4.2.** There exist positive numerical constants $c$ and $c_0$ such that the following holds for any $D \ge 2$. Provided that

$$ \left(\frac{k}{n}\right) \vee \left(\frac{\lambda k}{\sqrt{nq}}\right) \vee \left(\frac{\lambda}{q}\right) \vee \left(\frac{\epsilon \lambda k^2}{n\sqrt{q}}\right) \le D^{-c_0}, \quad (31) $$

then, all six models (HS-I), (HS-P), (SBM-I), (SBM-P), (TS-I), (TS-P) satisfy

$$ \text{Adv}_{\le D}^2 \le 1 + cD^{-1}. \quad (32) $$

Under the low-degree conjecture, Theorem 4.2 provides a strong indication that when Condition (31) holds it is impossible in polynomial-time to distinguish the distribution $\mathbb{P}$ and $\mathbb{P}_{H_1}$. Given Theorem 3.4 and the Bound (23), to prove this theorem, we only have to control the first moments $\mathbb{E}_{H_1}[\Psi_G]$ for $G \in \mathcal{G}_{\le D}$.

Condition (31) is the conjunction of Condition (28) for reconstruction and the condition $\epsilon\lambda^2k^2 \le D^{-c_0}n\sqrt{q}$. In particular, the latter inequality is optimal for the alteration detection problem. Indeed, consider the statistic $T = \sum_{i<j} Y_{ij}$. Since $\lambda \le q$, we have $T - \mathbb{E}[T] = \mathbb{E}_{\mathbb{P}}(n\sqrt{q})$ and $T - \mathbb{E}_{H_1}[T] = \mathbb{E}_{\mathbb{P}_{H_1}}(n\sqrt{q})$. As a consequence, $T$ is powerful as soon as $|\mathbb{E}[T] - \mathbb{E}_{H_1}[T]| \ge n\sqrt{q}$. Since $\mathbb{E}[T] - \mathbb{E}_{H_1}[T]$ is of the order of $\epsilon\lambda k^2$, the result follows.

# 5 Graph definitions

In order to show the almost orthonormality of the family $(\Psi_G)_{G \in \mathcal{G}_{\le D}}$, we have to work out cross products of the form $\mathbb{E}[P_{G^{(1)}} P_{G^{(2)}}]$ for two templates $G^{(1)}$ and $G^{(2)}$. In turn, this is done by working out quantities of the form $\mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]$ where $\pi^{(1)}$ and $\pi^{(2)}$ are two labelings of $G^{(1)}$ and $G^{(2)}$. This requires a systematic way to classify the combinatorial structures that arise when two template graphs are overlaid. The purpose of this section is to introduce all these concepts.

Recalling that we write $\pi^{(1)}[G]$ and $\pi^{(2)}[G]$ for the corresponding labeled graph, $\mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]$ highly depends on the nodes in common between these two graphs. Indeed,

$$ P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}} = \prod_{(v_1,v_2) \in E^{(1)}} Y_{\pi^{(1)}(v_1)\pi^{(1)}(v_2)} \prod_{(v_1,v_2) \in E^{(2)}} Y_{\pi^{(2)}(v_1)\pi^{(2)}(v_2)}, $$

and the distribution of the product is a function of the edges that appear twice in $\pi^{(1)}[G^{(1)}]$ and $\pi^{(2)}[G^{(2)}]$ and of the edges that appear only once in these two graphs.

## 5.1 Node matching and graph merging

**Matching of nodes.** Consider two templates $G^{(1)} = (V^{(1)}, E^{(1)})$ and $G^{(2)} = (V^{(2)}, E^{(2)})$. Given labelings $\pi^{(1)}$ and $\pi^{(2)}$, we say that two nodes $v^{(1)}$ and $v^{(2)}$ are matched if $\pi^{(1)}(v^{(1)}) = \pi^{(2)}(v^{(2)})$. More generally, a matching $\mathbf{M}$ stands for a set of pairs of nodes $(v^{(1)}, v^{(2)}) \in V^{(1)} \times V^{(2)}$ where no node in $V^{(1)}$ or $V^{(2)}$ appears twice. We denote $\mathcal{M}$ for the collection of all possible node matchings. For $\mathbf{M} \in \mathcal{M}$, we define the collection of labelings that are compatible with $\mathbf{M}$ by

$$ \Pi(\mathbf{M}) = \{ \pi^{(1)} \in \Pi_{V^{(1)}}, \pi^{(2)} \in \Pi_{V^{(2)}} : \forall (v^{(1)}, v^{(2)}) \in V^{(1)} \times V^{(2)}, \{\pi^{(1)}(v^{(1)}) = \pi^{(2)}(v^{(2)})\} \iff \{(v^{(1)}, v^{(2)}) \in \mathbf{M}\} \}. \quad (33) $$

Importantly, as $\mathbb{P}$ is permutation invariant, $\mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]$ is the same for all $(\pi^{(1)}, \pi^{(2)})$ in $\Pi(\mathbf{M})$. Given a matching $\mathbf{M}$, we write that two edges $e \in E^{(1)}$ and $e' \in E^{(2)}$ are matched if the corresponding incident nodes are matched.
<figure><img src="image_1.png" /><figcaption>Figure 1: Illustration of two templates $G^{(1)}$ and $G^{(2)}$, a matching $\mathbf{M}$ and the symmetric difference graph $G_{\Delta}$.</figcaption></figure>

**Merged graph $G_{\cup}$, intersection graph $G_{\cap}$, and symmetric difference graph $G_{\Delta}$.** Consider two templates $G^{(1)}$ and $G^{(2)} \in \mathcal{G}_{\le D}$ and two labelings $\pi^{(1)}$ and $\pi^{(2)}$. Then, the merged graph $G_{\cup} = (V_{\cup}, E_{\cup})$ is defined as the union of $\pi^{(1)}[G^{(1)}]$ and $\pi^{(2)}[G^{(2)}]$, with the convention that two same edges are merged into a single edge. Similarly, we define the intersection graph $G_{\cap} = (V_{\cap}, E_{\cap})$ and the symmetric difference graph $G_{\Delta} = (V_{\Delta}, E_{\Delta})$ so that $E_{\Delta} = E_{\cup} \setminus E_{\cap}$ — see Figure 1 for an example. We also have $|E_{\cup}| = |E^{(1)}| + |E^{(2)}| - |E_{\cap}|$ and $|V_{\cup}| = |V^{(1)}| + |V^{(2)}| - |\mathbf{M}|$ for $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$. Note that, for a fixed matching $\mathbf{M}$, all graphs $G_{\cup}$ (resp. $G_{\cap}, G_{\Delta}$) are isomorphic for $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$ and we shall refer to quantities such as $|E_{\Delta}|, |V_{\Delta}|, \dots$ associated to a matching $\mathbf{M}$.

Finally, we write $\#CC_{\Delta}$ for the number of connected components in $G_{\Delta}$, and $\#CC_{\text{pure}}$ for the number of connected components in $G_{\Delta}$ that are solely composed of nodes from $G^{(1)}$, or from $G^{(2)}$. This is the number of connected components that are “untouched” from the matching process. These two quantities only depend on $(\pi^{(1)}, \pi^{(2)})$ through the matching $\mathbf{M}$.

**Sets of unmatched nodes and of semi-matched nodes.** Write $U^{(1)}$, resp. $U^{(2)}$ for the set of nodes in $\pi^{(1)}[G^{(1)}]$, resp. $\pi^{(2)}[G^{(2)}]$ that are not matched, namely the **unmatched nodes**, that is

$$U^{(1)} = \pi^{(1)}(V^{(1)}) \setminus \pi^{(2)}(V^{(2)}); \quad U^{(2)} = \pi^{(2)}(V^{(2)}) \setminus \pi^{(1)}(V^{(1)}) .$$

Again, $|U^{(1)}|$ and $|U^{(2)}|$ only depend on $(\pi^{(1)}, \pi^{(2)})$ through the matching $\mathbf{M}$. We have, for $i \in \{1, 2\}$,

$$|V^{(i)}| = |\mathbf{M}| + |U^{(i)}| . \qquad (34)$$

Write also $\mathbf{M}_{\text{SM}} = \mathbf{M}_{\text{SM}}(\mathbf{M}) \subset \mathbf{M}$, for the set of node matches of $(G^{(1)}, G^{(2)})$ that are matched, and yet that are not pruned when creating the symmetric difference graph $G_{\Delta}$. This is the set of **semi-matched nodes** — i.e. at least one of their incident edges is not matched. The remaining pairs of nodes $\mathbf{M} \setminus \mathbf{M}_{\text{SM}}$ are said to be **perfectly matched** as all the edges incident to them are matched. We write $\mathbf{M}_{\text{PM}} = \mathbf{M}_{\text{PM}}(\mathbf{M})$ for the set of perfect matches in $\mathbf{M}$. Note that

$$|V^{(1)}| + |V^{(2)}| = |V_{\Delta}| + |\mathbf{M}_{\text{SM}}| + 2|\mathbf{M}_{\text{PM}}| . \qquad (35)$$

**Definition of some relevant sets of nodes matchings.** We define $\mathcal{M}^* \subset \mathcal{M}$ for the collection of matchings $\mathbf{M}$ such that all connected components of $G^{(1)}$ and of $G^{(2)}$ intersect<fnref n="2" /> with $\mathbf{M}$. As a consequence, for any $\mathbf{M} \in \mathcal{M}^*$, we have $\#CC_{\text{pure}} = 0$. Finally, we introduce $\mathcal{M}_{\text{PM}} \subset \mathcal{M}$ for the collection of perfect matchings, that is matchings $\mathcal{M}$ such that all the nodes in $V^{(1)}$ and $V^{(2)}$ are **perfectly matched**. Note that, if $\mathbf{M} \in \mathcal{M}_{\text{PM}}$, then $G_{\Delta}$ is the empty graph (with $E_{\Delta} = \emptyset$). Besides, $\mathcal{M}_{\text{PM}} \neq \emptyset$ if and only $G^{(1)}$ and $G^{(2)}$ are isomorphic, which is equivalent to $G^{(1)} = G^{(2)}$ when $G^{(1)}, G^{(2)} \in \mathcal{G}_{\le D}$.

<footnote n="2">²Here, we mean that, for each connected component, at least one its vertices appears in a tuple of $\mathbf{M}$.</footnote>
<figure><img src="image_2.png" /><figcaption>Figure 2: Illustration of the shadow of a graph. The information contained in the shadow are all labels of the nodes which are colored. The labels of the black part is not registered in the shadow — but we know the “shape” and that all nodes in the black part are perfectly matched.</figcaption></figure>

## 5.2 Further definitions

This subsection gathers other concepts that will be useful for establishing the almost orthonormality of the basis. It can be skipped at first reading.

**Shadow matchings.** Write for two sets $\overline{U}^{(1)} \subset V^{(1)}, \overline{U}^{(2)} \subset V^{(2)}$ and for a set of node matches $\mathbf{M} \in \mathcal{M}$
$$ \mathcal{M}_{\text{shadow}}(\overline{U}_1, \overline{U}_2, \mathbf{M}) = \{\mathbf{M}' \in \mathcal{M} : U^{(1)}(\mathbf{M}') = \overline{U}^{(1)}, U^{(2)}(\mathbf{M}') = \overline{U}^{(2)}, \mathbf{M}_{\text{SM}}(\mathbf{M}') = \mathbf{M}\}, \quad (36) $$

namely the set of all matchings that lead to the set $\mathbf{M}$ of semi matched nodes and to the sets $\overline{U}_1, \overline{U}_2$ of unmatched nodes in resp. $G^{(1)}, G^{(2)}$. We say that these matchings satisfy a given **shadow** $(\overline{U}_1, \overline{U}_2, \mathbf{M})$. The only thing that can vary between two elements of $\mathcal{M}_{\text{shadow}}(\overline{U}_1, \overline{U}_2, \mathbf{M})$ is the matching of the nodes that are not in $\overline{U}_1, \overline{U}_2$, or part of a pair of nodes in $\mathbf{M}$. This matching must however ensure that all of these nodes are perfectly matched.

**Edit Distance between graphs.** For any two templates $G^{(1)}$ and $G^{(2)}$, we define the so-called edit distance.

$$ d(G^{(1)}, G^{(2)}) := \min_{\mathbf{M} \in \mathcal{M}} |E_{\Delta}|. \quad (37) $$

Note that $d(G^{(1)}, G^{(2)}) = 0$ if and only if $G^{(1)}$ and $G^{(2)}$ are isomorphic. As a consequence, if $G^{(1)}$ and $G^{(2)}$ are in $\mathcal{G}_{\le D}$, the edit distance is equal to 0 if and only if $G^{(1)} = G^{(2)}$.

# 6 Core of the proof: the (HS-I) model when $q = 1/2$

In what follows, our goal is to set aside the technicalities arising from the consideration of more complex models, and instead focus on the simple (HS-I) model in the case $q = 1/2$. This will allow us to clearly illustrate how our proof technique proceeds in order to prove almost orthonormality. We present a detailed and annotated proof for this specific case. Although the other models, as well as the case $q \ne 1/2$, involve certain important technical differences, the core ideas and methods of the proof remain the same.

Assume that $D \ge 2$ and that for some large enough universal constant $c_0 \ge 5$.

$$ \frac{\lambda k}{\sqrt{q}n} \vee \frac{\lambda}{\sqrt{q}} \vee \frac{k}{n} \le D^{-8c_0}, \quad (38) $$
with $\bar{q} = q(1 - q)$. For $\mathbb{P} = \mathbb{P}_{H_0}$, our goal is to prove the almost $L^2(\mathbb{P})$-orthonormality of the family of invariant polynomials $(\Psi_G)_{G \in \mathcal{G}_{\le D}}$ with $\Psi_G = \frac{\bar{P}_G}{\sqrt{\mathcal{V}(G)}}$ defined in (17) and (19).

Through this proof as well as other proofs, we shall often use that, for any template graph $G$, its number of vertices, edges, and connected components are respectively at most equal to $2D$, $D$, and $D$.

**Proposition 6.1.** Let $\Gamma$ be the Gram matrix $(\Gamma_{G^{(1)},G^{(2)}})_{G^{(1)},G^{(2)} \in \mathcal{G}_{\le D}} = (\mathbb{E}[\Psi_{G^{(1)}}\Psi_{G^{(2)}}])_{G^{(1)},G^{(2)} \in \mathcal{G}_{\le D}}$. Under the Condition (38), we have
$$ \|\Gamma - I\|_{op} \le 2D^{-c_0}. $$

This proposition is mostly Theorem 3.4 in our specific model. We emphasize that once this result is proven, a bound on $\mathrm{Adv}_{\le D}$ can be derived simply. Indeed, note first that $\mathbb{E}[\Psi_G] = 0$ due to the centering (17), i.e. 1 is orthogonal to all $\Psi_G$. Hence the previous proposition together with Lemma 3.3 imply that

$$ \mathrm{Adv}_{\le D}^2 = \sup_{\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}}} \frac{\mathbb{E}_{H_1} \left[ \alpha_\emptyset + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right]^2}{\mathbb{E} \left[ \left( \alpha_\emptyset + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right)^2 \right]} \le \frac{1 + \| (\mathbb{E}_{H_1} \Psi_G)_{G \in \mathcal{G}_{\le D}} \|_2^2}{(1 - 2D^{-c_0})^2}. \quad (39) $$

So it only remains to bound $\|(\mathbb{E}_{H_1} \Psi_G)_{G \in \mathcal{G}_{\le D}}\|_2^2$ in order to get a bound on $\mathrm{Adv}_{\le D}$. In the remaining of this section, we focus on the proof of Proposition 6.1.

**Step 0: Preliminary computations.** We observe that $\mathbb{E}[Y_{ij}|z] = \Theta_{z_i z_j} = \lambda \mathbf{1}\{z_i \le k\}\mathbf{1}\{z_j \le k\}$ and $\mathbb{E}[Y_{ij}^2|z] = \bar{q} + \Theta_{z_i z_j}(1 - 2q) = \bar{q}$ for $q = 1/2$. Consider two templates $G^{(1)}, G^{(2)}$, some node matching $\mathbf{M} \in \mathcal{M}$ and two injections $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$. Since the $Y_{ij}$ are conditionally independent given $z$, we have under $\mathbb{P}$

$$ \begin{aligned} \mathbb{E} [P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}] &= \mathbb{E} \left[ \prod_{(i,j) \in E_{\Delta}} Y_{ij} \prod_{(i,j) \in E_{\cap}} Y_{ij}^2 \right] \\ &= \mathbb{E} \left[ \prod_{(i,j) \in E_{\Delta}} (\lambda \mathbf{1}\{z_i \le k\} \mathbf{1}\{z_j \le k\}) \prod_{(i,j) \in E_{\cap}} \bar{q} \right] \\ &= \lambda^{|E_{\Delta}|} \bar{q}^{|E_{\cap}|} \mathbb{P}[z_i \le k, \text{ for } i \in V_{\Delta}] \\ &= \lambda^{|E_{\Delta}|} \left(\frac{k}{n}\right)^{|V_{\Delta}|} \bar{q}^{|E_{\cap}|} = \left(\frac{\lambda}{\bar{q}}\right)^{|E_{\Delta}|} \left(\frac{k}{n}\right)^{|V_{\Delta}|} \bar{q}^{|E_{\cup}|}. \end{aligned} \quad (40) $$

This implies in particular (with $G^{(2)} = \emptyset$)

$$ \mathbb{E}[P_{G^{(1)}, \pi^{(1)}}] = \lambda^{|E^{(1)}|} \left(\frac{k}{n}\right)^{|V^{(1)}|}. \quad (41) $$

Also if $\mathbf{M} = \emptyset$, then for any functions $f^{(1)}, f^{(2)}$ of edges respectively in $\pi^{(1)}(E^{(1)}), \pi^{(2)}(E^{(2)})$, then

$$ \mathbf{E}[f^{(1)} f^{(2)}] = \mathbf{E}[f^{(1)}] \mathbb{E}[f^{(2)}], \quad (42) $$

by independence of $(Y_{ij})_{(i,j) \in \pi^{(1)}(E^{(1)})}$ and $(Y_{ij})_{(i,j) \in \pi^{(2)}(E^{(2)})}$.

**Step 1: From $P_{G,\pi}$ to $\bar{P}_{G,\pi}$.** A first key observation is that thanks to the centering (17), the Gram matrix

$$ (\mathbb{E}[\bar{P}_{G^{(1)},\pi^{(1)}} \bar{P}_{G^{(2)},\pi^{(2)}}])_{G^{(1)},G^{(2)} \in \mathcal{G}_{\le D}, \pi^{(1)} \in \Pi_{V^{(1)}}, \pi^{(2)} \in \Pi_{V^{(2)}}} \quad (43) $$

associated to $(\bar{P}_{G,\pi})_{G \in \mathcal{G}_{\le D}, \pi \in \Pi_V}$ is quite sparse — unlike the one associated to $(P_{G,\pi})_{G \in \mathcal{G}_{\le D}, \pi \in \Pi_V}$. Furthermore, on the non-zero entries, it is quite close to the Gram matrix associated to $(P_{G,\pi})_{G \in \mathcal{G}_{\le D}, \pi \in \Pi_V}$.
**Proposition 6.2.** Let $\mathcal{M}^*$ be the collection of matchings $\mathcal{M}$ such that all connected components of $G^{(1)}$ and of $G^{(2)}$ intersect with $\mathcal{M}$.

1. If $\mathcal{M} \notin \mathcal{M}^*$, we have $\mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G^{(2)},\pi^{(2)}}] = 0$;

2. If $\mathcal{M} \in \mathcal{M}^*$, we have

$$ \left| \frac{\mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G^{(2)},\pi^{(2)}}] - \mathbb{E}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}]}{\mathbb{E}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}]} \right| \le D^{-3c_0}. $$

*Proof of Proposition 6.2.* Write $G^{(1)} = (G_1^{(1)}, \dots, G_{\#CC_{G^{(1)}}}^{(1)})$, and $G^{(2)} = (G_1^{(2)}, \dots, G_{\#CC_{G^{(2)}}}^{(2)})$ for the decomposition of $G^{(1)}, G^{(2)}$ into their resp. $\#CC_{G^{(1)}}$, $\#CC_{G^{(2)}}$ connected components. Write also $\pi_1^{(1)}, \dots, \pi_{\#CC_{G^{(1)}}}^{(1)}$, and $\pi_1^{(2)}, \dots, \pi_{\#CC_{G^{(2)}}}^{(2)}$ for their respective labelings.

**Proof of 1):** If $\mathcal{M} \notin \mathcal{M}^*$, there exists one connected component belonging to either $G^{(1)}$ or $G^{(2)}$, whose nodes are not matched in $\mathcal{M}$. Assume w.l.o.g. that this connected component is $G_1^{(1)}$. By Equation (42), we have

$$ \mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G^{(2)},\pi^{(2)}}] = \mathbb{E}[\overline{P}_{G_1^{(1)},\pi^{(1)}}] \mathbb{E}\left[\prod_{l=2}^{\#CC_{G^{(1)}}} \overline{P}_{G_l^{(1)},\pi^{(1)}} \times \overline{P}_{G^{(2)},\pi^{(2)}}\right] = 0, \quad (44) $$

since $\mathbb{E}[\overline{P}_{G_1^{(1)},\pi^{(1)}}] = 0$ according to the centering (17).

**Proof of 2):** From the identity

$$ \prod_{\ell=1}^{L} (a_{\ell} - b_{\ell}) = \sum_{S \subset [L]} (-1)^{|S|} \prod_{\ell \notin S} a_{\ell} \prod_{\ell \in S} b_{\ell}, \quad (45) $$

we derive

$$ \mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G^{(2)},\pi^{(2)}}] = \sum_{\substack{S_1 \subset [\#CC_{G^{(1)}}] \\ S_2 \subset [\#CC_{G^{(2)}}]}} (-1)^{|S_1|+|S_2|} \mathbb{E}\left[\prod_{i \in [\#CC_{G^{(1)}}] \setminus S_1} P_{G_i^{(1)},\pi_i^{(1)}} \prod_{i \in [\#CC_{G^{(2)}}] \setminus S_2} P_{G_i^{(2)},\pi_i^{(2)}}\right] \\ \times \mathbb{E}\left[\prod_{i \in S_1} P_{G_i^{(1)},\pi_i^{(1)}}\right] \mathbb{E}\left[\prod_{i \in S_2} P_{G_i^{(2)},\pi_i^{(2)}}\right], $$

Then, the following lemma holds.

**Lemma 6.3.** For any any $S_1 \subset [\#CC_{G^{(1)}}]$ and any $S_2 \subset [\#CC_{G^{(2)}}]$, we have

$$ 0 \le \mathbb{E} \left[ \prod_{i \in [\#CC_{G^{(1)}}] \setminus S_1} P_{G_i^{(1)}, \pi_i^{(1)}} \prod_{i \in [\#CC_{G^{(2)}}] \setminus S_2} P_{G_i^{(2)}, \pi_i^{(2)}} \right] \mathbb{E} \left[ \prod_{i \in S_1} P_{G_i^{(1)}, \pi_i^{(1)}} \right] \mathbb{E} \left[ \prod_{i \in S_2} P_{G_i^{(2)}, \pi_i^{(2)}} \right] \\ \le \left(\frac{k}{n}\right)^{(|S_1|+|S_2|)/2} \mathbb{E} \left[ P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}} \right]. $$

This leads to:

$$ \frac{\left| \mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G^{(2)},\pi^{(2)}}] - \mathbb{E}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}] \right|}{\mathbb{E}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}]} \le \sum_{S_1 \subset [\#CC_{G^{(1)}}], S_2 \subset [\#CC_{G^{(2)}}]: |S_1 \cup |S_2| \ge 1} \left(\frac{k}{n}\right)^{(|S_1|+|S_2|)/2} \\ \le \sum_{s_1 \le D, s_2 \le D: s_1 \vee s_2 \ge 1} D^{s_1+s_2} \left(\frac{k}{n}\right)^{(s_1+s_2)/2} \\ \le D^{-3c_0}, $$

by Equation (38) with $c_0 \ge 5$ and $D \ge 2$.
**Proof of Lemma 6.3.** Define the matching $\mathbf{M}$ from $M$ by removing all node pairs such that a least one node lies in the connected components indexed by $S_1$ or $S_2$. Then, we take $(\bar{\pi}^{(1)}, \bar{\pi}^{(2)}) \in \Pi(\bar{\mathbf{M}})$. Note that, without loss of generality, we can take $\bar{\pi}^{(1)} = \pi^{(1)}$, and $\bar{\pi}^{(2)}$ restricted to nodes that do not belong to a match in $\mathbf{M}$ is equal to $\pi^{(2)}$. Equipped with this notation, we have

$$ \mathbb{E} \left[ \left[ \prod_{i \in [\#CC_{G^{(1)}}] \setminus S_1} P_{G_i^{(1)}, \pi_i^{(1)}} \prod_{i \in [\#CC_{G^{(2)}}] \setminus S_2} P_{G_i^{(2)}, \pi_i^{(2)}} \right] \mathbb{E} \left[ \left[ \prod_{i \in S_1} P_{G_i^{(1)}, \pi_i^{(1)}} \right] \mathbb{E} \left[ \left[ \prod_{i \in S_2} P_{G_i^{(2)}, \pi_i^{(2)}} \right] \right] \right] = \mathbb{E} \left[ P_{G^{(1)}, \bar{\pi}^{(1)}} P_{G^{(2)}, \bar{\pi}^{(2)}} \right], \quad (46) $$

We write $G_{\Delta} = (V_{\Delta}, E_{\Delta})$, $G_{\cap} = (V_{\cap}, E_{\cap})$, $G_{\cup} = (V_{\cup}, E_{\cup})$ for the resp. symmetric difference, intersection and union graphs corresponding to the labeled graphs $\pi^{(1)}(G^{(1)}), \pi^{(2)}(G^{(2)})$ and also $\bar{G}_{\Delta} = (\bar{V}_{\Delta}, \bar{E}_{\Delta})$, $\bar{G}_{\cap} = (\bar{V}_{\cap}, \bar{E}_{\cap})$, $\bar{G}_{\cup} = (\bar{V}_{\cup}, \bar{E}_{\cup})$ for the resp. symmetric difference, intersection and union graphs corresponding to the labeled graphs $\bar{\pi}^{(1)}(G^{(1)}), \bar{\pi}^{(2)}(G^{(2)})$.

By Equation (40), we have

$$ \mathbb{E} [P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}] = \left(\frac{\lambda}{\bar{q}}\right)^{|E_{\Delta}|} \left(\frac{k}{n}\right)^{|V_{\Delta}|} \bar{q}^{|E_{\cup}|}, \quad \text{and} \quad \mathbb{E} [P_{G^{(1)}, \bar{\pi}^{(1)}} P_{G^{(2)}, \bar{\pi}^{(2)}}] = \left(\frac{\lambda}{\bar{q}}\right)^{|\bar{E}_{\Delta}|} \left(\frac{k}{n}\right)^{|\bar{V}_{\Delta}|} \bar{q}^{|\bar{E}_{\cup}|}. $$

Since $\bar{M} \subset \mathbf{M}$, we have

$$ |\bar{E}_{\Delta}| \ge |E_{\Delta}| \quad \text{and} \quad |\bar{E}_{\cup}| \ge |E_{\cup}|. \quad (47) $$

So that since $\lambda \le \bar{q} = 1/4$

$$ \mathbb{E} [P_{G^{(1)}, \bar{\pi}^{(1)}} P_{G^{(2)}, \bar{\pi}^{(2)}}] \le \left(\frac{k}{n}\right)^{|\bar{V}_{\Delta}| - |V_{\Delta}|} \mathbb{E} [P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}]. $$

In addition, again since $\bar{M} \subset \mathbf{M}$, we have

$$ |\bar{V}_{\Delta}| = |V_{\Delta}| + |\mathbf{M} \setminus \bar{\mathbf{M}}|. \quad (48) $$

On $\mathcal{M}^*$, each connected component indexed by $S_1, S_2$ must contain at least one matched node in $\mathbf{M}$, which cannot be in $\bar{\mathbf{M}}$, so we have

$$ 2|\mathbf{M} \setminus \bar{\mathbf{M}}| \ge |S_1| + |S_2|. \quad (49) $$

Combining the last three equations concludes the proof of this lemma. $\square$

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

**Step 2: Entry-wise control of the Gram matrix.** A first step towards deriving a bound on the operator norm of $\Gamma - I$, is to derive a bound for each entry. Building on the orthogonality between many $\bar{P}_{G^{(1)}, \pi^{(1)}}$ and $\bar{P}_{G^{(2)}, \pi^{(2)}}$, and on the proximity between $\bar{P}_{G, \pi}$ and $P_{G, \pi}$, we prove below that $\Gamma$ is entrywise close to the identity, which is the core of the proof of Proposition 6.1.

**Proposition 6.4.** Consider two templates $G^{(1)}, G^{(2)} \in \mathcal{G}_{\le D}$. We have

$$ |\Gamma_{G^{(1)}, G^{(2)}} - \mathbf{1}\{G^{(1)} = G^{(2)}\}| = |\mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}] - \mathbf{1}\{G^{(1)} = G^{(2)}\}| \le 2D^{-3c_0d(G^{(1)}, G^{(2)})\vee 1}, $$

with $d$ the edit distance defined by (37).

**Proof of Proposition 6.4.** We have by definition:

$$ \begin{aligned} \mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}] &= \sum_{\mathbf{M} \in \mathcal{M}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})} \frac{1}{\sqrt{\mathcal{V}(G^{(1)}) \mathcal{V}(G^{(2)})}} \mathbb{E}[\bar{P}_{G^{(1)}, \pi^{(1)}} \bar{P}_{G^{(2)}, \pi^{(2)}}] \\ &= \sum_{\mathbf{M} \in \mathcal{M}^*} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})} \frac{1}{\sqrt{\mathcal{V}(G^{(1)}) \mathcal{V}(G^{(2)})}} \mathbb{E}[\bar{P}_{G^{(1)}, \pi^{(1)}} \bar{P}_{G^{(2)}, \pi^{(2)}}], \end{aligned} $$
where the second line follows from Proposition 6.2.

**Step 2a: Decomposition of the scalar product over $M^* \setminus M_{PM}$ and $M_{PM}$**. The set $M_{PM}$ is non-empty only if $G^{(1)} = G^{(2)}$. And if $G^{(1)} = G^{(2)}$, we have for any $\pi \in \Pi_{V^{(1)}}$

$$ \sum_{M \in \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \mathbb{E} \left[ \overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}} \right] = \frac{n! |\mathrm{Aut}(G^{(1)})| \mathbb{E} \left[ \overline{P}_{G^{(1)}, \pi}^2 \right]}{(n - |V^{(1)}|)! \mathbb{V}(G^{(1)})} = \frac{\mathbb{E} \left[ \overline{P}_{G^{(1)}, \pi}^2 \right]}{\overline{q}^{|E^{(1)}|}}, \quad (50) $$

since

$$ |\mathcal{M}_{PM}| = |\mathrm{Aut}(G^{(1)})| \quad \text{and} \quad |\Pi(\mathbf{M})| = \frac{n!}{(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))!}, \quad (51) $$

and by definition of $\mathbb{V}(G^{(1)})$. Equation (40) ensures that $\mathbb{E}[P_{G^{(1)}, \pi^{(1)}}^2] = \overline{q}^{|E^{(1)}|}$, so by Proposition 6.2 we have

$$ (1 - D^{-3c_0}) \overline{q}^{|E^{(1)}|} \le \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}}^2] \le \overline{q}^{|E^{(1)}|} (1 + D^{-3c_0}) . \quad (52) $$

Hence

$$ \left| \mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}] - 1 \{G^{(1)} = G^{(2)}\} \right| \\ \le \left| \sum_{M \in \mathcal{M}^* \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \mathbb{E} \left[ \overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}} \right] \right| + D^{-3c_0} =: A + D^{-3c_0}. $$

**Step 2b: Making $A$ explicit as a sum of $A_M$.** Observe that for any $M \in \mathcal{M}$, we have that $\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] = E_M$ is constant for any $(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)$. So that by Equation (51)

$$ A = \left| \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M}^* \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} E_M \right| \\ = \left| \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M}^* \setminus \mathcal{M}_{PM}} \frac{n!}{(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))!} E_M \right| . $$

By Proposition 6.2 and Equation (40), we have

$$ E_M \le \lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|} \overline{q}^{|E_\cap|} (1 + D^{-3c_0}), \quad (53) $$

where we recall that $|E_\Delta|$, $|V_\Delta|$, $|E_\cap|$ only depend on the matching $M$ as all graphs $G_\Delta$ (resp. $G_\cap$) are isomorphic for $(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)$.

Since $\frac{n!}{(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))!} \frac{\sqrt{(n - |V^{(1)}|)(n - |V^{(2)}|)!}}{n!} \le n^{|U^{(1)}| + |U^{(2)}|/2}$ where we recall that $|U^{(a)}|$ is the number of unmatched nodes in $G^{(a)}$, and by definition of $\mathbb{V}(G)$, we have

$$ A \le \frac{1}{\sqrt{|\mathrm{Aut}(G^{(1)})| |\mathrm{Aut}(G^{(2)})|}} \sum_{M \in \mathcal{M}^* \setminus \mathcal{M}_{PM}} n^{|U^{(1)}| + |U^{(2)}|/2} \left(\frac{\lambda}{\sqrt{\overline{q}}}\right)^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|} (1 + D^{-3c_0}) \\ \le \frac{2}{\sqrt{|\mathrm{Aut}(G^{(1)})| |\mathrm{Aut}(G^{(2)})|}} \sum_{M \in \mathcal{M}^* \setminus \mathcal{M}_{PM}} \left(\frac{\lambda k}{\sqrt{\overline{q}}n}\right)^{|U^{(1)}| + |U^{(2)}|} \left(\frac{\lambda}{\sqrt{\overline{q}}}\right)^{|E_\Delta| - |U^{(1)}| - |U^{(2)}|} \left(\frac{k}{n}\right)^{|V_\Delta| - |U^{(1)}| - |U^{(2)}|} , $$

using that $D \ge 2$ and $c_0 \ge 4$, and rearranging terms in the last line. Write $A_M$ for the summand in the last line.
**Step 2c: Bounding of A by summing over shadows.** Recall we define shadows and $M_{\text{shadow}}$ in Section 5. We now regroup the sum inside A by enumerating all possible matchings that are compatible with a shadow. We get

$$A \le \frac{2}{\sqrt{|\text{Aut}(G^{(1)})||\text{Aut}(G^{(2)})|}} \sum_{\substack{U^{(1)} \subset V^{(1)}, U^{(2)} \subset V^{(2)}, \\ \underline{M} \in \mathcal{M} \setminus \mathcal{M}_{\text{PM}}}} \sum_{\mathbf{M} \in \mathcal{M}_{\text{shadow}}(U^{(1)}, U^{(2)}, \underline{M})} A_{\mathbf{M}}.$$

We have the following control for the cardinality of $M_{\text{shadow}}$:

$$|\mathcal{M}_{\text{shadow}}(U^{(1)}, U^{(2)}, \underline{M})| \le \min(|\text{Aut}(G^{(1)})|, |\text{Aut}(G^{(2)})|), \quad (54)$$

see Lemma A.5 and its proof. Observe that two matchings $M$ and $M'$ that belong to $M_{\text{shadow}}(U^{(1)}, U^{(2)}, \underline{M})$ have the same difference graph $G_{\Delta}$. Hence

$$A \le 2 \sum_{\substack{U^{(1)} \subset V^{(1)}, U^{(2)} \subset V^{(2)}, \\ \underline{M} \in \mathcal{M} \setminus \mathcal{M}_{\text{PM}}}} A_{\mathbf{M}}. \quad (55)$$

**Step 2d: Bounding $A_M$.** A key observation is that for any graph $G_{\Delta} = (V_{\Delta}, E_{\Delta})$ without isolated nodes, we have $|E_{\Delta}| \ge |V_{\Delta}| - \#\text{CC}_{\Delta}$. Since $|M_{\text{SM}}| + |U^{(1)}| + |U^{(2)}| = |V_{\Delta}|$, it follows

$$\begin{aligned} |E_{\Delta}| &\ge |U^{(1)}| + |U^{(2)}| &\text{if } \mathbf{M} \in \mathcal{M}^*, &&\text{since in this case } |\mathbf{M}_{\text{SM}}| - \#\text{CC}_{\Delta} \ge 0; \\ |E_{\Delta}| &\ge d(G^{(1)}, G^{(2)}) \lor 1, &\text{by definition of the edit distance and if } \mathbf{M} \notin \mathcal{M}_{\text{PM}}. \end{aligned}$$

Hence, the signal assumption (38) ensures that for $\mathbf{M} \in \mathcal{M}^* \setminus \mathcal{M}_{\text{PM}}$

$$\begin{aligned} A_{\mathbf{M}} &\le D^{-8c_0(|U^{(1)}|+|U^{(2)}|)} D^{-8c_0(|E_{\Delta}|-(|U^{(1)}|+|U^{(2)}|))} D^{-8c_0|\mathbf{M}_{\text{SM}}|} \le D^{-8c_0[|E_{\Delta}|+|\mathbf{M}_{\text{SM}}|]} \\ &\le D^{-4c_0[d(G^{(1)},G^{(2)})\lor 1+|U^{(1)}|+|U^{(2)}|+|\mathbf{M}_{\text{SM}}|]} . \end{aligned}$$

**Step 2e: Final bound on A.** Plugging this bound on $A_{G_{\Delta}}$, back in Equation (55), we get

$$A \le 2 \sum_{\substack{U^{(1)} \subset V^{(1)}, U^{(2)} \subset V^{(2)}, \\ \underline{M} \in \mathcal{M} \setminus \mathcal{M}_{\text{PM}}}} D^{-4c_0[d(G^{(1)},G^{(2)})\lor 1+|U^{(1)}|+|U^{(2)}|+|\mathbf{M}_{\text{SM}}|]} . \quad (56)$$

So, when we enumerate over all possible sets $U^{(1)}, U^{(2)}, \underline{M}$ that have respective cardinality $u_1, u_2$, and $m$, and since these sets have cardinalities bounded resp. by $(2D)^{u_1}, (2D)^{u_2}$ and $(2D)^{2m}$, we obtain

$$A \le 2 \sum_{u_1, u_2, m \ge 0} (2D)^{u_1+u_2+2m} D^{-4c_0[d(G^{(1)},G^{(2)})\lor 1+u_1+u_2+m]} \le D^{-3c_0(d(G^{(1)},G^{(2)})\lor 1)},$$

using again that $c_0 \ge 5$ and $D \ge 2$. $\square$

**Step 3. From entrywise bound to operator norm bound.** In Step 2, we proved an entrywise bound on $\Gamma - I$. To prove Proposition 6.1, it remains to provide a bound in operator norm. Since for symmetric matrices the $\ell^2 \to \ell^2$ operator norm can be upper bounded by the $\ell^\infty \to \ell^\infty$ operator norm, which is the maximum of the $\ell^1$-norm of the rows, we can translate the entrywise bound of Proposition 6.4 to a bound in $\ell^2 \to \ell^2$ operator norm

$$\|\Gamma - I\|_{op} \le \max_{G^{(1)}} |\Gamma_{G^{(1)}, G^{(1)}} - 1| + \sum_{G^{(2)} \in \mathcal{G}_{\le D} : G^{(2)} \ne G^{(1)}} |\Gamma_{G^{(1)}, G^{(2)}}|.$$

We have the following lemma.

**Lemma 6.5.** Fix a template $G^{(1)}$. For any positive integer $u$, we have

$$\#\{G^{(2)} \in \mathcal{G}_{\le D} : d(G^{(1)}, G^{(2)}) = u\} \le (2u + 2D)^{2u}.$$
Proof of Lemma 6.5. If $d(G^{(1)}, G^{(2)}) = u$, this entails that there exist labelings $\pi^{(1)}$ and $\pi^{(2)}$ of these two templates such that the edit distance between the labelled graphs is equal to $u$. For a given graph with $v$ nodes, the number of graphs at edit distance equal to $u$ is at most $v^{2u}$. Since $G^{(1)}$ has a most $2D$ nodes and the number of additional nodes given by the labeling of $G^{(2)}$ is at most $2u$, the result follows. $\square$

We also use that, if $G^{(2)} \neq G^{(1)}$, then $d(G^{(1)}, G^{(2)}) \geq 1$ as they are not isomorphic. It then follows from Proposition 6.4 and Lemma 6.5 that

$$ \sum_{G^{(2)} \in \mathcal{G}_{\leq D}, G^{(2)} \neq G^{(1)}} |\Gamma_{G^{(1)}, G^{(2)}}| \leq \sum_{G^{(2)} \in \mathcal{G}_{\leq D}, G^{(2)} \neq G^{(1)}} 2D^{-3c_0 d(G^{(1)}, G^{(2)})} \\ \leq \sum_{2D \geq u \geq 1} |\{G^{(2)} : d(G^{(1)}, G^{(2)}) = u\}| 2D^{-3c_0 u} \\ \leq \sum_{2D \geq u \geq 1} 2(2u + 2D)^{2u} D^{-3c_0 u} \leq \sum_{2D \geq u \geq 1} 2D^{-3(c_0-2)u} \leq D^{-c_0}, $$

since $D \geq 2$ and $c_0 \geq 5$. Using Proposition 6.4, to bound the remaining term $|\Gamma_{G^{(1)}, G^{(1)}} - 1|$, we conclude the proof of Proposition 6.1

# 7 Almost orthonormality of $(\Psi_G)_{G \in \mathcal{G}_{\leq D}}$ under general conditions

In this section, we establish that the almost orthonormality of the family $(\Psi_G)_{G \in \mathcal{G}_{\leq D}}$ — resp. $(\Psi_G^{(1,2)})_{G \in \mathcal{G}_{\leq D}^{(1,2)}}$ — actually holds under some generic conditions, which are easy to check in our general model (1). To motivate these conditions, we explain where they are needed to extend the proof arguments of Section 6. We first state the following signal restriction on $\lambda, k, q$, that we will need in all models.

**Condition 3 (C-Signal).** We assume that $\Theta_{ij} \in [0, \lambda]$. For some constant $c_s > 1$, we have

$$ \left(\frac{k}{n}\right) \vee \left(\frac{\lambda k}{\sqrt{nq}}\right) \vee \left(\frac{\lambda}{q}\right) \leq D^{-8c_s}. \qquad (57) $$

This condition matches that in Theorems 3.4 and 3.6 and has been discussed just below Theorem 3.4. In this general setting, $k$ plays the role of a sparsity and $\lambda$ of the signal. In what follows, we distinguish between the **Independent-Sampling** scheme, which is simpler, and the **Permutation Sampling** scheme, where the independence property from Equation (42) is lost, and we require an additional condition.

## 7.1 Independent-Sampling scheme

The first part of Proposition 6.2 is still true in our more general models under **Independent-Sampling**, as, by independence of the labels $(z_i)$'s Equation 42 remains true. In the proof of the second part of Proposition 6.2, the key lemma is Lemma 6.3 where we bound each term that appears in the decomposition of $\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}]$. For this purpose, we have to control the first and second moment of polynomials $\overline{P}_{G, \pi}$.

**Condition 4 (C-Moment).** For some non-negative constants $c_m$, the following holds. For all templates $G = (V, E)$ with less than $D$ edges, and for any labeling $\pi \in \Pi_V$, we have

$$ |\mathbb{E}[P_{G, \pi}]| \leq (D^{c_m} \lambda)^{|E|} \left(D^{c_m} \frac{k}{n}\right)^{|V|-\#CC_G}. \qquad (58) $$

For instance, in (41), we have proved that (HS-I) satisfies $\mathbb{E}[P_{G, \pi}] = \lambda^{|E|} (\frac{k}{n})^{|V|}$ so that (58) even holds with an additional factor $(k/n)^{\#CC_G}$. It turns out that (58) is sufficient for our purpose. In what follows, we introduce $p$ and $\bar{p}$ by

$$ p = \lambda + q; \quad \bar{p} := p(1-q)^2 + (1-p)q^2, \qquad (59) $$
where we observe $\bar{p} = \bar{q} + \lambda(1 - 2q) \ge \bar{q}$ since we assume that $q \le 1/2$. In our framework, $p$ corresponds to the maximum connection probability in the random graph.

In a related way to the previous condition, the following condition bounds the covariance and variance of monomials $P_{G,\pi}$ in terms of some characteristics of the graph $G$.

**Condition 5 (C-Variance).** For some non-negative constants $c_{v,1}, c_{v,2}, c_{v,3}$, and some $c_{v,4} \ge 1$, the following holds.

1. Fix two templates $G^{(1)} = (V^{(1)}, E^{(1)})$, $G^{(2)} = (V^{(2)}, E^{(2)}) \in \mathcal{G}_{\le D}$ and let $\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\text{PM}}$ be a matching. For any $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$ we have

$$ \left| \mathbb{E} [P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}] \right| \le c_{v,2} (D^{c_{v,1}} \lambda)^{|E_{\Delta}|} |\bar{p}|^{|E_{\cap}|} \left( D^{c_{v,1}} \frac{k}{n} \right)^{|V_{\Delta}| - \#CC_{\Delta}} . $$

2. For any template $G = (V, E) \in \mathcal{G}_{\le D}$ and for any $\pi \in \Pi_V$, we have

$$ \left| \mathbb{E} [P_{G, \pi}^2] - \bar{q}^{|E|} \right| \le c_{v,3} D^{-c_{v,4}} \bar{q}^{|E|} . $$

In (40), we have proved that, for (HS-I) with $q = 1/2$ — so that $\bar{p} = \bar{q}$ — we have $\mathbb{E} [P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}] = \lambda^{|E_{\Delta}|} |\bar{q}|^{|E_{\cap}|} (\frac{k}{n})^{|V_{\Delta}|}$. In the first part of the above condition, we only require a bound up to a polynomial factor in $D$ and up to a factor $(k/n)^{\#CC_{\Delta}}$. Similarly, (40) enforces that for (HS-I) with $q = 1/2$ we have $\mathbb{E} [P_{G, \pi}^2] = \bar{q}^{|E|}$. The second part of C-Moment only requires that this holds approximately.

Under the above conditions, we can adapt the proof arguments of Section 6 to establish the almost orthonormality of the $\Psi_G$'s.

**Theorem 7.1.** Consider the Independent-Sampling scheme and fix $D \ge 2$. Assume that Conditions C-Signal, C-Moment, and C-Variance are fulfilled with $c_s > 1$ large enough in comparison to the other constants. Then, for all $(\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}})$, we have

$$ (1 - cD^{-c_s/2}) \|\alpha\|_2^2 \le \mathbb{E} \left[ \left( \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right)^2 \right] \le (1 + cD^{-c_s/2}) \|\alpha\|_2^2, \quad (60) $$

where the positive constant $c$ depends on the constants $c_m, c_{v,1}, \dots, c_{v,4}$.

## 7.2 Permutation Sampling scheme

Under the Permutation Sampling scheme, polynomials $P_{G^{(1)}, \pi^{(1)}}$ and $P_{G^{(2)}, \pi^{(2)}}$ with disjoint nodes — that is $\pi^{(1)}(V^{(1)}) \cap \pi^{(2)}(V^{(2)}) = \emptyset$— are not independent anymore, albeit this dependency is arguably quite weak. Therefore, the first part of Proposition 6.2 is not going to hold anymore in these models. The purpose of the next condition is to establish that $\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}]$ is small enough for matchings $\mathbf{M}$ that do not belong to $\mathcal{M}^*$. Although this condition is arguably quite ad-hoc and technical to define, it turns out to be relatively simple to check in all our models.

**Condition 6 (C-Variance-Permutation).** Let $G^{(1)} = (V^{(1)}, E^{(1)})$, $G^{(2)} = (V^{(2)}, E^{(2)}) \in \mathcal{G}_{\le D}$ be two templates and let $\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\text{PM}}$ be a matching. Consider any $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$. In the sequel, we write $\tilde{\mathbb{E}}$ for the expectation in the model where the latent assignments $(z_i)$s are sampled independently (that is under Independent-Sampling). Define the graph $\mathcal{N}[z; G_\cup]$ with vertices $\omega_0, \omega_1, \dots, \omega_{\#CC_{\text{pure}}}$ where, for $i > 0$, $\omega_i$ corresponds to the $i$-th pure connected component of $G_\Delta$ and $\omega_0$ corresponds to the collections the remaining nodes of $G_\cup$ — if $V_\cap$ is empty, we do not define $\omega_0$. We set an edge between $\omega_i$ and $\omega_j$ if and only if at least one vertex $a$ in the node set $\omega_i$ of $G_\cup$ shares the same latent assignment as one vertex $b$ in the node set $\omega_j$ of $G_\cup$, that is $z_a = z_b$. Define the event $\mathcal{A}$ such that the graph $\mathcal{N}[z; G_\cup]$ is connected. Then, we have

$$ \left| \tilde{\mathbb{E}} [1\{\mathcal{A}\} P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}] \right| \le c_{vd,2} D^{c_{vd,1}} (D^{c_{vd,1}} \lambda)^{|E_{\Delta}|} |\bar{p}|^{|E_{\cap}|} \left( D^{c_{vd,1}} \frac{k}{n} \right)^{|V_{\Delta}| - \#CC_{\Delta}} \left( c_{vd,2} \frac{D^{c_{vd,1}}}{\sqrt{n}} \right)^{\#CC_{\text{pure}}} , $$

for some non-negative constants $c_{vd,1}, c_{vd,2}$.
The following theorem holds under the above assumptions.

**Theorem 7.2.** Consider the Permutation Sampling scheme and fix $D \ge 2$. Assume that Conditions C-Signal, C-Moment, C-Variance, and C-Variance-Permutation are fulfilled with $c_s > 1$ large enough in comparison to the other constants. Then, for all $(\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}})$, we have

$$ (1 - cD^{-c_s/2}) \|\alpha\|_2^2 \le \mathbb{E} \left[ \left( \alpha_\emptyset + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right)^2 \right] \le (1 + cD^{-c_s/2}) \|\alpha\|_2^2, \quad (61) $$

where $c$ depends on the constants $c_m, c_{v,1}, \dots, c_{vd,2}$.

## 7.3 Almost orthonormality for estimation

For estimation, the following theorem holds. It is a generic version of Theorem 3.4 and Proposition 6.1, in models Permutation Sampling- and replacing Theorem 7.1 in Independent-Sampling.

**Theorem 7.3.** Fix any $D \ge 2$. Under either the conditions of Theorem 7.1 or those of Theorem 7.2, we have

$$ (1 - cD^{-c_s/2}) \|\alpha\|_2^2 \le \mathbb{E} \left[ \left( \alpha_\emptyset + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G^{(1,2)} \right)^2 \right] \le (1 + cD^{-c_s/2}) \|\alpha\|_2^2, \quad (62) $$

for all $(\alpha_\emptyset, (\alpha_G)_{G \in \mathcal{G}_{\le D}^{(1,2)}})$. Here, the positive constant $c$ depends on the other constants in the conditions.

## 7.4 All conditions are satisfied in our models

The next proposition states that all six models satisfy the desired conditions. The explicit values for $c_m, c_{v,1}, c_{v,2}, c_{v,3}, c_{v,4}, c_{v,1}$, and $c_{vd,2}$ are given in the proofs.

**Proposition 7.4.** Assume that the parameters $(k, n, p, q)$ satisfy C-Signal with $c_s = 1$. Then, (HS-I), (SBM-I), (TS-I) satisfy Conditions C-Moment and C-Variance. Also, (HS-P), (SBM-P), (TS-P) satisfy C-Moment, C-Variance, and C-Variance-Permutation.

Then, Theorem 3.4 is a straightforward consequence of Theorems 7.1 and 7.2 and Proposition 7.4, whereas Theorem 3.6 is a consequence of Theorem 7.3 and Proposition 7.4.

# 8 Discussion

## 8.1 Flexibility of the almost orthonormal basis

In this work, we introduced the polynomial basis $(\Psi_G)_{G \in \mathcal{G}_{\le D}}$, which turns out to be almost orthonormal for a variety of permutation-invariant graph models. This almost orthonormality can be readily exploited to establish low-degree (LD) lower bounds for other testing and functional estimation problems, such as testing the value of $k$ or $\lambda$. Moreover, it enables a tighter connection between LD upper and lower bounds by finding the decomposition in the basis $\Psi_G$ of a polynomial that nearly attains $\text{Corr}_{\le D}$ and $\text{Adv}_{\le D}$.

To illustrate the flexibility of our approach, we mention some subsequent application of it in [CGV25a; CGV25b] to SBM with a large number $K = n/k$ number of groups. In a striking paper, Chin et al. [Chi+25] have recently shown that, at least in the regime where $q$ scales in $1/n$, it is possible to recover the groups when $K \ge \sqrt{n}$ below the Kesten-Stigun threshold that what longstandingly conjectured [Dec+11] to be the computational barrier. Their procedure is based on numbers of non-bactracking paths in the graph. However, they did not provide a matching LD lower bound. By considering an almost-orthonormal basis similar to $\Psi_G$ but with a different normalization, [CGV25a] have established a LD lower bould for all regimes of $q$. They also introduced in [CGV25a; CGV25b] new efficient procedures based on motif counting that match this LD lower bound. The choices of the motifs –cliques, self-avoiding path, blow-up graphs [CGV25b]–
actually depends on the sparsity $q$. Importantly, in these works, the almost-orthonormal basis provides
strong insights that are instrumental for the construction of these new procedures.

Beyond graph data, we expect this approach to extend naturally to other distributional models with transformation invariance. Compared with [SW22] and [SW25], our constructive method is more direct and transparent. In particular, it provides an alternative proof strategy to [SW25] when inverting the overcomplete linear system therein becomes intractable, and an alternative to [SW22] when controlling the cumulants proves difficult, or when the Jensen bound in [SW22] is not tight. We illustrated this by establishing LD lower bounds for Permutation Sampling models.

## 8.2 Getting sharp results

Our results can be improved in two main directions:

* First, we have only analyzed the regime $\lambda = o(q)$, see Theorem 7.1. We conjecture that this restriction is merely an artefact of the proof, and that (after a suitable renormalization) the basis $\Psi_G$ remains almost orthonormal in all regimes where recovery is computationally hard. For (HS-I) and (SBM-I), however, certain adjustments are needed in both the variance proxy and the proof. In particular, for $\lambda \ge \sqrt{q}$, the variance proxies $\mathbb{V}(G)$, $\mathbb{V}^{(1,2)}(G)$ can be significantly smaller than $\mathbb{E}[\overline{P}_G^2]$. In particular, the contribution of perfectly matched nodes in $\mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G^{(2)},\pi^{(2)}}]$ must be handled more carefully than in Section 6. This extension was very recently carried out in [CGV25a].

* Second, compared with [SW25], our LD lower bounds are tight only up to a poly-$D$ factor. Removing this extra factor is an interesting— albeit likely delicate— combinatorial problem, which we also leave for future work.

## Acknowledgements

The work of A. Carpentier is partially supported by the Deutsche Forschungsgemeinschaft (DFG)- Project-ID 318763901 - SFB1294 "Data Assimilation", Project A03, by the DFG on the Forschungsgruppe FOR5381 "Mathematical Statistics in the Information Age - Statistical Efficiency and Computational Tractability", Project TP 02 (Project-ID 460867398), and by the DFG on the French-German PRCI ANR-DFG ASCAI CA1488/4-1 "Aktive und Batch-Segmentierung, Clustering und Seriation: Grundlagen der KI" (Project-ID 490860858). The work of the last three authors has also been fully or partially supported by ANR-21-CE23-0035 (ASCAI, ANR) and ANR-19-CHIA-0021-01 (BiSCottE, ANR). The work of A. Carpentier and N. Verzelen is also supported by the Universite franco-allemande (UFA) through the college doctoral franco-allemand CDFA-02-25 "Statistisches Lernen für komplexe stochastische Prozesse".

## References

[AS15] Emmanuel Abbe and Colin Sandon. "Community Detection in General Stochastic Block Models: Fundamental Limits and Efficient Algorithms for Recovery". In: *Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS)*. FOCS '15. Washington, DC, USA: IEEE Computer Society, 2015, pp. 670–688.

[Ban+21] Afonso S Bandeira, Jess Banks, Dmitriy Kunisky, Christopher Moore, and Alex Wein. "Spectral planting and the hardness of refuting cuts, colorability, and communities in random graphs". In: *Conference on Learning Theory*. PMLR. 2021, pp. 410–473.

[Ban+22] Afonso S Bandeira, Ahmed El Alaoui, Samuel Hopkins, Tselil Schramm, Alexander S Wein, and Ilias Zadik. "The Franz-Parisi criterion and computational trade-offs in high dimensional statistics". In: *Advances in Neural Information Processing Systems* 35 (2022), pp. 33831–33844.

[Bar+19] Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, and Aaron Potechin. "A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem". In: *SIAM Journal on Computing* 48.2 (2019), pp. 687–735. eprint: https://doi.org/10.1137/17M1138236.
[BB20] Matthew Brennan and Guy Bresler. "Reducibility and statistical-computational gaps from secret leakage". In: *Conference on Learning Theory*. PMLR. 2020, pp. 648-847.

[BBH18] Matthew Brennan, Guy Bresler, and Wasim Huleihel. "Reducibility and computational lower bounds for problems with planted sparse structure". In: *Conference On Learning Theory*. PMLR. 2018, pp. 48-166.

[BCV24] Clément Berenfeld, Alexandra Carpentier, and Nicolas Verzelen. "Seriation of Tœplitz and latent position matrices: optimal rates and computational trade-offs". In: *arXiv preprint arXiv:2408.10004*. (2024).

[BLM15] Charles Bordenave, Marc Lelarge, and Laurent Massoulié. "Non-backtracking spectrum of random graphs: community detection and non-regular ramanujan graphs". In: *2015 IEEE 56th Annual Symposium on Foundations of Computer Science*. IEEE. 2015, pp. 1347-1357.

[BR13] Quentin Berthet and Philippe Rigollet. "Complexity Theoretic Lower Bounds for Sparse Principal Component Detection". In: *Proceedings of the 26th Annual Conference on Learning Theory*. Ed. by Shai Shalev-Shwartz and Ingo Steinwart. Vol. 30. Proceedings of Machine Learning Research. Princeton, NJ, USA: PMLR, Dec. 2013, pp. 1046-1066.

[Bre+21] Matthew Brennan, Guy Bresler, Samuel B Hopkins, Jerry Li, and Tselil Schramm. "Statistical query algorithms and low-degree tests are almost equivalent". In: *Proceedings of Thirty Fourth Conference on Learning Theory*. Ed. by Mikhail Belkin and Samory Kpotufe. Vol. 134. Proceedings of Machine Learning Research. PMLR, 15-19 Aug 2021, pp. 774-774.

[CGV25a] Alexandra Carpentier, Christophe Giraud, and Nicolas Verzelen. "Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities". In: *arXiv preprint arXiv:2509.15822* (2025).

[CGV25b] Alexandra Carpentier, Christophe Giraud, and Nicolas Verzelen. "Phase Transition for Stochastic Block Model with more than $\sqrt{n}$ Communities (II)". In: *arXiv preprint arXiv:2511.21526* (2025).

[Chi+25] Byron Chin, Elchanan Mossel, Youngtak Sohn, and Alexander S. Wein. "Stochastic block models with many communities and the Kesten-Stigum bound - extended abstract". In: *Proceedings of Thirty Eighth Conference on Learning Theory*. Ed. by Nika Haghtalab and Ankur Moitra. Vol. 291. Proceedings of Machine Learning Research. PMLR, 30 Jun-04 Jul 2025, pp. 1253-1258.

[CM23] Tony Cai and Rong Ma. "Matrix reordering for noisy disordered matrices: Optimality and computationally efficient algorithms". In: *IEEE Transactions on Information Theory* (2023).

[Dec+11] Aurelien Decelle, Florent Krzakala, Cristopher Moore, and Lenka Zdeborová. "Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications". In: *Phys. Rev. E* 84 (6 Dec. 2011), p. 066106.

[Din+24] Yunzi Ding, Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. "Subexponential-time algorithms for sparse PCA". In: *Foundations of Computational Mathematics* 24.3 (2024), pp. 865-914.

[Din+25] Jingqiu Ding, Yiding Hua, Lucas Slot, and David Steurer. "Low degree conjecture implies sharp computational thresholds in stochastic block model". In: *arXiv preprint arXiv:2502.15024* (2025).

[DM15] Yash Deshpande and Andrea Montanari. "Finding hidden cliques of size $\sqrt{N/e}$ in nearly linear time". In: *Foundations of Computational Mathematics* 15.4 (2015), pp. 1069-1128.

[DMW25] Abhishek Dhawan, Cheng Mao, and Alexander S. Wein. "Detection of Dense Subhypergraphs by Low-Degree Polynomials". In: *Random Structures & Algorithms* 66.1 (2025), e21279. eprint: https://onlinelibrary.wiley.com/doi/pdf/10.1002/rsa.21279.

[EGV24] Bertrand Even, Christophe Giraud, and Nicolas Verzelen. "Computation-information gap in high-dimensional clustering". In: *Proceedings of Thirty Seventh Conference on Learning Theory*. Ed. by Shipra Agrawal and Aaron Roth. Vol. 247. Proceedings of Machine Learning Research. PMLR, 30 Jun-03 Jul 2024, pp. 1646-1712.
[EGV25a] Bertrand Even, Christophe Giraud, and Nicolas Verzelen. "Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables". In: arXiv preprint arXiv:2507.07946 (2025). arXiv: 2507.07946 [math.ST].

[EGV25b] Bertrand Even, Christophe Giraud, and Nicolas Verzelen. "Computational lower bounds in latent models: clustering, sparse-clustering, biclustering". In: arXiv preprint arXiv:2506.13647 (2025). arXiv: 2506.13647 [math.ST].

[EH25] Dor Elimelech and Wasim Huleihel. "Detecting arbitrary planted subgraphs in random graphs". In: arXiv preprint arXiv:2503.19069 (2025).

[FMR19] Nicolas Flammarion, Cheng Mao, and Philippe Rigollet. "Optimal rates of statistical seriation". In: Bernoulli 25.1 (2019), pp. 623-653.

[Gam21] David Gamarnik. "The overlap gap property: A topological barrier to optimizing over random structures". In: Proceedings of the National Academy of Sciences 118.41 (2021), e2108492118.

[GJW24] David Gamarnik, Aukosh Jagannath, and Alexander S Wein. "Hardness of random optimization problems for Boolean circuits, low-degree polynomials, and Langevin dynamics". In: SIAM Journal on Computing 53.1 (2024), pp. 1-46.

[Hop+17] Samuel B. Hopkins, Pravesh K. Kothari, Aaron A. Potechin, Prasad Raghavendra, Tselil chramm, and David Steurer. "The Power of Sum-of-Squares for Detecting Hidden Structures". In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). Los Alamitos, CA, USA: IEEE Computer Society, Oct. 2017, pp. 720-731.

[Hop18] Samuel Hopkins. "Statistical inference and the sum of squares method". PhD thesis. Cornell University, 2018.

[HS17] Samuel B. Hopkins and David Steurer. "Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems". In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 2017, pp. 379-390.

[Kea98] Michael Kearns. "Efficient noise-tolerant learning from statistical queries". In: Journal of the ACM (JACM) 45.6 (1998), pp. 983-1006.

[KMW24] Dmitriy Kunisky, Cristopher Moore, and Alexander S Wein. "Tensor cumulants for statistical inference on invariant distributions". In: 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS). IEEE. 2024, pp. 1007-1026.

[Kot+23] Pravesh Kothari, Santosh S Vempala, Alexander S Wein, and Jeff Xu. "Is planted coloring easier than planted clique?" In: The Thirty Sixth Annual Conference on Learning Theory. PMLR. 2023, pp. 5343-5372.

[Kun24] Dmitriy Kunisky. "Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models". In: arXiv preprint arXiv:2412.21155 (2024).

[KWB19] Dmitriy Kunisky, Alexander S Wein, and Afonso S Bandeira. "Notes on computational hardness of hypothesis testing: Predictions using the low-degree likelihood ratio". In: ISAAC Congress (International Society for Analysis, its Applications and Computation). Springer. 2019, pp. 1-50.

[LG24] Yuetian Luo and Chao Gao. "Computational lower bounds for graphon estimation via low-degree polynomials". In: The Annals of Statistics 52.5 (2024), pp. 2318-2348.

[Li25] Zhangsong Li. "Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs". In: arXiv preprint arXiv:2502.09832 (2025).

[Mas14] Laurent Massoulié. "Community detection thresholds and the weak Ramanujan property". In: Proceedings of the forty-sixth annual ACM symposium on Theory of computing. 2014, pp. 694-703.

[MW25] Andrea Montanari and Alexander S Wein. "Equivalence of approximate message passing and low-degree polynomials in rank-one matrix estimation". In: Probability Theory and Related Fields 191.1 (2025), pp. 181-233.
[MWZ23] Cheng Mao, Alexander S Wein, and Shenduo Zhang. “Detection-recovery gap for planted dense cycles”. In: The Thirty Sixth Annual Conference on Learning Theory. PMLR. 2023, pp. 2440–2481.

[Rus+22] Cynthia Rush, Fiona Skerman, Alexander S Wein, and Dana Yang. “Is it easier to count communities than find them?” In: arXiv preprint arXiv:2212.10872 (2022).

[Sem24] Guilhem Semerjian. “Matrix denoising: Bayes-optimal estimators via low-degree polynomials”. In: Journal of Statistical Physics 191.10 (2024), p. 139.

[SW22] Tselil Schramm and Alexander S Wein. “Computational barriers to estimation from low-degree polynomials”. In: The Annals of Statistics 50.3 (2022), pp. 1833–1858.

[SW25] Youngtak Sohn and Alexander S. Wein. “Sharp Phase Transitions in Estimation with Low-Degree Polynomials”. In: Proceedings of the 57th Annual ACM Symposium on Theory of Computing (2025), pp. 891–902. arXiv: 2502.14407 [math.ST].

[Wei25] Alexander S. Wein. “Computational Complexity of Statistics: New Insights from Low-Degree Polynomials”. In: arXiv preprint arXiv:2506.10748 (2025). arXiv: 2506.10748 [math.ST].

A Proof of the almost orthonormality results (Theorems 7.1 and 7.2)

We show simultaneously both theorems. Define the symmetric Gram matrix $\Gamma$ of size $|G_{\le D}| + 1$ associated to the basis $(1, (\Psi_G)_{G \in G_{\le D}})$ by $\Gamma_{G^{(1)}, G^{(2)}} := \mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}]$ for any $(G^{(1)}, G^{(2)}) \in G_{\le D}$, $\Gamma_{1,1} = 1$, and $\Gamma_{1,G} := \mathbb{E}[\Psi_G] = 0$. Write $I$ for the identity matrix. In order to establish the result, it suffices to bound the operator norm of $\|\Gamma - I\|_{op}$. The key step of the proof is to control each entry of the matrix $\Gamma$. Recall the distance $d(.,.)$ defined in (37).

**Proposition A.1.** Consider any $D \ge 2$. Under *Independent-Sampling*, assume that Conditions *C-Moment*, *C-Variance* and *C-Signal* are fulfilled and that the constant $c_s > 4$ is large compared to the other other ones. Under *Permutation Sampling*, assume that Conditions *C-Moment*, *C-Variance*, *C-Variance-Permutation*, and *C-Signal* are fulfilled with a constant $c_s > 4$ that is large enough.

There exist two positive constants $c$ and $c'$ depending on those arising in Conditions *C-Variance* and *C-Moment* (and *C-Variance-Permutation* in the second case) such that the following holds for any templates $G^{(1)}, G^{(2)} \in G_{\le D}$.

$$1 \text{ if } G^{(1)} \neq G^{(2)}: \qquad |\mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}]| \leq cD^{-c_s d(G^{(1)}, G^{(2)})}, \qquad (63)$$

$$2 \text{ and if } G^{(1)} = G^{(2)}: \qquad |\mathbb{E}[(\Psi_{G^{(1)}})^2] - 1| \leq c' D^{-c_s}. \qquad (64)$$

It is easy to conclude from this last proposition. Since the row and the column of $\Gamma$ corresponding to the element 1 of the basis is zero outside the diagonal term, we only have to consider the submatrix of $\Gamma$ corresponding to $G$, $G \in G_{\le D}$. Since the operator norm of a symmetric matrix is bounded by the maximum $\ell_1$ norm of its rows, we have

$$\|\Gamma - I\|_{op} \le \max_{G^{(1)}} \left\{ |\Gamma_{G^{(1)}, G^{(1)}} - 1| + \sum_{G^{(2)} \in G_{\le D}, G^{(2)} \ne G^{(1)}} |\Gamma_{G^{(1)}, G^{(2)}}| \right\}.$$

To bound the latter sum, we use that, for a fixed template $G_{\le D}^{(1)}$, the number of templates $G_{\le D}^{(2)}$ such that $d(G^{(1)}, G^{(2)}) = u$ is bounded by $(u + D)^{2u}$. When $G^{(2)} \in \tilde{G}_{\le D}$ differs from $G^{(1)}$, it is, by definition,
not-isomorphic to $G^{(2)}$ and $d(G^{(1)}, G^{(2)}) \ge 1$. It then follows from Proposition A.1 that

$$
\begin{align*}
\sum_{G^{(2)} \in \mathcal{G}_{\le D}, G^{(2)} \neq G^{(1)}} |\Gamma_{G^{(1)}, G^{(2)}}| &\le \sum_{G^{(2)} \in \mathcal{G}_{\le D}, G^{(2)} \neq G^{(1)}} cD^{-c_s} d(G^{(1)}, G^{(2)}) \\
&\le \sum_{2D \ge u \ge 1} |\{G^{(2)} : d(G^{(1)}, G^{(2)}) = u\}| cD^{-c_s u} \\
&\le \sum_{2D \ge u \ge 1} (u + D)^{2u} cD^{-c_s u} \\
&\le \sum_{2D \ge u \ge 1} c' D^{-(c_s - 6)u} \le cD^{-c_s/2},
\end{align*}
$$

since $D \ge 2$ provided we have $c_s \ge 12$. Applying the second part of Proposition A.1, we conclude that

$$
\|\Gamma - I\|_{op} \le cD^{-c_s/2} + c' D^{-c_s}.
$$

A.1 Proof of Proposition A.1

We first state the following lemmas, whose proof are postponed to the end of the subsection. Given two templates $G^{(1)}$, $G^{(2)}$ and labeling $\pi^{(1)}$ and $\pi^{(2)}$, recall that $G_{\Delta}$ stands for the labelled graph corresponding to a symmetric difference between $\pi^{(1)}[G^{(1)}]$ and $\pi^{(2)}[G^{(2)}]$. Also, recall the collection $\mathcal{M}^*$ of matchings of two templates $G^{(1)}$ and $G^{(2)}$ that does not lead to any pure connected component.

**Lemma A.2.** *Consider both *Independent-Sampling* and *Permutation Sampling*. Suppose that Conditions *C-Moment* and *C-Variance* are fulfilled and that *C-Signal* is fulfilled with a constant $c_s$ large enough compared the constants arising in the other conditions.*

1. Let $G^{(1)}, G^{(2)} \in \mathcal{G}_{\le D}$ be two templates and let $\mathbf{M} \in \mathcal{M}^* \setminus \mathcal{M}_{\text{PM}}$ be a matching. For any $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$, we have $|\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}]| \le \psi[G_{\Delta}]$ where

$$
\psi[G_{\Delta}] := c_{v,2} D^{2|\overline{p}|} \mathbb{E}^{|E_{\cap}|} (D^{c_{v,1}} \lambda)^{|E_{\Delta}|} \left( \frac{D^{1+c_{v,1}\vee c_m} k}{n} \right)^{|V_{\Delta}| - \#CC_{\Delta}} . \quad (65)
$$

2 Also, for any template $G = (V, E) \in \mathcal{G}_{\le D}$ and any $\pi \in \Pi_V$, we have

$$
|\mathbb{E}[\overline{P}_{G,\pi}^2] - \overline{q}^{|E|}| \leq [2c_{v,2}D^{4+c_{v,1}\vee c_m}\frac{k}{n} + c_{v,3}D^{-c_{v,4}}]\overline{q}^{|E|}.
$$

**Lemma A.3.** Let $G^{(1)}, G^{(2)} \in \mathcal{G}_{\le D}$ be two templates and let $\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}^*$ be a matching with a least one pure connected component. We consider two cases:

1 Under *Independent-Sampling*, we have $\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] = 0$. By convention, we define $\psi(G_{\Delta}) = 0$.

2 Under *Permutation Sampling*, we assume that Conditions *C-Moment*, *C-Variance*, and *C-Variance-Permutation* are fullfilled and that *C-Signal* is fulfilled with a constant $c_s$ large enough. Then, we have

$$
|\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}]| \leq \psi[G_{\Delta}],
$$

where we define in this case

$$
\psi[G_{\Delta}] := c_0 D^{c_1} \overline{p}^{|E_{\cap}|} (D^{c_1} \lambda)^{|E_{\Delta}|} \left( \frac{D^{c_1} k}{n} \right)^{|V_{\Delta}| - \#CC_{\Delta}} \left[ c_0 \frac{D^{c_1}}{\sqrt{n}} \right]^{\#CC_{\text{pure}}} , \quad (66)
$$

for some constants $c_0$ and $c_1$ that only depend on those in *C-Moment*, *C-Variance*, and *C-Variance-Permutation*.

Provided that the constant $c_s$ arising in Condition C-Signal is large enough, the conditions of the above lemma are fulfilled. Fix any template $G^{(1)}$ and $G^{(2)}$ in $\mathcal{G}_{\le D}$.
**Step 1: Sum of covariances.** We distinguish perfect matchings and non-perfect matchings — see Section 5 for definitions. We start from the decomposition

$$
\begin{align*}
\mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}] &= \frac{1}{\sqrt{\mathbb{V}(G^{(1)}) \mathbb{V}(G^{(2)})}} \sum_{\pi^{(1)} \in \Pi_{\mathbb{V}(1)}, \pi^{(2)} \in \Pi_{\mathbb{V}(2)}} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \\
&= \frac{1}{\sqrt{\mathbb{V}(G^{(1)}) \mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \\
&= \frac{1}{\sqrt{\mathbb{V}(G^{(1)}) \mathbb{V}(G^{(2)})}} \left[ \sum_{M \in \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \right. \\
&\qquad \left. + \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \right].
\end{align*}
$$

If $G^{(1)} \neq G^{(2)}$, there does not exist any perfect matching — see Section 5. Hence, we have

$$
\left| \mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}] \right| \le \left| \frac{1}{\sqrt{\mathbb{V}(G^{(1)}) \mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \right| . \quad (67)
$$

Conversely, if $G^{(1)} = G^{(2)}$, the number of perfect matchings is, by definition, the size of the automorphism
group, that is $|\mathcal{M}_{PM}| = |\mathrm{Aut}(G^{(1)})|$. Besides, for such a perfect matching $\mathbf{M}$, the number of possible labelings
is simply $|\Pi(\mathbf{M})| = \frac{n!}{(n-|\mathbb{V}^{(1)}|)!}$. By Lemma A.2, and the definition (18) of $\mathbb{V}(G^{(1)})$, we get

$$
\begin{align}
|\mathbb{E}[\Psi_{G^{(1)}} \Psi_{G^{(2)}}] - 1| &\le c \left[ \frac{kD^{4+c_{v,1}}c_m}{n} + D^{-c_{v,4}} \right] + \left| \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \right| \nonumber \\
&\le c_0 D^{-c_s} + \left| \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \right|, \tag{68}
\end{align}
$$

where we used Condition **C-Signal** and that $c_s$ is large enough in the last line and where $c$ and $c_0$ are
positive constants that depend on the constant arising in the conditions. Hence, we just need to bound

$$
A := \left| \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] \right| . \quad (69)
$$

In light of (67) and (68), it suffices to establish that

$$
A \leq c'' D^{-c_s} (d(G^{(1)}, G^{(2)}) \vee 1) . \quad (70)
$$

We start from Lemmas A.2 and A.3.

$$
A \le \frac{1}{\sqrt{\mathbb{V}(G^{(1)})\mathbb{V}(G^{(2)})}} \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)} \psi[G_{\Delta}] .
$$

For fixed $(G^{(1)}, G^{(2)}, \mathbf{M})$, the number $|\Pi(\mathbf{M})|$ of possible labelings that are compatible with $\mathbf{M}$ is
$$ \frac{n!}{(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))!} $$
. It then follows from the definition (18) of $\mathbb{V}(G)$ that

$$
A \le \frac{1}{\overline{q}^{|E^{(1)}|+|E^{(2)}|/2} \sqrt{|\mathrm{Aut}(G^{(1)})||\mathrm{Aut}(G^{(2)})|}} \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} \frac{\sqrt{(n-|V^{(1)}|)!(n-|V^{(2)}|)!}}{(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))!} \psi[G_{\Delta}].
$$
Since $|\mathbf{M}| \le |V^{(1)}| \wedge |V^{(2)}|$, it follows that $(n - |V^{(1)}|)![(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))]^{-1} \le n^{|V^{(2)}|-|\mathbf{M}|}$ and $(n - |V^{(2)}|)![(n - (|V^{(1)}| + |V^{(2)}| - |\mathbf{M}|))]^{-1} \le n^{|V^{(1)}|-|\mathbf{M}|}$. We arrive at

$$A \le \frac{1}{\bar{q}^{(|E^{(1)}|+|E^{(2)}|)/2} \sqrt{|\mathrm{Aut}(G^{(1)})||\mathrm{Aut}(G^{(2)})|}} \sum_{\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\mathrm{PM}}} n^{(|V^{(1)}|+|V^{(2)}|)/2 - |\mathbf{M}|} \psi[G_{\Delta}] \\ \le \frac{1}{\bar{q}^{(|E^{(1)}|+|E^{(2)}|)/2} \sqrt{|\mathrm{Aut}(G^{(1)})||\mathrm{Aut}(G^{(2)})|}} \sum_{\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\mathrm{PM}}} n^{(|U^{(1)}|+|U^{(2)}|)/2} \psi[G_{\Delta}],$$

where we used Equation (34) in the last line and we recall that $U^{(1)}$ and $U^{(2)}$ are the sets of nodes in $G^{(1)}$ and $G^{(2)}$ that are not matched — see again Section 5 for definitions.

**Step 2: Building up on Lemmas A.2 and A.3.** Define $A_0 = A\sqrt{|\mathrm{Aut}(G^{(1)})||\mathrm{Aut}(G^{(2)})|}$. Also, we write $U = |U^{(1)}| + |U^{(2)}|$. Recall the definitions of $\psi[G_{\Delta}]$ from Lemmas A.2 and A.3. Equipped with this notation, we have

$$\psi[G_{\Delta}] := c_0 D^{c_1} \bar{p}^{|E^{(1)}|} (D^{c_1} \lambda)^{|E_{\Delta}|} \left(\frac{D^{c_1} k}{n}\right)^{|V_{\Delta}| - \#CC_{\Delta}} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^{\#CC_{\mathrm{pure}}},$$

with the convention $(1/0)^0 = 0$ and where $c_0$ and $c_1$ depend on $c_{\mathbf{m}}$, and $c_{v,1}, \dots, c_{v,4}$, and possibly $c_{\mathrm{vd},1}$, $c_{\mathrm{vd},2}$.

$$A_0 \le c_0 D^{c_1} \sum_{\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\mathrm{PM}}} n^{U/2} \left(\frac{\bar{p}}{\bar{q}}\right)^{(|E^{(1)}|+|E^{(2)}|)/2} \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{p}}}\right)^{|E_{\Delta}|} \left(\frac{D^{c_1} k}{n}\right)^{|V_{\Delta}| - \#CC_{\Delta}} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^{\#CC_{\mathrm{pure}}}. $$

By Condition C-Signal and definition (59), we have

$$\frac{\bar{p}}{\bar{q}} = 1 + \frac{\lambda(1 - 2q)}{q(1 - q)} \le 1 + \frac{\lambda}{q(1 - q)} \le 1 + \frac{D^{-8c_s}}{1 - q} \le 1 + 2D^{-8c_s} \le 1 + D^{-4}. \quad (71)$$

In the last inequality, we used that $c_s > 1$ and that $D \ge 2$. As a consequence $(1 + D^{-4})^{2D} \le 2$ and we deduce that

$$A_0 \le 2c_0 D^{c_1} \sum_{\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\mathrm{PM}}} n^{U/2} \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E_{\Delta}|} \left(\frac{D^{c_1} k}{n}\right)^{|V_{\Delta}| - \#CC_{\Delta}} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^{\#CC_{\mathrm{pure}}} \\ := 2c_0 D^{c_1} \sum_{\mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\mathrm{PM}}} A_{\mathbf{M}}. \qquad (72)$$

**Step 3: Relying on the graph properties of $G_{\Delta}$ for $A_{\mathbf{M}}$.** Let us decompose $(G^{(1)}, G^{(2)}, \mathbf{M})$ into $(G'^{(1)}, G'^{(2)}, \mathbf{M}, G^{(3)})$ where, in $G'^{(1)}$ (resp. $G'^{(2)}$), we have removed all the pure connected components of $G^{(1)}$ (resp. $G^{(2)}$) and we gather all these connected components in $G^{(3)}$. For $(G'^{(1)}, G'^{(2)}, \mathbf{M})$, we can then define the number $U'$ of unmatched nodes and the intersection graph $G'_{\Delta}$ with $CC'_{\Delta}$ connected components. Equipped with this notation, we have $\#CC_{\mathrm{pure}} = \#CC_{G^{(3)}}, |V_{\Delta}| = |V'_{\Delta}| + |V^{(3)}|, \#CC_{\Delta} = \#CC'_{\Delta} + \#CC_{G^{(3)}},$
and $U = U' + |V^{(3)}|$. Then, we reorganize $A_M$ as follows

$$
\begin{align*}
A_M &= \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E'_\Delta|} \left(D^{c_1} \frac{k}{\sqrt{n}}\right)^{|U'|} \left(D^{c_1} \frac{k}{n}\right)^{|V'_\Delta|-|U'|-\#CC'_\Delta} \\
&\qquad \cdot \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E^{(3)}|} \left(D^{c_1} \frac{k}{\sqrt{n}}\right)^{|V^{(3)}|-\#CC_{G^{(3)}}} (c_0 D^{c_1})^{\#CC_{G^{(3)}}} \\
&\stackrel{(a)}{\le} \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E'_\Delta|} \left(D^{c_1} \frac{k}{\sqrt{n}}\right)^{|U'|} \left(D^{c_1} \frac{k}{n}\right)^{|M_{SM}|-\#CC'_\Delta} \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E^{(3)}|} \left(\frac{c_0 D^{2c_1} k}{\sqrt{n}}\right)^{|V^{(3)}|-\#CC_{G^{(3)}}} \\
&\le \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E'_\Delta|-|U'|} \left(\frac{D^{2c_1} k \lambda}{\sqrt{n \bar{q}}}\right)^{|U'|} \left(\frac{D^{c_1} k}{n}\right)^{|M_{SM}|-\#CC'_\Delta} \\
&\qquad \cdot \left(D^{c_1} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E^{(3)}|-|V^{(3)}|+\#CC_{G^{(3)}}} \left(\frac{c_0 D^{3c_1} k \lambda}{\sqrt{n \bar{q}}}\right)^{|V^{(3)}|-\#CC_{G^{(3)}}},
\end{align*}
$$

where we used in (a) that $|V'_\Delta| = |U'| + |M_{SM}|$ as the nodes in $G'_\Delta$ are either unmatched or semi-matched and that $|V^{(3)}| \ge 2\#CC_{G^{(3)}}$ as all connected components have at least two nodes. Let us show that all the exponents in the above bound $A_M$ are nonnegative. For any graph $G = (V, E)$, we have $|E|-|V|+\#CC_G \ge 0$ and $|V| \ge \#CC_G$.

**Lemma A.4.** We have

$$|\mathbf{M}_{\mathrm{SM}}| \geq \#CC'_{\Delta}, \quad |E'_{\Delta}| \geq U' .$$

Hence, relying on Condition C-Signal, we obtain

$$A_M \le D^{-6c_s [|E'_\Delta| + |E^{(3)}| + |M_{SM}| - \#CC'_\Delta]} . \quad (73)$$

Since $|M_{SM}| \ge \#CC'_\Delta$ and $|E'_\Delta| + |E^{(3)}| = |E_\Delta| \ge d(G^{(1)}, G^{(2)}) \lor 1$ by definition (37) of $d(\cdot, \cdot)$, it follows that

$$|E'_{\Delta}| + |E^{(3)}| + |M_{SM}| - \#CC'_{\Delta} \ge d(G^{(1)}, G^{(2)}) \lor 1 .$$

Also, since each connected component of $G^{(3)}$ has at least two nodes, we deduce that $|E^{(3)}| \ge |V^{(3)}|/2$. Since $|E'_\Delta| \ge U'$ and $U' + |M_{SM}| = |V'_\Delta| \ge 2\#CC'_\Delta$ as each connected component of $G'_\Delta$ has at least two nodes, we conclude that

$$|E'_{\Delta}| + |E^{(3)}| + |M_{SM}| - \#CC'_{\Delta} \ge \frac{|V^{(3)}|}{2} + \frac{U' + |M_{SM}|}{2} = \frac{U + |M_{SM}|}{2} .$$

Gathering the two previous bounds in (73), we get

$$A_M \le D^{-3c_s [[U+|M_{SM}|] \vee d(G^{(1)}, G^{(2)}) \vee 1]} .$$

Coming back to (72) and using again that $c_s$ is large enough, we get

$$A_0 \le 2c_0 \sum_{M \in \mathcal{M} \setminus \mathcal{M}_{PM}} (D^{-2c_s})^{|U+|M_{SM}|} \vee d(G^{(1)}, G^{(2)}) \vee 1 .$$

**Step 4: Summing over shadows.** Recall the definition of shadows and of $M_{shadow}$ in Section 5. We now regroup the sum inside $A$ by enumerating all possible matchings that are compatible with a specific shadow. Recall also the definition of $A_0$. We get

$$
A \le \frac{2c_0}{\sqrt{|\mathrm{Aut}(G^{(1)})||\mathrm{Aut}(G^{(2)})|}} \sum_{\substack{U^{(1)} \subseteq V^{(1)}, \\ U^{(2)} \subseteq V^{(2)}, \\ \underline{M} \in \mathcal{M}_{\mathrm{shadow}}(U^{(1)}, U^{(2)}, \underline{M})}} \sum_{M \in \mathcal{M}_{\mathrm{shadow}}(U^{(1)}, U^{(2)}, \underline{M})} (D^{-2c_s})^{|U+|M_{SM}|} \vee d(G^{(1)}, G^{(2)}) \vee 1 .
$$

We have the following control for $M_{shadow}$.
**Lemma A.5.** For any $U_1, U_2$, and $\mathbf{M}$, we have

$$ |\mathcal{M}_{\text{shadow}}(U_1, U_2, \mathbf{M})| \le \min(|\text{Aut}(G^{(1)})|, |\text{Aut}(G^{(2)})|) . \quad (74) $$

Observe that two matchings $\mathbf{M}$ and $\mathbf{M}'$ that belong to $\mathcal{M}_{\text{shadow}}(U^{(1)}, U^{(2)}, \mathbf{M})$ have the same difference graph $G_{\Delta}$ and have a common value of $|\mathbf{M}_{\text{SM}}|$. Hence, it follows from Lemma A.5 that

$$ A \le 2c_0 \sum_{\substack{U^{(1)} \subset V^{(1)}, U^{(2)} \subset V^{(2)}, \\ \mathbf{M} \in \mathcal{M} \setminus \mathcal{M}_{\text{PM}}}} (D^{-2c_s})^{[U+|\mathbf{M}_{\text{SM}}|] \vee d(G^{(1)}, G^{(2)}) \vee 1} . $$

Now enumerating over all possible sets $U^{(1)}, U^{(2)}, \mathbf{M}$ that have respective cardinality $u_1, u_2$, and $m$ and noting that the size these collections are respectively bounded by $(2D)^{u_1}, (2D)^{u_2}$ and $(2D)^{2m}$, we conclude that

$$ A \le 2c_0 \sum_{u_1, u_2, m \ge 0} (2D)^{u_1+u_2+2m} (D^{-2c_s})^{[u_1+u_2+m] \vee d(G^{(1)}, G^{(2)}) \vee 1} \le c'' D^{-c_s} d(G^{(1)}, G^{(2)}) \vee 1, $$

assuming that $c_s \ge 4$ and $D \ge 2$. We have established (70) and this concludes the proof.

## A.2 Proof of Lemma A.2

First, we consider some $\mathbf{M} \in \mathcal{M}^* \setminus \mathcal{M}_{\text{PM}}$. Since $\mathbf{M}$ belongs $\mathcal{M}^*$, the matching $\mathbf{M}$ does not let any connected component of $\pi^{(1)}[G^{(1)}]$ and $\pi^{(2)}[G^{(2)}]$ be unmatched. Let us decompose $G^{(1)} = (G_1^{(1)}, \dots, G_{cc_1}^{(1)})$ and $G^{(2)} = (G_1^{(2)}, \dots, G_{cc_2}^{(2)})$ into their $cc_1$ and $cc_2$ connected components. Given a set $S_1 \subset [cc_1]$, define $G_{-S_1}^{(1)}$ as the subgraph of $G^{(1)}$ such that we have removed the connected components corresponding to $S_1$. Write $A := |\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}]|$. By definition, we have

$$ \begin{aligned} |A| &= \left| \sum_{S_1 \subseteq [cc_1]} \sum_{S_2 \subseteq [cc_2]} \mathbb{E} \left[ P_{G_{-S_1}^{(1)}, \pi^{(1)}} P_{G_{-S_2}^{(2)}, \pi^{(2)}} \right] \prod_{i \in S_1} \mathbb{E}[P_{G_i^{(1)}, \pi^{(1)}}] \prod_{i \in S_2} \mathbb{E}[P_{G_i^{(2)}, \pi^{(2)}}] (-1)^{|S_1|+|S_2|} \right| \\ &\le \sum_{s_1=0}^{cc_1} \sum_{s_2=0}^{cc_2} D^{s_1+s_2} \max_{S_1:|S_1|=s_1, S_2:|S_2|=s_2} \left| \mathbb{E} \left[ P_{G_{-S_1}^{(1)}, \pi^{(1)}} P_{G_{-S_2}^{(2)}, \pi^{(2)}} \right] \prod_{i \in S_1} \mathbb{E}[P_{G_i^{(1)}, \pi^{(1)}}] \prod_{i \in S_2} \mathbb{E}[P_{G_i^{(2)}, \pi^{(2)}}] \right| . \end{aligned} $$

Then, we apply C-Moment as well as the first part of C-Variance. We write $G_{\Delta;-S_1;-S_2}$ for the symmetric difference graph associated to $G_{-S_1}^{(1)}$ and $G_{-S_2}^{(2)}$. We get

$$ \begin{aligned} |A| &\le \sum_{s_1=0}^{cc_1} \sum_{s_2=0}^{cc_2} D^{s_1+s_2} \max_{S_1:|S_1|=s_1, S_2:|S_2|=s_2} c_{v,2}(D^{c_{v,1}}\lambda)^{|E_{\Delta,-S_1,-S_2}|} \overline{p}^{|E_{\cap,-S_1,-S_2}|} \left( D^{c_{v,1}} \frac{k}{n} \right)^{|V_{\Delta,-S_1,-S_2}| - \#CC_{\Delta,-S_1,-S_2}} \\ &\qquad \prod_{a=1}^2 \prod_{i \in S_a} (D^{c_a}\lambda)^{|E_i^{(a)}|} \left( D^{c_a} \frac{k}{n} \right)^{|V_i^{(a)}| - 1} \\ &\le \sum_{s_1=0}^{cc_1} \sum_{s_2=0}^{cc_2} D^{s_1+s_2} \max_{S_1:|S_1|=s_1, S_2:|S_2|=s_2} c_{v,2}(D^{c_{v,1} \vee c_a}\lambda)^{|E_{\Delta}|} \overline{p}^{|E_{\cap}|} \left( D^{c_{v,1} \vee c_a} \frac{k}{n} \right)^R, \end{aligned} $$

where we used in the last line that $D^{c_{v,1} \vee c_a} \lambda \le \overline{p} \le 1$ by Equation (59) and Condition C-Signal with $c_s > 0$ sufficiently large and where

$$ R := |V_{\Delta,-S_1,-S_2}| - \#CC_{\Delta,-S_1,-S_2} + \sum_{i \in S_1} (|V_i^{(1)}| - 1) + \sum_{i \in S_2} (|V_i^{(2)}| - 1) . \quad (75) $$

Since the number of nodes $|V_i^{(1)}|$ of each connected component is at least of 2, we easily check that

$$ R \ge \sum_{i \in S_1} (|V_i^{(1)}| - 1) + \sum_{i \in S_2} (|V_i^{(2)}| - 1) \ge |S_1| + |S_2| . $$
Coming back to A, we arrive to the bound

$$|A| \leq D^2 \max_{S_1, S_2} (D^{c_{v,1} \vee c_m} \lambda)^{|E_\Delta|} |\bar{p}|^{|E_\cap|} \left(D^{1+c_{v,1} \vee c_m} \frac{k}{n}\right)^R .$$

Again, by Condition C-Signal with $c_s > 0$ sufficiently large, we have $D^{1+c_{v,1} \vee c_m} k \leq n$. Hence, it remains to lower bound R.

**Lemma A.6.** The quantity R defined in (75) satisfies $R \geq V_\Delta - \#CC_\Delta$.

Gathering this lemma with our previous bound, we arrive at

$$|\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}]| \leq \psi[G_\Delta], \quad (76)$$

in the specific case where $M \in \mathcal{M}^* \setminus \mathcal{M}_{PM}$, that is when $\#CC_{pure} = \emptyset$. We have proved the first part of the lemma.

Let us turn to $\mathbb{E}[\overline{P}_{G, \pi}^2]$. We start as in the first step of this proof. We decompose $G = (G_1, \dots, G_{cc})$ into its cc connected components. First, we bound $A := \mathbb{E}[\overline{P}_{G, \pi}^2] - \mathbb{E}[P_{G, \pi}^2]$. Given $S \subset [cc]$, we write $P_{G_{-S}, \pi}$ as the polynomial associated to the graph where we have removed the connected components in S. Opening the expression of $\overline{P}$ we derive that

$$|A| \leq \left| \sum_{S_1, S_2 \subseteq [cc]: S_1 \cup S_2 \neq \emptyset} \mathbb{E}[P_{G_{-S_1}, \pi} P_{G_{-S_2}, \pi}] \prod_{i \in S_1} \mathbb{E}[P_{G_i, \pi}] \prod_{i \in S_2} \mathbb{E}[P_{G_i, \pi}] (-1)^{|S_1|+|S_2|} \right| \\ \leq \sum_{s_1, s_2 = 0: s_1+s_2>0}^{cc} D^{s_1+s_2} \max_{S_1:|S_1|=s_1, S_2:|S_2|=s_2} |\mathbb{E}[P_{G_{-S_1}, \pi} P_{G_{-S_2}, \pi}] \prod_{i \in S_1} \mathbb{E}[P_{G_i, \pi}] \prod_{i \in S_2} \mathbb{E}[P_{G_i, \pi}]| .$$

Then, we apply C-Moment as well as the first part of C-Variance. We write $G_{\Delta;-S_1;-S_2}$ (resp. $G_{\cap;S_1;S_2}$) for the symmetric difference graph (resp. intersection graph) associated to $G_{-S_1}$ and $G_{-S_2}$. We get

$$|A| \leq \sum_{s_1, s_2: s_1+s_2>0} D^{s_1+s_2} \max_{S_1:|S_1|=s_1, S_2:|S_2|=s_2} c_{v,2} (D^{c_{v,1}} \lambda)^{|E_\Delta,-S_1,-S_2|} \frac{|\bar{p}|^{|E_\cap;-S_1,-S_2|}}{|\bar{p}|^{|E_\cap;-S_1,-S_2|} - \#CC_{\Delta,-S_1,-S_2}} \left(D^{c_{v,1}} \frac{k}{n}\right)^{|V_\Delta,-S_1,-S_2| - \#CC_{\Delta,-S_1,-S_2}} \\ \prod_{a=1}^2 \prod_{i \in S_a} (D^{c_m} \lambda)^{|E_i|} \left(D^{c_m} \frac{k}{n}\right)^{|V_i|-1} \\ \leq \sum_{s_1, s_2: s_1+s_2>0} D^{s_1+s_2} \max_{S_1:|S_1|=s_1, S_2:|S_2|=s_2} c_{v,2} \bar{p}^{|E|} \left(D^{c_{v,1} \vee c_m} \frac{k}{n}\right)^{s_1+s_2},$$

where we used Condition C-Signal with $c_s$ large enough to ensure that $D^{c_{v,1} \vee c_m} \frac{k}{n} \leq 1$ and $D^{c_{v,1} \vee c_m} \lambda \leq \bar{p}$ and we used that $|E_\Delta, -S_1, -S_2| + |E_\cap; -S_1, -S_2| + \sum_{a,i} |E_i| \geq |E|$. We have proved in (71) that $\bar{p} \leq \bar{q}(1 + D^{-4})$. Since $|E| \leq D$, we arrive at

$$|\mathbb{E}[\overline{P}_{G, \pi}^2] - \mathbb{E}[P_{G, \pi}^2]| \leq 2c_{v,2}D^{4+c_{v,1} \vee c_m} \frac{k}{n} \bar{q}^{|E|}.$$

Combining this inequality with Condition C-Variance, we conclude that

$$|\mathbb{E}[\overline{P}_{G, \pi}^2] - \bar{q}^{|E|}| \leq \left[ 2c_{v,2} D^{4+c_{v,1} \vee c_m} \frac{k}{n} + c_{v,3} D^{-c_{v,4}} \right] \bar{q}^{|E|}.$$
## A.3 Proof of Lemma A.3

The first statement of the lemma is straightforward. Without loss of the generality, we may assume that there exists a connected component $G'$ of $G^{(1)}$ such that $\pi^{(1)}(V')$ does not intersect $\pi^{(2)}(V^{(2)})$. Writing $\pi'$ for the restriction of $\pi^{(1)}$ to $V'$, $G^{(0)} = (V^{(0)}, E^{(0)})$ for the remainder of $G^{(1)}$ after we have removed $G'$, and $\pi^{(0)}$ for the restriction of $\pi^{(1)}$ to $V^{(0)}$, we get

$$ \overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}} = \overline{P}_{G', \pi'} \overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(2)}, \pi^{(2)}} = [P_{G', \pi'} - \mathbb{E}(P_{G', \pi'})] \overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(2)}, \pi^{(2)}} $$

Since the latent assignments $z_i$ are sampled with replacement, $P_{G', \pi'}$ is independent of $\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(2)}, \pi^{(2)}}$ and it follows that $\mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] = 0$.

The main challenge in the proof is to consider the setting where we sample latent assignments without replacement. Indeed, in this case, polynomials associated to indices are not independent and we have to quantify this dependence. Let $G^{(1)} = (V^{(1)}, E^{(1)})$ and $G^{(2)} = (V^{(2)}, E^{(2)})$ be two templates with at most $D$ edges, $M \in \mathcal{M} \setminus \mathcal{M}^*$ be a matching that leads to a least one connected pure connected component, and let $(\pi^{(1)}, \pi^{(2)}) \in \Pi(M)$. For short, we write $r = \#\text{CC}_{\text{pure}} \ge 1$ for the number of such pure connected components. Then, we enumerate $(G^{(1)}, \pi^{(1)}), \dots, (G^{(r)}, \pi^{(r)})$ these pure connected components and their corresponding labelings. Besides, we write $(G^{(0)}, \pi^{(0)})$ and $(G^{(0)}, \pi^{(0)})$ the remainder of $(G^{(1)}, \pi^{(1)})$ and of $(G^{(2)}, \pi^{(2)})$ after we have removed them. Equipped with this notation, we have the following decomposition

$$ \overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}} = \overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(0)}, \pi^{(0)}} \prod_{a=1}^{r} \overline{P}_{G_a', \pi_a'} $$

To ease the reading, we write, for $a = 1, \dots, r$, $\overline{P}_a$ for $\overline{P}_{G_a', \pi_a'}$ and we define $\overline{P}_0 := \overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(0)}, \pi^{(0)}} - \mathbb{E}[\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(0)}, \pi^{(0)}}]$ as the centered version of $\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(0)}, \pi^{(0)}}$. Then, it follows that

$$ \mathbb{E}[\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}] = \mathbb{E}\left[\prod_{a=0}^{r} \overline{P}_a\right] + \mathbb{E}\left[\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(0)}, \pi^{(0)}}\right] \mathbb{E}\left[\prod_{a=1}^{r} \overline{P}_a\right]. \quad (77) $$

The quantity $\mathbb{E}[\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G^{(0)}, \pi^{(0)}}]$ has been controlled in Lemma A.2 as the graph $G_{\Delta}^{(0)}$ that arises from $(G^{(0)}, \pi^{(0)})$ and $(G^{(0)}, \pi^{(0)})$ does not contain any pure connected component. Since $\sum_{a=1}^{r} |V_a'| + |V_{\Delta}^{(0)}| = |V_{\Delta}|$ and $\sum_{a=1}^{n} |E_a'| + |E_{\Delta}^{(0)}| = |E_{\Delta}|$, we only have to prove that

$$ \mathbb{E}\left[\prod_{a=1}^{r} \overline{P}_a\right] \le c_0 D^{c_1} (D^{c_1} \lambda)^{\sum_{a=1}^{r} |E^{(a)}|} \left(D^{c_1} \frac{k}{n}\right)^{\sum_{a=1}^{r} (|V^{(a)}| - 1)} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^r; \quad (78) $$

$$ \mathbb{E}\left[\prod_{a=0}^{r} \overline{P}_a\right] \le c_0 \overline{p}^{|E|} D^{c_1} (D^{c_1} \lambda)^{|E_{\Delta}|} \left(D^{c_1} \frac{k}{n}\right)^{|V_{\Delta}| - \#\text{CC}_{\Delta}} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^r, \quad (79) $$

for some positive quantities $c_0$ and $c_1$ large enough that depend on the constants in Condition C-Moment, C-Variance, C-Variance-Permutation.

In this proof, $c_0$ and $c_1$ may change from line to line. Importantly, each random variable $\overline{P}_i$ is centered and involves different latent assignments because we sample without replacement. To emphasize these latent assignments, we write $Z_a = \{z_{\pi^{(a)}(v)} : v \in V^{(a)}\}$ for $a = 1, \dots, r$ and we also define $Z_0 = \{z_{\pi^{(0)}(v)} : v \in V^{(0)}\} \cup \{z_{\pi^{(0)}(v)} : v \in V^{(0)}\}$ for the latent assignments involved in $\overline{P}_0$.

We introduce the probability distribution $\mathbb{P}_R$ where, as in $\mathbb{P}$, each $Z_a$ is sampled without replacement but, contrary to $\mathbb{P}$, the $Z_a$'s are sampled independently. Define the event $\mathcal{E}$ (resp. $\mathcal{E}'$) such that all the $Z_a$'s with $a = 1, \dots, r$ (resp. $a = 0, \dots, r$) are distinct. Then, by definition of $\mathbb{E}_R$, we have

$$ \mathbb{E}\left[\prod_{a=1}^{r} \overline{P}_a\right] = \mathbb{P}_R(\mathcal{E}) \mathbb{E}_R\left[\mathbf{1}\{\mathcal{E}\} \prod_{a=1}^{r} \overline{P}_a\right]; \quad (80) $$

$$ \mathbb{E}\left[\prod_{a=0}^{r} \overline{P}_a\right] = \mathbb{P}_R(\mathcal{E}') \mathbb{E}_R\left[\mathbf{1}\{\mathcal{E}\} \prod_{a=0}^{r} \overline{P}_a\right]. \quad (81) $$
Our purpose is therefore to upper bound the latter quantity. We shall prove this in a recursive manner.

In the sequel, we write $[0; r]$ for the set $\{0, 1, \dots, r\}$. Given a partition $\mathcal{B} = (B_1, \dots, B_t)$ of $[r]$ or of $[0; r]$, we define the event $\mathcal{E}_B$ such that, for any group $B \neq B'$ in the partition and any $(i, j) \in B \times B'$, we have $Z_i \cap Z_j = \emptyset$. If $\mathcal{B}$ is the trivial partition (i.e. $|\mathcal{B}| = 1$), we take the convention that the event $\mathcal{E}_B$ is an event of probability one.

Given a subset $B \subset [0; r]$, we define the event $\mathcal{A}_B$ such that, for any $i$ and $i'$ in $B$, there exists a sequence $i_0 = i, i_1, \dots, i_s = i'$ in $B$ such that $Z_{i_t} \cap Z_{i_{t+1}} \neq \emptyset$ for all $t = 0, \dots, s-1$. In other words, if we draw edges between $i$ and $j$ whenever $Z_i \cap Z_j \neq \emptyset$, then, under the event $\mathcal{A}_B$, $B$ is connected. Henceforth, under $\mathcal{A}_B$, we say that the polynomials indexed by $B$ are connected through their latent assignments. When $|B| = 1$, we take the convention that $\mathcal{A}_B$ is a probability-one event.

The following lemma is a consequence of Condition C-Variance-Permutation. In this lemma, $E'_\Delta$, $V'_\Delta$, and $E'_\cap$ refer to graphs associated to the intersection and the symmetric difference of $(G^{(0)}, \pi^{(0)})$ and $(G^{(0)}, \pi^{(0)})$.

**Lemma A.7.** Let $B$ be a subset of $[0; r]$. If $0 \notin B$, we define

$$ \varphi(B) := c_0 D^{c_1} (D^{c_1} \lambda)^{\sum_{a \in B} |E^{(a)}|} \left(D^{c_1} \frac{k}{n}\right)^{\sum_{a \in B} (|V^{(a)}| - 1)} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^{|B|} . $$

If $0 \in B$, we define

$$ \varphi(B) := c_0 \bar{p}^{|E'_\cap|} D^{c_1} (D^{c_1} \lambda)^{|E'_\Delta| + \sum_{a \in B \setminus \{0\}} |E^{(a)}|} \left(D^{c_1} \frac{k}{n}\right)^{|V'_\Delta| - \#CC'_\Delta + \sum_{a \in B \setminus \{0\}} (|V^{(a)}| - 1)} \left[c_0 \frac{D^{c_1}}{\sqrt{n}}\right]^{|B|-1}, $$

Then, we have $|\mathbb{E}_R[\mathbf{1}\{\mathcal{A}_B\} \prod_{a \in B} \bar{P}_a]| \le \varphi(B)$.

The following lemma is proved by induction.

**Lemma A.8.** For any partition $\mathcal{B}$ of $[r]$ we have

$$ \left| \mathbb{E}_R \left[ \mathbf{1}_{\mathcal{E}_B} \prod_{B \in \mathcal{B}} \mathbf{1}_{\mathcal{A}_B} \prod_{a \in B} \bar{P}_a \right] \right| \le r^{3r} 2^r \prod_{i=1}^r \varphi(\{i\}) . $$

For any partition $\mathcal{B}$ of $[0; r]$, we have

$$ \left| \mathbb{E}_R \left[ \mathbf{1}_{\mathcal{E}_B} \prod_{B \in \mathcal{B}} \mathbf{1}_{\mathcal{A}_B} \prod_{a \in B} \bar{P}_a \right] \right| \le (r+1)^{3(r+1)} 2^{(r+1)} \prod_{i=0}^r \varphi(\{i\}) . $$

Before establishing these lemmas, let us finish the proof. Coming back to (80) and (81), we straightforwardly derive from Lemma A.8 that

$$ \left| \mathbb{E} \left[ \prod_{a=1}^{r} \bar{P}_a \right] \right| \le r^{3r} 2^r \prod_{i=1}^{r} \varphi(\{i\}) ; \qquad \left| \mathbb{E} \left[ \prod_{a=0}^{r} \bar{P}_a \right] \right| \le (r+1)^{3(r+1)} 2^{(r+1)} \prod_{i=0}^{r} \varphi(\{i\}) . $$

This yields (78) and (79). The result follows.

*Proof of Lemma A.8.* We only prove the result for a partition $\mathcal{B}$ of $[r]$, the arguments being the same for partitions $\mathcal{B}$ of $[0; r]$. Given $B \subset [r]$, we define $W_B := \mathbf{1}\{\mathcal{A}_B\} \prod_{i \in B} \bar{P}_i$. First, for $|\mathcal{B}| = 1$, the result holds by Lemma A.7. Consider a partition $\mathcal{B}$ of $[r]$ with more than one group. Note that, for $B \in \mathcal{B}$, the $W_B$'s are independent under $\mathbb{P}_R$. This entails that

$$ \mathbb{E}_R \left[ \prod_{B \in \mathcal{B}} W_B \right] = \prod_{B \in \mathcal{B}} \mathbb{E}_R [W_B] . $$

As a consequence, we get

$$ \mathbb{E}_R[\mathbf{1}\{\mathcal{E}_B\} \prod_{B \in \mathcal{B}} W_B] = \prod_{B \in \mathcal{B}} \mathbb{E}_R[W_B] - \mathbb{E}_R \left[ \mathbf{1}\{\mathcal{E}_B^c\} \prod_{B \in \mathcal{B}} W_B \right] . $$
For two partitions $\mathcal{B}$ and $\mathcal{B}'$, we write $\mathcal{B} \prec \mathcal{B}'$ if $\mathcal{B}'$ is (strictly) finer than $\mathcal{B}$. Observe that

$$1\{\mathcal{E}_{\mathcal{B}}^{c}\} \prod_{B \in \mathcal{B}} 1\{\mathcal{A}_{B}\} = \sum_{\mathcal{B}' \succ \mathcal{B}} 1\{\mathcal{E}_{\mathcal{B}'}\} \prod_{\mathcal{B}' \in \mathcal{B}'} 1\{\mathcal{A}_{\mathcal{B}'}\}.$$

We therefore obtain

$$\left| \mathbb{E}_R \left[ 1\{\mathcal{E}_B\} \prod_{B \in \mathcal{B}} W_B \right] \right| \le \left| \prod_{B \in \mathcal{B}} \mathbb{E}_R [W_B] \right| + \sum_{\mathcal{B}' \succ \mathcal{B}} \left| \mathbb{E}_R \left[ 1\{\mathcal{E}_{B'}\} \prod_{B' \in \mathcal{B}'} W_{B'} \right] \right|.$$

By a straightforward induction, we get that

$$\left| \mathbb{E}_R \left[ 1\{\mathcal{E}_B\} \prod_{B \in \mathcal{B}} W_B \right] \right| \le \sum_{\mathcal{B}' \succeq \mathcal{B}} U_{\mathcal{B}, \mathcal{B}'} \left| \prod_{B' \in \mathcal{B}'} \mathbb{E}_R [W_{B'}] \right|,$$

where $U_{\mathcal{B},\mathcal{B}'}$ is defined by recursion by $U_{\mathcal{B},\mathcal{B}} = 1$ and, for $\mathcal{B}' \succ \mathcal{B}$, $U_{\mathcal{B},\mathcal{B}'} := \sum_{\mathcal{B}'' : \mathcal{B}' \succeq \mathcal{B}'' \succ \mathcal{B}} U_{\mathcal{B}'' , \mathcal{B}''}$. In fact, for $\mathcal{B}' \succ \mathcal{B}$, $U_{\mathcal{B},\mathcal{B}'}$ corresponds the number of sequences of partitions of the form $(\mathcal{B}^{(0)}, \dots, \mathcal{B}^{(l)})$ with $\mathcal{B}^{(0)} = \mathcal{B}'$, $\mathcal{B}^{(l)} = \mathcal{B}$, and $\mathcal{B}^{(i-1)} \succ \mathcal{B}^{(i)}$ for all $i = 1, \dots, l$. Since, going from $\mathcal{B}'$ to $\mathcal{B}$ in such a sequence amounts to sequentially merging elements of $\mathcal{B}'$, one checks that $U_{\mathcal{B},\mathcal{B}'} \le |\mathcal{B}'|^{2|\mathcal{B}'|} 2^{|\mathcal{B}'|}$. Also, by Lemma A.7, we have $|\mathbb{E}[W_B]| \le \varphi(\mathcal{B})$. Gathering everything, we conclude

$$\left| \mathbb{E}_R \left[ 1\{\mathcal{E}_B\} \prod_{B \in \mathcal{B}} W_B \right] \right| \le r^{3r} 2^r \prod_{i=1}^r \varphi(\{i\}) .$$

<figure><img src="image_5.png" /></figure>

*Proof of Lemma A.7.* Without loss of generality, we only have to consider the cases where $B = [0;r]$ or $B = [r]$. We start by considering $B = [r]$ and we write $\mathcal{A}$ for $\mathcal{A}_B$. First, we develop the product

$$\mathbb{E}_R \left[ 1\{\mathcal{A}\} \prod_{a \in [r]} \bar{P}_a \right] = \sum_{T \subset [r]} \prod_{a \in [r] \setminus T} (-1)^{r-|T|} \mathbb{E} [P_{G^{(a)}, \pi^{(a)}}] \mathbb{E}_R \left[ 1\{\mathcal{A}\} \prod_{a \in T} P_{G^{(a)}, \pi^{(a)}} \right].$$

Given $z \in [n]^n$, we consider the restriction $z_{\text{supp}}$ of $z$ to $\cup_{a=1}^r \pi^{(a)}(V^{(a)})$. Importantly, for any configuration $z_{\text{supp}}$, we have $\mathbb{E}[P_{G^{(a)}, \pi^{(a)}}|z_{\text{supp}}] \ge 0$ since the probability of each edge in $Y^*$ is at least $q$. Recall that $\tilde{P}$ refers to distribution where all the $z_i$s are sampled independently. Any configuration $z_{\text{supp}}$ that satisfies $\mathcal{A}$ and arises with positive probability under $\mathbb{P}_R$ satisfies

$$\mathbb{P}_R[z_{\text{supp}} = z'_{\text{supp}}] \le \tilde{P}[z_{\text{supp}} = z'_{\text{supp}}] \left(1 - \frac{2D}{n}\right)^{-2D} \le \tilde{P}[z_{\text{supp}} = z'_{\text{supp}}] \left(1 + \frac{8D^2}{n}\right) \le 2\tilde{P}[z_{\text{supp}} = z'_{\text{supp}}],$$

where we used that at most $2D$ nodes are involved in $\cup_{a=1}^r \pi^{(a)}(V^{(a)})$ and use that $D^2/n$ is small enough by Condition C-Signal. Using that, for any configuration $z$, $\tilde{\mathbb{E}}[1\{\mathcal{A}\} \prod_{a \in T} P_{G^{(a)}, \pi^{(a)}}|z] \ge 0$, we obtain

$$\left| \mathbb{E}_R \left[ 1\{\mathcal{A}\} \prod_{a \in [r]} \bar{P}_a \right] \right| \le 2 \sum_{T \subset [r]} \prod_{a \in [r] \setminus T} \mathbb{E} [P_{G^{(a)}, \pi^{(a)}}] \tilde{\mathbb{E}} \left[ 1\{\mathcal{A}\} \prod_{a \in T} P_{G^{(a)}, \pi^{(a)}} \right]. \quad (82)$$

To control this term, we sum over the partitions $\mathcal{T} = (T_1, T_2, \dots, T_{|\mathcal{T}|})$ of $T$ and we use the event $\mathcal{A}_{\mathcal{T}} = \cap_{i=1}^{|\mathcal{T}|} \mathcal{A}_{T_i}$ where we recall that $\mathcal{A}_{T_i}$ states that the polynomials indexed by $T_i$ are connected through their
hidden labels.

$$
\begin{aligned}
\tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}\} \prod_{a \in T} P_{G^{(a)}, \pi^{(a)}} \right] &\le \sum_{\mathcal{T}} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}\} \mathbf{1}\{\mathcal{A}_{\mathcal{T}}\} \prod_{a \in T} P_{G^{(a)}, \pi^{(a)}} \right] \\
&\le \sum_{\mathcal{T}} \left( \frac{4D^2}{n} \right)^{|\mathcal{T}|-1} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{\mathcal{T}}\} \prod_{a \in T} P_{G^{(a)}, \pi^{(a)}} \right] \\
&\le \sum_{\mathcal{T}} \left( \frac{4D^2}{n} \right)^{|\mathcal{T}|-1} \prod_{i=1}^{|\mathcal{T}|} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{T_i}\} \prod_{a \in T_i} P_{G^{(a)}, \pi^{(a)}} \right],
\end{aligned}
$$

where we used the independence of the sampling design in the second and in the third line. Coming back to (82), we arrive at

$$
\mathbb{E}_R \left[ \mathbf{1}\{\mathcal{A}\} \prod_{a \in [r]} \bar{P}_a \right] \le 2^{r+1} r^r \max_{T \subset [r]} \max_{\mathcal{T}: \text{partition of T}} \left( \frac{4D^2}{n} \right)^{|\mathcal{T}|-1} \prod_{a \in [r] \setminus T} \mathbb{E} \left[ P_{G^{(a)}, \pi^{(a)}} \right] \prod_{i=1}^{|\mathcal{T}|} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{T_i}\} \prod_{a \in T_i} P_{G^{(a)}, \pi^{(a)}} \right]. \quad (83)
$$

To conclude, we rely on Conditions C-Moment and C-Variance-Permutation. This leads us to the desired bound.

Let us turn to the case where $B = [0; r]$. The only difference is that the polynomial $\bar{P}_0$ is now involved.

$$
\bar{P}_0 := \bar{P}_{G^{(0)}, \pi^{(0)}} \bar{P}_{G^{(0)}, \pi^{(0)}} - \mathbb{E} \left[ \bar{P}_{G^{(0)}, \pi^{(0)}} \bar{P}_{G^{(0)}, \pi^{(0)}} \right].
$$

Denote $cc_0$ and $cc'_0$ the number of connected components of $G^{(0)}$ and $G^{(0)}$ and write $(G^{(0;i)}, \pi^{(0;i)})$ and $(G^{(0;i)}, \pi^{(0;i)})$ for the corresponding labelled connected components. Then, arguing as for (83), we get

$$
\mathbb{E}_R \left[ \mathbf{1}\{\mathcal{A}\} \prod_{a \in [0; r]} \bar{P}_a \right] \le 2^{r+2} (r+1)^{r+1} [S_1 + S_2] ; \quad (84)
$$

$$
S_1 := \max_{T \subset [r]} \left| \mathbb{E} \left[ \bar{P}_{G^{(0)}, \pi^{(0)}} \bar{P}_{G^{(0)}, \pi^{(0)}} \right] \right| \max_{\mathcal{T}} \left( \frac{4D^2}{n} \right)^{|\mathcal{T}|-1} \prod_{a \in [r] \setminus T} \mathbb{E} \left[ P_{G^{(a)}, \pi^{(a)}} \right] \prod_{i=1}^{|\mathcal{T}|} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{T_i}\} \prod_{a \in T_i} P_{G^{(a)}, \pi^{(a)}} \right] ;
$$

$$
S_2 := 2^{cc_0+cc'_0} \max_{L \subset [cc_0]; L' \subset [cc'_0]} \max_{0 \in T \subset [0; r]} \max_{\mathcal{T}} \left( \frac{4D^2}{n} \right)^{|\mathcal{T}|-1} \prod_{a \in [cc_0] \setminus L} \mathbb{E} \left[ P_{G^{(0;a)}, \pi^{(0;a)}} \right] \prod_{a \in [cc_0] \setminus L'} \mathbb{E} \left[ P_{G^{(0;a)}, \pi^{(0;a)}} \right]
$$

$$
\cdot \prod_{a \in [r] \setminus T} \mathbb{E} [P_{G^{(a)}, \pi^{(a)}}]
$$

$$
\cdot \prod_{i:0 \notin T_i} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{T_i}\} \prod_{a \in T_i} P_{G^{(a)}, \pi^{(a)}} \right] \prod_{i:0 \in T_i} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{T_i}\} \prod_{a \in T_i \setminus \{0\}} P_{G^{(a)}, \pi^{(a)}} \prod_{a \in L} P_{G^{(0;a)}, \pi^{(0;a)}} \prod_{a \in L'} P_{G^{(0;a)}, \pi^{(0;a)}} \right].
$$

All the terms in $S_1$ and $S_2$ are straightforwardly controlled using Conditions C-Moment, C-Variance, C-Variance-Permutation, except for the last expression

$$
\prod_{i:0 \in T_i} \tilde{\mathbb{E}} \left[ \mathbf{1}\{\mathcal{A}_{T_i}\} \prod_{a \in T_i \setminus \{0\}} P_{G^{(a)}, \pi^{(a)}} \prod_{a \in L} P_{G^{(0,a)}, \pi^{(0,a)}} \prod_{a \in L'} P_{G^{(0,a)}, \pi^{(0,a)}} \right] .
$$

Indeed, since we have left out $\prod_{a \in [cc_0] \setminus L} P_{G^{(0;a)}, \pi^{(0;a)}}$ and $\prod_{a \in [cc_0] \setminus L'} P_{G^{(0;a)}, \pi^{(0;a)}}$ in the above expression, the event $\mathcal{A}_{T_i}$ is not of the right form to apply C-Variance-Permutation. For this purpose, we need to form a new graph $\tilde{G}_{\Delta}$ associated to $\prod_{a \in T_i \setminus \{0\}} P_{G^{(a)}, \pi^{(a)}} \prod_{a \in L} P_{G^{(0,a)}, \pi^{(0;a)}} \prod_{a \in L'} P_{G^{(0,a)}, \pi^{(0;a)}}$. In comparison to the original graph $G_{\Delta}$, the pure connected components associated to $P_{G^{(a)}, \pi^{(a)}}$ with $a \notin T_i$ have been
removed whereas some non-pure connected components of $G_Δ$ have possibly been removed or broken into several connected components that are now possibly pure because of the removal of $\prod_{a \in [cc_0] \setminus L} P_{G^{(0;a)}, \pi^{(0;a)}}$ and $\prod_{a \in [cc_0] \setminus L'} P_{G^{(0;a)}, \pi^{(0;a)}}$. Denote $\tilde{r}$ the number of pure connected components associated to $\tilde{G}_Δ$, and define the polynomials $\tilde{P}_1, \dots, \tilde{P}_{\tilde{r}}$ associated to the pure connected components and $\tilde{P}_0$ the polynomial associated to all the non-pure connected components in such a way that

$$ \prod_{a \in T_i \setminus \{0\}} P_{G^{(a)}, \pi^{(a)}} \prod_{a \in L} P_{G^{(0;a)}, \pi^{(0;a)}} \prod_{a \in L'} P_{G^{(0;a)}, \pi^{(0;a)}} = \tilde{P}_0 \tilde{P}_1 \dots \tilde{P}_{\tilde{r}} . $$

Given a set $B \subset [0; \tilde{r}]$, define the event $\tilde{\mathcal{A}}_B$ such that the polynomials $\tilde{P}_i$ indexed by $B$ are connected through their latent assignments. Given a partition $\tilde{\mathcal{B}}$ of $[0; \tilde{r}]$, we write $u(\tilde{\mathcal{B}}) \ge 0$ for the number of groups of $\tilde{\mathcal{B}}$ which are only made of pure connected components from the original graph $G_Δ$. Let $S \subset [n]$ be the subset of nodes involved in $\tilde{P}_0 \tilde{P}_1 \dots \tilde{P}_{\tilde{r}}$. Write $z_S$ for the restriction of the configuration $z$ to $S$. Fix a specific configuration $z'_S \in [n]^S$. Let $\tilde{B}_{z'_S}$ be the minimal partition of $[0; \tilde{r}]$ such that $\prod_{B \in \tilde{B}_{z'_S}} 1_{\{\tilde{\mathcal{A}}_B\}} = 1$. Then, one easily checks that $\tilde{P}[A_{T_i} | z_S = z'_S] \le (4D^2/n)^{u(\tilde{B}_{z'_S})}$. This leads us to

$$ \tilde{\mathbb{E}} \left[ 1_{\{A_{T_i}\}} \tilde{P}_0 \tilde{P}_1 \dots \tilde{P}_{\tilde{r}} \right] \le \sum_{\tilde{\mathcal{B}} \text{ partition of } [0, \tilde{r}]} \left( \frac{4D^2}{n} \right)^{u(\tilde{\mathcal{B}})} \tilde{\mathbb{E}} \left[ \left[ \prod_{B \in \tilde{\mathcal{B}}} 1_{\{\tilde{\mathcal{A}}_B\}} \right] \tilde{P}_0 \tilde{P}_1 \dots \tilde{P}_{\tilde{r}} \right] \\ \le \sum_{\tilde{\mathcal{B}} \text{ partition of } [0, \tilde{r}]} \left( \frac{4D^2}{n} \right)^{u(\tilde{\mathcal{B}})} \prod_{B \in \tilde{\mathcal{B}}} \tilde{\mathbb{E}} \left[ 1_{\{\tilde{\mathcal{A}}_B\}} \prod_{l \in B} \tilde{P}_l \right], $$

where we used the independence of the sampling design in the second line. Finally, we can bound all the expressions in this last expression using C-Moment, C-Variance, C-Variance-Permutation. Putting everything together and coming back to (84) concludes the proof. □

<figure><img src="image_6.png" /></figure>

## A.4 Proof of technical lemmas

*Proof of lemma A.4.* Each connected component of $G'_Δ$ contains at least a matched node. This node cannot be perfectly matched, otherwise it does not arise in $G'_Δ$. As a consequence, we have $|\mathbf{M}_{SM}| \ge \#CC'_Δ$. Besides, $G'_Δ$ satisfies $|E'_Δ| \ge |V'_Δ| - \#CC'_Δ$. By the previous inequality this enforces, that $|E'_Δ| \ge |V'_Δ| - |\mathbf{M}_{SM}| = U'$. □

*Proof of Lemma A.6.* Each connected component of $G^{(1)}$ is matched at least to another connected component of $G^{(2)}$. By a simple induction argument, we are reduced to showing this specific bound for any $G^{(1)}$ and $G^{(2)}$,

$$ |V^{(1)}| - \#CC_{G^{(1)}} + |V^{(2)}| - \#CC_{G^{(2)}} \ge |V_{\Delta}| - \#CC_{\Delta}. \quad (85) $$

First, we have $|V^{(1)}| + |V^{(2)}| = |V_Δ| + |\mathbf{M}_{PM}| + |\mathbf{M}|$ by construction. Second, each matching can at most connect 2 connected components that were disconnected. Hence, we have $\#CC_Δ \ge \#CC_{G^{(1)}} + \#CC_{G^{(2)}} - |\mathbf{M}|$. Gathering the two last bounds leads to (85). □

*Proof of Lemma A.5.* Fix $\overline{U}_1, \overline{U}_2$, and $\underline{M}$. Then, we define $V_{PM}^{(1)}$ (resp. $V_{PM}^{(2)}$) as the set of perfectly matched nodes. By construction, $V_{PM}^{(1)}$ is the subset of $V^{(1)}$ that are neither in $\overline{U}_1$ nor in $\underline{M}$. Fix a matching $\mathbf{M}^{(0)}$ in $\mathcal{M}_{\text{shadow}}(\overline{U}_1, \overline{U}_2, \underline{M})$ and consider the corresponding bijection $\phi^{(0)}: V_{PM}^{(1)} \mapsto V_{PM}^{(2)}$ defined by $\mathbf{M}_{PM}^{(0)} = \{(v, \phi^{(0)}(v)): v \in V_{PM}^{(1)}\}$. Now, consider any other matching $\mathbf{M}'$ in $\mathcal{M}_{\text{shadow}}(\overline{U}_1, \overline{U}_2, \underline{M})$ and build similarly the bijection $\phi': V_{PM}^{(1)} \mapsto V_{PM}^{(2)}$ such that $\mathbf{M}'_{PM} = \{(v, \phi'(v)): v \in V_{PM}^{(1)}\}$. Then, we can define the bijection $\phi': V^{(1)} \mapsto V^{(1)}$ such that $\phi'(v) = v$ if $v \notin V_{PM}^{(1)}$ and $\phi'(v) = (\phi^{(0)})^{-1}(\phi'(v))$. We claim that $\phi$ is an automorphism of $G^{(1)}$. Let us conclude the proof before establishing the claim. Any two distinct $\mathbf{M}'$ and $\mathbf{M}''$ in $\mathcal{M}_{\text{shadow}}(\overline{U}_1, \overline{U}_2, \underline{M})$ lead to distinct automorphisms $\phi'$ and $\phi''$. Thus, we get

$$ |\mathcal{M}_{\text{shadow}}(\overline{U}_1, \overline{U}_2, \underline{M})| \le |\text{Aut}(G^{(1)})|. $$
By symmetry, we also conclude that the cardinality is smaller than $|\text{Aut}(G^{(2)})|$.

Let us prove the claim. Consider any edge $(v_1, v_2)$ in $G^{(1)}$. If neither $v_1$ nor $v_2$ belong to $V_{PM}^{(1)}$, then $(\varphi(v_1), \varphi(v_2)) = (v_1, v_1)$ are connected in $G^{(1)}$. If $v_1$ belongs to $V_{PM}^{(1)}$ and $v_2$ does not belong to $V_{PM}^{(1)}$, then it follows that $v_2$ is semi-matched, i.e. there exists $w \in V^{(2)}$ such that $(v_2, w) \in M_{SM} = M$. Since $v_1$ is perfectly matched, it follows that $(\varphi(v_1), w)$ are connected in $G^{(2)}$. By the same argument, we deduce that $((\varphi^{(0)})^{-1}(\varphi(v_1)), v_2) = (\varphi(v_1), \varphi(v_2))$ are connected in $G^{(1)}$. Finally, we consider the case where both $v_1$ and $v_2$ belong to $V_{PM}^{(1)}$. Since both are perfectly matched $(\varphi(v_1), \varphi(v_2))$ are connected in $G^{(2)}$ and they belong to $V_{PM}^{(2)}$. Repeating again the argument, we conclude that $(\varphi(v_1), \varphi(v_2)) = ((\varphi^{(0)})^{-1}(\varphi(v_1)), (\varphi^{(0)})^{-1}(\varphi(v_2)))$ are connected in $G^{(1)}$. □

# B Proof of Proposition 7.4

## B.1 Independent sampling, Condition 1

We start with some notation and general computations. Consider any two templates $G^{(1)} = (V^{(1)}, E^{(1)})$, $G^{(2)} = (V^{(2)}, E^{(2)})$ in $G_{\le D}$ and any two labelings $\pi^{(1)}$ and $\pi^{(2)}$. Write $G_{\cup} = (V_{\cup}, E_{\cup})$ for the merged labeled graph of $\pi^{(1)}(G^{(1)})$ and $\pi^{(2)}(G^{(2)})$ and $G_{\Delta} = (V_{\Delta}, E_{\Delta})$ for the associated labeled symmetric difference graph — see Section 5 for definitions. We may decompose the product of polynomials

$$ 
\begin{aligned}
P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}} &= \prod_{(i,j) \in E^{(1)}} Y_{\pi^{(1)}(i)\pi^{(1)}(i)} \prod_{(i,j) \in E^{(2)}} Y_{\pi^{(2)}(i)\pi^{(2)}(i)} \\
&= \prod_{(i,j) \in E_{\Delta}} Y_{ij} \prod_{(i,j) \in E_{\cap}} Y_{ij}^2,
\end{aligned} 
\quad (86) $$

Recall that, given $z$, the $(Y_{ij})_{1 \le i < j \le n}$ are independent with $\mathbb{P}[Y_{ij} = (1-q)|z] = q + \Theta_{z_i z_j}$ and $\mathbb{P}[Y_{ij} = -q|z] = 1 - q - \Theta_{z_i z_j}$ — see Model 2. In particular, we have

$$ \mathbb{E}[P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}|z] = \prod_{(i,j) \in E_{\Delta}} \Theta_{z_i z_j} \prod_{(i,j) \in E_{\cap}} [(1-q)^2(q + \Theta_{z_i z_j}) + q^2(1-q - \Theta_{z_i z_j})] . \quad (87) $$

In all the problems that we consider in this subsection, we have that $\Theta$ only takes two values: 0 or $\lambda = p - q > 0$. Recall the definition of $\bar{p} = p(1-q)^2 + (1-p)q^2$ and $\bar{q} = q(1-q)$. Since $\bar{p} = \bar{q} + (p-q)(1-2q)$ and since we assume that $q \le 1/2$, it follows that $\bar{p} \ge \bar{q}$. In this specific case, the identity (87) simplifies to

$$ \mathbb{E}[P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}|z] = \lambda^{|E^{\Delta}|} \prod_{(i,j) \in E_{\Delta}} \mathbf{1}_{\Theta_{z_i z_j} \neq 0} \prod_{(i,j) \in E_{\cap}} [\bar{\mathbf{1}}_{\Theta_{z_i z_j} = 0} + \bar{p}\mathbf{1}_{\Theta_{z_i z_j} \neq 0}] . \quad (88) $$

We shall build upon this identity to establish the different conditions for each model. Similarly, we have the following formula.

$$ \mathbb{E}[P_{G^{(1)}, \pi^{(1)}}|z] = \lambda^{|E^{(1)}|} \prod_{(i,j) \in E^{(1)}} \mathbf{1}\{\Theta_{z_{\pi^{(1)}(i)}z_{\pi^{(1)}(j)}} \neq 0\} . \quad (89) $$

Let us turn to checking our assumptions for the three models.

**Hidden subclique model (HS-I)** Consider a template $G = (V, E)$ and a labeling $\pi$. In light of (89), the conditional expectation of $P_{G,\pi}$ given $z$ is non-zero if and only if $z_{\pi(i)} \le k$ for all $i \in k$. This leads us to

$$ \mathbb{E}[P_{G,\pi}] = \lambda^{|E|} \mathbb{E} \left[ \prod_{i \in V} \mathbf{1}\{z_{\pi(i)} \le k\} \right] , \quad (90) $$

where $\mathbb{E}[\prod_{i \in V} \mathbf{1}\{z_{\pi(i)} \le k\}] = (\frac{k}{n})^{|V|}$. Hence, Condition C-Moment holds with $c_m = 0$.

Consider any two $G^{(1)}$, $G^{(2)}$ and $\pi^{(1)}$, $\pi^{(2)}$. Recall that $G_{\cup}$ (resp. $G_{\cap}$, $G_{\Delta}$) stands for the merged (resp. intersection, resp. symmetric difference) graph of $\pi^{(1)}[G^{(1)}]$ and $\pi^{(2)}[G^{(2)}]$. We integrate (88) over all latent
assignments $z$ that lead to a non-zero conditional expectation in (88). First, observe that this constrains to have $z_i \le k$ for all $i$ in $V_\Delta$. The vertex set $V_\cap$ of the intersection graph $G_\cap$ is partitioned into $(V_{PM}, V_{SM})$ where we recall that $V_{PM}$ corresponds to the perfectly matched nodes and $V_{SM}$ to the semi-matched nodes, that is nodes that are matched but not perfectly matched. By definition, $(V_{PM}, V_\Delta)$ form a partition of $V_\cup$ and $V_{SM} \subset V_\Delta$. As a consequence, to compute $\mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]$, we have to sum over all possible configurations for $(z_i)_{i \in V_{PM}}$. For any subset $T \subseteq V_\cap$ of nodes, we denote $E_\cap[T]$ for the edge set of the subgraph of $G_\cap$ induced by $T$.

$$ \mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}] = \lambda^{|E_\Delta|} \mathbb{E}[\prod_{i \in V_\Delta} \mathbf{1}\{z_i \le k\}] \sum_{S \subseteq V_{PM}} \overline{q}^{|E_\cap|-|E_\cap[S \cup V_{SM}]|} \overline{p}^{|E_\cap[S \cup V_{SM}]|} \mathbb{P}[\{i: z_i \le k\} \cap V_\cap = S] , \quad (91) $$

where, in the random size model (HS-I), we have $\mathbb{P}[\{i: z_i \le k\} \cap V_\cap = S] = \left(\frac{k}{n}\right)^{|S|} \left(1 - \frac{k}{n}\right)^{|V_{PM}| - |S|}$. Noting that $\overline{p} \ge \overline{q}$, we get the following bound

$$ \overline{q}^{|E_\cap|} \lambda^{|E_\Delta|} \mathbb{E}[\prod_{i \in V_\Delta} \mathbf{1}\{z_i \le k\}] \le \mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}] \le \overline{p}^{|E_\cap|} \lambda^{|E_\Delta|} \mathbb{E}[\prod_{i \in V_\Delta} \mathbf{1}\{z_i \le k\}], \quad (92) $$

where $\mathbb{E}[\prod_{i \in V_\Delta} \mathbf{1}\{z_i = 1\}] = (k/n)^{|V_\Delta|}$. Since $|E_\cap| = (|E^{(1)}| + |E^{(2)}| - |E_\Delta|)/2$, (HS-I) satisfies the first part of Condition C-Variance with $c_{v,1} = 0$ and $c_{v,2} = 1$. Next, we consider the case where $(G^{(1)}, \pi^{(1)}) = (G^{(2)}, \pi^{(2)})$ so that $E_\Delta = \emptyset$. By Condition C-Signal, we have $\lambda \le qD^{-8}$, so that $\overline{p} = \overline{q} + \lambda(1 - 2q) \le \overline{q}(1 + D^{-8})$. It follows from (92) that

$$ [\mathbb{E}[P_{\pi,G}^2] - \overline{q}^{|E|}] \le \overline{q}^{|E|} [(1 + D^{-8})^D - 1] \le 2D^{-7} \overline{q}^{|E|} . $$

The second part of Condition C-Variance is therefore satisfied with $c_{v,3} = 2$ and $c_{v,4} = 7$.

**Stochastic Block Model (SBM-I)** As previously, we first work out the moment of polynomials. In order to have $\mathbb{E}[P_{G,\pi}|z] \ne 0$, it is necessary that $\Theta_{z_{\pi^{(i)}}, z_{\pi^{(j)}}}$ is always non-zero for all edges $(i,j)$ of $G$. As a consequence, all nodes in a connected component of $\pi[G]$ should belong the same group of the SBM, so that

$$ \mathbb{E}[P_{G,\pi}] = \lambda^{|E|} \mathbb{P}[\{z \text{ in the same block over each CC}\}] . \quad (93) $$

where, for (SBM-I), we have $\mathbb{P}[\{z \text{ in the same block over each CC}\}] = \left(\frac{k}{n}\right)^{|V|-\#CC_G}$. Hence, Condition C-Moment holds with $c_m = 0$.

Let us turn to the second moment. Coming back to (88), we see that the conditional expectation of $P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}$ is non-zero only if, inside each connected component of $G_\Delta$, all the nodes belong to the same group of the SBM. Write $R(z)$ for the partition of $V_\cup$ associated to groups of the SBM and write $R_0$ for the finest partition of $V_\cup$ such that all connected components of $G_\Delta$ belong to the same group of $R_0$. For any two partitions $R_1$ and $R_2$, we write $R_1 \subseteq R_2$ if $R_2$ is finer or equal to $R_1$. Finally, we write that $i \stackrel{R}{\sim} j$ when $i$ and $j$ are in the same group according to the partition $R$. Then, we have

$$ \mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}] = \lambda^{|E_\Delta|} \sum_{R \subseteq R_0} \mathbb{P}[R(z) = R] \overline{q}^{|E_\cap|} \prod_{(i,j) \in E_\cap} \left(\frac{\overline{p}}{\overline{q}}\right)^{1\{i \sim j\}} . \quad (94) $$

Since $\overline{p} \ge \overline{q}$, we conclude that

$$ \overline{q}^{|E_\cap|} \lambda^{|E_\Delta|} \mathbb{P}[R(z) \preceq R_0] \le \mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}] \le \overline{p}^{|E_\cap|} \lambda^{|E_\Delta|} \mathbb{P}[R(z) \preceq R_0] , \quad (95) $$

where, in (SBM-I), we have $\mathbb{P}[R(z) \preceq R_0] = (k/n)^{|V|-\#CC_\Delta}$. Hence, (SBM-I) satisfies the first part of Condition C-Variance with $c_{v,1} = 0$ and $c_{v,2} = 1$. Next, we consider the case where $(G^{(1)}, \pi^{(1)}) = (G^{(2)}, \pi^{(2)})$ so that $E_\Delta = \emptyset$. By Condition C-Signal, we have $\lambda \le qD^{-8}$, it follows that $\overline{p} = \overline{q} + \lambda(1 - 2q) \le \overline{q}(1 + D^{-8})$. Thus, as for (HS-I), we conclude that the second part of Condition C-Variance is satisfied with $c_{v,3} = 2$ and $c_{v,4} = 7$.
**Tœplitz Seriation (TS-I)** By (89), we derive that

$$ \mathbb{E}[P_{G,\pi}] = \lambda^{|E|} |\mathbb{E}[\prod_{(i,j) \in E} \mathbf{1}\{|z_i - z_j| \le \frac{k}{2}\}] | \quad (96) $$

$$ \le \lambda^{|E|} \left( \frac{k+1}{n} \right)^{|V|-|CC_G|} . \quad (97) $$

To establish this upper bound, we considered a subset of E corresponding to a covering forest of G and we used that the probability of $\mathbf{1}\{|z_i - z_j| \le k/2\}$ is at most $(k+1)/n$. Hence, Condition C-Moment holds with $c_m = 1$ since $D \ge 2$.

Let us turn to the second moment. Since $\bar{p} \ge \bar{q}$, arguing similarly as for the SBM case, we get

$$ \bar{q}^{|E \cap \lambda|} \lambda^{|E_\Delta|} \le \frac{\mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]}{\mathbb{E}[\prod_{(i,j) \in E_\Delta} \mathbf{1}\{|z_i - z_j| \le k/2\}]} \le \bar{p}^{|E \cap \lambda|} \lambda^{|E_\Delta|} . \quad (98) $$

For the upper bound, we can again say that $\mathbb{E}[\prod_{(i,j) \in E_\Delta} \mathbf{1}\{|z_i - z_j| \le k/2\}] \le [(k+1)/n]^{|V_\Delta|-\#CC_\Delta}$. For the lower bound, we use the following argument. Root arbitrarily each connected component of $G_\Delta$. If any node $j$ satisfies $|z_j - z_i| \le k/4$ where $i$ is the corresponding root of its connected component, we have $\prod_{(i,j) \in E_\Delta} \mathbf{1}\{|z_i - z_j| \le k/2\} = 1$. This allows to get bound

$$ \left(\frac{k}{4n}\right)^{|V_\Delta|-\#CC_\Delta} \le \mathbb{E}\left[\prod_{(i,j) \in E_\Delta} \mathbf{1}\{|z_i - z_j| \le k/2\}\right] \le \left(\frac{k+1}{n}\right)^{|V_\Delta|-\#CC_\Delta} . \quad (99) $$

As a consequence of (98) and (99), we readily deduce that the first part of Condition C-Variance holds with $c_{v,1} = c_{v,2} = 1$. Now, we focus on the $\mathbb{E}[P_{G,\pi}]$. Since $E_\Delta = \emptyset$, we get $\bar{q}^{|E|} \le \mathbb{E}[P_{G,\pi}] \le \bar{q}^{|E|}(\bar{q})^{|E|}$. We argue as in the previous case that $(\bar{q})^{|E|} \le 1 + D^{-8}$ to conclude that the second part of Condition C-Variance holds with $c_{v,3} = 2$ and $c_{v,4} = 7$.

## B.2 Permutation sampling, Condition 2

**Hidden subclique model (HS-P)** Both bounds (90) and (92) are still valid in this model. However, as the sample of the $z_i$'s is now without replacement, this changes the probabilities of the form $\mathbb{E}[\prod_{i \in V} \mathbf{1}\{z_i \le k\}]$. In particular, for any fixed $V$, we have

$$ \mathbb{E}\left[\prod_{i \in V} \mathbf{1}\{z_i \le k\}\right] \le \left(\frac{k}{n - |V|}\right)^{|V|} . \quad (100) $$

For any $V$ such that $|V| \le 4D$, $(n/(n - |V|))^{|V|} \le 1 + 32D^2/n$ provided that $32D^2 \le n$. In particular, all the upper bounds of moments for (HS-I) are still valid up to an additional multiplicative factor 2. Then, Condition C-Variance is still valid but with constants $c_{v,1} = 0$, $c_{v,2} = 2$, $c_{v,3} = 2$, and $c_{v,4} = 7$. Besides, Condition C-Moment holds with $c_m = 1$.

It remains to establish Condition C-Variance-Permutation. For short, we write $cc = \#CC_{\text{pure}}$. We only consider the case where at least one connected component of $G_\Delta$ is not pure, the other case being handled similarly. Recall the graph $\mathcal{N}(z, G_\cup)$ in the definition of C-Variance-Permutation. Let $\mathcal{T}$ denote the collection of all trees over the vertices $\{\omega_0, \dots, \omega_{cc}\}$. As $\mathcal{A}$ corresponds to the event where $\mathcal{N}(z, G_\cup)$ is connected, we can upper bound $\mathbf{1}\{\mathcal{A}\}$ by the $\sum_{\mathcal{T} \in \mathcal{T}} \mathbf{1}\{\mathcal{N}(z, G_\cup) \supset \mathcal{T}\}$, where $\mathcal{N}(z, G_\cup) \supset \mathcal{T}$ means $\mathcal{T}$ is a subgraph of $\mathcal{N}(z, G_\cup)$.

$$ \tilde{\mathbb{E}}[\mathbf{1}\{\mathcal{A}\} P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}] \le \sum_{\mathcal{T} \in \mathcal{T}} \tilde{\mathbb{E}}[\mathbf{1}\{\mathcal{N}(z, G_\cup) \supset \mathcal{T}\} P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}] , $$

In turn, the existence of a given edge in $\mathcal{N}(z, G_\cup)$ between $\omega_i$ and $\omega_j$ corresponds to the equality of two latent assignments in a node corresponding to $\omega_i$ and a node corresponding to $\omega_j$. Let $W$ be a set of couples
of nodes in $[n]$. We introduce the event $C_W$ such that all couples in $W$ share the same latent assignment. Let $W_T$ be the collection of all sets $W$ of $cc$ couples such that $C_W \subset \{\mathcal{N}(z, G_\cup) \supseteq T\}$. Since $|T| = (cc+1)^{cc-1}$ and since $|W_T| \le (4D^2)^{cc}$, we arrive at

$$ \begin{aligned} \tilde{\mathbb{E}}[\mathbf{1}\{\mathcal{A}\}P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}] & \le \sum_{T \in \mathcal{T}} \sum_{W \in \mathbf{W}_T} \tilde{\mathbb{E}}[\mathbf{1}\{C_W\}P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}] \\ & \le (cc+1)^{cc-1} \left(\frac{4D^2}{n}\right)^{cc} \max_{T \in \mathcal{T}, W \in \mathbf{W}_T} \tilde{\mathbb{E}}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}|\mathbf{1}\{C_W\}] . \end{aligned} \quad (101) $$

We point out that the upper bound (101) is also valid for (SBM-P) and for (TS-P) and we shall use it again. Hence, we only have to bound the last conditional expectation. For (HS-P), the event $C_W$ implies that each of the nodes in the $cc$ couples share the same latent assignment. Then, arguing as for (92), we arrive at

$$ \tilde{\mathbb{E}}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}|\mathbf{1}\{C_W\}] \le \bar{p}^{|E_\cap|}\lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|-\#CC_\Delta} . $$

We conclude that

$$ \begin{aligned} \tilde{\mathbb{E}}[\mathbf{1}\{\mathcal{A}\}P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}] & \le (cc+1)^{cc-1} \left(\frac{4D^2}{n}\right)^{cc} \bar{p}^{|E_\cap|}\lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|-\#CC_\Delta} \\ & \le \bar{p}^{|E_\cap|}\lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|-\#CC_\Delta} \left(\frac{8D^2}{\sqrt{n}}\right)^{cc} . \end{aligned} $$

Hence, C-Variance-Permutation holds with $c_{vd,1} = 2$ and $c_{vd,2} = 8$.

**Stochastic Block Model (SBM-P)** The first moment expression (93) and the second moment bounds (95) still hold, the only difference being the controls of the probabilities $\mathbb{P}[\{z \text{ constant over each CC}\}]$ and $\mathbb{P}[R(z) \succeq R_0]$. As for (HS-P) and in particular as in (100), we use simple bounds for Hypergeometric distributions to get that

$$ \begin{aligned} \mathbb{P}[R(z) \succeq R_0] \left(\frac{k}{n}\right)^{-|V_\Delta|+\#CC_\Delta} & \le 1 + \frac{32D^2}{n} \le 2, \\ \left| \mathbb{P}[\{z \text{ constant over each CC}\}] \left(\frac{k}{n}\right)^{-|V|+\#CC_G} \right| & \le 2. \end{aligned} \quad (102) $$

where we use that $32D^2 \le n$ by Condition C-Signal with $c_s = 1$. Then, all the upper bounds of moments for (SBM-I) are still valid up to an additional multiplicative factor $(1+D^{-1})$ and the lower bounds of moments for (SBM-I) are valid up to a multiplicative factor $(1-D^{-1})$. In particular, Condition C-Variance is still valid but with constants $c_{v,1} = 0$, $c_{v,2} = 2$, $c_{v,3} = 2$, and $c_{v,4} = 7$. Furthermore, Condition C-Moment holds with $c_m = 1$.

It remains to establish Condition C-Variance-Permutation. As for (HS-P), we only consider the case where $G_\Delta$ contains at least one non-pure connected component. We also start from (101). Consider $W \in W_T$. Under $C_W$, conditionally to $z$, the expectation of $P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}$ is equal to zero only if all the connected components that are connected by an edge in $T$ belong to the same group of the SBM. Arguing as before, we arrive at

$$ \tilde{\mathbb{E}}[P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}|C_W] \le \bar{p}^{|E_\cap|}\lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|-\#CC_\Delta} . $$

We conclude that

$$ \begin{aligned} \tilde{\mathbb{E}}[\mathbf{1}\{\mathcal{A}\}P_{G^{(1)},\pi^{(1)}}P_{G^{(2)},\pi^{(2)}}] & \le (cc+1)^{cc-1} \left(\frac{4D^2}{n}\right)^{cc} \bar{p}^{|E_\cap|}\lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|-\#CC_\Delta} \\ & \le \bar{p}^{|E_\cap|}\lambda^{|E_\Delta|} \left(\frac{k}{n}\right)^{|V_\Delta|-\#CC_\Delta} \left(\frac{8D^2}{\sqrt{n}}\right)^{cc} . \end{aligned} $$

Hence, C-Variance-Permutation holds with $c_{vd,1} = 2$ and $c_{vd,2} = 8$.
**Tœplitz Seriation (TS-P)** Again, we mainly reduce ourselves to (TS-I). Both (96) and (98) are still valid and we only have to bound quantities of the form $\mathbb{E}[\prod_{(i,j) \in E} \mathbf{1}\{|z_i - z_j| \le k/2\}]$ for some graph $G = (V, E)$ with $|V| \le 4D$. Arguing as for (TS-I) but using the sampling with replacement, we get

$$ \mathbb{E}\left[\prod_{(i,j) \in E} \mathbf{1}\{|z_i - z_j| \le k/2\}\right] \le \left[\frac{k}{n - 4D}\right]^{|V| - \#CC_G} \le 2\left(\frac{k}{n}\right)^{|V| - \#CC_G}, $$

since $32D^2 \le n$. Then, all the upper bounds of moments for (TS-P) are still valid up to an additional multiplicative factor 2. In particular, Condition C-Variance is still valid but with constants $c_{v,1} = 1$, $c_{v,2} = 2$, $c_{v,3} = 2$, and $c_{v,4} = 7$. Finally, C-Moment holds with $c_m = 4$.

It remains to establish C-Variance-Permutation. We again start from (101). Consider $W \in \mathbf{W}_T$. Arguing as for (99), we arrive at

$$ \tilde{\mathbb{E}}[P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}} |C_W] \le \bar{p}^{|E_{\cap}|} \lambda^{|E_{\Delta}|} \left(\frac{k+1}{n}\right)^{|V_{\Delta}| - \#CC_{\Delta}}. $$

$$ \begin{aligned} \tilde{\mathbb{E}}[\mathbf{1}\{A\} P_{G^{(1)}, \pi^{(1)}} P_{G^{(2)}, \pi^{(2)}}] &\le (cc + 1)^{cc-1} \left(\frac{4D^2}{n}\right)^{cc} \bar{p}^{|E_{\cap}|} \lambda^{|E_{\Delta}|} \left(\frac{k+1}{n}\right)^{|V_{\Delta}| - \#CC_{\Delta}} \\ &\le \bar{p}^{|E_{\cap}|} \lambda^{|E_{\Delta}|} \left(\frac{k+1}{n}\right)^{|V_{\Delta}| - \#CC_{\Delta}} \left(\frac{8D^2}{\sqrt{n}}\right)^{cc}. \end{aligned} $$

Hence, C-Variance-Permutation holds with $c_{vd,1} = 2$ and $c_{vd,2} = 8$.

## C Proof of Theorem 4.2

We start from Lemma 3.3 and then we use almost orthonormality of the basis — see Theorem 3.4.

$$ \begin{aligned} \mathrm{Adv}^2_{\le D} = & \sup_{\alpha_{\emptyset}, (\alpha_G)_{G \in \mathcal{G}_{\le D}}} \frac{\mathbb{E}_{H_1}^2 \left[ \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right]}{\mathbb{E} \left[ \left[ \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \Psi_G \right]^2 \right]} \le \sup_{\alpha_{\emptyset}, (\alpha_G)_{G \in \mathcal{G}_{\le D}}} \frac{\left[ \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\le D}} \alpha_G \mathbb{E}_{H_1} [\Psi_G] \right]^2}{(1 - D^{-2}) \|\alpha\|_2^2} \\ & \le (1 - cD^{-2})^{-1} \left[ 1 + \sum_{G \in \mathcal{G}_{\le D}} \mathbb{E}_{H_1}^2 [\Psi_G] \right]. \end{aligned} \quad (103) $$

As a consequence, we only have to bound the first moment of the polynomials $\Psi_G$ under the alternative for all our six models. We simultaneously consider all six models.

**Step 1: Moment of $\bar{P}_{G,\pi}$ for a template $G$.** Let us denote $r$ the number of connected components of $G$, we write $(G^{(1)}, \pi^{(1)}, \dots, G^{(r)}, \pi^{(r)})$ for the corresponding decomposition. For $i = 1, \dots, r$, define the event $\zeta_i$ where no node in $\pi^{(i)}(V^{(i)})$ is altered. Under this event, $P_{G^{(i)}, \pi^{(i)}}$ follows the same distribution under $\mathbb{P}_{H_1}$ as that under $\mathbb{P}$. Besides, for any function $f(Y)$ that does not depend on $(Y_{rs})_{(r,s) \in \pi^{(i)}(E^{(i)})}$, we have $\mathbb{E}_{H_1}[\mathbf{1}\{\zeta_i^c\} P_{G^{(i)}, \pi^{(i)}} f(Y)] = 0$ as under $\zeta_i^c$, one of the edges involved in $P_{G^{(i)}, \pi^{(i)}}$ has probability $q$. Then,
developing the polynomial $\overline{P}_{G,\pi}$ and introducing the events $\zeta_i$, we obtain

$$
\begin{align*}
\mathbb{E}_{H_1} \left[ \prod_{k=1}^{r} \overline{P}_{G^{(k)}, \pi^{(k)}} \right] &= \sum_{T \subset [r]} (-1)^{|T|} \mathbb{E}_{H_1} \left[ \prod_{k \in [r] \setminus T} (\mathbf{1}\{\zeta_k^c\} + \mathbf{1}\{\zeta_k\}) P_{G^{(k)}, \pi^{(k)}} \right] \prod_{k \in T} \mathbb{E}[P_{G^{(k)}, \pi^{(k)}}] \\
&= \sum_{T \subset [r]} (-1)^{|T|} \mathbb{E}_{H_1} \left[ \prod_{k \in [r] \setminus T} \mathbf{1}\{\zeta_k\} P_{G^{(k)}, \pi^{(k)}} \right] \prod_{k \in T} \mathbb{E}[P_{G^{(k)}, \pi^{(k)}}] \\
&= \sum_{T \subset [r]} (-1)^{|T|} \mathbb{E} \left[ \prod_{k \in [r] \setminus T} \mathbf{1}\{\zeta_k\} P_{G^{(k)}, \pi^{(k)}} \right] \prod_{k \in T} \mathbb{E}[P_{G^{(k)}, \pi^{(k)}}] \\
&= \mathbb{E} \left[ \prod_{k \in [r]} (\overline{P}_{G^{(k)}, \pi^{(k)}} - \mathbf{1}\{\zeta_k^c\} P_{G^{(k)}, \pi^{(k)}}) \right] \\
&= \sum_{T \subset [r]} \mathbb{E} \left[ (-1)^{r-|T|} \prod_{k \in [r] \setminus T} \mathbf{1}\{\zeta_k^c\} P_{G^{(k)}, \pi^{(k)}} \prod_{k \in T} \overline{P}_{G^{(k)}, \pi^{(k)}} \right] .
\end{align*}
$$

For the models (HS-I), (SBM-I), and (TS-I), the random variables $\overline{P}_{G^{(k)}, \pi^{(k)}}$ are independent and cen-
tered. Hence, this simplifies as

$$
\mathbb{E}_{H_1} \left[ \prod_{k=1}^{r} \overline{P}_{G^{(k)}, \pi^{(k)}} \right] = (-1)^r \mathbb{E} \left[ \prod_{k \in [r]} \mathbf{1}\{\zeta_k^c\} P_{G^{(k)}, \pi^{(k)}} \right] .
$$

Then, one bounds the latter term for all three models. We conclude that

$$
\left| \mathbb{E}_{H_1} \left[ \prod_{k=1}^{r} \overline{P}_{G^{(k)}, \pi^{(k)}} \right] \right| \le \lambda^{|E|} \left( \frac{2k}{n} \right)^{|V|-\#CC_G} \left( 2D\epsilon \frac{k}{n} \right)^{\#CC_G} . \quad (104)
$$

For the models (HS-P), (SBM-P), and (TS-P) additional work is required to account for the dependencies.

**Lemma C.1.** For models (HS-P), (SBM-P), and (TS-P). Under the assumptions of Theorem 4.2, we have

$$
\left| \mathbb{E}_{H_1} \left[ \prod_{k=1}^{r} \overline{P}_{G^{(k)}, \pi^{(k)}} \right] \right| \le c_1 (D^c \lambda)^{|E|} \left( D^c \frac{k}{n} \right)^{|V|-\#CC_G} \left( c_1 D^c \left( \frac{k\epsilon}{n} \vee \frac{1}{\sqrt{n}} \right) \right)^{\#CC_G} , \quad (105)
$$

where c and c_1 are numerical constants.

**Step 2: Bounding** $|\mathbb{E}_{H_1}[\Psi_G]|$. By Definition (19) of $\Psi_G$, we derive from (104) and (105) that, in all six models, we have

$$
|\mathbb{E}_{H_1}[\Psi_G]| \le c_1 \left(D^c \frac{\lambda}{\sqrt{q}}\right)^{|E|} \left(D^c \frac{k}{\sqrt{n}}\right)^{|V|-\#CC_G} \left[c_1 D^c \left(1 + \epsilon \frac{k}{\sqrt{n}}\right)\right]^{\#CC_G} .
$$

Reorganizing the products, we get

$$
|\mathbb{E}_{H_1}[\Psi_G]| \le c_1 \left[ c_1 D^{3c} \left( \frac{\lambda k}{\sqrt{q}n} + \frac{\lambda k^2 \epsilon}{n\sqrt{q}} \right) \right]^{\#CC_G} \left( D^c \frac{\lambda}{\sqrt{q}} \right)^{|E|+\#CC_G-|V|} \left( D^{2c} \frac{k\lambda}{\sqrt{nq}} \right)^{|V|-2\#CC_G} .
$$

As $G$ does not contain any isolated node, each connected component contains at least two nodes and therefore
$\#CC_G \le |V|/2$. Besides, any graph satisfies $|E| \ge |V| - \#CC_G$. Since we assume that $q \le 1/2$, $\bar{q}$ is larger
than $q/2$. Then, relying on the conditions (31) of the theorem, and assuming the constant $c_0$ in the latter
theorem is large enough, we obtain

$$
|\mathbb{E}_{H_1}[\Psi_G]| \leq D^{-c_0|E|/2} .
$$
**Step 3: Bounding the advantage.** Coming back to (103), we simply need to enumerate all $G \in \mathcal{G}_{\le D}$. For this purpose, we use the crude bound that there are no more $v^{2e}$ templates with $v$ nodes and $e$ edges. This allows us to conclude that

$$ \begin{aligned} \mathrm{Adv}_{\le D}^2 &\le (1 - cD^{-2})^{-1} \left[ 1 + \sum_{G \in \mathcal{G}_{\le D}} D^{-c_0|E|} \right] \\ &\le (1 - cD^{-2})^{-1} \left[ 1 + \sum_{v=1}^{2D} \sum_{e=1}^{D} v^{2e} D^{-c_0 e} \right] \\ &\le 1 + \frac{c}{D}, \end{aligned} $$

provided that $c_0$ is large enough and where the numerical constant $c$ changed from line to line. This concludes the proof.

*Proof of Lemma C.1.* In this proof, the positive numerical constants $c$ and $c_1$ may change from line to line.

$$ \begin{aligned} \left| \mathbb{E}_{H_1} \left[ \prod_{k=1}^{r} \bar{P}_{G^{(k)}, \pi^{(k)}} \right] \right| &\le \sum_{T \subset [r]} \left| \mathbb{E} \left[ \prod_{k \in [r] \setminus T} \mathbf{1}_{\{\zeta_k^c\}} P_{G^{(k)}, \pi^{(k)}} \prod_{k \in T} \bar{P}_{G^{(k)}, \pi^{(k)}} \right] \right| \\ &\le 2^r \max_{T \subset [r]} \mathbb{E} \left[ \prod_{k \in [r] \setminus T} \mathbf{1}_{\{\zeta_k^c\}} P_{G^{(k)}, \pi^{(k)}} \right] \left| \mathbb{E} \left[ \prod_{k \in T} \bar{P}_{G^{(k)}, \pi^{(k)}} \right] \right| \\ &\quad + 2^r \max_{T \subset [r]} \left| \mathbb{E} \left[ \left( \prod_{k \in [r] \setminus T} \mathbf{1}_{\{\zeta_k^c\}} P_{G^{(k)}, \pi^{(k)}} - \mathbb{E} \left[ \prod_{k \in [r] \setminus T} \mathbf{1}_{\{\zeta_k^c\}} P_{G^{(k)}, \pi^{(k)}} \right] \right) \prod_{k \in T} \bar{P}_{G^{(k)}, \pi^{(k)}} \right] \right| \\ &:= 2^r \left( \max_{T \subset [r]} A_{1;T} + \max_{T \subset [r]} A_{2;T} \right). \end{aligned} $$

It is easy to control $A_{1;T}$ from our previous computations. Indeed, for (HS-P), (SBM-P), and (TS-P), one easily derives that

$$ \mathbb{E} \left[ \prod_{k \in B} \mathbf{1}_{\{\zeta_k^c\}} P_{G^{(k)}, \pi^{(k)}} \right] \le \lambda \sum_{k \in B} |E^{(k)}| \left(2 \frac{k}{n}\right)^{\sum_{k \in B} |V^{(k)}|} (2D\epsilon)^{|B|}, \quad (106) $$

whereas the term $|\mathbb{E}[\prod_{k \in T} \bar{P}_{G^{(k)}, \pi^{(k)}}]|$ is either 0 when $T$ is a singleton or is controlled by Lemma A.3 for more general $T$ since all three models satisfy C-Moment, C-Variance, and C-Variance-Permutation. This allows us to derive that

$$ \max_{T \subset [r]} A_{1,T} \le c_1 (D^c \lambda)^{|E|} \left(D^c \frac{k}{n}\right)^{|V|-\#CC_G} \left(c_1 D^c \left(\frac{k\epsilon}{n} \vee \frac{1}{\sqrt{n}}\right)\right)^{\#CC_G}. $$

The control of $A_{2;T}$ requires additional work.

**Lemma C.2.** All three models (HS-P), (SBM-P), and (TS-P) satisfy

$$ \max_{T \subset [r]} A_{2,T} \le c_1 (D^c \lambda)^{|E|} \left(D^c \frac{k}{n}\right)^{|V|-\#CC_G} \left(c_1 D^c \left(\frac{k\epsilon}{n} \vee \frac{1}{\sqrt{n}}\right)\right)^{\#CC_G}. $$

Gathering these two bounds, we conclude that

$$ \left| \mathbb{E}_{H_1} \left[ \prod_{k=1}^{r} \bar{P}_{G^{(k)}, \pi^{(k)}} \right] \right| \le c_1 (D^c \lambda)^{|E|} \left(D^c \frac{k}{n}\right)^{|V|-\#CC_G} \left(c_1 D^c \left(\frac{k\epsilon}{n} \vee \frac{1}{\sqrt{n}}\right)\right)^{\#CC_G}. $$
*Proof of Lemma C.2.* We use a similar approach to the proof of Lemma A.3. Let us slightly change the notation in order to be able to be able to adapt the arguments. Let us assume that we are given $(G^{(1)}, \pi^{(1)}), \dots, (G^{(s)}, \pi^{(s)})$ and $(G^{(1)}, \pi^{(1)}), \dots, (G^{(r)}, \pi^{(r)})$ whose nodes are all distinct. For $i=1, \dots, s$, we define the event $\xi'_i$ for the polynomial $(G^{(i)}, \pi^{(i)})$. Then, we write

$$P_0 := \prod_{i=1}^{s} \mathbf{1}\{\xi_i^{c'}\} \overline{P}_{G^{(i)}, \pi^{(i)}},$$

Also, $\overline{P}_0 := P_0 - \mathbb{E}[P_0]$. Furthermore, for $i=1, \dots, r$, we write $P_i := P_{G^{(i)}, \pi^{(i)}}$ and $\overline{P}_i := \overline{P}_{G^{(i)}, \pi^{(i)}}$. Define $e := \sum_{i=1}^r |E^{(i)}|$ and $e' := \sum_{i=1}^s |E^{(i)}|$, $v := \sum_{i=1}^r |V^{(i)}|$, and $v' := \sum_{i=1}^s |V^{(i)}|$. To establish the lemma, we need to show that

$$\left| \mathbb{E}_{H_1} \left[ \prod_{i=0}^{r} \overline{P}_i \right] \right| \le c_1 (D^c \lambda)^{e+e'} \left( D^c \frac{k}{n} \right)^{v+v'-r-s} \left( c_1 D^c \left( \frac{k\epsilon}{n} \vee \frac{1}{\sqrt{n}} \right) \right)^{r+s}.$$

Arguing as in the proof of Lemma A.3, we have

$$\left| \mathbb{E}_{H_1} \left[ \prod_{i=0}^{r} \overline{P}_i \right] \right| \le \left| \mathbb{E}_R \left[ \prod_{i=0}^{r} \overline{P}_i \right] \right|,$$

where the expectation $\mathbb{E}_R(\cdot)$ is with respect to the distribution where the latent assignments $z_i$ for each $\overline{P}_a$'s are sampled without replacement but are independent between different $\overline{P}_a$. Arguing exactly as in the proof of Lemma A.8, we observe

$$\left| \mathbb{E}_R \left[ \prod_{i=0}^{r} \overline{P}_i \right] \right| \le (r+1)^{3(r+1)} 2^{r+1} \max_{\mathcal{B}: \text{partition of } [0,r+1]} \prod_{B \in \mathcal{B}} \left| \mathbb{E}_R \left[ \mathbf{1}_{\mathcal{A}_B} \prod_{i \in B} \overline{P}_i \right] \right|,$$

where $\mathcal{A}_B$ is defined as in the proof of Lemma A.3. If $0 \notin B$, we can simply rely on Lemma A.7 which states that

$$\left| \mathbb{E}_R \left[ \mathbf{1}_{\mathcal{A}_B} \prod_{i \in B} \overline{P}_i \right] \right| \le c_1 D^c (D^c \lambda)^{\sum_{a \in B} |E^{(a)}|} \left( D^c \frac{k}{n} \right)^{\sum_{a \in B} (|V^{(a)}|-1)} \left[ c \frac{c_1 D^c}{\sqrt{n}} \right]^{|B|}.$$

When $0 \in B$, we adapt the proof of Lemma A.7 to establish the following bound

**Lemma C.3.** For any subset $B \subset [0; r]$ such that $0 \in B$, we have

$$\left| \mathbb{E}_R \left[ \mathbf{1}_{\mathcal{A}_B} \prod_{i \in B} \overline{P}_i \right] \right| \le c_1 D^c (D^c \lambda)^a \left( D^c \frac{k}{n} \right)^b \left[ c \frac{c_1 D^c}{\sqrt{n}} \right]^{|B|-1} \left( c_0 \frac{D^{c_1} k \epsilon}{n} \right)^s,$$

$$\text{where } a = \sum_{i \in B \setminus \{0\}} |E^{(i)}| + \sum_{i=1}^{s} |E^{(i)}| \text{ and } b = \sum_{i \in B \setminus \{0\}} (|V^{(i)}| - 1) + (\sum_{i=1}^{s} |V^{(i)}| - 1).$$

We conclude by gathering all the corresponding bounds. $\square$

*Proof of Lemma C.3.* Without loss of generality we assume that $B = [0; r]$. The approach closely follows that of the proof of Lemma A.7. In particular, we introduce the expectation $\tilde{\mathbb{E}}$ with respect to the distribution where we sample latent assignments $z_i$s with replacement.

$$\mathbb{E}_R \left[ \mathbf{1}_{\{A_{[0;r]}}} \prod_{i=0}^{r} \overline{P}_a \right] \le 2^{r+1} (r+1)^{r+1} \max_{T \subset [0;r]} \max_{\mathcal{T}: \text{partition of } T} \left( \frac{4D^2}{n} \right)^{|\mathcal{T}|-1} \prod_{a \in [r] \setminus T} \mathbb{E}[P_a] \prod_{T' \in \mathcal{T}} \tilde{\mathbb{E}} \left[ \mathbf{1}_{\{A_{T'}\}} \prod_{a \in T'} P_a \right]. \quad (107)$$

The term $\mathbb{E}[P_0]$ is controlled in (106). For $i=1, \dots, r$, the quantities $\mathbb{E}[P_i]$ are controlled by Condition C-Moment which is fullfilled for all three models. If $0 \notin T'$, the term $\tilde{\mathbb{E}}[\mathbf{1}_{\{A_{T'}\}} \prod_{a \in T'} P_a]$ is also controlled by C-Variance-Permutation. Hence, we only have to control the expression $\tilde{\mathbb{E}}[\mathbf{1}_{\{A_{T'}\}} \prod_{a \in T'} P_a]$ with
0 ∈ T'. For all three models (HS-P), (SBM-P), and (TS-P), we finally need to control this expectation. We claim that, for all these models, we have

$$
\tilde{\mathbb{E}} \left[ \mathbf{1}_{\{\mathcal{A}_{T'}\}} \prod_{a \in T'} P_a \right] \le c_0 (D^{c_1} \lambda)^a \left(D^{c_1} \frac{k}{n}\right)^b \left(c_0 \frac{D^{c_1}}{\sqrt{n}}\right)^{|T'|-1} \left(c_0 \frac{D^{c_1} k \epsilon}{n}\right)^s, \quad (108)
$$

where $a = \sum_{i \in T' \setminus \{0\}} |E^{(i)}| + \sum_{i=1}^s |E^{(i)}|$ and $b = \sum_{i \in T' \setminus \{0\}} (|V^{(i)}| - 1) + (\sum_{i=1}^s |V^{(i)}| - 1)$. We only prove this claim for (SBM-P), the arguments being quite similar for the other models. Each of the nodes in a connected component must belong to the same group of the SBM; this occurs with probability $(k/n)^b$. We also have the additional restriction that that connected components indexed by $T'$ are connected through their hidden labels, which occurs with probability $(D^2/n)^{|T'|} \le (D^2/\sqrt{n})^{|T'|-1}$. Besides, each of the $s$ connected components belong to an altered group of the SBM, which occurs with probability $k\epsilon/n$. The bound (108) follows. Gathering all these bounds in (107) leads to the desired result. □

D Proofs for LD estimation problems

D.1 Proof of Theorem 7.3

This proof closely follows that of Theorem 7.1 and we only emphasize the few differences. In particular,
we define the Gram matrix Γ of size |G<sub>≤D</sub><sup>(1,2)</sup>| + 1 associated to the basis (1, (Ψ<sub>G</sub><sup>(1,2)</sup>)<sub>G∈G<sub>≤D</sub><sup>(1,2)</sup></sub>) by Γ<sub>G<sup>(1)</sup>,G<sup>(2)</sup></sub> =
E[Ψ<sub>G<sup>(1)</sup></sub><sup>(1,2)</sup>Ψ<sub>G<sup>(2)</sup></sub><sup>(1,2)</sup>] for any (G<sup>(1)</sup>, G<sup>(2)</sup>) ∈ G<sub>≤D</sub><sup>(1,2)</sup>, Γ<sub>1,1</sub> = 1, and Γ<sub>1,G</sub> = E[Ψ<sub>G</sub><sup>(1,2)</sup>] = 0 for G ∈ G<sub>≤D</sub><sup>(1,2)</sup>. First, we
bound the individual terms of Γ by stating a counterpart of Proposition A.1.

For this purpose, we need to define a variant of $d(G^{(1)}, G^{(2)})$. Let

$$
d^{(1,2)}(G^{(1)}, G^{(2)}) := \min_{M \in \mathcal{M}^{(1,2)}} |E_{\Delta}| . \qquad (109)
$$

Note that $d^{(1,2)}(G^{(1)}, G^{(2)}) = 0$ if and only if $G^{(1)}$ and $G^{(2)}$ are equivalent.

**Proposition D.1.** Fix $D \ge 2$. Under *Independent-Sampling*, we assume that *Conditions C-Variance, C-Moment and C-Signal* are fulfilled and that the constant $c_s > 4$ is large compared to the other other ones. Under *Permutation Sampling*, we assume that *Conditions C-Variance, C-Moment, C-Variance-Permutation, and C-Signal* are fulfilled and that the constant $c_s > 4$ is large compared to the other other ones. There exists two positive constants $c$ and $c'$ depending on those arising in *Conditions C-Variance, C-Moment, and possibly C-Variance-Permutation* such that the following holds for any templates $G^{(1)}, G^{(2)} \in \mathcal{G}_{\le D}$.

$$
1 \text{ if } G^{(1)} \neq G^{(2)}:
\left| \mathbb{E} \left[ \Psi_{G^{(1)}}^{(1,2)} \Psi_{G^{(2)}}^{(1,2)} \right] \right| \leq c D^{-c_s} d^{(1,2)}(G^{(1)}, G^{(2)}), \quad (110)
$$

$$
2 \text{ and if } G^{(1)} = G^{(2)}:
\left| \mathbb{E}[(\Psi_{G^{(1)}}^{(1,2)})^2] - 1 \right| \le c' D^{-c_s}. \qquad (111)
$$

Then, we establish that Γ is diagonal dominant as in the proof of Theorem 7.1, the only small difference being that we sum over templates in $G_{\le D}^{(1,2)}$ and that we consider the distance $d^{(1,2)}(G^{(1)}, G^{(2)})$. To handle this, we first observe that, as long as $G^{(1)} \neq G^{(2)}$ in $G_{\le D}^{(1,2)}$, we have $d^{(1,2)}(G^{(1)}, G^{(2)}) \ge 1$. Also, given a positive integer $u$, and a given template $G^{(1)}$, the number of templates $G^{(2)}$ in $G_{\le D}^{(1,2)}$ such that $d^{(1,2)}(G^{(1)}, G^{(2)}) = u$ is bounded by $(u+D)^{2u}$. The rest of the proof is unchanged.

*Proof of Proposition D.1.* This proof closely follows that of Proposition A.1 up to a few changes. First, we claim that the analogues of Lemmas A.2 and A.3 still hold. The proof is postponed to the end of the subsection.

**Lemma D.2.** Consider the same assumptions as in Lemma A.2 or A.3.
1. Let $G^{(1)}, G^{(2)} \in \mathcal{G}_{\le D}^{(1,2)}$ be two templates and let $\mathbf{M} \in \mathcal{M}^{(1,2)} \setminus \mathcal{M}_{\text{PM}}^{(1,2)}$ be a matching. For any $(\pi^{(1)}, \pi^{(2)}) \in \Pi^{(1,2)}(\mathbf{M})$, we have $|\mathbb{E}[\overline{\mathbf{P}}_{G^{(1)},\pi^{(1)}}^{(1,2)} \overline{\mathbf{P}}_{G^{(2)},\pi^{(2)}}^{(1,2)}]| \le \psi[G_{\Delta}]$ where we recall that $\psi[G_{\Delta}]$ is defined in Lemmas A.2 and A.3.

2. Also, for any template $G = (V, E) \in \mathcal{G}_{\le D}^{(1,2)}$ and any $\pi \in \Pi_{V}^{(1,2)}$, we have

$$|\mathbb{E}[\overline{(\mathbf{P}_{G,\pi}^{(1,2)})}^2] - \overline{q}^{|E|} | \leq [2c_{v,2}D^{4+c_{v,1}\vee c_m}\frac{k}{n} + c_{v,3}D^{-c_{v,4}}]\overline{q}^{|E|}.$$

As in Step 1 from the proof of Proposition A.1, we start from the identity

$$\begin{aligned} \mathbb{E}[\Psi_{G^{(1)}}^{(1,2)} \Psi_{G^{(2)}}^{(1,2)}] &= \frac{1}{\sqrt{\mathbb{V}^{(1,2)}(G^{(1)}) \mathbb{V}^{(1,2)}(G^{(2)})}} \sum_{\pi^{(1)} \in \Pi_{V^{(1)}}^{(1,2)}, \pi^{(2)} \in \Pi_{V^{(2)}}^{(1,2)}} \mathbb{E}[\overline{\mathbf{P}}_{G^{(1)},\pi^{(1)}}^{(1,2)} \overline{\mathbf{P}}_{G^{(2)},\pi^{(2)}}^{(1,2)}] \\ &= \frac{1}{\sqrt{\mathbb{V}^{(1,2)}(G^{(1)}) \mathbb{V}^{(1,2)}(G^{(2)})}} \sum_{\mathbf{M} \in \mathcal{M}^{(1,2)}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi^{(1,2)}(\mathbf{M})} \mathbb{E}[\overline{\mathbf{P}}_{G^{(1)},\pi^{(1)}}^{(1,2)} \overline{\mathbf{P}}_{G^{(2)},\pi^{(2)}}^{(1,2)}], \end{aligned}$$

where $\mathcal{M}^{(1,2)}$ is the set of all matchings included in $\mathcal{M}$ that contain $(v_1^{(1)}, v_1^{(2)}), (v_2^{(1)}, v_2^{(2)})$ and where $\Pi^{(1,2)}(\mathbf{M})$ is the set of all pairs $(\pi^{(1)}, \pi^{(2)}) \in \Pi(\mathbf{M})$ such that $\pi^{(a)}(v_1^{(a)}) = 1, \pi^{(a)}(v_2^{(a)}) = 2$ for $a = 1, 2$.

Observe that $|\Pi^{(1,2)}(\mathbf{M})| = \frac{(n-2)!}{(n-|V^{(1)}|)!}$ for a perfect matching. We proceed similarly to the proof of Proposition A.1. For $G^{(1)} \neq G^{(2)}$, we have

$$|\mathbb{E}[\Psi_{G^{(1)}}^{(1,2)} \Psi_{G^{(2)}}^{(1,2)}]| \leq A^{(1,2)}, \qquad (112)$$

whereas, for $G^{(1)} = G^{(2)}$, we have

$$|\mathbb{E}[\Psi_{G^{(1)}}^{(1,2)} \Psi_{G^{(2)}}^{(1,2)}] - 1| \leq A^{(1,2)} + B^{(1,2)}, \qquad (113)$$

where

$$A^{(1,2)} := \left| \frac{1}{\sqrt{\mathbb{V}^{(1,2)}(G^{(1)}) \mathbb{V}^{(1,2)}(G^{(2)})}} \sum_{\mathbf{M} \in \mathcal{M}^{(1,2)} \setminus \mathcal{M}_{\text{PM}}} \sum_{(\pi^{(1)}, \pi^{(2)}) \in \Pi^{(1,2)}(\mathbf{M})} \mathbb{E}[\overline{\mathbf{P}}_{G^{(1)}, \pi^{(1)}} \overline{\mathbf{P}}_{G^{(2)}, \pi^{(2)}}] \right|; \qquad (114)$$

$$B^{(1,2)} := \mathbf{1}\{G^{(1)} = G^{(2)}\} \left| \frac{1}{\overline{q}^{|V^{(1)}|}} \mathbb{E}[(\overline{\mathbf{P}}_{G^{(1)}, \pi^{(1)}})^2] - 1 \right|, \qquad (115)$$

where the last quantity does not depend on the choice of $\pi^{(1)} \in \Pi_{V^{(1)}}$. It was already proven that in the proof of Proposition A.1 that

$$B^{(1,2)} \leq c_0 D^{-c_s}. \qquad (116)$$

Recall that $|\Pi^{(1,2)}(\mathbf{M})| = \frac{(n-2)!}{(n-|V^{(1)}|+|V^{(2)}|-|\mathbf{M}|)!}$. By definition (24) of $\mathbb{V}^{(1,2)}(G)$ and Lemma D.2, we get

$$A^{(1,2)} \leq \frac{1}{\overline{q}^{|E^{(1)}|+|E^{(2)}|/2} \sqrt{|\text{Aut}^{(1,2)}(G^{(1)})||\text{Aut}^{(1,2)}(G^{(2)})|}} \sum_{\mathbf{M} \in \mathcal{M}^{(1,2)} \setminus \mathcal{M}_{\text{PM}}} \frac{\sqrt{(n-|V^{(1)}|)!(n-|V^{(2)}|)!}}{(n-(|V^{(1)}|+|V^{(2)}|-|\mathbf{M}|))!} \psi[G_{\Delta}].$$

Then, arguing as in the end of Step 1 in the proof of Proposition A.1, we get

$$A^{(1,2)} \leq \frac{1}{\overline{q}^{|E^{(1)}|+|E^{(2)}|/2} \sqrt{|\text{Aut}^{(1,2)}(G^{(1)})||\text{Aut}^{(1,2)}(G^{(2)})|}} \sum_{\mathbf{M} \in \mathcal{M}^{(1,2)} \setminus \mathcal{M}_{\text{PM}}} n^{|(U^{(1)}|+|(U^{(2)})|)/2} \psi[G_{\Delta}].$$

Then, Lemma A.4 in Step 3 is still valid upon replacing $d(G^{(1)}, G^{(2)})$ by $d^{(1,2)}(G^{(1)}, G^{(2)})$. We then proceed as in Steps 3 and 4 of the proof of Proposition A.1. We obtain

$$A^{(1,2)} \leq \frac{2c_0}{\sqrt{|\text{Aut}^{(1,2)}(G^{(1)})||\text{Aut}^{(1,2)}(G^{(2)})|}} \sum_{\mathbf{M} \in \mathcal{M}^{(1,2)} \setminus \mathcal{M}_{\text{PM}}} (D^{-2c_s})^{[U+|\mathbf{M}_{\text{SM}}|] \vee d^{(1,2)}(G^{(1)}, G^{(2)}) \vee 1},$$
for some constant $c_0$. We conclude the proof by a slight modification of the Step 4 of the proof of Proposition A.1. As in the latter, we enumerate all possible matchings corresponding to any possible shadow:

$$A^{(1,2)} \le \frac{2D^2 c_{v,2}}{\sqrt{|\mathrm{Aut}^{(1,2)}(G^{(1)})||\mathrm{Aut}^{(1,2)}(G^{(2)})|}} \sum_{\substack{U^{(1)} \subset V^{(1)} \setminus \{v_1^{(1)}, v_2^{(1)}\}, \\ U^{(2)} \subset V^{(2)} \setminus \{v_1^{(2)}, v_2^{(2)}\}, \\ \underline{M} \in \mathcal{M} \setminus \mathcal{M}_{\mathrm{PM}}}} \sum_{\mathbf{M} \in \mathcal{M}_{\mathrm{shadow}}(U^{(1)}, U^{(2)}, \underline{M})} (D^{-2c_s})^{[U+|\mathbf{M}_{\mathrm{SM}}|] \vee d^{(1,2)}(G^{(1)}, G^{(2)}) \vee 1}.$$

where $\mathcal{M}_{\mathrm{shadow}}^{(1,2)}(U^{(1)}, U^{(2)}, \underline{M}) = \mathcal{M}_{\mathrm{shadow}}(U^{(1)}, U^{(2)}, \underline{M}) \cap \mathcal{M}^{(1,2)}$. Similarly to Lemma A.5 we have

$$|\mathcal{M}_{\mathrm{shadow}}^{(1,2)}(U_1, U_2, \underline{M})| \le \min(|\mathrm{Aut}^{(1,2)}(G^{(1)})|, |\mathrm{Aut}^{(1,2)}(G^{(2)})|). \quad (117)$$

Then, as in the end of the proof of Proposition A.1, we conclude that

$$A^{(1,2)} \le cD^{-c_s[d^{(1,2)}(G^{(1)}, G^{(2)}) \vee 1]}.$$

Coming back to (112), we have established the first part of the proposition. The second part of the proposition follows from the latter equality together with (113) and (116). □

**Proof of Lemma D.2.** First, consider the case where neither $v_1^{(a)}$ nor $v_2^{(a)}$ is isolated in $G^{(a)}$ for $a = 1, 2$. Then, we have $\overline{P}_{G^{(a)}, \pi^{(a)}} = \overline{P}_{G^{(a)}, \pi^{(a)}}$ and the bound in Lemma D.2 holds by Lemmas A.2 and A.3. Then, consider the case where both $v_1^{(1)}$ and $v_1^{(2)}$ are isolated and say that neither $v_2^{(1)}$ nor $v_2^{(2)}$ are isolated. Then, $\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}}$ is equal to $\overline{P}_{G^{\prime(1)}, \pi^{\prime(1)}} \overline{P}_{G^{\prime(2)}, \pi^{\prime(2)}}$ where, in $G^{\prime(a)}$, we have removed the isolated node $v_1^{(a)}$ for $a = 1, 2$. Hence, we can apply Lemmas A.2 and A.3 to the latter polynomials. Since the corresponding $G'_{\Delta}$ is equal to $G_{\Delta}$, the result follows again by Lemma D.2. By symmetry, it remains to consider the case where $v_1^{(1)}$ is isolated while $v_1^{(2)}$ is not and neither $v_2^{(1)}$ nor $v_2^{(2)}$ are isolated. Then, $\overline{P}_{G^{(1)}, \pi^{(1)}} \overline{P}_{G^{(2)}, \pi^{(2)}} = \overline{P}_{G^{(1)}, \pi^{\prime(1)}} \overline{P}_{G^{(2)}, \pi^{\prime(2)}}$ and we can apply again Lemma A.2 and A.3. Denote $G''_{\Delta}$ the corresponding symmetric difference graph between $\pi^{\prime(1)}[G^{\prime(1)}]$ and $\pi^{(2)}[G^{(2)}]$, we only have to check that $\psi[G_{\Delta}] \le \psi[G''_{\Delta}]$. The latter is true because $G_{\Delta}$ and $G''_{\Delta}$ have the same number of vertices, edges, connected components, the only differences being that the number of semi-matched nodes is larger for $G_{\Delta}$ than for $G''_{\Delta}$ whereas the number of pure connected components is possibly larger for $G''_{\Delta}$ than for $G_{\Delta}$. □

## D.2 Proof of Theorem 4.1

It follows from Lemma 3.5 and Theorem 3.6 that

$$\mathrm{Corr}^2_{\le D} \le [1-cD^{-2}]^{-1} \sup_{\alpha} \frac{\left( \alpha_0 \mathbb{E}[x] + \sum_{G \in \mathcal{G}^{(1,2)}_{\le D}} \alpha_G \mathbb{E}[x \Psi_G^{(1,2)}] \right)}{\|\alpha\|_2^2} = [1-cD^{-2}]^{-1} \left[ \mathbb{E}[x]^2 + \sum_{G \in \mathcal{G}^{(1,2)}_{\le D}} \mathbb{E}[x \Psi_G^{(1,2)}] \right]^2.$$

We readily have $\mathbb{E}[x] \le (k+1)/(n-k)$ for all six models and we even have $\mathbb{E}[x] \le k^2/[n(n-1)]$ for (HS-I) and (HS-P). Hence, we mainly need to bound the first moments $\mathbb{E}^2[x\Psi_G^{(1,2)}]$ which is done in the following lemma.

**Lemma D.3.** Under the assumptions of Theorem 4.1 and for $c_0 > 0$ a large enough universal constant, all 6 models satisfy

$$|\mathbb{E}[x\Psi_G^{(1,2)}]| \le \frac{k}{n} D^{-c_0/2|E|}.$$
Let us finish the proof before showing the lemma.

$$ \mathrm{Corr}^2_{\leq D} \leq [1 - cD^{-2}]^{-1} \left[ \frac{(k+1)^2}{(n-k)^2} + \frac{k^2}{n^2} \sum_{G \in \mathcal{G}^{(1,2)}_{\leq D}} D^{-c_0|E|} \right] . $$

Since the number of templates $G$ in $\mathcal{G}^{(1,2)}_{\leq D}$ with $v$ nodes and $e$ edges is smaller than $v^{2e}$, we have $\sum_{G \in \mathcal{G}^{(1,2)}_{\leq D}} D^{-c_0|E|} \leq D^{-2}$ as long as $c_0$ is large enough. Together with the fact that $k/n$ is small enough, we conclude that $\mathrm{Corr}^2_{\leq D} \leq \frac{k^2}{n^2}(1 + c/D^2)$.

To get a smaller bound of $\mathrm{Corr}^2_{\leq D}$ for (HS-I) and (HS-P), instead of Lemma D.3, we simply rely on the following lemma.

**Lemma D.4.** Under the assumptions of Theorem 4.1 and for $c_0 > 0$ a large enough universal constant, (HS-I) and (HS-P) satisfy

$$ |\mathbb{E}[x\Psi_G^{(1,2)}]| \leq \frac{k^2}{n^2} D^{-c_0/2|E|} . $$

*Proof of Lemma D.4.* For both (HS-I) and (HS-P), we argue as before to bound the first and second moments of polynomials. Note that these bounds are smaller by a factor $k/n$ than their counterpart in C-Moment and C-Variance.

$$ \begin{aligned} |\mathbb{E}[P_{G,\pi}]| &\leq (D^{c_0}\lambda)^{|E|} \left(D^{c'} \frac{k}{n}\right)^{|V|} ; \\ |\mathbb{E}[P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]| &\leq \lambda^{|E_\Delta|} \bar{p}^{|E_\cup|} \left(D^{c'} \frac{k}{n}\right)^{|V_\Delta|} . \end{aligned} $$

Also, for (HS-P), we readily have

$$ |\tilde{\mathbb{E}}[1\{\mathcal{A}\}P_{G^{(1)},\pi^{(1)}} P_{G^{(2)},\pi^{(2)}}]| \leq \lambda^{|E_\Delta|} \bar{p}^{|E_\cap|} \left(D^{c} \frac{k}{n}\right)^{1+|V_\Delta|-\#CC_\Delta} \left(c \frac{D^{c'}}{\sqrt{n}}\right)^{\#CC_{\text{pure}}} , $$

which is also smaller by a factor $k/n$, than its analogue in C-Variance-Permutation.

<figure><img src="image_7.png" /></figure>

*Proof of Lemma D.3.* As a warmup, consider the case where $E = \{(v_1, v_2)\}$ so that $G$ only contains two nodes. We have

$$ |\mathbb{E}[x\Psi_G^{(1,2)}]| = \frac{\mathbb{E}[x\lambda] - \mathbb{E}[x]\mathbb{E}[x\lambda]}{\sqrt{\bar{q}}} \leq \frac{(k+1)\lambda}{(n-k-1)\sqrt{\bar{q}}} \quad (118) $$

in all six models. Relying on the signal condition in Theorem 4.1, we deduce that $|\mathbb{E}[x\Psi_G^{(1,2)}]| \leq D^{-c_0/2}k/n$.

We now turn to templates $G \in \mathcal{G}^{(1,2)}_{\leq D}$ with $|V| \geq 3$ nodes. We consider three cases depending on the connections between $v_1$ and $v_2$.

**Case 1:** $(v_1, v_2) \notin G$. Let $\pi$ be any labeling in $\Pi^{(1,2)}(V)$. If either $v_1$ or $v_2$ are isolated in $G$, we prune $(G, \pi)$ into $(G', \pi')$ by removing the node. In this way, $\bar{P}_{G,\pi}^{(1,2)} = \bar{P}_{G',\pi'}$. Besides, we define $G^{(0)}$ as the template that only contain the edge $(v_1, v_2)$ and $\pi^{(0)}$ such that $\pi^{(0)}(v_1) = 1$ and $\pi^{(0)}(v_2) = 2$. We have for all models that

$$ \mathbb{E}[xP_{G,\pi}^{(1,2)}] = \frac{1}{\lambda} \mathbb{E}[P_{G^{(0)},\pi^{(0)}} \bar{P}_{G',\pi'}]. $$

Coming back to the definition of $\Psi_G^{(1,2)}$, this leads us to

$$ |\mathbb{E}[x\Psi_G^{(1,2)}]| \leq \frac{n^{|V|-2-1}}{\bar{q}^{|E|/2}} \left( \frac{1}{\lambda} |\mathbb{E}[\bar{P}_{G^{(0)},\pi^{(0)}} \bar{P}_{G',\pi'}]| + \mathbb{E}[x] |\mathbb{E}[\bar{P}_{G',\pi'}]| \right) . \quad (119) $$
By Proposition 7.4, provided that we choose $c_0$ large enough in the statement of Theorem 4.1, all our six models satisfy Condition C-Moment, C-Variance, as well as C-Variance-Permutation for (HS-P), (SBM-P), (TS-P) for some numerical constants and we are therefore in position to apply Lemmas A.2 and A.3 to all six models.

$$
\begin{align*}
\frac{n^{|V|/2-1}}{\bar{q}^{|E|/2}} \mathbb{E}[x] |\mathbb{E}[\overline{P}_{G',\pi'}]| &\le cD^2 \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} n^{|V|/2-1} \left(\frac{D^{c'} k}{n}\right)^{|V'|-\#CC_{G'}} \left[c \frac{D^{c'}}{\sqrt{n}}\right]^{\#CC_{G'}} \\
&\le cD^2 \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} \left[\frac{D^{c'} k}{\sqrt{n}}\right]^{|V'|-\#CC_{G'}} (cD^{c'})^{\#CC_{G'}} \\
&\le cD^2 \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|-|V'|+\#CC_{G'}} \left[\frac{D^{2c'} k \lambda}{\sqrt{n\bar{q}}}\right]^{|V'|-\#CC_{G'}} (cD^{c'})^{\#CC_{G'}} \\
&\le cD^2 \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} \left[c \frac{D^{3c'} k \lambda}{\sqrt{n\bar{q}}}\right]^{|V'|-\#CC_{G'}} \\
&\le \frac{1}{2} \frac{k}{n} D^{-c_0 |E|/2}, \tag{120}
\end{align*}
$$

where we used in the second line that $|V'| \ge |V| - 2$ and that, for $c_0$ large enough, we have $cD^{c'}k/n \le 1$ and we used in the penultimate line that $|V'| \ge 2\#CC_{G'}$. In the last line, we used the conditions of Theorem 4.1 as well as the fact that $|E| \ge |V'| - |\#CC_{G'}|$ and $c_0$ is large enough.

Let us turn to the first term in (119). We again apply Lemma A.3.

$$
\frac{n^{|V|/2-1}}{\lambda \bar{q}^{|E|/2}} |\mathbb{E}[\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G', \pi'}]| \le cD^{2+c'} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} n^{|V|/2-1} \left(\frac{D^{c'} k}{n}\right)^{|V|-a} \left[c \frac{D^{c'}}{\sqrt{n}}\right]^b, \quad (121)
$$

where $a$ corresponds to the number of connected components in the concatenation of $\pi'[G']$ and $\pi^{(0)}[G^{(0)}]$ and $b$ corresponds to the number of pure connected components in the same graph. Note that $a$ and $b$ depend on the connection of $v_1$ and $v_2$ in $G$. We consider four subcases.

**Case 1-a:** both $v_1$ and $v_2$ are isolated in $G$. In the this case, $|V'| = |V| - 2$, $b = \#CC(G') + 1$ and $a = \#CC(G') + 1$. We deduce from (121) that

$$
\begin{align*}
\frac{n^{|V|/2-1}}{\lambda \bar{q}^{|E|/2}} |\mathbb{E}[\overline{P}_{G^{(0)}, \pi^{(0)}} \overline{P}_{G', \pi'}]| &\le cD^{2+c'} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} n^{|V'|/2} \left(\frac{D^{c'} k}{n}\right)^{|V'|+1-\#CC(G')} \left[c \frac{D^{c'}}{\sqrt{n}}\right]^{\#CC(G')+1} \\
&\le c^2 D^{2+3c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} \left(\frac{D^{c'} k}{\sqrt{n}}\right)^{|V'|-\#CC(G')} \left[c D^{c'}\right]^{\#CC(G')} \frac{1}{\sqrt{n}} \\
&\le c^2 D^{2+3c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|-|V'|+\#CC(G')} \left(c \frac{D^{2c'} k \lambda}{\sqrt{n\bar{q}}}\right)^{|V'|-\#CC(G')} \left[c D^{c'}\right]^{\#CC(G')} \frac{1}{\sqrt{n}} \\
&\le c^2 D^{2+3c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|-|V'|+\#CC(G')} \left(c \frac{D^{3c'} k \lambda}{\sqrt{n\bar{q}}}\right)^{|V'|-\#CC(G')} \frac{1}{\sqrt{n}} \\
&\le \frac{1}{2} \frac{k}{n} D^{-c_0 |E|/2}, \tag{122}
\end{align*}
$$

where we argued as for (120).

**Case 1-b:** $v_1$ or $v_2$ is isolated in $G$, but not both of them. In this case, $|V'| = |V| - 1$, $a = \#CC(G')$, and