$b = \#CC(G') - 1$. Arguing as previously, 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 c D^{2+c'} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} n^{|V'|/2-1/2} \left(\frac{D^{c'} k}{n}\right)^{|V'|+1-\#CC(G')} \left[\frac{c D^{c'}}{\sqrt{n}}\right]^{\#CC(G')-1} \\
&\le c D^{2+2c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} \left(c \frac{D^{2c'} k}{\sqrt{n}}\right)^{|V'|-\#CC(G')} \\
&\le c D^{2+2c'} \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')} \\
&\le \frac{1}{2} \frac{k}{n} D^{-c_0 |E|/2} . \tag{123}
\end{align*}
$$

**Case 1-c:** $v_1$ and $v_2$ are not isolated in $G$, but they do not belong to the same connected component. In this case, $|V'| = |V|$, $a = \#CC(G') - 1$, and $b = \#CC(G') - 2$. Arguing as previously, 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 c D^{2+c'} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} n^{|V'|/2-1} \left(\frac{D^{c'} k}{n}\right)^{|V'|+1-\#CC(G')} \left[\frac{c D^{c'}}{\sqrt{n}}\right]^{\#CC(G')-2} \\
&\le c D^{2+2c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} \left(\frac{c D^{2c'} k}{\sqrt{n}}\right)^{|V'|-\#CC(G')} \\
&\le c D^{2+2c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|-|V'|+\#CC(G')} \left(\frac{c 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{124}
\end{align*}
$$

**Case 1-d:** $v_1$ and $v_2$ belong to the same connected component in $G$. In this case, $|V'| = |V|$, $a = \#CC(G')$, and $b = \#CC(G') - 1$. Arguing as previously, 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 c D^{2+c'} \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[\frac{c D^{c'}}{\sqrt{n}}\right]^{\#CC(G')-1} \\
&\le c D^{2+c'} \frac{1}{\sqrt{n}} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|} \left(c \frac{D^{2c'} k}{\sqrt{n}}\right)^{|V'|-\#CC(G')} \\
&\le c^2 D^{2+3c'} \frac{k}{n} \left(D^{c'} \frac{\lambda}{\sqrt{\bar{q}}}\right)^{|E|+1-|V'|+\#CC(G')} \left(\frac{c D^{3c'} \lambda k}{\sqrt{n \bar{q}}}\right)^{|V'|-1-\#CC(G')} \\
&\le \frac{k}{2n} D^{-c_0 |E|/2}, \tag{125}
\end{align*}
$$

where we used again in the last line that all connected components have at least two nodes and we used the conditions on $\lambda$ from the statement of Theorem 4.1. Then, gathering (119 - 125) concludes the proof.

**Case 2:** $(v_1, v_2) \in G$. We decompose $G$ into $G^{(1)}$ and $G'$ where $G^{(1)}$ corresponds to the connected component of $G$ that contains both $v_1$ and $v_2$, whereas $G'$ contains all the other connected components. We only consider the case where $G'$ is non-empty, the case where $G$ has only one connected component being similar. Fix any $\pi \in \Pi_V^{(1,2)}$ and write $\pi^{(1)}$ and $\pi'$ for the corresponding restrictions of the labelings to $V^{(1)}$
and $V'$. By definition of the polynomials $\Psi_G^{(1,2)}$ and $\overline{P}_G^{(1,2)}$, we have

$$ egin{aligned} |\mathbb{E}[x\Psi_G^{(1,2)}]| &= \sqrt{\frac{(n-2)!}{(n-|V|)!|\text{Aut}^{(1,2)}(G)|\overline{q}^{|E|}}} |\mathbb{E}[xP_{G^{(1)},\pi^{(1)}}\overline{P}_{G',\pi'}] - \mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[x\overline{P}_{G',\pi'}]| \\ &\le \frac{n^{|V|/2-1}}{\overline{q}^{|E|/2}} |\mathbb{E}[P_{G^{(1)},\pi^{(1)}}\overline{P}_{G',\pi'}] - \mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[x\overline{P}_{G',\pi'}]| \\ &\le \frac{n^{|V|/2-1}}{\overline{q}^{|E|/2}} [|\mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G',\pi'}]| + |\mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[\overline{P}_{G',\pi'}]| + |\mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[x\overline{P}_{G',\pi'}]|] , \end{aligned} \quad (126) $$

where we used in the second line that conditionally on $z$ the expectation of $P_{G^{(1)},\pi^{(1)}}\overline{P}_{G',\pi'}$ is zero whenever $x=0$.

We first bound the first term $\mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G',\pi'}]$. Since $\pi^{(1)}[G^{(1)}]$ and $\pi^{(1)}[G']$ do not intersect it follows from Lemma A.3 that

$$ \begin{aligned} \frac{n^{|V|/2-1}}{\overline{q}^{|E|/2}} \mathbb{E}[\overline{P}_{G^{(1)},\pi^{(1)}}\overline{P}_{G',\pi'}] &\le cD^2 \left(D^{c'} \frac{\lambda}{\sqrt{\overline{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 \frac{1}{2} \frac{k}{n} D^{-c_0|E|/2}, \end{aligned} \quad (127) $$

where we used that $c_0$ is large enough and we argued as in Case 1. Let us turn to the second term in (126). By Condition C-Moment, we have

$$ \mathbb{E}[P_{G^{(1)},\pi^{(1)}}] \le (D^{c'} \lambda)^{|E^{(1)}|} \left(D^{c'} \frac{k}{n}\right)^{|V^{(1)}|-1} . $$

Also, if $G'$ has a single connected component, we have $\mathbb{E}[\overline{P}_{G',\pi'}] = 0$. If $G'$ has at least two connected component, then $\mathbb{E}[\overline{P}_{G',\pi'}]$ is controlled by Lemma A.3. In particular, we have

$$ |\mathbb{E}[\overline{P}_{G',\pi'}]| \le c D^{c'} \left(D^{c'} \lambda\right)^{|E'|} \left(\frac{D^{c'} k}{n}\right)^{|V'|-\#CC_{G'}} \left(c \frac{D^{c'}}{\sqrt{n}}\right)^{\#CC_{G'}} . $$

We deduce from the two previous bounds that

$$ \begin{aligned} \frac{n^{|V|/2-1}}{\overline{q}^{|E|/2}} |\mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[\overline{P}_{G',\pi'}]| &\le c \frac{1}{\sqrt{n}} D^{c'} \left(D^{c'} \frac{\lambda}{\sqrt{\overline{q}}}\right)^{|E|} \left(\frac{D^{c'} k}{\sqrt{n}}\right)^{|V|-\#CC_G} \left(c D^{c'}\right)^{\#CC_G-1} \\ &\le \frac{k}{n} c^2 D^{3c'} \left(D^{c'} \frac{\lambda}{\sqrt{\overline{q}}}\right)^{|E'|} \left(c \frac{D^{2c'} k}{\sqrt{n}}\right)^{|V|-1-\#CC_G} \\ &\le \frac{k}{n} c^2 D^{3c'} \left(D^{c'} \frac{\lambda}{\sqrt{\overline{q}}}\right)^{|E'|-|V|+1-\#CC_G} \left(c \frac{D^{2c'} k \lambda}{\sqrt{n\overline{q}}}\right)^{|V|-1-\#CC_G} \\ &\le \frac{k}{4n} e^{-c_0|E|/2} . \end{aligned} \quad (128) $$

where we used that $c_0$ is large enough in the statement of the theorem. To handle the last term $|\mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[x\overline{P}_{G',\pi'}]|$, we control $|\mathbb{E}[x\overline{P}_{G',\pi'}]|$ by arguing as in case 1-a. This allows us to prove that $|\mathbb{E}[P_{G^{(1)},\pi^{(1)}}]\mathbb{E}[x\overline{P}_{G',\pi'}]| \le \frac{k}{4n} e^{-c_0|E|/2}$. Then, gathering (127) and (128), we conclude that

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

The result follows.

<figure><img src="image_8.png" /></figure>
E Proofs of the invariance properties

Proof of Lemma 3.1. Let $adv_{\leq D}(f) = \frac{\mathbb{E}_{H_1}[f]}{\sqrt{\mathbb{E}[f^2]}}$ be the objective function optimized in the advantage. Suppose $f^* \in \arg\max_{Y} adv_{\leq D}$ is a polynomial of degree less than $D$ attaining the maximal advantage—it is not hard to see that the maximum exists. Let $\sigma$ be any permutation of $[n]$. By the permutation invariance properties of the distributions under the null and the alternative hypotheses, it turns out that the polynomial defined by $Y \mapsto f^*(Y) = f^*(Y_\sigma)$ also maximizes the advantage. Defining the permutation invariant polynomial $f_{\text{inv}}^*$ by $f_{\text{inv}}^*(Y) = \frac{1}{n!} \sum_{\sigma} f^*(Y_\sigma)$, we get that

$$ \text{adv}_{\leq D} \left( \frac{1}{n!} \sum_{\sigma} f^*(PY) \right) = \frac{\mathbb{E}_{H_1} \left[ \frac{1}{n!} \sum_{\sigma} f^*(Y_\sigma) \right]}{\sqrt{\mathbb{E} \left( \frac{1}{n!} \sum_{\sigma} f^*(Y_\sigma) \right)^2}} . $$

By invariance of $H_1$ with respect to permutations, the numerator is equal to the numerator in $\mathbb{E}_{H_1}(f^*(Y))$. For the denominator, by convexity of the square function and invariance with respect to permutations, we get

$$ \mathbb{E} \left( \frac{1}{n!} \sum_{\sigma} f^*(Y_\sigma) \right)^2 \leq \mathbb{E} (f^*(Y))^2 . $$

Therefore, $adv_{\leq D}(f_{\text{inv}}^*) \geq adv_{\leq D}(f^*)$ and the advantage is maximized by a permutation invariant function. $\square$

Proof of Lemma 3.2. First, we easily check that the constant function 1 and the polynomials $P_{G,\pi}$ with $G = (V, E) \in \mathcal{G}_{\leq D}$ and $\pi \in \Pi_V$ correspond to the canonical basis of polynomials of degree at most $D$ with $n$ variables.

Consider any permutation-invariant polynomial $f \in \mathcal{P}_{\leq D}^{\text{inv}}$. There exist unique numerical values $(\alpha_{G,\pi})_{G \in \mathcal{G}_{\leq D}}$ such that

$$ f(Y) = \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\leq D}, \pi \in \Pi_V} \alpha_{G, \pi} P_{G, \pi}(Y) . \qquad (129) $$

Given any permutation $\sigma$ of $[n]$, we define $f_\sigma$ by $f_\sigma(Y) = f(Y_\sigma)$. By permutation invariance, we have $f_\sigma = f$. As a consequence, it follows from the decomposition of $f$ that

$$ f(Y) = \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\leq D}} \sum_{\pi \in \Pi_V} P_{G, \pi}(Y) \left[ \frac{1}{n!} \sum_{\sigma} \alpha_{G, \pi \circ \sigma^{-1}} \right] . $$

One easily checks that, for a fixed template $G$, $\frac{1}{n!} \sum_{\sigma} \alpha_{G, \pi \circ \sigma^{-1}}$ does not depend on $\pi$. Hence, there exist $\alpha_G$'s such that

$$ f(Y) = \alpha_{\emptyset} + \sum_{G \in \mathcal{G}_{\leq D}} \alpha_G P_{G, \pi}(Y) . \qquad (130) $$

Besides, by uniqueness of the decomposition (129), it follows that $\alpha_{G,\pi} = \alpha_G$ for all $\pi \in \Pi_V$ and the decomposition (130) is therefore unique. $\square$

Proof of Lemma 3.5. Relying on the permutation invariance of the distribution $\mathbb{P}$, we can argue as in the proof of Lemma 3.1, that there exists a polynomial $f$ with $\text{deg}(f) \leq D$ that maximizes $\frac{\mathbb{E}[fX]}{\sqrt{\mathbb{E}[f^2]}}$ over all polynomials of degree at most $D$ and that is invariant by permutations over $\{3, \dots, n\}$; in other words, for all permutations $\sigma : [n] \to [n]$ such that $\sigma(1) = 1$, and $\sigma(2) = 2$, we have $f(Y) = f(Y_\sigma)$ where $Y_\sigma = (Y_{\sigma(i),\sigma(j)})$. Then, similarly to the proof of Lemma 3.2, we check that $(1, (P_G^{(1,2)})_{G \in \mathcal{G}_{\leq D}^{(1,2)}})$ is a basis of the space of polynomials that are invariant by permutations of $\{3, \dots, n\}$. Since $(1, (\Psi_G^{(1,2)})_{G \in \mathcal{G}_{\leq D}^{(1,2)}})$ span the same space, this allows us to conclude. $\square$