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

HAL
open science

# On the Estimation of Network Complexity: Dimension of Graphons

Yann Issartel

► To cite this version:

Yann Issartel. On the Estimation of Network Complexity: Dimension of Graphons. Journal of Machine Learning Research, 2021, 10.48550/arXiv.1909.02900. [https://doi.org/10.48550/arXiv.1909.02900]

HAL Id: hal-02413537

https://hal.science/hal-02413537

Submitted on 29 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
<figure><img src="image_1.png" /></figure>

HAL
open science

# On the Estimation of Network Complexity: Dimension of Graphons

Yann Issartel

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

## To cite this version:

Yann Issartel. On the Estimation of Network Complexity: Dimension of Graphons. Journal of Machine Learning Research, 2021, 10.48550/arXiv.1909.02900. [hal-02413537]

HAL Id: hal-02413537

https://hal.science/hal-02413537v1

Submitted on 29 May 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# On the Estimation of Network Complexity:
Dimension of Graphons

**Yann Issartel**

YANN.ISSARTEL@ENSAE.FR

Université Paris-Saclay, Laboratoire de Mathématiques d'Orsay,
91405 Orsay, France.

CREST, Ensae, Institut Polytechnique de Paris, 91120 Palaiseau, France.

**Editor:** Edo Airoldi

## Abstract

Network complexity has been studied for over half a century and has found a wide range of applications. Many methods have been developed to characterize and estimate the complexity of networks. However, there has been little research with statistical guarantees. In this paper, we develop a statistical theory of graph complexity in a general model of random graphs, the so-called graphon model.

Given a graphon, we endow the latent space of the nodes with the neighborhood distance. Our complexity index is then based on the covering number and the Minkowski dimension of this metric space. Although the latent space is not identifiable, these indices turn out to be identifiable. This notion of complexity has simple interpretations on popular examples: it matches the number of communities in stochastic block models; the dimension of the Euclidean space in random geometric graphs; the regularity of the link function in Hölder graphons.

From a single observation of the graph, we construct an estimator of the neighborhood-distance and show universal non-asymptotic bounds for its risk, matching minimax lower bounds. Based on this estimated distance, we compute the corresponding covering number and Minkowski dimension and we provide optimal non-asymptotic error bounds for these two plug-in estimators.

**Keywords:** random graph model, graphon, neighborhood distance, covering number, Minkowski dimension

## 1. Introduction

Networks appear in many areas where data is a collection of objects interacting with each other. Examples include numerous phenomena in the fields of physics, biology, neuroscience and social sciences. A major issue is to extract information from these data repositories. This exciting challenge has led researchers to seek characterizations of networks, among which their complexity has received a lot of attention for more than half a century. See (Dehmer and Mowshowitz, 2011; Zenil et al., 2018) for two recent reviews. Indeed, network complexity is a key feature used in various applications, for example, to quantify the complexity of chemical structures (Bonchev and Buck, 2005), to describe business processes (Latva-Koivisto), to characterize software libraries (Veldhuizen, 2005), and to study general graphs (Constantine, 1990).
# On the Estimation of Network Complexity:
Dimension of Graphons

**Yann Issartel**

YANN.ISSARTEL@ENSAE.FR

Université Paris-Saclay, Laboratoire de Mathématiques d'Orsay,
91405 Orsay, France.

CREST, Ensae, Institut Polytechnique de Paris, 91120 Palaiseau, France.

**Editor:** Edo Airoldi

## Abstract

Network complexity has been studied for over half a century and has found a wide range of applications. Many methods have been developed to characterize and estimate the complexity of networks. However, there has been little research with statistical guarantees. In this paper, we develop a statistical theory of graph complexity in a general model of random graphs, the so-called graphon model.

Given a graphon, we endow the latent space of the nodes with the neighborhood distance. Our complexity index is then based on the covering number and the Minkowski dimension of this metric space. Although the latent space is not identifiable, these indices turn out to be identifiable. This notion of complexity has simple interpretations on popular examples: it matches the number of communities in stochastic block models; the dimension of the Euclidean space in random geometric graphs; the regularity of the link function in Hölder graphons.

From a single observation of the graph, we construct an estimator of the neighborhood-distance and show universal non-asymptotic bounds for its risk, matching minimax lower bounds. Based on this estimated distance, we compute the corresponding covering number and Minkowski dimension and we provide optimal non-asymptotic error bounds for these two plug-in estimators.

**Keywords:** random graph model, graphon, neighborhood distance, covering number, Minkowski dimension

## 1. Introduction

Networks appear in many areas where data is a collection of objects interacting with each other. Examples include numerous phenomena in the fields of physics, biology, neuroscience and social sciences. A major issue is to extract information from these data repositories. This exciting challenge has led researchers to seek characterizations of networks, among which their complexity has received a lot of attention for more than half a century. See (Dehmer and Mowshowitz, 2011; Zenil et al., 2018) for two recent reviews. Indeed, network complexity is a key feature used in various applications, for example, to quantify the complexity of chemical structures (Bonchev and Buck, 2005), to describe business processes (Latva-Koivisto), to characterize software libraries (Veldhuizen, 2005), and to study general graphs (Constantine, 1990).
The definition and estimation of network complexity is an active line of research (Morzy et al., 2017; Zufiria and Barriales-Valbuena, 2017; Claussen, 2007). However, there appear to be little (or no) mathematical results on the statistical side of the problem. In this paper, we develop a statistical theory of graph complexity in a universal model of random graphs. To the best of our knowledge, it is the first contribution on complexity estimation with statistical guarantees.

## 1.1 Modeling Assumption

Statistical inference on random graphs is a fast-growing area of research (Matias and Robin, 2014; Rácz et al., 2017; Abbe, 2017) and has found a wide range of applications (Goldenberg et al., 2010; Sarkar et al., 2011). Usually, it assumes there exists an unknown feature in the underlying model and the goal is to recover this feature from a single realization of the random graph.

Here, we follow this direction with the *W-random graph model* (also known as graphon model). This general model falls into the category of non-parametric descriptions of networks (Bickel and Chen, 2009) and satisfies some forms of universality (Diaconis and Janson, 2007). See section 1.3 for details. In this paper, we define a notion of complexity for this model and then consider the problem of inferring this complexity from a single graph observation.

W-random graphs allow to model many real-world networks, such as social networks where nodes represent different people and edges people's friendships. In this example, one may expect that the friendship probability $p_{ij}$ between individual $i$ and $j$ depends on their personal attributes (like jobs, ages, leisure). To model such mechanism, one may assume the observed graph is generated according to the W-random graph model, i.e. (1) for each node $i$ of the network, an attribute $\omega_i$ is drawn from a distribution $\mu$ on a space $\Omega$ (where $\Omega$ can be seen as the social space of all possible individual features: jobs, ages,...); (2) two people are friends, independently of the others, with probability $p_{ij} = W(\omega_i, \omega_j)$, where $W: \Omega \times \Omega \rightarrow [0, 1]$ is a symmetric function. Thus, a W-random graph is specified by the triplet of parameters $(\Omega, \mu, W)$, often called *graphon* in the literature (Lovász, 2012).

Such modeling falls into the popular “latent space approach” (Hoff et al., 2002). Indeed, the personal attributes may not be observed in practice and accordingly, the W-random graph model assumes that the $\omega_i$ and $\Omega$ are latent (unobserved). In fact, all parameters of the graphon $(\Omega, \mu, W)$ are unknown, and the only observation is the edges of the graph, i.e. the adjacency matrix $A$ where $A_{ij} = 1$ stands for the presence of an edge between the $i^{th}$ and $j^{th}$ nodes, and $A_{ij} = 0$ otherwise. See Section 2 for a formal presentation of this model.

## 1.2 Contribution

### 1.2.1 COMPLEXITY INDEX

Our first objective is the definition of a complexity index in the W-random graph model. As a natural candidate, one might think of the dimension of the latent space, like $d$ if $\Omega = [0, 1]^d$. However, this index is inadequate because of a major identifiability issue. Indeed, it is known that (see Lovász, 2012) the attribute space $\Omega$ is not identifiable from the observed adjacency matrix $A$. Even worse, it has been shown that all W-random graph distributions can be
The definition and estimation of network complexity is an active line of research (Morzy et al., 2017; Zufiria and Barriales-Valbuena, 2017; Claussen, 2007). However, there appear to be little (or no) mathematical results on the statistical side of the problem. In this paper, we develop a statistical theory of graph complexity in a universal model of random graphs. To the best of our knowledge, it is the first contribution on complexity estimation with statistical guarantees.

## 1.1 Modeling Assumption

Statistical inference on random graphs is a fast-growing area of research (Matias and Robin, 2014; Rácz et al., 2017; Abbe, 2017) and has found a wide range of applications (Goldenberg et al., 2010; Sarkar et al., 2011). Usually, it assumes there exists an unknown feature in the underlying model and the goal is to recover this feature from a single realization of the random graph.

Here, we follow this direction with the *W-random graph model* (also known as graphon model). This general model falls into the category of non-parametric descriptions of networks (Bickel and Chen, 2009) and satisfies some forms of universality (Diaconis and Janson, 2007). See section 1.3 for details. In this paper, we define a notion of complexity for this model and then consider the problem of inferring this complexity from a single graph observation.

W-random graphs allow to model many real-world networks, such as social networks where nodes represent different people and edges people's friendships. In this example, one may expect that the friendship probability $p_{ij}$ between individual $i$ and $j$ depends on their personal attributes (like jobs, ages, leisure). To model such mechanism, one may assume the observed graph is generated according to the W-random graph model, i.e. (1) for each node $i$ of the network, an attribute $\omega_i$ is drawn from a distribution $\mu$ on a space $\Omega$ (where $\Omega$ can be seen as the social space of all possible individual features: jobs, ages,...); (2) two people are friends, independently of the others, with probability $p_{ij} = W(\omega_i, \omega_j)$, where $W: \Omega \times \Omega \rightarrow [0, 1]$ is a symmetric function. Thus, a W-random graph is specified by the triplet of parameters $(\Omega, \mu, W)$, often called *graphon* in the literature (Lovász, 2012).

Such modeling falls into the popular “latent space approach” (Hoff et al., 2002). Indeed, the personal attributes may not be observed in practice and accordingly, the W-random graph model assumes that the $\omega_i$ and $\Omega$ are latent (unobserved). In fact, all parameters of the graphon $(\Omega, \mu, W)$ are unknown, and the only observation is the edges of the graph, i.e. the adjacency matrix $A$ where $A_{ij} = 1$ stands for the presence of an edge between the $i^{th}$ and $j^{th}$ nodes, and $A_{ij} = 0$ otherwise. See Section 2 for a formal presentation of this model.

## 1.2 Contribution

### 1.2.1 COMPLEXITY INDEX

Our first objective is the definition of a complexity index in the W-random graph model. As a natural candidate, one might think of the dimension of the latent space, like $d$ if $\Omega = [0, 1]^d$. However, this index is inadequate because of a major identifiability issue. Indeed, it is known that (see Lovász, 2012) the attribute space $\Omega$ is not identifiable from the observed adjacency matrix $A$. Even worse, it has been shown that all W-random graph distributions can be
represented on the specific space $\Omega = [0, 1]$ (Lovász, 2012). It is therefore pointless to think about the graph complexity purely in terms of the latent space. Likewise, the regularity of the link function (like $\alpha$ if $W$ is $\alpha$-Hölder) is not suited due to the non-identifiability of $W$.

These issues motivate the introduction of a more abstract index. Given a graphon $(\Omega, \mu, W)$, we endow the latent space $\Omega$ with the so-called neighborhood distance

$$r_W(\omega, \omega') = \left( \int_{\Omega} |W(\omega, \omega'') - W(\omega', \omega'')|^2 \mu(d\omega'') \right)^{1/2} . \quad (1)$$

From the above description of a W-random graph, we can see that the quantity $r_W(\omega_i, \omega_j)$ measures the propensity of the nodes $i$ and $j$ to be connected with similar nodes. Our complexity index is then defined as the covering number and the Minkowski dimension of a purified version of the (pseudo-) metric space $(\Omega, r_W)$. The purification process is detailed in section 3.1. Recall the definitions of these two standard measures for metric spaces: the $\epsilon$-covering number $N_{\Omega}^{(c)}(\epsilon)$ is the minimal number of balls of radius $\epsilon$ required to entirely cover the (pseudo-) metric space $(\Omega, r_W)$. And the Minkowski dimension is the following limit on the covering number

$$dim \Omega := \lim_{\epsilon \to 0} \frac{\log N_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} \quad (2)$$

when the limit exists. In particular, the Minkowski dimension does not have to be an integer.

Although none of the three parameters $\Omega, \mu$ and $W$ are identifiable in the W-random graph model, we prove that the covering number and the Minkowski dimension of a purified version of $(\Omega, r_W)$ are identifiable.

We also illustrate that this notion of complexity is sound on classic examples of random graphs. Specifically, we show that $N_{\Omega}^{(c)}(\epsilon)$ is equal to the number of well-spaced communities in the stochastic block model; that $dim \Omega$ matches the dimension of the Euclidean space in some random geometric graphs; and that $dim \Omega$ is equal to the regularity of the link function in some Hölder graphon models. See Section 3.2 for details.

In addition to all applications listed in the introduction, these complexity indices may also be useful to adjust analytical methods to particular networks, for example, when estimating the link function $W$ (see section 1.3 and 3.2 for related comments) or in learning representation where the goal is to find an informative metric space to place/represent the nodes of the network (Hoff et al., 2002; Perozzi et al., 2014; Grover and Leskovec, 2016).

### 1.2.2 STATISTICAL ESTIMATION

From the observed adjacency matrix $A$ of a W-random graph, we estimate the neighborhood distance (1) on the sampled points $\omega_1, \dots, \omega_n$. The corresponding distance estimator $\hat{r}$ is defined in Section 4.1. We show universal non-asymptotic bounds for its risk (Theorem 1). Let $\omega_{m(i)} \in \{\omega_1, \dots, \omega_n\} \setminus \{\omega_i\}$ denote a nearest neighbor of $\omega_i$ with respect to the distance $r_W$.

**Theorem 1** Consider the distance estimator $\hat{r}$, defined in Section 4.1. Then, for any graphon $(\Omega, \mu, W)$, we have
represented on the specific space $\Omega = [0, 1]$ (Lovász, 2012). It is therefore pointless to think about the graph complexity purely in terms of the latent space. Likewise, the regularity of the link function (like $\alpha$ if $W$ is $\alpha$-Hölder) is not suited due to the non-identifiability of $W$.

These issues motivate the introduction of a more abstract index. Given a graphon $(\Omega, \mu, W)$, we endow the latent space $\Omega$ with the so-called neighborhood distance

$$r_W(\omega, \omega') = \left( \int_{\Omega} |W(\omega, \omega'') - W(\omega', \omega'')|^2 \mu(d\omega'') \right)^{1/2} \quad (1)$$

From the above description of a W-random graph, we can see that the quantity $r_W(\omega_i, \omega_j)$ measures the propensity of the nodes $i$ and $j$ to be connected with similar nodes. Our complexity index is then defined as the covering number and the Minkowski dimension of a purified version of the (pseudo-) metric space $(\Omega, r_W)$. The purification process is detailed in section 3.1. Recall the definitions of these two standard measures for metric spaces: the $\epsilon$-covering number $N_{\Omega}^{(c)}(\epsilon)$ is the minimal number of balls of radius $\epsilon$ required to entirely cover the (pseudo-) metric space $(\Omega, r_W)$. And the Minkowski dimension is the following limit on the covering number

$$dim \Omega := \lim_{\epsilon \to 0} \frac{\log N_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} \quad (2)$$

when the limit exists. In particular, the Minkowski dimension does not have to be an integer.

Although none of the three parameters $\Omega, \mu$ and $W$ are identifiable in the W-random graph model, we prove that the covering number and the Minkowski dimension of a purified version of $(\Omega, r_W)$ are identifiable.

We also illustrate that this notion of complexity is sound on classic examples of random graphs. Specifically, we show that $N_{\Omega}^{(c)}(\epsilon)$ is equal to the number of well-spaced communities in the stochastic block model; that $dim \Omega$ matches the dimension of the Euclidean space in some random geometric graphs; and that $dim \Omega$ is equal to the regularity of the link function in some Hölder graphon models. See Section 3.2 for details.

In addition to all applications listed in the introduction, these complexity indices may also be useful to adjust analytical methods to particular networks, for example, when estimating the link function $W$ (see section 1.3 and 3.2 for related comments) or in learning representation where the goal is to find an informative metric space to place/represent the nodes of the network (Hoff et al., 2002; Perozzi et al., 2014; Grover and Leskovec, 2016).

### 1.2.2 STATISTICAL ESTIMATION

From the observed adjacency matrix $A$ of a W-random graph, we estimate the neighborhood distance (1) on the sampled points $\omega_1, \dots, \omega_n$. The corresponding distance estimator $\hat{r}$ is defined in Section 4.1. We show universal non-asymptotic bounds for its risk (Theorem 1). Let $\omega_{m(i)} \in \{\omega_1, \dots, \omega_n\} \setminus \{\omega_i\}$ denote a nearest neighbor of $\omega_i$ with respect to the distance $r_W$.

**Theorem 1** Consider the distance estimator $\hat{r}$, defined in Section 4.1. Then, for any graphon $(\Omega, \mu, W)$, we have
$\forall i, j \in [n],$

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

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

In the upper bound, there is a bias term $r_W(\omega_j, \omega_{m(j)})$ which is the distance between the sampled point $\omega_j$ and its nearest neighbor $\omega_{m(i)}$ (w.r.t. the neighborhood distance). This bias depends on the form of the underlying graphon $(\Omega, \mu, W)$, for example, it is equal to zero w.h.p. in the stochastic block model (i.e., when the link function $W$ is piecewise constant on $\Omega = [0, 1]$). We also derive a minimax lower bound that matches the upper bound of Theorem 1. See Section 4.2 for details on the distance estimation.

Based on the estimated distances $\hat{r}(i, j)$, we estimate the covering number $N_{\Omega}^{(c)}(\epsilon)$ by plug-in and provide universal non-asymptotic error bounds for this estimator. See Section 4.3 for details. Our results on the distance and covering number are therefore valid for all graphons, unlike most results in the graphon literature.

Combining the above covering number estimator $\hat{N}_{\Omega}^{(c)}$ with formula (2), we derive an estimator of the Minkowski dimension

$$\widehat{dim}_D := \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon_D)}{-\log \epsilon_D}$$

which satisfies a high probability convergence rate (Theorem 2). For this result, we assume the Minkowski dimension is upper bounded by some constant $D$ and use a particular radius $\epsilon_D$ defined in Section 4.4. We also make some mild assumptions on the graphon geometry, which are inspired by the problem of estimation of manifold dimension (see section 1.3 for this related literature). Besides, we show that this set of assumptions is minimal, in the sense that, if any of these assumptions is removed, all dimension estimators make an estimation error of the order 1.

**Theorem 2** Under some mild assumptions, defined in Section 4.4, the following holds. If $dim \Omega$ is any real in $[0, D]$, then

$$|\widehat{dim}_D - dim \Omega| \lesssim \frac{1}{\log n}$$

with probability at least $1 - C'/n$ for some constant $C'$ independent of $n$.

Finally, we prove that the upper bound $\log^{-1} n$ is optimal, which means that no estimator can improve on this error. For detailed results, see Section 4.4.

As extensions, we show that the above results also cover the important setting of sparse networks, which has been considered several times in the literature (see Bickel et al., 2011; Wolfe and Olhede, 2013; Klopp et al., 2017; Xu et al., 2014). In addition, we describe a polynomial-time algorithm to approximate the covering number estimator; we do so by using a classic greedy algorithm that is known to satisfy some theoretical guarantees. See Section 6 for these two extensions.

Finally, we test if the packing number (of a purified version of $(\Omega, r_W)$) is smaller than $K$, with a specific care for controlling the type I error probability uniformly over all graphons.
$\forall i, j \in [n],$

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

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

In the upper bound, there is a bias term $r_W(\omega_j, \omega_{m(j)})$ which is the distance between the sampled point $\omega_j$ and its nearest neighbor $\omega_{m(i)}$ (w.r.t. the neighborhood distance). This bias depends on the form of the underlying graphon $(\Omega, \mu, W)$, for example, it is equal to zero w.h.p. in the stochastic block model (i.e., when the link function $W$ is piecewise constant on $\Omega = [0, 1]$). We also derive a minimax lower bound that matches the upper bound of Theorem 1. See Section 4.2 for details on the distance estimation.

Based on the estimated distances $\hat{r}(i, j)$, we estimate the covering number $N_{\Omega}^{(c)}(\epsilon)$ by plug-in and provide universal non-asymptotic error bounds for this estimator. See Section 4.3 for details. Our results on the distance and covering number are therefore valid for all graphons, unlike most results in the graphon literature.

Combining the above covering number estimator $\hat{N}_{\Omega}^{(c)}$ with formula (2), we derive an estimator of the Minkowski dimension

$$\widehat{dim}_D := \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon_D)}{-\log \epsilon_D}$$

which satisfies a high probability convergence rate (Theorem 2). For this result, we assume the Minkowski dimension is upper bounded by some constant $D$ and use a particular radius $\epsilon_D$ defined in Section 4.4. We also make some mild assumptions on the graphon geometry, which are inspired by the problem of estimation of manifold dimension (see section 1.3 for this related literature). Besides, we show that this set of assumptions is minimal, in the sense that, if any of these assumptions is removed, all dimension estimators make an estimation error of the order 1.

**Theorem 2** Under some mild assumptions, defined in Section 4.4, the following holds. If $dim \Omega$ is any real in $[0, D]$, then

$$|\widehat{dim}_D - dim \Omega| \lesssim \frac{1}{\log n}$$

with probability at least $1 - C'/n$ for some constant $C'$ independent of $n$.

Finally, we prove that the upper bound $\log^{-1} n$ is optimal, which means that no estimator can improve on this error. For detailed results, see Section 4.4.

As extensions, we show that the above results also cover the important setting of sparse networks, which has been considered several times in the literature (see Bickel et al., 2011; Wolfe and Olhede, 2013; Klopp et al., 2017; Xu et al., 2014). In addition, we describe a polynomial-time algorithm to approximate the covering number estimator; we do so by using a classic greedy algorithm that is known to satisfy some theoretical guarantees. See Section 6 for these two extensions.

Finally, we test if the packing number (of a purified version of $(\Omega, r_W)$) is smaller than $K$, with a specific care for controlling the type I error probability uniformly over all graphons.
We prove this error is smaller than $2/n$ for any graphon. For technical reasons detailed in Section 5, we use here the packing number instead of the covering number, which are essentially the same measures (see Appendix A for a reminder about these usual measures for metric spaces).

## 1.3 Connection with the Literature

### 1.3.1 W-RANDOM GRAPH MODEL

The most simple random graph is the Erdös-Rényi model where each edge has the same probability $p$ of being present, independently of the other edges. The study of this generative model has been impressively fruitful in mathematics (Bollobás, 1998) but does not replicate even the simplest properties of real-world networks. Hence, the assumption of a constant connection probability $p$ has been relaxed in the celebrated stochastic block model (Holland et al., 1983) where the connection probabilities may vary with the community membership of each node. Although this model has attracted a lot of attention (Abbe, 2017), it fails to catch some subtle aspects of very large graphs. Such modeling issues have led to a non-parametric view of network analysis (Bickel and Chen, 2009), in particular the introduction of the W-random graph model (Diaconis and Janson, 2007).

The universality of the W-random graphs has two parts. On the one hand, the graphon $(\Omega, \mu, W)$ plays a key role in network analysis as a powerful representation of many graph properties. Indeed, it has been shown that many sequences of growing graphs can be represented by graphons. For details, see the theory of graph limits introduced by Lovász and Szegedy (2006) or the comprehensive monograph by Lovász (2012). On the other hand, the W-random graph model is connected with the theory of exchangeable random graphs. In fact, every distribution on random graphs that is invariant by permutation of nodes can be expressed with W-random graphs (Diaconis and Janson, 2007; Aldous, 1981; Kallenberg, 1989). Thus, the W-random graphs encompass many random graph models, including stochastic block models, random geometric graphs (Penrose et al., 2003) and random dot product graphs (Tang et al., 2013; Athreya et al., 2017).

### 1.3.2 GRAPHON ESTIMATION

There has been much interest in the recovery of the function $W$ (or the matrix of probabilities $[W(\omega_i, \omega_j)]_{i,j \le n}$) on the specific space $\Omega = [0, 1]$. Usually, authors assume the graphon has some regularity (e.g. $W$ is Hölder continuous on $[0, 1]$) and then use an approximation by SBM, which can be seen as an approximation by constant piecewise functions of $W$ (Borgs et al., 2015; Wolfe and Olhede, 2013; Gao et al., 2015; Klopp et al., 2017; Latouche and Robin, 2016). We also mention an alternative approach based on neighborhood-smoothing (Zhang et al., 2015; Xu et al., 2014). In comparison with this literature, our objective is less ambitious since we only estimate a feature of the graph (its complexity). In return, we carry out a general analysis and do not assume any smoothness condition on $\Omega = [0, 1]$. Indeed, our results on the neighborhood distance and covering number estimations are valid for all graphons. For the dimension, we make mild assumptions which are similar to those in the “intrinsic dimension estimation” literature (see subsection 1.3.3 for a brief description of this related problem).
We prove this error is smaller than $2/n$ for any graphon. For technical reasons detailed in Section 5, we use here the packing number instead of the covering number, which are essentially the same measures (see Appendix A for a reminder about these usual measures for metric spaces).

## 1.3 Connection with the Literature

### 1.3.1 W-RANDOM GRAPH MODEL

The most simple random graph is the Erdös-Rényi model where each edge has the same probability $p$ of being present, independently of the other edges. The study of this generative model has been impressively fruitful in mathematics (Bollobás, 1998) but does not replicate even the simplest properties of real-world networks. Hence, the assumption of a constant connection probability $p$ has been relaxed in the celebrated stochastic block model (Holland et al., 1983) where the connection probabilities may vary with the community membership of each node. Although this model has attracted a lot of attention (Abbe, 2017), it fails to catch some subtle aspects of very large graphs. Such modeling issues have led to a non-parametric view of network analysis (Bickel and Chen, 2009), in particular the introduction of the W-random graph model (Diaconis and Janson, 2007).

The universality of the W-random graphs has two parts. On the one hand, the graphon $(\Omega, \mu, W)$ plays a key role in network analysis as a powerful representation of many graph properties. Indeed, it has been shown that many sequences of growing graphs can be represented by graphons. For details, see the theory of graph limits introduced by Lovász and Szegedy (2006) or the comprehensive monograph by Lovász (2012). On the other hand, the W-random graph model is connected with the theory of exchangeable random graphs. In fact, every distribution on random graphs that is invariant by permutation of nodes can be expressed with W-random graphs (Diaconis and Janson, 2007; Aldous, 1981; Kallenberg, 1989). Thus, the W-random graphs encompass many random graph models, including stochastic block models, random geometric graphs (Penrose et al., 2003) and random dot product graphs (Tang et al., 2013; Athreya et al., 2017).

### 1.3.2 GRAPHON ESTIMATION

There has been much interest in the recovery of the function $W$ (or the matrix of probabilities $[W(\omega_i, \omega_j)]_{i,j \le n}$) on the specific space $\Omega = [0, 1]$. Usually, authors assume the graphon has some regularity (e.g. $W$ is Hölder continuous on $[0, 1]$) and then use an approximation by SBM, which can be seen as an approximation by constant piecewise functions of $W$ (Borgs et al., 2015; Wolfe and Olhede, 2013; Gao et al., 2015; Klopp et al., 2017; Latouche and Robin, 2016). We also mention an alternative approach based on neighborhood-smoothing (Zhang et al., 2015; Xu et al., 2014). In comparison with this literature, our objective is less ambitious since we only estimate a feature of the graph (its complexity). In return, we carry out a general analysis and do not assume any smoothness condition on $\Omega = [0, 1]$. Indeed, our results on the neighborhood distance and covering number estimations are valid for all graphons. For the dimension, we make mild assumptions which are similar to those in the “intrinsic dimension estimation” literature (see subsection 1.3.3 for a brief description of this related problem).
In the estimation problem of $W$, the latent space $[0, 1]$ is sometimes considered instead of $\Omega$. This choice is not restrictive (if no assumption is made on the function $W$ on $[0, 1]$) because both settings generate the same W-random graph distributions (Lovász, 2012). However, the restricted setting $[0, 1]$ is not always convenient to work with, whereas the general setting $\Omega$ leads to simpler and cleaner situations (Lovász, 2012). Indeed, many random graph distributions are naturally represented on $\Omega$ so that their properties are easy to interpret. See Section 3.2 for illustrative examples.

The $l_2$-neighborhood distance (1) is a variant of the $l_1$-neighborhood distance introduced by Lovász (2012). This variant has been leveraged several times for the estimation of $[W(\omega_i, \omega_j)]_{i,j \le n}$ (Zhang et al., 2015; Xu et al., 2014) where the authors use it as a criterion to select neighborhoods of nodes. Here, our estimator of the $l_2$-neighborhood distance is inspired by the work of Zhang et al. (2015), as will be discussed later.

In sparse settings as well, the matrix $[W(\omega_i, \omega_j)]_{i,j \le n}$ can be estimated by averaging over "similar" observed entries, where "similar" is defined by some neighbor estimator. In (Li et al., 2019) for example, the neighbor estimator is simply the $l_2$-distance between two rows in the observed matrix, and the random fraction of observed entries is larger than $n^{-1/2+\delta}$ for any $\delta > 0$. We also consider this sparse regime for the estimation of the $l_2$-neighborhood distance, but we do not use the same estimator as Li et al. (2019) since it suffers from a constant bias $O(1)$. For details, see the equations page 7 in (Li et al., 2019).

However, the distance estimators in (Li et al., 2019; Zhang et al., 2015) and the current paper are only based on immediate neighborhoods, which are not sufficiently informative in very sparse regimes, where the fraction of observed entries is $o(n^{-1/2})$. Although this is not the focus of our paper, we mention that there exist successful methods in such very sparse regimes. For example, the similarity between two nodes can be estimated by comparing the two sets of paths starting from these nodes (Borgs et al., 2017). By considering paths of length (strictly) larger than 1, this approach allows to gather information within larger neighborhoods than immediate neighbors. However, the theoretical guarantees proved for this method (Borgs et al., 2017) are restricted to functions $W$ of finite spectrum and defined on $[0, 1]$, whereas we study any function on any space $\Omega$.

### 1.3.3 INTRINSIC DIMENSION ESTIMATION

There is a considerable body of literature on the estimation of intrinsic dimension of a manifold (Kim et al., 2016; Kégl, 2003; Koltchinskii, 2000; Levina and Bickel, 2005). In the simplest setting, points are sampled on a manifold of $\mathbb{R}^m$ whose dimension is an integer, and the objective is to recover this dimension from the sample. In contrast, here we do not assume the dimension is an integer, we do not observe the $n$ sampled points $\omega_1, \dots, \omega_n$, and we are not in the Euclidean metric space $\mathbb{R}^m$. Indeed, the neighborhood distance $r_W$ is unknown, and our only observation is the connections of the graph.

**OUTLINE OF THE PAPER.** Section 2 gives a formal presentation of the problem. Section 3 presents the complexity index and some illustrations. In Section 4, we focus on statistical estimation (distance, covering number, dimension). In Section 5, we test the graph complexity. In Section 6, we provide two extensions (estimation on sparse graphs, and a polynomial-time algorithm). Proofs are deferred to the appendix.
In the estimation problem of $W$, the latent space $[0, 1]$ is sometimes considered instead of $\Omega$. This choice is not restrictive (if no assumption is made on the function $W$ on $[0, 1]$) because both settings generate the same W-random graph distributions (Lovász, 2012). However, the restricted setting $[0, 1]$ is not always convenient to work with, whereas the general setting $\Omega$ leads to simpler and cleaner situations (Lovász, 2012). Indeed, many random graph distributions are naturally represented on $\Omega$ so that their properties are easy to interpret. See Section 3.2 for illustrative examples.

The $l_2$-neighborhood distance (1) is a variant of the $l_1$-neighborhood distance introduced by Lovász (2012). This variant has been leveraged several times for the estimation of $[W(\omega_i, \omega_j)]_{i,j \le n}$ (Zhang et al., 2015; Xu et al., 2014) where the authors use it as a criterion to select neighborhoods of nodes. Here, our estimator of the $l_2$-neighborhood distance is inspired by the work of Zhang et al. (2015), as will be discussed later.

In sparse settings as well, the matrix $[W(\omega_i, \omega_j)]_{i,j \le n}$ can be estimated by averaging over "similar" observed entries, where "similar" is defined by some neighbor estimator. In (Li et al., 2019) for example, the neighbor estimator is simply the $l_2$-distance between two rows in the observed matrix, and the random fraction of observed entries is larger than $n^{-1/2+\delta}$ for any $\delta > 0$. We also consider this sparse regime for the estimation of the $l_2$-neighborhood distance, but we do not use the same estimator as Li et al. (2019) since it suffers from a constant bias $O(1)$. For details, see the equations page 7 in (Li et al., 2019).

However, the distance estimators in (Li et al., 2019; Zhang et al., 2015) and the current paper are only based on immediate neighborhoods, which are not sufficiently informative in very sparse regimes, where the fraction of observed entries is $o(n^{-1/2})$. Although this is not the focus of our paper, we mention that there exist successful methods in such very sparse regimes. For example, the similarity between two nodes can be estimated by comparing the two sets of paths starting from these nodes (Borgs et al., 2017). By considering paths of length (strictly) larger than 1, this approach allows to gather information within larger neighborhoods than immediate neighbors. However, the theoretical guarantees proved for this method (Borgs et al., 2017) are restricted to functions $W$ of finite spectrum and defined on $[0, 1]$, whereas we study any function on any space $\Omega$.

### 1.3.3 INTRINSIC DIMENSION ESTIMATION

There is a considerable body of literature on the estimation of intrinsic dimension of a manifold (Kim et al., 2016; Kégl, 2003; Koltchinskii, 2000; Levina and Bickel, 2005). In the simplest setting, points are sampled on a manifold of $\mathbb{R}^m$ whose dimension is an integer, and the objective is to recover this dimension from the sample. In contrast, here we do not assume the dimension is an integer, we do not observe the $n$ sampled points $\omega_1, \dots, \omega_n$, and we are not in the Euclidean metric space $\mathbb{R}^m$. Indeed, the neighborhood distance $r_W$ is unknown, and our only observation is the connections of the graph.

**OUTLINE OF THE PAPER.** Section 2 gives a formal presentation of the problem. Section 3 presents the complexity index and some illustrations. In Section 4, we focus on statistical estimation (distance, covering number, dimension). In Section 5, we test the graph complexity. In Section 6, we provide two extensions (estimation on sparse graphs, and a polynomial-time algorithm). Proofs are deferred to the appendix.
NOTATION. we write $a \lesssim b$, if there exists a constant $C$ such that $a \le Cb$; and note $a \asymp b$, if there exist two constants $c, c'$ such that $ca \le b \le c'a$. We denote by $a \lor b$ (respectively $a \land b$) the maximum (resp. minimum) between $a$ and $b$; by $[a]_+$ the maximum between 0 and $a$; by $[n]$ the set $\{1, \dots, n\}$; by $B(x, \epsilon)$ a ball of radius $\epsilon$ and center $x$. We note $1_{\mathcal{E}}$ the indicator function corresponding to any event $\mathcal{E}$. We write “a.e.” for “almost everywhere”; and “w.r.t.” for “with respect to”; and “w.h.p.” for “with high probability”, which means that the probability converges to 1 as the number of graph nodes tends to infinity.

## 2. Model

### 2.1 Setting

For a set of vertices $V = \{1, \dots, n\}$, a W-random graph $G = (V, E)$ is generated as follows. Let $(\Omega, \mu, W)$ be an unknown triplet of parameters, which is composed of a measurable set $\Omega$, a probability measure $\mu$ on $\Omega$, and a symmetric (measurable) function $W: \Omega \times \Omega \to [0, 1]$. Such a triplet is called a graphon and we write $\mathcal{W}$ the collection of all graphons. For each node $i \in V$, an unknown attribute $\omega_i \in \Omega$ is drawn in an i.i.d. manner from the distribution $\mu$. Conditionally to the attributes $\omega = (\omega_1, \dots, \omega_n)$, an edge connects two vertices $i$ and $j$, independently of the other edges, with probability $W(\omega_i, \omega_j)$.

$$ \mathbb{P}((i, j) \in E | \omega) = W(\omega_i, \omega_j) \qquad (3) $$

Our data are a single observation of the W-random graph. Formally, it is an adjacency matrix $A = [A_{ij}]_{i,j \le n}$ defined by $A_{ij} = 1$ if $(i, j) \in E$, and 0 otherwise. This symmetric binary matrix with zero-entries on the diagonal represents an undirected, unweighted graph with no self edges. The distribution of $A$ is called the data distribution and is denoted by $\mathbb{P}^{(n)}_{(\Omega, \mu, W)}$. The goal will be to define an index characterizing the complexity of the limiting distribution $\mathbb{P}^{(\infty)}_{(\Omega, \mu, W)}$. In particular, the index should be identifiable from all distributions $\mathbb{P}^{(n)}_{(\Omega, \mu, W)}$, $1 \le n \le \infty$, in order to be estimated from the data $A$. The dependence in $n$ is often dropped out in the rest of the paper.

### 2.2 Non-identifiability and Equivalence Class of Graphons

From the observation $A$, the function $W$ is not identifiable. Indeed, for any measure-preserving bijection $\phi: \Omega \to \Omega$, we can observe that the map $W^{\phi}(x, y) = W(\phi(x), \phi(y))$ leaves the data distribution unchanged, i.e.:

$$ \mathbb{P}_{(\Omega, \mu, W)} = \mathbb{P}_{(\Omega, \mu, W^{\phi})}. $$

In fact, even the latent space $\Omega$ is not identifiable. The full picture is described by Lovász (2012, chap.10):

Two graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$ parametrize the same data distributions for all $n$, if and only if, there exist some measure-preserving maps $\phi: [0, 1] \to \Omega$ and $\psi: [0, 1] \to \Omega'$ such that $W^{\phi}(x, y) = W^{\psi}(x, y)$ a.e.
NOTATION. we write $a \lesssim b$, if there exists a constant $C$ such that $a \le Cb$; and note $a \asymp b$, if there exist two constants $c, c'$ such that $ca \le b \le c'a$. We denote by $a \lor b$ (respectively $a \land b$) the maximum (resp. minimum) between $a$ and $b$; by $[a]_+$ the maximum between 0 and $a$; by $[n]$ the set $\{1, \dots, n\}$; by $B(x, \epsilon)$ a ball of radius $\epsilon$ and center $x$. We note $1_{\mathcal{E}}$ the indicator function corresponding to any event $\mathcal{E}$. We write “a.e.” for “almost everywhere”; and “w.r.t.” for “with respect to”; and “w.h.p.” for “with high probability”, which means that the probability converges to 1 as the number of graph nodes tends to infinity.

## 2. Model

### 2.1 Setting

For a set of vertices $V = \{1, \dots, n\}$, a W-random graph $G = (V, E)$ is generated as follows. Let $(\Omega, \mu, W)$ be an unknown triplet of parameters, which is composed of a measurable set $\Omega$, a probability measure $\mu$ on $\Omega$, and a symmetric (measurable) function $W: \Omega \times \Omega \to [0, 1]$. Such a triplet is called a graphon and we write $\mathcal{W}$ the collection of all graphons. For each node $i \in V$, an unknown attribute $\omega_i \in \Omega$ is drawn in an i.i.d. manner from the distribution $\mu$. Conditionally to the attributes $\omega = (\omega_1, \dots, \omega_n)$, an edge connects two vertices $i$ and $j$, independently of the other edges, with probability $W(\omega_i, \omega_j)$.

$$ \mathbb{P}((i, j) \in E | \omega) = W(\omega_i, \omega_j) \qquad (3) $$

Our data are a single observation of the W-random graph. Formally, it is an adjacency matrix $A = [A_{ij}]_{i,j \le n}$ defined by $A_{ij} = 1$ if $(i, j) \in E$, and 0 otherwise. This symmetric binary matrix with zero-entries on the diagonal represents an undirected, unweighted graph with no self edges. The distribution of $A$ is called the data distribution and is denoted by $\mathbb{P}^{(n)}_{(\Omega, \mu, W)}$. The goal will be to define an index characterizing the complexity of the limiting distribution $\mathbb{P}^{(\infty)}_{(\Omega, \mu, W)}$. In particular, the index should be identifiable from all distributions $\mathbb{P}^{(n)}_{(\Omega, \mu, W)}$, $1 \le n \le \infty$, in order to be estimated from the data $A$. The dependence in $n$ is often dropped out in the rest of the paper.

### 2.2 Non-identifiability and Equivalence Class of Graphons

From the observation $A$, the function $W$ is not identifiable. Indeed, for any measure-preserving bijection $\phi: \Omega \to \Omega$, we can observe that the map $W^{\phi}(x, y) = W(\phi(x), \phi(y))$ leaves the data distribution unchanged, i.e.:

$$ \mathbb{P}_{(\Omega, \mu, W)} = \mathbb{P}_{(\Omega, \mu, W^{\phi})}. $$

In fact, even the latent space $\Omega$ is not identifiable. The full picture is described by Lovász (2012, chap.10):

Two graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$ parametrize the same data distributions for all $n$, if and only if, there exist some measure-preserving maps $\phi: [0, 1] \to \Omega$ and $\psi: [0, 1] \to \Omega'$ such that $W^{\phi}(x, y) = W^{\psi}(x, y)$ a.e.
where [0, 1] is the probability space endowed with the uniform measure. This characterization will be useful to prove the identifiability of our complexity index. For clarity of this future discussion, we consider the corresponding quotient space $W/\sim$, which is the set of equivalence classes of graphons leading to the same data distributions.

### 3. Complexity Index

Given a graphon $(\Omega, \mu, W)$, we endow the latent space $\Omega$ with the neighborhood distance

$$r_W(\omega, \omega') = \left( \int_{\Omega} |W(\omega, \omega'') - W(\omega', \omega'')|^2 \mu(d\omega'') \right)^{1/2} \quad (4)$$

which is the $l_2$-norm $||W(\omega, \cdot) - W(\omega', \cdot)||_{2,\mu}$ between the slices of the function $W$ in $\omega$ and $\omega'$. Then, we measure the complexity of the pseudo-metric space $(\Omega, r_W)$ in a classic way, using its covering number $N_{\Omega}^{(c)}(\epsilon)$ and its Minkowski dimension:

$$dim \Omega := \lim_{\epsilon \to 0} \frac{\log N_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} \quad (5)$$

when the limit exists. See appendix A for additional information about these two standard measures of metric spaces.

Unfortunately, the covering number and the Minkowski dimension of a graphon are not identifiable from the data distribution $P_{(\Omega, \mu, W)}$. Indeed, they are not robust to changes of the graphon on null-sets, whereas such changes leave the data distribution unaltered (a null-set is a set of zero measure in the probability space $(\Omega, \mu)$). This fact is illustrated in the following example where two equivalent graphons (i.e. leading to the same data distributions) have two different Minkowski dimensions. As we can see, this problem is due to the presence of a “big” null-set in $\Omega$.

**EXAMPLE.** Let $\Omega := \{2\}$ and $\Omega' := \{2\} \cup [0, 1]$ be two latent spaces endowed with a common probability distribution $\mu$ such that $\mu[\{2\}] = 1$. Let $W'$ be a function defined on $\Omega' \times \Omega'$ such that $W'(x', y') = (x'+y')/3$ for $x', y' \in [0, 1]$. Let $W$ be any measurable function on $\Omega \times \Omega$ such that $W(2, 2) = W'(2, 2)$. Then, the two graphons $(\Omega, \mu, W)$, $(\Omega', \mu, W')$ are equivalent, and yet they have two different Minkowski dimensions: $dim \Omega = 0$ since $r_W = 0$ on $\Omega$, while $dim \Omega' = 1$ since $r_{W'}(x', z') = |x' - z'|/3$ for $x', z' \in [0, 1]$. $\square$

#### 3.1 Purification Process for Identifiability

To define an identifiable index of complexity, we need to take care of “big” null-sets (seen in the above example). Usually, these pathological sets are not present in standard representations $(\Omega, \mu, W)$ and even useless in terms of modeling. Thus, we get rid of them; we do so by using a general remedy, called pure graphon.

**Definition (Lovász, 2012, chap.13)** A graphon $(\Omega, \mu, W)$ is called pure if $(\Omega, r_W)$ is a complete separable metric space and the probability measure has full support (that is, every ball of non-zero radius has positive measure). Besides, there is a pure graphon in each equivalence class of graphons.
where [0, 1] is the probability space endowed with the uniform measure. This characterization will be useful to prove the identifiability of our complexity index. For clarity of this future discussion, we consider the corresponding quotient space $W/\sim$, which is the set of equivalence classes of graphons leading to the same data distributions.

### 3. Complexity Index

Given a graphon $(\Omega, \mu, W)$, we endow the latent space $\Omega$ with the neighborhood distance

$$r_W(\omega, \omega') = \left( \int_{\Omega} |W(\omega, \omega'') - W(\omega', \omega'')|^2 \mu(d\omega'') \right)^{1/2} \quad (4)$$

which is the $l_2$-norm $||W(\omega, \cdot) - W(\omega', \cdot)||_{2,\mu}$ between the slices of the function $W$ in $\omega$ and $\omega'$. Then, we measure the complexity of the pseudo-metric space $(\Omega, r_W)$ in a classic way, using its covering number $N_{\Omega}^{(c)}(\epsilon)$ and its Minkowski dimension:

$$dim \Omega := \lim_{\epsilon \to 0} \frac{\log N_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} \quad (5)$$

when the limit exists. See appendix A for additional information about these two standard measures of metric spaces.

Unfortunately, the covering number and the Minkowski dimension of a graphon are not identifiable from the data distribution $P_{(\Omega, \mu, W)}$. Indeed, they are not robust to changes of the graphon on null-sets, whereas such changes leave the data distribution unaltered (a null-set is a set of zero measure in the probability space $(\Omega, \mu)$). This fact is illustrated in the following example where two equivalent graphons (i.e. leading to the same data distributions) have two different Minkowski dimensions. As we can see, this problem is due to the presence of a “big” null-set in $\Omega$.

**EXAMPLE.** Let $\Omega := \{2\}$ and $\Omega' := \{2\} \cup [0, 1]$ be two latent spaces endowed with a common probability distribution $\mu$ such that $\mu[\{2\}] = 1$. Let $W'$ be a function defined on $\Omega' \times \Omega'$ such that $W'(x', y') = (x'+y')/3$ for $x', y' \in [0, 1]$. Let $W$ be any measurable function on $\Omega \times \Omega$ such that $W(2, 2) = W'(2, 2)$. Then, the two graphons $(\Omega, \mu, W)$, $(\Omega', \mu, W')$ are equivalent, and yet they have two different Minkowski dimensions: $dim \Omega = 0$ since $r_W = 0$ on $\Omega$, while $dim \Omega' = 1$ since $r_{W'}(x', z') = |x' - z'|/3$ for $x', z' \in [0, 1]$. $\square$

#### 3.1 Purification Process for Identifiability

To define an identifiable index of complexity, we need to take care of “big” null-sets (seen in the above example). Usually, these pathological sets are not present in standard representations $(\Omega, \mu, W)$ and even useless in terms of modeling. Thus, we get rid of them; we do so by using a general remedy, called pure graphon.

**Definition (Lovász, 2012, chap.13)** A graphon $(\Omega, \mu, W)$ is called pure if $(\Omega, r_W)$ is a complete separable metric space and the probability measure has full support (that is, every ball of non-zero radius has positive measure). Besides, there is a pure graphon in each equivalence class of graphons.
For illustrative examples of pure graphons, see Section 3.2. There is no “big” null-set in pure graphons (since their measure $\mu$ has full support by definition) and the complexity index takes the same value on the pure graphons of a same equivalence class of $W/ \sim$ (Lemma 3).

**Lemma 3** If two pure graphons are equivalent, then their covering numbers are equal.

The proof of Lemma 3 is written in Appendix C.2. Lemma 3 directly implies that the Minkowski dimension takes the same value for two equivalent pure graphons. Thus, for any limiting W-random graph distribution $P_{(\Omega, \mu, W)}^{(\infty)}$, we define its complexity as the covering number and the Minkowski dimension of any pure graphon from the corresponding equivalence class. According to the above lemma, these indices are identifiable from all data distributions $P_{(\Omega, \mu, W)}^{(n)}$, $1 \le n \le \infty$. From now on, we can work exclusively with pure graphons without the loss of generality, since there are pure graphons in each equivalence class of $W/ \sim$. In the remaining of the subsection, we describe two consequences of working with pure graphons.

The metric properties are preserved between equivalent pure graphons (Lemma 4).

**Lemma 4** Let $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$ be two pure graphons, endowed with their respective neighborhood distances $r_W$ and $r_{W'}$. If the two graphons are in a same equivalence class of $W/ \sim$, then for some bijective measure-preserving map $\phi: \Omega' \to \Omega$, we have

$$r_{W'}(x, y) = r_W(\phi(x), \phi(y)) \quad \text{almost surely on } \Omega' \times \Omega'$$

Lemma 4 states that the metric spaces $(\Omega, r_W)$ and $(\Omega', r_{W'})$ are isometric up to a null-set, it is therefore not surprising that they share the same covering number (Lemma 3). The proof of lemma 4 is written in Appendix C.1. Note that Lemma 4 ensures that the future distance estimation is a well-posed problem.

Another consequence of working with pure graphon is that the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in $\Omega$. Lemma 5 is proved in Appendix C.3.

**Lemma 5** For a pure graphon $(\Omega, \mu, W)$ such that $N_{\Omega}^{(c)}(\epsilon) < \infty$ for all $\epsilon > 0$, the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in the metric space $(\Omega, r_W)$. That is, for all radii $\epsilon > 0$, the event

$$\mathcal{E}(\epsilon) = \{\text{each ball of radius } \epsilon \text{ in } (\Omega, r_W) \text{ contains at least a sampled point } \omega_i\}$$

holds with a probability tending to one as $n \to \infty$.

## 3.2 Illustrative Examples

We exemplify the complexity index with instances of W-random graphs that are often considered in the literature: a stochastic block model (Holland et al., 1983; Abbe, 2017), a random Hölder graph (Gao et al., 2015; Zhang et al., 2015) and a random geometric graph (Penrose et al., 2003; Arias-Castro et al., 2018; De Castro et al., 2017; Bubeck et al., 2016).

**STOCHASTIC BLOCK MODEL.** It produces a structure of community dividing the node set into $K$ subsets of nodes which share a same pattern of connection. More precisely, the
For illustrative examples of pure graphons, see Section 3.2. There is no “big” null-set in pure graphons (since their measure $\mu$ has full support by definition) and the complexity index takes the same value on the pure graphons of a same equivalence class of $W/\sim$ (Lemma 3).

**Lemma 3** If two pure graphons are equivalent, then their covering numbers are equal.

The proof of Lemma 3 is written in Appendix C.2. Lemma 3 directly implies that the Minkowski dimension takes the same value for two equivalent pure graphons. Thus, for any limiting W-random graph distribution $P_{(\Omega, \mu, W)}^{(\infty)}$, we define its complexity as the covering number and the Minkowski dimension of any pure graphon from the corresponding equivalence class. According to the above lemma, these indices are identifiable from all data distributions $P_{(\Omega, \mu, W)}^{(n)}$, $1 \le n \le \infty$. From now on, we can work exclusively with pure graphons without the loss of generality, since there are pure graphons in each equivalence class of $W/\sim$. In the remaining of the subsection, we describe two consequences of working with pure graphons.

The metric properties are preserved between equivalent pure graphons (Lemma 4).

**Lemma 4** Let $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$ be two pure graphons, endowed with their respective neighborhood distances $r_W$ and $r_{W'}$. If the two graphons are in a same equivalence class of $W/\sim$, then for some bijective measure-preserving map $\phi: \Omega' \to \Omega$, we have

$$r_{W'}(x, y) = r_W(\phi(x), \phi(y)) \quad \text{almost surely on } \Omega' \times \Omega'$$

Lemma 4 states that the metric spaces $(\Omega, r_W)$ and $(\Omega', r_{W'})$ are isometric up to a null-set, it is therefore not surprising that they share the same covering number (Lemma 3). The proof of lemma 4 is written in Appendix C.1. Note that Lemma 4 ensures that the future distance estimation is a well-posed problem.

Another consequence of working with pure graphon is that the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in $\Omega$. Lemma 5 is proved in Appendix C.3.

**Lemma 5** For a pure graphon $(\Omega, \mu, W)$ such that $N_{\Omega}^{(c)}(\epsilon) < \infty$ for all $\epsilon > 0$, the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in the metric space $(\Omega, r_W)$. That is, for all radii $\epsilon > 0$, the event

$$\mathcal{E}(\epsilon) = \{\text{each ball of radius } \epsilon \text{ in } (\Omega, r_W) \text{ contains at least a sampled point } \omega_i\}$$

holds with a probability tending to one as $n \to \infty$.

## 3.2 Illustrative Examples

We exemplify the complexity index with instances of W-random graphs that are often considered in the literature: a stochastic block model (Holland et al., 1983; Abbe, 2017), a random Hölder graph (Gao et al., 2015; Zhang et al., 2015) and a random geometric graph (Penrose et al., 2003; Arias-Castro et al., 2018; De Castro et al., 2017; Bubeck et al., 2016).

**STOCHASTIC BLOCK MODEL.** It produces a structure of community dividing the node set into $K$ subsets of nodes which share a same pattern of connection. More precisely, the
edges are independently sampled from each others, and the probability of an edge between two nodes only depends on their community membership. The SBM with $K$ communities can be written in the framework of the W-random graph model, by setting $\Omega = \{c_1, \dots, c_K\}$, so that each node belongs to one of the $K$ communities $c_i$, and connects to each other with probability $W(c_i, c_j)$. A natural notion of complexity for SBM is the number $K$ of communities, which coincides with the $\epsilon$-covering number of $\{c_1, \dots, c_K\}$ for small radii $\epsilon$.

**APPROXIMATION BY SBM.** In the estimation of $W$ based on the classic approximation by SBM (Gao et al., 2015; Klopp et al., 2017), the right number of communities can be selected using the covering number. Indeed, Proposition 6 states that, for any graphon $(\Omega, \mu, W)$, the function $W$ can be “$O(\epsilon)$-approximated” in $l_2$-norm by an SBM with at most $N_{\Omega}^{(c)}(\epsilon)$ communities. The proof is written in Appendix B.1.

**Proposition 6** Consider any graphon $(\Omega, \mu, W)$ and its $\epsilon$-covering number $N_{\Omega}^{(c)}(\epsilon)$, defined in Section 3. There exists a graphon $(\Omega, \mu, \overline{W})$ equivalent to an SBM with $N_{\Omega}^{(c)}(\epsilon)$ communities, such that,

$$ \int_{\Omega^2} (W(\omega, \omega') - \overline{W}(\omega, \omega'))^2 \mu(d\omega)\mu(d\omega') \le (4\epsilon)^2. $$

**RANDOM HÖLDER GRAPH.** Let $\Omega = [0, 1]^d$ be endowed with the uniform measure, and $W$ fulfill a double Hölder condition:

$$ m||\omega' - \omega||_2^{\alpha} \le |W(\omega', \omega'') - W(\omega, \omega'')| \le M||\omega' - \omega||_2^{\alpha} \quad (6) $$

for some Hölder exponent $\alpha > 0$ (and some constants $m, M > 0$). This means that each node has its specific attribute of $d$ variables, and connects to another node with a probability that smoothly depends on the node attributes. A natural notion of complexity for this graph distribution should increase with the number $d$ of variables, and decrease with the level $\alpha$ of smoothness. This intuitive notion is matched by the Minkowski dimension, which is equal to $d/\alpha$. See Appendix A for details.

**RANDOM GEOMETRIC GRAPH.** It generates simple spatial networks placing nodes in a Euclidean metric space and connecting two nodes if their Euclidean distance is small. Let $\Omega = [0, 1]^d$ be endowed with the uniform measure and the indicator function $W(\omega, \omega') = \mathbb{I}_{||\omega-\omega'||_2 \le \delta}$ for some constant $\delta > 0$. Appendix A shows that $dim \Omega = 2d$. Thus, the Minkowski dimension matches the Euclidean dimension of the latent space, up to a factor 2.

# 4. Estimation of the Complexity Index

Given a pure graphon $(\Omega, \mu, W)$, assume a W-random graph is generated from the probability distribution $P_{(\Omega, \mu, W)}$ defined in Section 2.1. From a single observation of the adjacency matrix $A$ of this graph, we want to estimate the complexity index (introduced in Section 3.1). In particular, the underlying graphon $(\Omega, \mu, W)$ is unknown, and the sampled points $\omega_1, \dots, \omega_n$ are not observed.

This section is organized in the following manner. We first estimate the neighborhood distance (4) on the sampled points $\omega_1, \dots, \omega_n$. Based on these estimated distances, we then estimate the $\epsilon$-covering number of $(\{\omega_1, \dots, \omega_n\}, r_W)$ by plug-in. Denote by $\tilde{N}_{\Omega}^{(c)}(\epsilon)$ this
edges are independently sampled from each others, and the probability of an edge between two nodes only depends on their community membership. The SBM with K communities can be written in the framework of the W-random graph model, by setting $\Omega = \{c_1, \dots, c_K\}$, so that each node belongs to one of the K communities $c_i$, and connects to each other with probability $W(c_i, c_j)$. A natural notion of complexity for SBM is the number K of communities, which coincides with the $\epsilon$-covering number of $\{c_1, \dots, c_K\}$ for small radii $\epsilon$.

**APPROXIMATION BY SBM.** In the estimation of $W$ based on the classic approximation by SBM (Gao et al., 2015; Klopp et al., 2017), the right number of communities can be selected using the covering number. Indeed, Proposition 6 states that, for any graphon $(\Omega, \mu, W)$, the function $W$ can be “$O(\epsilon)$-approximated” in $l_2$-norm by an SBM with at most $N_{\Omega}^{(c)}(\epsilon)$ communities. The proof is written in Appendix B.1.

**Proposition 6** Consider any graphon $(\Omega, \mu, W)$ and its $\epsilon$-covering number $N_{\Omega}^{(c)}(\epsilon)$, defined in Section 3. There exists a graphon $(\Omega, \mu, \overline{W})$ equivalent to an SBM with $N_{\Omega}^{(c)}(\epsilon)$ communities, such that,

$$ \int_{\Omega^2} (W(\omega, \omega') - \overline{W}(\omega, \omega'))^2 \mu(d\omega)\mu(d\omega') \le (4\epsilon)^2. $$

**RANDOM HÖLDER GRAPH.** Let $\Omega = [0, 1]^d$ be endowed with the uniform measure, and $W$ fulfill a double Hölder condition:

$$ m||\omega' - \omega||_2^{\alpha} \le |W(\omega', \omega'') - W(\omega, \omega'')| \le M||\omega' - \omega||_2^{\alpha} \quad (6) $$

for some Hölder exponent $\alpha > 0$ (and some constants $m, M > 0$). This means that each node has its specific attribute of $d$ variables, and connects to another node with a probability that smoothly depends on the node attributes. A natural notion of complexity for this graph distribution should increase with the number $d$ of variables, and decrease with the level $\alpha$ of smoothness. This intuitive notion is matched by the Minkowski dimension, which is equal to $d/\alpha$. See Appendix A for details.

**RANDOM GEOMETRIC GRAPH.** It generates simple spatial networks placing nodes in a Euclidean metric space and connecting two nodes if their Euclidean distance is small. Let $\Omega = [0, 1]^d$ be endowed with the uniform measure and the indicator function $W(\omega, \omega') = \mathbb{I}_{||\omega-\omega'||_2 \le \delta}$ for some constant $\delta > 0$. Appendix A shows that $dim \Omega = 2d$. Thus, the Minkowski dimension matches the Euclidean dimension of the latent space, up to a factor 2.

# 4. Estimation of the Complexity Index

Given a pure graphon $(\Omega, \mu, W)$, assume a W-random graph is generated from the probability distribution $\mathbb{P}_{(\Omega, \mu, W)}$ defined in Section 2.1. From a single observation of the adjacency matrix $A$ of this graph, we want to estimate the complexity index (introduced in Section 3.1). In particular, the underlying graphon $(\Omega, \mu, W)$ is unknown, and the sampled points $\omega_1, \dots, \omega_n$ are not observed.

This section is organized in the following manner. We first estimate the neighborhood distance (4) on the sampled points $\omega_1, \dots, \omega_n$. Based on these estimated distances, we then estimate the $\epsilon$-covering number of $(\{\omega_1, \dots, \omega_n\}, r_W)$ by plug-in. Denote by $\tilde{N}_{\Omega}^{(c)}(\epsilon)$ this
estimator. We finally estimate the Minkowski dimension using $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$ at a well chosen radius $\epsilon$.

## 4.1 Distance-estimator

Let us explain the construction of the distance estimator. The $l_2$-neighborhood distance is naturally associated with a structure of inner product. Given some square-integrable functions $f$ and $g$ on $\Omega$, we write their inner product $\langle f, g \rangle := \int_{\Omega} f(z)g(z)\mu(dz)$. Let $W(\omega_i, \cdot)$ denote the function $x \mapsto W(\omega_i, x)$, then the neighborhood distance admits the following decomposition

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

We estimate separately the crossed term and the two quadratic terms of (7).

Note $A_i$ the $i^{th}$ row vector of the adjacency matrix $A$, and $\langle A_i, A_j \rangle_n = \sum_{i=1}^n A_{ik}A_{jk}/n$ the inner product between two such rows. Given $\omega_i, \omega_j$, we observe that $\langle A_i, A_j \rangle_n$ is (almost) a sum of i.i.d. random variables (up to a duplicated entry because of the symmetry of the adjacency matrix $A$). Indeed, the $n-2$ random variables $\{A_{ik}A_{jk} : k \in [n] \text{ and } k \neq i, j\}$ are independent with the same mean conditionally to $\omega_i, \omega_j$:

$$\mathbb{E}[A_{ik}A_{jk}|\omega_i, \omega_j] = \langle W(\omega_i, \cdot), W(\omega_j, \cdot) \rangle$$

where the mean $\mathbb{E}$ is taken over the data distribution $\mathbb{P}_{(\Omega, \mu, W)}$. It is therefore possible to use Hoeffding's inequality to prove that $|\langle A_i, A_j \rangle_n - \langle W(\omega_i, \cdot), W(\omega_j, \cdot) \rangle| \lesssim \sqrt{\log n/n}$ w.h.p. (see Proposition 26 in Appendix D.1). Thus, the inner product between two different rows is a consistent estimator of the crossed term $\langle W(\omega_i, \cdot), W(\omega_j, \cdot) \rangle$ in (7).

To estimate the remaining quadratic term $\langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle$ in (7), we cannot proceed in the same way since $\frac{1}{n}\langle A_i, A_i \rangle$ is an inconsistent estimator of $\langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle$; indeed, we have

$$\mathbb{E}[A_{ik}A_{ik}|\omega_i] = \mathbb{E}[A_{ik}|\omega_i] = \langle W(\omega_i, \cdot), 1 \rangle \neq \langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle.$$

To work around this issue, we simply approximate the quadratic term by a crossed term to be back to the previous case. Specifically, the approximation consists in replacing a sampled point by its nearest neighbor as follows: let $\omega_{m(i)} \in \{\omega_1, \dots, \omega_n\}$ denote a nearest neighbor of $\omega_i$ according to the distance $r_W$, that is $m(i) \in \text{argmin}_{t: t \neq i} r_W(\omega_i, \omega_t)$, then we have the following approximation:

$$|\langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle - \langle W(\omega_i, \cdot), W(\omega_{m(i)}, \cdot) \rangle| = |\langle W(\omega_i, \cdot), W(\omega_i, \cdot) - W(\omega_{m(i)}, \cdot) \rangle| \\ \leq r_W(\omega_i, \omega_{m(i)}) \quad (8)$$

using Cauchy-Schwarz inequality. Thus, the nearest neighbor approximation (8) entails a bias in our estimation procedure, which is equal to the distance between $\omega_i$ and its nearest neighbor $\omega_{m(i)}$.

Since the index $m(i)$ is unknown, we define an index estimator $\hat{m}(i)$ such that $\omega_{\hat{m}(i)}$ is hopefully close to $\omega_i$ according to $r_W$, and then we use $\langle A_i, A_{\hat{m}(i)} \rangle_n$ to estimate the quadratic term. Formally, $\hat{m}(i)$ is a minimizer of the distance function $j \mapsto \hat{f}(i, j)$ defined by

$$\hat{f}(i, j) = \max_{k: k \neq i, j} |\langle A_k, A_i - A_j \rangle_n| \quad (9)$$
estimator. We finally estimate the Minkowski dimension using $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$ at a well chosen radius $\epsilon$.

## 4.1 Distance-estimator

Let us explain the construction of the distance estimator. The $l_2$-neighborhood distance is naturally associated with a structure of inner product. Given some square-integrable functions $f$ and $g$ on $\Omega$, we write their inner product $\langle f, g \rangle := \int_{\Omega} f(z)g(z)\mu(dz)$. Let $W(\omega_i, \cdot)$ denote the function $x \mapsto W(\omega_i, x)$, then the neighborhood distance admits the following decomposition

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

We estimate separately the crossed term and the two quadratic terms of (7).

Note $A_i$ the $i^{th}$ row vector of the adjacency matrix $A$, and $\langle A_i, A_j \rangle_n = \sum_{i=1}^n A_{ik}A_{jk}/n$ the inner product between two such rows. Given $\omega_i, \omega_j$, we observe that $\langle A_i, A_j \rangle_n$ is (almost) a sum of i.i.d. random variables (up to a duplicated entry because of the symmetry of the adjacency matrix $A$). Indeed, the $n-2$ random variables $\{A_{ik}A_{jk} : k \in [n] \text{ and } k \neq i, j\}$ are independent with the same mean conditionally to $\omega_i, \omega_j$:

$$\mathbb{E}[A_{ik}A_{jk}|\omega_i, \omega_j] = \langle W(\omega_i, \cdot), W(\omega_j, \cdot) \rangle$$

where the mean $\mathbb{E}$ is taken over the data distribution $\mathbb{P}_{(\Omega, \mu, W)}$. It is therefore possible to use Hoeffding's inequality to prove that $|\langle A_i, A_j \rangle_n - \langle W(\omega_i, \cdot), W(\omega_j, \cdot) \rangle| \lesssim \sqrt{\log n/n}$ w.h.p. (see Proposition 26 in Appendix D.1). Thus, the inner product between two different rows is a consistent estimator of the crossed term $\langle W(\omega_i, \cdot), W(\omega_j, \cdot) \rangle$ in (7).

To estimate the remaining quadratic term $\langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle$ in (7), we cannot proceed in the same way since $\frac{1}{n}\langle A_i, A_i \rangle$ is an inconsistent estimator of $\langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle$; indeed, we have

$$\mathbb{E}[A_{ik}A_{ik}|\omega_i] = \mathbb{E}[A_{ik}|\omega_i] = \langle W(\omega_i, \cdot), 1 \rangle \neq \langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle.$$

To work around this issue, we simply approximate the quadratic term by a crossed term to be back to the previous case. Specifically, the approximation consists in replacing a sampled point by its nearest neighbor as follows: let $\omega_{m(i)} \in \{\omega_1, \dots, \omega_n\}$ denote a nearest neighbor of $\omega_i$ according to the distance $r_W$, that is $m(i) \in \text{argmin}_{t: t \neq i} r_W(\omega_i, \omega_t)$, then we have the following approximation:

$$|\langle W(\omega_i, \cdot), W(\omega_i, \cdot) \rangle - \langle W(\omega_i, \cdot), W(\omega_{m(i)}, \cdot) \rangle| = |\langle W(\omega_i, \cdot), W(\omega_i, \cdot) - W(\omega_{m(i)}, \cdot) \rangle| \\ \leq r_W(\omega_i, \omega_{m(i)}) \quad (8)$$

using Cauchy-Schwarz inequality. Thus, the nearest neighbor approximation (8) entails a bias in our estimation procedure, which is equal to the distance between $\omega_i$ and its nearest neighbor $\omega_{m(i)}$.

Since the index $m(i)$ is unknown, we define an index estimator $\hat{m}(i)$ such that $\omega_{\hat{m}(i)}$ is hopefully close to $\omega_i$ according to $r_W$, and then we use $\langle A_i, A_{\hat{m}(i)} \rangle_n$ to estimate the quadratic term. Formally, $\hat{m}(i)$ is a minimizer of the distance function $j \mapsto \hat{f}(i, j)$ defined by

$$\hat{f}(i, j) = \max_{k: k \neq i, j} |\langle A_k, A_i - A_j \rangle_n| \quad (9)$$
where $\hat{f}(i, j)$ represents a proxy for the distance between the $i^{th}$ and $j^{th}$ rows of the adjacency matrix, which is enough to define the index estimator

$$ \hat{m}(i) = \underset{j: j \neq i}{\operatorname{argmin}} \hat{f}(i, j). \qquad (10) $$

Note that $\hat{f}(i, j)$ is small in expectation if $\omega_i$ and $\omega_j$ are close according to the neighborhood distance; indeed, $\mathbb{E}[\hat{f}(i, j)|\omega_i, \omega_j, \omega_k] = \max_{k \neq i, j} |\langle W(\omega_i, .) - W(\omega_j, .), W(\omega_k, .) \rangle| \le r_W(\omega_i, \omega_j)$ using Cauchy-Schwarz inequality.

Putting together the estimators of the crossed term and the two quadratic terms, we get the following estimator of the square distance $r_W^2(\omega_i, \omega_j)$:

$$ \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 \qquad (11) $$

for all $i, j \in [n]$, where $\hat{m}(i)$ is given by (10).

**REMARK:** The distance-estimator (11) is inspired by the work of Zhang et al. (2015), in which the authors want to recover the expectation of the adjacency matrix $A$, based on neighborhood smoothing. They rely on the proxy (9) to select neighborhood of points with respect to the neighborhood distance. Restricting themselves on graphons of the form $([0, 1], \lambda, W)$ with $\lambda$ the uniform measure and $W$ a piecewise Lipschitz function, they derive risk bounds for the estimation of $W$. In contrast, here we do not make any assumption on the graphon, and our objective is to provide an estimator of the neighborhood distance per se.

## 4.2 Consistency of the Distance-estimator

The statistical recovery of the set of distances $\{r_W(\omega_i, \omega_j) : i, j \in [n]\}$ is a well-posed problem, since the neighborhood distance is invariant on each equivalence class of graphons (Lemma 4). Theorem 7 gives non-asymptotic error bounds for the distance-estimator (11). The proof is written in Appendix D.1.

**Theorem 7** Given any (pure) graphon $(\Omega, \mu, W)$, consider the data distribution $\mathbb{P}_{(\Omega, \mu, W)}$ defined in model (3). For all $1 \le i \le n$, let $\omega_{m(i)} \in \{\omega_1, \dots, \omega_n\} \setminus \{\omega_i\}$ denote a nearest neighbor of $\omega_i$ according to the distance $r_W$. Then, for the distance-estimator (11), the event

$$ \mathcal{E}_{dist} = \{ \forall i, j \in [n] : |r_W^2(\omega_i, \omega_j) - \hat{r}^2(i, j)| \le 3r_W(\omega_j, \omega_{m(j)}) + 3r_W(\omega_i, \omega_{m(i)}) + 36\sqrt{\log(n)/n} \} $$
holds with probability $\mathbb{P}_{(\Omega, \mu, W)}[\mathcal{E}_{dist}] \ge 1 - \frac{2}{n}$.

Theorem 7 implies that the distance-estimator (11) is a consistent estimator of the neighborhood distance (4), provided that the $\epsilon$-covering number is finite for all radii $\epsilon > 0$. Indeed, for a finite covering number, Lemma 5 ensures that the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in $(\Omega, r_W)$, which implies that the bias $r_W(\omega_i, \omega_{m(i)})$ is convergent in probability to zero as $n$ grows to infinity.

Let us describe the upper bound of Theorem 7. On the one hand, there is a fluctuation term $\sqrt{\log(n)/n}$ that corresponds to the convergence property of the inner products
where $\hat{f}(i, j)$ represents a proxy for the distance between the $i^{th}$ and $j^{th}$ rows of the adjacency matrix, which is enough to define the index estimator

$$ \hat{m}(i) = \underset{j: j \neq i}{\operatorname{argmin}} \hat{f}(i, j). \qquad (10) $$

Note that $\hat{f}(i, j)$ is small in expectation if $\omega_i$ and $\omega_j$ are close according to the neighborhood distance; indeed, $\mathbb{E}[\hat{f}(i, j)|\omega_i, \omega_j, \omega_k] = \max_{k \neq i, j} |\langle W(\omega_i, .) - W(\omega_j, .), W(\omega_k, .) \rangle| \le r_W(\omega_i, \omega_j)$ using Cauchy-Schwarz inequality.

Putting together the estimators of the crossed term and the two quadratic terms, we get the following estimator of the square distance $r_W^2(\omega_i, \omega_j)$:

$$ \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 \qquad (11) $$

for all $i, j \in [n]$, where $\hat{m}(i)$ is given by (10).

**REMARK:** The distance-estimator (11) is inspired by the work of Zhang et al. (2015), in which the authors want to recover the expectation of the adjacency matrix $A$, based on neighborhood smoothing. They rely on the proxy (9) to select neighborhood of points with respect to the neighborhood distance. Restricting themselves on graphons of the form $([0, 1], \lambda, W)$ with $\lambda$ the uniform measure and $W$ a piecewise Lipschitz function, they derive risk bounds for the estimation of $W$. In contrast, here we do not make any assumption on the graphon, and our objective is to provide an estimator of the neighborhood distance per se.

## 4.2 Consistency of the Distance-estimator

The statistical recovery of the set of distances $\{r_W(\omega_i, \omega_j) : i, j \in [n]\}$ is a well-posed problem, since the neighborhood distance is invariant on each equivalence class of graphons (Lemma 4). Theorem 7 gives non-asymptotic error bounds for the distance-estimator (11). The proof is written in Appendix D.1.

**Theorem 7** Given any (pure) graphon $(\Omega, \mu, W)$, consider the data distribution $\mathbb{P}_{(\Omega, \mu, W)}$ defined in model (3). For all $1 \le i \le n$, let $\omega_{m(i)} \in \{\omega_1, \dots, \omega_n\} \setminus \{\omega_i\}$ denote a nearest neighbor of $\omega_i$ according to the distance $r_W$. Then, for the distance-estimator (11), the event

$$ \mathcal{E}_{dist} = \{ \forall i, j \in [n] : |r_W^2(\omega_i, \omega_j) - \hat{r}^2(i, j)| \le 3r_W(\omega_j, \omega_{m(j)}) + 3r_W(\omega_i, \omega_{m(i)}) + 36\sqrt{\log(n)/n} \} $$
holds with probability $\mathbb{P}_{(\Omega, \mu, W)}[\mathcal{E}_{dist}] \ge 1 - \frac{2}{n}$.

Theorem 7 implies that the distance-estimator (11) is a consistent estimator of the neighborhood distance (4), provided that the $\epsilon$-covering number is finite for all radii $\epsilon > 0$. Indeed, for a finite covering number, Lemma 5 ensures that the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in $(\Omega, r_W)$, which implies that the bias $r_W(\omega_i, \omega_{m(i)})$ is convergent in probability to zero as $n$ grows to infinity.

Let us describe the upper bound of Theorem 7. On the one hand, there is a fluctuation term $\sqrt{\log(n)/n}$ that corresponds to the convergence property of the inner products
between rows of A, i.e.: $|\langle A_i, A_j \rangle_n - \langle W(\omega_i, .), W(\omega_j, .) \rangle| \lesssim \sqrt{\log n/n}$ w.h.p. for $i \neq j$. On the other hand, there is a bias term $r_W(\omega_i, \omega_{m(i)})$ that results from the nearest neighbor approximation (8). Its value depends on the graphon regularity. For instance, in the SBM example of Section 3.2, the bias term $r_W(\omega_i, \omega_{m(i)})$ is equal to zero w.h.p. (indeed, $\omega_i$ and its nearest neighbor $\omega_{m(i)}$ are in the same community w.h.p., and thus separated by a distance zero w.r.t. $r_W$). In the random Hölder graph example, the bias term is of the order of $(\log(n)/n)^{\alpha/d}$ w.h.p..

The next result gives a lower bound matching the upper bound of Theorem 7, up to a numerical constant. Specifically, there exists a graphon $(\Omega, \mu, W_n)$ for each sample size $n \ge 1$, such that the lower bound holds for (at least) some of the $O(n^2)$ distances.

**Theorem 8** There exists a sequence of graphons $(\Omega, \mu, W_n)_{n \in \mathbb{N}}$ and some numerical constants $p, c, c' > 0$, such that the following holds for any estimator $\hat{d}$ and any permutation $\sigma$ of the $n$ indices. With a probability larger than $p$, the lower bound

$$ \left| r_{W_n}^2(\omega_i, \omega_j) - \hat{d}^2(\sigma(i), \sigma(j)) \right| \ge c' \left( r_{W_n}(\omega_j, \omega_{m(j)}) + r_{W_n}(\omega_i, \omega_{m(i)}) + \sqrt{\frac{\log n}{n}} \right) $$

is satisfied for (at least) $c n$ different pairs $(i, j)$.

The lower bound in Theorem 8 holds regardless of the nodes labels $i \in \{1, \dots, n\}$ since it is satisfied for any permutation $\sigma$ of the $n$ indices $\{1, \dots, n\}$. This is relevant in the model (3) where the data distribution is invariant by relabeling of the nodes.

In particular, Theorem 8 can be written for a graphon $(\Omega, \mu, W_n)_n$ whose bias $r_{W_n}(\omega_i, \omega_{m(i)})$ is equal to a numerical constant, thus giving the next result.

**Theorem 9** There exists a sequence of graphons $(\Omega, \mu, W_n)_{n \in \mathbb{N}}$ and some numerical constants $p, c > 0$, such that the following holds for any estimator $\hat{d}$ and any permutation $\sigma$ of the $n$ indices. With a probability larger than $p$, the lower bound

$$ \left| r_{W_n}^2(\omega_i, \omega_j) - \hat{d}^2(\sigma(i), \sigma(j)) \right| \ge \frac{1}{800} $$

is satisfied for (at least) $c n$ different pairs $(i, j)$.

The constant error in this lower bound does not violate the vanishing error bound in Theorem 7. Indeed, the graphon changes with $n$ in the above lower bounds whereas it remains fixed in the upper bound of Theorem 7.

Although Theorem 8 is a standard way of stating lower bounds in the literature, it is not sufficient to show that the right dependence on the bias $r_W(\omega_i, \omega_{m(i)})$ is linear. For example, if $r_W(\omega_i, \omega_{m(i)})$ is equal to a numerical constant, then one can replace $r_W(\omega_i, \omega_{m(i)})$ with $r_W^2(\omega_i, \omega_{m(i)})$ in Theorem 8 (by adapting the numerical constant $c'$ which was not tight anyway). One can observe that such a change from $r_W(\omega_i, \omega_{m(i)})$ to $r_W^2(\omega_i, \omega_{m(i)})$ is also possible in the case where $r_W(\omega_i, \omega_{m(i)})$ is smaller than the fluctuation term $\sqrt{\log(n)/n}$.
between rows of A, i.e.: $|\langle A_i, A_j \rangle_n - \langle W(\omega_i, .), W(\omega_j, .) \rangle| \lesssim \sqrt{\log n/n}$ w.h.p. for $i \neq j$. On the other hand, there is a bias term $r_W(\omega_i, \omega_{m(i)})$ that results from the nearest neighbor approximation (8). Its value depends on the graphon regularity. For instance, in the SBM example of Section 3.2, the bias term $r_W(\omega_i, \omega_{m(i)})$ is equal to zero w.h.p. (indeed, $\omega_i$ and its nearest neighbor $\omega_{m(i)}$ are in the same community w.h.p., and thus separated by a distance zero w.r.t. $r_W$). In the random Hölder graph example, the bias term is of the order of $(\log(n)/n)^{\alpha/d}$ w.h.p..

The next result gives a lower bound matching the upper bound of Theorem 7, up to a numerical constant. Specifically, there exists a graphon $(\Omega, \mu, W_n)$ for each sample size $n \ge 1$, such that the lower bound holds for (at least) some of the $O(n^2)$ distances.

**Theorem 8** There exists a sequence of graphons $(\Omega, \mu, W_n)_{n \in \mathbb{N}}$ and some numerical constants $p, c, c' > 0$, such that the following holds for any estimator $\hat{d}$ and any permutation $\sigma$ of the $n$ indices. With a probability larger than $p$, the lower bound

$$|r_{W_n}^2(\omega_i, \omega_j) - \hat{d}^2(\sigma(i), \sigma(j))| \ge c' \left( r_{W_n}(\omega_j, \omega_{m(j)}) + r_{W_n}(\omega_i, \omega_{m(i)}) + \sqrt{\frac{\log n}{n}} \right)$$

is satisfied for (at least) $c n$ different pairs $(i, j)$.

The lower bound in Theorem 8 holds regardless of the nodes labels $i \in \{1, \dots, n\}$ since it is satisfied for any permutation $\sigma$ of the $n$ indices $\{1, \dots, n\}$. This is relevant in the model (3) where the data distribution is invariant by relabeling of the nodes.

In particular, Theorem 8 can be written for a graphon $(\Omega, \mu, W_n)_n$ whose bias $r_{W_n}(\omega_i, \omega_{m(i)})$ is equal to a numerical constant, thus giving the next result.

**Theorem 9** There exists a sequence of graphons $(\Omega, \mu, W_n)_{n \in \mathbb{N}}$ and some numerical constants $p, c > 0$, such that the following holds for any estimator $\hat{d}$ and any permutation $\sigma$ of the $n$ indices. With a probability larger than $p$, the lower bound

$$|r_{W_n}^2(\omega_i, \omega_j) - \hat{d}^2(\sigma(i), \sigma(j))| \ge \frac{1}{800}$$

is satisfied for (at least) $c n$ different pairs $(i, j)$.

The constant error in this lower bound does not violate the vanishing error bound in Theorem 7. Indeed, the graphon changes with $n$ in the above lower bounds whereas it remains fixed in the upper bound of Theorem 7.

Although Theorem 8 is a standard way of stating lower bounds in the literature, it is not sufficient to show that the right dependence on the bias $r_W(\omega_i, \omega_{m(i)})$ is linear. For example, if $r_W(\omega_i, \omega_{m(i)})$ is equal to a numerical constant, then one can replace $r_W(\omega_i, \omega_{m(i)})$ with $r_W^2(\omega_i, \omega_{m(i)})$ in Theorem 8 (by adapting the numerical constant $c'$ which was not tight anyway). One can observe that such a change from $r_W(\omega_i, \omega_{m(i)})$ to $r_W^2(\omega_i, \omega_{m(i)})$ is also possible in the case where $r_W(\omega_i, \omega_{m(i)})$ is smaller than the fluctuation term $\sqrt{\log(n)/n}$.
Therefore, neither the lower bound of Theorem 8 nor the lower bound of Theorem 9 is enough informative to decipher whether the optimal rate is of the order of $r_W^2(\omega_i, \omega_{m(i)}) + \sqrt{\log(n)/n}$ or $r_W(\omega_i, \omega_{m(i)}) + \sqrt{\log(n)/n}$.

A quadratic dependency $r_W^2(\omega_i, \omega_{m(i)})$ would improve on the linear dependency since the neighborhood distance $r_W$ is always smaller than 1 by definition. Hence, one may wonder whether such an improvement is possible, especially that Theorem 7 is an error bound on square distances, $|r_W^2(\omega_i, \omega_j) - \hat{d}^2(i, j)|$. It turns out that even replacing the bias $r_W(\omega_i, \omega_{m(i)})$ with $r_W^{1+\gamma}(\omega_i, \omega_{m(i)})$ for some $\gamma > 0$ is impossible. In other words, no estimator $\hat{d}$ simultaneously satisfies the following inequalities, with high probability, over all graphons $(\Omega, \mu, W)$:

$$ \forall i, j \in [n]: $$

$$ \left| r_W^2(\omega_i, \omega_j) - \hat{d}^2(i, j) \right| \le C \left( r_W^{1+\gamma}(\omega_j, \omega_{m(j)}) + r_W^{1+\gamma}(\omega_i, \omega_{m(i)}) + \sqrt{\log(n)/n} \right) \quad (12) $$

where $C$ is a numerical constant. Indeed, Theorem 10 ensures that the uniform bound (12) cannot be achieved by any estimator $\hat{d}$ as soon as $\gamma > 0$, thus proving that the bias-dependence is linear ($\gamma = 0$) at best.

**Theorem 10** There exists a sequence of graphons $(\Omega, \mu, W_n)_{n \in \mathbb{N}}$ and some numerical constants $p > 0$, $\gamma \ge 0$ and $c > 0$, such that the following holds for any estimator $\hat{d}$ and any permutation $\sigma$ of the $n$ indices. With a probability larger than $p$, the following lower bound is satisfied for (at least) $c$ different pairs $(i, j)$,

$$ \left| r_{W_n}^2(\omega_i, \omega_j) - \hat{d}^2(\sigma(i), \sigma(j)) \right| \gtrsim \kappa_n(\gamma) \left( r_{W_n}^{1+\gamma}(\omega_j, \omega_{m(j)}) + r_{W_n}^{1+\gamma}(\omega_i, \omega_{m(i)}) + \sqrt{\frac{\log n}{n}} \right) $$

where $\kappa_n(\gamma) \xrightarrow{n} \infty$ as soon as $\gamma > 0$, and $\kappa_n(0) = O(1)$.

Theorem 8 is a direct consequence of Theorem 10 for $\gamma = 0$. The proof of Theorem 10 can be found in Appendix D.2.

In conclusion, the upper bounds in Theorem 7 have the right dependence on the bias.

### 4.2.1 DISCUSSION ABOUT THE DISTANCE ESTIMATION AND OPEN QUESTIONS

The lower bound in Theorem 8 only holds for $O(n)$ distances among the $O(n^2)$ ones. As to whether this could be extended to $O(n^2)$ distances, the question is left open. This generalization would confirm that the dependence on the bias should be linear and thus that the upper bounds of Theorem 7 have the optimal bias-dependence.

This gap may come from technical shortcomings of our proof, rather than an inherent feature of the estimation problem. Indeed, the instance of W-random graph constructed for the lower bounds, has only one outlier node whose $O(n)$ distances are incorrectly estimated. A possible difficulty for generalizing the proof to $O(n^2)$ distances is the randomness of the sample $\omega_1, \dots, \omega_n \stackrel{iid}{\sim} \mu$ and the symmetry of the matrix $A$, as they bring regularization effects to the problem.
Therefore, neither the lower bound of Theorem 8 nor the lower bound of Theorem 9 is enough informative to decipher whether the optimal rate is of the order of $r_W^2(\omega_i, \omega_{m(i)}) + \sqrt{\log(n)/n}$ or $r_W(\omega_i, \omega_{m(i)}) + \sqrt{\log(n)/n}$.

A quadratic dependency $r_W^2(\omega_i, \omega_{m(i)})$ would improve on the linear dependency since the neighborhood distance $r_W$ is always smaller than 1 by definition. Hence, one may wonder whether such an improvement is possible, especially that Theorem 7 is an error bound on square distances, $|r_W^2(\omega_i, \omega_j) - \hat{d}^2(i, j)|$. It turns out that even replacing the bias $r_W(\omega_i, \omega_{m(i)})$ with $r_W^{1+\gamma}(\omega_i, \omega_{m(i)})$ for some $\gamma > 0$ is impossible. In other words, no estimator $\hat{d}$ simultaneously satisfies the following inequalities, with high probability, over all graphons $(\Omega, \mu, W)$:

$$ \forall i, j \in [n] : $$

$$ |r_W^2(\omega_i, \omega_j) - \hat{d}^2(i, j)| \le C (r_W^{1+\gamma}(\omega_j, \omega_{m(j)}) + r_W^{1+\gamma}(\omega_i, \omega_{m(i)}) + \sqrt{\log(n)/n}) \quad (12) $$

where $C$ is a numerical constant. Indeed, Theorem 10 ensures that the uniform bound (12) cannot be achieved by any estimator $\hat{d}$ as soon as $\gamma > 0$, thus proving that the bias-dependence is linear ($\gamma = 0$) at best.

**Theorem 10** There exists a sequence of graphons $(\Omega, \mu, W_n)_{n \in \mathbb{N}}$ and some numerical constants $p > 0$, $\gamma \ge 0$ and $c > 0$, such that the following holds for any estimator $\hat{d}$ and any permutation $\sigma$ of the $n$ indices. With a probability larger than $p$, the following lower bound is satisfied for (at least) $c$ different pairs $(i, j)$,

$$ |r_{W_n}^2(\omega_i, \omega_j) - \hat{d}^2(\sigma(i), \sigma(j))| \gtrsim \kappa_n(\gamma) \left( r_{W_n}^{1+\gamma}(\omega_j, \omega_{m(j)}) + r_{W_n}^{1+\gamma}(\omega_i, \omega_{m(i)}) + \sqrt{\frac{\log n}{n}} \right) $$

$$ \text{where } \kappa_n(\gamma) \xrightarrow{n} \infty \text{ as soon as } \gamma > 0, \text{ and } \kappa_n(0) = O(1). $$

Theorem 8 is a direct consequence of Theorem 10 for $\gamma = 0$. The proof of Theorem 10 can be found in Appendix D.2.

In conclusion, the upper bounds in Theorem 7 have the right dependence on the bias.

### 4.2.1 DISCUSSION ABOUT THE DISTANCE ESTIMATION AND OPEN QUESTIONS

The lower bound in Theorem 8 only holds for $O(n)$ distances among the $O(n^2)$ ones. As to whether this could be extended to $O(n^2)$ distances, the question is left open. This generalization would confirm that the dependence on the bias should be linear and thus that the upper bounds of Theorem 7 have the optimal bias-dependence.

This gap may come from technical shortcomings of our proof, rather than an inherent feature of the estimation problem. Indeed, the instance of W-random graph constructed for the lower bounds, has only one outlier node whose $O(n)$ distances are incorrectly estimated. A possible difficulty for generalizing the proof to $O(n^2)$ distances is the randomness of the sample $\omega_1, \dots, \omega_n \stackrel{iid}{\sim} \mu$ and the symmetry of the matrix $A$, as they bring regularization effects to the problem.
Another element suggesting that the lower bounds in Theorem 8 may not be specific to one outlier, is that the upper bounds in Theorem 7 are not sensitive to $O(1)$ nodes. Indeed, by reading the proof of Theorem 7, one can observe that the upper bounds will not improve after removing $O(1)$ nodes.

Note that our lower bound has probably no direct consequences on graphon estimation since the bound only hinges on $O(1)$ outlier nodes, which would be negligible in the estimation of the probabilities matrix $[W(\omega_i, \omega_j)]_{1\le i,j\le n}$ with respect to the Frobenius norm.

The fluctuation term $f_n := \sqrt{\log(n)/n}$ in the upper bounds of Theorem 7 is natural, as each inner product is computed with $\Theta(n)$ entries, leading to an error $1/\sqrt{n}$, and the $\sqrt{\log(n)}$ allows us to show high probability bounds for each of the $\Theta(n^2)$ distances. However, this explanation is specific to our estimator, and the optimality of $f_n$ with respect to all estimators remains to be proved. The fact that $f_n$ appears in the lower bound of Theorem 8 does not prove that $f_n$ is inevitable since $f_n$ is actually negligible compared to the bias term $r_{W_n}(\omega_i, \omega_{m(i)})$ in this lower bound. Indeed, Theorem 8 is based on an instance of graphon $W_n$ satisfying $r_{W_n}(\omega_i, \omega_{m(i)}) \gtrsim f_n$.

## 4.3 Consistency of the Covering Number Estimator

We have defined the $\epsilon$-covering number estimator $\hat{N}_{\Omega}^{(c)}(\epsilon)$ as the covering number of the set $\{1, \dots, n\}$ w.r.t. the distance-estimator $\hat{r}$. Consider $e_{sup}$ the supremum of the errors of $\hat{r}$:

$$e_{sup} := \sup_{i,j \in [n]} |r_W(\omega_i, \omega_j) - \hat{r}(i, j)|.$$

Then, the covering number estimator is linked with the true covering number of $\{\omega_1, \dots, \omega_n\}$ by the following inequalities

$$\forall \epsilon > e_{sup}, \quad N_{\omega_1, \dots, \omega_n}^{(c)}(\epsilon + e_{sup}) \le \hat{N}_{\Omega}^{(c)}(\epsilon) \le N_{\omega_1, \dots, \omega_n}^{(c)}(\epsilon - e_{sup}).$$

To compare the covering numbers of $\{\omega_1, \dots, \omega_n\}$ and $\Omega$, we need to measure the difference between the sample $\omega_1, \dots, \omega_n$ and the space $\Omega$. We do so by introducing the sampling error $s_{\omega}$ defined as

$$s_{\omega} = \sup_{\omega \in \Omega} \inf_{i \in \{1, \dots, n\}} r_W(\omega, \omega_i) \quad (13)$$

which is the greatest distance that separates a point of $\Omega$ from the set $\{\omega_1, \dots, \omega_n\}$. Thus, the covering numbers (w.r.t. the true distance $r_W$) of $\omega_1, \dots, \omega_n$ and $\Omega$ are linked by the following inequalities

$$\forall \epsilon > s_{\omega}, \quad N_{\Omega}^{(c)}(\epsilon + s_{\omega}) \le N_{\omega_1, \dots, \omega_n}^{(c)}(\epsilon) \le N_{\Omega}^{(c)}(\epsilon - s_{\omega}).$$

Finally, for

$$b_{sup}^2 := 6 \sup_{i \in [n]} r_W(\omega_i, \omega_{m(i)}) + 36 \sqrt{\log(n)/n}, \quad (14)$$

Theorem 7 ensures that $e_{sup} \le b_{sup}$ with probability at least $1 - 2/n$. From the above displays, we obtain the following proposition.
Another element suggesting that the lower bounds in Theorem 8 may not be specific to one outlier, is that the upper bounds in Theorem 7 are not sensitive to $O(1)$ nodes. Indeed, by reading the proof of Theorem 7, one can observe that the upper bounds will not improve after removing $O(1)$ nodes.

Note that our lower bound has probably no direct consequences on graphon estimation since the bound only hinges on $O(1)$ outlier nodes, which would be negligible in the estimation of the probabilities matrix $[W(\omega_i, \omega_j)]_{1\le i,j\le n}$ with respect to the Frobenius norm.

The fluctuation term $f_n := \sqrt{\log(n)/n}$ in the upper bounds of Theorem 7 is natural, as each inner product is computed with $\Theta(n)$ entries, leading to an error $1/\sqrt{n}$, and the $\sqrt{\log(n)}$ allows us to show high probability bounds for each of the $\Theta(n^2)$ distances. However, this explanation is specific to our estimator, and the optimality of $f_n$ with respect to all estimators remains to be proved. The fact that $f_n$ appears in the lower bound of Theorem 8 does not prove that $f_n$ is inevitable since $f_n$ is actually negligible compared to the bias term $r_{W_n}(\omega_i, \omega_{m(i)})$ in this lower bound. Indeed, Theorem 8 is based on an instance of graphon $W_n$ satisfying $r_{W_n}(\omega_i, \omega_{m(i)}) \gtrsim f_n$.

## 4.3 Consistency of the Covering Number Estimator

We have defined the $\epsilon$-covering number estimator $\hat{N}_{\Omega}^{(c)}(\epsilon)$ as the covering number of the set $\{1, \dots, n\}$ w.r.t. the distance-estimator $\hat{r}$. Consider $e_{sup}$ the supremum of the errors of $\hat{r}$:

$$e_{sup} := \sup_{i,j \in [n]} |r_W(\omega_i, \omega_j) - \hat{r}(i, j)|.$$

Then, the covering number estimator is linked with the true covering number of $\{\omega_1, \dots, \omega_n\}$ by the following inequalities

$$\forall \epsilon > e_{sup}, \quad N_{\omega_1, \dots, \omega_n}^{(c)}(\epsilon + e_{sup}) \le \hat{N}_{\Omega}^{(c)}(\epsilon) \le N_{\omega_1, \dots, \omega_n}^{(c)}(\epsilon - e_{sup}).$$

To compare the covering numbers of $\{\omega_1, \dots, \omega_n\}$ and $\Omega$, we need to measure the difference between the sample $\omega_1, \dots, \omega_n$ and the space $\Omega$. We do so by introducing the sampling error $s_{\omega}$ defined as

$$s_{\omega} = \sup_{\omega \in \Omega} \inf_{i \in \{1, \dots, n\}} r_W(\omega, \omega_i) \quad (13)$$

which is the greatest distance that separates a point of $\Omega$ from the set $\{\omega_1, \dots, \omega_n\}$. Thus, the covering numbers (w.r.t. the true distance $r_W$) of $\omega_1, \dots, \omega_n$ and $\Omega$ are linked by the following inequalities

$$\forall \epsilon > s_{\omega}, \quad N_{\Omega}^{(c)}(\epsilon + s_{\omega}) \le N_{\omega_1, \dots, \omega_n}^{(c)}(\epsilon) \le N_{\Omega}^{(c)}(\epsilon - s_{\omega}).$$

Finally, for

$$b_{sup}^2 := 6 \sup_{i \in [n]} r_W(\omega_i, \omega_{m(i)}) + 36 \sqrt{\log(n)/n}, \quad (14)$$

Theorem 7 ensures that $e_{sup} \le b_{sup}$ with probability at least $1 - 2/n$. From the above displays, we obtain the following proposition.
**Proposition 11** Given any (pure) graphon $(\Omega, \mu, W)$, consider the data distribution $P_{(\Omega, \mu, W)}$ defined in model (3). Let $b_{sup}$ and $s_{\omega}$ be the distance error bound (14) and the sampling error (13). Then, the estimator $\hat{N}_{\Omega}^{(c)}$ satisfies the following non-asymptotic bounds

$$ \forall \epsilon > b_{sup} + s_{\omega}, \quad N_{\Omega}^{(c)}(\epsilon + b_{sup} + s_{\omega}) \le \hat{N}_{\Omega}^{(c)}(\epsilon) \le N_{\Omega}^{(c)}(\epsilon - b_{sup} - s_{\omega}) \quad (15) $$

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

As a result, we have a consistent estimation of the $\epsilon$-covering number for almost every $\epsilon$, provided that the covering number is finite for all radii. Indeed, if $N_{\Omega}^{(c)}(\epsilon) < \infty$ for all $\epsilon > 0$, then the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in $(\Omega, r_W)$ by Lemma 5, which implies that $b_{sup}$ and $s_{\omega}$ converge in probability to zero; Then, taking the limit $n \to \infty$ in (15), one has the convergence in probability of $\hat{N}_{\Omega}^{(c)}$ towards $N_{\Omega}^{(c)}(\epsilon)$, for all $\epsilon$ where the step function $\epsilon \mapsto N_{\Omega}^{(c)}(\epsilon)$ is continuous (i.e., for almost every $\epsilon$).

## 4.4 Consistency of the Dimension Estimator

We estimate the Minkowski dimension of $(\Omega, r_W)$ using the data-function $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$ at a well chosen radius $\epsilon$. The following observation makes it clear that each graphon requires a specific choice of radius, and thus no (universal) radius is suited for all graphons.

**OBSERVATION.** (1) at very small scale (i.e. very small $\epsilon$), the covering number may just count the points of the sample $\omega_1, \dots, \omega_n$ and the data look zero-dimensional; (2) if the scale is comparable to the noise due to the distance estimation, the covering number estimator $\hat{N}_{\Omega}^{(c)}(\epsilon)$ is not reliable; (3) for an intermediate scale, it is possible to have a good estimation of the dimension, as we shall see in Theorem 12; (4) at very big scale, the apparent geometry may not reflect the Minkowski dimension (which is, by definition, a measure of the complexity at infinitesimal scale).

Hence, we consider a subset of graphons for which there exists a radius that is well-suited for dimension estimation. We sometimes denote $dim \Omega$ by $d$ for brevity, and write $B(\omega, \epsilon)$ the ball of center $\omega \in \Omega$ with radius $\epsilon$ (w.r.t. the neighborhood distance). Given constants $D, v, \alpha > 0$ and $M \ge 1 \ge m > 0$, we define the set $W(D, \alpha, m, M, v)$ of all (pure) graphons $(\Omega, \mu, W)$ satisfying

1. $dim \Omega \le D$.

2. For $dim \Omega := d$ and all $\epsilon \in (0, v]$,

$$ \alpha \epsilon^d \le \mu [B(\omega, \epsilon)] \quad (H_1^{\alpha, v}) $$

$$ m\epsilon^{-d} \le N_{\Omega}^{(c)}(\epsilon) \le M\epsilon^{-d}. \quad (H_2^{m,M,v}) $$

The assumption $H_2^{m,M,v}$ links the covering number with the Minkowski dimension of the graphon. The condition $H_1^{\alpha,v}$ enforces a minimal measure for each ball of $(\Omega, r_W)$; in
**Proposition 11** Given any (pure) graphon $(\Omega, \mu, W)$, consider the data distribution $P_{(\Omega, \mu, W)}$ defined in model (3). Let $b_{sup}$ and $s_{\omega}$ be the distance error bound (14) and the sampling error (13). Then, the estimator $\hat{N}_{\Omega}^{(c)}$ satisfies the following non-asymptotic bounds

$$ \forall \epsilon > b_{sup} + s_{\omega}, \quad N_{\Omega}^{(c)}(\epsilon + b_{sup} + s_{\omega}) \le \hat{N}_{\Omega}^{(c)}(\epsilon) \le N_{\Omega}^{(c)}(\epsilon - b_{sup} - s_{\omega}) \quad (15) $$

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

As a result, we have a consistent estimation of the $\epsilon$-covering number for almost every $\epsilon$, provided that the covering number is finite for all radii. Indeed, if $N_{\Omega}^{(c)}(\epsilon) < \infty$ for all $\epsilon > 0$, then the sample $\omega_1, \dots, \omega_n$ is asymptotically dense in $(\Omega, r_W)$ by Lemma 5, which implies that $b_{sup}$ and $s_{\omega}$ converge in probability to zero; Then, taking the limit $n \to \infty$ in (15), one has the convergence in probability of $\hat{N}_{\Omega}^{(c)}$ towards $N_{\Omega}^{(c)}(\epsilon)$, for all $\epsilon$ where the step function $\epsilon \mapsto N_{\Omega}^{(c)}(\epsilon)$ is continuous (i.e., for almost every $\epsilon$).

## 4.4 Consistency of the Dimension Estimator

We estimate the Minkowski dimension of $(\Omega, r_W)$ using the data-function $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$ at a well chosen radius $\epsilon$. The following observation makes it clear that each graphon requires a specific choice of radius, and thus no (universal) radius is suited for all graphons.

**OBSERVATION.** (1) at very small scale (i.e. very small $\epsilon$), the covering number may just count the points of the sample $\omega_1, \dots, \omega_n$ and the data look zero-dimensional; (2) if the scale is comparable to the noise due to the distance estimation, the covering number estimator $\hat{N}_{\Omega}^{(c)}(\epsilon)$ is not reliable; (3) for an intermediate scale, it is possible to have a good estimation of the dimension, as we shall see in Theorem 12; (4) at very big scale, the apparent geometry may not reflect the Minkowski dimension (which is, by definition, a measure of the complexity at infinitesimal scale).

Hence, we consider a subset of graphons for which there exists a radius that is well-suited for dimension estimation. We sometimes denote $dim \Omega$ by $d$ for brevity, and write $B(\omega, \epsilon)$ the ball of center $\omega \in \Omega$ with radius $\epsilon$ (w.r.t. the neighborhood distance). Given constants $D, v, \alpha > 0$ and $M \ge 1 \ge m > 0$, we define the set $W(D, \alpha, m, M, v)$ of all (pure) graphons $(\Omega, \mu, W)$ satisfying

1. $dim \Omega \le D$.

2. For $dim \Omega := d$ and all $\epsilon \in (0, v]$,

$$ \alpha \epsilon^d \le \mu[B(\omega, \epsilon)] \quad (H_1^{\alpha, v}) $$

$$ m\epsilon^{-d} \le N_{\Omega}^{(c)}(\epsilon) \le M\epsilon^{-d}. \quad (H_2^{m,M,v}) $$

The assumption $H_2^{m,M,v}$ links the covering number with the Minkowski dimension of the graphon. The condition $H_1^{\alpha,v}$ enforces a minimal measure for each ball of $(\Omega, r_W)$; in
particular, it strengthens the non-zero measure of balls of pure graphons, seen in Section 3.1. Mention can be made of the problem of recovery of the dimension of a manifold, where similar hypotheses are often considered (see Koltchinskii, 2000, for example). Besides, $H_1^{\alpha, v}$ may be seen as a small-ball condition used in learning problems (Mendelson, 2014; Lecué et al., 2018).

With the radius

$$ \epsilon_D \asymp \left( \frac{\log n}{n} \right)^{1/(4\sqrt{2D})} \qquad (16) $$

we consistently estimate the Minkowski dimension (Theorem 12) using the following estimator

$$ \widehat{dim}_D := \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon_D)}{-\log \epsilon_D}. \qquad (17) $$

**Theorem 12** For all graphons $(\Omega, \mu, W)$ in $W(D, \alpha, m, M, v)$ and all large enough $n$, we have

$$ |\widehat{dim}_D - dim \Omega| \le \frac{C(D, \alpha, m, M)}{\log n} $$

with probability at least $1 - C'(\alpha, M)/n$ w.r.t. the distribution $P_{(\Omega, \mu, W)}$, and for some constants $C'(\alpha, M)$ and $C(D, \alpha, m, M)$ that are independent of $n$.

Theorem 12 is a corollary of Theorem 35 in Appendix E.1, which gives a non-asymptotic high probability bound for $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$ at any radius $\epsilon$.

One can observe that the convergence rate $\log^{-1} n$ of Theorem 12 is optimal, in the sense that faster convergence rates cannot be achieved by any estimator of the form $\log \hat{N}_{\Omega}^{(c)}(\hat{\epsilon})/ - \log \hat{\epsilon}^1$. To see it, take a graphon of dimension $d > 1$ with covering number $N_{\Omega}^{(c)}(\epsilon) = m\epsilon^{-d}$ for some constant $m > 1$. Even if there exists a covering number estimator that gives a perfect estimation, i.e. $\hat{N}_{\Omega}^{(c)} = N_{\Omega}^{(c)}$, this still entails an error for the dimension estimation. Indeed, in such a case we have:

$$ \left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \right| = \frac{\log m}{-\log \epsilon} $$

which is (at least) of the order $\log^{-1} n$ since the radius $\epsilon$ cannot be taken smaller than $n^{-1}$ in general (otherwise, the estimator of the covering number may just count the $n$ sampled points). Thus, the convergence rate $\log^{-1} n$ is optimal for the classical method of estimation of the Minkowski dimension, which is based on the the plug-in of a covering number estimate into formula (5).

Next we show that no estimator $^2$ can improve on the error bound $\log^{-1} n$, over the following sequence of sets. Given $n > 0$, let $W_n(D, \alpha, m, M, v)$ be the class of all (pure)

<footnote n="1">1. $\hat{N}_{\Omega}^{(c)}$ is any consistent estimator of the covering number, and $\hat{\epsilon}$ is any estimator of a “well chosen radius”.</footnote>

<footnote n="2">2. An estimator is defined as a function of the adjacency matrix $A \in \{0, 1\}^{n \times n}$.</footnote>
particular, it strengthens the non-zero measure of balls of pure graphons, seen in Section 3.1. Mention can be made of the problem of recovery of the dimension of a manifold, where similar hypotheses are often considered (see Koltchinskii, 2000, for example). Besides, $H_1^{\alpha, v}$ may be seen as a small-ball condition used in learning problems (Mendelson, 2014; Lecué et al., 2018).

With the radius

$$ \epsilon_D \asymp \left( \frac{\log n}{n} \right)^{1/(4\sqrt{2D})} \qquad (16) $$

we consistently estimate the Minkowski dimension (Theorem 12) using the following estimator

$$ \widehat{dim}_D := \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon_D)}{-\log \epsilon_D}. \qquad (17) $$

**Theorem 12** For all graphons $(\Omega, \mu, W)$ in $W(D, \alpha, m, M, v)$ and all large enough $n$, we have

$$ |\widehat{dim}_D - dim \Omega| \le \frac{C(D, \alpha, m, M)}{\log n} $$

with probability at least $1 - C'(\alpha, M)/n$ w.r.t. the distribution $P_{(\Omega, \mu, W)}$, and for some constants $C'(\alpha, M)$ and $C(D, \alpha, m, M)$ that are independent of $n$.

Theorem 12 is a corollary of Theorem 35 in Appendix E.1, which gives a non-asymptotic high probability bound for $-\log \hat{N}_{\Omega}^{(c)}(\epsilon)/\log \epsilon$ at any radius $\epsilon$.

One can observe that the convergence rate $\log^{-1} n$ of Theorem 12 is optimal, in the sense that faster convergence rates cannot be achieved by any estimator of the form $\log \hat{N}_{\Omega}^{(c)}(\hat{\epsilon})/ - \log \hat{\epsilon}^1$. To see it, take a graphon of dimension $d > 1$ with covering number $N_{\Omega}^{(c)}(\epsilon) = m\epsilon^{-d}$ for some constant $m > 1$. Even if there exists a covering number estimator that gives a perfect estimation, i.e. $\hat{N}_{\Omega}^{(c)} = N_{\Omega}^{(c)}$, this still entails an error for the dimension estimation. Indeed, in such a case we have:

$$ \left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon)}{-\log \epsilon} - d \right| = \frac{\log m}{-\log \epsilon} $$

which is (at least) of the order $\log^{-1} n$ since the radius $\epsilon$ cannot be taken smaller than $n^{-1}$ in general (otherwise, the estimator of the covering number may just count the $n$ sampled points). Thus, the convergence rate $\log^{-1} n$ is optimal for the classical method of estimation of the Minkowski dimension, which is based on the the plug-in of a covering number estimate into formula (5).

Next we show that no estimator $^2$ can improve on the error bound $\log^{-1} n$, over the following sequence of sets. Given $n > 0$, let $W_n(D, \alpha, m, M, v)$ be the class of all (pure)

<footnote n="1">1. $\hat{N}_{\Omega}^{(c)}$ is any consistent estimator of the covering number, and $\hat{\epsilon}$ is any estimator of a “well chosen radius”.</footnote>

<footnote n="2">2. An estimator is defined as a function of the adjacency matrix $A \in \{0, 1\}^{n \times n}$.</footnote>
graphons fulfilling $H_1^{\alpha,v}$ and $H_2^{m,M,v}$ for all $\epsilon \in (1/n, v]$ instead of $\epsilon \in (0, v]$, so $W_n(D, \alpha, m, M, v)$ is a subset of $W(D, \alpha, m, M, v)$. On this sequence of sets, one can readily extend Theorem 12 and retrieve the same error bound, using the same estimator (17). This means that there exist some constants $C(D, \alpha, m, M)$ and $C'(\alpha, M)$ that are independent of $n$, such that for all graphons in $W_n(D, \alpha, m, M, v)$ and all large enough $n$, the following error bound holds

$$ \left| \widehat{dim}_D - dim \Omega \right| \le \frac{C(D, \alpha, m, M)}{\log n} \qquad (18) $$

with probability at least $1 - C'(\alpha, M)/n$. Then, Theorem 13 shows that no estimator can improve on the (order of the) bound (18). The proof is written in Appendix E.2.2.

**Theorem 13** For any $D > 2$, some numerical constants $\alpha, m, M, v > 0$ and all large enough $n$, we have

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

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

Let us discuss the minimal aspect of the conditions defining $W_n(D, \alpha, m, M, v)$. First, the assumption that the dimension is upper bounded seems natural, as our available data $A \in \{0, 1\}^{n \times n}$ is a finite set. Indeed, for metric spaces $(\Omega_n, r_{W_n})$ with arbitrary large dimensions (like $dim \Omega_n/n \to \infty$ for instance), a finite sample $\omega_1, \dots, \omega_n$ may look like a set of distant and isolated points, which does not reflect the true geometry of $(\Omega_n, r_{W_n})$. Since this situation is not conducive to accurate estimates of the complexity of $\Omega_n$, we avoid it by assuming the dimension is upper bounded. Second, we show that the assumptions $H_1^{\alpha,v}$ and $H_2^{m,M,v}$ are minimal, in the sense that, removing any one of them entails a large loss for any estimator. Specifically, let $W_n^{min(j)}(D, \alpha, m, M, v)$ be the collection of all (pure) graphons satisfying all conditions of the set $W_n(D, \alpha, m, M, v)$ except the condition $H_j$ (where $H_j$ denotes $H_1^{\alpha,v}$ or $H_2^{m,M,v}$ according to the value of $j \in \{1, 2\}$). Then, Theorem 14 shows that any estimator suffers from an error of the order $D$, over the class $W_n^{min(j)}(D, \alpha, m, M, v)$. The proof is written in Appendix E.2.2.

**Theorem 14** For any $D > 2$, some numerical constants $\alpha, m, M, v > 0$, all $j \in \{1, 2\}$ and all large enough $n$, we have

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

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

**REMARK:** our optimal rate of estimation may seem at odds with the faster rates of convergence in the literature about intrinsic dimension estimation, see (Kim et al., 2016)
graphons fulfilling $H_1^{\alpha,v}$ and $H_2^{m,M,v}$ for all $\epsilon \in (1/n, v]$ instead of $\epsilon \in (0, v]$, so $W_n(D, \alpha, m, M, v)$ is a subset of $W(D, \alpha, m, M, v)$. On this sequence of sets, one can readily extend Theorem 12 and retrieve the same error bound, using the same estimator (17). This means that there exist some constants $C(D, \alpha, m, M)$ and $C'(\alpha, M)$ that are independent of $n$, such that for all graphons in $W_n(D, \alpha, m, M, v)$ and all large enough $n$, the following error bound holds

$$ \left| \widehat{dim}_D - dim \Omega \right| \le \frac{C(D, \alpha, m, M)}{\log n} \quad (18) $$

with probability at least $1 - C'(\alpha, M)/n$. Then, Theorem 13 shows that no estimator can improve on the (order of the) bound (18). The proof is written in Appendix E.2.2.

**Theorem 13** For any $D > 2$, some numerical constants $\alpha, m, M, v > 0$ and all large enough $n$, we have

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

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

Let us discuss the minimal aspect of the conditions defining $W_n(D, \alpha, m, M, v)$. First, the assumption that the dimension is upper bounded seems natural, as our available data $A \in \{0, 1\}^{n \times n}$ is a finite set. Indeed, for metric spaces $(\Omega_n, r_{W_n})$ with arbitrary large dimensions (like $dim \Omega_n/n \to \infty$ for instance), a finite sample $\omega_1, \dots, \omega_n$ may look like a set of distant and isolated points, which does not reflect the true geometry of $(\Omega_n, r_{W_n})$. Since this situation is not conducive to accurate estimates of the complexity of $\Omega_n$, we avoid it by assuming the dimension is upper bounded. Second, we show that the assumptions $H_1^{\alpha,v}$ and $H_2^{m,M,v}$ are minimal, in the sense that, removing any one of them entails a large loss for any estimator. Specifically, let $W_n^{min(j)}(D, \alpha, m, M, v)$ be the collection of all (pure) graphons satisfying all conditions of the set $W_n(D, \alpha, m, M, v)$ except the condition $H_j$ (where $H_j$ denotes $H_1^{\alpha,v}$ or $H_2^{m,M,v}$ according to the value of $j \in \{1, 2\}$). Then, Theorem 14 shows that any estimator suffers from an error of the order $D$, over the class $W_n^{min(j)}(D, \alpha, m, M, v)$. The proof is written in Appendix E.2.2.

**Theorem 14** For any $D > 2$, some numerical constants $\alpha, m, M, v > 0$, all $j \in \{1, 2\}$ and all large enough $n$, we have

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

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

**REMARK:** our optimal rate of estimation may seem at odds with the faster rates of convergence in the literature about intrinsic dimension estimation, see (Kim et al., 2016)
for instance. This is due to the important differences in the modeling assumptions. In the work of Kim et al. (2016), for example, the observed data are n i.i.d. sampled points from a well-behaved manifold in $\mathbb{R}^m$ whose dimension is an integer. In contrast, here we do not assume the dimension is an integer, we do not observe the n sampled points $\omega_1, \dots, \omega_n$, and do not know the metric $r_W$.

**COMMENTS ON $H_1^{\alpha,v}$, $H_2^{m,M,v}$**: we only make the assumptions $H_1^{\alpha,v}$, $H_2^{m,M,v}$ at a small scale, that is for $\epsilon \in (0, v]$. Besides, the right hand side of $H_2^{m,M,v}$ is almost free since it is already implied by $H_1^{\alpha,v}$ for $M = 2^d/\alpha$. Let us briefly explain how these assumptions imply the error bound of Theorem 12. The assumption $H_1^{\alpha,v}$ ensures that the difference between the sampled points $\omega_1, \dots, \omega_n$ and the latent space $\Omega$ is not too large. By definition, this implies that the sampling error (13) and the distance error (14) are small. Accordingly, we can choose a radius $\epsilon_D$ that is larger than these two errors, and reliably estimate the $\epsilon_D$-covering number $N_{\Omega}^{(c)}(\epsilon_D)$ by Proposition 11. Then, we use a plug-in to estimate the quantity $-\log N_{\Omega}^{(c)}(\epsilon_D)/\log \epsilon_D$, which is a good approximation of the dimension by assumption $H_2^{m,M,v}$. To sum up, the radius $\epsilon_D$ must be larger than the sampling and distance errors, but still small enough to well approximate the Minkowski dimension with $-\log N_{\Omega}^{(c)}(\epsilon_D)/\log \epsilon_D$.

# 5. Testing the Complexity

Given the adjacency matrix of a W-random graph, we want to know if the graph is simple or complex. In other words, we would like to test the null-hypothesis $N_{\Omega}^{(c)}(\epsilon) \le K$ for a given $K > 0$, with a specific care for minimizing the assumptions on the graphon. However, instead of using the covering number we use the packing number $N_{\Omega}^{(p)}(\epsilon)$ for some reasons to be specified in Section 5.1. For now, note that it is essentially the same measure as the covering number, and all previous results of the paper can be adapted to the packing number (without any significant difference). See Appendix A for a reminder of this usual measure for metric spaces.

In hypothesis testing, it is common to be conservative and focus on the minimization of the type I error, which is the probability of rejecting the null-hypothesis incorrectly. Accordingly, our objective is to control the type I error without any assumption on the graphon, while keeping a control of the type II error under reasonable assumptions. (the type II error is the probability of accepting the null-hypothesis incorrectly)

## 5.1 Testing the Null-hypothesis without Assumption on the Graphon, via Under-estimation of the Packing Number

To test the null-hypothesis without assumption on the graphon, we want to define a complexity estimator that does not overestimate the true complexity w.h.p.. Unfortunately, the inequality on the covering number estimator from Proposition 11

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

is difficult to leverage for an under-estimation since the errors $b_{sup}$ and $s_{\omega}$ are unknown and take specific values for each graphon. However, we show below that the sampling error
for instance. This is due to the important differences in the modeling assumptions. In the work of Kim et al. (2016), for example, the observed data are n i.i.d. sampled points from a well-behaved manifold in $\mathbb{R}^m$ whose dimension is an integer. In contrast, here we do not assume the dimension is an integer, we do not observe the n sampled points $\omega_1, \dots, \omega_n$, and do not know the metric $r_W$.

**COMMENTS ON $H_1^{\alpha,v}$, $H_2^{m,M,v}$**: we only make the assumptions $H_1^{\alpha,v}$, $H_2^{m,M,v}$ at a small scale, that is for $\epsilon \in (0, v]$. Besides, the right hand side of $H_2^{m,M,v}$ is almost free since it is already implied by $H_1^{\alpha,v}$ for $M = 2^d/\alpha$. Let us briefly explain how these assumptions imply the error bound of Theorem 12. The assumption $H_1^{\alpha,v}$ ensures that the difference between the sampled points $\omega_1, \dots, \omega_n$ and the latent space $\Omega$ is not too large. By definition, this implies that the sampling error (13) and the distance error (14) are small. Accordingly, we can choose a radius $\epsilon_D$ that is larger than these two errors, and reliably estimate the $\epsilon_D$-covering number $N_{\Omega}^{(c)}(\epsilon_D)$ by Proposition 11. Then, we use a plug-in to estimate the quantity $-\log N_{\Omega}^{(c)}(\epsilon_D)/\log \epsilon_D$, which is a good approximation of the dimension by assumption $H_2^{m,M,v}$. To sum up, the radius $\epsilon_D$ must be larger than the sampling and distance errors, but still small enough to well approximate the Minkowski dimension with $-\log N_{\Omega}^{(c)}(\epsilon_D)/\log \epsilon_D$.

# 5. Testing the Complexity

Given the adjacency matrix of a W-random graph, we want to know if the graph is simple or complex. In other words, we would like to test the null-hypothesis $N_{\Omega}^{(c)}(\epsilon) \le K$ for a given $K > 0$, with a specific care for minimizing the assumptions on the graphon. However, instead of using the covering number we use the packing number $N_{\Omega}^{(p)}(\epsilon)$ for some reasons to be specified in Section 5.1. For now, note that it is essentially the same measure as the covering number, and all previous results of the paper can be adapted to the packing number (without any significant difference). See Appendix A for a reminder of this usual measure for metric spaces.

In hypothesis testing, it is common to be conservative and focus on the minimization of the type I error, which is the probability of rejecting the null-hypothesis incorrectly. Accordingly, our objective is to control the type I error without any assumption on the graphon, while keeping a control of the type II error under reasonable assumptions. (the type II error is the probability of accepting the null-hypothesis incorrectly)

## 5.1 Testing the Null-hypothesis without Assumption on the Graphon, via Under-estimation of the Packing Number

To test the null-hypothesis without assumption on the graphon, we want to define a complexity estimator that does not overestimate the true complexity w.h.p.. Unfortunately, the inequality on the covering number estimator from Proposition 11

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

is difficult to leverage for an under-estimation since the errors $b_{sup}$ and $s_{\omega}$ are unknown and take specific values for each graphon. However, we show below that the sampling error
$s_\omega$ can be removed, by working with the packing number instead of the covering number. Then, we show that the distance error bound $b_{sup}$ can be handled with a slight modification of the distance-estimator $\hat{r}$, defined earlier by (11).

Based on the distance estimator $\hat{r}$, we can define a plug-in estimator $\hat{N}_{\Omega}^{(p)}(\epsilon)$ of the packing number, as we did for the covering number estimator. This estimator satisfies almost the same non-asymptotic bounds as the covering number estimator, see the following proposition, which is a slight variant of Proposition 11. The proof is omitted.

**Proposition 15** Given any graphon $(\Omega, \mu, W)$, consider the data distribution $P_{(\Omega, \mu, W)}$ defined in model (3). Let $b_{sup}$ and $s_\omega$ be the distance error bound (14) and the sampling error (13). Then, the packing number estimator $\hat{N}_{\Omega}^{(p)}$ satisfies the following inequalities

$$ \forall \epsilon > b_{sup}, \quad N_{\Omega}^{(p)}(\epsilon + b_{sup} + 2s_{\omega}) \le \hat{N}_{\Omega}^{(p)}(\epsilon) \le N_{\Omega}^{(p)}(\epsilon - b_{sup}) $$

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

Hence, we have

$$ \hat{N}_{\Omega}^{(p)}(\epsilon + b_{sup}) \le N_{\Omega}^{(p)}(\epsilon) $$

without the sampling error $s_\omega$ anymore.

The next step is to control the remaining error term $b_{sup}$ coming from the estimator $\hat{r}$. Obviously, when $b_{sup}$ is positive and relatively large, the estimator $\hat{r}$ over-estimates some distances, and thus the plug-in estimator $\hat{N}_{\Omega}^{(p)}$ based on $\hat{r}$ may over-estimate the packing number. In order to avoid such an over-estimation, we modify the previous estimator $\hat{r}$, by taking a maximum in front of the negative term involved in (the expression of) $\hat{r}^2$:

$$ \hat{r}_{new}^2(i, j) := \left[ \langle A_i, A_{\hat{m}(i)} \rangle_n + \langle A_j, A_{\hat{m}(j)} \rangle_n - 2 \max_{k \in \{i, \hat{m}(i)\}, l \in \{j, \hat{m}(j)\}} \langle A_k, A_l \rangle_n \right]_+ \quad (19) $$

We show in Appendix G.1 that the new distance estimator $\hat{r}_{new}$ satisfies the same upper bound as $\hat{r}$ in Theorem 7 (up to a numerical constant 5/3) but also successfully underestimates the neighborhood distance $r_W$ in some sense (see Lemma 42 for details). Then, defining a new packing number estimator based on $\hat{r}_{new}$, which is denoted by $\hat{N}_{\Omega}^{(p.new)}$ in the following, we finally get the wanted under-estimation of the packing number, see Theorem 16 below. The proof is written in Appendix G.1.

**Theorem 16** Given any graphon $(\Omega, \mu, W)$, consider the data distribution $P_{(\Omega, \mu, W)}$ defined in model (3). Then, for the radius $\hat{\epsilon} = \sqrt{\epsilon^2 + t_n}$ with $t_n = 12 \sqrt{\frac{\log n}{n}}$, the estimator $\hat{N}_{\Omega}^{(p.new)}$ satisfies the following inequalities

$$ \forall \epsilon > 0, \quad N_{\Omega}^{(p)}\left(\hat{\epsilon} + \frac{5}{3}b_{sup} + 2s_{\omega}\right) \le \hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon}) \le N_{\Omega}^{(p)}(\epsilon) \quad (20) $$

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

Thus, without any assumption on the graphon, the estimator $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon})$ does not overestimate the $\epsilon$-packing number with high probability. Besides, the left hand side of (20) shows that it does not under-estimate (significantly) more than the previous estimator $\hat{N}_{\Omega}^{(p)}$ of the packing number (seen in Proposition 15).
$s_\omega$ can be removed, by working with the packing number instead of the covering number. Then, we show that the distance error bound $b_{sup}$ can be handled with a slight modification of the distance-estimator $\hat{r}$, defined earlier by (11).

Based on the distance estimator $\hat{r}$, we can define a plug-in estimator $\hat{N}_{\Omega}^{(p)}(\epsilon)$ of the packing number, as we did for the covering number estimator. This estimator satisfies almost the same non-asymptotic bounds as the covering number estimator, see the following proposition, which is a slight variant of Proposition 11. The proof is omitted.

**Proposition 15** Given any graphon $(\Omega, \mu, W)$, consider the data distribution $P_{(\Omega, \mu, W)}$ defined in model (3). Let $b_{sup}$ and $s_\omega$ be the distance error bound (14) and the sampling error (13). Then, the packing number estimator $\hat{N}_{\Omega}^{(p)}$ satisfies the following inequalities

$$ \forall \epsilon > b_{sup}, \quad N_{\Omega}^{(p)}(\epsilon + b_{sup} + 2s_{\omega}) \le \hat{N}_{\Omega}^{(p)}(\epsilon) \le N_{\Omega}^{(p)}(\epsilon - b_{sup}) $$

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

Hence, we have

$$ \hat{N}_{\Omega}^{(p)}(\epsilon + b_{sup}) \le N_{\Omega}^{(p)}(\epsilon) $$

without the sampling error $s_\omega$ anymore.

The next step is to control the remaining error term $b_{sup}$ coming from the estimator $\hat{r}$. Obviously, when $b_{sup}$ is positive and relatively large, the estimator $\hat{r}$ over-estimates some distances, and thus the plug-in estimator $\hat{N}_{\Omega}^{(p)}$ based on $\hat{r}$ may over-estimate the packing number. In order to avoid such an over-estimation, we modify the previous estimator $\hat{r}$, by taking a maximum in front of the negative term involved in (the expression of) $\hat{r}^2$:

$$ \hat{r}_{new}^2(i, j) := \left[ \langle A_i, A_{\hat{m}(i)} \rangle_n + \langle A_j, A_{\hat{m}(j)} \rangle_n - 2 \max_{k \in \{i, \hat{m}(i)\}, l \in \{j, \hat{m}(j)\}} \langle A_k, A_l \rangle_n \right]_+ \quad (19) $$

We show in Appendix G.1 that the new distance estimator $\hat{r}_{new}$ satisfies the same upper bound as $\hat{r}$ in Theorem 7 (up to a numerical constant 5/3) but also successfully under-estimates the neighborhood distance $r_W$ in some sense (see Lemma 42 for details). Then, defining a new packing number estimator based on $\hat{r}_{new}$, which is denoted by $\hat{N}_{\Omega}^{(p.new)}$ in the following, we finally get the wanted under-estimation of the packing number, see Theorem 16 below. The proof is written in Appendix G.1.

**Theorem 16** Given any graphon $(\Omega, \mu, W)$, consider the data distribution $P_{(\Omega, \mu, W)}$ defined in model (3). Then, for the radius $\hat{\epsilon} = \sqrt{\epsilon^2 + t_n}$ with $t_n = 12 \sqrt{\frac{\log n}{n}}$, the estimator $\hat{N}_{\Omega}^{(p.new)}$ satisfies the following inequalities

$$ \forall \epsilon > 0, \quad N_{\Omega}^{(p)}\left(\hat{\epsilon} + \frac{5}{3}b_{sup} + 2s_{\omega}\right) \le \hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon}) \le N_{\Omega}^{(p)}(\epsilon) \quad (20) $$

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

Thus, without any assumption on the graphon, the estimator $\hat{N}_{\Omega}^{(p.new)}(\hat{\epsilon})$ does not overestimate the $\epsilon$-packing number with high probability. Besides, the left hand side of (20) shows that it does not under-estimate (significantly) more than the previous estimator $\hat{N}_{\Omega}^{(p)}$ of the packing number (seen in Proposition 15).
## 5.2 Results on the Packing Number Test

We accept the null hypothesis if and only if $\hat{N}_{\Omega}^{(p.new)}(\epsilon) \le K$. The upper bound (20) ensures that the type I error is controlled for all graphons, which gives the following result.

**Corollary 17** For any graphon, the type I error is lower than $\frac{2}{n}$ with respect to the distribution $P_{(\Omega, \mu, W)}$.

By definition of the packing number, the type II error is small as soon as $K+1$ sampled points are separated by at least a distance $\epsilon + \text{err}$, where $\text{err}$ upper bounds all errors of distance estimation between the $K+1$ points. This condition on the sampled points is satisfied w.h.p. by each of the following graphons.

Given two parameters $\eta > 0$ and $\beta > 1/n$, let $W(\eta, \beta)$ denote a collection of graphons for which there exist $K+1$ balls $B(x_1, \eta_1), \dots, B(x_{K+1}, \eta_{K+1})$ in $(\Omega, r_W)$ such that

1. the $K+1$ balls are weighted enough: $\mu[B(x_i, \eta_i)] \ge \beta$ for all $i \in [K+1]$,

2. the radii are small enough: $\eta_i \le \eta/2$ for all $i \in [K+1]$,

3. the centers are spaced enough: $r_W(x_i, x_j) \ge \sqrt{\epsilon^2 + 10\eta + 6t_n} + \eta$.

The small-ball condition 1. is similar to the assumption $H_1^{\alpha, v}$ for the dimension estimation; it ensures that some of the sampled points $\omega_1, \dots, \omega_n$ belong to the $K+1$ balls w.h.p.. The third condition 3. ensures that these balls are enough distant from each other, so that the sampled points in these balls are separated enough, in order to have $\hat{N}_{\Omega}^{(p.new)}(\epsilon) \ge K+1$ and confirm the alternative hypothesis correctly.

**Theorem 18** Assume the graphon $(\Omega, \mu, W)$ belongs to $W(\eta, \beta)$ for some $\beta > 1/n$. Then, the type II error is smaller than

$$ \frac{2}{n} + 2\beta n(K+1) \exp[-\beta(n-1)] $$

with respect to the distribution $P_{(\Omega, \mu, W)}$.

The proof of Theorem 18 is written in Appendix G.2.2. This result implies that, for any graphon in $W(\eta, \beta)$, the type II error is convergent to zero as soon as the measure of each ball $B(x_i, \eta_i)$ is large enough to satisfy $\beta \ge n^{-1}$. For example, if each of the $K+1$ balls has a measure that is larger than $\log[Kn]/n$, then the type II error is smaller than $\log(n)/n$ up to some numerical constant. In Appendix A.3, Theorem 18 is improved by using the graphon regularity at a finer level (see Theorem 21).

# 6. Further Considerations

## 6.1 Estimation of the Complexity with Sparse Observations

In the W-random graph model (3), each node has an average degree that is linear with $n$ the total number of nodes. However, real-world networks are often sparse with node degrees varying from zero to $n$. This motivates to consider a model of sparse graph where the node degree can be an order of magnitude smaller than $n$.
## 5.2 Results on the Packing Number Test

We accept the null hypothesis if and only if $\hat{N}_{\Omega}^{(p.new)}(\epsilon) \le K$. The upper bound (20) ensures that the type I error is controlled for all graphons, which gives the following result.

**Corollary 17** For any graphon, the type I error is lower than $\frac{2}{n}$ with respect to the distribution $P_{(\Omega, \mu, W)}$.

By definition of the packing number, the type II error is small as soon as $K+1$ sampled points are separated by at least a distance $\epsilon + err$, where $err$ upper bounds all errors of distance estimation between the $K+1$ points. This condition on the sampled points is satisfied w.h.p. by each of the following graphons.

Given two parameters $\eta > 0$ and $\beta > 1/n$, let $W(\eta, \beta)$ denote a collection of graphons for which there exist $K+1$ balls $B(x_1, \eta_1), \dots, B(x_{K+1}, \eta_{K+1})$ in $(\Omega, r_W)$ such that

1. the $K+1$ balls are weighted enough: $\mu[B(x_i, \eta_i)] \ge \beta$ for all $i \in [K+1]$,

2. the radii are small enough: $\eta_i \le \eta/2$ for all $i \in [K+1]$,

3. the centers are spaced enough: $r_W(x_i, x_j) \ge \sqrt{\epsilon^2 + 10\eta + 6t_n} + \eta$.

The small-ball condition 1. is similar to the assumption $H_1^{\alpha, v}$ for the dimension estimation; it ensures that some of the sampled points $\omega_1, \dots, \omega_n$ belong to the $K+1$ balls w.h.p.. The third condition 3. ensures that these balls are enough distant from each other, so that the sampled points in these balls are separated enough, in order to have $\hat{N}_{\Omega}^{(p.new)}(\epsilon) \ge K+1$ and confirm the alternative hypothesis correctly.

**Theorem 18** Assume the graphon $(\Omega, \mu, W)$ belongs to $W(\eta, \beta)$ for some $\beta > 1/n$. Then, the type II error is smaller than

$$ \frac{2}{n} + 2\beta n(K+1) \exp[-\beta(n-1)] $$

with respect to the distribution $P_{(\Omega, \mu, W)}$.

The proof of Theorem 18 is written in Appendix G.2.2. This result implies that, for any graphon in $W(\eta, \beta)$, the type II error is convergent to zero as soon as the measure of each ball $B(x_i, \eta_i)$ is large enough to satisfy $\beta \ge n^{-1}$. For example, if each of the $K+1$ balls has a measure that is larger than $\log[Kn]/n$, then the type II error is smaller than $\log(n)/n$ up to some numerical constant. In Appendix A.3, Theorem 18 is improved by using the graphon regularity at a finer level (see Theorem 21).

# 6. Further Considerations

## 6.1 Estimation of the Complexity with Sparse Observations

In the W-random graph model (3), each node has an average degree that is linear with $n$ the total number of nodes. However, real-world networks are often sparse with node degrees varying from zero to $n$. This motivates to consider a model of sparse graph where the node degree can be an order of magnitude smaller than $n$.
Given a sequence $\rho_n$ such that $\rho_n \to 0$, the definition of model (3) can be modified to have average node degrees of the order of $\rho_n n$. Consider the adjacency matrix $A$, defined by model (3), whose edges are independently retained with probability $\rho_n$ and erased with probability $1 - \rho_n$. We refer to this set-up as “the sparse setting” and denote by $\mathbb{P}_{(\Omega, \mu, W), \rho_n}$ the corresponding data distribution. This model has been considered several times in the literature (see Bickel et al., 2011; Wolfe and Olhede, 2013; Klopp et al., 2017; Xu et al., 2014).

We now extend the results of Section 4 to this sparse setting. Corollary 19 gives non-asymptotic error bounds for the distance estimation. It is a slight variant of Theorem 7. For completeness, the proof is written in Appendix F.1.

**Corollary 19** Assume the scaling parameter $\rho_n$ is lower bounded by

$$ \rho_n \geq 2\sqrt{\log(n)/(n-2)}. \qquad (21) $$

Then, the following event

$$ \mathcal{E}_{dist}^{sp} = \left\{ \forall i, j \in [n] : \begin{array}{l} |\rho_n^2 r_W^2(\omega_i, \omega_j) - \hat{r}^2(i, j)| \\ \leq 3\rho_n \left( \rho_n r_W(\omega_j, \omega_{m(j)}) + \rho_n r_W(\omega_i, \omega_{m(i)}) + 20\sqrt{\log(n)/n} \right) \end{array} \right\} $$

holds with probability $\mathbb{P}_{(\Omega, \mu, W), \rho_n}(\mathcal{E}_{dist}^{sp}) \geq 1 - \frac{2}{n}$.

We estimate the Minkowski dimension using the following radius

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

Corollary 20 is an adaptation of Theorem 12 for the sparse setting. The proof is written in Appendix F.2.

**Corollary 20** For all graphs $(\Omega, \mu, W)$ in $W(D, \alpha, m, M, v)$, all scaling parameters $\rho_n$ fulfilling (21), and all radii satisfying (22), the following rate of estimation of the dimension holds with probability tending to 1 as $n \to \infty$ (w.r.t. the distribution $\mathbb{P}_{(\Omega, \mu, W), \rho_n}$).

$$ \left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon_{D, \rho_n})}{-\log \epsilon_{D, \rho_n}} - d \right| \leq C(D, \alpha, m, M, t) \begin{cases} 1 & \text{if } \rho_n \asymp \sqrt{\log(n)/n}, \\ (\log n)^{-1} & \text{if } \rho_n \asymp (\log(n)/n)^{(1/2)-t}, \end{cases} $$

where $t \in (0, 1/2)$ and $C(D, \alpha, m, M, t)$ is some constant independent of $n$.

### 6.1.1 DISCUSSION ABOUT THE DISTANCE ESTIMATION IN SPARSE REGIMES AND OPEN QUESTION

Corollary 19 extends the upper bounds to the sparse setting where each entry of the adjacency matrix $[A_{ij}]_{1\leq i,j \leq n}$ is observed with probability $\rho_n$ independently. The scaling
Given a sequence $\rho_n$ such that $\rho_n \to 0$, the definition of model (3) can be modified to have average node degrees of the order of $\rho_n n$. Consider the adjacency matrix $A$, defined by model (3), whose edges are independently retained with probability $\rho_n$ and erased with probability $1 - \rho_n$. We refer to this set-up as “the sparse setting” and denote by $\mathbb{P}_{(\Omega, \mu, W), \rho_n}$ the corresponding data distribution. This model has been considered several times in the literature (see Bickel et al., 2011; Wolfe and Olhede, 2013; Klopp et al., 2017; Xu et al., 2014).

We now extend the results of Section 4 to this sparse setting. Corollary 19 gives non-asymptotic error bounds for the distance estimation. It is a slight variant of Theorem 7. For completeness, the proof is written in Appendix F.1.

**Corollary 19** Assume the scaling parameter $\rho_n$ is lower bounded by

$$ \rho_n \geq 2\sqrt{\log(n)/(n-2)}. \qquad (21) $$

Then, the following event

$$ \mathcal{E}_{dist}^{sp} = \left\{ \forall i, j \in [n] : \begin{array}{l} |\rho_n^2 r_W^2(\omega_i, \omega_j) - \hat{r}^2(i, j)| \\ \leq 3\rho_n \left( \rho_n r_W(\omega_j, \omega_{m(j)}) + \rho_n r_W(\omega_i, \omega_{m(i)}) + 20\sqrt{\log(n)/n} \right) \end{array} \right\} $$

holds with probability $\mathbb{P}_{(\Omega, \mu, W), \rho_n}(\mathcal{E}_{dist}^{sp}) \geq 1 - \frac{2}{n}$.

We estimate the Minkowski dimension using the following radius

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

Corollary 20 is an adaptation of Theorem 12 for the sparse setting. The proof is written in Appendix F.2.

**Corollary 20** For all graphs $(\Omega, \mu, W)$ in $W(D, \alpha, m, M, v)$, all scaling parameters $\rho_n$ fulfilling (21), and all radii satisfying (22), the following rate of estimation of the dimension holds with probability tending to 1 as $n \to \infty$ (w.r.t. the distribution $\mathbb{P}_{(\Omega, \mu, W), \rho_n}$).

$$ \left| \frac{\log \hat{N}_{\Omega}^{(c)}(\epsilon_{D, \rho_n})}{-\log \epsilon_{D, \rho_n}} - d \right| \leq C(D, \alpha, m, M, t) \begin{cases} 1 & \text{if } \rho_n \asymp \sqrt{\log(n)/n}, \\ (\log n)^{-1} & \text{if } \rho_n \asymp (\log(n)/n)^{(1/2)-t}, \end{cases} $$

where $t \in (0, 1/2)$ and $C(D, \alpha, m, M, t)$ is some constant independent of $n$.

### 6.1.1 DISCUSSION ABOUT THE DISTANCE ESTIMATION IN SPARSE REGIMES AND OPEN QUESTION

Corollary 19 extends the upper bounds to the sparse setting where each entry of the adjacency matrix $[A_{ij}]_{1\leq i,j \leq n}$ is observed with probability $\rho_n$ independently. The scaling
parameter is assumed to satisfy $\rho_n \gtrsim \sqrt{\log(n)/n}$ where the $\sqrt{\log(n)}$ in the numerator allows us to show high probability concentration, and the $1/\sqrt{n}$ ensures that there are enough data for the distance estimator to work. Indeed, the distance estimator is a linear combination of scalar products, and most scalar products are equal to zero in the very sparse regime $\rho_n = o(\sqrt{1/n})$ where pairs of nodes tend to have no common neighbors (i.e. common non-zero entries in the adjacency matrix).

Therefore, one needs to find new strategies to estimate the distances in very sparse regimes. A direction of research could be, for example, the nearest neighbor method in (Borgs et al., 2017) which is successfully applied to matrix estimation when $\rho_n \gtrsim n^{-1} \log(n)^2$. Overall, it would be interesting to complete the picture of the distance estimation problem according to different regimes of sparsity.

## 6.2 Polynomial-time Algorithm (with Theoretical Guarantee)

In contrast with the previous sections, here we take into account the computational aspect of the problem. Computing the covering number of a finite set is NP-hard, hence we approximate it with a greedy algorithm (Chvatal, 1979).

For completeness, the polynomial-time procedure for estimating $N_{\Omega}^{(c)}(\epsilon)$ is described below. The algorithm proceeds in two steps: Step 1 computes all distances $\hat{r}(i, j)$ using the distance-estimator (11); in particular, this step requires the computation of all index estimators $\hat{m}(j)$ defined by (10). Step 2 approximates the $\epsilon$-covering number of $\{1, \dots, n\}$ w.r.t. the distance estimator $\hat{r}$, by sequentially selecting balls (of radius $\epsilon$) according to one rule: at each stage, select the ball that contains the largest number of uncovered elements. At the end of the process, the number of selected balls is returned. This output is denoted by $\hat{N}_{\Omega}^{(ap.c)}(\epsilon)$.
parameter is assumed to satisfy $\rho_n \gtrsim \sqrt{\log(n)/n}$ where the $\sqrt{\log(n)}$ in the numerator allows us to show high probability concentration, and the $1/\sqrt{n}$ ensures that there are enough data for the distance estimator to work. Indeed, the distance estimator is a linear combination of scalar products, and most scalar products are equal to zero in the very sparse regime $\rho_n = o(\sqrt{1/n})$ where pairs of nodes tend to have no common neighbors (i.e. common non-zero entries in the adjacency matrix).

Therefore, one needs to find new strategies to estimate the distances in very sparse regimes. A direction of research could be, for example, the nearest neighbor method in (Borgs et al., 2017) which is successfully applied to matrix estimation when $\rho_n \gtrsim n^{-1}\log(n)^2$. Overall, it would be interesting to complete the picture of the distance estimation problem according to different regimes of sparsity.

## 6.2 Polynomial-time Algorithm (with Theoretical Guarantee)

In contrast with the previous sections, here we take into account the computational aspect of the problem. Computing the covering number of a finite set is NP-hard, hence we approximate it with a greedy algorithm (Chvatal, 1979).

For completeness, the polynomial-time procedure for estimating $N_{\Omega}^{(c)}(\epsilon)$ is described below. The algorithm proceeds in two steps: Step 1 computes all distances $\hat{r}(i, j)$ using the distance-estimator (11); in particular, this step requires the computation of all index estimators $\hat{m}(j)$ defined by (10). Step 2 approximates the $\epsilon$-covering number of $\{1, \dots, n\}$ w.r.t. the distance estimator $\hat{r}$, by sequentially selecting balls (of radius $\epsilon$) according to one rule: at each stage, select the ball that contains the largest number of uncovered elements. At the end of the process, the number of selected balls is returned. This output is denoted by $\hat{N}_{\Omega}^{(ap.c)}(\epsilon)$.
COVERING NUMBER ALGORITHM

**Input:** $A = [A_{ij}]$ adjacency matrix of size $n \times n$, a radius $\epsilon$.

**Step 1 : constructing the distance-estimator $\hat{r}$**

1. Compute the nearest neighbor's index of each sampled point $\omega_i$:
   $\forall i \in \{1, \dots, n\}, \quad \hat{m}(i) = \underset{j: j \neq i}{\operatorname{argmin}} \max_{k: k \neq i, j} |\langle A_k, A_i - A_j \rangle_n|$.

2. Compute all the distances:
   $\forall i, j \in \{1, \dots, n\}, \quad \hat{r}(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$.

**Step 2 : computing an approximation of the $\epsilon$-covering number**

3. In the space $S_0 = \{1, \dots, n\}$ endowed with the distance function $\hat{r}$, consider $B_0 = \{B_j\}_{j \le n}$ the set of all the balls of radius $\epsilon$.

4. Obtain a cover of $\{1, \dots, n\}$ as follows:
   Set $i = 0$. While $S_i \neq \emptyset$, do:

(a) Select a ball $B$ in $B_i$ that contains the largest number of elements of $S_i$.

(b) Set $S_{i+1} = S_i \setminus B$ to remove the elements covered by $B$,

(c) Set $B_{i+1} = B_i \setminus \{B\}$ to update the set of available balls,

(d) Set $i = i + 1$ to continue the algorithm.

**Output:** the number $i$ of selected balls, denoted by $\hat{N}_{\Omega}^{(ap.c)}(\epsilon)$.

We also suggest a heuristic for tuning $\epsilon$ in the estimation of the Minkowski dimension. First, run several times COVERING NUMBER ALGORITHM for a range of different radii $\epsilon_1, \dots, \epsilon_t$, and then plot $\log \hat{N}_{\Omega}^{(ap.c)}(\epsilon_j)/\log \epsilon_j$ for $j = 1, \dots, t$. As in Figure 1, we look for a graph function that (roughly) admits the three following parts: (1) for big radii, the shape of the curve is irregular and seems sawtooth; (2) for medium radii, there is almost a plateau whose value is the dimension estimate; (3) for small radii, there is an abrupt drop towards zero.

According to the theoretical guarantee of the greedy algorithm (Chvatal, 1979), one has

$$ \hat{N}_{\Omega}^{(c)}(\epsilon) \le \hat{N}_{\Omega}^{(ap.c)}(\epsilon) \le 2 \log(n) \hat{N}_{\Omega}^{(c)}(\epsilon) $$

where $\hat{N}_{\Omega}^{(c)}(\epsilon)$ is the consistent estimator introduced in Section 4. Then, for graphons fulfilling the assumptions of Theorem 12, there exist some radii $\epsilon$ such that $-\log \hat{N}_{\Omega}^{(ap.c)}(\epsilon)/\log \epsilon$ is close to the Minkowski dimension up to a small error term $-\log (2 \log(n))/\log \epsilon$.

We shortly illustrate the empirical performance of our algorithm on the random geometric graph, introduced in Section 3.2. Consider the latent space $[0, 1]$, endowed with the uniform measure and the function $W(x, y) = \mathbb{I}_{\|x-y\|_2 \le 0.1}$, which has a Minkowski dimension 2 and satisfies the assumptions of Theorem 12. We sample $n = 1000$ points uniformly on $[0, 1]$ and plot the outputs $-\log \hat{N}_{\Omega}^{(ap.c)}(\epsilon)/\log \epsilon$ over the range of radii $\epsilon \in$
COVERING NUMBER ALGORITHM

**Input:** A = [A<sub>ij</sub>] adjacency matrix of size *n* × *n*, a radius *ϵ*.

**Step 1 : constructing the distance-estimator r̂**

1. Compute the nearest neighbor's index of each sampled point $\omega_i$:
   $\forall i \in \{1, \dots, n\}, \quad \hat{m}(i) = \underset{j: j \neq i}{\operatorname{argmin}} \max_{k: k \neq i, j} |\langle A_k, A_i - A_j \rangle_n|.$

2. Compute all the distances:

$$ \forall i, j \in \{1, \dots, n\}, \quad \hat{r}(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. $$

**Step 2 : computing an approximation of the ϵ-covering number**

3. In the space $S_0 = \{1, \dots, n\}$ endowed with the distance function $\hat{r}$, consider $B_0 = \{B_j\}_{j \le n}$ the set of all the balls of radius $\epsilon$.

4. Obtain a cover of $\{1, \dots, n\}$ as follows:

Set $i = 0$. While $S_i \neq \emptyset$, do:

(a) Select a ball $B$ in $B_i$ that contains the largest number of elements of $S_i$.

(b) Set $S_{i+1} = S_i \setminus B$ to remove the elements covered by $B$,

(c) Set $B_{i+1} = B_i \setminus \{B\}$ to update the set of available balls,

(d) Set $i = i + 1$ to continue the algorithm.

**Output:** the number $i$ of selected balls, denoted by $\hat{N}_{\Omega}^{(ap.c)}(\epsilon)$.

We also suggest an heuristic for tuning $\epsilon$ in the estimation of the Minkowski dimension. First, run several times COVERING NUMBER ALGORITHM for a range of different radii $\epsilon_1, \dots, \epsilon_t$, and then plot $\log \hat{N}_{\Omega}^{(ap.c)}(\epsilon_j)/\log \epsilon_j$ for $j = 1, \dots, t$. As in Figure 1, we look for a graph function that (roughly) admits the three following parts: (1) for big radii, the shape of the curve is irregular and seems sawtooth; (2) for medium radii, there is almost a plateau whose value is the dimension estimate; (3) for small radii, there is an abrupt drop towards zero.

According to the theoretical guarantee of the greedy algorithm (Chvatal, 1979), one has

$$ \hat{N}_{\Omega}^{(c)}(\epsilon) \le \hat{N}_{\Omega}^{(ap.c)}(\epsilon) \le 2 \log(n) \hat{N}_{\Omega}^{(c)}(\epsilon) $$

where $\hat{N}_{\Omega}^{(c)}(\epsilon)$ is the consistent estimator introduced in Section 4. Then, for graphons fulfilling the assumptions of Theorem 12, there exist some radii $\epsilon$ such that $-\log \hat{N}_{\Omega}^{(ap.c)}(\epsilon)/\log \epsilon$ is close to the Minkowski dimension up to a small error term $-\log (2 \log(n))/\log \epsilon$.

We shortly illustrate the empirical performance of our algorithm on the random geometric graph, introduced in Section 3.2. Consider the latent space $[0, 1]$, endowed with the uniform measure and the function $W(x, y) = \mathbb{I}_{\|x-y\|_2 \le 0.1}$, which has a Minkowski dimension 2 and satisfies the assumptions of Theorem 12. We sample $n = 1000$ points uniformly on $[0, 1]$ and plot the outputs $-\log \hat{N}_{\Omega}^{(ap.c)}(\epsilon)/\log \epsilon$ over the range of radii $\epsilon \in$
<figure><img src="image_3.png" /><figcaption>Figure 1: W-random graph with Minkowski dimension 2</figcaption></figure>

$\{0.005 + k * 0.005; k \in \{0, \dots, 100\}\}$. This is represented by the red curve in Figure 1. As we can see, it is close to the true dimension at some intermediate radii, which coincides with our theoretical results. Specifically, we observe the three typical parts in the graph function: (1) on the right of the figure, the sawtooth-shaped curve means that the radius is too big for approaching the Minkowski dimension (which is by definition a limit in $\epsilon \to 0$); (2) on the middle, there is a plateau whose value is close to the dimension; (3) on the left, there is an abrupt drop because the covering number estimator eventually just counts the sampled points $\omega_1, \dots, \omega_n$. As a reference, we also plot $-\log N_{\omega_1, \dots, \omega_n}^{(ap.c)}(\epsilon)/\log \epsilon$ in blue, where $N_{\omega_1, \dots, \omega_n}^{(ap.c)}(\epsilon)$ is the *approximated* covering number of the sample $\{\omega_1, \dots, \omega_n\}$ w.r.t. to the true distance $r_W$.

# 7. Discussion

## 7.1 On the Definition of our Complexity Index

We have introduced an index of complexity for the limiting distributions $P_{(\Omega, \mu, W)}^{(\infty)}$ of W-random graphs. It has some geometric flavor as the index is based on the Minkowski dimension of the metric space $(\Omega, r_W)$, where $\Omega$ is the latent space of the W-random graph and $r_W$ is the neighborhood distance defined on $\Omega$. Accordingly, the index inherits from the general features of the Minkowski dimension which hold for any metric space. One of these features is the following maximum property: for any metric space $(X, d)$ which admits a partition $X = X_1 \cup \dots \cup X_k$, it is known that the Minkowski dimension of $X$ is equal to the maximum of the Minkowski dimensions of the $X_i$, $i \in [k]$. Thus, our index captures a maximum complexity of $(\Omega, r_W)$, which is an interesting information about the
<figure><img src="image_4.png" /><figcaption>Figure 1: W-random graph with Minkowski dimension 2</figcaption></figure>

$\{0.005 + k * 0.005; k \in \{0, \dots, 100\}\}$. This is represented by the red curve in Figure 1. As we can see, it is close to the true dimension at some intermediate radii, which coincides with our theoretical results. Specifically, we observe the three typical parts in the graph function: (1) on the right of the figure, the sawtooth-shaped curve means that the radius is too big for approaching the Minkowski dimension (which is by definition a limit in $\epsilon \to 0$); (2) on the middle, there is a plateau whose value is close to the dimension; (3) on the left, there is an abrupt drop because the covering number estimator eventually just counts the sampled points $\omega_1, \dots, \omega_n$. As a reference, we also plot $-\log N_{\omega_1, \dots, \omega_n}^{(ap.c)}(\epsilon)/\log \epsilon$ in blue, where $N_{\omega_1, \dots, \omega_n}^{(ap.c)}(\epsilon)$ is the *approximated* covering number of the sample $\{\omega_1, \dots, \omega_n\}$ w.r.t. to the true distance $r_W$.

# 7. Discussion

## 7.1 On the Definition of our Complexity Index

We have introduced an index of complexity for the limiting distributions $P_{(\Omega, \mu, W)}^{(\infty)}$ of W-random graphs. It has some geometric flavor as the index is based on the Minkowski dimension of the metric space $(\Omega, r_W)$, where $\Omega$ is the latent space of the W-random graph and $r_W$ is the neighborhood distance defined on $\Omega$. Accordingly, the index inherits from the general features of the Minkowski dimension which hold for any metric space. One of these features is the following maximum property: for any metric space $(X, d)$ which admits a partition $X = X_1 \cup \dots \cup X_k$, it is known that the Minkowski dimension of $X$ is equal to the maximum of the Minkowski dimensions of the $X_i$, $i \in [k]$. Thus, our index captures a maximum complexity of $(\Omega, r_W)$, which is an interesting information about the
distributions $\mathbb{P}_{(\Omega, \mu, W)}^{(\infty)}$ of W-random graphs. In order to complete our index, however, it would be worthwhile to investigate other notions of complexity as well. For example, one could think of some sort of average complexity instead of the maximum complexity measured by our index, maybe replacing the Minkowski dimension with a dimension that satisfies the following kind of property: for any metric space $X = X_1 \sqcup \dots \sqcup X_k$ endowed with a probability distribution $\mu$, the dimension of $X$ would be equal to an average of the dimensions of the $X_i$ weighted according to $\mu$. However, for such an index based on a dimension of $(\Omega, r_W)$, we remind that a major difficulty is to verify the identifiability of the index from the distribution $\mathbb{P}_{(\Omega, \mu, W)}^{(\infty)}$.

We have approximated the Minkowski dimension using a greedy algorithm in section 6.2, because the computational cost of this dimension is prohibitive. As an alternative, the correlation dimension is widely-used in manifold learning for its computational simplicity. Given sampled points $x_1, \dots, x_n \stackrel{\text{iid}}{\sim} \mu$ in a metric space $(X, d)$ endowed with a probability distribution $\mu$, the correlation integral is usually defined as

$$C(\epsilon) = \lim_{n \to \infty} \frac{2}{n(n-1)} \sum_{i=1}^{n} \sum_{\substack{j=1 \\ j \neq i}}^{n} \mathbb{I}_{\{d(x_i, x_j) < \epsilon\}}$$

where $\mathbb{I}_A$ denotes the indicator function of any event $A$. If the limit exists, the correlation dimension of $(X, d)$ is

$$D_{corr} = \lim_{\epsilon \to 0} \frac{\log C(\epsilon)}{\log \epsilon}.$$

It is known that $D_{corr}$ approximates well the Minkowski dimension when the distribution $\mu$ is nearly uniform on $X$, whereas it may be smaller for non-uniform distributions (Kégl, 2003). In fact, one can observe that $D_{corr}$ satisfies a minimum property, that is, the correlation dimension of $X = X_1 \sqcup \dots \sqcup X_k$ is equal to the minimum of the correlation dimensions of the $X_i$, $i \in [k]$. A direction of research could be to extend the correlation dimension to W-random graph distributions, so that one get a complexity index that is simple to compute. To this end, one could consider the following form of the correlation integral

$$C(\epsilon) = \mathbb{E}_{\substack{\omega_1 \sim \mu \\ \omega_2 \sim \mu}} [\mathbb{I}_{\{r_W(\omega_1, \omega_2) < \epsilon\}}]$$

with respect to the metric space $(\Omega, r_W)$ associated with a graphon $(\Omega, \mu, W)$.

## 7.2 On the Rates of Estimation

The focus of the current paper is on the whole class of graphons, which is a very general setting. In particular, our error bounds for the neighborhood distance and the covering number hold for any graphon. Therefore, a natural question is whether faster rates could be derived on sub-classes of graphons.

To estimate the Minkowski dimension of $(\Omega, r_W)$, we consider traditional assumptions in manifold learning, namely $(H_1^{\alpha, v})$ and $(H_2^{m, M, v})$, which essentially say that the metric space $(\Omega, r_W)$ behaves like a Euclidean space of dimension $d$ endowed with a uniform distribution $\mu$. Under these Euclidean-type assumptions, we prove that the optimal rate of estimation is $\log^{-1} n$. This rate matches known results for the Minkowski dimension in manifold learning,
distributions $\mathbb{P}_{(\Omega, \mu, W)}^{(\infty)}$ of W-random graphs. In order to complete our index, however, it would be worthwhile to investigate other notions of complexity as well. For example, one could think of some sort of average complexity instead of the maximum complexity measured by our index, maybe replacing the Minkowski dimension with a dimension that satisfies the following kind of property: for any metric space $X = X_1 \sqcup \dots \sqcup X_k$ endowed with a probability distribution $\mu$, the dimension of $X$ would be equal to an average of the dimensions of the $X_i$ weighted according to $\mu$. However, for such an index based on a dimension of $(\Omega, r_W)$, we remind that a major difficulty is to verify the identifiability of the index from the distribution $\mathbb{P}_{(\Omega, \mu, W)}^{(\infty)}$.

We have approximated the Minkowski dimension using a greedy algorithm in section 6.2, because the computational cost of this dimension is prohibitive. As an alternative, the correlation dimension is widely-used in manifold learning for its computational simplicity. Given sampled points $x_1, \dots, x_n \stackrel{\text{iid}}{\sim} \mu$ in a metric space $(X, d)$ endowed with a probability distribution $\mu$, the correlation integral is usually defined as

$$C(\epsilon) = \lim_{n \to \infty} \frac{2}{n(n-1)} \sum_{i=1}^{n} \sum_{\substack{j=1 \\ j \neq i}}^{n} \mathbb{I}_{\{d(x_i, x_j) < \epsilon\}}$$

where $\mathbb{I}_A$ denotes the indicator function of any event $A$. If the limit exists, the correlation dimension of $(X, d)$ is

$$D_{corr} = \lim_{\epsilon \to 0} \frac{\log C(\epsilon)}{\log \epsilon}.$$

It is known that $D_{corr}$ approximates well the Minkowski dimension when the distribution $\mu$ is nearly uniform on $X$, whereas it may be smaller for non-uniform distributions (Kégl, 2003). In fact, one can observe that $D_{corr}$ satisfies a minimum property, that is, the correlation dimension of $X = X_1 \sqcup \dots \sqcup X_k$ is equal to the minimum of the correlation dimensions of the $X_i$, $i \in [k]$. A direction of research could be to extend the correlation dimension to W-random graph distributions, so that one get a complexity index that is simple to compute. To this end, one could consider the following form of the correlation integral

$$C(\epsilon) = \mathbb{E}_{\substack{\omega_1 \sim \mu \\ \omega_2 \sim \mu}} [\mathbb{I}_{\{r_W(\omega_1, \omega_2) < \epsilon\}}]$$

with respect to the metric space $(\Omega, r_W)$ associated with a graphon $(\Omega, \mu, W)$.

## 7.2 On the Rates of Estimation

The focus of the current paper is on the whole class of graphons, which is a very general setting. In particular, our error bounds for the neighborhood distance and the covering number hold for any graphon. Therefore, a natural question is whether faster rates could be derived on sub-classes of graphons.

To estimate the Minkowski dimension of $(\Omega, r_W)$, we consider traditional assumptions in manifold learning, namely $(H_1^{\alpha, v})$ and $(H_2^{m, M, v})$, which essentially say that the metric space $(\Omega, r_W)$ behaves like a Euclidean space of dimension $d$ endowed with a uniform distribution $\mu$. Under these Euclidean-type assumptions, we prove that the optimal rate of estimation is $\log^{-1} n$. This rate matches known results for the Minkowski dimension in manifold learning,
see for instance (Koltchinskii, 2000). A future direction of research for W-random graph complexity could be the definition of new indices that enjoy faster rates of estimation.

Acknowledgments

We would like to thank Nicolas Verzelen for sharing his ideas, and Christophe Giraud for valuable advice. This research was initially supported by an AMX PhD funding from École Polytechnique, and then by a grant of the French National Research Agency (ANR), “Investissements d’Avenir” (LabEx Eencode/ANR-11-LABX-0047).

Appendix A. Additional Information

A.1 Basic Information on the Covering and Packing Numbers and the Minkowski Dimension

Given any set $S$, its covering number $N^{(c)}(\epsilon)$ is the minimal number of balls of radius $\epsilon$ required to entirely cover $S$, with the constraint that the ball centers are in $S$. This measure is widely used for general metric spaces. Likewise, the packing number $N^{(p)}(\epsilon)$ is the maximum number of points in a given space (strictly) separated by at least a given distance $\epsilon$. Both measures are similar and linked by the following inequalities $N^{(c)}(\epsilon) \le N^{(p)}(\epsilon) \le N^{(c)}(\epsilon/2)$. In all the paper (except the last subsection 5), our results are mostly stated with the covering number, but each of them can be adapted to the packing number.

The covering number requires to choose the scale $\epsilon$ at which we look at the data. To get rid of this parameter, it is common to consider the Minkowski dimension which is defined by $\lim_{\epsilon \to 0} -\log N^{(c)}(\epsilon)/\log \epsilon$. Note that the same formula holds with the packing number instead. The Minkowski dimension is used for infinite (separable) spaces, when the covering number diverges to infinity as $\epsilon$ goes to zero. This dimension is therefore complementary to the covering number. It is known to match with some other classical notions of dimension in simple cases, for example the Minkowski dimension of the hypercube $[0, 1]^d$ is equal to its Euclidean dimension $d$. The Minkowski dimension has the advantage to be applicable on a wide range of spaces (whose dimension is not necessarily an integer) and to be easy to compute (in comparison with the Hausdorff dimension for example).

A.2 Details on the Illustrative Examples

RANDOM HÖLDER GRAPH. Recall that the graphon $(\Omega, \mu, W)$ is $([0, 1]^d, \lambda, W)$ where $\lambda$ is the uniform measure on $[0, 1]^d$ and $W$ satisfies the following condition: there exist three constants $m, M, \alpha > 0$ such that for all $\omega, \omega', \omega'' \in [0, 1]^d$,

$$m||\omega' - \omega||_2^\alpha \le |W(\omega', \omega'') - W(\omega, \omega'')| \le M||\omega' - \omega||_2^\alpha$$

where $\alpha$ is the level of regularity of the function $W$ and $||\omega' - \omega||_2$ is the Euclidean distance between $\omega'$ and $\omega$ in $[0, 1]^d$. From the above display, we directly deduce some bounds on the neighborhood distance (4) :

$$\forall \omega, \omega' \in [0, 1]^d,$$

$$m||\omega' - \omega||_2^\alpha \le r_W(\omega', \omega) \le M||\omega' - \omega||_2^\alpha.$$
see for instance (Koltchinskii, 2000). A future direction of research for W-random graph complexity could be the definition of new indices that enjoy faster rates of estimation.

## Acknowledgments

We would like to thank Nicolas Verzelen for sharing his ideas, and Christophe Giraud for valuable advice. This research was initially supported by an AMX PhD funding from École Polytechnique, and then by a grant of the French National Research Agency (ANR), “Investissements d’Avenir” (LabEx Eencode/ANR-11-LABX-0047).

## Appendix A. Additional Information

### A.1 Basic Information on the Covering and Packing Numbers and the Minkowski Dimension

Given any set $S$, its covering number $N^{(c)}(\epsilon)$ is the minimal number of balls of radius $\epsilon$ required to entirely cover $S$, with the constraint that the ball centers are in $S$. This measure is widely used for general metric spaces. Likewise, the packing number $N^{(p)}(\epsilon)$ is the maximum number of points in a given space (strictly) separated by at least a given distance $\epsilon$. Both measures are similar and linked by the following inequalities $N^{(c)}(\epsilon) \le N^{(p)}(\epsilon) \le N^{(c)}(\epsilon/2)$. In all the paper (except the last subsection 5), our results are mostly stated with the covering number, but each of them can be adapted to the packing number.

The covering number requires to choose the scale $\epsilon$ at which we look at the data. To get rid of this parameter, it is common to consider the Minkowski dimension which is defined by $\lim_{\epsilon \to 0} -\log N^{(c)}(\epsilon)/\log \epsilon$. Note that the same formula holds with the packing number instead. The Minkowski dimension is used for infinite (separable) spaces, when the covering number diverges to infinity as $\epsilon$ goes to zero. This dimension is therefore complementary to the covering number. It is known to match with some other classical notions of dimension in simple cases, for example the Minkowski dimension of the hypercube $[0, 1]^d$ is equal to its Euclidean dimension $d$. The Minkowski dimension has the advantage to be applicable on a wide range of spaces (whose dimension is not necessarily an integer) and to be easy to compute (in comparison with the Hausdorff dimension for example).

### A.2 Details on the Illustrative Examples

RANDOM HÖLDER GRAPH. Recall that the graphon $(\Omega, \mu, W)$ is $([0, 1]^d, \lambda, W)$ where $\lambda$ is the uniform measure on $[0, 1]^d$ and $W$ satisfies the following condition: there exist three constants $m, M, \alpha > 0$ such that for all $\omega, \omega', \omega'' \in [0, 1]^d$,

$$m||\omega' - \omega||_2^\alpha \le |W(\omega', \omega'') - W(\omega, \omega'')| \le M||\omega' - \omega||_2^\alpha$$

where $\alpha$ is the level of regularity of the function $W$ and $||\omega' - \omega||_2$ is the Euclidean distance between $\omega'$ and $\omega$ in $[0, 1]^d$. From the above display, we directly deduce some bounds on the neighborhood distance (4) :

$$\forall \omega, \omega' \in [0, 1]^d,$$

$$m||\omega' - \omega||_2^\alpha \le r_W(\omega', \omega) \le M||\omega' - \omega||_2^\alpha.$$
Thus, the distance $r_W$ behaves (up to some constants) like the Euclidean distance on $[0, 1]^d$ raised to the power of $\alpha$. As the covering number of the Euclidean hypercube $([0, 1]^d, ||.||_2)$ is approximately equal to $\epsilon^{-d}$ for small radii, we have

$$ (\epsilon/m)^{-d/\alpha} \lesssim N_{\Omega}^{(c)}(\epsilon) \lesssim (\epsilon/M)^{-d/\alpha}. $$

Hence $dim \Omega = d/\alpha$, which means that the Minkowski dimension of $(\Omega, r_W)$ is equal to the ratio between the Euclidean dimension of the latent space $[0, 1]^d$ and the regularity of the function $W$.

**RANDOM GEOMETRIC GRAPH EXAMPLE.** Recall that the graphon is $([0, 1]^d, \lambda, W)$ where $\lambda$ is the uniform measure, and $W$ is defined as $W(\omega, \omega') = \mathbb{I}_{||\omega-\omega'||_2 \le \delta}$ for some parameter $\delta \in ]0, 1[$, and $||\omega - \omega'||_2$ is the Euclidean distance between $\omega, \omega' \in [0, 1]^d$. Here, the bounds on the neighborhood distance are rather involved and deferred to the Appendix B.2. The main message is that

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

if $||\omega - \omega'||_2$ is small enough, which means that the distance $r_W$ behaves like the squared root of the Euclidean norm in $[0, 1]^d$. Following the line of the Random Hölder graph example, we can see that $N_{\Omega}^{(c)}(\epsilon)$ behaves like $\epsilon^{-2d}$ for $\epsilon$ small enough. By definition of the Minkowski dimension, it follows that $dim \Omega = 2d$.

### A.3 Test: Improvement of the Type II Error

The control of the type II error can be refined using the graphon regularity at a finer level. Instead of considering the set $W(\eta, \beta)$ of graphons with $K+1$ well separated balls (Theorem 18), here we consider the new set $W(\eta, \beta, M, K')$ of graphons with $M$ disjoint collections of $K+1+K'$ separated balls. That is, for a collection of $K+1+K'$ balls, we assume the same conditions of separation, size and measure as in a collection of $K+1$ balls defined by $W(\eta, \beta)$ (in Theorem 18). In addition, we assume that the $M$ formations of $K+1+K'$ balls do not intersect each other (i.e. no ball from a collection overlaps a ball from another collection). Thus, the new set $W(\eta, \beta, M, K')$ of graphons is linked with the previous one by the following equality $W(\eta, \beta, 1, 0) = W(\eta, \beta)$.

**Theorem 21** If the underlying graphon belongs to $W(\eta, \beta, M, K')$ with $\beta \ge 1/n$, then the type II error is smaller than $\frac{2}{n} + \tilde{p}_n^M$, where $\tilde{p}_n$ admits the following upper bound

$$ \binom{K + K' + 1}{K' + 1} (2\beta n \exp[-\beta(n-1)])^{(K'+1)}. $$

The proof of Theorem 18 is written in Appendix G.2.2.

## Appendix B. Proofs for Illustrative Examples

### B.1 Proof of Proposition 6: Approximation by SBM

Given a graphon $(\Omega, \mu, W)$ and a radius $\epsilon > 0$, we consider a cover of $(\Omega, r_W)$ whose the cardinality is $N_{\Omega}^{(c)}(\epsilon)$ (written $N$ for brevity), and the ball centers are $x_1, \dots, x_N$. The
Thus, the distance $r_W$ behaves (up to some constants) like the Euclidean distance on $[0, 1]^d$ raised to the power of $\alpha$. As the covering number of the Euclidean hypercube $([0, 1]^d, ||.||_2)$ is approximately equal to $\epsilon^{-d}$ for small radii, we have

$$ (\epsilon/m)^{-d/\alpha} \lesssim N_{\Omega}^{(c)}(\epsilon) \lesssim (\epsilon/M)^{-d/\alpha}. $$

Hence $dim \Omega = d/\alpha$, which means that the Minkowski dimension of $(\Omega, r_W)$ is equal to the ratio between the Euclidean dimension of the latent space $[0, 1]^d$ and the regularity of the function $W$.

**RANDOM GEOMETRIC GRAPH EXAMPLE.** Recall that the graphon is $([0, 1]^d, \lambda, W)$ where $\lambda$ is the uniform measure, and $W$ is defined as $W(\omega, \omega') = \mathbb{I}_{||\omega-\omega'||_2 \le \delta}$ for some parameter $\delta \in ]0, 1[$, and $||\omega - \omega'||_2$ is the Euclidean distance between $\omega, \omega' \in [0, 1]^d$. Here, the bounds on the neighborhood distance are rather involved and deferred to the Appendix B.2. The main message is that

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

if $||\omega - \omega'||_2$ is small enough, which means that the distance $r_W$ behaves like the squared root of the Euclidean norm in $[0, 1]^d$. Following the line of the Random Hölder graph example, we can see that $N_{\Omega}^{(c)}(\epsilon)$ behaves like $\epsilon^{-2d}$ for $\epsilon$ small enough. By definition of the Minkowski dimension, it follows that $dim \Omega = 2d$.

### A.3 Test: Improvement of the Type II Error

The control of the type II error can be refined using the graphon regularity at a finer level. Instead of considering the set $W(\eta, \beta)$ of graphons with $K+1$ well separated balls (Theorem 18), here we consider the new set $W(\eta, \beta, M, K')$ of graphons with $M$ disjoint collections of $K+1+K'$ separated balls. That is, for a collection of $K+1+K'$ balls, we assume the same conditions of separation, size and measure as in a collection of $K+1$ balls defined by $W(\eta, \beta)$ (in Theorem 18). In addition, we assume that the $M$ formations of $K+1+K'$ balls do not intersect each other (i.e. no ball from a collection overlaps a ball from another collection). Thus, the new set $W(\eta, \beta, M, K')$ of graphons is linked with the previous one by the following equality $W(\eta, \beta, 1, 0) = W(\eta, \beta)$.

**Theorem 21** If the underlying graphon belongs to $W(\eta, \beta, M, K')$ with $\beta \ge 1/n$, then the type II error is smaller than $\frac{2}{n} + \tilde{p}_n^M$, where $\tilde{p}_n$ admits the following upper bound

$$ \binom{K + K' + 1}{K' + 1} (2\beta n \exp[-\beta(n-1)])^{(K'+1)}. $$

The proof of Theorem 18 is written in Appendix G.2.2.

## Appendix B. Proofs for Illustrative Examples

### B.1 Proof of Proposition 6: Approximation by SBM

Given a graphon $(\Omega, \mu, W)$ and a radius $\epsilon > 0$, we consider a cover of $(\Omega, r_W)$ whose the cardinality is $N_{\Omega}^{(c)}(\epsilon)$ (written $N$ for brevity), and the ball centers are $x_1, \dots, x_N$. The
Voronoi cell $V_j$ of $x_j$ is the set of all elements in $\Omega$ that are closer to $x_j$ than to any other $x_k$, $k \neq j$, according to the metric $r_W$. In the case of equality, where a point $\omega$ is at equal distance of several ball centers $x_i$, it belongs to the Veronoi cell of smallest index $i$.

$$V_j := \{ \omega \in \Omega : r_W(\omega, x_j) < r_W(\omega, x_k) \text{ if } k < j, \text{ and } r_W(\omega, x_j) \le r_W(\omega, x_k) \text{ otherwise} \}$$

Define the SBM approximation of $W$ as follows:

$$\overline{W}(x, y) = \sum_{i,j=1}^{N} 1_{x \in V_i} 1_{y \in V_j} \frac{1}{\mu(V_i)\mu(V_j)} \int_{V_i} \int_{V_j} W(z_1, z_2)\mu(dz_1)\mu(dz_2)$$

By triangular inequality and Jensen inequality:

$$\int_{\Omega^2} (W(x, y) - \overline{W}(x, y))^2 \mu(dx)\mu(dy) \le 2 \int_{\Omega^2} \sum_{j=1}^{N} 1_{y \in V_j} \left[ \frac{1}{\mu(V_j)} \int_{V_j} [W(x, y) - W(x, z_2)]^2 \mu(dz_2) \right] \mu(dx)\mu(dy) +$$

$$2 \int_{\Omega^2} \left[ \sum_{i,j=1}^{N} 1_{x \in V_i} 1_{y \in V_j} \frac{1}{\mu(V_i)\mu(V_j)} \int_{V_i} \int_{V_j} [W(x, z_2) - W(z_1, z_2)]^2 \mu(dz_1)\mu(dz_2) \right] \mu(dx)\mu(dy)$$

Note that the first term is smaller than $8\epsilon^2$ by integrating with respect to $x$ and using the fact that $y$ and $z_2$ belong to the same Voronoi cell. The second term simplifies

$$2 \int_{\Omega^2} \left[ \sum_{i=1}^{N} 1_{x \in V_i} \frac{1}{\mu(V_i)} \int_{V_i} [W(x, y) - W(z_1, y)]^2 \mu(dz_1) \right] \mu(dx)\mu(dy)$$

which is again smaller than $8\epsilon^2$. The approximation error of $W$ by $\overline{W}$ is therefore lower than $4\epsilon$ in $l_2$-norm. The proposition is proved. ■

## B.2 The Neighborhood Distance for the Random Geometric Graph Example

Lemma 22 gives bounds on the neighborhood distance for the random geometric graph of Section 3.2. For simplicity, we neglect the side effects associated with a point too close of the side of $\Omega = [0, 1]^d$. That is, we assume the parameter $\delta$ is small compared to 1 (where 1 is the length of a side of $[0, 1]^d$). Write $V_d$ the volume of the unit ball in $[0, 1]^d$ endowed with the Euclidean norm $||.||_2$, and write $I_x(\cdot, \cdot)$ the (regularized) incomplete beta function (see DLMF, Eq.8.17.2 for a definition).

**Lemma 22** If $||x-y||_2 > 2\delta$, then $r_W^2(x, y) = 2V_d\delta^d$; otherwise $r_W^2(x, y) = 2V_d\delta^d I_x(\frac{1}{2}, \frac{d+1}{2})$ for $x = (\frac{||x-y||_2}{2\delta})^2$. As a consequence, $\sqrt{||x-y||_2} \lesssim r_W(x, y) \lesssim \sqrt{||x-y||_2}$ as soon as $||x-y||_2$ is small enough (compared to $\delta$).

According to the above lemma, the neighborhood distance $r_W$ behaves like the squared root of the Euclidean norm of $[0, 1]^d$ if $||x-y||_2$ is small enough. For lower dimensions, for instance $d=3$, we can also use the paper of Li (2011) to get the simpler formula: if $||x-y||_2 < 2\delta$, then

$$r_W^2(x, y) = 2\pi \left( \delta^2 - \frac{||x-y||_2^2}{12} \right) ||x-y||_2.$$
Voronoi cell $V_j$ of $x_j$ is the set of all elements in $\Omega$ that are closer to $x_j$ than to any other $x_k$, $k \neq j$, according to the metric $r_W$. In the case of equality, where a point $\omega$ is at equal distance of several ball centers $x_i$, it belongs to the Veronoi cell of smallest index $i$.

$$V_j := \{ \omega \in \Omega : r_W(\omega, x_j) < r_W(\omega, x_k) \text{ if } k < j, \text{ and } r_W(\omega, x_j) \leq r_W(\omega, x_k) \text{ otherwise} \}$$

Define the SBM approximation of $W$ as follows:

$$\overline{W}(x, y) = \sum_{i,j=1}^{N} 1_{x \in V_i} 1_{y \in V_j} \frac{1}{\mu(V_i)\mu(V_j)} \int_{V_i} \int_{V_j} W(z_1, z_2)\mu(dz_1)\mu(dz_2)$$

By triangular inequality and Jensen inequality:

$$\int_{\Omega^2} (W(x, y) - \overline{W}(x, y))^2 \mu(dx) \mu(dy) \leq 2 \int_{\Omega^2} \sum_{j=1}^{N} 1_{y \in V_j} \left[ \frac{1}{\mu(V_j)} \int_{V_j} [W(x, y) - W(x, z_2)]^2 \mu(dz_2) \right] \mu(dx) \mu(dy) +$$

$$2 \int_{\Omega^2} \left[ \sum_{i,j=1}^{N} 1_{x \in V_i} 1_{y \in V_j} \frac{1}{\mu(V_i)\mu(V_j)} \int_{V_i} \int_{V_j} [W(x, z_2) - W(z_1, z_2)]^2 \mu(dz_1)\mu(dz_2) \right] \mu(dx)\mu(dy)$$

Note that the first term is smaller than $8\epsilon^2$ by integrating with respect to $x$ and using the fact that $y$ and $z_2$ belong to the same Voronoi cell. The second term simplifies

$$2 \int_{\Omega^2} \left[ \sum_{i=1}^{N} 1_{x \in V_i} \frac{1}{\mu(V_i)} \int_{V_i} [W(x, y) - W(z_1, y)]^2 \mu(dz_1) \right] \mu(dx)\mu(dy)$$

which is again smaller than $8\epsilon^2$. The approximation error of $W$ by $\overline{W}$ is therefore lower than $4\epsilon$ in $l_2$-norm. The proposition is proved. ■

## B.2 The Neighborhood Distance for the Random Geometric Graph Example

Lemma 22 gives bounds on the neighborhood distance for the random geometric graph of Section 3.2. For simplicity, we neglect the side effects associated with a point too close of the side of $\Omega = [0, 1]^d$. That is, we assume the parameter $\delta$ is small compared to 1 (where 1 is the length of a side of $[0, 1]^d$). Write $V_d$ the volume of the unit ball in $[0, 1]^d$ endowed with the Euclidean norm $||.||_2$, and write $I_x(\cdot, \cdot)$ the (regularized) incomplete beta function (see DLMF, Eq.8.17.2 for a definition).

**Lemma 22** If $||x-y||_2 > 2\delta$, then $r_W^2(x, y) = 2V_d\delta^d$; otherwise $r_W^2(x, y) = 2V_d\delta^d I_x(\frac{1}{2}, \frac{d+1}{2})$ for $x = (\frac{||x-y||_2}{2\delta})^2$. As a consequence, $\sqrt{||x-y||_2} \lesssim r_W(x, y) \lesssim \sqrt{||x-y||_2}$ as soon as $||x-y||_2$ is small enough (compared to $\delta$).

According to the above lemma, the neighborhood distance $r_W$ behaves like the squared root of the Euclidean norm of $[0, 1]^d$ if $||x-y||_2$ is small enough. For lower dimensions, for instance $d=3$, we can also use the paper of Li (2011) to get the simpler formula: if $||x-y||_2 < 2\delta$, then

$$r_W^2(x, y) = 2\pi \left( \delta^2 - \frac{||x - y||_2^2}{12} \right) ||x - y||_2.$$
*Proof of Lemma 22.* For the random geometric graph, observe that the computation of the neighborhood distance is equivalent to the computation of the volumes of hyperspherical caps. Using the formula (3) in the paper of Li (2011) (and neglecting the side effects due to the boundary of the latent space), we have: if $||x - y||_2 < 2\delta$, then

$$r_W^2(x, y) = 2V_d\delta^d \left[ 1 - I_x\left(\frac{d+1}{2}, \frac{1}{2}\right) \right]$$

where $x = 1 - \left(\frac{||x-y||_2}{2\delta}\right)^2$. Basic properties of the (regularized) incomplete beta function (see DLMF, Eq.8.17.4) allows to rewrite the last formula: if $||x - y||_2 < 2\delta$, then

$$r_W^2(x, y) = 2V_d\delta^d I_x\left(\frac{1}{2}, \frac{d+1}{2}\right) \qquad (23)$$

where $x = \left(\frac{||x-y||_2}{2\delta}\right)^2$. Let $B(a, b)$ denote the beta function (DLMF, Eq.5.12.1), then the above formula (23) can be developed using the recurrence formula $I_x(a, b + 1) = I_x(a, b) + \frac{x^a(1-x)^b}{bB(a, b)}$ (DLMF, Eq.8.17.21). It follows that $r_W$ satisfies the following bounds: $\sqrt{||x - y||_2} \lesssim r_W(x, y) \lesssim \sqrt{||x - y||_2}$ as soon as $||x - y||_2$ is small enough. ■

# Appendix C. Identifiability and Pure Graphons

## C.1 Proof of Lemma 4: Invariance of the Neighborhood Distance

Given two equivalent pure graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$, let us show that their respective neighborhood distances $r_W$ and $r_{W'}$ are linked by the following $\mu' \otimes \mu'$-almost surely equality

$$r_W(\phi(x), \phi(y)) = r_{W'}(x, y)$$

for some measure-preserving bijection $\phi : \Omega' \to \Omega$.

It follows from Lemma 23, which links any two equivalent pure graphons. Denote by $W^\phi$ the function $(x, y) \mapsto W(\phi(x), \phi(y))$.

**Lemma 23 (Lovász, 2012, Section 13.3)** If two pure graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$ are equivalent, then there exists a bijective measure-preserving map $\phi : \Omega' \to \Omega$ such that $W^\phi(x, y) = W'(x, y)$ $\mu' \otimes \mu'$-almost surely.

Indeed, by definition of the neighborhood distance,

$$r_{W'}(x, y) = \left( \int_{\Omega'} |W'(x, z') - W(y, z')|^2 \mu'(dz') \right)^{1/2}$$

which gives the following $\mu' \otimes \mu'$-almost surely equality by Lemma 23,

$$r_{W'}(x, y) = \left( \int_{\Omega'} |W(\phi(x), \phi(z')) - W(\phi(y), \phi(z'))|^2 \mu'(dz') \right)^{1/2}$$
*Proof of Lemma 22.* For the random geometric graph, observe that the computation of the neighborhood distance is equivalent to the computation of the volumes of hyperspherical caps. Using the formula (3) in the paper of Li (2011) (and neglecting the side effects due to the boundary of the latent space), we have:
if $||x - y||_2 < 2\delta$, then

$$r_W^2(x, y) = 2V_d \delta^d \left[ 1 - I_x\left(\frac{d+1}{2}, \frac{1}{2}\right) \right]$$

where $x = 1 - \left(\frac{||x-y||_2}{2\delta}\right)^2$. Basic properties of the (regularized) incomplete beta function (see DLMF, Eq.8.17.4) allows to rewrite the last formula:
if $||x - y||_2 < 2\delta$, then

$$r_W^2(x, y) = 2V_d \delta^d I_x\left(\frac{1}{2}, \frac{d+1}{2}\right) \qquad (23)$$

where $x = \left(\frac{||x-y||_2}{2\delta}\right)^2$. Let $B(a, b)$ denote the beta function (DLMF, Eq.5.12.1), then the above formula (23) can be developed using the recurrence formula $I_x(a, b + 1) = I_x(a, b) + \frac{x^a(1-x)^b}{bB(a,b)}$ (DLMF, Eq.8.17.21). It follows that $r_W$ satisfies the following bounds: $\sqrt{||x - y||_2} \lesssim r_W(x, y) \lesssim \sqrt{||x - y||_2}$ as soon as $||x - y||_2$ is small enough. ■

# Appendix C. Identifiability and Pure Graphons

## C.1 Proof of Lemma 4: Invariance of the Neighborhood Distance

Given two equivalent pure graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$, let us show that their respective neighborhood distances $r_W$ and $r_{W'}$ are linked by the following $\mu' \otimes \mu'$-almost surely equality

$$r_W(\phi(x), \phi(y)) = r_{W'}(x, y)$$

for some measure-preserving bijection $\phi : \Omega' \to \Omega$.

It follows from Lemma 23, which links any two equivalent pure graphons. Denote by $W^\phi$ the function $(x, y) \mapsto W(\phi(x), \phi(y))$.

**Lemma 23 (Lovász, 2012, Section 13.3)** If two pure graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$ are equivalent, then there exists a bijective measure-preserving map $\phi : \Omega' \to \Omega$ such that $W^\phi(x, y) = W'(x, y)$ $\mu' \otimes \mu'$-almost surely.

Indeed, by definition of the neighborhood distance,

$$r_{W'}(x, y) = \left( \int_{\Omega'} |W'(x, z') - W(y, z')|^2 \mu'(dz') \right)^{1/2}$$

which gives the following $\mu' \otimes \mu'$-almost surely equality by Lemma 23,

$$r_{W'}(x, y) = \left( \int_{\Omega'} |W(\phi(x), \phi(z')) - W(\phi(y), \phi(z'))|^2 \mu'(dz') \right)^{1/2}$$
for some measure-preserving bijection $\phi : \Omega' \to \Omega$. Then, using a pushforward measure (or image measure),

$$r_{W'}(x, y) = \left( \int_{\Omega} |W(\phi(x), z) - W(\phi(y), z)|^2 \mu(dz) \right)^{1/2}$$

$\mu' \otimes \mu'$-almost surely, so that, by definition of the neighborhood distance,

$$r_{W'}(x, y) = r_W(\phi(x), \phi(y))$$

$\mu' \otimes \mu'$-almost surely. Lemma 4 is proved. ■

## C.2 Proof of Lemma 3: Identifiability of the Covering Number

Given two equivalent pure graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$, let us prove that their respective covering numbers are equal: $N_{\Omega}^{(c)}(\epsilon) = N_{\Omega'}^{(c)}(\epsilon)$ for all $\epsilon > 0$.

According to Lemma 4, there exists a measure-preserving bijection $\phi$, such that the two metric spaces $(\Omega, r_W)$ and $(\Omega', r_{W'})$ are linked by the equality $r_{W'}(x, y) = r_W(\phi(x), \phi(y))$ on a subset of measure 1, say $\Sigma \subseteq \Omega'$ with $\mu'(\Sigma) = 1$. This means that both subspaces $(\phi(\Sigma), r_W)$ and $(\Sigma, r_{W'})$ are linked by a bijection that preserves the distances, which directly implies equality between their covering numbers: $N_{\phi(\Sigma)}^{(c)}(\epsilon) = N_{\Sigma}^{(c)}(\epsilon)$ for all $\epsilon > 0$.

Then, for proving Lemma 3, it is enough to show the two following inequalities

$$N_{\Omega}^{(c)}(\epsilon) \geq N_{\phi(\Sigma)}^{(c)}(\epsilon + \delta) \qquad (24)$$

$$N_{\Sigma}^{(c)}(\epsilon + \delta) \geq N_{\Omega'}^{(c)}(\epsilon + \delta) \qquad (25)$$

for any $\delta > 0$. Indeed, combining these two inequalities with the covering number equality from the above paragraph, one has $N_{\Omega}^{(c)}(\epsilon) \geq N_{\Omega'}^{(c)}(\epsilon + \delta)$. Taking the limit $\delta \to 0$ and using the right-continuity of the covering number (Lemma 24), this gives $N_{\Omega}^{(c)}(\epsilon) \geq N_{\Omega'}^{(c)}(\epsilon)$. As the reverse inequality holds by symmetry of the proof, one obtain the equality $N_{\Omega}^{(c)}(\epsilon) = N_{\Omega'}^{(c)}(\epsilon)$ of Lemma 3.

**Lemma 24** Given a pure graphon $(\Omega, \mu, W)$, the function $\epsilon \mapsto N_{\Omega}^{(c)}(\epsilon)$ is piecewise constant and right-continuous (note that we use closed balls in the definition). Likewise, $\epsilon \mapsto N_{\Omega}^{(p)}(\epsilon)$ is a right continuous piecewise function.

Assume $\Sigma$ is dense in $(\Omega', r_{W'})$. Each cover of $\Sigma$ is closed as a finite union of closed balls. Hence it is also a cover of $\Omega'$ by density of $\Sigma$ in $\Omega'$. This proves (25). Likewise, assume $\phi(\Sigma)$ is dense in $(\Omega, r_W)$. An $\epsilon$-cover of $\Omega$ can be transformed into an $(\epsilon + \delta)$-cover of $\phi(\Sigma)$ by moving the ball centers from $\Omega$ to $\Sigma$ and increasing the ball radius of $\delta$ (for arbitrary small $\delta$). This proves (24) for any $\delta > 0$.

Let us show the density of $\phi(\Sigma)$ in $(\Omega, r_W)$. One has $\mu(\phi(\Sigma)) = \mu'(\Sigma) = 1$ by definition of a (bijective) measure-preserving map, which implies that $\phi(\Sigma)$ intersects each ball of non-zero measure in $(\Omega, r_W)$. As the measure of a pure graphon has full-support by definition, then each ball of non-zero radius has a non-zero measure. Thus, $\phi(\Sigma)$ intersects each ball of non-zero radius in $(\Omega, r_W)$, which means that $\phi(\Sigma)$ is dense in $(\Omega, r_W)$. Similarly, we can show the density of $\Sigma$ in $(\Omega', r_{W'})$.

Lemma 3 is proved for the covering number. The proof for the packing number is similar and omitted. ■
for some measure-preserving bijection $\phi : \Omega' \to \Omega$. Then, using a pushforward measure (or image measure),

$$r_{W'}(x, y) = \left( \int_{\Omega} |W(\phi(x), z) - W(\phi(y), z)|^2 \mu(dz) \right)^{1/2}$$

$\mu' \otimes \mu'$-almost surely, so that, by definition of the neighborhood distance,

$$r_{W'}(x, y) = r_W(\phi(x), \phi(y))$$

$\mu' \otimes \mu'$-almost surely. Lemma 4 is proved. ■

## C.2 Proof of Lemma 3: Identifiability of the Covering Number

Given two equivalent pure graphons $(\Omega, \mu, W)$ and $(\Omega', \mu', W')$, let us prove that their respective covering numbers are equal: $N_{\Omega}^{(c)}(\epsilon) = N_{\Omega'}^{(c)}(\epsilon)$ for all $\epsilon > 0$.

According to Lemma 4, there exists a measure-preserving bijection $\phi$, such that the two metric spaces $(\Omega, r_W)$ and $(\Omega', r_{W'})$ are linked by the equality $r_{W'}(x, y) = r_W(\phi(x), \phi(y))$ on a subset of measure 1, say $\Sigma \subseteq \Omega'$ with $\mu'(\Sigma) = 1$. This means that both subspaces $(\phi(\Sigma), r_W)$ and $(\Sigma, r_{W'})$ are linked by a bijection that preserves the distances, which directly implies equality between their covering numbers: $N_{\phi(\Sigma)}^{(c)}(\epsilon) = N_{\Sigma}^{(c)}(\epsilon)$ for all $\epsilon > 0$.

Then, for proving Lemma 3, it is enough to show the two following inequalities

$$N_{\Omega}^{(c)}(\epsilon) \geq N_{\phi(\Sigma)}^{(c)}(\epsilon + \delta) \qquad (24)$$

$$N_{\Sigma}^{(c)}(\epsilon + \delta) \geq N_{\Omega'}^{(c)}(\epsilon + \delta) \qquad (25)$$

for any $\delta > 0$. Indeed, combining these two inequalities with the covering number equality from the above paragraph, one has $N_{\Omega}^{(c)}(\epsilon) \geq N_{\Omega'}^{(c)}(\epsilon + \delta)$. Taking the limit $\delta \to 0$ and using the right-continuity of the covering number (Lemma 24), this gives $N_{\Omega}^{(c)}(\epsilon) \geq N_{\Omega'}^{(c)}(\epsilon)$. As the reverse inequality holds by symmetry of the proof, one obtain the equality $N_{\Omega}^{(c)}(\epsilon) = N_{\Omega'}^{(c)}(\epsilon)$ of Lemma 3.

**Lemma 24** Given a pure graphon $(\Omega, \mu, W)$, the function $\epsilon \mapsto N_{\Omega}^{(c)}(\epsilon)$ is piecewise constant and right-continuous (note that we use closed balls in the definition). Likewise, $\epsilon \mapsto N_{\Omega}^{(p)}(\epsilon)$ is a right continuous piecewise function.

Assume $\Sigma$ is dense in $(\Omega', r_{W'})$. Each cover of $\Sigma$ is closed as a finite union of closed balls. Hence it is also a cover of $\Omega'$ by density of $\Sigma$ in $\Omega'$. This proves (25). Likewise, assume $\phi(\Sigma)$ is dense in $(\Omega, r_W)$. An $\epsilon$-cover of $\Omega$ can be transformed into an $(\epsilon + \delta)$-cover of $\phi(\Sigma)$ by moving the ball centers from $\Omega$ to $\Sigma$ and increasing the ball radius of $\delta$ (for arbitrary small $\delta$). This proves (24) for any $\delta > 0$.

Let us show the density of $\phi(\Sigma)$ in $(\Omega, r_W)$. One has $\mu(\phi(\Sigma)) = \mu'(\Sigma) = 1$ by definition of a (bijective) measure-preserving map, which implies that $\phi(\Sigma)$ intersects each ball of non-zero measure in $(\Omega, r_W)$. As the measure of a pure graphon has full-support by definition, then each ball of non-zero radius has a non-zero measure. Thus, $\phi(\Sigma)$ intersects each ball of non-zero radius in $(\Omega, r_W)$, which means that $\phi(\Sigma)$ is dense in $(\Omega, r_W)$. Similarly, we can show the density of $\Sigma$ in $(\Omega', r_{W'})$.

Lemma 3 is proved for the covering number. The proof for the packing number is similar and omitted. ■