### C.2.1 PROOF OF LEMMA 24.

The function $\epsilon \mapsto N_{\Omega}^{(c)}(\epsilon)$ is non-increasing from $[0, \infty[$ to the set of all non-negative integers, it is therefore a piecewise constant function. Thus, for any radius $\epsilon_0 > 0$, there exists a (strictly) larger radius $\epsilon_1$ such that the covering number $N_{\Omega}^{(c)}(\epsilon)$ is equal to a constant, say $N$, over the interval $(\epsilon_0, \epsilon_1)$. To prove the right continuity in $\epsilon_0$, let us show the inequality $N_{\Omega}^{(c)}(\epsilon_0) \le N$ (since we already know the reverse inequality by monotonicity of the covering number function), or equivalently that there exists a cover of $\Omega$ that is composed of $N$ balls of radius $\epsilon_0$.

Given a radius $\epsilon$ and $K$ points $c = (c_1, \dots, c_K) \in \Omega^K$, denote by $C_{\Omega}(c, \epsilon)$ the union of $K$ balls of centers $c_1, \dots, c_K$. In the following, we prove: (1) the existence of some $c_0 \in \Omega^N$ such that $C_{\Omega}(c_0, \epsilon)$ covers $\Omega$ for all $\epsilon \in (\epsilon_0, (\epsilon_1 + \epsilon_0)/2]$; (2) for such a $c_0$, $C_{\Omega}(c_0, \epsilon_0)$ covers $\Omega$. Thus, Lemma 24 will be proved.

(1) Define the set $E_{\Omega}(\epsilon) := \{c \in \Omega^N : \Omega \subseteq C_{\Omega}(c, \epsilon)\}$ for any given radius $\epsilon > 0$. Then, consider the following sequence of nested sets $\tilde{E}_k := E_{\Omega}(\epsilon_0 + (\epsilon_1 - \epsilon_0)/k)$ where $k \ge 2$ is an integer. The Cantor's intersection theorem (recalled in Lemma 25 below) ensures that $\cap_{k \ge 2} \tilde{E}_k \ne \emptyset$, provided that the assumptions of the theorem hold. For clarity, this verification is deferred to the end of the proof. As the set $\cap_{\epsilon_0 < \epsilon < \epsilon_1} E_{\Omega}(\epsilon)$ is equal to $\cap_{k \ge 2} \tilde{E}_k$, one has $\cap_{\epsilon_0 < \epsilon < \epsilon_1} E_{\Omega}(\epsilon) \ne \emptyset$, which means that there exists some $c_0 \in \Omega^N$ such that $C_{\Omega}(c_0, \epsilon)$ covers $\Omega$ for all $\epsilon \in (\epsilon_0, (\epsilon_1 + \epsilon_0)/2]$.

(2) By contradiction, let us prove that $C_{\Omega}(c_0, \epsilon_0)$ covers $\Omega$. If $C_{\Omega}(c_0, \epsilon_0)$ does not cover $\Omega$, then there exists some $y$ in the open set $\Omega \setminus C_{\Omega}(c_0, \epsilon_0)$, which implies that there exists an open ball $B(y, \eta)$ in $\Omega \setminus C_{\Omega}(c_0, \epsilon_0)$ for some radius $\eta > 0$. Hence, $r_W(y, c_{0,j}) \ge \eta + \epsilon_0$ for all $j \in \{1, \dots, N\}$, which means that $C_{\Omega}(c_0, \epsilon)$ does not cover $\Omega$ for the radius $\epsilon = \epsilon_0 + \eta/2$ for instance. This is a contradiction with point (1) above.

**Lemma 25 (Cantor's intersection theorem)** Suppose that $(X, d)$ is a complete metric space, and $C_n$ is a sequence of non-empty closed nested subsets of $X$ whose diameters tend to zero. Then the intersection of the $C_n$ contains exactly one point, that is $\cap_{k=1}^{\infty} C_k = \{x\}$ for some $x$ in $X$.

*Verification of the assumptions of Lemma 25.* Since $(\Omega, r_W)$ is a complete metric space by definition of a pure graphon, the product space $(\Omega^N, r_W^{sup})$ is also complete for the sup-distance $r_W^{sup}(x, y) := \sup_{1 \le j \le N} r_W(x_j, y_j)$ with $x = (x_1, \dots, x_N)$, $y = (y_1, \dots, y_N) \in \Omega^N$. By definition of $\tilde{E}_k$, the sequence $(\tilde{E}_k)_k$ is composed of nested sets, which are also non-empty since $N_{\Omega}^{(c)}(\epsilon) = N$ over $(\epsilon_0, \epsilon_1)$. To prove that each $\tilde{E}_k$ is a closed subset of $\Omega^N$, it is enough to show that $E_{\Omega}(\epsilon)$ is closed for any $\epsilon \in (\epsilon_0, \epsilon_1)$. Let $(x^k)_{k \ge 0}$ be a sequence in $E_{\Omega}(\epsilon)$ such that $x^k \to x \in \Omega^N$ as $k \to \infty$. Then, for any $\eta > 0$, there exists some $k_0$ such that the sup-distance between $x^{k_0} = (x_1^{k_0}, \dots, x_N^{k_0})$ and $x = (x_1, \dots, x_N)$ is at most $\eta$. As $x^{k_0} \in E_{\Omega}(\epsilon)$, one know that, for any $y \in \Omega$, there exists some $j_0$ such that $r_W(y, x_{j_0}^{k_0}) \le \epsilon$. Thus, using the triangle inequality, one has for any $\eta > 0$,

$$r_W(y, x_{j_0}) \le r_W(y, x_{j_0}^{k_0}) + r_W(x_{j_0}^{k_0}, x_{j_0}) \le \epsilon + \eta$$

which implies that $r_W(y, x_{j_0}) \le \epsilon$. Hence, $y \in C_{\Omega}(x, \epsilon)$ for any $y \in \Omega$, which means that $x \in E_{\Omega}(\epsilon)$. $E_{\Omega}(\epsilon)$ is therefore a closed subset of $\Omega^N$. All the conditions of Lemma 25 are checked.
### C.2.1 PROOF OF LEMMA 24.

The function $\epsilon \mapsto N_{\Omega}^{(c)}(\epsilon)$ is non-increasing from $[0, \infty[$ to the set of all non-negative integers, it is therefore a piecewise constant function. Thus, for any radius $\epsilon_0 > 0$, there exists a (strictly) larger radius $\epsilon_1$ such that the covering number $N_{\Omega}^{(c)}(\epsilon)$ is equal to a constant, say $N$, over the interval $(\epsilon_0, \epsilon_1)$. To prove the right continuity in $\epsilon_0$, let us show the inequality $N_{\Omega}^{(c)}(\epsilon_0) \le N$ (since we already know the reverse inequality by monotonicity of the covering number function), or equivalently that there exists a cover of $\Omega$ that is composed of $N$ balls of radius $\epsilon_0$.

Given a radius $\epsilon$ and $K$ points $c = (c_1, \dots, c_K) \in \Omega^K$, denote by $C_{\Omega}(c, \epsilon)$ the union of $K$ balls of centers $c_1, \dots, c_K$. In the following, we prove: (1) the existence of some $c_0 \in \Omega^N$ such that $C_{\Omega}(c_0, \epsilon)$ covers $\Omega$ for all $\epsilon \in (\epsilon_0, (\epsilon_1 + \epsilon_0)/2]$; (2) for such a $c_0$, $C_{\Omega}(c_0, \epsilon_0)$ covers $\Omega$. Thus, Lemma 24 will be proved.

(1) Define the set $E_{\Omega}(\epsilon) := \{c \in \Omega^N : \Omega \subseteq C_{\Omega}(c, \epsilon)\}$ for any given radius $\epsilon > 0$. Then, consider the following sequence of nested sets $\tilde{E}_k := E_{\Omega}(\epsilon_0 + (\epsilon_1 - \epsilon_0)/k)$ where $k \ge 2$ is an integer. The Cantor's intersection theorem (recalled in Lemma 25 below) ensures that $\cap_{k \ge 2} \tilde{E}_k \ne \emptyset$, provided that the assumptions of the theorem hold. For clarity, this verification is deferred to the end of the proof. As the set $\cap_{\epsilon_0 < \epsilon < \epsilon_1} E_{\Omega}(\epsilon)$ is equal to $\cap_{k \ge 2} \tilde{E}_k$, one has $\cap_{\epsilon_0 < \epsilon < \epsilon_1} E_{\Omega}(\epsilon) \ne \emptyset$, which means that there exists some $c_0 \in \Omega^N$ such that $C_{\Omega}(c_0, \epsilon)$ covers $\Omega$ for all $\epsilon \in (\epsilon_0, (\epsilon_1 + \epsilon_0)/2]$.

(2) By contradiction, let us prove that $C_{\Omega}(c_0, \epsilon_0)$ covers $\Omega$. If $C_{\Omega}(c_0, \epsilon_0)$ does not cover $\Omega$, then there exists some $y$ in the open set $\Omega \setminus C_{\Omega}(c_0, \epsilon_0)$, which implies that there exists an open ball $B(y, \eta)$ in $\Omega \setminus C_{\Omega}(c_0, \epsilon_0)$ for some radius $\eta > 0$. Hence, $r_W(y, c_{0,j}) \ge \eta + \epsilon_0$ for all $j \in \{1, \dots, N\}$, which means that $C_{\Omega}(c_0, \epsilon)$ does not cover $\Omega$ for the radius $\epsilon = \epsilon_0 + \eta/2$ for instance. This is a contradiction with point (1) above.

**Lemma 25 (Cantor's intersection theorem)** Suppose that $(X, d)$ is a complete metric space, and $C_n$ is a sequence of non-empty closed nested subsets of $X$ whose diameters tend to zero. Then the intersection of the $C_n$ contains exactly one point, that is $\cap_{k=1}^{\infty} C_k = \{x\}$ for some $x$ in $X$.

*Verification of the assumptions of Lemma 25.* Since $(\Omega, r_W)$ is a complete metric space by definition of a pure graphon, the product space $(\Omega^N, r_W^{sup})$ is also complete for the sup-distance $r_W^{sup}(x, y) := \sup_{1 \le j \le N} r_W(x_j, y_j)$ with $x = (x_1, \dots, x_N)$, $y = (y_1, \dots, y_N) \in \Omega^N$. By definition of $\tilde{E}_k$, the sequence $(\tilde{E}_k)_k$ is composed of nested sets, which are also non-empty since $N_{\Omega}^{(c)}(\epsilon) = N$ over $(\epsilon_0, \epsilon_1)$. To prove that each $\tilde{E}_k$ is a closed subset of $\Omega^N$, it is enough to show that $E_{\Omega}(\epsilon)$ is closed for any $\epsilon \in (\epsilon_0, \epsilon_1)$. Let $(x^k)_{k \ge 0}$ be a sequence in $E_{\Omega}(\epsilon)$ such that $x^k \to x \in \Omega^N$ as $k \to \infty$. Then, for any $\eta > 0$, there exists some $k_0$ such that the sup-distance between $x^k_0 = (x_1^{k_0}, \dots, x_N^{k_0})$ and $x = (x_1, \dots, x_N)$ is at most $\eta$. As $x^k_0 \in E_{\Omega}(\epsilon)$, one know that, for any $y \in \Omega$, there exists some $j_0$ such that $r_W(y, x_{j_0}^{k_0}) \le \epsilon$. Thus, using the triangle inequality, one has for any $\eta > 0$,

$$r_W(y, x_{j_0}) \le r_W(y, x_{j_0}^{k_0}) + r_W(x_{j_0}^{k_0}, x_{j_0}) \le \epsilon + \eta$$

which implies that $r_W(y, x_{j_0}) \le \epsilon$. Hence, $y \in C_{\Omega}(x, \epsilon)$ for any $y \in \Omega$, which means that $x \in E_{\Omega}(\epsilon)$. $E_{\Omega}(\epsilon)$ is therefore a closed subset of $\Omega^N$. All the conditions of Lemma 25 are checked.
The part of Lemma 24 on the covering number is proved. For the packing number, the proof is similar and omitted. ■

### C.3 Proof of Lemma 5: Asymptotic Density of the Sample

Given $\epsilon > 0$, consider a cover of $(\Omega, r_W)$ whose cardinality is the integer $N_{\Omega}^{(c)}(\epsilon/4)$ (written $N$ for brevity) and whose balls are written $B_1, \dots, B_N$. Let us upper bound the probability that (at least) one of these balls contains zero sampled point $\omega_i$. Using the union bound, this probability is smaller than

$$ \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{ B_j \text{ contains zero sampled point among } \omega_1, \dots, \omega_n \} $$

which is upper bounded by $N(1 - \mu(B_j))^n \le N(1 - \beta)^n$ where $\beta := \min_{j \in [N]} \mu(B_j)$. One has $\beta > 0$ since each ball of a pure graphon has non-zero measure. And as $N$ is not equal to infinity by assumption, this probability tends to zero with $n$. Thus, with high probability, all balls $B_j$ from the cover contains at least a sampled point. Finally, the asymptotic density of the sample follows from the fact that each ball of radius $\epsilon$ of $(\Omega, r_W)$ contains a ball $B_j$ from the cover. Lemma 5 is proved. ■

## Appendix D. Estimation of the Neighborhood Distance

### D.1 Proof of Theorem 7: the Upper Bound

Theorem 7 is a direct consequence of the two following propositions. Proposition 26 shows the consistency of the inner products between the rows of the adjacency matrix $A$. That is, $\langle A_i, A_j \rangle_n$ is convergent in probability towards $\langle W(\omega_i, .), W(\omega_j, .) \rangle$ if $i \neq j$. Actually, Proposition 26 gives a uniform convergence over all $i, j \in [n]$, $i \neq j$.

**Proposition 26** The following event on inner products

$$ \mathcal{E}_{in} := \left\{ \forall i, j \in [n] : \left| \langle A_i, A_j \rangle_n - \langle W(\omega_i, .), W(\omega_j, .) \rangle \right| \le 3\sqrt{\frac{\log n}{n}} \right\} $$

holds with probability $\mathbb{P}_{(\Omega, \mu, W)}(\mathcal{E}_{in}) \ge 1 - \frac{2}{n}$ as soon as $n \ge 6$.

We have seen that the neighborhood distance $r_W$ can be decomposed into one crossed term and two quadratic terms as follows

$$ r_W^2(\omega_i, \omega_j) = \langle W(\omega_i, .), W(\omega_i, .) \rangle + \langle W(\omega_j, .), W(\omega_j, .) \rangle - 2\langle W(\omega_i, .), W(\omega_j, .) \rangle. \quad (26) $$

Proposition 26 ensures that the crossed term is consistently estimated. Proposition 27 deals with the quadratic terms $\langle W(\omega_i, .), W(\omega_i, .) \rangle$.

**Proposition 27** Conditionally to the event $\mathcal{E}_{in}$ (defined above), the following inequalities

$$ \forall i \in [n] : \left| \langle A_i, A_{\hat{m}(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| \le 3 r_W(\omega_i, \omega_{m(i)}) + 15 \sqrt{\log(n)/n} $$

hold simultaneously as soon as $n \ge 6$.
The part of Lemma 24 on the covering number is proved. For the packing number, the proof is similar and omitted. ■

### C.3 Proof of Lemma 5: Asymptotic Density of the Sample

Given $\epsilon > 0$, consider a cover of $(\Omega, r_W)$ whose cardinality is the integer $N_{\Omega}^{(c)}(\epsilon/4)$ (written $N$ for brevity) and whose balls are written $B_1, \dots, B_N$. Let us upper bound the probability that (at least) one of these balls contains zero sampled point $\omega_i$. Using the union bound, this probability is smaller than

$$ \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains zero sampled point among } \omega_1, \dots, \omega_n\} $$

which is upper bounded by $N(1 - \mu(B_j))^n \le N(1 - \beta)^n$ where $\beta := \min_{j \in [N]} \mu(B_j)$. One has $\beta > 0$ since each ball of a pure graphon has non-zero measure. And as $N$ is not equal to infinity by assumption, this probability tends to zero with $n$. Thus, with high probability, all balls $B_j$ from the cover contains at least a sampled point. Finally, the asymptotic density of the sample follows from the fact that each ball of radius $\epsilon$ of $(\Omega, r_W)$ contains a ball $B_j$ from the cover. Lemma 5 is proved. ■

## Appendix D. Estimation of the Neighborhood Distance

### D.1 Proof of Theorem 7: the Upper Bound

Theorem 7 is a direct consequence of the two following propositions. Proposition 26 shows the consistency of the inner products between the rows of the adjacency matrix $A$. That is, $\langle A_i, A_j \rangle_n$ is convergent in probability towards $\langle W(\omega_i, .), W(\omega_j, .) \rangle$ if $i \neq j$. Actually, Proposition 26 gives a uniform convergence over all $i, j \in [n], i \neq j$.

**Proposition 26** The following event on inner products

$$ \mathcal{E}_{in} := \left\{ \forall i, j \in [n] : \left| \langle A_i, A_j \rangle_n - \langle W(\omega_i, .), W(\omega_j, .) \rangle \right| \le 3\sqrt{\frac{\log n}{n}} \right\} $$

holds with probability $\mathbb{P}_{(\Omega, \mu, W)}(\mathcal{E}_{in}) \ge 1 - \frac{2}{n}$ as soon as $n \ge 6$.

We have seen that the neighborhood distance $r_W$ can be decomposed into one crossed term and two quadratic terms as follows

$$ r_W^2(\omega_i, \omega_j) = \langle W(\omega_i, .), W(\omega_i, .) \rangle + \langle W(\omega_j, .), W(\omega_j, .) \rangle - 2\langle W(\omega_i, .), W(\omega_j, .) \rangle. \quad (26) $$

Proposition 26 ensures that the crossed term is consistently estimated. Proposition 27 deals with the quadratic terms $\langle W(\omega_i, .), W(\omega_i, .) \rangle$.

**Proposition 27** Conditionally to the event $\mathcal{E}_{in}$ (defined above), the following inequalities

$$ \forall i \in [n] : \left| \langle A_i, A_{\hat{m}(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| \le 3 r_W(\omega_i, \omega_{m(i)}) + 15 \sqrt{\log(n)/n} $$

hold simultaneously as soon as $n \ge 6$.
The estimation error of (26) by our distance estimator

$$ \hat{r}^2(i, j) = \langle A_i, A_{\hat{m}(i)} \rangle_n + \langle A_j, A_{\hat{m}(j)} \rangle_n - 2 \langle A_i, A_j \rangle_n $$

follows directly from Propositions 26 and 27. Theorem 7 is proved.

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

### D.1.1 PROOF OF PROPOSITION 26.

By triangle inequality, the expression

$$ \left| \sum_k \frac{A_{ik}A_{kj}}{n} - \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right| $$

is smaller than

$$ \leq \frac{1}{n} \left| \sum_{k \neq i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right| + \frac{1}{n} \left[ (A_{ii} + A_{jj})A_{ij} + 2 \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right] $$

which is upper bounded by

$$ \leq \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right| + \frac{4}{n} $$

Conditionally to $\omega_i, \omega_j$ (with $i \neq j$), the $n-2$ random variables $\{A_{ik}A_{kj} : k \in [n], k \neq i, j\}$ are independent with a mean $\mathbb{E}[A_{ik}A_{kj}|\omega_i, \omega_j] = \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz)$ for all $k \neq i, j$ (where $\mathbb{E}$ is the expectation with respect to the distribution $\mathbb{P}_{(\Omega, \mu, W)}$). It follows from Hoeffding's inequality that

$$ \mathbb{P}_{(\Omega, \mu, W)} \left( \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right| \geq \epsilon \middle| \omega_i, \omega_j \right) $$

is lower than

$$ \leq 2\exp(-2(n-2)\epsilon^2) \leq 2\exp(-n\epsilon^2) $$

for $\epsilon > 0$ and $n \geq 4$. Since the above inequality is satisfied for almost every $\omega_i, \omega_j \in \Omega$, one has the same upper bound with probability 1 without conditioning. Hence, taking a union bound over all $i \neq j$ one obtain

$$ \mathbb{P}_{(\Omega, \mu, W)} \left( \bigcup_{i,j:i \neq j} \left\{ \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right| \geq \epsilon \right\} \right) \leq 2n^2 \exp(-n\epsilon^2). $$

Then, setting $\epsilon = \sqrt{\frac{3 \log n}{n}}$ one derive

$$ \mathbb{P}_{(\Omega, \mu, W)} \left( \bigcup_{i,j:i \neq j} \left\{ \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z)W(\omega_j, z)\mu(dz) \right| \geq \sqrt{\frac{3 \log n}{n}} \right\} \right) \leq \frac{2}{n}. $$
The estimation error of (26) by our distance estimator

$$ \hat{r}^2(i, j) = \langle A_i, A_{\hat{m}(i)} \rangle_n + \langle A_j, A_{\hat{m}(j)} \rangle_n - 2 \langle A_i, A_j \rangle_n $$

follows directly from Propositions 26 and 27. Theorem 7 is proved.

### D.1.1 PROOF OF PROPOSITION 26.

By triangle inequality, the expression

$$ \left| \sum_k \frac{A_{ik} A_{kj}}{n} - \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| $$

is smaller than

$$ \leq \frac{1}{n} \left| \sum_{k \neq i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| + \frac{1}{n} \left[ (A_{ii} + A_{jj}) A_{ij} + 2 \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right] $$

which is upper bounded by

$$ \leq \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| + \frac{4}{n}. $$

Conditionally to $\omega_i, \omega_j$ (with $i \neq j$), the $n-2$ random variables $\{A_{ik}A_{kj} : k \in [n], k \neq i, j\}$ are independent with a mean $\mathbb{E}[A_{ik}A_{kj}|\omega_i, \omega_j] = \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz)$ for all $k \neq i, j$ (where $\mathbb{E}$ is the expectation with respect to the distribution $\mathbb{P}_{(\Omega, \mu, W)}$). It follows from Hoeffding's inequality that

$$ \mathbb{P}_{(\Omega, \mu, W)} \left( \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| \geq \epsilon \middle| \omega_i, \omega_j \right) $$

is lower than

$$ \leq 2\exp(-2(n-2)\epsilon^2) \leq 2\exp(-n\epsilon^2) $$

for $\epsilon > 0$ and $n \geq 4$. Since the above inequality is satisfied for almost every $\omega_i, \omega_j \in \Omega$, one has the same upper bound with probability 1 without conditioning. Hence, taking a union bound over all $i \neq j$ one obtain

$$ \mathbb{P}_{(\Omega, \mu, W)} \left( \bigcup_{i,j:i \neq j} \left\{ \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| \geq \epsilon \right\} \right) \leq 2n^2 \exp(-n\epsilon^2). $$

Then, setting $\epsilon = \sqrt{\frac{3 \log n}{n}}$ one derive

$$ \mathbb{P}_{(\Omega, \mu, W)} \left( \bigcup_{i,j:i \neq j} \left\{ \frac{1}{n-2} \left| \sum_{k \neq i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| \geq \sqrt{\frac{3 \log n}{n}} \right\} \right) \leq \frac{2}{n}. $$
Combining the above expressions, we get the following inequality

$$ \max_{i,j:i \neq j} \left| \sum_k \frac{A_{ik} \cdot A_{kj}}{n} - \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| \leq \sqrt{\frac{3 \log n}{n}} + \frac{4}{n} \leq 3 \sqrt{\frac{\log n}{n}} $$

with probability at least $1 - \frac{2}{n}$ as soon as $n \geq 6$. The proof of Proposition 26 is complete.

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

### D.1.2 PROOF OF PROPOSITION 27.

$$ \left| \langle A_i, A_{\hat{m}(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| \leq \left| \langle A_i, A_{\hat{m}(i)} - A_{m(i)} \rangle_n \right| + \left| \langle A_i, A_{m(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| \quad (27) $$

For the second term of the upper bound (27),

$$ \begin{aligned} \left| \langle A_i, A_{m(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| &\leq \left| \langle A_i, A_{m(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_{m(i)}, .) \rangle \right| \\ &\quad + \left| \langle W(\omega_i, .), W(\omega_{m(i)}, .) - W(\omega_i, .) \rangle \right| \\ &\leq 3 \sqrt{\log(n)/n} + r_W(\omega_i, \omega_{m(i)}) \end{aligned} $$

by Proposition 26 and Cauchy-Schwarz inequality. For the first term of the upper bound (27), if $\hat{m}(i) \neq m(i)$,

$$ \begin{aligned} \left| \langle A_i, A_{\hat{m}(i)} - A_{m(i)} \rangle_n \right| &\leq \left| \langle A_i - A_{m(i)}, A_{\hat{m}(i)} \rangle_n \right| + \left| \langle A_i - A_{\hat{m}(i)}, A_{m(i)} \rangle_n \right| \\ &\leq \hat{f}(i, m(i)) + \hat{f}(i, \hat{m}(i)) \\ &\leq 2\hat{f}(i, m(i)) \end{aligned} $$

by definition of $\hat{m}(i)$ and $\hat{f}$ in (9). We upper bound $\hat{f}(i, m(i))$ as follows.

$$ \begin{aligned} \hat{f}(i, m(i)) &:= \max_{k \neq i, m(i)} \left| \langle A_k, A_i - A_{m(i)} \rangle_n \right| \\ &\leq \max_{k \neq i, m(i)} \left| \langle W(\omega_k, .), W(\omega_i, .) - W(\omega_{m(i)}, .) \rangle \right| \\ &\quad + 2 \max_{l,t: l \neq t} \left| \langle A_l, A_t \rangle_n - \langle W(\omega_l, .), W(\omega_t, .) \rangle \right| \\ &\leq r_W(\omega_i, \omega_{m(i)}) + 6 \sqrt{\log(n)/n} \end{aligned} $$

by Proposition 26 and Cauchy-Schwarz. Combining the upper bounds on (27), Proposition 27 is proved.

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

## D.2 Proof of Theorem 10 : the Lower Bound

Theorem 10 is a corollary of Theorem 28 (written below). Let $\mathbf{r}_\omega$ denote the $n \times n$ symmetric matrix with entries $r_W(\omega_i, \omega_j)$, $1 \leq i \leq j \leq n$. Given a real $\delta > 0$, a graphon $(\Omega, \mu, W)$, a permutation $\sigma$ of $\{1, \dots, n\}$ and an estimator $\hat{d}$, we define

$$ S_{(\Omega, \mu, W)}(\hat{d}, \sigma, \mathbf{r}_\omega) = \left\{ (i, j) : 32 \left| \hat{d}^2(\sigma(i), \sigma(j)) - r_W^2(\omega_i, \omega_j) \right| \geq 2\delta \text{ and } 2\delta \geq r_W(\omega_i, \omega_{m(i)}) + r_W(\omega_j, \omega_{m(j)}) \right\} $$
Combining the above expressions, we get the following inequality

$$ \max_{i,j:i \neq j} \left| \sum_k \frac{A_{ik} \cdot A_{kj}}{n} - \int_{\Omega} W(\omega_i, z) W(\omega_j, z) \mu(dz) \right| \leq \sqrt{\frac{3 \log n}{n}} + \frac{4}{n} \leq 3 \sqrt{\frac{\log n}{n}} $$

with probability at least $1 - \frac{2}{n}$ as soon as $n \geq 6$. The proof of Proposition 26 is complete.

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

### D.1.2 PROOF OF PROPOSITION 27.

$$ \left| \langle A_i, A_{\hat{m}(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| \leq \left| \langle A_i, A_{\hat{m}(i)} - A_{m(i)} \rangle_n \right| + \left| \langle A_i, A_{m(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| \quad (27) $$

For the second term of the upper bound (27),

$$ \begin{aligned} \left| \langle A_i, A_{m(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_i, .) \rangle \right| &\leq \left| \langle A_i, A_{m(i)} \rangle_n - \langle W(\omega_i, .), W(\omega_{m(i)}, .) \rangle \right| \\ &\quad + \left| \langle W(\omega_i, .), W(\omega_{m(i)}, .) - W(\omega_i, .) \rangle \right| \\ &\leq 3 \sqrt{\log(n)/n} + r_W(\omega_i, \omega_{m(i)}) \end{aligned} $$

by Proposition 26 and Cauchy-Schwarz inequality. For the first term of the upper bound (27), if $\hat{m}(i) \neq m(i)$,

$$ \begin{aligned} \left| \langle A_i, A_{\hat{m}(i)} - A_{m(i)} \rangle_n \right| &\leq \left| \langle A_i - A_{m(i)}, A_{\hat{m}(i)} \rangle_n \right| + \left| \langle A_i - A_{\hat{m}(i)}, A_{m(i)} \rangle_n \right| \\ &\leq \hat{f}(i, m(i)) + \hat{f}(i, \hat{m}(i)) \\ &\leq 2\hat{f}(i, m(i)) \end{aligned} $$

by definition of $\hat{m}(i)$ and $\hat{f}$ in (9). We upper bound $\hat{f}(i, m(i))$ as follows.

$$ \begin{aligned} \hat{f}(i, m(i)) &:= \max_{k \neq i, m(i)} \left| \langle A_k, A_i - A_{m(i)} \rangle_n \right| \\ &\leq \max_{k \neq i, m(i)} \left| \langle W(\omega_k, .), W(\omega_i, .) - W(\omega_{m(i)}, .) \rangle \right| \\ &\quad + 2 \max_{l,t: l \neq t} \left| \langle A_l, A_t \rangle_n - \langle W(\omega_l, .), W(\omega_t, .) \rangle \right| \\ &\leq r_W(\omega_i, \omega_{m(i)}) + 6 \sqrt{\log(n)/n} \end{aligned} $$

by Proposition 26 and Cauchy-Schwarz. Combining the upper bounds on (27), Proposition 27 is proved.

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

## D.2 Proof of Theorem 10 : the Lower Bound

Theorem 10 is a corollary of Theorem 28 (written below). Let $\mathbf{r}_\omega$ denote the $n \times n$ symmetric matrix with entries $r_W(\omega_i, \omega_j)$, $1 \leq i \leq j \leq n$. Given a real $\delta > 0$, a graphon $(\Omega, \mu, W)$, a permutation $\sigma$ of $\{1, \dots, n\}$ and an estimator $\hat{d}$, we define

$$ S_{(\Omega, \mu, W)}(\hat{d}, \sigma, \mathbf{r}_\omega) = \left\{ (i, j) : 32 \left| \hat{d}^2(\sigma(i), \sigma(j)) - r_W^2(\omega_i, \omega_j) \right| \geq 2\delta \quad \text{and} \quad 2\delta \geq r_W(\omega_i, \omega_{m(i)}) + r_W(\omega_j, \omega_{m(j)}) \right\} $$
and

$$ \Phi_{(\Omega, \mu, W)}(\hat{d}, \mathbf{r}_{\omega}) = \inf_{\sigma} \mathrm{Card} \ S_{(\Omega, \mu, W)}(\hat{d}, \sigma, \mathbf{r}_{\omega}) \qquad (28) $$

where $\Phi_{(\Omega, \mu, W)}(\hat{d}, \mathbf{r}_{\omega})$ is the number of pairs $(i, j)$ where the estimator $\hat{d}$ is no better than our estimator $\hat{r}$, roughly speaking. That is, $\Phi_{(\Omega, \mu, W)}(\hat{d}, \mathbf{r}_{\omega})$ counts the pairs $(i, j)$ for which the error of $\hat{d}$ is larger than the bias of our distance estimator $\hat{r}$, which is $r_W(\omega_i, \omega_{m(i)}) + r_W(\omega_j, \omega_{m(j)})$ up to some numerical constants. We put an infimum over all permutations $\sigma$ of the $n$ indices because we consider the problem of recovery of the set of distances $r_W(\omega_i, \omega_j)$, $1 \le i \le j \le n$, regardless of their labeling. According to Theorem 28, there exists a sequence of graphons $(\Omega, \mu, W_n)$ such that for any estimator $\hat{d}$, the quantity $\Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_{\omega})$ grows linearly with $n$ (on an event of positive probability).

**Theorem 28** There exists a sequence $(\Omega, \mu, W_n)_{n \ge 0}$ of SBM such that for all $n \ge 10$, all $\delta \in (\sqrt{\frac{8}{n-2}}, 1/40)$ and some numerical constants $c > 0$ and $p > 0$, the following lower bound holds

$$ \inf_{\hat{d}} \mathbb{P}_{(\Omega, \mu, W_n)} \left[ \Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_{\omega}) > cn \right] \ge p \qquad (29) $$

where $\inf_{\hat{d}}$ is the infimum over all estimators.

Theorem 10 follows from Theorem 28, choosing $\delta = (\sqrt{\frac{\log n}{n}})^{1/(1+\gamma)}$. ■

Note that Theorem 9 follows from Theorem 28 for $\delta = 1/50$.

*Proof of Theorem 28.* The proof follows the general scheme of reduction for testing two hypotheses (see Yu, 1997; Tsybakov, 2009). We start with the definition of some SBM with five communities where the latent space $\Omega$ is $\{C_1, \dots, C_5\}$. We then show that for these SBM, any distance estimator suffers from a large loss.

Let $n \ge 10$ and $\delta \in (\sqrt{8/n - 2}, 1/40)$. Consider the symmetric functions $W_n : \{C_1, \dots, C_5\}^2 \to \{C_1, \dots, C_5\}$ as described in Table 1 below. That is, for the two diagonal blocks $\{C_1, C_2\}^2$ and $\{C_3, C_4, C_5\}^2$, it is a constant function:

$$ W_n(x, y) = \begin{cases} 1/2 & \text{if } (x, y) \in \{C_1, C_2\}^2, \\ 1/2 & \text{if } (x, y) \in \{C_3, C_4, C_5\}^2, \end{cases} $$

and for the upper right corner block $\{C_1, C_2\} \times \{C_3, C_4, C_5\}$:

$$ W_n(x, y) = \begin{cases} 1/2 + u_x \sqrt{\delta/2} & \text{if } y \in C_3, \\ 1/2 + u_x \delta & \text{if } y \in C_4, \\ 1/2 + u_x/2 & \text{if } y \in C_5, \end{cases} \qquad u_x = \begin{cases} +1 & \text{if } x \in C_1, \\ -1 & \text{if } x \in C_2. \end{cases} $$

The latent space $\{C_1, \dots, C_5\}$ is endowed with the probability measure $\mu$ defined as follows:

$$ \mu(C_1) = \mu(C_2) = \frac{1 - 2\eta}{2} $$
and

$$ \Phi_{(\Omega, \mu, W)}(\hat{d}, \mathbf{r}_{\omega}) = \inf_{\sigma} \mathrm{Card} \ S_{(\Omega, \mu, W)}(\hat{d}, \sigma, \mathbf{r}_{\omega}) \qquad (28) $$

where $\Phi_{(\Omega, \mu, W)}(\hat{d}, \mathbf{r}_{\omega})$ is the number of pairs $(i, j)$ where the estimator $\hat{d}$ is no better than our estimator $\hat{r}$, roughly speaking. That is, $\Phi_{(\Omega, \mu, W)}(\hat{d}, \mathbf{r}_{\omega})$ counts the pairs $(i, j)$ for which the error of $\hat{d}$ is larger than the bias of our distance estimator $\hat{r}$, which is $r_W(\omega_i, \omega_{m(i)}) + r_W(\omega_j, \omega_{m(j)})$ up to some numerical constants. We put an infimum over all permutations $\sigma$ of the $n$ indices because we consider the problem of recovery of the set of distances $r_W(\omega_i, \omega_j)$, $1 \le i \le j \le n$, regardless of their labeling. According to Theorem 28, there exists a sequence of graphons $(\Omega, \mu, W_n)$ such that for any estimator $\hat{d}$, the quantity $\Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_{\omega})$ grows linearly with $n$ (on an event of positive probability).

**Theorem 28** There exists a sequence $(\Omega, \mu, W_n)_{n \ge 0}$ of SBM such that for all $n \ge 10$, all $\delta \in (\sqrt{\frac{8}{n-2}}, 1/40)$ and some numerical constants $c > 0$ and $p > 0$, the following lower bound holds

$$ \inf_{\hat{d}} \mathbb{P}_{(\Omega, \mu, W_n)} \left[ \Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_{\omega}) > cn \right] \ge p \qquad (29) $$

where $\inf_{\hat{d}}$ is the infimum over all estimators.

Theorem 10 follows from Theorem 28, choosing $\delta = (\sqrt{\frac{\log n}{n}})^{1/(1+\gamma)}$. ■

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

Note that Theorem 9 follows from Theorem 28 for $\delta = 1/50$.

*Proof of Theorem 28.* The proof follows the general scheme of reduction for testing two hypotheses (see Yu, 1997; Tsybakov, 2009). We start with the definition of some SBM with five communities where the latent space $\Omega$ is $\{C_1, \dots, C_5\}$. We then show that for these SBM, any distance estimator suffers from a large loss.

Let $n \ge 10$ and $\delta \in (\sqrt{8/n - 2}, 1/40)$. Consider the symmetric functions $W_n : \{C_1, \dots, C_5\}^2 \to \{C_1, \dots, C_5\}$ as described in Table 1 below. That is, for the two diagonal blocks $\{C_1, C_2\}^2$ and $\{C_3, C_4, C_5\}^2$, it is a constant function:

$$ W_n(x, y) = \begin{cases} 1/2 & \text{if } (x, y) \in \{C_1, C_2\}^2, \\ 1/2 & \text{if } (x, y) \in \{C_3, C_4, C_5\}^2, \end{cases} $$

and for the upper right corner block $\{C_1, C_2\} \times \{C_3, C_4, C_5\}$:

$$ W_n(x, y) = \begin{cases} 1/2 + u_x \sqrt{\delta/2} & \text{if } y \in C_3, \\ 1/2 + u_x \delta & \text{if } y \in C_4, \\ 1/2 + u_x/2 & \text{if } y \in C_5, \end{cases} \qquad u_x = \begin{cases} +1 & \text{if } x \in C_1, \\ -1 & \text{if } x \in C_2. \end{cases} $$

The latent space $\{C_1, \dots, C_5\}$ is endowed with the probability measure $\mu$ defined as follows:

$$ \mu(C_1) = \mu(C_2) = \frac{1 - 2\eta}{2} $$
$$ \frac{1}{2}\mu(C_3) = \mu(C_4) = \mu(C_5) = \frac{\eta}{2} $$

where $\eta = 2/(n-2)$.

<table><caption>Table 1: values of $W_n(C_i, C_j)$</caption><thead><tr><th></th><th>C<sub>1</sub></th><th>C<sub>2</sub></th><th>C<sub>3</sub></th><th>C<sub>4</sub></th><th>C<sub>5</sub></th></tr></thead><tbody><tr><th>C<sub>1</sub></th><td rowspan="2">1/2</td><td>1/2 + &radic;&delta;/2</td><td>1/2 + &delta;</td><td>1</td></tr><tr><th>C<sub>2</sub></th><td>1/2 - &radic;&delta;/2</td><td>1/2 - &delta;</td><td>0</td></tr><tr><th>C<sub>3</sub></th><td></td><td></td><td rowspan="3">1/2</td><td></td><td></td></tr><tr><th>C<sub>4</sub></th><td></td><td></td><td></td><td></td></tr><tr><th>C<sub>5</sub></th><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table 2: bounds on $r_W^2(C_i, C_j)$</caption><thead><tr><th></th><th>C<sub>1</sub></th><th>C<sub>2</sub></th><th>C<sub>3</sub></th><th>C<sub>4</sub></th><th>C<sub>5</sub></th></tr></thead><tbody><tr><th>C<sub>1</sub></th><td>≤ 2η</td><td>≥ δ/4</td><td>≤ 5δ<sup>2</sup></td><td>≥ 1/4</td></tr><tr><th>C<sub>2</sub></th><td></td><td></td><td></td><td></td></tr></tbody></table>

We compute some bounds on the neighborhood distance associated with the above SBM, see Table 2 for a summary. These bounds follow easily from the definition (4) of the distance. For example,

$$ r_W^2(C_1, C_3) \geq \int_{\{C_1, C_2\}} |W(C_1, z) - W(C_3, z)|^2 \mu(dz) \geq (\mu(C_1) + \mu(C_2))\delta/2 \geq (1 - 2\eta)\delta/2 $$

which is larger than $\delta/4$ since $\eta = 2/(n-2)$ and $n \geq 10$.

We now introduce two events $\mathcal{R}_1$ and $\mathcal{R}_2$ on the sampled points $\omega_1, \dots, \omega_n$, which lead to different sets of distances (for $r_W$), and yet are difficult to decipher for any estimator based on the adjacency matrix $A$. In addition, we want these two events to happen with a positive probability $p$ that is independent of $n$. Observe that the union of the two communities $C_1, C_2$ have a total weight $1 - 2\eta = 1 - 4/(n-2)$ and thus concentrate most of the probability measure, whereas each of the remaining communities $C_3, C_4, C_5$ has a weight of the order of $n^{-1}$. It follows that most of the sampled points $\omega_1, \dots, \omega_n$ belong to the communities $C_1, C_2$ with large probability. In particular, the two following events

$$ \mathcal{R}_1 = \{C_1 \cup C_2, C_4, C_5 \text{ respectively contain n-2, 1, 1 sampled points}\} $$

$$ \mathcal{R}_2 = \{C_1 \cup C_2, C_3 \text{ respectively contain n-2, 2 sampled points}\} $$

happen with a positive probability that is independent of $n$ (Lemma 29).

**Lemma 29** The probability of each event $\mathcal{R}_1$ and $\mathcal{R}_2$ is lower bounded by some numerical constant $p > 0$:

$$ \mathbb{P}(\mathcal{R}_2) \geq \mathbb{P}(\mathcal{R}_1) \geq p $$

$$ \text{where } \mathbb{P}(\mathcal{R}_k) := \mathbb{P}_{(\Omega, \mu, W_n)}(\mathcal{R}_k) = \int_{(\omega_1, \dots, \omega_n) \in \{C_1, \dots, C_5\}^n} 1_{\mathcal{R}_k}(\omega_1, \dots, \omega_n) d\mu(\omega_1) \dots d\mu(\omega_n). $$
$$ \frac{1}{2}\mu(C_3) = \mu(C_4) = \mu(C_5) = \frac{\eta}{2} $$

where $\eta = 2/(n-2)$.

<table><caption>Table 1: values of $W_n(C_i, C_j)$</caption><thead><tr><th></th><th>C<sub>1</sub></th><th>C<sub>2</sub></th><th>C<sub>3</sub></th><th>C<sub>4</sub></th><th>C<sub>5</sub></th></tr></thead><tbody><tr><th>C<sub>1</sub></th><td rowspan="2">1/2</td><td>1/2 + &radic;&delta;/2</td><td>1/2 + &delta;</td><td>1</td></tr><tr><th>C<sub>2</sub></th><td>1/2 - &radic;&delta;/2</td><td>1/2 - &delta;</td><td>0</td></tr><tr><th>C<sub>3</sub></th><td></td><td></td><td rowspan="3">1/2</td><td></td><td></td></tr><tr><th>C<sub>4</sub></th><td></td><td></td><td></td><td></td></tr><tr><th>C<sub>5</sub></th><td></td><td></td><td></td><td></td></tr></tbody></table>

<table><caption>Table 2: bounds on $r_W^2(C_i, C_j)$</caption><thead><tr><th></th><th>C<sub>1</sub></th><th>C<sub>2</sub></th><th>C<sub>3</sub></th><th>C<sub>4</sub></th><th>C<sub>5</sub></th></tr></thead><tbody><tr><th>C<sub>1</sub></th><td>≤ 2η</td><td>≥ δ/4</td><td>≤ 5δ<sup>2</sup></td><td>≥ 1/4</td></tr><tr><th>C<sub>2</sub></th><td></td><td></td><td></td><td></td></tr></tbody></table>

We compute some bounds on the neighborhood distance associated with the above SBM, see Table 2 for a summary. These bounds follow easily from the definition (4) of the distance. For example,

$$ r_W^2(C_1, C_3) \geq \int_{\{C_1, C_2\}} |W(C_1, z) - W(C_3, z)|^2 \mu(dz) \geq (\mu(C_1) + \mu(C_2))\delta/2 \geq (1 - 2\eta)\delta/2 $$

which is larger than $\delta/4$ since $\eta = 2/(n-2)$ and $n \geq 10$.

We now introduce two events $\mathcal{R}_1$ and $\mathcal{R}_2$ on the sampled points $\omega_1, \dots, \omega_n$, which lead to different sets of distances (for $r_W$), and yet are difficult to decipher for any estimator based on the adjacency matrix $A$. In addition, we want these two events to happen with a positive probability $p$ that is independent of $n$. Observe that the union of the two communities $C_1, C_2$ have a total weight $1 - 2\eta = 1 - 4/(n-2)$ and thus concentrate most of the probability measure, whereas each of the remaining communities $C_3, C_4, C_5$ has a weight of the order of $n^{-1}$. It follows that most of the sampled points $\omega_1, \dots, \omega_n$ belong to the communities $C_1, C_2$ with large probability. In particular, the two following events

$$ \mathcal{R}_1 = \{C_1 \cup C_2, C_4, C_5 \text{ respectively contain n-2, 1, 1 sampled points}\} $$

$$ \mathcal{R}_2 = \{C_1 \cup C_2, C_3 \text{ respectively contain n-2, 2 sampled points}\} $$

happen with a positive probability that is independent of $n$ (Lemma 29).

**Lemma 29** The probability of each event $\mathcal{R}_1$ and $\mathcal{R}_2$ is lower bounded by some numerical constant $p > 0$:

$$ \mathbb{P}(\mathcal{R}_2) \geq \mathbb{P}(\mathcal{R}_1) \geq p $$

$$ \text{where } \mathbb{P}(\mathcal{R}_k) := \mathbb{P}_{(\Omega, \mu, W_n)}(\mathcal{R}_k) = \int_{(\omega_1, \dots, \omega_n) \in \{C_1, \dots, C_5\}^n} 1_{\mathcal{R}_k}(\omega_1, \dots, \omega_n) d\mu(\omega_1) \dots d\mu(\omega_n). $$
One of the interests of the two events $\mathcal{R}_1, \mathcal{R}_2$ is to lead to different sets of distances. Specifically, if $\mathcal{R}_1$ (resp. $\mathcal{R}_2$) holds, the random matrix $\mathbf{r}_\omega = [r_W(\omega_i, \omega_j)]_{i,j \in [n]}$ of distances is denoted by $\mathbf{r}_1 = [r_1(i,j)]_{i,j \in [n]}$ (resp. $\mathbf{r}_2 = [r_2(i,j)]_{i,j \in [n]}$). We measure the difference between both matrices $\mathbf{r}_1, \mathbf{r}_2$ of distances as follows:

$$ \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) = \inf_{\sigma} \mathrm{Card} \left\{ (i,j) : \begin{array}{l} 16|r_2^2(i,j) - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \\ r_2(i,m(i)) + r_2(j,m(j)) \le 2\delta \\ r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le 2\delta \end{array} \right\} \quad (30) $$

where $\tilde{\Phi}$ is the number of pairs $(i, j)$ on which $\mathbf{r}_1$ and $\mathbf{r}_2$ are separated by at least the bias of our distance estimator $\hat{r}$ (up to some numerical constants). Note that this measure is independent of the labeling $i \in \{1, \dots, n\}$ since an infimum is taken over all permutations $\sigma$ of the $n$ indices. Lemma 30 ensures that $\mathbf{r}_1$ and $\mathbf{r}_2$ are different enough for a number of pairs $(i, j)$ that is linear with $n$, regardless of their labeling.

**Lemma 30** There exists a numerical constant $c$ such that $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) \ge 2cn$.

So far, we have two events of positive probability which lead to two different sets of distances. It remains to see that they are difficult to decipher from the observed adjacency matrix $A$ (Lemma 31). For simplicity, write $\mathbb{P}$ for $\mathbb{P}_{(\Omega, \mu, W)}$ in the following, and $\omega$ the $n$-tuple $(\omega_1, \dots, \omega_n)$, and $\{0, 1\}_{\mathrm{sym}}^{n \times n}$ the set of binary symmetric matrices of size $n \times n$.

**Lemma 31** For any $M \in \{0, 1\}_{\mathrm{sym}}^{n \times n}$, one has

$$ \mathbb{P}[A = M | \omega \in \mathcal{R}_1] = \mathbb{P}[A = M | \omega \in \mathcal{R}_2]. $$

We now have all the ingredients to lower bound $\mathbb{P}[\Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_\omega) > cn]$ and prove Theorem 28. For clarity, $\Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_\omega)$ is denoted by $\Phi(\hat{d}, \mathbf{r}_\omega)$ in the following. Then, one has

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn] \ge \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn | \mathcal{R}_1] \mathbb{P}(\mathcal{R}_1) + \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn | \mathcal{R}_2] \mathbb{P}(\mathcal{R}_2) $$

By definition of the SBM, the matrix $\mathbf{r}_1$ remains the same for any $\omega \in \mathcal{R}_1$, up to a permutation of the labeling. Combining with the fact that $\Phi$ is independent of the labeling, one obtain that $\Phi(\hat{d}, \mathbf{r}_1)$ takes a same value for all $\omega \in \mathcal{R}_1$. Similarly, $\Phi(\hat{d}, \mathbf{r}_2)$ takes the same value for all $\omega \in \mathcal{R}_2$. Hence, the above display says that $\mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn]$ is larger than

$$ (\mathbb{P}[\Phi(\hat{d}, \mathbf{r}_1) > cn | \mathcal{R}_1] + \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2]) (\mathbb{P}(\mathcal{R}_1) \wedge \mathbb{P}(\mathcal{R}_2)) $$

and since $\mathbb{P}(\mathcal{R}_1) \wedge \mathbb{P}(\mathcal{R}_2) \ge p$ by Lemma 29, one has

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn] \ge (\mathbb{P}[\Phi(\hat{d}, \mathbf{r}_1) > cn | \mathcal{R}_1] + \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2])p $$
One of the interests of the two events $\mathcal{R}_1, \mathcal{R}_2$ is to lead to different sets of distances. Specifically, if $\mathcal{R}_1$ (resp. $\mathcal{R}_2$) holds, the random matrix $\mathbf{r}_\omega = [r_W(\omega_i, \omega_j)]_{i,j \in [n]}$ of distances is denoted by $\mathbf{r}_1 = [r_1(i,j)]_{i,j \in [n]}$ (resp. $\mathbf{r}_2 = [r_2(i,j)]_{i,j \in [n]}$). We measure the difference between both matrices $\mathbf{r}_1, \mathbf{r}_2$ of distances as follows:

$$ \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) = \inf_{\sigma} \mathrm{Card} \left\{ (i,j) : \begin{array}{l} 16|r_2^2(i,j) - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \\ r_2(i,m(i)) + r_2(j,m(j)) \le 2\delta \\ r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le 2\delta \end{array} \right\} \quad (30) $$

where $\tilde{\Phi}$ is the number of pairs $(i,j)$ on which $\mathbf{r}_1$ and $\mathbf{r}_2$ are separated by at least the bias of our distance estimator $\hat{r}$ (up to some numerical constants). Note that this measure is independent of the labeling $i \in \{1, \dots, n\}$ since an infimum is taken over all permutations $\sigma$ of the $n$ indices. Lemma 30 ensures that $\mathbf{r}_1$ and $\mathbf{r}_2$ are different enough for a number of pairs $(i,j)$ that is linear with $n$, regardless of their labeling.

**Lemma 30** There exists a numerical constant $c$ such that $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) \ge 2cn$.

So far, we have two events of positive probability which lead to two different sets of distances. It remains to see that they are difficult to decipher from the observed adjacency matrix $A$ (Lemma 31). For simplicity, write $\mathbb{P}$ for $\mathbb{P}_{(\Omega, \mu, W)}$ in the following, and $\omega$ the $n$-tuple $(\omega_1, \dots, \omega_n)$, and $\{0, 1\}_{\mathrm{sym}}^{n \times n}$ the set of binary symmetric matrices of size $n \times n$.

**Lemma 31** For any $M \in \{0, 1\}_{\mathrm{sym}}^{n \times n}$, one has

$$ \mathbb{P}[A = M | \omega \in \mathcal{R}_1] = \mathbb{P}[A = M | \omega \in \mathcal{R}_2]. $$

We now have all the ingredients to lower bound $\mathbb{P}[\Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_\omega) > cn]$ and prove Theorem 28. For clarity, $\Phi_{(\Omega, \mu, W_n)}(\hat{d}, \mathbf{r}_\omega)$ is denoted by $\Phi(\hat{d}, \mathbf{r}_\omega)$ in the following. Then, one has

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn] \ge \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn | \mathcal{R}_1] \mathbb{P}(\mathcal{R}_1) \\ + \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn | \mathcal{R}_2] \mathbb{P}(\mathcal{R}_2) $$

By definition of the SBM, the matrix $\mathbf{r}_1$ remains the same for any $\omega \in \mathcal{R}_1$, up to a permutation of the labeling. Combining with the fact that $\Phi$ is independent of the labeling, one obtain that $\Phi(\hat{d}, \mathbf{r}_1)$ takes a same value for all $\omega \in \mathcal{R}_1$. Similarly, $\Phi(\hat{d}, \mathbf{r}_2)$ takes the same value for all $\omega \in \mathcal{R}_2$. Hence, the above display says that $\mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn]$ is larger than

$$ (\mathbb{P}[\Phi(\hat{d}, \mathbf{r}_1) > cn | \mathcal{R}_1] + \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2]) (\mathbb{P}(\mathcal{R}_1) \wedge \mathbb{P}(\mathcal{R}_2)) $$

and since $\mathbb{P}(\mathcal{R}_1) \wedge \mathbb{P}(\mathcal{R}_2) \ge p$ by Lemma 29, one has

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn] \ge (\mathbb{P}[\Phi(\hat{d}, \mathbf{r}_1) > cn | \mathcal{R}_1] + \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2])p $$
Now assume that

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2] \ge \mathbb{P}[cn > \Phi(\hat{d}, \mathbf{r}_1) | \mathcal{R}_1]. \quad (31) $$

Then, combining the two last inequalities gives

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_\omega) > cn] \ge p $$

which gives the lower bound of Theorem 28.

Let us show that (31) holds. Lemma 31 gives

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2] = \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_1]. $$

Then, we use the generalized triangle inequality of Lemma 32 with $B = \hat{d}$.

**Lemma 32** For any $B \in \{0, 1\}_{sym}^{n \times n}$, we have $\Phi(B, \mathbf{r}_1) + \Phi(B, \mathbf{r}_2) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$.

That is,

$$ \Phi(\hat{d}, \mathbf{r}_2) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) - \Phi(\hat{d}, \mathbf{r}_1) $$

which is larger than

$$ 2cn - \Phi(\hat{d}, \mathbf{r}_1) $$

by Lemma 30. Combining the above displays, one has

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2] \ge \mathbb{P}[cn > \Phi(\hat{d}, \mathbf{r}_1) | \mathcal{R}_1]. $$

The line (31) is therefore proved and Theorem 28 follows.

We now show the technical lemmas, used in the proof of Theorem 28.

### D.2.1 PROOF OF LEMMA 29.

Let $n \ge 10$. We show that each of the two events $\mathcal{R}_1, \mathcal{R}_2$ occurs with a positive probability that is independent of $n$. By definition of the events, one has

$$ \mathbb{P}(\mathcal{R}_2) \ge \mathbb{P}(\mathcal{R}_1) = \frac{n(n-1)}{2} \left(\frac{\eta}{2}\right)^2 (1-2\eta)^{n-2} $$

which is equal to the following expression for $\eta = 2/(n-2)$,

$$ \frac{n(n-2)}{2} \left(\frac{1}{n-2}\right)^2 \exp\left[(n-2)\log\left(1 - \frac{4}{n-2}\right)\right] $$

Using $\log(1-x) \ge -x/(1-x)$ for all $x$ in $]0, 1[$,

$$ \mathbb{P}(\mathcal{R}_1) \ge \exp\left[-\frac{4}{1 - \frac{4}{n-2}}\right] $$

which is larger than some positive numerical constant. Lemma 29 is proved.
Now assume that

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2] \geq \mathbb{P}[cn > \Phi(\hat{d}, \mathbf{r}_1) | \mathcal{R}_1]. \quad (31) $$

Then, combining the two last inequalities gives

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_{\omega}) > cn] \geq p $$

which gives the lower bound of Theorem 28.

Let us show that (31) holds. Lemma 31 gives

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2] = \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_1]. $$

Then, we use the generalized triangle inequality of Lemma 32 with $B = \hat{d}$.

**Lemma 32** For any $B \in \{0, 1\}_{sym}^{n \times n}$, we have $\Phi(B, \mathbf{r}_1) + \Phi(B, \mathbf{r}_2) \geq \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$.

That is,

$$ \Phi(\hat{d}, \mathbf{r}_2) \geq \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) - \Phi(\hat{d}, \mathbf{r}_1) $$

which is larger than

$$ 2cn - \Phi(\hat{d}, \mathbf{r}_1) $$

by Lemma 30. Combining the above displays, one has

$$ \mathbb{P}[\Phi(\hat{d}, \mathbf{r}_2) > cn | \mathcal{R}_2] \geq \mathbb{P}[cn > \Phi(\hat{d}, \mathbf{r}_1) | \mathcal{R}_1]. $$

The line (31) is therefore proved and Theorem 28 follows.

We now show the technical lemmas, used in the proof of Theorem 28.

### D.2.1 PROOF OF LEMMA 29.

Let $n \geq 10$. We show that each of the two events $\mathcal{R}_1, \mathcal{R}_2$ occurs with a positive probability that is independent of $n$. By definition of the events, one has

$$ \mathbb{P}(\mathcal{R}_2) \geq \mathbb{P}(\mathcal{R}_1) = \frac{n(n-1)}{2} \left(\frac{\eta}{2}\right)^2 (1-2\eta)^{n-2} $$

which is equal to the following expression for $\eta = 2/(n-2)$,

$$ \frac{n(n-2)}{2} \left(\frac{1}{n-2}\right)^2 \exp\left[(n-2)\log\left(1 - \frac{4}{n-2}\right)\right] $$

Using $\log(1-x) \geq -x/(1-x)$ for all $x$ in $]0, 1[$,

$$ \mathbb{P}(\mathcal{R}_1) \geq \exp\left[-\frac{4}{1 - \frac{4}{n-2}}\right] $$

which is larger than some positive numerical constant. Lemma 29 is proved.
### D.2.2 PROOF OF LEMMA 30.

The proof consists in finding a lower bound of $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$ that is linear with $n$. As $\tilde{\Phi}$ is independent of the labeling of the set of distances $\mathbf{r}_1$ and $\mathbf{r}_2$, one can assume the two following labelings without the loss of generality. For the matrix $\mathbf{r}_1$ (defined on the event $\mathcal{R}_1$), assume the $(n-1)^{th}$ and $n^{th}$ columns correspond to the two sampled points in $\{C_4, C_5\}$. For $\mathbf{r}_2$ (defined on $\mathcal{R}_2$), assume the $(n-1)^{th}$ and $n^{th}$ columns correspond to the two sampled points in $C_3$. Accordingly, the $n-2$ first columns of $\mathbf{r}_1$ and $\mathbf{r}_2$ are associated with the sampled points in $\{C_1, C_2\}$.

We focus on the $(n-1)^{th}$ and $n^{th}$ columns of $\mathbf{r}_2$ corresponding to the points in $C_3$. For the measure $\tilde{\Phi}$, at least one these two columns will be necessarily compared to one of the $n-1$ first columns of $\mathbf{r}_1$. In other words, the distances associated with a point in $C_3$ will be compared to the distances associated with a point in $C_1, C_2$ or $C_4$. As we can see in Table 1 and 2, such comparisons will lead to the lower bound $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) \ge n-3$. The corresponding computation are done below, focusing on the two vectors of distances $[r_2(k, n-1)]_{k \le n-2}$ and $[r_2(k, n)]_{k \le n-2}$.

By definition, $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$ is based on the infimum over all permutations. Let $\sigma$ be any permutation of $\{1, \dots, n\}$ and prove the lower bound for $\sigma$, distinguishing three cases.

**Case 1:** if $\sigma(n) = n$, then $\sigma(j) \in \{1, \dots, n-1\}$ for all $j \le n-1$. For convenience, note $C_{i,j}$ for a point in $C_i \cup C_j$. For all $j \le n-2$, one has

$$ \left| r_2^2(j, n-1) - r_1^2(\sigma(j), \sigma(n-1)) \right| = \left| r_W^2(C_{1,2}, C_3) - r_W^2(C_{1,2,4}, C_{1,2,4}) \right| $$

according to the chosen labelings (described above). It follows from Table 2 that:

$$ \left| r_W^2(C_{1,2}, C_3) - r_W^2(C_{1,2,4}, C_{1,2,4}) \right| \ge \delta/4 - \max(2\eta, 5\delta^2) $$

which is equal to $\delta(1/4 - 5\delta)$ since $\eta = 2/(n-2)$ and $\delta^2 > 8/(n-2)$ by assumption. Hence, using the condition $\delta \le 1/40$, it is larger than $\delta/8$, so that,

$$ 16 \left| r_2^2(j, n-1) - r_1^2(\sigma(j), \sigma(n-1)) \right| \ge 2\delta $$

for all $j \le n-2$.

It remains to upper bound the bias terms by $2\delta$. The ones related to $\mathbf{r}_2$ are easily obtained: for all $j \le n$,

$$ r_2(j, m(j)) \le r_W(C_1, C_2) \le 2\eta \le \delta $$

since on the event $\mathcal{R}_2$, a point $\omega_j$ is either in $C_1 \cup C_2$ and hence $r_2(j, m(j)) \le r_W(C_1, C_2)$, or in $C_3$ and thus $r_2(j, m(j)) = 0$ (because its nearest neighbor is in $C_3$ too). This gives the bounds on the bias terms

$$ r_2(i, m(i)) + r_2(j, m(j)) \le 2\delta $$

for all $i, j$. The corresponding bounds for $\mathbf{r}_1$ are similarly obtained from Table 1, but with more calculations. It is therefore encapsulated in the following lemma.

**Lemma 33** If $\sigma(n) = n$, we have $r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le 2\delta$ for all $j, i \le n-1$ such that $i \ne j$.
### D.2.2 PROOF OF LEMMA 30.

The proof consists in finding a lower bound of $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$ that is linear with $n$. As $\tilde{\Phi}$ is independent of the labeling of the set of distances $\mathbf{r}_1$ and $\mathbf{r}_2$, one can assume the two following labelings without the loss of generality. For the matrix $\mathbf{r}_1$ (defined on the event $\mathcal{R}_1$), assume the $(n-1)^{th}$ and $n^{th}$ columns correspond to the two sampled points in $\{C_4, C_5\}$. For $\mathbf{r}_2$ (defined on $\mathcal{R}_2$), assume the $(n-1)^{th}$ and $n^{th}$ columns correspond to the two sampled points in $C_3$. Accordingly, the $n-2$ first columns of $\mathbf{r}_1$ and $\mathbf{r}_2$ are associated with the sampled points in $\{C_1, C_2\}$.

We focus on the $(n-1)^{th}$ and $n^{th}$ columns of $\mathbf{r}_2$ corresponding to the points in $C_3$. For the measure $\tilde{\Phi}$, at least one these two columns will be necessarily compared to one of the $n-1$ first columns of $\mathbf{r}_1$. In other words, the distances associated with a point in $C_3$ will be compared to the distances associated with a point in $C_1, C_2$ or $C_4$. As we can see in Table 1 and 2, such comparisons will lead to the lower bound $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) \ge n-3$. The corresponding computation are done below, focusing on the two vectors of distances $[r_2(k, n-1)]_{k \le n-2}$ and $[r_2(k, n)]_{k \le n-2}$.

By definition, $\tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$ is based on the infimum over all permutations. Let $\sigma$ be any permutation of $\{1, \dots, n\}$ and prove the lower bound for $\sigma$, distinguishing three cases.

**Case 1:** if $\sigma(n) = n$, then $\sigma(j) \in \{1, \dots, n-1\}$ for all $j \le n-1$. For convenience, note $C_{i,j}$ for a point in $C_i \cup C_j$. For all $j \le n-2$, one has

$$ \left| r_2^2(j, n-1) - r_1^2(\sigma(j), \sigma(n-1)) \right| = \left| r_W^2(C_{1,2}, C_3) - r_W^2(C_{1,2,4}, C_{1,2,4}) \right| $$

according to the chosen labelings (described above). It follows from Table 2 that:

$$ \left| r_W^2(C_{1,2}, C_3) - r_W^2(C_{1,2,4}, C_{1,2,4}) \right| \ge \delta/4 - \max(2\eta, 5\delta^2) $$

which is equal to $\delta(1/4 - 5\delta)$ since $\eta = 2/(n-2)$ and $\delta^2 > 8/(n-2)$ by assumption. Hence, using the condition $\delta \le 1/40$, it is larger than $\delta/8$, so that,

$$ 16 \left| r_2^2(j, n-1) - r_1^2(\sigma(j), \sigma(n-1)) \right| \ge 2\delta $$

for all $j \le n-2$.

It remains to upper bound the bias terms by $2\delta$. The ones related to $\mathbf{r}_2$ are easily obtained: for all $j \le n$,

$$ r_2(j, m(j)) \le r_W(C_1, C_2) \le 2\eta \le \delta $$

since on the event $\mathcal{R}_2$, a point $\omega_j$ is either in $C_1 \cup C_2$ and hence $r_2(j, m(j)) \le r_W(C_1, C_2)$, or in $C_3$ and thus $r_2(j, m(j)) = 0$ (because its nearest neighbor is in $C_3$ too). This gives the bounds on the bias terms

$$ r_2(i, m(i)) + r_2(j, m(j)) \le 2\delta $$

for all $i, j$. The corresponding bounds for $\mathbf{r}_1$ are similarly obtained from Table 1, but with more calculations. It is therefore encapsulated in the following lemma.

**Lemma 33** If $\sigma(n) = n$, we have $r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le 2\delta$ for all $j, i \le n-1$ such that $i \ne j$.
Combining the above displays, we obtain the lower bound

$$ \text{Card} \left\{ (i,j) : \begin{array}{l} 16|r_2^2(i,j) - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \\ r_2(i,m(i)) + r_2(j,m(j)) \le 2\delta \\ r_1(\sigma(i),m(\sigma(i))) + r_1(\sigma(j),m(\sigma(j))) \le 2\delta \end{array} \right\} \ge n-3 \quad (32) $$

for all permutations fulfilling $\sigma(n) = n$.

**Case 2:** if $\sigma(n-1) = n$, then $\sigma(n), \sigma(j) \in \{1, \dots, n-1\}$ for all $j \le n-2$. Following the same proof as above, we can show that $|r_2^2(n,j) - r_1^2(\sigma(n), \sigma(j))| \ge 2\delta$ for all $j \le n-2$. Likewise, the bounds on the bias terms are obtained as before. The inequality (32) is therefore proved for all permutations fulfilling $\sigma(n-1) = n$.

**Case 3:** if $\sigma(n) \ne n$ and $\sigma(n-1) \ne n$. Following the same proof as above, we can show that $|r_2^2(n,j) - r_1^2(\sigma(n), \sigma(j))| \ge 2\delta$ for all $j \le n-2$ such that $j \ne \sigma^{-1}(n)$. The inequality (32) is therefore proved for all permutations $\sigma(n) \ne n$ and $\sigma(n-1) \ne n$.

Finally, the lower bound (32) is true for all permutations $\sigma$, in particular for the infimum over all of them. Lemma 30 is proved. ■

### D.2.3 PROOF OF LEMMA 33.

Let us upper bound the bias terms for $\mathbf{r}_1$, in the case of an arbitrary permutation $\sigma$ fulfilling $\sigma(n) = n$. On the event $\mathcal{R}_1$, one has

$$ r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le r_W(\mathcal{C}_1, \mathcal{C}_4) + r_W(\mathcal{C}_1, \mathcal{C}_2). $$

for all $j, i \le n-1$ such that $j \ne i$. In Table 1 and Table 2, one observes that

$$ \begin{aligned} r_W(\mathcal{C}_1, \mathcal{C}_2) &\le \sqrt{2\eta} \\ r_W(\mathcal{C}_1, \mathcal{C}_4) &\le \sqrt{\delta^2(1 - 2\eta) + (\delta/2)\eta + \delta^2(\eta/2) + (1/4)(\eta/2)}. \end{aligned} $$

The second bound is smaller than $\sqrt{\delta^2(1 - (3\eta/2)) + \eta/4}$ since $(\delta/2)\eta \le (1/4)(\eta/2)$ (using the assumption $\delta \le 1/40$). Hence,

$$ r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le \sqrt{\delta^2 + \eta/4} + \sqrt{2\eta} $$

which is lower than $\delta + 2\sqrt{\eta}$, and again, lower than $2\delta$ (since $\sqrt{\eta} = \sqrt{2/(n-2)}$ is smaller than $\delta/2$ by assumption). Lemma 33 is proved. ■

### D.2.4 PROOF OF LEMMA 32.

Given any matrix $B \in \{0, 1\}^{n \times n}_{sym}$, let us show the following inequality $\Phi(B, \mathbf{r}_1) + \Phi(B, \mathbf{r}_2) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$ where $\tilde{\Phi}$ and $\Phi$ are respectively defined by (30) and (28).

For all permutations $\sigma$ of $\{1, \dots, n\}$, the triangle inequality gives

$$ 2|B_{ij}-r_2^2(i,j)|\sqrt{2}|B_{ij}-r_1^2(\sigma(i)\sigma(j))| \ge |B_{ij}-r_2^2(i,j)|+|B_{ij}-r_1^2(\sigma(i)\sigma(j))| \ge |r_2^2(i,j)-r_1^2(\sigma(i)\sigma(j))| $$
Combining the above displays, we obtain the lower bound

$$ \text{Card} \left\{ (i,j) : \begin{array}{l} 16|r_2^2(i,j) - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \\ r_2(i,m(i)) + r_2(j,m(j)) \le 2\delta \\ r_1(\sigma(i),m(\sigma(i))) + r_1(\sigma(j),m(\sigma(j))) \le 2\delta \end{array} \right\} \ge n-3 \quad (32) $$

for all permutations fulfilling $\sigma(n) = n$.

**Case 2:** if $\sigma(n-1) = n$, then $\sigma(n), \sigma(j) \in \{1, \dots, n-1\}$ for all $j \le n-2$. Following the same proof as above, we can show that $|r_2^2(n,j) - r_1^2(\sigma(n), \sigma(j))| \ge 2\delta$ for all $j \le n-2$. Likewise, the bounds on the bias terms are obtained as before. The inequality (32) is therefore proved for all permutations fulfilling $\sigma(n-1) = n$.

**Case 3:** if $\sigma(n) \ne n$ and $\sigma(n-1) \ne n$. Following the same proof as above, we can show that $|r_2^2(n,j) - r_1^2(\sigma(n), \sigma(j))| \ge 2\delta$ for all $j \le n-2$ such that $j \ne \sigma^{-1}(n)$. The inequality (32) is therefore proved for all permutations $\sigma(n) \ne n$ and $\sigma(n-1) \ne n$.

Finally, the lower bound (32) is true for all permutations $\sigma$, in particular for the infimum over all of them. Lemma 30 is proved. ■

### D.2.3 PROOF OF LEMMA 33.

Let us upper bound the bias terms for $\mathbf{r}_1$, in the case of an arbitrary permutation $\sigma$ fulfilling $\sigma(n) = n$. On the event $\mathcal{R}_1$, one has

$$ r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le r_W(C_1, C_4) + r_W(C_1, C_2). $$

for all $j, i \le n-1$ such that $j \ne i$. In Table 1 and Table 2, one observes that

$$ \begin{aligned} r_W(C_1, C_2) &\le \sqrt{2\eta} \\ r_W(C_1, C_4) &\le \sqrt{\delta^2(1 - 2\eta) + (\delta/2)\eta + \delta^2(\eta/2) + (1/4)(\eta/2)}. \end{aligned} $$

The second bound is smaller than $\sqrt{\delta^2(1 - (3\eta/2)) + \eta/4}$ since $(\delta/2)\eta \le (1/4)(\eta/2)$ (using the assumption $\delta \le 1/40$). Hence,

$$ r_1(\sigma(i), m(\sigma(i))) + r_1(\sigma(j), m(\sigma(j))) \le \sqrt{\delta^2 + \eta/4} + \sqrt{2\eta} $$

which is lower than $\delta + 2\sqrt{\eta}$, and again, lower than $2\delta$ (since $\sqrt{\eta} = \sqrt{2/(n-2)}$ is smaller than $\delta/2$ by assumption). Lemma 33 is proved. ■

### D.2.4 PROOF OF LEMMA 32.

Given any matrix $B \in \{0, 1\}^{n \times n}_{sym}$, let us show the following inequality $\Phi(B, \mathbf{r}_1) + \Phi(B, \mathbf{r}_2) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2)$ where $\tilde{\Phi}$ and $\Phi$ are respectively defined by (30) and (28).

For all permutations $\sigma$ of $\{1, \dots, n\}$, the triangle inequality gives

$$ 2|B_{ij}-r_2^2(i,j)|\sqrt{2}|B_{ij}-r_1^2(\sigma(i)\sigma(j))| \ge |B_{ij}-r_2^2(i,j)|+|B_{ij}-r_1^2(\sigma(i)\sigma(j))| \ge |r_2^2(i,j)-r_1^2(\sigma(i)\sigma(j))| $$
so that $\text{Card} \left\{ (i,j) : \begin{array}{l} 16|r_2^2(i,j) - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \\ r_2(i,m(i)) + r_2(j,m(j)) \le 2\delta \\ r_1(\sigma(i),m(\sigma(i))) + r_1(\sigma(j),m(\sigma(j))) \le 2\delta \end{array} \right\}$ lower bounds the sum

of the two cardinal numbers

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij} - r_2^2(i,j)| \ge 2\delta \ge r_2(i,m(i)) + r_2(j,m(j)) \right\} \quad \text{and} $$

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij} - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \ge r_1(\sigma(i),m(\sigma(i))) + r_1(\sigma(j),m(\sigma(j))) \right\}. $$

Taking a permutation that minimizes the latter cardinal, one has

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij} - r_2^2(i,j)| \ge 2\delta \ge r_2(i,m(i)) + r_2(j,m(j)) \right\} + \Phi(B, \mathbf{r}_1) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) $$

by definition of $\Phi$ and $\tilde{\Phi}$. The above inequality holds for any matrix in $\{0,1\}_{sym}^{n \times n}$, in particular for $B^\sigma$ defined by $B_{ij}^\sigma = B_{\sigma(i),\sigma(j)}$ (where $B \in \{0,1\}_{sym}^{n \times n}$ and any permutation $\sigma$). Using $\Phi(B^\sigma, \mathbf{r}_1) = \Phi(B, \mathbf{r}_1)$, the above display becomes

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij}^\sigma - r_2^2(i,j)| \ge 2\delta \ge r_2(i,m(i)) + r_2(j,m(j)) \right\} + \Phi(B, \mathbf{r}_1) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) $$

and thus, choosing the permutation that minimize the left term,

$$ \Phi(B, \mathbf{r}_1) + \Phi(B, \mathbf{r}_2) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2). $$

This generalized triangle inequality holds for all $B \in \{0,1\}_{sym}^{n \times n}$. Lemma 32 is proved. ■

### D.2.5 PROOF OF LEMMA 31.

In the following, we write $\mathbb{P}$ for $\mathbb{P}_{(\Omega, \mu, W)}$, and $\mu^{\otimes n}$ for the product measure, and $\omega$ for the $n$-tuple $(\omega_1, \dots, \omega_n)$. Lemma 31 states that for all $M \in \{0,1\}_{sym}^{n \times n}$,

$$ \mathbb{P}[A = M | \omega \in \mathcal{R}_1] = \mathbb{P}[A = M | \omega \in \mathcal{R}_2] $$

which is equivalent to

$$ p_{\mathcal{R}_1}(M)/\mathbb{P}(\mathcal{R}_1) = p_{\mathcal{R}_2}(M)/\mathbb{P}(\mathcal{R}_2) \qquad (33) $$

where $p_{\mathcal{R}_1}(M)$ denotes

$$ p_{\mathcal{R}_1}(M) := \mathbb{P}(\{A = M\} \cap \mathcal{R}_1) = \int_{\omega \in \mathcal{R}_k} \mathbb{P}(A = M | \omega) d\mu^{\otimes n}(\omega). $$

Hence, we want to prove that

$$ 2p_{\mathcal{R}_1}(M) = p_{\mathcal{R}_2}(M) $$

since $2\mathbb{P}(\mathcal{R}_1) = \mathbb{P}(\mathcal{R}_2)$ by definition of the events $\mathcal{R}_1$ and $\mathcal{R}_2$.
so that $\text{Card} \left\{ (i,j) : \begin{array}{l} 16|r_2^2(i,j) - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \\ r_2(i,m(i)) + r_2(j,m(j)) \le 2\delta \\ r_1(\sigma(i),m(\sigma(i))) + r_1(\sigma(j),m(\sigma(j))) \le 2\delta \end{array} \right\}$ lower bounds the sum

of the two cardinal numbers

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij} - r_2^2(i,j)| \ge 2\delta \ge r_2(i,m(i)) + r_2(j,m(j)) \right\} \quad \text{and} $$

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij} - r_1^2(\sigma(i)\sigma(j))| \ge 2\delta \ge r_1(\sigma(i),m(\sigma(i))) + r_1(\sigma(j),m(\sigma(j))) \right\}. $$

Taking a permutation that minimizes the latter cardinal, one has

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij} - r_2^2(i,j)| \ge 2\delta \ge r_2(i,m(i)) + r_2(j,m(j)) \right\} + \Phi(B, \mathbf{r}_1) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) $$

by definition of $\Phi$ and $\tilde{\Phi}$. The above inequality holds for any matrix in $\{0,1\}_{sym}^{n \times n}$, in particular for $B^\sigma$ defined by $B_{ij}^\sigma = B_{\sigma(i),\sigma(j)}$ (where $B \in \{0,1\}_{sym}^{n \times n}$ and any permutation $\sigma$). Using $\Phi(B^\sigma, \mathbf{r}_1) = \Phi(B, \mathbf{r}_1)$, the above display becomes

$$ \text{Card} \left\{ (i,j) : 32 |B_{ij}^\sigma - r_2^2(i,j)| \ge 2\delta \ge r_2(i,m(i)) + r_2(j,m(j)) \right\} + \Phi(B, \mathbf{r}_1) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2) $$

and thus, choosing the permutation that minimize the left term,

$$ \Phi(B, \mathbf{r}_1) + \Phi(B, \mathbf{r}_2) \ge \tilde{\Phi}(\mathbf{r}_1, \mathbf{r}_2). $$

This generalized triangle inequality holds for all $B \in \{0,1\}_{sym}^{n \times n}$. Lemma 32 is proved. ■

### D.2.5 PROOF OF LEMMA 31.

In the following, we write $\mathbb{P}$ for $\mathbb{P}_{(\Omega, \mu, W)}$, and $\mu^{\otimes n}$ for the product measure, and $\omega$ for the $n$-tuple $(\omega_1, \dots, \omega_n)$. Lemma 31 states that for all $M \in \{0,1\}_{sym}^{n \times n}$,

$$ \mathbb{P}[A = M | \omega \in \mathcal{R}_1] = \mathbb{P}[A = M | \omega \in \mathcal{R}_2] $$

which is equivalent to

$$ p_{\mathcal{R}_1}(M)/\mathbb{P}(\mathcal{R}_1) = p_{\mathcal{R}_2}(M)/\mathbb{P}(\mathcal{R}_2) \qquad (33) $$

where $p_{\mathcal{R}_1}(M)$ denotes

$$ p_{\mathcal{R}_1}(M) := \mathbb{P}(\{A = M\} \cap \mathcal{R}_1) = \int_{\omega \in \mathcal{R}_k} \mathbb{P}(A = M | \omega) d\mu^{\otimes n}(\omega). $$

Hence, we want to prove that

$$ 2p_{\mathcal{R}_1}(M) = p_{\mathcal{R}_2}(M) $$

since $2\mathbb{P}(\mathcal{R}_1) = \mathbb{P}(\mathcal{R}_2)$ by definition of the events $\mathcal{R}_1$ and $\mathcal{R}_2$.
Let $\mathcal{R}_1(k, l)$ be the event defined by $\mathcal{R}_1 \cap \{(\omega_k, \omega_l) \in \mathcal{C}_4 \times \mathcal{C}_5\}$. Thus, the event $\mathcal{R}_1$ is the union $\cup_{1 \le k \ne l \le n} \mathcal{R}_1(k, l)$. For any matrix $M = [M_{ij}]_{i,j \le n}$ in $\{0, 1\}_{\text{sym}}^{n \times n}$,

$$p_{\mathcal{R}_1}(M) = \int_{\omega \in \mathcal{R}_1} \mathbb{P}(A = M | \omega) \, d\mu^{\otimes n}(\omega) = \sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(k, l)} \mathbb{P}(A = M | \omega) \, d\mu^{\otimes n}(\omega).$$

Given a permutation $\sigma$ of $\{1, \dots, n\}$, denote by $M^{\sigma}$ the matrix $M_{ij}^{\sigma} = M_{\sigma(i), \sigma(j)}$ with $i, j \in \{1, \dots, n\}$. Write $\sigma_{kl}$ for a permutation fulfilling $\sigma(n-1) = k$ and $\sigma(n) = l$. Then, the probability $p_{\mathcal{R}_1}(M)$ is equal to

$$\sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(k, l)} \mathbb{P}(A^{\sigma_{kl}} = M^{\sigma_{kl}} | \omega) d\mu^{\otimes n}(\omega) = \sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(n-1, n)} \mathbb{P}(A = M^{\sigma_{kl}} | \omega) d\mu^{\otimes n}(\omega).$$

Conditionally to $\omega$, the entries of $A$ for $i < j$ are independent Bernoulli variables, so that

$$p_{\mathcal{R}_1}(M) = \sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(n-1, n)} \prod_{1 \le i < j \le n} \mathbb{P}(A_{ij} = M_{ij}^{\sigma_{kl}} | \omega_i, \omega_j) d\mu^{\otimes n}(\omega).$$

On the event $\mathcal{R}_1(n-1, n)$, the $\omega_1, \dots, \omega_{n-2}$ are in $\mathcal{C}_1 \cup \mathcal{C}_1$, and $(\omega_{n-1}, \omega_n)$ are in $\mathcal{C}_4 \times \mathcal{C}_5$. As the function $W_n$ of the SBM is equal to $1/2$ on the diagonal blocks $\{\mathcal{C}_1, \mathcal{C}_2\}^2$ and $\{\mathcal{C}_3, \mathcal{C}_4, \mathcal{C}_5\}^2$, one has $\mathbb{P}(A_{ij} = M_{ij}^{\sigma_{kl}} | \omega_i, \omega_j) = \frac{1}{2}$ for all $(i, j)$ in the set $\{(i, j) : i < j \le n-2\} \cup \{(n-1, n)\}$ of cardinality $g_n = n(n-1)/2 - 2(n-2)$. Hence, the probability $p_{\mathcal{R}_1}(M)$ is equal to

$$\sum_{1 \le k \ne l \le n} \left(\frac{1}{2}\right)^{g_n} \int_{\omega \in \mathcal{R}_1(n-1, n)} \prod_{1 \le i \le n-2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu^{\otimes n}(\omega)$$

or equivalently to

$$\sum_{1 \le k \ne l \le n} \left(\frac{1}{2}\right)^{g_n} \int_{(\omega_{n-1}, \omega_n) \in \mathcal{C}_4 \times \mathcal{C}_5} X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) d\mu^{\otimes 2}(\omega_{n-1}, \omega_n)$$

with

$$X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) := \prod_{1 \le i \le n-2} \int_{\omega_i \in \mathcal{C}_1 \cup \mathcal{C}_2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i).$$

Likewise, $\mathcal{R}_2$ is the union $\cup_{1 \le k < l \le n} \mathcal{R}_2(k, l)$ where each $\mathcal{R}_2(k, l)$ is the event $\mathcal{R}_2 \cap \{\omega_k, \omega_l \in \mathcal{C}_3\}$. Following the same proof as for $\mathcal{R}_1$, one can show that

$$p_{\mathcal{R}_2}(M) = \sum_{1 \le k < l \le n} \left(\frac{1}{2}\right)^{g_n} \int_{(\omega_{n-1}, \omega_n) \in \mathcal{C}_3 \times \mathcal{C}_3} X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) d\mu^{\otimes 2}(\omega_{n-1}, \omega_n).$$

**Lemma 34** There exists a constant $X_{M^{\sigma_{kl}}}$ such that $X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) = X_{M^{\sigma_{kl}}}$ whether $\mathcal{R}_1(n-1, n)$ or $\mathcal{R}_2(n-1, n)$ holds.
Let $\mathcal{R}_1(k, l)$ be the event defined by $\mathcal{R}_1 \cap \{(\omega_k, \omega_l) \in \mathcal{C}_4 \times \mathcal{C}_5\}$. Thus, the event $\mathcal{R}_1$ is the union $\cup_{1 \le k \ne l \le n} \mathcal{R}_1(k, l)$. For any matrix $M = [M_{ij}]_{i,j \le n}$ in $\{0, 1\}_{\text{sym}}^{n \times n}$,

$$p_{\mathcal{R}_1}(M) = \int_{\omega \in \mathcal{R}_1} \mathbb{P}(A = M | \omega) \, d\mu^{\otimes n}(\omega) = \sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(k, l)} \mathbb{P}(A = M | \omega) \, d\mu^{\otimes n}(\omega).$$

Given a permutation $\sigma$ of $\{1, \dots, n\}$, denote by $M^{\sigma}$ the matrix $M_{ij}^{\sigma} = M_{\sigma(i), \sigma(j)}$ with $i, j \in \{1, \dots, n\}$. Write $\sigma_{kl}$ for a permutation fulfilling $\sigma(n-1) = k$ and $\sigma(n) = l$. Then, the probability $p_{\mathcal{R}_1}(M)$ is equal to

$$\sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(k, l)} \mathbb{P}(A^{\sigma_{kl}} = M^{\sigma_{kl}} | \omega) d\mu^{\otimes n}(\omega) = \sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(n-1, n)} \mathbb{P}(A = M^{\sigma_{kl}} | \omega) d\mu^{\otimes n}(\omega).$$

Conditionally to $\omega$, the entries of $A$ for $i < j$ are independent Bernoulli variables, so that

$$p_{\mathcal{R}_1}(M) = \sum_{1 \le k \ne l \le n} \int_{\omega \in \mathcal{R}_1(n-1, n)} \prod_{1 \le i < j \le n} \mathbb{P}(A_{ij} = M_{ij}^{\sigma_{kl}} | \omega_i, \omega_j) d\mu^{\otimes n}(\omega).$$

On the event $\mathcal{R}_1(n-1, n)$, the $\omega_1, \dots, \omega_{n-2}$ are in $\mathcal{C}_1 \cup \mathcal{C}_1$, and $(\omega_{n-1}, \omega_n)$ are in $\mathcal{C}_4 \times \mathcal{C}_5$. As the function $W_n$ of the SBM is equal to $1/2$ on the diagonal blocks $\{\mathcal{C}_1, \mathcal{C}_2\}^2$ and $\{\mathcal{C}_3, \mathcal{C}_4, \mathcal{C}_5\}^2$, one has $\mathbb{P}(A_{ij} = M_{ij}^{\sigma_{kl}} | \omega_i, \omega_j) = \frac{1}{2}$ for all $(i, j)$ in the set $\{(i, j) : i < j \le n-2\} \cup \{(n-1, n)\}$ of cardinality $g_n = n(n-1)/2 - 2(n-2)$. Hence, the probability $p_{\mathcal{R}_1}(M)$ is equal to

$$\sum_{1 \le k \ne l \le n} \left(\frac{1}{2}\right)^{g_n} \int_{\omega \in \mathcal{R}_1(n-1, n)} \prod_{1 \le i \le n-2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu^{\otimes n}(\omega)$$

or equivalently to

$$\sum_{1 \le k \ne l \le n} \left(\frac{1}{2}\right)^{g_n} \int_{(\omega_{n-1}, \omega_n) \in \mathcal{C}_4 \times \mathcal{C}_5} X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) d\mu^{\otimes 2}(\omega_{n-1}, \omega_n)$$

with

$$X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) := \prod_{1 \le i \le n-2} \int_{\omega_i \in \mathcal{C}_1 \cup \mathcal{C}_2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i).$$

Likewise, $\mathcal{R}_2$ is the union $\cup_{1 \le k < l \le n} \mathcal{R}_2(k, l)$ where each $\mathcal{R}_2(k, l)$ is the event $\mathcal{R}_2 \cap \{\omega_k, \omega_l \in \mathcal{C}_3\}$. Following the same proof as for $\mathcal{R}_1$, one can show that

$$p_{\mathcal{R}_2}(M) = \sum_{1 \le k < l \le n} \left(\frac{1}{2}\right)^{g_n} \int_{(\omega_{n-1}, \omega_n) \in \mathcal{C}_3 \times \mathcal{C}_3} X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) d\mu^{\otimes 2}(\omega_{n-1}, \omega_n).$$

**Lemma 34** There exists a constant $X_{M^{\sigma_{kl}}}$ such that $X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n) = X_{M^{\sigma_{kl}}}$ whether $\mathcal{R}_1(n-1, n)$ or $\mathcal{R}_2(n-1, n)$ holds.
Using Lemma 34, one has

$$p_{\mathcal{R}_1}(M) = \left(\frac{1}{2}\right)^{g_n} \sum_{1 \le k \ne l \le n} X_{M^{\sigma_{kl}}} \mu(C_4) \mu(C_5)$$

and

$$p_{\mathcal{R}_2}(M) = \left(\frac{1}{2}\right)^{g_n} \sum_{1 \le k < l \le n} X_{M^{\sigma_{kl}}} \mu(C_3)^2$$

so that $p_{\mathcal{R}_1}(M) = p_{\mathcal{R}_2}(M)/2$, since $\mu(C_4) = \mu(C_5) = \mu(C_3)/2$ (by construction of the SBM). Lemma 31 is proved. ■

### D.2.6 PROOF OF LEMMA 34.

For brevity, write $\mathbb{P}$ for $\mathbb{P}_{(\Omega, \mu, W)}$ in the following. By definition, $X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n)$ is the product of the $n-2$ following terms

$$\int_{\omega_i \in C_1 \cup C_2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i)$$

$i = 1, \dots, n-2$. The above display is equal to

$$\int_{\omega_i \in C_1} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i) + \int_{\omega_i \in C_2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i).$$

If $(\omega_{n-1}, \omega_n) \in C_4 \times C_5$, then

$$= \int_{\omega_i \in C_1} [1/2 + (2M_{i,n-1}^{\sigma_{kl}} - 1) \delta] [1/2 + (2M_{i,n}^{\sigma_{kl}} - 1)(1/2)] d\mu(\omega_i) + \int_{\omega_i \in C_2} [1/2 - (2M_{i,n-1}^{\sigma_{kl}} - 1) \delta] [1/2 - (2M_{i,n}^{\sigma_{kl}} - 1)(1/2)] d\mu(\omega_i)$$

which is equal to $[1/2 + (2M_{i,n-1}^{\sigma_{kl}} - 1)(2M_{i,n}^{\sigma_{kl}} - 1)\delta] \mu(C_1)$, since $\mu(C_1) = \mu(C_2)$. If $(\omega_{n-1}, \omega_n) \in C_3 \times C_3$, then

$$= \int_{\omega_i \in C_1} [1/2 + (2M_{i,n-1}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] [1/2 + (2M_{i,n}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] d\mu(\omega_i) + \int_{\omega_i \in C_2} [1/2 - (2M_{i,n-1}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] [1/2 - (2M_{i,n}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] d\mu(\omega_i)$$

which is equal to $[1/2 + (2M_{i,n-1}^{kl} - 1)(2M_{i,n}^{\sigma_{kl}} - 1)\delta] \mu(C_1)$.

Hence $X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n)$ is equal to the same constant whether $(\omega_{n-1}, \omega_n)$ belongs to $C_3 \times C_3$ or $C_4 \times C_5$. Lemma 34 is proved. ■
Using Lemma 34, one has

$$p_{\mathcal{R}_1}(M) = \left(\frac{1}{2}\right)^{g_n} \sum_{1 \le k \ne l \le n} X_{M^{\sigma_{kl}}} \mu(C_4) \mu(C_5)$$

and

$$p_{\mathcal{R}_2}(M) = \left(\frac{1}{2}\right)^{g_n} \sum_{1 \le k < l \le n} X_{M^{\sigma_{kl}}} \mu(C_3)^2$$

so that $p_{\mathcal{R}_1}(M) = p_{\mathcal{R}_2}(M)/2$, since $\mu(C_4) = \mu(C_5) = \mu(C_3)/2$ (by construction of the SBM). Lemma 31 is proved. ■

### D.2.6 PROOF OF LEMMA 34.

For brevity, write $\mathbb{P}$ for $\mathbb{P}_{(\Omega, \mu, W)}$ in the following. By definition, $X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n)$ is the product of the $n-2$ following terms

$$\int_{\omega_i \in C_1 \cup C_2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i)$$

$i = 1, \dots, n-2$. The above display is equal to

$$\int_{\omega_i \in C_1} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i) \\ + \int_{\omega_i \in C_2} \mathbb{P}(A_{i,n-1} = M_{i,n-1}^{\sigma_{kl}} | \omega_i, \omega_{n-1}) \mathbb{P}(A_{i,n} = M_{i,n}^{\sigma_{kl}} | \omega_i, \omega_n) d\mu(\omega_i).$$

If $(\omega_{n-1}, \omega_n) \in C_4 \times C_5$, then

$$= \int_{\omega_i \in C_1} [1/2 + (2M_{i,n-1}^{\sigma_{kl}} - 1) \delta] [1/2 + (2M_{i,n}^{\sigma_{kl}} - 1)(1/2)] d\mu(\omega_i) \\ + \int_{\omega_i \in C_2} [1/2 - (2M_{i,n-1}^{\sigma_{kl}} - 1) \delta] [1/2 - (2M_{i,n}^{\sigma_{kl}} - 1)(1/2)] d\mu(\omega_i)$$

which is equal to $[1/2 + (2M_{i,n-1}^{\sigma_{kl}} - 1)(2M_{i,n}^{\sigma_{kl}} - 1)\delta] \mu(C_1)$, since $\mu(C_1) = \mu(C_2)$. If $(\omega_{n-1}, \omega_n) \in C_3 \times C_3$, then

$$= \int_{\omega_i \in C_1} [1/2 + (2M_{i,n-1}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] [1/2 + (2M_{i,n}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] d\mu(\omega_i) \\ + \int_{\omega_i \in C_2} [1/2 - (2M_{i,n-1}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] [1/2 - (2M_{i,n}^{\sigma_{kl}} - 1) \sqrt{\delta/2}] d\mu(\omega_i)$$

which is equal to $[1/2 + (2M_{i,n-1}^{kl} - 1)(2M_{i,n}^{\sigma_{kl}} - 1)\delta] \mu(C_1)$.

Hence $X_{M^{\sigma_{kl}}}(\omega_{n-1}, \omega_n)$ is equal to the same constant whether $(\omega_{n-1}, \omega_n)$ belongs to $C_3 \times C_3$ or $C_4 \times C_5$. Lemma 34 is proved. ■
# Appendix E. Estimation of the Minkowski Dimension

## E.1 Proof of Theorem 12: the Upper Bound

Theorem 12 is a corollary of Theorem 35, which gives non-asymptotic high-probability bounds for the risk of the data-function $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$.

**Theorem 35** Assume the graphon $(\Omega, \mu, W)$ satisfies $H_1^{\alpha, v}$ and $H_2^{m, M, v}$ and has a Minkowski dimension $d \in (0, \infty)$. If $n$ is large enough to satisfy the below inequality

$$2\log n/n \le \alpha (v/14)^{2d} \wedge (v/14)^4,$$

then the following holds with probability at least $1 - (2 + 4\alpha M)/n$ with respect to the distribution $P_{(\Omega, \mu, W)}$. The sum of the distance error bound (14) and the sampling error (13) is upper bounded as follows

$$\frac{b_{sup} + s_{\omega}}{6} \le err_{n,d} := \left(\frac{\log n}{n}\right)^{1/4} + \left(\frac{2 \log n}{\alpha n}\right)^{1/2d}. \quad (34)$$

For all $\epsilon \in (2(b_{sup} + s_{\omega}), v/7]$, the covering number estimator $\hat{N}_{\Omega}^{(c)}(\epsilon)$ satisfies the following upper bound

$$\left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \right| \le \frac{1}{-\log \epsilon} \left[ \log \left( M \vee \frac{1}{m} \right) + 6d \frac{err_{n,d}}{\epsilon} \left( 1 + \frac{err_{n,d}}{\epsilon} \right) \right]$$

Theorem 12 follows from Theorem 35 by choosing any radius $\epsilon$ that minimizes the above upper bound, that is, any radius $\epsilon_D$ of the order of $\sup_{\{d: d \le D\}} err_{n,d} = err_{n,D}$. ■

**COMMENTS ON THEOREM 35**: We first remark that the above theorem based on the covering number can also be adapted to the packing number (without difficulties). We now comment on the two additive error terms in the upper bound. The term $-\log (M \vee (1/m))/\log \epsilon$ stands for the gap between the Minkowski dimension and the quantity that we actually estimate, i.e. $-\log N_{\Omega}^{(c)}(\epsilon)/\log \epsilon$. This gap depends on the parameters of the assumption $H_2^{m, M, v}$. The second error term $-derr_{n,d}/(\epsilon \log \epsilon)$ represents the gap between the latter estimated quantity and the estimator $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$. To control this gap, we need to estimate the covering number correctly, and thus to control the error sum $b_{sup} + s_{\omega}$ involved in Proposition 11. Actually, the theorem ensures that this error sum is smaller than $err_{n,d}$. This comes from the fact that the difference between the sample $\omega_1, \dots, \omega_n$ and the latent space $\Omega$ is not too large, thanks to the assumption $H_1^{\alpha, v}$. See the proof below for details.

Finally, the upper bound holds with probability at least $1 - 2/n - 4\alpha M/n$. The first quantity $2/n$ corresponds to the event $\mathcal{E}_{dist}^c$ defined in Theorem 7, i.e. that the distance estimator does not satisfy the distance error bound $b_{sup}$. The second quantity $4\alpha M/n$ corresponds to the probability of the event where the sampled points do not cover well the latent space, leading to a large sampling error $s_{\omega}$ and a large distance error bound $b_{sup}$. This event, denoted by $\mathcal{E}_{bad}$, is rigorously defined in the following proof.
# Appendix E. Estimation of the Minkowski Dimension

## E.1 Proof of Theorem 12: the Upper Bound

Theorem 12 is a corollary of Theorem 35, which gives non-asymptotic high-probability bounds for the risk of the data-function $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$.

**Theorem 35** Assume the graphon $(\Omega, \mu, W)$ satisfies $H_1^{\alpha, v}$ and $H_2^{m, M, v}$ and has a Minkowski dimension $d \in (0, \infty)$. If $n$ is large enough to satisfy the below inequality

$$2\log n/n \le \alpha (v/14)^{2d} \wedge (v/14)^4,$$

then the following holds with probability at least $1 - (2 + 4\alpha M)/n$ with respect to the distribution $P_{(\Omega, \mu, W)}$. The sum of the distance error bound (14) and the sampling error (13) is upper bounded as follows

$$\frac{b_{sup} + s_{\omega}}{6} \le err_{n,d} := \left(\frac{\log n}{n}\right)^{1/4} + \left(\frac{2\log n}{\alpha n}\right)^{1/2d}. \quad (34)$$

For all $\epsilon \in (2(b_{sup} + s_{\omega}), v/7]$, the covering number estimator $\hat{N}_{\Omega}^{(c)}(\epsilon)$ satisfies the following upper bound

$$\left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \right| \le \frac{1}{-\log \epsilon} \left[ \log \left( M \vee \frac{1}{m} \right) + 6d \frac{err_{n,d}}{\epsilon} \left( 1 + \frac{err_{n,d}}{\epsilon} \right) \right]$$

Theorem 12 follows from Theorem 35 by choosing any radius $\epsilon$ that minimizes the above upper bound, that is, any radius $\epsilon_D$ of the order of $\sup_{\{d: d \le D\}} err_{n,d} = err_{n,D}$. ■

**COMMENTS ON THEOREM 35:** We first remark that the above theorem based on the covering number can also be adapted to the packing number (without difficulties). We now comment on the two additive error terms in the upper bound. The term $-\log (M \vee (1/m))/\log \epsilon$ stands for the gap between the Minkowski dimension and the quantity that we actually estimate, i.e. $-\log N_{\Omega}^{(c)}(\epsilon)/\log \epsilon$. This gap depends on the parameters of the assumption $H_2^{m, M, v}$. The second error term $-d err_{n,d}/(\epsilon \log \epsilon)$ represents the gap between the latter estimated quantity and the estimator $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$. To control this gap, we need to estimate the covering number correctly, and thus to control the error sum $b_{sup} + s_{\omega}$ involved in Proposition 11. Actually, the theorem ensures that this error sum is smaller than $err_{n,d}$. This comes from the fact that the difference between the sample $\omega_1, \dots, \omega_n$ and the latent space $\Omega$ is not too large, thanks to the assumption $H_1^{\alpha, v}$. See the proof below for details.

Finally, the upper bound holds with probability at least $1 - 2/n - 4\alpha M/n$. The first quantity $2/n$ corresponds to the event $\mathcal{E}_{dist}^c$ defined in Theorem 7, i.e. that the distance estimator does not satisfy the distance error bound $b_{sup}$. The second quantity $4\alpha M/n$ corresponds to the probability of the event where the sampled points do not cover well the latent space, leading to a large sampling error $s_{\omega}$ and a large distance error bound $b_{sup}$. This event, denoted by $\mathcal{E}_{bad}$, is rigorously defined in the following proof.
Proof of Theorem 35. Assume the event $\mathcal{E}_{dist}$ of Theorem 7 holds, that is the errors of distance-estimator are uniformly bounded by $b_{sup}$. On this event, Proposition 11 gives

$$N_{\Omega}^{(c)}(\epsilon + b_{sup} + s_{\omega}) \leq \hat{N}_{\Omega}^{(c)}(\epsilon) \leq N_{\Omega}^{(c)}(\epsilon - b_{sup} - s_{\omega})$$

for all $\epsilon \in (b_{sup} + s_{\omega}, 1)$, so that

$$\frac{\log N_{\Omega}^{(c)}(\epsilon + s_{\omega} + b_{sup})}{-\log \epsilon} - d \leq \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \leq \frac{\log N_{\Omega}^{(c)}(\epsilon - s_{\omega} - b_{sup})}{-\log \epsilon} - d.$$

As the assumption $H_2^{m,M,v}$ is valid in the neighborhood $(0, v]$, we need to check that $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ to use this assumption. For clarity, we do this verification at the end of the proof. Hence, using $H_2^{m,M,v}$, one has

$$\frac{\log m}{-\log \epsilon} - d \left[ \frac{\log(\epsilon + s_{\omega} + b_{sup})}{-\log \epsilon} + 1 \right] \leq \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \leq \frac{\log M}{-\log \epsilon} - d \left[ \frac{\log(\epsilon - s_{\omega} - b_{sup})}{-\log \epsilon} + 1 \right] \quad (35)$$

In the right hand side of (35), the right term is upper bounded by

$$-d \left[ \frac{\log(\epsilon - s_{\omega} - b_{sup})}{-\log \epsilon} + 1 \right] \leq -d \frac{\log(1 - (s_{\omega} + b_{sup})/\epsilon)}{-\log \epsilon}$$

which is again upper bounded by

$$d \frac{(s_{\omega} + b_{sup})/\epsilon + ((s_{\omega} + b_{sup})/\epsilon)^2}{-\log \epsilon}$$

if $(s_{\omega} + b_{sup}) \leq \epsilon/2$. Similarly in the left hand side of (35), the right term is lower bounded by

$$-d \left[ \frac{\log(\epsilon + s_{\omega} + b_{sup})}{-\log \epsilon} + 1 \right] \geq -d \frac{(s_{\omega} + b_{sup})/\epsilon}{-\log \epsilon}.$$

Combining the above displays, one derive

$$\frac{\log m}{-\log \epsilon} - d \frac{(s_{\omega} + b_{sup})/\epsilon}{-\log \epsilon} \leq \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \leq \frac{\log M}{-\log \epsilon} + d \frac{(s_{\omega} + b_{sup})/\epsilon + ((s_{\omega} + b_{sup})/\epsilon)^2}{-\log \epsilon} \quad (36)$$

It remains to upper bound the error sum $s_{\omega} + b_{sup}$ in (36). Given a cover of $\Omega$, composed of $N_{\Omega}^{(c)}(\eta)$ balls $B_j$ of radius $\eta$, one define the following event

$$\mathcal{E}_{bad}(\eta) := \{ \exists j : B_j \text{ contains exactly 0 or 1 sampled point among } \omega_1, \dots, \omega_n \}. \quad (37)$$

Assume the complementary event $\mathcal{E}_{bad}^c(\eta)$ holds. This means that each ball of the cover of $\Omega$ contains at least two sampled points. Hence, one has

$$\begin{cases} s_{\omega} \leq 2\eta, \\ \sup_{i \in \{1, \dots, n\}} r_W(\omega_i, \omega_{m(i)}) \leq 2\eta. \end{cases}$$
Proof of Theorem 35. Assume the event $\mathcal{E}_{dist}$ of Theorem 7 holds, that is the errors of distance-estimator are uniformly bounded by $b_{sup}$. On this event, Proposition 11 gives

$$N_{\Omega}^{(c)}(\epsilon + b_{sup} + s_{\omega}) \leq \hat{N}_{\Omega}^{(c)}(\epsilon) \leq N_{\Omega}^{(c)}(\epsilon - b_{sup} - s_{\omega})$$

for all $\epsilon \in (b_{sup} + s_{\omega}, 1)$, so that

$$\frac{\log N_{\Omega}^{(c)}(\epsilon + s_{\omega} + b_{sup})}{-\log \epsilon} - d \leq \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \leq \frac{\log N_{\Omega}^{(c)}(\epsilon - s_{\omega} - b_{sup})}{-\log \epsilon} - d.$$

As the assumption $H_2^{m,M,v}$ is valid in the neighborhood $(0, v]$, we need to check that $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ to use this assumption. For clarity, we do this verification at the end of the proof. Hence, using $H_2^{m,M,v}$, one has

$$\frac{\log m}{-\log \epsilon} - d \left[ \frac{\log(\epsilon + s_{\omega} + b_{sup})}{-\log \epsilon} + 1 \right] \leq \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \leq \frac{\log M}{-\log \epsilon} - d \left[ \frac{\log(\epsilon - s_{\omega} - b_{sup})}{-\log \epsilon} + 1 \right] \quad (35)$$

In the right hand side of (35), the right term is upper bounded by

$$-d \left[ \frac{\log(\epsilon - s_{\omega} - b_{sup})}{-\log \epsilon} + 1 \right] \leq -d \frac{\log(1 - (s_{\omega} + b_{sup})/\epsilon)}{-\log \epsilon}$$

which is again upper bounded by

$$d \frac{(s_{\omega} + b_{sup})/\epsilon + ((s_{\omega} + b_{sup})/\epsilon)^2}{-\log \epsilon}$$

if $(s_{\omega} + b_{sup}) \leq \epsilon/2$. Similarly in the left hand side of (35), the right term is lower bounded by

$$-d \left[ \frac{\log(\epsilon + s_{\omega} + b_{sup})}{-\log \epsilon} + 1 \right] \geq -d \frac{(s_{\omega} + b_{sup})/\epsilon}{-\log \epsilon}.$$

Combining the above displays, one derive

$$\frac{\log m}{-\log \epsilon} - d \frac{(s_{\omega} + b_{sup})/\epsilon}{-\log \epsilon} \leq \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \leq \frac{\log M}{-\log \epsilon} + d \frac{(s_{\omega} + b_{sup})/\epsilon + ((s_{\omega} + b_{sup})/\epsilon)^2}{-\log \epsilon} \quad (36)$$

It remains to upper bound the error sum $s_{\omega} + b_{sup}$ in (36). Given a cover of $\Omega$, composed of $N_{\Omega}^{(c)}(\eta)$ balls $B_j$ of radius $\eta$, one define the following event

$$\mathcal{E}_{bad}(\eta) := \{ \exists j : B_j \text{ contains exactly } 0 \text{ or } 1 \text{ sampled point among } \omega_1, \dots, \omega_n \}. \quad (37)$$

Assume the complementary event $\mathcal{E}_{bad}^c(\eta)$ holds. This means that each ball of the cover of $\Omega$ contains at least two sampled points. Hence, one has

$$\begin{cases} s_{\omega} \leq 2\eta, \\ \sup_{i \in \{1, \dots, n\}} r_W(\omega_i, \omega_{m(i)}) \leq 2\eta. \end{cases}$$
which directly implies the following upper bound

$$b_{sup} + s_{\omega} \leq 6 \left( \frac{\log n}{n} \right)^{1/4} + 4\sqrt{\eta} + 2\eta$$

by definition of $b_{sup}$ in (14). Thus, for the particular radius $\eta_n := [2 \log(n)/(\alpha n)]^{1/d}$,

$$b_{sup} + s_{\omega} \leq 6 \left( \frac{\log n}{n} \right)^{1/4} + 6 \left( \frac{2 \log n}{\alpha n} \right)^{1/2d}.$$

It follows from the definition (34) of $err_{n,d}$ that

$$s_{\omega} + b_{sup} \leq 6err_{n,d}.$$

Combining the above upper bound with (36), one deduce the inequalities of the theorem.

The above displays hold conditionally to the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$, which happens with probability at least $1 - (2 + 4\alpha M)/n$ (Lemma 36).

**Lemma 36** The probability $\mathbb{P}_{(\Omega, \mu, W)}(\mathcal{E}_{bad}(\eta_n) \cup \mathcal{E}_{dist}^c)$ is smaller than $(2 + 4\alpha M)/n$.

The condition $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ (used at the beginning of the proof) is satisfied (Lemma 37).

**Lemma 37** On the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$, one has $\epsilon + s_{\omega} + b_{sup} \in (0, v]$.

Theorem 35 is proved.

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

### E.1.1 PROOF OF LEMMA 37.

We want to prove that $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ on the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$. We have already seen that $s_{\omega} + b_{sup} \leq 6err_{n,d}$ on this event, so it is enough to prove that $\epsilon + 6err_{n,d} \leq v$. By assumption in Theorem 35, one has

$$2 \frac{\log n}{n} \leq \alpha \left(\frac{v}{14}\right)^{2d} \wedge \left(\frac{v}{14}\right)^4,$$

which implies

$$\left(\frac{2 \log n}{\alpha n}\right)^{1/2d} \leq v/14 \quad \text{and} \quad \left(\frac{\log n}{n}\right)^{1/4} \leq v/14,$$

and thus

$$err_{n,d} \leq v/7.$$

Finally, one has $\epsilon + 6err_{n,d} \leq v$, since $\epsilon \leq v/7$ by assumption. Hence, $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ on the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$. The lemma is proved.

<figure><img src="image_8.png" /></figure>
which directly implies the following upper bound

$$b_{sup} + s_{\omega} \leq 6 \left( \frac{\log n}{n} \right)^{1/4} + 4\sqrt{\eta} + 2\eta$$

by definition of $b_{sup}$ in (14). Thus, for the particular radius $\eta_n := [2 \log(n)/(\alpha n)]^{1/d}$,

$$b_{sup} + s_{\omega} \leq 6 \left( \frac{\log n}{n} \right)^{1/4} + 6 \left( \frac{2 \log n}{\alpha n} \right)^{1/2d}.$$

It follows from the definition (34) of $err_{n,d}$ that

$$s_{\omega} + b_{sup} \leq 6err_{n,d}.$$

Combining the above upper bound with (36), one deduce the inequalities of the theorem.

The above displays hold conditionally to the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$, which happens with probability at least $1 - (2 + 4\alpha M)/n$ (Lemma 36).

**Lemma 36** The probability $\mathbb{P}_{(\Omega, \mu, W)}(\mathcal{E}_{bad}(\eta_n) \cup \mathcal{E}_{dist}^c)$ is smaller than $(2 + 4\alpha M)/n$.

The condition $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ (used at the beginning of the proof) is satisfied (Lemma 37).

**Lemma 37** On the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$, one has $\epsilon + s_{\omega} + b_{sup} \in (0, v]$.

Theorem 35 is proved.

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

### E.1.1 PROOF OF LEMMA 37.

We want to prove that $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ on the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$. We have already seen that $s_{\omega} + b_{sup} \leq 6err_{n,d}$ on this event, so it is enough to prove that $\epsilon + 6err_{n,d} \leq v$. By assumption in Theorem 35, one has

$$2 \frac{\log n}{n} \leq \alpha \left(\frac{v}{14}\right)^{2d} \wedge \left(\frac{v}{14}\right)^4,$$

which implies

$$\left(\frac{2 \log n}{\alpha n}\right)^{1/2d} \leq v/14 \quad \text{and} \quad \left(\frac{\log n}{n}\right)^{1/4} \leq v/14,$$

and thus

$$err_{n,d} \leq v/7.$$

Finally, one has $\epsilon + 6err_{n,d} \leq v$, since $\epsilon \leq v/7$ by assumption. Hence, $\epsilon + s_{\omega} + b_{sup} \in (0, v]$ on the event $\mathcal{E}_{bad}^c(\eta_n) \cap \mathcal{E}_{dist}$. The lemma is proved.

<figure><img src="image_9.png" /></figure>
### E.1.2 PROOF OF LEMMA 36.

Let us upper bound the probability $P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n) \cup \mathcal{E}_{dist}^c)$. The union bound gives

$$P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n) \cup \mathcal{E}_{dist}^c) \leq P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n)) + P_{(\Omega,\mu,W)}(\mathcal{E}_{dist}^c) \leq P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n)) + \frac{2}{n}$$

where the last inequality comes from Theorem 7. If the cover defined by $\mathcal{E}_{bad}(\eta_n)$ satisfies the condition (39), then Lemma 38 ensures that

$$P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n)) \leq 2N_{\Omega}^{(c)}(\eta_n)n\beta\exp[-\beta(n-1)]. \quad (38)$$

**Lemma 38** Let $B_1, \dots, B_N$ be $N$ balls in $(\Omega, r_W)$ of measure (strictly) larger than $1/n$, that is,

$$\min_{j \leq N} \mu(B_j) \geq \beta > 1/n \quad (39)$$

for some real $\beta$. Then the probability that (at least) one ball contains exactly zero or one sampled point is smaller than

$$2Nn\beta\exp[-\beta(n-1)].$$

Assume that $\eta_n \in (0, v]$ to use the assumption $H_1^{\alpha,v}$. Then, one obtain the following lower bound for the cover defined by $\mathcal{E}_{bad}(\eta_n)$,

$$\mu(B_j) \geq \alpha \eta_n^d = 2 \log(n)/n$$

so that assumption (39) is satisfied. Applying Lemma 38 for $\beta = \alpha \eta_n^d$, one has

$$P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n)) \leq 2N_{\Omega}^{(c)}(\eta)n\alpha \eta^d \exp[-\alpha \eta^d(n-1)].$$

Combining with the inequality $N_{\Omega}^{(c)}(\eta) \leq M\eta^{-d}$ from assumption $H_2^{m,M,v}$, one derive

$$P_{(\Omega,\mu,W)}(\mathcal{E}_{bad}(\eta_n)) \leq 2Mn\alpha \exp[-\alpha \eta^d(n-1)]$$

and since $\alpha \eta_n^d = 2 \log(n)/n$, one obtain the upper bound

$$2Mn\alpha \exp[-\frac{2\log n}{n}(n-1)].$$

The above display is finally smaller than

$$4Mn\alpha\exp[-2\log n] \leq (4M\alpha)/n.$$

To conclude the proof, it remains to check the condition $\eta_n \in (0, v]$ that we assume earlier. The following assumption of Theorem 35

$$2\frac{\log n}{n} \leq \alpha \left(\frac{v}{14}\right)^{2d} \wedge \left(\frac{v}{14}\right)^4$$

ensures that the radius $\eta_n = [2\log(n)/(\alpha n)]^{1/d}$ satisfies the condition $\eta_n \in (0, v]$. Lemma 36 is proved. ■
### E.1.2 PROOF OF LEMMA 36.

Let us upper bound the probability $P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n) \cup \mathcal{E}_{\text{dist}}^c)$. The union bound gives

$$P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n) \cup \mathcal{E}_{\text{dist}}^c) \leq P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n)) + P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{dist}}^c) \leq P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n)) + \frac{2}{n}$$

where the last inequality comes from Theorem 7. If the cover defined by $\mathcal{E}_{\text{bad}}(\eta_n)$ satisfies the condition (39), then Lemma 38 ensures that

$$P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n)) \leq 2N_{\Omega}^{(c)}(\eta_n)n\beta\exp[-\beta(n-1)]. \quad (38)$$

**Lemma 38** Let $B_1, \dots, B_N$ be $N$ balls in $(\Omega, r_W)$ of measure (strictly) larger than $1/n$, that is,

$$\min_{j \leq N} \mu(B_j) \geq \beta > 1/n \quad (39)$$

for some real $\beta$. Then the probability that (at least) one ball contains exactly zero or one sampled point is smaller than

$$2Nn\beta\exp[-\beta(n-1)].$$

Assume that $\eta_n \in (0, v]$ to use the assumption $H_1^{\alpha, v}$. Then, one obtain the following lower bound for the cover defined by $\mathcal{E}_{\text{bad}}(\eta_n)$,

$$\mu(B_j) \geq \alpha \eta_n^d = 2 \log(n)/n$$

so that assumption (39) is satisfied. Applying Lemma 38 for $\beta = \alpha \eta_n^d$, one has

$$P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n)) \leq 2N_{\Omega}^{(c)}(\eta)n\alpha \eta^d \exp[-\alpha \eta^d(n-1)].$$

Combining with the inequality $N_{\Omega}^{(c)}(\eta) \leq M\eta^{-d}$ from assumption $H_2^{m, M, v}$, one derive

$$P_{(\Omega, \mu, W)}(\mathcal{E}_{\text{bad}}(\eta_n)) \leq 2Mn\alpha \exp[-\alpha \eta^d(n-1)]$$

and since $\alpha \eta_n^d = 2 \log(n)/n$, one obtain the upper bound

$$2Mn\alpha \exp[-\frac{2\log n}{n}(n-1)].$$

The above display is finally smaller than

$$4Mn\alpha\exp[-2\log n] \leq (4M\alpha)/n.$$

To conclude the proof, it remains to check the condition $\eta_n \in (0, v]$ that we assume earlier. The following assumption of Theorem 35

$$2 \frac{\log n}{n} \leq \alpha \left(\frac{v}{14}\right)^{2d} \wedge \left(\frac{v}{14}\right)^4$$

ensures that the radius $\eta_n = [2 \log(n)/(\alpha n)]^{1/d}$ satisfies the condition $\eta_n \in (0, v]$. Lemma 36 is proved. ■
### E.1.3 PROOF OF LEMMA 38.

Given $N$ balls $B_1, \dots, B_N$, let us upper bound the probability that (at least) one of the balls contains exactly zero or one sampled point $\omega_i$. With the union bound, this probability is lower than

$$ \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains exactly } 0 \text{ or } 1 \text{ sampled point among } \omega_1, \dots, \omega_n\} $$

which is again upper bounded with the union bound by

$$ \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains exactly } 0 \text{ point}\} + \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains exactly } 1 \text{ point}\}. $$

Since the probability of the event $\{B_j \text{ contains exactly } 0 \text{ point}\}$ is equal to $(1 - \mu(B_j))^n$, and since the probability of $\{B_j \text{ contains exactly } 1 \text{ point}\}$ is $n\mu(B_j)(1 - \mu(B_j))^{n-1}$, the above sum is upper bounded by

$$ \sum_{j=1}^{N} (1 - \mu(B_j))^n + \sum_{j=1}^{N} n\mu(B_j)(1 - \mu(B_j))^{n-1}. $$

Combining the assumption $\mu(B_j) \ge \beta > 1/n$ with the monotonicity of the functions $x \mapsto (1-x)^n$ and $x \mapsto nx(1-x)^{n-1}$ on $(1/n, 1)$, one has the following upper bound

$$ N[(1 - \beta)^n + n\beta(1 - \beta)^{n-1}] $$

which is lower than $2Nn\beta(1 - \beta)^{n-1} \le 2Nn\beta \exp[-\beta(n - 1)]$. Lemma 38 is proved. ■

## E.2 Lower Bound and Minimal Conditions

### E.2.1 PROOF OF THEOREM 13.

From (Falconer, chap.2), we deduce directly the following lemma.

**Lemma 39** Given $L > 1$ and $n \ge 2$, there exists a set $\Omega_0 \subset (0, 1/(Ln)) \times (0, 1/(Ln))$ with Minkowski dimension $d_2 = 1 + \log^{-1}(n)$ w.r.t the Euclidean distance of $[0, 1]^2$, and a probability measure $\mu_0$ on $\Omega_0$.

Based on $(\Omega_0, \mu_0)$ described in Lemma 39, we construct two graphons that are difficult to distinguish for any estimator.

* $\Omega_1 = (0, 1) \times \{0\} \subset [0, 1]^2$ endowed with the uniform measure $\lambda$ on $(0, 1)$. In particular, $\lambda((0, 1) \times \{0\}) = 1$.

* $\Omega_2 = \Omega_1 \cup \Omega_0 \subset [0, 1]^2$ endowed with the probability measure:

$$ \mu_2 = (1 - n^{-1})\lambda + n^{-1}\mu_0. $$
### E.1.3 PROOF OF LEMMA 38.

Given $N$ balls $B_1, \dots, B_N$, let us upper bound the probability that (at least) one of the balls contains exactly zero or one sampled point $\omega_i$. With the union bound, this probability is lower than

$$ \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains exactly } 0 \text{ or } 1 \text{ sampled point among } \omega_1, \dots, \omega_n\} $$

which is again upper bounded with the union bound by

$$ \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains exactly } 0 \text{ point}\} + \sum_{j=1}^{N} \mathbb{P}_{(\Omega, \mu, W)} \{B_j \text{ contains exactly } 1 \text{ point}\}. $$

Since the probability of the event $\{B_j \text{ contains exactly } 0 \text{ point}\}$ is equal to $(1 - \mu(B_j))^n$, and since the probability of $\{B_j \text{ contains exactly } 1 \text{ point}\}$ is $n\mu(B_j)(1 - \mu(B_j))^{n-1}$, the above sum is upper bounded by

$$ \sum_{j=1}^{N} (1 - \mu(B_j))^n + \sum_{j=1}^{N} n\mu(B_j)(1 - \mu(B_j))^{n-1}. $$

Combining the assumption $\mu(B_j) \ge \beta > 1/n$ with the monotonicity of the functions $x \mapsto (1-x)^n$ and $x \mapsto nx(1-x)^{n-1}$ on $(1/n, 1)$, one has the following upper bound

$$ N[(1 - \beta)^n + n\beta(1 - \beta)^{n-1}] $$

which is lower than $2Nn\beta(1 - \beta)^{n-1} \le 2Nn\beta \exp[-\beta(n - 1)]$. Lemma 38 is proved. ■

## E.2 Lower Bound and Minimal Conditions

### E.2.1 PROOF OF THEOREM 13.

From (Falconer, chap.2), we deduce directly the following lemma.

**Lemma 39** Given $L > 1$ and $n \ge 2$, there exists a set $\Omega_0 \subset (0, 1/(Ln)) \times (0, 1/(Ln))$ with Minkowski dimension $d_2 = 1 + \log^{-1}(n)$ w.r.t the Euclidean distance of $[0, 1]^2$, and a probability measure $\mu_0$ on $\Omega_0$.

Based on $(\Omega_0, \mu_0)$ described in Lemma 39, we construct two graphons that are difficult to distinguish for any estimator.

* $\Omega_1 = (0, 1) \times \{0\} \subset [0, 1]^2$ endowed with the uniform measure $\lambda$ on $(0, 1)$. In particular, $\lambda((0, 1) \times \{0\}) = 1$.

* $\Omega_2 = \Omega_1 \cup \Omega_0 \subset [0, 1]^2$ endowed with the probability measure:

$$ \mu_2 = (1 - n^{-1})\lambda + n^{-1}\mu_0. $$
Consider a symmetric function $W: [0, 1]^2 \times [0, 1]^2 \to [0, 1]$ satisfying a double Hölder condition (6) with Hölder exponent $\alpha = 1$. Then, Appendix A.2 shows that the neighborhood distance (associated with such a $W$) behaves like the euclidean distance on $[0, 1]^2$, i.e.:

$$r_W(\omega, \omega') \asymp \|\omega - \omega\|_2$$

for all $\omega, \omega' \in [0, 1]^2$. Hence, $(\Omega_1, \lambda, W)$ and $(\Omega_2, \mu, W)$ satisfy $dim \Omega_2 = 1 + \log^{-1}(n)$ and $dim \Omega_1 = 1$, respectively. For brevity, we denote these dimensions by $d_2$ and $d_1$ in the following.

Let us check that all conditions of $W_n(D, \alpha, m, M, v)$ are satisfied by both graphons $(\Omega_1, \lambda, W)$ and $(\Omega_2, \mu_2, W)$. It is clear that $(\Omega_1, \lambda, W)$ belongs to the set $W_n(D, \alpha, m, M, v)$ for large enough $M$ and small enough $\alpha, m$. For the graphon $(\Omega_2, \mu_2, W)$, one has:

* Assumption $H_1^{\alpha,v}$: for any point $\omega \in \Omega_0$, note $\omega_{proj} \in \Omega_1$ its closest point in $\Omega_1$. As $\Omega_0 \subset (0, 1/(Ln))^2$, we have $r_W(\omega, \omega_{proj}) \le 1/(2n)$ for large enough $L$. Then, for all $\epsilon > 1/n$ and all $\omega \in \Omega_0$, one has

$$\begin{aligned}
\mu_2[B(\omega, \epsilon)] &\ge (1 - n^{-1})\lambda[B(\omega, \epsilon)] \\
&\ge (1 - n^{-1})\lambda[B(\omega_{proj}, \epsilon - 1/(2n))] \\
&\ge \frac{1}{2}\lambda[B(\omega_{proj}, \epsilon/2)].
\end{aligned}$$

which is larger than $\epsilon$ (up to a numerical constant) since $(\Omega_1, \lambda, W)$ satisfies the condition $H_1^{\alpha,v}$ for all $\epsilon > 0$.

* Assumption $H_2^{m,M,v}$ lower bound: $N_{\Omega_2}^{(c)}(\epsilon) \gtrsim N_{\Omega_1}^{(c)}(\epsilon) \gtrsim \epsilon^{-d_1}$ which is larger than $\epsilon^{-d_2+\log^{-1}(n)} \gtrsim \epsilon^{-d_2}$ because $\epsilon^{\log^{-1}(n)} \asymp 1$ for all $\epsilon \in (1/n, 1)$.

* Assumption $H_2^{m,M,v}$ upper bound: $N_{\Omega_2}^{(c)}(\epsilon) \lesssim N_{\Omega_1}^{(c)}(\epsilon) + N_{\Omega_0}^{(c)}(\epsilon) \lesssim N_{\Omega_1}^{(c)}(\epsilon)$ since $N_{\Omega_0}^{(c)}(\epsilon) \lesssim N_{\Omega_0}^{(c)}(1/n) = 1$ for $\epsilon > 1/n$ and large enough $L$. Combining with the fact that $(\Omega_1, \lambda, W)$ satisfies $H_2^{m,M,v}$, one obtain $N_{\Omega_2}^{(c)}(\epsilon) \lesssim \epsilon^{-d_1}$.

Thus, both graphons $(\Omega_1, \lambda, W)$ and $(\Omega_2, \mu_2, W)$ fulfill all conditions of $W_n(D, \alpha, m, M, v)$ for large enough constants $L, M$ and small enough constants $\alpha, m$.

We define the event $\mathcal{E}_{\Omega_1}$ where the i.i.d. sample $\omega_1, \dots, \omega_n$ is such that all points $\omega_1, \dots, \omega_n$ belong to $\Omega_1$. In particular, for the graphon $(\Omega_2, \mu_2, W)$, the probability of this event is larger than

$$\mu_2[\mathcal{E}_{\Omega_1}] \ge (1 - n^{-1})^n \ge \frac{1}{3}.$$

Then, for any estimator $\hat{d}$ based on the adjacency matrix $A$, one has

$$\begin{aligned}
\mathbb{P}_{(\Omega_2, \mu_2, W)}[|\hat{d} - dim \Omega_2| &\ge \frac{1}{2} \log^{-1}(n)] \\
&\ge \mathbb{P}_{(\Omega_2, \mu_2, W)}[|\hat{d} - dim \Omega_2| \ge \frac{1}{2} \log^{-1}(n)|\mathcal{E}_{\Omega_1}] \mu_2(\mathcal{E}_{\Omega_1})
\end{aligned}$$
Consider a symmetric function $W : [0, 1]^2 \times [0, 1]^2 \to [0, 1]$ satisfying a double Hölder condition (6) with Hölder exponent $\alpha = 1$. Then, Appendix A.2 shows that the neighborhood distance (associated with such a $W$) behaves like the euclidean distance on $[0, 1]^2$, i.e.:

$$r_W(\omega, \omega') \asymp \|\omega - \omega\|_2$$

for all $\omega, \omega' \in [0, 1]^2$. Hence, $(\Omega_1, \lambda, W)$ and $(\Omega_2, \mu, W)$ satisfy $dim \Omega_2 = 1 + \log^{-1}(n)$ and $dim \Omega_1 = 1$, respectively. For brevity, we denote these dimensions by $d_2$ and $d_1$ in the following.

Let us check that all conditions of $W_n(D, \alpha, m, M, v)$ are satisfied by both graphons $(\Omega_1, \lambda, W)$ and $(\Omega_2, \mu_2, W)$. It is clear that $(\Omega_1, \lambda, W)$ belongs to the set $W_n(D, \alpha, m, M, v)$ for large enough $M$ and small enough $\alpha, m$. For the graphon $(\Omega_2, \mu_2, W)$, one has:

* Assumption $H_1^{\alpha,v}$: for any point $\omega \in \Omega_0$, note $\omega_{proj} \in \Omega_1$ its closest point in $\Omega_1$. As $\Omega_0 \subset (0, 1/(Ln))^2$, we have $r_W(\omega, \omega_{proj}) \le 1/(2n)$ for large enough $L$. Then, for all $\epsilon > 1/n$ and all $\omega \in \Omega_0$, one has

$$\begin{aligned}
\mu_2[B(\omega, \epsilon)] &\ge (1 - n^{-1})\lambda[B(\omega, \epsilon)] \\
&\ge (1 - n^{-1})\lambda[B(\omega_{proj}, \epsilon - 1/(2n))] \\
&\ge \frac{1}{2}\lambda[B(\omega_{proj}, \epsilon/2)].
\end{aligned}$$

which is larger than $\epsilon$ (up to a numerical constant) since $(\Omega_1, \lambda, W)$ satisfies the condition $H_1^{\alpha,v}$ for all $\epsilon > 0$.

* Assumption $H_2^{m,M,v}$ lower bound: $N_{\Omega_2}^{(c)}(\epsilon) \gtrsim N_{\Omega_1}^{(c)}(\epsilon) \gtrsim \epsilon^{-d_1}$ which is larger than $\epsilon^{-d_2+\log^{-1}(n)} \gtrsim \epsilon^{-d_2}$ because $\epsilon^{\log^{-1}(n)} \asymp 1$ for all $\epsilon \in (1/n, 1)$.

* Assumption $H_2^{m,M,v}$ upper bound: $N_{\Omega_2}^{(c)}(\epsilon) \lesssim N_{\Omega_1}^{(c)}(\epsilon) + N_{\Omega_0}^{(c)}(\epsilon) \lesssim N_{\Omega_1}^{(c)}(\epsilon)$ since $N_{\Omega_0}^{(c)}(\epsilon) \lesssim N_{\Omega_0}^{(c)}(1/n) = 1$ for $\epsilon > 1/n$ and large enough $L$. Combining with the fact that $(\Omega_1, \lambda, W)$ satisfies $H_2^{m,M,v}$, one obtain $N_{\Omega_2}^{(c)}(\epsilon) \lesssim \epsilon^{-d_1}$.

Thus, both graphons $(\Omega_1, \lambda, W)$ and $(\Omega_2, \mu_2, W)$ fulfill all conditions of $W_n(D, \alpha, m, M, v)$ for large enough constants $L, M$ and small enough constants $\alpha, m$.

We define the event $\mathcal{E}_{\Omega_1}$ where the i.i.d. sample $\omega_1, \dots, \omega_n$ is such that all points $\omega_1, \dots, \omega_n$ belong to $\Omega_1$. In particular, for the graphon $(\Omega_2, \mu_2, W)$, the probability of this event is larger than

$$\mu_2[\mathcal{E}_{\Omega_1}] \ge (1 - n^{-1})^n \ge \frac{1}{3}.$$

Then, for any estimator $\hat{d}$ based on the adjacency matrix $A$, one has

$$\begin{aligned}
\mathbb{P}_{(\Omega_2, \mu_2, W)}[|\hat{d} - dim \Omega_2| &\ge \frac{1}{2} \log^{-1}(n)] \\
&\ge \mathbb{P}_{(\Omega_2, \mu_2, W)}[|\hat{d} - dim \Omega_2| \ge \frac{1}{2} \log^{-1}(n)|\mathcal{E}_{\Omega_1}] \mu_2(\mathcal{E}_{\Omega_1})
\end{aligned}$$
which is larger than

$$ \frac{1}{3} \mathbb{P}_{(\Omega_1, \lambda, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega_1| \le \frac{1}{2} \log^{-1}(n) \right] $$

since $|\hat{d} - \mathrm{dim} \, \Omega_1| \le \frac{1}{2} \log^{-1}(n)$ implies $|\hat{d} - \mathrm{dim} \, \Omega_2| \ge \frac{1}{2} \log^{-1}(n)$. Thus, by writing

$$ p := \mathbb{P}_{(\Omega_1, \lambda, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega_1| > \frac{1}{2} \log^{-1}(n) \right], $$

the above displays entail

$$ \mathbb{P}_{(\Omega_2, \mu_2, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega_2| \ge \frac{1}{2} \log^{-1}(n) \right] \ge \frac{1}{3} (1 - p) $$

which imply that

$$ \begin{aligned} \sup_{W_n(D, \alpha, m, M, v)} & \mathbb{P}_{(\Omega, \mu, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega| \ge \frac{1}{2} \log^{-1}(n) \right] \\ & \ge \max_{(\Omega_1, \lambda, W), (\Omega_2, \mu_2, W)} \mathbb{P}_{(\Omega, \mu, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega| \ge \frac{1}{2} \log^{-1}(n) \right] \\ & \ge p \lor \frac{1-p}{3} \end{aligned} $$

which is larger than 1/4. Theorem 13 is proved.

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

### E.2.2 PROOF OF THEOREM 14.

There are two cases.

For the class $W_n^{\mathrm{min}(1)}(D, \alpha, m, M, v)$, the condition $H_1^{\alpha, v}$ is not imposed. Consider the two following graphons.

* $(\Omega_1, \lambda, W)$ where $\Omega_1 = [0, 1] \times \{0\}^{D-1}$ is endowed with the uniform measure $\lambda$ on $[0, 1]$, with $\lambda(\Omega_1) = 1$, and where $W: [0, 1]^D \times [0, 1]^D \to [0, 1]$ is a symmetric function that satisfies a double Hölder condition (6) with Hölder exponent $\alpha = 1$.

* $(\Omega_2, \mu_2, W)$ where $\Omega_2 = [0, 1]^D$ and $\mu_2 = (1 - n^{-1})\lambda + n^{-1}\nu$, with $\nu$ the uniform measure on $[0, 1]^D$.

Following the proof of Theorem 13, we can show that these two graphons belong to $W_n^{\mathrm{min}(1)}(D, \alpha, m, M, v)$, and that

$$ \sup_{W_n^{\mathrm{min}(1)}(D, \alpha, m, M, v)} \mathbb{P}_{(\Omega, \mu, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega| \ge \frac{D}{2} \right] \ge \frac{1}{4} \quad (40) $$

which gives the error bound of Theorem 14.

For the class $W_n^{\mathrm{min}(2)}(D, \alpha, m, M, v)$, the assumption $H_2^{m, M, v}$ is not assumed. As in the proof of Theorem 13, we can see that the two following graphons belong to $W_n^{\mathrm{min}(2)}(D, \alpha, m, M, v)$.

* $(\Omega_1, \lambda, W)$ as defined in the above case.
which is larger than

$$ \frac{1}{3} \mathbb{P}_{(\Omega_1, \lambda, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega_1| \le \frac{1}{2} \log^{-1}(n) \right] $$

since $|\hat{d} - \mathrm{dim} \, \Omega_1| \le \frac{1}{2} \log^{-1}(n)$ implies $|\hat{d} - \mathrm{dim} \, \Omega_2| \ge \frac{1}{2} \log^{-1}(n)$. Thus, by writing

$$ p := \mathbb{P}_{(\Omega_1, \lambda, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega_1| > \frac{1}{2} \log^{-1}(n) \right], $$

the above displays entail

$$ \mathbb{P}_{(\Omega_2, \mu_2, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega_2| \ge \frac{1}{2} \log^{-1}(n) \right] \ge \frac{1}{3} (1 - p) $$

which imply that

$$ \begin{aligned} \sup_{W_n(D, \alpha, m, M, v)} & \mathbb{P}_{(\Omega, \mu, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega| \ge \frac{1}{2} \log^{-1}(n) \right] \\ & \ge \max_{(\Omega_1, \lambda, W), (\Omega_2, \mu_2, W)} \mathbb{P}_{(\Omega, \mu, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega| \ge \frac{1}{2} \log^{-1}(n) \right] \\ & \ge p \lor \frac{1-p}{3} \end{aligned} $$

which is larger than 1/4. Theorem 13 is proved.

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

### E.2.2 PROOF OF THEOREM 14.

There are two cases.

For the class $W_n^{\mathrm{min}(1)}(D, \alpha, m, M, v)$, the condition $H_1^{\alpha, v}$ is not imposed. Consider the two following graphons.

* $(\Omega_1, \lambda, W)$ where $\Omega_1 = [0, 1] \times \{0\}^{D-1}$ is endowed with the uniform measure $\lambda$ on $[0, 1]$, with $\lambda(\Omega_1) = 1$, and where $W: [0, 1]^D \times [0, 1]^D \to [0, 1]$ is a symmetric function that satisfies a double Hölder condition (6) with Hölder exponent $\alpha = 1$.

* $(\Omega_2, \mu_2, W)$ where $\Omega_2 = [0, 1]^D$ and $\mu_2 = (1 - n^{-1})\lambda + n^{-1}\nu$, with $\nu$ the uniform measure on $[0, 1]^D$.

Following the proof of Theorem 13, we can show that these two graphons belong to $W_n^{\mathrm{min}(1)}(D, \alpha, m, M, v)$, and that

$$ \sup_{W_n^{\mathrm{min}(1)}(D, \alpha, m, M, v)} \mathbb{P}_{(\Omega, \mu, W)} \left[ |\hat{d} - \mathrm{dim} \, \Omega| \ge \frac{D}{2} \right] \ge \frac{1}{4} \quad (40) $$

which gives the error bound of Theorem 14.

For the class $W_n^{\mathrm{min}(2)}(D, \alpha, m, M, v)$, the assumption $H_2^{m, M, v}$ is not assumed. As in the proof of Theorem 13, we can see that the two following graphons belong to $W_n^{\mathrm{min}(2)}(D, \alpha, m, M, v)$.

* $(\Omega_1, \lambda, W)$ as defined in the above case.
• $(\Omega_2, \mu_2, W)$ where $\Omega_2 = [0, 1/(Ln)]^D$ for some large enough (numerical) constant $L$, and $\mu_2 = (1 - n^{-1})\lambda + n^{-1}\nu$, with $\nu$ the uniform measure on $[0, 1/(Ln)]^D$.

As before, one can prove the error bound (40) over the class $W_n^{min(2)}(D, \alpha, m, M, v)$.

Thus, (40) is proved for $W_n^{min(j)}(D, \alpha, m, M, v)$, with $j \in \{1, 2\}$, and Theorem 14 follows.

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

# Appendix F. Estimation with Sparse Observations

## F.1 Proof of Corollary 19 : Estimation of the Distances

Corollary 19 is a reformulation of Theorem 7 in the sparse setting and their proofs are almost identical. In this appendix, denote by $W_n$ the function $\rho_n W$. Accordingly, $r_{W_n}$ denotes the neighborhood distance (4) where $W$ has been replaced with $W_n$. Hence, $r_{W_n} = \rho_n r_W$.

Corollary 19 is a direct consequence of the two following Lemmas.

**Lemma 40** For $\rho_n \ge 2\sqrt{\frac{\log n}{n-2}}$ and $n \ge 5$, the following event

$$ \mathcal{E}_{in}^{sp} := \left\{ \forall i, j \in [n] : \left| \langle A_i, A_j \rangle_n - \langle W_n(\omega_i, .), W_n(\omega_j, .) \rangle \right| \le 5 \rho_n \sqrt{\frac{\log n}{n}} \right\} $$

holds with probability at least $1 - \frac{2}{n}$ with respect to the distribution $P_{(\Omega, \mu, W), \rho_n}$.

Following the proof of Proposition 26, we show Lemma 40 below, by replacing Hoeffding inequality with Bernstein inequality, in order to benefit from the small variance of $A_{ij}$ (which is now of the order of $\rho_n$).

**Lemma 41** Conditionally to the event $\mathcal{E}_{in}^{sp}$, the following inequalities

$$ \forall i \in [n] : \left| \langle A_i, A_{\hat{m}(i)} \rangle_n - \langle W_n(\omega_i, .), W_n(\omega_i, .) \rangle \right| \le 3\rho_n r_{W_n}(\omega_i, \omega_{m(i)}) + 25 \rho_n \sqrt{\log(n)/n} $$

hold simultaneously.

The proof of lemma 41 is almost the same as for Proposition 27. It is omitted.

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

### F.1.1 PROOF OF LEMMA 40

Conditionally to $\omega_i, \omega_j$, $i \ne j$, the $n-2$ random variables $\{A_{ik}A_{kj} : k \in [n], k \ne i, j\}$ are independent with expectation $E[A_{ik}A_{kj}] = \int_{\Omega} W_n(\omega_i, z)W_n(\omega_j, z)\mu(dz)$ for all $k \ne i, j$ (where $E$ is taken w.r.t. the distribution $P_{(\Omega, \mu, W), \rho_n}$). Using Bernstein inequality (see Sridharan, 2002, for instance), one has

$$ P_{(\Omega, \mu, W), \rho_n} \left( \frac{1}{n-2} \left| \sum_{k \ne i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W_n(\omega_i, z) W_n(\omega_j, z) \mu(dz) \right| \ge \epsilon \middle| \omega_i, \omega_j \right) $$

smaller than

$$ \le 2\exp \left( \frac{-(n-2)\epsilon^2}{2\rho_n^2 + 2\epsilon/3} \right) $$
• $(\Omega_2, \mu_2, W)$ where $\Omega_2 = [0, 1/(Ln)]^D$ for some large enough (numerical) constant $L$, and $\mu_2 = (1 - n^{-1})\lambda + n^{-1}\nu$, with $\nu$ the uniform measure on $[0, 1/(Ln)]^D$.

As before, one can prove the error bound (40) over the class $W_n^{min(2)}(D, \alpha, m, M, v)$.

Thus, (40) is proved for $W_n^{min(j)}(D, \alpha, m, M, v)$, with $j \in \{1, 2\}$, and Theorem 14 follows.

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

# Appendix F. Estimation with Sparse Observations

## F.1 Proof of Corollary 19 : Estimation of the Distances

Corollary 19 is a reformulation of Theorem 7 in the sparse setting and their proofs are almost identical. In this appendix, denote by $W_n$ the function $\rho_n W$. Accordingly, $r_{W_n}$ denotes the neighborhood distance (4) where $W$ has been replaced with $W_n$. Hence, $r_{W_n} = \rho_n r_W$.

Corollary 19 is a direct consequence of the two following Lemmas.

**Lemma 40** For $\rho_n \ge 2\sqrt{\frac{\log n}{n-2}}$ and $n \ge 5$, the following event

$$ \mathcal{E}_{in}^{sp} := \left\{ \forall i, j \in [n] : \left| \langle A_i, A_j \rangle_n - \langle W_n(\omega_i, .), W_n(\omega_j, .) \rangle \right| \le 5 \rho_n \sqrt{\frac{\log n}{n}} \right\} $$

holds with probability at least $1 - \frac{2}{n}$ with respect to the distribution $P_{(\Omega, \mu, W), \rho_n}$.

Following the proof of Proposition 26, we show Lemma 40 below, by replacing Hoeffding inequality with Bernstein inequality, in order to benefit from the small variance of $A_{ij}$ (which is now of the order of $\rho_n$).

**Lemma 41** Conditionally to the event $\mathcal{E}_{in}^{sp}$, the following inequalities

$$ \forall i \in [n] : \left| \langle A_i, A_{\hat{m}(i)} \rangle_n - \langle W_n(\omega_i, .), W_n(\omega_i, .) \rangle \right| \le 3\rho_n r_{W_n}(\omega_i, \omega_{m(i)}) + 25 \rho_n \sqrt{\log(n)/n} $$

hold simultaneously.

The proof of lemma 41 is almost the same as for Proposition 27. It is omitted.

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

### F.1.1 PROOF OF LEMMA 40

Conditionally to $\omega_i, \omega_j$, $i \ne j$, the $n-2$ random variables $\{A_{ik}A_{kj} : k \in [n], k \ne i, j\}$ are independent with expectation $E[A_{ik}A_{kj}] = \int_{\Omega} W_n(\omega_i, z)W_n(\omega_j, z)\mu(dz)$ for all $k \ne i, j$ (where $E$ is taken w.r.t. the distribution $P_{(\Omega, \mu, W), \rho_n}$). Using Bernstein inequality (see Sridharan, 2002, for instance), one has

$$ P_{(\Omega, \mu, W), \rho_n} \left( \frac{1}{n-2} \left| \sum_{k \ne i, j} A_{ik} A_{kj} - (n-2) \int_{\Omega} W_n(\omega_i, z) W_n(\omega_j, z) \mu(dz) \right| \ge \epsilon \middle| \omega_i, \omega_j \right) $$

smaller than

$$ \le 2\exp\left(\frac{-(n-2)\epsilon^2}{2\rho_n^2 + 2\epsilon/3}\right) $$
for $\epsilon > 0$. Since the above inequality is satisfied for almost every $\omega_i, \omega_j \in \Omega$, we have the same upper bound for the non-conditional probability. Then, setting $\epsilon = 3\rho_n\sqrt{\frac{\log n}{n-2}}$ gives

$$2\exp\left(\frac{-(n-2)\epsilon^2}{2\rho_n^2 + 2\epsilon/3}\right) \le 2\exp\left(\frac{-9\log n}{2 + \frac{2}{\rho_n}\sqrt{\frac{\log n}{n-2}}}\right) \le \frac{2}{n^3}$$

since $\rho_n \ge 2\sqrt{\frac{\log n}{n-2}}$ by assumption. Thus, by using the union bound over all $i \ne j$, one obtain

$$\mathbb{P}_{(\Omega, \mu, W), \rho_n} \left( \bigcup_{i,j:i \ne j} \left\{ \frac{1}{n-2} \left| \sum_{k \ne i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W_n(\omega_i, z)W_n(\omega_j, z)\mu(dz) \right| \ge \epsilon \right\} \right) \le \frac{2}{n}.$$

And finally, following the proof of Proposition 26 leads to

$$\max_{i,j:i \ne j} \left| \sum_k \frac{A_{ik}A_{kj}}{n} - \int_{\Omega} W_n(\omega_i, z)W_n(\omega_j, z)\mu(dz) \right| \le 3\rho_n \sqrt{\frac{\log n}{n-2}} + \frac{4}{n}$$

with probability at least $1 - \frac{2}{n}$. To conclude the proof of Lemma 40, observe that above display is upper bounded by

$$\le 5\rho_n\sqrt{\frac{\log n}{n}}$$

as soon as $n \ge 5$.

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

## F.2 Proof of of Corollary 20 : Estimation of the Dimension

In the proof of Theorem 35, one has seen

$$\frac{\log m}{-\log \epsilon} - d \frac{(s_{\omega} + b_{sup})/\epsilon}{-\log \epsilon} \le \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \le \frac{\log M}{-\log \epsilon} + d \frac{(s_{\omega} + b_{sup})/\epsilon + ((s_{\omega} + b_{sup})/\epsilon)^2}{-\log \epsilon}.$$

The sampling error $s_{\omega}$ is not affected by the sparsification of the data through $\rho_n$, and thus takes the same value as in Theorem 35. On the other hand, the distance error bound $b_{sup}$ changes, and is now defined as

$$b_{sup}^2 := 6 \max_{1 \le i \le n} r_W(\omega_i, \omega_{m(i)}) + \frac{60}{\rho_n} \sqrt{\log(n)/n}$$

according to Corollary 19. Following the proof of Theorem 35, one has

$$b_{sup} + s_{\omega} \le 6 \left( \frac{2 \log n}{\alpha n} \right)^{1/2d} + \frac{8}{\sqrt{\rho_n}} \left( \frac{\log n}{n} \right)^{1/4}.$$

Define

$$err_{n,d,\rho_n} := \left( \frac{2 \log n}{\alpha n} \right)^{1/2d} + \frac{1}{\sqrt{\rho_n}} \left( \frac{\log n}{n} \right)^{1/4} \quad (41)$$
for $\epsilon > 0$. Since the above inequality is satisfied for almost every $\omega_i, \omega_j \in \Omega$, we have the same upper bound for the non-conditional probability. Then, setting $\epsilon = 3\rho_n\sqrt{\frac{\log n}{n-2}}$ gives

$$2\exp\left(\frac{-(n-2)\epsilon^2}{2\rho_n^2 + 2\epsilon/3}\right) \le 2\exp\left(\frac{-9\log n}{2 + \frac{2}{\rho_n}\sqrt{\frac{\log n}{n-2}}}\right) \le \frac{2}{n^3}$$

since $\rho_n \ge 2\sqrt{\frac{\log n}{n-2}}$ by assumption. Thus, by using the union bound over all $i \ne j$, one obtain

$$\mathbb{P}_{(\Omega, \mu, W), \rho_n} \left( \bigcup_{i,j:i \ne j} \left\{ \frac{1}{n-2} \left| \sum_{k \ne i, j} A_{ik}A_{kj} - (n-2) \int_{\Omega} W_n(\omega_i, z)W_n(\omega_j, z)\mu(dz) \right| \ge \epsilon \right\} \right) \le \frac{2}{n}.$$

And finally, following the proof of Proposition 26 leads to

$$\max_{i,j:i \ne j} \left| \sum_k \frac{A_{ik}A_{kj}}{n} - \int_{\Omega} W_n(\omega_i, z)W_n(\omega_j, z)\mu(dz) \right| \le 3\rho_n \sqrt{\frac{\log n}{n-2}} + \frac{4}{n}$$

with probability at least $1 - \frac{2}{n}$. To conclude the proof of Lemma 40, observe that above display is upper bounded by

$$\le 5\rho_n\sqrt{\frac{\log n}{n}}$$

as soon as $n \ge 5$.

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

## F.2 Proof of of Corollary 20 : Estimation of the Dimension

In the proof of Theorem 35, one has seen

$$\frac{\log m}{-\log \epsilon} - d \frac{(s_{\omega} + b_{sup})/\epsilon}{-\log \epsilon} \le \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \le \frac{\log M}{-\log \epsilon} + d \frac{(s_{\omega} + b_{sup})/\epsilon + ((s_{\omega} + b_{sup})/\epsilon)^2}{-\log \epsilon}.$$

The sampling error $s_\omega$ is not affected by the sparsification of the data through $\rho_n$, and thus takes the same value as in Theorem 35. On the other hand, the distance error bound $b_{sup}$ changes, and is now defined as

$$b_{sup}^2 := 6 \max_{1 \le i \le n} r_W(\omega_i, \omega_{m(i)}) + \frac{60}{\rho_n} \sqrt{\log(n)/n}$$

according to Corollary 19. Following the proof of Theorem 35, one has

$$b_{sup} + s_{\omega} \le 6 \left( \frac{2 \log n}{\alpha n} \right)^{1/2d} + \frac{8}{\sqrt{\rho_n}} \left( \frac{\log n}{n} \right)^{1/4}.$$

Define

$$err_{n,d,\rho_n} := \left( \frac{2 \log n}{\alpha n} \right)^{1/2d} + \frac{1}{\sqrt{\rho_n}} \left( \frac{\log n}{n} \right)^{1/4} \quad (41)$$
so that

$$b_{sup} + s_{\omega} \leq 8 err_{n,d,\rho_n}.$$

Following the proof of Theorem 35, one obtain the same error bound for the dimension estimation, after replacing 6 err$_{n,d}$ with 8 err$_{n,d,\rho_n}$. Indeed, one has

$$\left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \right| \leq \frac{1}{-\log \epsilon} \left[ \log \left( M \vee \frac{1}{m} \right) + 8d \frac{\mathrm{err}_{n,d}}{\epsilon} \left( 1 + \frac{\mathrm{err}_{n,d}}{\epsilon} \right) \right] \quad (42)$$

for all $\epsilon \in ]0, v/9]$ and all $n$ such that

$$2\log n/n \leq \alpha (v/18)^{2d} \wedge \rho_n^2 (v/18)^4.$$

As in the proof of Theorem 12, one minimizes the error bound (42) by choosing a particular radius of the order of $\sup_{\{d: d \leq D\}} err_{n,d,\rho_n} = err_{n,D,\rho_n}$. This gives a radius that satisfies the following relation

$$\epsilon_{D, \rho_n} \asymp \left( \frac{\log n}{n} \right)^{1/(2D)} \vee \frac{1}{\sqrt{\rho_n}} \left( \frac{\log n}{n} \right)^{1/4}.$$

Corollary 20 follows from the plug-in of $\epsilon_{D, \rho_n}$ in (42).

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

# Appendix G. Testing the Complexity via Under-estimation of the Packing Number

The current appendix is organized as follows. We first analyse the performance of the new distance estimator (19) and then deduce a control on the type I and II errors of the test.

## G.1 Performance of the New Distance Estimator

Lemma 42 shows that the new distance-estimator $\hat{r}_{new}$ does not over-estimate $r_W$ in the sense of (44), without underestimating too much (45). Let $U$ be the function defined by

$$U(i) = \underset{t \in \{i, \hat{m}(i)\}}{\operatorname{argmax}} \langle W(\omega_t, .), W(\omega_t, .) \rangle \quad (43)$$

for all $i \in [n]$. This means that $U(i)$ indicates which of the two functions $W(\omega_i, .)$ or $W(\omega_{\hat{m}(i)}, .)$ has the largest $l_2$-norm $||.||_{2,\mu}$ (see Section 4.1 for the definitions of the inner product and the norm).

**Lemma 42** Consider $t_n = 12 \sqrt{\frac{\log n}{n}}$ a fluctuation term and the function $U$ introduced in (43). One has the following bounds on the new distance estimator (19)

$$\hat{r}_{new}^2(i, j) \leq r_W^2(\omega_{U(i)}, \omega_{U(j)}) + t_n \quad (44)$$

$$\hat{r}_{new}^2(i, j) \geq r_W^2(\omega_i, \omega_j) - 5r_W(\omega_i, \omega_{m(i)}) - 5r_W(\omega_j, \omega_{m(j)}) - 5t_n \quad (45)$$

holding simultaneously for all $i, j \in [n]$ with probability at least $1 - \frac{2}{n}$ with respect to the distribution $P_{(\Omega, \mu, W)}$.
so that

$$b_{sup} + s_{\omega} \leq 8 err_{n,d,\rho_n}.$$

Following the proof of Theorem 35, one obtain the same error bound for the dimension estimation, after replacing 6 err$_{n,d}$ with 8 err$_{n,d,\rho_n}$. Indeed, one has

$$\left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \right| \leq \frac{1}{-\log \epsilon} \left[ \log \left( M \vee \frac{1}{m} \right) + 8d \frac{\mathrm{err}_{n,d}}{\epsilon} \left( 1 + \frac{\mathrm{err}_{n,d}}{\epsilon} \right) \right] \quad (42)$$

for all $\epsilon \in ]0, v/9]$ and all $n$ such that

$$2\log n/n \leq \alpha (v/18)^{2d} \wedge \rho_n^2 (v/18)^4.$$

As in the proof of Theorem 12, one minimizes the error bound (42) by choosing a particular radius of the order of $\sup_{\{d: d \leq D\}} err_{n,d,\rho_n} = err_{n,D,\rho_n}$. This gives a radius that satisfies the following relation

$$\epsilon_{D, \rho_n} \asymp \left( \frac{\log n}{n} \right)^{1/(2D)} \vee \frac{1}{\sqrt{\rho_n}} \left( \frac{\log n}{n} \right)^{1/4}.$$

Corollary 20 follows from the plug-in of $\epsilon_{D, \rho_n}$ in (42).

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

# Appendix G. Testing the Complexity via Under-estimation of the Packing Number

The current appendix is organized as follows. We first analyse the performance of the new distance estimator (19) and then deduce a control on the type I and II errors of the test.

## G.1 Performance of the New Distance Estimator

Lemma 42 shows that the new distance-estimator $\hat{r}_{new}$ does not over-estimate $r_W$ in the sense of (44), without underestimating too much (45). Let $U$ be the function defined by

$$U(i) = \underset{t \in \{i, \hat{m}(i)\}}{\operatorname{argmax}} \langle W(\omega_t, .), W(\omega_t, .) \rangle \quad (43)$$

for all $i \in [n]$. This means that $U(i)$ indicates which of the two functions $W(\omega_i, .)$ or $W(\omega_{\hat{m}(i)}, .)$ has the largest $l_2$-norm $||.||_{2,\mu}$ (see Section 4.1 for the definitions of the inner product and the norm).

**Lemma 42** Consider $t_n = 12 \sqrt{\frac{\log n}{n}}$ a fluctuation term and the function $U$ introduced in (43). One has the following bounds on the new distance estimator (19)

$$\hat{r}_{new}^2(i, j) \leq r_W^2(\omega_{U(i)}, \omega_{U(j)}) + t_n \quad (44)$$

$$\hat{r}_{new}^2(i, j) \geq r_W^2(\omega_i, \omega_j) - 5r_W(\omega_i, \omega_{m(i)}) - 5r_W(\omega_j, \omega_{m(j)}) - 5t_n \quad (45)$$

holding simultaneously for all $i, j \in [n]$ with probability at least $1 - \frac{2}{n}$ with respect to the distribution $P_{(\Omega, \mu, W)}$.
Let us prove Lemma 42. Recall the useful Proposition 26 on the convergence of the inner products: the event $\mathcal{E}_{in}$ where the following inequalities hold simultaneously for all $i \neq j$

$$ |\langle A_i, A_j \rangle_n - \langle W(\omega_i, .), W(\omega_j, .) \rangle| \le 3\sqrt{\log n/n} \quad (46) $$

happens with probability at least $1 - 2/n$.

**Proof of (44).** Assume the above event $\mathcal{E}_{in}$ holds. For all $i, j \in [n]$ such that $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} = \emptyset$, the line (46) gives

$$ \hat{r}_{new}^2(i, j) \le \langle W(\omega_i, .), W(\omega_{\hat{m}(i)}, .) \rangle + \langle W(\omega_j, .), W(\omega_{\hat{m}(j)}, .) \rangle - 2 \max_{v \in \{i, \hat{m}(i)\}, w \in \{j, \hat{m}(j)\}} \langle W(\omega_v, .), W(\omega_w, .) \rangle + t_n $$

with $t_n = 12 \sqrt{\log n}$. Then, using the function $U$ defined by (43), one has

$$ \hat{r}_{new}^2(i, j) \le \langle W(\omega_{U(i)}, .), W(\omega_{U(i)}, .) \rangle + \langle W(\omega_{U(j)}, .), W(\omega_{U(j)}, .) \rangle - 2 \langle W(\omega_{U(i)}, .), W(\omega_{U(j)}, .) \rangle + t_n $$

which is upper bounded by

$$ r_W^2(\omega_{U(i)}, \omega_{U(j)}) + t_n $$

with Cauchy-Schwarz inequality. The line (44) is proved in the case $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} = \emptyset$.

If $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} \neq \emptyset$, we can see that $\hat{r}_{new}^2(i, j) \le 0$. Thus (44) trivially holds in this case too. The inequalities (44) are proved. ■

**Proof of (45).** Assume the event $\mathcal{E}_{in}$ of Proposition 26 holds.

If $i, j \in [n]$ such that $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} = \emptyset$,

$$ |r_W^2(\omega_i, \omega_j) - \hat{r}_{new}^2(i, j)| \le |r_W^2(\omega_i, \omega_j) - \hat{r}^2(i, j)| + |\hat{r}^2(i, j) - \hat{r}_{new}^2(i, j)| $$

by triangle inequality. The left term is upper bounded by

$$ 3 r_W(\omega_j, \omega_{m(j)}) + 3 r_W(\omega_i, \omega_{m(i)}) + 36 \sqrt{\log(n)/n} $$

thanks to Theorem 7. The right term is equal to

$$ 2 \left| \langle A_i, A_j \rangle - \max_{k \in \{i, \hat{m}(i)\}, l \in \{j, \hat{m}(j)\}} \langle A_k, A_l \rangle \right| $$

which is upper bounded by

$$ r_W(\omega_j, \omega_{m(j)}) + r_W(\omega_i, \omega_{m(i)}) + 12 \sqrt{\log(n)/n} $$

using the same technique as in the proof of Theorem 7. Combining the above displays, one has

$$ |r_W^2(\omega_i, \omega_j) - \hat{r}_{new}^2(i, j)| \le 5 r_W(\omega_j, \omega_{m(j)}) + 5 r_W(\omega_i, \omega_{m(i)}) + 60 \sqrt{\log(n)/n}, $$

which implies

$$ \hat{r}_{new}^2(i, j) \ge r_W^2(\omega_i, \omega_j) - 5 r_W(\omega_j, \omega_{m(j)}) - 5 r_W(\omega_i, \omega_{m(i)}) - 60 \sqrt{\log(n)/n}. \quad (47) $$
Let us prove Lemma 42. Recall the useful Proposition 26 on the convergence of the inner products: the event $\mathcal{E}_{in}$ where the following inequalities hold simultaneously for all $i \neq j$

$$ |\langle A_i, A_j \rangle_n - \langle W(\omega_i, .), W(\omega_j, .) \rangle| \le 3\sqrt{\log n/n} \quad (46) $$

happens with probability at least $1 - 2/n$.

**Proof of (44).** Assume the above event $\mathcal{E}_{in}$ holds. For all $i, j \in [n]$ such that $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} = \emptyset$, the line (46) gives

$$ \hat{r}_{new}^2(i, j) \le \langle W(\omega_i, .), W(\omega_{\hat{m}(i)}, .) \rangle + \langle W(\omega_j, .), W(\omega_{\hat{m}(j)}, .) \rangle - 2 \max_{v \in \{i, \hat{m}(i)\}, w \in \{j, \hat{m}(j)\}} \langle W(\omega_v, .), W(\omega_w, .) \rangle + t_n $$

with $t_n = 12 \sqrt{\log n}$. Then, using the function $U$ defined by (43), one has

$$ \hat{r}_{new}^2(i, j) \le \langle W(\omega_{U(i)}, .), W(\omega_{U(i)}, .) \rangle + \langle W(\omega_{U(j)}, .), W(\omega_{U(j)}, .) \rangle - 2 \langle W(\omega_{U(i)}, .), W(\omega_{U(j)}, .) \rangle + t_n $$

which is upper bounded by

$$ r_W^2(\omega_{U(i)}, \omega_{U(j)}) + t_n $$

with Cauchy-Schwarz inequality. The line (44) is proved in the case $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} = \emptyset$.

If $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} \neq \emptyset$, we can see that $\hat{r}_{new}^2(i, j) \le 0$. Thus (44) trivially holds in this case too. The inequalities (44) are proved. ■

**Proof of (45).** Assume the event $\mathcal{E}_{in}$ of Proposition 26 holds.

If $i, j \in [n]$ such that $\{i, \hat{m}(i)\} \cap \{j, \hat{m}(j)\} = \emptyset$,

$$ |r_W^2(\omega_i, \omega_j) - \hat{r}_{new}^2(i, j)| \le |r_W^2(\omega_i, \omega_j) - \hat{r}^2(i, j)| + |\hat{r}^2(i, j) - \hat{r}_{new}^2(i, j)| $$

by triangle inequality. The left term is upper bounded by

$$ 3 r_W(\omega_j, \omega_{m(j)}) + 3 r_W(\omega_i, \omega_{m(i)}) + 36 \sqrt{\log(n)/n} $$

thanks to Theorem 7. The right term is equal to

$$ 2 \left| \langle A_i, A_j \rangle - \max_{k \in \{i, \hat{m}(i)\}, l \in \{j, \hat{m}(j)\}} \langle A_k, A_l \rangle \right| $$

which is upper bounded by

$$ r_W(\omega_j, \omega_{m(j)}) + r_W(\omega_i, \omega_{m(i)}) + 12 \sqrt{\log(n)/n} $$

using the same technique as in the proof of Theorem 7. Combining the above displays, one has

$$ |r_W^2(\omega_i, \omega_j) - \hat{r}_{new}^2(i, j)| \le 5 r_W(\omega_j, \omega_{m(j)}) + 5 r_W(\omega_i, \omega_{m(i)}) + 60 \sqrt{\log(n)/n}, $$

which implies

$$ \hat{r}_{new}^2(i, j) \ge r_W^2(\omega_i, \omega_j) - 5 r_W(\omega_j, \omega_{m(j)}) - 5 r_W(\omega_i, \omega_{m(i)}) - 60 \sqrt{\log(n)/n}. \quad (47) $$
The line (45) is therefore proved in the case {$i, \hat{m}(i)} \cap \{j, \hat{m}(j)\} = \emptyset$.

If $i, j \in [n]$ such that {$i, \hat{m}(i)} \cap \{j, \hat{m}(j)\} \neq \emptyset$,

$$ \hat{r}_{new}(i, j) = 0. $$

Hence, it is enough to show that the right hand side of (47) is non-positive. Consider the particular case where $\hat{m}(i) = j$ and $i \neq \hat{m}(j)$ for example. Then, one has

$$ |\hat{r}^2(i, j)| = |\langle A_{\hat{m}(j)}, A_j \rangle - \langle A_i, A_j \rangle| \le |\langle A_i, A_j - A_{\hat{m}(j)} \rangle| + |\langle A_i - A_j, A_{\hat{m}(j)} \rangle| $$

which is upper bounded by

$$ \hat{f}(j, m(j)) + \hat{f}(i, m(i)) $$

where $\hat{f}$ has been introduced in (9). As in the proof of Theorem 7, one can show that the above display is upper bounded by

$$ r_W(\omega_j, \omega_{m(j)}) + r_W(\omega_i, \omega_{m(i)}) + 12 \sqrt{\log(n)/n} $$

on the event $\mathcal{E}_{in}$. Combining this upper bound of $\hat{r}$ with the following lower bound from Theorem 7

$$ \hat{r}^2(i, j) \ge r_W^2(\omega_i, \omega_j) - 3 r_W(\omega_i, \omega_{m(i)}) - 3 r_W(\omega_j, \omega_{m(j)}) - 36 \sqrt{\log(n)/n}, \quad (48) $$

one derive

$$ r_W^2(\omega_i, \omega_j) \le 4 r_W(\omega_i, \omega_{m(i)}) + 4 r_W(\omega_j, \omega_{m(j)}) + 48 \sqrt{\log(n)/n}. $$

This implies that the right hand side of (47) is non positive. Hence (45) is proved in the particular case $\hat{m}(i) = j$ and $i \neq \hat{m}(j)$. By symmetry, it remains only the case $\hat{m}(i) = \hat{m}(j)$ to do. Following the above proof, we can show taht (45) holds for this case too. The inequality (45) is therefore proved in the case {$i, \hat{m}(i)} \cap \{j, \hat{m}(j)\} \neq \emptyset$.

The line (45) is proved, and Lemma 42 follows.

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

## G.2 Control on the Type I and II Errors

In Theorem 16 on the new packing number estimator, the left hand side of (20) is similar to Section 4.3 on the covering number estimator, and thus straightforward. The right hand side of (20) and Corollary 17 are proved together below.

### G.2.1 PROOF FOR THE TYPE I ERROR

Assume the null-hypothesis $N_{\Omega}^{(p)}(\epsilon) \le K$ holds. We want to show that the same inequality is satisfied by the statistic $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon})$. Proof by contradiction: assume the inequality $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon}) \ge K + 1$ holds. This means that there are $K + 1$ indices $i_1, \dots, i_{K+1} \in [n]$ such that the following inequalities hold

$$ \forall s, t \in \{1, \dots, K+1\} : \hat{\epsilon}^2 < \hat{r}_{new}^2(i_s, i_t). $$
The line (45) is therefore proved in the case {$i, \hat{m}(i)} \cap \{j, \hat{m}(j)\} = \emptyset$.

If $i, j \in [n]$ such that {$i, \hat{m}(i)} \cap \{j, \hat{m}(j)\} \neq \emptyset$,

$$ \hat{r}_{new}(i, j) = 0. $$

Hence, it is enough to show that the right hand side of (47) is non-positive. Consider the particular case where $\hat{m}(i) = j$ and $i \neq \hat{m}(j)$ for example. Then, one has

$$ |\hat{r}^2(i, j)| = |\langle A_{\hat{m}(j)}, A_j \rangle - \langle A_i, A_j \rangle| \le |\langle A_i, A_j - A_{\hat{m}(j)} \rangle| + |\langle A_i - A_j, A_{\hat{m}(j)} \rangle| $$

which is upper bounded by

$$ \hat{f}(j, m(j)) + \hat{f}(i, m(i)) $$

where $\hat{f}$ has been introduced in (9). As in the proof of Theorem 7, one can show that the above display is upper bounded by

$$ r_W(\omega_j, \omega_{m(j)}) + r_W(\omega_i, \omega_{m(i)}) + 12 \sqrt{\log(n)/n} $$

on the event $\mathcal{E}_{in}$. Combining this upper bound of $\hat{r}$ with the following lower bound from Theorem 7

$$ \hat{r}^2(i, j) \ge r_W^2(\omega_i, \omega_j) - 3 r_W(\omega_i, \omega_{m(i)}) - 3 r_W(\omega_j, \omega_{m(j)}) - 36 \sqrt{\log(n)/n}, \quad (48) $$

one derive

$$ r_W^2(\omega_i, \omega_j) \le 4 r_W(\omega_i, \omega_{m(i)}) + 4 r_W(\omega_j, \omega_{m(j)}) + 48 \sqrt{\log(n)/n}. $$

This implies that the right hand side of (47) is non positive. Hence (45) is proved in the particular case $\hat{m}(i) = j$ and $i \neq \hat{m}(j)$. By symmetry, it remains only the case $\hat{m}(i) = \hat{m}(j)$ to do. Following the above proof, we can show taht (45) holds for this case too. The inequality (45) is therefore proved in the case {$i, \hat{m}(i)} \cap \{j, \hat{m}(j)\} \neq \emptyset$.

The line (45) is proved, and Lemma 42 follows.

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

## G.2 Control on the Type I and II Errors

In Theorem 16 on the new packing number estimator, the left hand side of (20) is similar to Section 4.3 on the covering number estimator, and thus straightforward. The right hand side of (20) and Corollary 17 are proved together below.

### G.2.1 PROOF FOR THE TYPE I ERROR

Assume the null-hypothesis $N_{\Omega}^{(p)}(\epsilon) \le K$ holds. We want to show that the same inequality is satisfied by the statistic $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon})$. Proof by contradiction: assume the inequality $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon}) \ge K + 1$ holds. This means that there are $K + 1$ indices $i_1, \dots, i_{K+1} \in [n]$ such that the following inequalities hold

$$ \forall s, t \in \{1, \dots, K+1\} : \hat{\epsilon}^2 < \hat{r}_{new}^2(i_s, i_t). $$
Combining the above inequalities with the under-estimation property (44), one has

$$ \forall s, t \in \{1, \dots, K+1\} : \hat{\epsilon}^2 < r_W^2(\omega_{U(i_s)}, \omega_{U(i_t)}) + t_n $$

with probability at least $1 - 2/n$. Replacing the radius $\hat{\epsilon}^2$ by its value $\epsilon^2 + t_n$, it comes

$$ \forall s, t \in \{1, \dots, K+1\} : \epsilon^2 < r_W^2(\omega_{U(i_s)}, \omega_{U(i_t)}). $$

Thus, $K+1$ sampled points are separated by at least a distance $\epsilon$, which implies $N_{\Omega}^{(p)}(\epsilon) \ge K+1$. This contradicts the null-hypothesis. ■

Corollary 17 and Theorem 16 are therefore proved.

### G.2.2 PROOF FOR THE TYPE II ERROR (THEOREM 18).

Consider a graphon $(\Omega, \mu, W)$ in the set $W(\eta, \beta)$. By definition of $W(\eta, \beta)$, there are $K+1$ balls in $(\Omega, r_W)$ whose centers are separated by at least a distance $\sqrt{\epsilon^2 + 10\eta + 6t_n} + \eta$. Label these balls by $s \in \{1, \dots, K+1\}$. As in the proof for the dimension estimation, assume the complementary of the event $\mathcal{E}_{bad}$, i.e. assume that each of the $K+1$ balls contains at least two sampled points. Accordingly, denote by $i_1, j_1, \dots, i_{K+1}, j_{K+1}$ the indices of the corresponding sampled points such that $\omega_{i_s}, \omega_{j_s}$ belong to the $s^{th}$ ball with $s \in \{1, \dots, K+1\}$. Since the radius of these ball is smaller than $\eta/2$, one has

$$ r_W(\omega_{i_s}, \omega_{m(i_s)}) \le r_W(\omega_{i_s}, \omega_{j_s}) \le \eta \quad (49) $$

for all $s \in \{1, \dots, K+1\}$.

On the event $\mathcal{E}_{in}$ of Proposition 26, Lemma 42 gives

$$ \hat{r}_{new}^2(i_s, i_t) \ge r_W^2(\omega_{i_s}, \omega_{i_t}) - 5r_W(\omega_{i_s}, \omega_{m(i_s)}) - 5r_W(\omega_{j_s}, \omega_{m(j_s)}) - 5t_n. $$

for all $s \neq t \in \{1, \dots, K+1\}$. Using (49), one derive

$$ \hat{r}_{new}^2(i_s, i_t) \ge r_W^2(\omega_{i_s}, \omega_{i_t}) - 10\eta - 5t_n. \quad (50) $$

The ball centers are separated by at least a distance $\sqrt{\epsilon^2 + 10\eta + 6t_n} + \eta$ by assumption, which implies that the points in these balls are separated by

$$ r_W(\omega_{i_s}, \omega_{i_t}) > \sqrt{\epsilon^2 + 10\eta + 6t_n} $$

for all $s \neq t \in \{1, \dots, K+1\}$, since the ball radii are all smaller than $\eta/2$. Combining this inequality with the line (50), one obtain

$$ \hat{r}_{new}^2(i_s, i_t) > \epsilon^2 + t_n $$

for all $s \neq t \in \{1, \dots, K+1\}$. Since $\hat{\epsilon} = \sqrt{\epsilon^2 + t_n}$, this gives $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon}) \ge K+1$. Thus, the alternative hypothesis is confirmed correctly.

The above displays hold on the event $\mathcal{E}_{in} \cap \mathcal{E}_{bad}^c$. Let us upper bound the probability of the complementary event. The union bound gives

$$ \mathbb{P}(\mathcal{E}_{in}^c \cup \mathcal{E}_{bad}) \le \frac{2}{n} + (K+1)2n\beta \exp[-\beta(n-1)] $$

thanks to Proposition 26 and Lemma 38. Theorem 18 is then proved. ■
Combining the above inequalities with the under-estimation property (44), one has

$$ \forall s, t \in \{1, \dots, K+1\} : \hat{\epsilon}^2 < r_W^2(\omega_{U(i_s)}, \omega_{U(i_t)}) + t_n $$

with probability at least $1 - 2/n$. Replacing the radius $\hat{\epsilon}^2$ by its value $\epsilon^2 + t_n$, it comes

$$ \forall s, t \in \{1, \dots, K+1\} : \epsilon^2 < r_W^2(\omega_{U(i_s)}, \omega_{U(i_t)}). $$

Thus, $K+1$ sampled points are separated by at least a distance $\epsilon$, which implies $N_{\Omega}^{(p)}(\epsilon) \ge K+1$. This contradicts the null-hypothesis. ■

Corollary 17 and Theorem 16 are therefore proved.

### G.2.2 PROOF FOR THE TYPE II ERROR (THEOREM 18).

Consider a graphon $(\Omega, \mu, W)$ in the set $W(\eta, \beta)$. By definition of $W(\eta, \beta)$, there are $K+1$ balls in $(\Omega, r_W)$ whose centers are separated by at least a distance $\sqrt{\epsilon^2 + 10\eta + 6t_n} + \eta$. Label these balls by $s \in \{1, \dots, K+1\}$. As in the proof for the dimension estimation, assume the complementary of the event $\mathcal{E}_{bad}$, i.e. assume that each of the $K+1$ balls contains at least two sampled points. Accordingly, denote by $i_1, j_1, \dots, i_{K+1}, j_{K+1}$ the indices of the corresponding sampled points such that $\omega_{i_s}, \omega_{j_s}$ belong to the $s^{th}$ ball with $s \in \{1, \dots, K+1\}$. Since the radius of these ball is smaller than $\eta/2$, one has

$$ r_W(\omega_{i_s}, \omega_{m(i_s)}) \le r_W(\omega_{i_s}, \omega_{j_s}) \le \eta \quad (49) $$

for all $s \in \{1, \dots, K+1\}$.

On the event $\mathcal{E}_{in}$ of Proposition 26, Lemma 42 gives

$$ \hat{r}_{new}^2(i_s, i_t) \ge r_W^2(\omega_{i_s}, \omega_{i_t}) - 5r_W(\omega_{i_s}, \omega_{m(i_s)}) - 5r_W(\omega_{j_s}, \omega_{m(j_s)}) - 5t_n. $$

for all $s \neq t \in \{1, \dots, K+1\}$. Using (49), one derive

$$ \hat{r}_{new}^2(i_s, i_t) \ge r_W^2(\omega_{i_s}, \omega_{i_t}) - 10\eta - 5t_n. \quad (50) $$

The ball centers are separated by at least a distance $\sqrt{\epsilon^2 + 10\eta + 6t_n} + \eta$ by assumption, which implies that the points in these balls are separated by

$$ r_W(\omega_{i_s}, \omega_{i_t}) > \sqrt{\epsilon^2 + 10\eta + 6t_n} $$

for all $s \neq t \in \{1, \dots, K+1\}$, since the ball radii are all smaller than $\eta/2$. Combining this inequality with the line (50), one obtain

$$ \hat{r}_{new}^2(i_s, i_t) > \epsilon^2 + t_n $$

for all $s \neq t \in \{1, \dots, K+1\}$. Since $\hat{\epsilon} = \sqrt{\epsilon^2 + t_n}$, this gives $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon}) \ge K+1$. Thus, the alternative hypothesis is confirmed correctly.

The above displays hold on the event $\mathcal{E}_{in} \cap \mathcal{E}_{bad}^c$. Let us upper bound the probability of the complementary event. The union bound gives

$$ \mathbb{P}(\mathcal{E}_{in}^c \cup \mathcal{E}_{bad}) \le \frac{2}{n} + (K+1)2n\beta \exp[-\beta(n-1)] $$

thanks to Proposition 26 and Lemma 38. Theorem 18 is then proved. ■
### G.2.3 PROOF FOR THE IMPROVEMENT OF THE TYPE II ERROR (THEOREM 21).

We have seen that the type II error is upper bounded by the probability of the event $\mathcal{E}_{in}^c \cap \mathcal{E}_{bad}$. Here the only difference is that $\mathcal{E}_{bad}$ refers to the new event where, for each of the $M$ collections of $K + 1 + K'$ balls, at least $K' + 1$ balls contain strictly less than two sampled points. For clarity, label these collections by $\{1, \dots, M\}$, and denote by $\mathcal{C}_j$ the event where at least $K' + 1$ balls of the $j$th collection contain strictly less than two sampled points. Then, we have

$$ \mathbb{P}[\mathcal{E}_{bad}] = \mathbb{P}[\mathcal{C}_1 \cap \dots \cap \mathcal{C}_M] $$

where $\mathbb{P}$ denote the probability distribution $\mathbb{P}_{(\Omega, \mu, W)}$ of the W-random graph. The above display is equal to

$$ \mathbb{P}[\mathcal{C}_1] \times \mathbb{P}[\mathcal{C}_2|\mathcal{C}_1] \times \dots \times \mathbb{P}[\mathcal{C}_M|\mathcal{C}_1, \dots, \mathcal{C}_{M-1}] $$

which is upper bounded by

$$ \mathbb{P}[\mathcal{C}_1] \times \mathbb{P}[\mathcal{C}_2] \times \dots \times \mathbb{P}[\mathcal{C}_M] $$

since the events $\mathcal{C}_1, \dots, \mathcal{C}_M$ are negatively associated (it is shown at the end of the proof). Finally, we have

$$ \mathbb{P}[\mathcal{E}_{bad}] \leq \mathbb{P}[\mathcal{C}_1]^M. \qquad (51) $$

Given the first collection of $K + 1 + K'$ balls, denote by $\mathcal{E}_j$ the event where the $j$th ball of the collection contains strictly less than two sampled points. By definition of the event $\mathcal{C}_1$, we have

$$ \mathbb{P}[\mathcal{C}_1] = \mathbb{P}[\exists i_1, \dots, i_{K'+1} \in \{1, \dots, K+1+K'\} : \mathcal{E}_{i_1} \cap \dots \cap \mathcal{E}_{i_{K'+1}}]. $$

The union bound gives

$$ \mathbb{P}[\mathcal{C}_1] \leq \sum_{i_1, \dots, i_{K'+1}} \mathbb{P}[\mathcal{E}_{i_1} \cap \dots \cap \mathcal{E}_{i_{K'+1}}] $$

where the sum is taken over all possible $K' + 1$ different indices. The above upper bound is equal to

$$ \sum_{i_1, \dots, i_{K'+1}} \mathbb{P}[\mathcal{E}_{i_1}] \times \mathbb{P}[\mathcal{E}_{i_2}|\mathcal{E}_{i_1}] \times \dots \times \mathbb{P}[\mathcal{E}_{i_{K'+1}}|\mathcal{E}_{i_1}, \dots, \mathcal{E}_{i_{K'}}]. $$

which is smaller than

$$ \sum_{i_1, \dots, i_{K'+1}} \mathbb{P}[\mathcal{E}_{i_1}] \times \dots \times \mathbb{P}[\mathcal{E}_{i_{K'+1}}] \qquad (52) $$

by negative association of the events $\mathcal{E}_k$ (this fact is proved at the end). Finally, Lemma 38 ensures that

$$ \mathbb{P}[\mathcal{E}_k] \leq 2\beta n \exp[-\beta(n-1)] $$

for all $k$, which allows to upper bound (52) and have

$$ \mathbb{P}[\mathcal{C}_1] \leq \binom{K+K'+1}{K'+1} (2\beta n \exp[-\beta(n-1)])^{(K'+1)}. \qquad (53) $$
### G.2.3 PROOF FOR THE IMPROVEMENT OF THE TYPE II ERROR (THEOREM 21).

We have seen that the type II error is upper bounded by the probability of the event $\mathcal{E}_{in}^c \cap \mathcal{E}_{bad}$. Here the only difference is that $\mathcal{E}_{bad}$ refers to the new event where, for each of the $M$ collections of $K+1+K'$ balls, at least $K'+1$ balls contain strictly less than two sampled points. For clarity, label these collections by $\{1, \dots, M\}$, and denote by $C_j$ the event where at least $K'+1$ balls of the $j$th collection contain strictly less than two sampled points. Then, we have

$$ \mathbb{P}[\mathcal{E}_{bad}] = \mathbb{P}[C_1 \cap \dots \cap C_M] $$

where $\mathbb{P}$ denote the probability distribution $P_{(\Omega, \mu, W)}$ of the W-random graph. The above display is equal to

$$ \mathbb{P}[C_1] \times \mathbb{P}[C_2|C_1] \times \dots \times \mathbb{P}[C_M|C_1, \dots, C_{M-1}] $$

which is upper bounded by

$$ \mathbb{P}[C_1] \times \mathbb{P}[C_2] \times \dots \times \mathbb{P}[C_M] $$

since the events $C_1, \dots, C_M$ are negatively associated (it is shown at the end of the proof). Finally, we have

$$ \mathbb{P}[\mathcal{E}_{bad}] \le \mathbb{P}[C_1]^M. \qquad (51) $$

Given the first collection of $K+1+K'$ balls, denote by $\mathcal{E}_j$ the event where the $j$th ball of the collection contains strictly less than two sampled points. By definition of the event $C_1$, we have

$$ \mathbb{P}[C_1] = \mathbb{P}[\exists i_1, \dots, i_{K'+1} \in \{1, \dots, K+1+K'\} : \mathcal{E}_{i_1} \cap \dots \cap \mathcal{E}_{i_{K'+1}}]. $$

The union bound gives

$$ \mathbb{P}[C_1] \le \sum_{i_1, \dots, i_{K'+1}} \mathbb{P}[\mathcal{E}_{i_1} \cap \dots \cap \mathcal{E}_{i_{K'+1}}] $$

where the sum is taken over all possible $K'+1$ different indices. The above upper bound is equal to

$$ \sum_{i_1, \dots, i_{K'+1}} \mathbb{P}[\mathcal{E}_{i_1}] \times \mathbb{P}[\mathcal{E}_{i_2}|\mathcal{E}_{i_1}] \times \dots \times \mathbb{P}[\mathcal{E}_{i_{K'+1}}|\mathcal{E}_{i_1}, \dots, \mathcal{E}_{i_{K'}}]. $$

which is smaller than

$$ \sum_{i_1, \dots, i_{K'+1}} \mathbb{P}[\mathcal{E}_{i_1}] \times \dots \times \mathbb{P}[\mathcal{E}_{i_{K'+1}}] \qquad (52) $$

by negative association of the events $\mathcal{E}_k$ (this fact is proved at the end). Finally, Lemma 38 ensures that

$$ \mathbb{P}[\mathcal{E}_k] \le 2\beta n \exp[-\beta(n-1)] $$

for all $k$, which allows to upper bound (52) and have

$$ \mathbb{P}[C_1] \le \binom{K+K'+1}{K'+1} (2\beta n \exp[-\beta(n-1)])^{(K'+1)}. \qquad (53) $$
Thus, setting $\tilde{p}_n = \mathbb{P}[C_1]$, we deduce from (51) that

$$ \mathbb{P}(\mathcal{E}_{in}^c \cup \mathcal{E}_{bad}) \leq \mathbb{P}(\mathcal{E}_{in}^c) + \mathbb{P}(\mathcal{E}_{bad}) \leq \frac{2}{n} + \tilde{p}_n^M, $$

where $\tilde{p}_n$ is upper bounded by (53).

It remains to show the negative association that we use in the above proof. Given the first collection of $K+1+K'$ balls, let us show that the corresponding events $\mathcal{E}_1, \dots, \mathcal{E}_{K+1+K'}$ are negatively associated. For the $n$ sampled points $\omega_1, \dots, \omega_n$, define $n_j$ the number of points in the $j$th ball of the collection. Theorem 13 of Dubhashi and Ranjan (1998) ensures that the variables $n_1, \dots, n_{K+1+K'}$ are negatively associated. Define the non-increasing function $h(n_j) = \mathbb{I}_{\mathcal{E}_j}$ where $\mathbb{I}_{\mathcal{E}_j}$ is the indicator function of $\mathcal{E}_j$. The second point of Proposition 7 of Dubhashi and Ranjan (1998) shows that $h(n_1), \dots, h(n_{K+1+K'})$ are negatively associated. This means that the events $\mathcal{E}_1, \dots, \mathcal{E}_{K+1+K'}$ are negatively associated.

Similarly, we show the negative association of the events $C_1, \dots, C_M$. Consider $n_j^t$ the number of sampled points in the $j$th ball of the $t$th collection. These variables are negatively associated according to Theorem 13 of Dubhashi and Ranjan (1998). Define the non-increasing functions $h_t(n_1^t, \dots, n_{K+1+K'}^t) = \mathbb{I}_{C_j}$ for all $t \leq M$. Then, Proposition 7 of Dubhashi and Ranjan (1998) shows that $\mathbb{I}_{C_1}, \dots, \mathbb{I}_{C_M}$ are negatively associated.

Theorem 21 is proved. ■

## References

* Emmanuel Abbe. Community detection and stochastic block models: recent developments. arXiv preprint arXiv:1703.10146, 2017.

* David J Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4):581–598, 1981.

* Ery Arias-Castro, Antoine Channarond, Bruno Pelletier, and Nicolas Verzelen. On the estimation of latent distances using graph distances. arXiv preprint arXiv:1804.10611, 2018.

* Avanti Athreya, Donniell E Fishkind, Minh Tang, Carey E Priebe, Youngser Park, Joshua T Vogelstein, Keith Levin, Vince Lyzinski, and Yichen Qin. Statistical inference on random dot product graphs: a survey. The Journal of Machine Learning Research, 18(1):8393–8484, 2017.

* Peter J. Bickel and Aiyou Chen. A nonparametric view of network models and new-man-girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068–21073, 2009.

* Peter J Bickel, Aiyou Chen, Elizaveta Levina, et al. The method of moments and degree distributions for network models. The Annals of Statistics, 39(5):2280–2301, 2011.

* Béla Bollobás. Random graphs. In Modern graph theory, pages 215–252. Springer, 1998.
Thus, setting $\tilde{p}_n = \mathbb{P}[C_1]$, we deduce from (51) that

$$ \mathbb{P}(\mathcal{E}_{in}^c \cup \mathcal{E}_{bad}) \leq \mathbb{P}(\mathcal{E}_{in}^c) + \mathbb{P}(\mathcal{E}_{bad}) \leq \frac{2}{n} + \tilde{p}_n^M, $$

where $\tilde{p}_n$ is upper bounded by (53).

It remains to show the negative association that we use in the above proof. Given the first collection of $K+1+K'$ balls, let us show that the corresponding events $\mathcal{E}_1, \dots, \mathcal{E}_{K+1+K'}$ are negatively associated. For the $n$ sampled points $\omega_1, \dots, \omega_n$, define $n_j$ the number of points in the $j$th ball of the collection. Theorem 13 of Dubhashi and Ranjan (1998) ensures that the variables $n_1, \dots, n_{K+1+K'}$ are negatively associated. Define the non-increasing function $h(n_j) = \mathbb{I}_{\mathcal{E}_j}$ where $\mathbb{I}_{\mathcal{E}_j}$ is the indicator function of $\mathcal{E}_j$. The second point of Proposition 7 of Dubhashi and Ranjan (1998) shows that $h(n_1), \dots, h(n_{K+1+K'})$ are negatively associated. This means that the events $\mathcal{E}_1, \dots, \mathcal{E}_{K+1+K'}$ are negatively associated.

Similarly, we show the negative association of the events $C_1, \dots, C_M$. Consider $n_j^t$ the number of sampled points in the $j$th ball of the $t$th collection. These variables are negatively associated according to Theorem 13 of Dubhashi and Ranjan (1998). Define the non-increasing functions $h_t(n_1^t, \dots, n_{K+1+K'}^t) = \mathbb{I}_{C_j}$ for all $t \leq M$. Then, Proposition 7 of Dubhashi and Ranjan (1998) shows that $\mathbb{I}_{C_1}, \dots, \mathbb{I}_{C_M}$ are negatively associated.

Theorem 21 is proved. ■

## References

* Emmanuel Abbe. Community detection and stochastic block models: recent developments. arXiv preprint arXiv:1703.10146, 2017.

* David J Aldous. Representations for partially exchangeable arrays of random variables. Journal of Multivariate Analysis, 11(4):581–598, 1981.

* Ery Arias-Castro, Antoine Channarond, Bruno Pelletier, and Nicolas Verzelen. On the estimation of latent distances using graph distances. arXiv preprint arXiv:1804.10611, 2018.

* Avanti Athreya, Donniell E Fishkind, Minh Tang, Carey E Priebe, Youngser Park, Joshua T Vogelstein, Keith Levin, Vince Lyzinski, and Yichen Qin. Statistical inference on random dot product graphs: a survey. The Journal of Machine Learning Research, 18(1):8393–8484, 2017.

* Peter J. Bickel and Aiyou Chen. A nonparametric view of network models and new-man-girvan and other modularities. Proceedings of the National Academy of Sciences, 106(50):21068–21073, 2009.

* Peter J Bickel, Aiyou Chen, Elizaveta Levina, et al. The method of moments and degree distributions for network models. The Annals of Statistics, 39(5):2280–2301, 2011.

* Béla Bollobás. Random graphs. In Modern graph theory, pages 215–252. Springer, 1998.
Danail Bonchev and Gregory A Buck. Quantitative measures of network complexity. In *Complexity in chemistry, biology, and ecology*, pages 191–235. Springer, 2005.

Christian Borgs, Jennifer Chayes, and Adam Smith. Private graphon estimation for sparse graphs. In *Advances in Neural Information Processing Systems*, pages 1369–1377, 2015.

Christian Borgs, Jennifer Chayes, Devavrat Shah, and Christina Lee Yu. Iterative collaborative filtering for sparse matrix estimation. *arXiv preprint arXiv:1712.00710*, 2017.

Sébastien Bubeck, Jian Ding, Ronen Eldan, and Miklós Z Rácz. Testing for high-dimensional geometry in random graphs. *Random Structures & Algorithms*, 49(3):503–532, 2016.

V. Chvatal. A greedy heuristic for the set-covering problem. *Mathematics of Operations Research*, 4(3):233–235, 1979.

Jens Christian Claussen. Offdiagonal complexity: A computationally quick complexity measure for graphs and networks. *Physica A: Statistical Mechanics and its Applications*, 375(1):365–373, 2007.

Gregory M Constantine. Graph complexity and the laplacian matrix in blocked experiments. *Linear and Multilinear Algebra*, 28(1-2):49–56, 1990.

Yohann De Castro, Claire Lacour, and Thanh Mai Pham Ngoc. Minimax adaptive estimation of nonparametric geometric graphs. *arXiv preprint arXiv:1708.02107*, 2017.

Matthias Dehmer and Abbe Mowshowitz. A history of graph entropy measures. *Information Sciences*, 181(1):57–78, 2011.

Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. *arXiv preprint arXiv:0712.2749*, 2007.

DLMF. *NIST Digital Library of Mathematical Functions*. http://dlmf.nist.gov/, Release 1.0.23 of 2019-06-15. URL http://dlmf.nist.gov/. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller and B. V. Saunders, eds.

Devdatt Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. *Random Structures & Algorithms*, 13(2):99–124, 1998.

Kenneth J Falconer. *Techniques in fractal geometry*, volume 3.

Chao Gao, Yu Lu, Harrison H Zhou, et al. Rate-optimal graphon estimation. *The Annals of Statistics*, 43(6):2624–2652, 2015.

Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, Edoardo M Airoldi, et al. A survey of statistical network models. *Foundations and Trends® in Machine Learning*, 2(2): 129–233, 2010.

Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In *Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 855–864. ACM, 2016.
Danail Bonchev and Gregory A Buck. Quantitative measures of network complexity. In *Complexity in chemistry, biology, and ecology*, pages 191–235. Springer, 2005.

Christian Borgs, Jennifer Chayes, and Adam Smith. Private graphon estimation for sparse graphs. In *Advances in Neural Information Processing Systems*, pages 1369–1377, 2015.

Christian Borgs, Jennifer Chayes, Devavrat Shah, and Christina Lee Yu. Iterative collaborative filtering for sparse matrix estimation. *arXiv preprint arXiv:1712.00710*, 2017.

Sébastien Bubeck, Jian Ding, Ronen Eldan, and Miklós Z Rácz. Testing for high-dimensional geometry in random graphs. *Random Structures & Algorithms*, 49(3):503–532, 2016.

V. Chvatal. A greedy heuristic for the set-covering problem. *Mathematics of Operations Research*, 4(3):233–235, 1979.

Jens Christian Claussen. Offdiagonal complexity: A computationally quick complexity measure for graphs and networks. *Physica A: Statistical Mechanics and its Applications*, 375(1):365–373, 2007.

Gregory M Constantine. Graph complexity and the laplacian matrix in blocked experiments. *Linear and Multilinear Algebra*, 28(1-2):49–56, 1990.

Yohann De Castro, Claire Lacour, and Thanh Mai Pham Ngoc. Minimax adaptive estimation of nonparametric geometric graphs. *arXiv preprint arXiv:1708.02107*, 2017.

Matthias Dehmer and Abbe Mowshowitz. A history of graph entropy measures. *Information Sciences*, 181(1):57–78, 2011.

Persi Diaconis and Svante Janson. Graph limits and exchangeable random graphs. *arXiv preprint arXiv:0712.2749*, 2007.

DLMF. *NIST Digital Library of Mathematical Functions*. http://dlmf.nist.gov/, Release 1.0.23 of 2019-06-15. URL http://dlmf.nist.gov/. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller and B. V. Saunders, eds.

Devdatt Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. *Random Structures & Algorithms*, 13(2):99–124, 1998.

Kenneth J Falconer. *Techniques in fractal geometry*, volume 3.

Chao Gao, Yu Lu, Harrison H Zhou, et al. Rate-optimal graphon estimation. *The Annals of Statistics*, 43(6):2624–2652, 2015.

Anna Goldenberg, Alice X Zheng, Stephen E Fienberg, Edoardo M Airoldi, et al. A survey of statistical network models. *Foundations and Trends® in Machine Learning*, 2(2): 129–233, 2010.

Aditya Grover and Jure Leskovec. *node2vec: Scalable feature learning for networks*. In *Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 855–864. ACM, 2016.
Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460):1090–1098, 2002.

Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109–137, 1983.

Olav Kallenberg. On the representation theorem for exchangeable arrays. Journal of Multivariate Analysis, 30(1):137–154, 1989.

Balázs Kégl. Intrinsic dimension estimation using packing numbers. In Advances in neural information processing systems, pages 697–704, 2003.

Jisu Kim, Alessandro Rinaldo, and Larry Wasserman. Minimax rates for estimating the dimension of a manifold. arXiv preprint arXiv:1605.01011, 2016.

Olga Klopp, Alexandre B Tsybakov, Nicolas Verzelen, et al. Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics, 45(1):316–354, 2017.

Vladimir I Koltchinskii. Empirical geometry of multivariate data: a deconvolution approach. Annals of statistics, pages 591–629, 2000.

Pierre Latouche and Stéphane Robin. Variational bayes model averaging for graphon functions and motif frequencies inference in w-graph models. Statistics and Computing, 26 (6):1173–1185, 2016.

Antti M Latva-Koivisto. Finding a complexity measure for business process models.

Guillaume Lecué, Shahar Mendelson, et al. Regularization and the small-ball method i: sparse recovery. The Annals of Statistics, 46(2):611–641, 2018.

Elizaveta Levina and Peter J Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems, pages 777–784, 2005.

Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics and Statistics, 4(1):66–70, 2011.

Yihua Li, Devavrat Shah, Dogyoon Song, and Christina Lee Yu. Nearest neighbors for matrix estimation interpreted as blind regression for latent variable model. IEEE Transactions on Information Theory, 66(3):1760–1784, 2019.

László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.

László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006.

Catherine Matias and Stéphane Robin. Modeling heterogeneity in random graphs through latent space models: a selective review. ESAIM: Proceedings and Surveys, 47:55–74, 2014.
Peter D Hoff, Adrian E Raftery, and Mark S Handcock. Latent space approaches to social network analysis. Journal of the american Statistical association, 97(460):1090–1098, 2002.

Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social networks, 5(2):109–137, 1983.

Olav Kallenberg. On the representation theorem for exchangeable arrays. Journal of Multivariate Analysis, 30(1):137–154, 1989.

Balázs Kégl. Intrinsic dimension estimation using packing numbers. In Advances in neural information processing systems, pages 697–704, 2003.

Jisu Kim, Alessandro Rinaldo, and Larry Wasserman. Minimax rates for estimating the dimension of a manifold. arXiv preprint arXiv:1605.01011, 2016.

Olga Klopp, Alexandre B Tsybakov, Nicolas Verzelen, et al. Oracle inequalities for network models and sparse graphon estimation. The Annals of Statistics, 45(1):316–354, 2017.

Vladimir I Koltchinskii. Empirical geometry of multivariate data: a deconvolution approach. Annals of statistics, pages 591–629, 2000.

Pierre Latouche and Stéphane Robin. Variational bayes model averaging for graphon functions and motif frequencies inference in w-graph models. Statistics and Computing, 26 (6):1173–1185, 2016.

Antti M Latva-Koivisto. Finding a complexity measure for business process models.

Guillaume Lecué, Shahar Mendelson, et al. Regularization and the small-ball method i: sparse recovery. The Annals of Statistics, 46(2):611–641, 2018.

Elizaveta Levina and Peter J Bickel. Maximum likelihood estimation of intrinsic dimension. In Advances in neural information processing systems, pages 777–784, 2005.

Shengqiao Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathematics and Statistics, 4(1):66–70, 2011.

Yihua Li, Devavrat Shah, Dogyoon Song, and Christina Lee Yu. Nearest neighbors for matrix estimation interpreted as blind regression for latent variable model. IEEE Transactions on Information Theory, 66(3):1760–1784, 2019.

László Lovász. Large networks and graph limits, volume 60. American Mathematical Soc., 2012.

László Lovász and Balázs Szegedy. Limits of dense graph sequences. Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006.

Catherine Matias and Stéphane Robin. Modeling heterogeneity in random graphs through latent space models: a selective review. ESAIM: Proceedings and Surveys, 47:55–74, 2014.
Shahar Mendelson. Learning without concentration. In *Conference on Learning Theory*, pages 25–39, 2014.

Mikołaj Morzy, Tomasz Kajdanowicz, and Przemysław Kazienko. On measuring the complexity of networks: Kolmogorov complexity versus entropy. *Complexity*, 2017, 2017.

Mathew Penrose et al. *Random geometric graphs*. Number 5. Oxford university press, 2003.

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In *Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 701–710. ACM, 2014.

Miklós Z Rácz, Sébastien Bubeck, et al. Basic models and questions in statistical network analysis. *Statistics Surveys*, 11:1–47, 2017.

Purnamrita Sarkar, Deepayan Chakrabarti, and Andrew W Moore. Theoretical justification of popular link prediction heuristics. In *Twenty-Second International Joint Conference on Artificial Intelligence*, 2011.

Karthik Sridharan. A gentle introduction to concentration inequalities. *Dept Comput Sci*, 2002.

Minh Tang, Daniel L Sussman, Carey E Priebe, et al. Universally consistent vertex classification for latent positions graphs. *The Annals of Statistics*, 41(3):1406–1430, 2013.

Alexandre B Tsybakov. *Introduction to nonparametric estimation*. Springer, New York, 2009.

Todd L Veldhuizen. Software libraries and their reuse: Entropy, kolmogorov complexity, and zipf’s law. *arXiv preprint cs/0508023*, 2005.

Patrick J Wolfe and Sofia C Olhede. Nonparametric graphon estimation. *arXiv preprint arXiv:1309.5936*, 2013.

Jiaming Xu, Laurent Massoulié, and Marc Lelarge. Edge label inference in generalized stochastic block models: from spectral theory to impossibility results. In *Conference on Learning Theory*, pages 903–920, 2014.

Bin Yu. Assouad, fano, and le cam. In *Festschrift for Lucien Le Cam*, pages 423–435. Springer, 1997.

Hector Zenil, Narsis Kiani, and Jesper Tegnér. A review of graph and network complexity from an algorithmic information perspective. *Entropy*, 20(8):551, 2018.

Yuan Zhang, Elizaveta Levina, and Ji Zhu. Estimating network edge probabilities by neighborhood smoothing. *arXiv preprint arXiv:1509.08588*, 2015.

Pedro Zufiria and Iker Barriales-Valbuena. Entropy characterization of random network models. *Entropy*, 19(7):321, 2017.
Shahar Mendelson. Learning without concentration. In *Conference on Learning Theory*, pages 25–39, 2014.

Mikołaj Morzy, Tomasz Kajdanowicz, and Przemysław Kazienko. On measuring the complexity of networks: Kolmogorov complexity versus entropy. *Complexity*, 2017, 2017.

Mathew Penrose et al. *Random geometric graphs*. Number 5. Oxford university press, 2003.

Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representations. In *Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining*, pages 701–710. ACM, 2014.

Miklós Z Rácz, Sébastien Bubeck, et al. Basic models and questions in statistical network analysis. *Statistics Surveys*, 11:1–47, 2017.

Purnamrita Sarkar, Deepayan Chakrabarti, and Andrew W Moore. Theoretical justification of popular link prediction heuristics. In *Twenty-Second International Joint Conference on Artificial Intelligence*, 2011.

Karthik Sridharan. A gentle introduction to concentration inequalities. *Dept Comput Sci*, 2002.

Minh Tang, Daniel L Sussman, Carey E Priebe, et al. Universally consistent vertex classification for latent positions graphs. *The Annals of Statistics*, 41(3):1406–1430, 2013.

Alexandre B Tsybakov. *Introduction to nonparametric estimation*. Springer, New York, 2009.

Todd L Veldhuizen. Software libraries and their reuse: Entropy, kolmogorov complexity, and zipf’s law. *arXiv preprint cs/0508023*, 2005.

Patrick J Wolfe and Sofia C Olhede. Nonparametric graphon estimation. *arXiv preprint arXiv:1309.5936*, 2013.

Jiaming Xu, Laurent Massoulié, and Marc Lelarge. Edge label inference in generalized stochastic block models: from spectral theory to impossibility results. In *Conference on Learning Theory*, pages 903–920, 2014.

Bin Yu. Assouad, fano, and le cam. In *Festschrift for Lucien Le Cam*, pages 423–435. Springer, 1997.

Hector Zenil, Narsis Kiani, and Jesper Tegnér. A review of graph and network complexity from an algorithmic information perspective. *Entropy*, 20(8):551, 2018.

Yuan Zhang, Elizaveta Levina, and Ji Zhu. Estimating network edge probabilities by neighborhood smoothing. *arXiv preprint arXiv:1509.08588*, 2015.

Pedro Zufiria and Iker Barriales-Valbuena. Entropy characterization of random network models. *Entropy*, 19(7):321, 2017.