{'fraction_non_alphanumeric': 0.062448344596237056, 'fraction_numerical': 0.01802469736010501, 'mean_word_length': 3.6463180483397335, 'pattern_counts': {'":': 0, '<': 7, '<?xml version=': 0, '>': 37, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 70, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
On the Estimation of Network Complexity: Dimension of Graphons

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 so-called neighborhood distance that measures the propensity of two nodes to be connected with similar nodes. Our complexity index is then based on the covering number and the Minkowski dimension of (a purified version 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 of random graphs: 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\"older graphon models. 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.


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 andMowshowitz, 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.

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 ω i is drawn from a distribution µ on a space Ω (where Ω 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 (ω i , ω j ), where W : Ω × Ω → [0, 1] is a symmetric function. Thus, a W-random graph is specified by the triplet of parameters (Ω, µ, 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 ω i and Ω are latent (unobserved). In fact, all parameters of the graphon (Ω, µ, 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.

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 Ω = [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 Ω 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 Ω = [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 α if W is α-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 (Ω, µ, W ), we endow the latent space Ω with the so-called neighborhood distance From the above description of a W-random graph, we can see that the quantity r W (ω i , ω 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 (Ω, r W ). The purification process is detailed in section 3.1.
Recall the definitions of these two standard measures for metric spaces: the -covering number N (c) Ω ( ) is the minimal number of balls of radius required to entirely cover the (pseudo-) metric space (Ω, r W ). And the Minkowski dimension is the following limit on the covering number when the limit exists. In particular, the Minkowski dimension does not have to be an integer.
Although none of the three parameters Ω, µ and W are identifiable in the W-ranom graph model, we prove that the covering number and the Minkowski dimension of a purified version of (Ω, 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 (c) Ω ( ) is equal to the number of well-spaced communities in the stochastic block model; that dim Ω matches the dimension of the Euclidean space in some random geometric graphs; and that dim Ω 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].

Statistical estimation
From the observed adjacency matrix A of a W-random graph, we estimate the neighborhood distance (1) on the sampled points ω 1 , . . . , ω n . The corresponding distance estimator r is defined in Section 4.1. We show universal nonasymptotic bounds for its risk (Theorem 1.1). Let ω m(i) ∈ {ω 1 , . . . , ω n }\{ω i } denote a nearest neighbor of ω i with respect to the distance r W .
In the upper bound, there is a bias term r W (ω j , ω m(j) ) which is the distance between the sampled point ω j and its nearest neighbor ω m(i) (w.r.t. the neighborhood distance). This bias depends on the form of the underlying graphon (Ω, µ, 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 Ω = [0, 1]). We also derive a minimax lower bound that matches the upper bound of Theorem 1.1. See Section 4.2 for details on the distance estimation. Based on the estimated distances r(i, j), we estimate the covering number N (c) Ω ( ) 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 N (c) Ω with formula (2), we derive an estimator of the Minkowski dimension which satisfies a high probability convergence rate (Theorem 1.2). For this result, we assume the Mikowski dimension is upper bounded by some constant D and use a particular radius 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 1.2 Under some mild assumptions, defined in Section 4.4, the following holds. If dim Ω is any real in [0, D], then dim D − dim Ω 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 (Ω, 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).

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 (Ω, µ, 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.

Graphon estimation
There has been much interest in the recovery of the function W (or the matrix of probabilities [W (ω i , ω j )] i,j≤n ) on the specific space Ω = [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 neighborhoodsmoothing [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 Ω = [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 problem of estimation of W , the latent space [0, 1] is sometimes considered instead of Ω. This choice is not restrictive (if no assumption is made on the function W on [0, 1]) because both settings generate the same Wrandom graph distributions [Lovász, 2012]. However, the restricted setting [0, 1] is not always convenient to work with, whereas the general setting Ω leads to simpler and cleaner situations [Lovász, 2012]. Indeed, many random graph distributions are naturally represented on Ω 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 (ω i , ω j )] i,j≤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.

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 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 ω 1 , . . . , ω n , and we are not in the Euclidean metric space 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 b, if there exists a constant C such that a ≤ Cb; and note a b, if there exist two constants c, c such that ca ≤ b ≤ c a. We denote by a ∨ b (respectively a ∧ b) the maximum (resp. minimum) between a and b; by [a] + the maximum between 0 and a; by [n] the set {1, . . . , n}; by B(x, ) a ball of radius and center x. We note 1 E the indicator function corresponding to any event 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.

Setting
For a set of vertices V = {1, . . . , n}, a W-random graph G = (V, E) is generated as follows. Let (Ω, µ, W ) be an unknown triplet of parameters, which is composed of a measurable set Ω, a probability measure µ on Ω, and a symmetric (measurable) function W : Ω × Ω → [0, 1]. For each node i ∈ V , an unknown attribute ω i ∈ Ω is drawn in an i.i.d. manner from the distribution µ. Conditionally to the attributes ω = (ω 1 , . . . , ω n ), an edge connects two vertices i and j, independently of the other edges, with probability W (ω i , ω j ).
Our data are a single observation of the W-random graph. Formally, it is an adjacency matrix A = [A ij ] i,j≤n defined by A ij = 1 if (i, j) ∈ 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 P (Ω,µ,W ) . The set of graphons is written W.

Non-identifiability and equivalence class of graphons
From the observation A, the function W is not identifiable. Indeed, for any measure-preserving bijection φ : Ω → Ω, we can observe that the map W φ (x, y) = W (φ(x), φ(y)) leaves the data distribution unchanged, i.e.: In fact, even the latent space Ω is not identifiable. The full picture is described by Lovász [2012, chap.10]: Two graphons (Ω, µ, W ) and (Ω , µ , W ) parametrize the same data distributions for all n, if and only if, there exist some measurepreserving maps φ : [0, 1] → Ω and ψ : 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/ ∼, which is the set of equivalence classes of graphons leading to the same data distributions.

Complexity index
Given a graphon (Ω, µ, W ), we endow the latent space Ω with the neighborhood distance which is the l 2 -norm ||W (ω, .)−W (ω , .)|| 2,µ between the slices of the function W in ω and ω . Then, we measure the complexity of the pseudo-metric space (Ω, r W ) in a classic way, using its covering number N (c) Ω ( ) and its Minkowski dimension: 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 (Ω,µ,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 (Ω, µ)). 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 Ω.

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 (Ω, µ, 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 (Ω, µ, W ) is called pure if (Ω, 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 µ has full support by definition) and the complexity index takes the same value on the pure graphons of a same equivalence class of W/ ∼ (Lemma 3.1).
Lemma 3.1 If two pure graphons are equivalent, then their covering numbers are equal.
The proof of Lemma 3.1 is written in Appendix C.2. Lemma 3.1 directly implies that the Minkowski dimension takes the same value for two equivalent pure graphons. We now define the complexity of a W-random graph distribution P (Ω,µ,W ) 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 therefore identifiable from P (Ω,µ,W ) . 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/ ∼. 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 3.2).
Lemma 3.2 Let (Ω, µ, W ) and (Ω , µ , 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/ ∼, then for some bijective measurepreserving map φ : Ω → Ω, we have Lemma 3.2 states that the metric spaces (Ω, r W ) and (Ω , r W ) are isometric up to a null-set, it is therefore not surprising that they share the same covering number (Lemma 3.1). The proof of lemma 3.2 is written in Appendix C.1. Note that Lemma 3.2 ensures that the future distance estimation is a well-posed problem.
Another consequence of working with pure graphon is that the sample ω 1 , . . . , ω n is asymptotically dense in Ω. Lemma 3.3 is proved in Appendix C.3. Lemma 3.3 For a pure graphon (Ω, µ, W ) such that N (c) Ω ( ) < ∞ for all > 0, the sample ω 1 , . . . , ω n is asymptotically dense in the metric space (Ω, r W ). That is, for all radii > 0, the event E( ) = {each ball of radius in (Ω, r W ) contains at least a sampled point ω i } holds with a probability tending to one as n → ∞.

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 Ω = {c 1 , . . . , 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 -covering number of {c 1 , . . . , c K } for small radii .
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 3.4 states that, for any graphon (Ω, µ, W ), the function W can be "O( )-approximated" in l 2 -norm by an SBM with at most N Random Hölder graph. Let Ω = [0, 1] d be endowed with the uniform measure, and W fulfill a double Hölder condition: for some Hölder exponent α > 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 α of smoothness. This intuitive notion is matched by the Minkowski dimension, which is equal to d/α. 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 Ω = [0, 1] d be endowed with the uniform measure and the indicator function W (ω, ω ) = I ||ω−ω || 2 ≤δ for some constant δ > 0. Appendix A shows that dim Ω = 2d. Thus, the Minkowski dimension matches the Euclidean dimension of the latent space, up to a factor 2.

Estimation of the complexity index
Given a pure graphon (Ω, µ, W ), assume a W-random graph is generated from the probability distribution P (Ω,µ,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 (Ω, µ, W ) is unknown, and the sampled points ω 1 , . . . , ω n are not observed.
This section is organized in the following manner. We first estimate the neighborhood distance (4) on the sampled points ω 1 , . . . , ω n . Based on these estimated distances, we then estimate the -covering number of ({ω 1 , . . . , ω n }, r W ) by plug-in. Denote by N

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 Ω, we write their inner product f, g := Ω f (z)g(z)µ(dz). Let W (ω i , .) denote the function x → W (ω i , x), then the neighborhood distance admits the following decomposition 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 A i , A j n = n i=1 A ik A jk /n the inner product between two such rows. Given ω i , ω j , we observe that A i , A j 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 ∈ [n] and k = i, j} are independent with the same mean conditionally to ω i , ω j : where the mean E is taken over the data distribution P (Ω,µ,W ) . It is therefore possible to use Hoeffding's inequality to prove that | A i , A j n − W (ω i , .), W (ω j , .) | log n/n w.h.p. (see Proposition D.1 in Appendix D.1). Thus, the inner product between two different rows is a consistent estimator of the crossed term W (ω i , .), W (ω j , .) in (7).
To estimate the remaining quadratic term W (ω i , .), W (ω i , .) in (7), we cannot proceed in the same way since 1 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 ω m(i) ∈ {ω 1 , . . . , ω n } denote a nearest neighbor of ω i according to the distance r W , that is m(i) ∈ argmin t: t =i r W (ω i , ω t ), then we have the following approximation: using Cauchy-Schwarz inequality. Thus, the nearest neighbor approximation (8) entails a bias in our estimation procedure, which is equal to the distance between ω i and its nearest neighbor ω m(i) . Since the index m(i) is unknown, we define an index estimator m(i) such that ω m(i) is hopefully close to ω i according to r W , and then we use A i , A m(i) n to estimate the quadratic term. Formally, m(i) is a minimizer of the distance function j → f (i, j) defined by where 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 Note that f (i, j) is small in expectation if ω i and ω j are close according to the Putting together the estimators of the crossed term and the two quadratic terms, we get the following estimator of the square distance r 2 W (ω i , ω j ): for all i, j ∈ [n], where 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], λ, W ) with λ 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.

Consistency of the distance-estimator
The statistical recovery of the set of distances {r W (ω i , ω j ) : i, j ∈ [n]} is a well-posed problem, since the neighborhood distance is invariant on each equivalence class of graphons (Lemma 3.2). Theorem 4.1 gives nonasymptotic error bounds for the distance-estimator (11). The proof is written in Appendix D.1.
Theorem 4.1 Given any (pure) graphon (Ω, µ, W ), consider the data distribution P (Ω,µ,W ) defined in model (3). For all 1 ≤ i ≤ n, let ω m(i) ∈ {ω 1 , . . . , ω n } \ {ω i } denote a nearest neighbor of ω i according to the distance r W . Then, for the distance-estimator (11), the event Theorem 4.1 implies that the distance-estimator (11) is a consistent estimator of the neighborhood distance (4), provided that the -covering number is finite for all radii > 0. Indeed, for a finite covering number, Lemma 3.3 ensures that the sample ω 1 , . . . , ω n is asymptotically dense in (Ω, r W ), which implies that the bias r W (ω i , ω m(i) ) is convergent in probability to zero as n grows to infinity.
Let us describe the upper bound of Theorem 4.1. On the one hand, there is a fluctuation term log(n)/n that corresponds to the convergence property of the inner products between rows of A, i.e.: On the other hand, there is a bias term r W (ω i , ω 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 (ω i , ω m(i) ) is equal to zero w.h.p. (indeed, ω i and its nearest neighbor ω 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) α/d w.h.p..
We now discuss the optimality of the upper bound of Theorem 4.1. As the event E dist is a uniform error bound on square distances, we may expect the bias term to be a square distance too (instead of a distance as in Theorem 4.1). Indeed, this expected bias r 2 W (ω i , ω m(i) ) would improve on r W (ω i , ω m(i) ) since the neighborhood distance r W is always smaller than 1 by definition. Then, one may wonder whether such an improvement is possible. It turns out that even replacing the bias r W (ω i , ω m(i) ) by r 1+γ W (ω i , ω m(i) ) for some γ > 0 is impossible. Indeed, no estimator d simultaneously satisfies the following inequalities ∀i, j ∈ [n] : w.h.p. for all graphons (Ω, µ, W ) and some numerical constant C. Specifically, Theorem 4.2 states that, for a sequence of graphons (Ω, µ, W n ) 1≤n , the (uniform) bound (12) cannot be achieved by any estimator d 1 .
Theorem 4.2 There exist a sequence of graphons (Ω, µ, W n ) n∈N and some numerical constants p > 0 and c > 0, such that the following holds for any estimator d and any permutation σ of the n indices. With a probability larger than p, the lower bound is satisfied for (at least) c n different pairs (i, j).
Hence, the uniform bound (12) cannot be achieved, implying that the upper bound of Theorem 4.1 is optimal. Note that the data distribution is invariant by relabeling of the nodes, and consequently we study the problem of estimating a set of distances (i.e., regardless of their labels i ∈ {1, . . . , n}). Accordingly, the above lower bound holds for any permutation σ of the n indices {1, . . . , n}. For a proof of Theorem 4.2, see Appendix D.2.

Consistency of the covering number estimator
We have defined the -covering number estimator N 1 defined as a function of the adjacency matrix A ∈ {0, 1} n×n .
Then, the covering number estimator is linked with the true covering number of {ω 1 , . . . , ω n } by the following inequalities To compare the covering numbers of {ω 1 , . . . , ω n } and Ω, we need to measure the difference between the sample ω 1 , . . . , ω n and the space Ω. We do so by introducing the sampling error s ω defined as which is the greatest distance that separates a point of Ω from the set {ω 1 , . . . , ω n }. Thus, the covering numbers (w.r.t. the true distance r W ) of ω 1 , . . . , ω n and Ω are linked by the following inequalities Theorem 4.1 ensures that e sup ≤ b sup with probability at least 1 − 2/n. From the above displays, we obtain the following proposition.
Proposition 4.3 Given any (pure) graphon (Ω, µ, W ), consider the data distribution P (Ω,µ,W ) defined in model (3). Let b sup and s ω be the distance error bound (14) and the sampling error (13). Then, the estimator N (c) Ω satisfies the following non-asymptotic bounds with probability at least 1 − 2 n according to the distribution P (Ω,µ,W ) .
As a result, we have a consistent estimation of the -covering number for almost every , provided that the covering number is finite for all radii. Indeed, if N (c) Ω ( ) < ∞ for all > 0, then the sample ω 1 , . . . ω n is asymptotically dense in (Ω, r W ) by Lemma 3.3, which implies that b sup and s ω converge in probability to zero; Then, taking the limit n → ∞ in (15), one has the convergence in probability of N

Consistency of the dimension estimator
We estimate the Minkowski dimension of (Ω, r W ) using the data-function − log N (c) Ω ( ) log at a well chosen radius . 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 ), the covering number may just count the points of the sample ω 1 , . . . , ω 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 N Hence, we consider a subset of graphons for which there exists a radius that is well-suited for dimension estimation. We sometimes denote dim Ω by d for brevity, and write B(ω, ) the ball of center ω ∈ Ω with radius (w.r.t. the neighborhood distance). Given constants D, v, α > 0 and M ≥ 1 ≥ m > 0 , we define the set W(D, α, m, M, v) of all (pure) graphons (Ω, µ, W ) satisfying 2. For dim Ω := d and all ∈]0, v], The assumption H m,M,v 2 links the covering number with the Minkowski dimension of the graphon. The condition H α,v 1 enforces a minimal measure for each ball of (Ω, 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 α,v 1 may be seen as a small-ball condition used in learning problems [Mendelson, 2014, Lecué et al., 2018.
With the radius we consistently estimate the Minkowski dimension (Theorem 4.4) using the following estimator Theorem 4.4 is a corollary of Theorem E.1 in Appendix E.1, which gives a non-asymptotic high probability bound for −log N (c) Ω ( ) log at any radius .
One can observe that the convergence rate log −1 n of Theorem 4.4 is optimal, in the sense that faster convergence rates cannot be achieved by any estimator of the form log N which is (at least) of the order log −1 n since the radius 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 3 can improve on the error bound log −1 n, over the following sequence of sets. Given n > 0, let Ω is any consistent estimator of the covering number, andˆ is any estimator of a "well chosen radius" 3 defined as a function of the adjacency matrix A ∈ {0, 1} n×n .
be the class of all (pure) graphons fulfilling, for all > 1/n, the conditions of the above set W(D, α, m, M, v). On this sequence of sets, one can readily extend Theorem 4.4 and retrieve the same error bound, using the same estimator (17). This means that there exist some constants C(D, α, m, M ) and C (α, M ) that are independent of n, such that for all graphons in W n (D, α, m, M, v) and all large enough n, the following error bound holds with probability at least 1 − C (α, M )/n. Then, Theorem 4.5 shows that no estimator can improve on the (order of the) bound (18). The proof is written in Appendix E.2.
Theorem 4.5 For any D > 2, some numerical constants α, m, M, v > 0 and all large enough n, we have where inf d is the infimum over all estimators.
Let us discuss the minimal aspect of the conditions defining W n (D, α, m, M, v). First, the assumption that the dimension is upper bounded seems natural, as our available data A ∈ {0, 1} n×n is a finite set. Indeed, for metric spaces (Ω n , r Wn ) with arbitrary large dimensions (like dim Ω n /n → ∞ for instance), a finite sample ω 1 , . . . , ω n may look like a set of distant and isolated points, which does not reflect the true geometry of (Ω n , r Wn ). Since this situation is not conducive to accurate estimates of the complexity of Ω n , we avoid it by assuming the dimension is upper bounded. Second, we show that the assumptions H α,v 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 R m whose dimension is an integer. In contrast, here we do not assume the dimension is an integer, not observe the n sampled points ω 1 , . . . , ω n , and not know the metric r W .

Comments on
Let us briefly explain how these assumptions imply the error bound of Theorem 4.4. The assumption H α,v 1 ensures that the difference between the sampled points ω 1 , . . . , ω n and the latent space Ω 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 D that is larger than these two errors, and reliably estimate the D -covering number N . To sum up, the radius D must be larger than the sampling and distance errors, but still small enough to well approximate the Minkowski dimension with − log N (c)

Testing the complexity
Given the adjacency matrix of a W-random graph, we want to known if the graph is simple or complex. In other words, we would like to test the null-hypothesis N (c) Ω ( ) ≤ 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 (p) Ω ( ) 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 4.3 N (c) is difficult to leverage for an under-estimation since the errors b sup and s ω are unknown and take specific values for each graphon. However, we show below that the sampling error s ω 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 distanceestimator r, defined earlier by (11). Based on the distance estimator r, we can define a plug-in estimator N (p) Ω ( ) 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 4.3. The proof is omitted.
Proposition 5.1 Given any graphon (Ω, µ, W ), consider the data distribution P (Ω,µ,W ) defined in model (3). Let b sup and s ω be the distance error bound (14) and the sampling error (13). Then, the packing number estimator N (p) Ω satisfies the following inequalities with probability at least 1 − 2 n with respect to the distribution P (Ω,µ,W ) .
Hence, we have N (p) without the sampling error s ω anymore. The next step is to control the remaining error term b sup . We do so by modifying the previous estimator r as follows: , and provides the underestimation of the packing number (Theorem 5.2). The proof is written in Appendix G.1.
Theorem 5.2 Given any graphon (Ω, µ, W ), consider the data distribution P (Ω,µ,W ) defined in model (3). Then, for the radius = √ 2 + t n with t n = 12 log n n , the estimator N (p.new) Ω satisfies the following inequalities with probability at least 1 − 2 n with respect to the distribution P (Ω,µ,W ) .
Thus, without any assumption on the graphon, the estimator N (p.new) Ω ( ) does not overestimate the -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 N (p) Ω of the packing number (seen in Proposition 5.1).

Results on the packing number test
We accept the null hypothesis if and only if N (p.new) Ω ( ) ≤ K. The upper bound (20) ensures that the type I error is controlled for all graphons, which gives the following result.
Corollary 5.3 For any graphon, the type I error is lower than 2 n with respect to the distribution P (Ω,µ,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 + 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 η > 0 and β > 1/n, let W(η, β) denote a collection of graphons for which there exist K + 1 balls 2. the radii are small enough: 3. the centers are spaced enough: The small-ball condition 1. is similar to the assumption H α,v 1 for the dimension estimation; it ensures that some of the sampled points ω 1 , . . . , ω 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 N (p.new) Ω ( ) ≥ K + 1 and confirm the alternative hypothesis correctly.
The proof of Theorem 5.4 is written in Appendix G.2. This result implies that, for any graphon in W(η, β), the type II error is convergent to zero as soon as the measure of each ball B(x i , η i ) is large enough to satisfy β 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 5.4 is improved by using the graphon regularity at a finer level (see Theorem A.1).
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 ρ n such that ρ n → 0, the definition of model (3) can be modified to have average node degrees of the order of ρ n n. Consider the adjacency matrix A, defined by model (3), whose edges are independently retained with probability ρ n and erased with probability 1 − ρ n . We refer to this set-up as "the sparse setting" and denote by P (Ω,µ,W ),ρ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 6.1 gives non-asymtotic error bounds for the distance estimation. It is a slight variant of Theorem 4.1. For completeness, the proof is written in Appendix F.1.
We estimate the Minkowski dimension using the following radius  (21), and all radii satisfying (22), the following rate of estimation of the dimension holds with probability tending to 1 as n → ∞ (w.r.t. the distribution P (Ω,µ,W ),ρn ).

Polynomial-time algorithm (with some theoretical guarantees)
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 (c) Ω ( ) is described below. The algorithm proceeds in two steps: Step 1 computes all distances r(i, j) using the distance-estimator (11); in particular, this step requires the computation of all index estimators m(j) defined by (10).
Step 2 approximates the -covering number of {1, . . . , n} w.r.t. the distance estimator r, by sequentially selecting balls (of radius ) 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 N (ap.c) Ω ( ).

Covering Number Algorithm
Input: A = [A ij ] 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 2. Compute all the distances: Step 2 : computing an approximation of the -covering number We also suggest an heuristic for tuning in the estimation of the Minkowski dimension. First, run several times Covering Number Algorithm for a range of different radii 1 , . . . , t , and then plot log N (ap.c) Ω ( j ) log j for j = 1, . . . , 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, 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) = I ||x−y|| 2 ≤0.1 , which has a Minkowski dimension 2 and satisfies the assumptions of Theorem 4.4. We sample n = 1000 points uniformly on [0, 1] and plot the outputs −log N (ap.c) Ω ( ) log over the range of radii ∈ 0.005 + k * 0.005 ; k ∈ {0, . . . , 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 → 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 ω 1 , . . . , ω n . As a reference, we also

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) ( ) is the minimal number of balls of radius 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) ( ) is the maximum number of points in a given space (strictly) separated by at least a given distance . Both measures are similar and linked by the following inequalities N (c) ( ) ≤ N (p) ( ) ≤ N (c) ( /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 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 →0 − log N (c) ( ) log . Note that the same formula holds with the packing number instead. The Minkowski dimension is useful for infinite (separable) spaces, when the covering number diverges to infinity as 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 (Ω, µ, W ) is ([0, 1] d , λ, W ) where λ is the uniform measure on [0, 1] d and W satisfies the following condition: there exist three constants m, M, α > 0 such that for all ω, ω , ω ∈ where α is the level of regularity of the function W and ||ω − ω|| 2 is the Euclidean distance between ω and ω in [0, 1] d . From the above display, we directly deduce some bounds on the neighborhood distance (4) : Thus, the distance r W behaves (up to some constants) like the Euclidean distance on [0, 1] d raised to the power of α. As the covering number of the Euclidean hypercube ([0, 1] d , ||.|| 2 ) is approximately equal to −d for small radii, we have ( /m) −d/α N (c) Ω ( ) ( /M ) −d/α . Hence dim Ω = d/α, which means that the Minkowski dimension of (Ω, 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 .

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(η, β) of graphons with K + 1 well separated balls (Theorem 5.4), here we consider the new set W(η, β, 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(η, β) (in Theorem 5.4). 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(η, β, M, K ) of graphons is linked with the previous one by the following equality W(η, β, 1, 0) = W(η, β).
Theorem A.1 If the underlying graphon belongs to W(η, β, M, K ) with β ≥ 1/n, then the type II error is smaller than 2 n + p M n , where p n admits the following upper bound .
The proof of Theorem 5.4 is written in Appendix G.2.

B Proofs for illustrative examples B.1 Proof of Proposition 3.4: approximation by SBM
Given a graphon (Ω, µ, W ) and a radius > 0, we consider a cover of (Ω, r W ) whose the cardinality is N (c) Ω ( ) (written N for brevity), and the ball centers are x 1 , . . . , x N . The Voronoi cell V j of x j is the set of all elements in Ω that are closer to x j than to any other x k , k = j, according to the metric r W . In the case of equality, where a point ω is at equal distance of several ball centers x i , it belongs to the Veronoi cell of smallest index i.
Define the SBM approximation of W as follows: By triangular inequality and Jensen inequality, the expression Note that the first term is smaller than 8 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 which is again smaller than 8 2 . The approximation error of W by W is therefore lower than 4 in l 2 -norm. The proposition is proved.

B.2 The neighborhood distance for the random geometric graph example
. As a consequence, ||x − y|| 2 r W (x, y) ||x − y|| 2 as soon as ||x − y|| 2 is small enough (compared to δ).
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δ, then Proof of Lemma B.1. For the random geometric graph, observe that the computation of the neighborhood distance is equivalent to the computation of the volumes of hypersherical 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δ, then where x = 1 − ||x−y|| 2 2δ 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δ, then . 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 Eq.8.17.21]. It follows that r W satisfies the following bounds: ||x − y|| 2 r W (x, y) ||x − y|| 2 as soon as ||x − y|| 2 is small enough. C Identifiability and pure graphons C.1 Proof of Lemma 3.2 : invariance of the neighborhood distance Given two equivalent pure graphons (Ω, µ, W ) and (Ω , µ , W ), let us show that their respective neighborhood distances r W and r W are linked by the following µ ⊗ µ -almost surely equality for some measure-preserving bijection φ : Ω → Ω. It follows from Lemma C.1, which links any two equivalent pure graphons. Denote by W φ the function (x, y) → W (φ(x), φ(y)).
Indeed, by definition of the neighborhood distance, which gives the following µ ⊗ µ -almost surely equality by Lemma C.1, for some measure-preserving bijection φ : Ω → Ω. Then, using a pushforward measure (or image measure), µ ⊗ µ -almost surely, so that, by definition of the neighborhood distance, µ ⊗ µ -almost surely. Lemma 3.2 is proved.

C.2 Proof of Lemma 3.1 : identifiability of the covering number
Given two equivalent pure graphons (Ω, µ, W ) and (Ω , µ , W ), let us prove that their respective covering numbers are equal: N (c) According to Lemma 3.2, there exists a measure-preserving bijection φ, such that the two metric spaces (Ω, r W ) and (Ω , r W ) are linked by the equality r W (x, y) = r W (φ(x), φ(y)) on a subset of measure 1, say Σ ⊆ Ω with µ (Σ) = 1. This means that both subpaces (φ(Σ), r W ) and (Σ, r W ) are linked by a bijection that preserves the distances, which directly implies equality between their covering numbers: N for any δ > 0. Indeed, combining these two inequalities with the covering number equality from the above paragraph, one has N (c) Ω ( + δ). Taking the limit δ → 0 and using the right-continuity of the covering number (Lemma C.2), this gives N Assume Σ is dense in (Ω , r W ). Each cover of Σ is closed as a finite union of closed balls. Hence it is also a cover of Ω by density of Σ in Ω . This proves (25). Likewise, assume φ(Σ) is dense in (Ω, r W ). An -cover of Ω can be transformed into an ( + δ)-cover of φ(Σ) by moving the ball centers from Ω to Σ and increasing the ball radius of δ (for arbitrary small δ). This proves (24) for any δ > 0.
Let us show the density of φ(Σ) in (Ω, r W ). One has µ(φ(Σ)) = µ (Σ) = 1 by definition of a (bijective) measure-preserving map, which implies that φ(Σ) intersects each ball of non-zero measure in (Ω, 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, φ(Σ) intersects each ball of non-zero radius in (Ω, r W ), which means that φ(Σ) is dense in (Ω, r W ). Similarly, we can show the density of Σ in (Ω , r W ).
Lemma 3.1 is proved for the covering number. The proof for the packing number is similar and omitted.
Proof of Lemma C.2. The function → N (c) Ω ( ) is non-increasing from [0, ∞[ to the set of all non-negative integers, it is therefore a piecewise constant function. Thus, for any radius 0 > 0, there exists a (strictly) larger radius 1 such that the covering number N Given a radius and K points c = (c 1 , . . . , c K ) ∈ Ω K , denote by C Ω (c, ) the union of K balls of centers c 1 , . . . , c K . In the following, we prove: 1/ the existence of some c 0 ∈ Ω N such that C Ω (c 0 , ) covers Ω for all ∈] 0 , ( 1 + 0 )/2]; 2/ for such a c 0 , C Ω (c 0 , 0 ) covers Ω. Thus, Lemma C.2 will be proved.

Lemma C.3 (Cantor's intersection theorem)
Suppose that (X, d) is a complete metric space, and C n is a sequence of non-empty closed nested subsets of X whose diameters tend to zero. Then the intersection of the C n contains exactly one point, that is ∩ ∞ k=1 C k = {x} for some x in X.
Verification of the assumptions of Lemma C.3. Since (Ω, r W ) is a complete metric space by definition of a pure graphon, the product space (Ω N , r sup W ) is also complete for the sup-distance r sup W (x, y) := sup 1≤j≤N r W (x j , y j ) with x = (x 1 , . . . , x N ), y = (y 1 , . . . , y N ) ∈ Ω N . By definition of E k , the sequence ( E k ) k is composed of nested sets, which are also non-empty since N (c) Ω ( ) = N over ] 0 , 1 [. To prove that each E k is a closed subset of Ω N , it is enough to show that E Ω ( ) is closed for any ∈] 0 , 1 [. Let (x k ) k≥0 be a sequence in E Ω ( ) such that x k → x ∈ Ω N as k → ∞. Then, for any η > 0, there exists some k 0 such that the sup-distance between x k 0 = (x k 0 1 , . . . , x k 0 N ) and x = (x 1 , . . . , x N ) is at most η. As x k 0 ∈ E Ω ( ), one know that, for any y ∈ Ω, there exists some j 0 such that r W (y, x k 0 j 0 ) ≤ . Thus, using the triangle inequality, one has for any η > 0, which implies that r W (y, x j 0 ) ≤ . Hence, y ∈ C Ω (x, ) for any y ∈ Ω, which means that x ∈ E Ω ( ). E Ω ( ) is therefore a closed subset of Ω N . All the conditions of Lemma C.3 are checked. The part of Lemma C.2 on the covering number is proved. For the packing number, the proof is similar and omitted.

C.3 Proof of Lemma 3.3: asymptotic density of the sample
Given > 0, consider a cover of (Ω, r W ) whose cardinality is the integer N (c) Ω ( /4) (written N for brevity) and whose balls are written B 1 , . . . , B N . Let us upper bound the probability that (at least) one of these balls contains zero sampled point ω i . Using the union bound, this probability is smaller than N j=1 P (Ω,µ,W ) {B j contains zero sampled point among ω 1 , . . . , ω n } which is upper bounded by N (1−µ(B j )) n ≤ N (1−β) n where β := min j∈[N ] µ(B j ). One has β > 0 since each ball of a pure graphon has non-zero measure. And as N is not equal to infinity by assumption, this probability tends to zero with n. Thus, with high probability, all balls B j from the cover contains at least a sampled point. Finally, the asymptotic density of the sample follows from the fact that each ball of radius of (Ω, r W ) contains a ball B j from the cover. Lemma 3.3 is proved. D Estimation of the neighborhood distance D.1 Proof of Theorem 4.1 : the upper bound Theorem 4.1 is a direct consequence of the two following propositions. Proposition D.1 shows the consistency of the inner products between the rows of the adjacency matrix A. That is, A i , A j n is convergent in probability towards W (ω i , .), W (ω j , .) if i = j. Actually, Proposition D.1 gives a uniform convergence over all i, j ∈ [n], i = j.
Proposition D.1 The following event on inner products log n n holds with probability P (Ω,µ,W ) (E in ) ≥ 1 − 2 n as soon as n ≥ 6.
We have seen that the neighborhood distance r W can be decomposed into one crossed term and two quadratic terms as follows (26) Proposition D.1 ensures that the crossed term is consistently estimated. Proposition D.2 deals with the quadratic terms W (ω i , .), W (ω i , .) .
The estimation error of (26) by our distance estimator Proof of Proposition D.1. By triangle inequality, the expression is smaller than which is upper bounded by for all k = i, j (where E is the expectation with respect to the distribution P (Ω,µ,W ) ). It follows from Hoeffding's inequality that for > 0 and n ≥ 4. Since the above inequality is satisfied for almost every ω i , ω j ∈ Ω, one has the same upper bound with probability 1 without conditioning. Hence, taking a union bound over all i = j one obtain Then, setting = 3 log n n gives P (Ω,µ,W ) 3 log n n smaller than 2/n.
Combining the above expressions, we get the following inequality with probability at least 1 − 2 n as soon as n ≥ 6.
Proof of Proposition D.2.
For the second term of the upper bound (27), by Proposition D.1 and Cauchy-Schwarz inequality. For the first term of the upper bound (27), if m(i) = m(i), by definition of m(i) and f in (9). We upper bound f (i, m(i)) as follows.

D.2 Proof of Theorem 4.2 : the lower bound
Theorem 4.2 is a corollary of Theorem D.3 (written below). Let r ω denote the n × n symmetric matrix with entries r W (ω i , ω j ), 1 ≤ i ≤ j ≤ n. Given a real δ > 0, a graphon (Ω, µ, W ), a permutation σ of {1, . . . , n} and an estimator d, we define where Φ (Ω,µ,W ) ( d , r ω ) is the number of pairs (i, j) where the estimator d is no better than our estimator r, roughly speaking. That is, Φ (Ω,µ,W ) ( d , r ω ) counts the pairs (i, j) for which the error of d is larger than the bias of our distance estimator r, which is r W (ω i , ω m(i) ) + r W (ω j , ω m(j) ) up to some numerical constants. We put an infimum over all permutations σ of the n indices because we consider the problem of recovery of the set of distances r W (ω i , ω j ), 1 ≤ i ≤ j ≤ n, regardless of their labeling. According to Theorem D.3, there exists a sequence of graphons (Ω, µ, W n ) such that for any estimator d, the quantity Φ (Ω,µ,Wn) ( d , r ω ) grows linearly with n (on an event of positive probability).
Theorem D.3 There exists a sequence (Ω, µ, W n ) n≥0 of SBM such that for all n ≥ 10, all δ ∈] 8 n−2 , 1/40[ and some numerical constants c > 0 and p > 0, the following lower bound holds where inf d is the infimum over all estimators. .
Proof of Theorem D.3. The proof follows the general scheme of reduction for testing two hypotheses [see Yu, 1997, Tsybakov, 2009. We start with the definition of some SBM with five communities where the latent space Ω is {C 1 , . . . , C 5 }. We then show that for these SBM, any distance estimator suffers from a large loss.
We now introduce two events R 1 and R 2 on the sampled points ω 1 , . . . , ω n , which lead to different sets of distances (for r W ), and yet are difficult to decipher for any estimator based on the adjacency matrix A. In addition, we want these two events to happen with a positive probability p that is independent of n. Observe that the union of the two communities C 1 , C 2 have a total weight 1 − 2η = 1 − 4/(n − 2) and thus concentrate most of the probability measure, whereas each of the remaining communities C 3 , C 4 , C 5 has a weight of the order of n −1 . It follows that most of the sampled points ω 1 , . . . , ω n belong to the communities C 1 , C 2 with large probability. In particular, the two following events R 1 = C 1 ∪ C 2 , C 4 , C 5 respectively contain n-2, 1, 1 sampled points R 2 = C 1 ∪ C 2 , C 3 respectively contain n-2, 2 sampled points happen with a positive probability that is independent of n (Lemma D.4).
One of the interests of the two events R 1 , R 2 is to lead to different sets of distances. Specifically, if R 1 (resp. R 2 ) holds, the random matrix r ω = [r W (ω i , ω j )] i,j∈[n] of distances is denoted by r 1 = [r 1 (i, j)] i,j∈[n] (resp. r 2 = [r 2 (i, j)] i,j∈ [n] ). We measure the difference between both matrices r 1 , r 2 of distances as follows: where Φ is the number of pairs (i, j) on which r 1 and r 2 are separated by at least the bias of our distance estimator r (up to some numerical constants). Note that this measure is independent of the labeling i ∈ {1 . . . , n} since an infimum is taken over all permutations σ of the n indices. Lemma D.5 ensures that r 1 and r 2 are different enough for a number of pairs (i, j) that is linear with n, regardless of their labeling.
Lemma D.5 There exists a numerical constant c such that Φ( r 1 , r 2 ) ≥ 2c n.
So far, we have two events of positive probability which lead to two different sets of distances. It remains to see that they are difficult to decipher from the observed adjacency matrix A (Lemma D.6). For simplicity, write P for P (Ω,µ,W ) in the following, and ω the n-tuple (ω 1 , . . . , ω n ), and {0, 1} n×n sym the set of binary symmetric matrices of size n × n.
Lemma D.6 For any M ∈ {0, 1} n×n sym , one has We now have all the ingredients to lower bound P Φ (Ω,µ,Wn) ( d, r ω ) > cn and prove Theorem D.3. For clarity, Φ (Ω,µ,Wn) ( d , r ω ) is denoted by Φ( d, r ω ) in the following. Then, one has By definition of the SBM, the matrix r 1 remains the same for any ω ∈ R 1 , up to a permutation of the labeling. Combining with the fact that Φ is independent of the labeling, one obtain that Φ( d, r 1 ) takes a same value for all ω ∈ R 1 . Similarly, Φ( d, r 2 ) takes the same value for all ω ∈ R 2 . Hence, the above display says that P Φ( d, r ω ) > cn is larger than P Φ( d, r 1 ) > cn|R 1 + P Φ( d, r 2 ) > cn|R 2 P(R 1 ) ∧ P(R 2 ) and since P(R 1 ) ∧ P(R 2 ) ≥ p by Lemma D.4, one has Then, combining the two last inequalities gives which gives the lower bound of Theorem D.3.
Then, we use the generalized triangle inequality of Lemma D.7 with B = d.
That is, which is larger than 2cn − Φ( d, r 1 ) by Lemma D.5. Combing the above displays, one has The line (31) is therefore proved and Theorem D.3 follows.
We now show the technical lemmas, used in the proof of Theorem D.3.
Proof of Lemma D.4. Let n ≥ 10. We show that each of the two events R 1 , R 2 occurs with a positive probability that is independent of n. By definition of the events, one has which is equal to the following expression for η = 2/(n − 2), which is larger than some positive numerical constant. Hence, Lemma D.4 is proved.
Proof of Lemma D.5. The proof consists in finding a lower bound of Φ(r 1 , r 2 ) that is linear with n. As Φ is independent of the labeling of the set of distances r 1 and r 2 , one can assume the two following labelings without the loss of generality. For the matrix r 1 (defined on the event R 1 ), assume the (n − 1) th and n th columns correspond to the two sampled points in {C 4 , C 5 }. For r 2 (defined on R 2 ), assume the (n − 1) th and n th columns correspond to the two sampled points in C 3 . Accordingly, the n − 2 first columns of r 1 and r 2 are associated with the sampled points in {C 1 , C 2 }.
We focus on the (n − 1) th and n th columns of r 2 corresponding to the points in C 3 . For the measure Φ, at least one these two columns will be necessarily compared to one of the n − 1 first columns of r 1 . In other words, the distances associated with a point in C 3 will be compared to the distances associated with a point in C 1 , C 2 or C 4 . As we can see in Table 1 and 2, such comparisons will lead to the lower bound Φ(r 1 , r 2 ) ≥ n − 3. The corresponding computation are done below, focusing on the two vectors of distances [r 2 (k, n − 1)] k≤n−2 and [r 2 (k, n)] k≤n−2 .
By definition, Φ(r 1 , r 2 ) is based on the infimum over all permutations. Let σ be any permutation of {1, . . . , n} and prove the lower bound for σ, distinguishing three cases.
It remains to upper bound the bias terms by 2δ. The ones related to r 2 are easily obtained: for all j ≤ n, r 2 (j, m(j)) ≤ r W (C 1 , C 2 ) ≤ 2η ≤ δ since on the event R 2 , a point ω j is either in C 1 ∪ C 2 and hence r 2 (j, m(j)) ≤ r W (C 1 , C 2 ), or in C 3 and thus r 2 (j, m(j)) = 0 (because its nearest neighbor is in C 3 too). This gives the bounds on the bias terms r 2 (i, m(i)) + r 2 (j, m(j)) ≤ 2 δ for all i, j. The corresponding bounds for r 1 are similarly obtained from Table  1, but with more calculations. It is therefore encapsulated in the following lemma.
Combining the above displays, we obtain the lower bound for all permutations fulfilling σ(n) = n.
Finally, the lower bound (32) is true for all permutations σ, in particular for the infimum over all of them. Lemma D.5 is proved.
Proof of Lemma D.6. In the following, we write P for P (Ω,µ,W ) , and µ ⊗n for the product measure, and ω for the n-tuple (ω 1 , . . . , ω n ). Lemma D.6 states that for all M ∈ {0, 1} n×n sym , which is equivalent to where p R 1 (M ) denotes Hence, we want to prove that since 2P(R 1 ) = P(R 2 ) by definition of the events R 1 and R 2 .
Proof of Lemma D.9. For brevity, write P for P (Ω,µ,W ) in the following. By definition, X M σ kl (ω n−1 , ω n ) is the product of the n − 2 following terms ω i ∈C 1 ∪ C 2 P(A i,n−1 = M σ kl i,n−1 |ω i , ω n−1 ) P(A i,n = M σ kl i,n |ω i , ω n ) dµ(ω i ) i = 1, . . . , n − 2. The above display is equal to If (ω n−1 , ω n ) ∈ C 4 × C 5 , then which is equal to 1/2 + (2M kl i,n−1 − 1)(2M σ kl i,n − 1)δ µ(C 1 ). Hence X M σ kl (ω n−1 , ω n ) is equal to the same constant whether (ω n−1 , ω n ) belongs to C 3 × C 3 or C 4 × C 5 . Lemma D.9 is proved.  Comments on Theorem E.1 : We first remark that the above theorem based on the covering number can also be adapted to the packing number (without difficulties). We now comment on the two additive error terms in the upper bound. The term −log (M ∨ (1/m)) log stands for the gap between the Minkowski dimension and the quantity that we actually estimate, i.e. −log N . The second error term −d err n,d ( log ) represents the gap between the latter estimated quantity and the estimator −log N (c) Ω ( ) log . To control this gap, we need to estimate the covering number correctly, and thus to control the error sum b sup + s ω involved in Proposition 4.3. Actually, the theorem ensures that this error sum is smaller than err n,d . This comes from the fact that the difference between the sample ω 1 , . . . , ω n and the latent space Ω is not too large, thanks to the assumption H α,v 1 . See the proof below for details.
Finally, the upper bound holds with probability at least 1−2/n−4 α M/n. The first quantity 2/n corresponds to the event E c dist defined in Theorem 4.1, i.e. that the the distance estimator does not satisfy the distance error bound b sup . The second quantity 4 α M/n corresponds to the probability of the event where the sampled points do not cover well the latent space, leading to a large sampling error s ω and a large distance error bound b sup . This event, denoted by E bad , is rigorously defined in the following proof.
Proof of Theorem E.1. Assume the event E dist of Theorem 4.1 holds, that is the errors of distance-estimator are uniformly bounded by b sup . On this event, Proposition 4.3 gives N (c) As the assumption H m,M,v 2 is valid in the neighborhood ]0, v], we need to check that + s ω + b sup ∈]0, v] to use this assumption. For clarity, we do this verification at the end of the proof. Hence, using H m,M,v 2 , one has (35) In the right hand side of (35), the right term is upper bounded by Similarly in the left hand side of (35), the right term is lower bounded by Combining the above displays, one derive (36) It remains to upper bound the error sum s ω + b sup in (36). Given a cover of Ω, composed of N (c) Ω (η) balls B j of radius η, one define the following event E bad (η) := ∃j : B j contains exactly 0 or 1 sampled point among ω 1 , . . . , ω n .
Assume the complementary event E c bad (η) holds. This means that each ball of the cover of Ω contains at least two sampled points. Hence, one has s ω ≤ 2η, sup i∈{1,..,n} r W (ω i , ω m(i) ) ≤ 2η.
which directly implies the following upper bound b sup + s ω ≤ 6 log n n . It follows from the definition (34) of err n,d that Combining the above upper bound with (36), one deduce the inequalities of the theorem. The above displays hold conditionally to the event E c bad (η n ) ∩ E dist , which happens with probability at least 1 − (2 + 4αM ) /n (Lemma E.2).
Theorem E.1 is proved.
Proof of Lemma E.3. We want to prove that + s ω + b sup ∈]0, v] on the event E c bad (η n ) ∩ E dist . We have already seen that s ω + b sup ≤ 6err n,d on this event, so it is enough to prove that + 6err n,d ≤ v. By assumption in Finally, one has + 6err n,d ≤ v, since ≤ v/7 by assumption. Hence, The lemma is proved.
Proof of Lemma E.2. Let us upper bound the probability P (Ω,µ,W ) (E bad (η n )∪ E c dist ). The union bound gives where the last inequality comes from Theorem 4.1. If the cover defined by E bad (η n ) satisfies the condition (39), then Lemma E.4 ensures that Lemma E.4 Let B 1 , . . . , B N be N balls in (Ω, r W ) of measure (strictly) larger than 1/n, that is, for some real β. Then the probability that (at least) one ball contains exactly zero or one sampled point is smaller than Assume that η n ∈]0, v] to use the assumption H α,v 1 . Then, one obtain the following lower bound for the cover defined by E bad (η n ), µ(B j ) ≥ α η d n = 2 log(n)/n so that assumption (39) is satisfied. Applying Lemma E.4 for β = α η d n , one has Since the probability of the event {B j contains exactly 0 point} is equal to (1 − µ(B j )) n , and since the probability of {B j contains exactly 1 point} is nµ(B j )(1 − µ(B j )) n−1 , the above sum is upper bounded by

Combining with the inequality N
Combining the assumption µ(B j ) ≥ β > 1/n with the monotonicity of the functions x → (1−x) n and x → nx(1−x) n−1 on ]1/n, 1[, one has the following upper bound

E.2 Lower bound and minimal conditions
Proof of Theorem 4.5. From [Falconer, chap.2], we deduce directly the following lemma.
Based on (Ω 0 , µ 0 ) described in Lemma E.5, we construct two graphons that are difficult to distinguish for any estimator.
Proof of Theorem 4.6. There are two cases. For the class W min(1) n (D, α, m, M, v), the condition H α,v 1 is not imposed. Consider the two following graphons. is not assumed. As in the proof of Theorem 4.5, we can see that the two following graphons belong to W min(2) n (D, α, m, M, v).
Following the proof of Theorem 4.5, with the above two graphons, one obtain the error bound (40)  F Estimation with sparse observations F.1 Proof of Corollary 6.1 : estimation of the distances Corollary 6.1 is a reformulation of Theorem 4.1 in the sparse setting and their proofs are almost identical. In this appendix, denote by W n the function ρ n W . Accordingly, r Wn denotes the neighborhood distance (4) where W has been replaced with W n . Hence, r Wn = ρ n r W .
Corollary 6.1 is a direct consequence of the two following Lemmas.
Following the proof of Proposition D.1, we show Lemma F.1 below, by replacing Hoeffding inequality with Bernstein inequality, in order to benefit from the small variance of A ij (which is now of the order of ρ n ).
The proof of lemma F.2 is almost the same as for Proposition D.2. It is omitted.
F.2 Proof of of Corollary 6.2 : estimation of the dimension In the proof of Theorem E.1, one has seen The sampling error s ω is not affected by the sparsification of the data through ρ n , and thus takes the same value as in Theorem E.1. On the other hand, the distance error bound b sup changes, and is now defined as b 2 sup := 6 max 1≤i≤n r W (ω i , ω m(i) ) + 60 ρ n log(n)/n according to Corollary 6.1. Following the proof of Theorem E.1, one has b sup + s ω ≤ 6 2 log n α n so that b sup + s ω ≤ 8 err n,d,ρn .
Following the proof of Theorem E.1, one obtain the same error bound for the dimension estimation, after replacing 6 err n,d with 8 err n,d,ρn . Indeed, one has log N (c) for all ∈]0, v/9] and all n such that 2log n/n ≤ α (v/18) 2d ∧ ρ 2 n (v/18) 4 .
As in the proof of Theorem 4.4, one minimizes the error bound (42) by choosing a particular radius of the order of sup

G Testing the complexity via under-estimation of the packing number
The current appendix is organized as follows. We first analyse the performance of the new distance estimator (19) and then deduce a control on the type I and II errors of the test.

G.1 Performance of the new distance estimator
which is upper bounded by f (j, m(j)) + f (i, m(i)) where f has been introduced in (9). As in the proof of Theorem 4.1, one can show that the above display is upper bounded by r W (ω j , ω m(j) ) + r W (ω i , ω m(i) ) + 12 log(n)/n on the event E in . Combining this upper bound of r with the following lower bound from Theorem 4.1 r 2 (i, j) ≥ r 2 W (ω i , ω j ) − 3 r W (ω i , ω m(i) ) − 3 r W (ω j , ω m(j) ) − 36 log(n)/n, one derive r 2 W (ω i , ω j ) ≤ 4 r W (ω i , ω m(i) ) + 4 r W (ω j , ω m(j) ) + 48 log(n)/n.
This implies that the right hand side of (47) is non positive. Hence (45) is proved in the particular case m(i) = j and i = m(j). By symmetry, it remains only the case m(i) = m(j) to do. Following the above proof, we can show taht (45) holds for this case too. The inequality (45)

G.2 Control on the type I and II errors
In Theorem 5.2 on the new packing number estimator, the left hand side of (20) is similar to Section 4.3 on the covering number estimator, and thus straightforward. The right hand side of (20) and Corollary 5.3 are proved together below.
Proof for the type I error. Assume the null-hypothesis N (p) Ω ( ) ≤ K holds. We want to show that the same inequality is satisfied by the statistic N (p.new) Ω ( ). Proof by contradiction: assume the inequality N (p.new) Ω ( ) ≥ K + 1 holds. This means that there are K + 1 indices i 1 , . . . , i K+1 ∈ [n] such that the following inequalities hold ∀s, t ∈ {1, . . . , K + 1} : 2 < r 2 new (i s , i t ).
Combining the above inequalities with the under-estimation property (44), one has ∀s, t ∈ {1, . . . , K + 1} : 2 < r 2 W (ω U (is) , ω U (it) ) + t n The above displays hold on the event E in ∩ E c bad . Let us upper bound the probability of the complementary event. The union bound gives P(E c in ∪ E bad ) ≤ 2 n + (K + 1)2nβ exp[−β(n − 1)] thanks to Proposition D.1 and Lemma E.4. Theorem 5.4 is then proved.
Proof for the improvement of the type II error (Theorem A.1). We have seen that the type II error is upper bounded by the probability of the event E c in ∩ E bad . Here the only difference is that E bad refers to the new event where, for each of the M collections of K + 1 + K balls, at least K + 1 balls contain strictly less than two sampled points. For clarity, label these collections by {1, . . . , M }, and denote by C j the event where at least K + 1 balls of the j th collection contain strictly less than two sampled points. Then, we have where P denote the probability distribution P (Ω,µ,W ) of the W-random graph. The above display is equal to Given the first collection of K +1+K balls, denote by E j the event where the j th ball of the collection contains strictly less than two sampled points. By definition of the event C 1 , we have P[ C 1 ] = P[ ∃ i 1 , . . . , i K +1 ∈ {1, . . . , K + 1 + K } : E i 1 ∩ . . . ∩ E i K +1 ].
The union bound gives where the sum is taken over all possible K + 1 different indices. The above upper bound is equal to which is smaller than by negative association of the events E k (this fact is proved at the end . Thus, setting p n = P[C 1 ], we deduce from (51) that where p n is upper bounded by (53).
It remains to show the negative association that we use in the above proof. Given the first collection of K + 1 + K balls, let us show that the corresponding events E 1 , . . . , E K+1+K are negatively associated. For the n sampled points ω 1 , . . . , ω n , define n j the number of points in the j th ball of the collection. Theorem 13 of Dubhashi and Ranjan [1998] ensures that the variables n 1 , . . . , n K+1+K are negatively associated. Define the nonincreasing function h(n j ) = I E j where I E j is the indicator function of E j . The second point of Proposition 7 of Dubhashi and Ranjan [1998] shows that h(n 1 ), . . . , h(n K+1+K ) are negatively associated. This means that the events E 1 , . . . , E K+1+K are negatively associated.
Similarly, we show the negative association of the events C 1 , . . . , C M . Consider n t j the number of sampled points in the j th ball of the t th collection. These variables are negatively associated according to Theorem 13 of Dubhashi and Ranjan [1998]. Define the non-increasing functions h t (n t 1 , . . . , n t K+1+K ) = I C j for all t ≤ M . Then, Proposition 7 of Dubhashi and Ranjan [1998] shows that I C 1 , . . . , I C M are negatively associated.
Theorem A.1 is proved.