arXiv:1712.01745v1 [math.ST] 5 Dec 2017

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX
PROCESSES
ZACHARIE NAULET, EKANSH SHARMA, VICTOR VEITCH,
AND DANIEL M. ROY
Abstract. Sparse exchangeable graphs resolve some pathologies in traditional random graph models, notably, providing models that are both
projective and allow sparsity. In a recent paper, Caron and Rousseau
(2017) show that for a large class of sparse exchangeable models, the
sparsity behaviour is governed by a single parameter: the tail-index of
the function (the graphon) that parameterizes the model. We propose
an estimator for this parameter and quantify its risk. Our estimator
is a simple, explicit function of the degrees of the observed graph. In
many situations of practical interest, the risk decays polynomially in
the size of the observed graph. Accordingly, the estimator is practically
useful for estimation of sparse exchangeable models. We also derive the
analogous results for the bipartite sparse exchangeable case.

1. Introduction
Most statistical models for relational data are based on vertex-exchangeable
random graphs (also called graphon models), see Orbanz and Roy (2015) for
a review. These models are interpretable and easy to work with, but have
the considerable limitation that, almost surely, they generate dense graphs;
that is, the number of edges scales quadratically with the number of vertices.
Sparse exchangeable random graphs (or graphex processes) Caron and Fox
(2017); Veitch and Roy (2015); Borgs et al. (2016) have been proposed as a
generalization of the graphon models that preserve the key properties, but
allow for sparsity. We recall these models for unipartite graphs and bipartite
graphs in sections 2.1 and 3.1.
Efficient estimation remains challenging for these new models. A situation of particular interest is to define graphex process models that are close
analogues of dense models that have been already proven to be useful in
practice; this is the approach of Todeschini and Caron (2016); Herlau et al.
(2016), and a number of models of this kind are described in Borgs et al.
(2016). Roughly speaking, we would like to combine efficient estimation procedures already developed in the dense case with some new procedures for
estimating the additional parameters governing the sparse behaviour.
Recently, Caron and Rousseau (2017) have studied asymptotics for an
important class of sparse exchangeable models (encompassing most known
Date: December 6, 2017.
1

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

2

examples). They derive the remarkable result that, for this model class,
the sparsity (i.e. the scaling of number of edges with respect to number of
vertices in the large graph limit) and the degree distribution of the graph are
governed by a single parameter of the model, which we call the tail-index σ.
The main contribution of the present paper is to propose a simple estimator
σ̂ for σ and to quantify its asymptotic risk. Our estimator is a simple, explicit
function of the degree distribution of the graph. Moreover, we show that in
many situations, the risk decays polynomially in the size of the graph—by
contrast, the more direct estimator of Caron and Rousseau (2017) has risk
that decays only logarithmically. The fast rate of convergence allows our
estimator to be used as a plugin estimator for σ. This enables, for example,
empirical Bayes procedures for estimating sparse exchangeable models; see
the companion paper Veitch et al. (2017) for an example applying this idea
to a complicated practical model.
We recall Caron and Rousseau’s findings in section 2.2 for simple graphs,
and briefly discuss the counterparts results for bipartite graphs in section 3.2.
The estimator and the main result for simple graphs are given in section 2.3,
and the corresponding results for bipartite graphs are given in section 3.3.
Throughout the document, we use the notations Xt ∼ Yt for limt Xt /Yt =
1. If Xt and Yt are random variables, the limit is understood almost-surely.
We also write Xt  Yt if there is a constant c ∈ R such that limt Xt /Yt = c.
Inequalities up to generic constants are denoted by the symbols . and &.
Moreover, we recall that a function ` : R+ → R+ is called slowly varying if
limx→∞ `(cx)/`(x) = 1 for all c > 0. Also, it is assumed that all random
variables are defined on a common probability space (Ω, F, P). The symbol E
will denote the expectation under P, and E[· | ·] and P(· | ·) stand respectively
for conditional expectation and conditional distribution. For any set S with
finite cardinality, we write |S| the number of elements in S.
2. Unipartite undirected graphs
An undirected graph g is an ordered pair g = (v, e) where v is a set of
vertices and e is a set of unordered pairs of vertices called edges. We also
consider graphs with no isolated vertices, that is for all u ∈ v there exists
u0 ∈ v such that {u, u0 } ∈ e.
2.1. The model. The model for random undirected graphs we consider in
that paper is the sparse exchangeable framework introduced by Caron and
Fox (2017) and further studied in Veitch and Roy (2015, 2016); Todeschini
and Caron (2016); Borgs et al. (2016); Borgs et al. (2017); Janson (2017);
Caron and Rousseau (2017). Let (X , ρ) be a measured space. By the mean
of random graph G = (V, E), it is understood V ⊆ X and E is a symmetric
point process (Daley and Vere-Jones, 2003a,b) over V × V , seen as a random
edge set for G. Because we assume G has no isolated vertices, G is entirely
determined by its edge set.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

3

The model can be summarized as follows. First, denoting by λ the
Lebesgue measure on R+ and by PP(m) the distribution of a Poisson process
(Daley and Vere-Jones, 2003a,b) with mean intensity measure m, draw,
Π = {(X1 , U1 ), (X2 , U2 ), . . .} ∼ PP(ρ × λ).
The random variables {U1 , U2 , . . .} are potential labels for vertices. By properties of Poisson processes, each of these labels is almost-surely unique. The
random variables {X1 , X2 , . . .} are latent features that govern how vertices
will connect. Let B = (Bi,j )(i,j)∈N2 be an array of binary variables that
indicate the vertices Ui and Uj are connected if Bi,j = 1 and not connected
if Bi,j = 0. Because we are considering undirected graphs, we always let
Bi,j = Bj,i . Then, conditional on Π, for a jointly measurable, symmetric,
function W : X × X → [0, 1] we let independently for all i ∈ N and all j ≤ i,
Bi,j | Π ∼ Bernoulli(W (Xi , Xj )).
Using the terminology of Veitch and Roy (2015); Borgs et al. (2016) we refer
to the function W as the graphon. For technical reasons, we always assume
in that paper W and ρ are chosen so that
Z Z
(1)
W (x, x0 ) ρ(dx)ρ(dx0 ) < +∞.
X

X

The random edge set for G is then the point process E given in the random
measure form by
XX
E :=
Bi,j δUi ,Uj .
i∈N j∈N

Equivalently, we shall write {Ui , Uj } ∈ E if and only if Bi,j = 1 (and thus
Bj,i = 1). The vertex set V of G is obtained from E according to the rule
Ui ∈ V if and only if there exists j ∈ N such that {Ui , Uj } ∈ E.
The generative process for G is called a graphex process. A sample from
a graphex process has an almost-surely infinite (but countable) number of
vertices. We view the model as defining a growing sequence of graphs indexed
by the (continuous) sample size α ∈ R+ . The (almost-surely) finite graph
Gα = (Vα , Eα ) is obtained from G by taking
XX
Eα :=
Bi,j 1Ui ≤α 1Uj ≤α δUi ,Uj ,
i∈N j∈N

and Ui ∈ Vα if and only if Ui ≤ α and there exists j ∈ N such that {Ui , Uj } ∈
Eα . The parameter α > 0 is referred to as the size of the subgraph Gα since
it controls the law of |Vα | and |Eα |.
2.2. Graphex marginal and tail-index. It is well-known (Caron and Fox,
2017; Veitch and Roy, 2015; Caron and Rousseau, 2017) that when ρ(X ) <
+∞ a graph G drawn from a graphex process is almost-surely dense, in the
sense that |Eα |  |Vα |2 almost-surely as α → ∞.
The most interesting situation happens when ρ(X ) = ∞ eventually. In
that case, as shown by Caron and Rousseau (2017), the asymptotic behavior

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

4

of Gα as α → ∞ is determined by the tail behavior of the graphex marginal
µ : X → R+ defined by
Z
W (x, x0 ) ρ(dx0 ).
µ(x) :=
X

More specifically, they show that if there is σ ∈ [0, 1] and a slowly varying
function ` such that as z → 0,
F (z) := ρ{x ∈ X : µ(x) ≥ z} ∼ z −σ `(z −1 ),

(2)

then, under mild supplementary assumptions on W , there are four regimes
for the asymptotic behavior of Gα :
• Dense : σ = 0 and limt→∞ `(t) < ∞. In that case F has compact
support and |Eα |  |Vα |2 almost-surely.
• Almost-dense : σ = 0 and limt→∞ `(t) = ∞. In that case |Eα |/|Vα |2 →
0 almost-surely, but |Eα |/|Vα |2− → ∞ almost-surely for every  > 0.
2
• Sparse with power-law : σ ∈ (0, 1). In that case, |Eα |  [|Vα |/`(α)] 1+σ
almost-surely. Moreover, the degree distribution1 of G has a powerlaw (Caron and Rousseau, 2017).
• Very sparse : σ = 1. In that case, ` has to go to zero sufficiently fast
and |Eα |/|Vα | → ∞ almost-surely while |Eα |/|Vα |1+ → 0 almostsurely for all  > 0.
We call σ in equation (2) the tail-index of µ. Clearly σ is a crucial parameter of graphex processes since it governs the asymptotic behavior of |Eα |,
|Vα | as well as the degree distribution of Gα .
2.3. Estimation of the tail-index. A naive estimator for σ based on the
asymptotic growth of |Eα |/|Vα | has been proposed in Caron and Rousseau
(2017). Limitations of the naive estimator are discussed later in section 3.4.
We now describe our estimator. For some real numbers p ∈ [0, 1], we first
introduce the new random variables


P
( P
0
if 0 ≤ p < 1,
p U ∈Vα 1 − (1 − p) U 0 ∈Vα \{U } 1Eα {U,U }
Np,α := P
P
0
if p = 1.
U ∈Vα 1{ U 0 ∈Vα \{U } 1Eα {U, U } > 0}
In general N1,α 6= |Vα | because N1,α discards all vertices that have only selfedges, i.e. N1,α counts vertices that are connected to at least one vertex
distinct from themselves. Then, for a chosen value of p ∈ (0, 1), we propose
to use as an estimator for σ,
( log N −log N
p,α
1,α
− 1 if Np,α ≥ 1,
− log p
σ̂p,α :=
0
otherwise.
1Here the degree distribution is understood as p
α := (pα,k )k≥1 where pα,k :=
o
n

|Vα |−1

P

U ∈Vα

1

P

U 0 ∈Vα

1Eα {U, U 0 } = k . It is said that pα has a power law if there

is a constant c > 0 and a slowly-varying function at infinity L such that pα,k ∼ k−c L(k)
for k large enough.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

5

Notice that σ̂p,α is well-defined since N1,α ≥ Np,α almost-surely for all 0 ≤
p ≤ 1. Also note that σ̂p,α does not depend explicitly on the sample size α;
this is important because α is generally considered to be unknown.
In practice, we observe better performance by computing the estimator
for values of p ∈ (0, 1) close to 1, see section 4.3 for illustration.
In order to be able to compute the risk of σ̂p,α , we require further assumptions on the model. Our first assumption is analogous to the assumptions
encountered in Veitch and Roy (2015); Caron and Rousseau (2017). We first
introduce the 2-points correlation function ν : X × X → R+ ,
Z
0
W (x, y)W (y, x0 ) ρ(dy).
ν(x, x ) :=
X

Assumption 1. If 0 ≤ σ < 1, we assume that there is a constant η >
max(1/2, σ) and a constant C ≥ 0 such that ν(x, x0 ) ≤ Cµ(x)η µ(x0 )η for all
x, x0 ∈ X . If σ = 1, we assume ν(x, x0 ) ≤ Cµ(x)µ(x0 ), and we set η = 1.
Also, it is well-known (Feller, 1971, Chapter XIII; Caron and Rousseau,
2017) that under equation (2) the asymptotic equivalence
(
Z

ασ `(α)Γ(1 − σ) if 0 ≤ σ < 1,
−αz
R∞
1−e
F (dz) ∼
(3)
α α z −1 `(z) dz if σ = 1
R+
holds as α → ∞. This relation is already enough to show consistency of σ̂p,α .
However, further assumptions on F are required to quantify the risk of the
estimator. In the present paper, we shall assume the following assumption.
Assumption 2. We assume that equation (2) holds. We furthermore assume
that for all p ∈ (0, 1) there is a sequence (Γp,α )α>0 such that
R
−pαz ) F (dz)
R+ (1 − e
R
− 1 ≤ Γp,α .
pσ R+ (1 − e−αz ) F (dz)
The purpose of assumption 2 is the following. The integral in equation (3)
plays a determining role in computing the risk of σ̂p,α . However, equation (3)
says nothing about the rate at which the integral approaches ασ `(α). Moreover, we know that `(pα)/`(α) → 1 as α → ∞ by the assumptions on `, but
again, the rate of convergence is unknown. These two rates are encapsulated
in assumption 2, allowing us to quantify the risk of σ̂p,α . Bounds on Γp,α
for various examples are given in section 2.5. These examples show that in
many cases Γp,α has polynomial decay.
We are now in position to state the main theorem of this section, whose
proof is deferred to appendix A.
Theorem 1. Under assumptions 1 and 2, there is a constant C 00 > 0 depending only on p and W such that for all α ≥ 1 it holds
n
o
Γ2p,α
00
2
−(1+σ)
1−2η
E[(σ̂p,α − σ)2 ] ≤
+
C
log(α)
max
α
,
α
.
(− log p)2

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

6

The bound in the previous theorem is relatively sharp in the sense that it
is easily seen by inspection of the proof of the theorem that if we also have
ν(x, y) & µ(x)η µ(y)η , then
n
o
E[(σ̂p,α − σ)2 ] & max α−(1+σ) , α1−2η .
2.4. Interpretation of the estimator. It is interesting to discuss the genesis of our estimator σ̂p,α since it gives a nice interpretation. We assume here
for simplicity that σ ∈ (0, 1). In that case, inspection of the proofs in Caron
and Rousseau (2017) shows2 that almost-surely as α → ∞,
N1,α  α1+σ `(α).
Then, if we could observe Gα and Gpα for some p ∈ (0, 1), we could estimate
σ by noticing that almost-surely as α → ∞,
N1,pα
`(pα)
∼ p1+σ ,
∼ p1+σ
N1,α
`(α)
because `(pα)/`(α) → 1 as α → ∞ by the slowly-varying function assumption.
Unfortunately, we in general have only one sample Gα at our disposal.
However, it is known (Borgs et al., 2017; Veitch and Roy, 2016) that if Gα is
e pα =
a size α subgraph of a graphex process G, then the random subgraph G
epα ) obtained from Gα by selecting vertices at random with probability
(Vepα , E
p and keeping only non-isolated vertices, has the same distribution as Gpα .
e pα = Gpα ;
We should emphasize here that same distribution does not mean G
nevertheless, the intuition is useful. The random variable Np,α is precisely
equal to E[|Vepα | | Gα ].
Rephrased, σ controls the rate of growth of the number of vertices. Intuitively, the number of vertices in the graph at smaller sizes can be estimated
as Np,α ; this allows us to estimate the growth rate, and thus also to estimate
σ.
2.5. Examples. Here we present some examples to show our assumptions
are in general not too silly. We consider the examples which were originally
given in Caron and Rousseau (2017), because they cover a large spectrum of
behavior. From sections 2.5.1 to 2.5.4, ρ is taken to be the Lebesgue measure
on R+ with Borel σ-algebra.
2.5.1. Dense graphs. Consider the function W (x, y) = (1−x)(1−y)1x≤1 1y≤1 .
Then µ(x) = 0.5(1 − x)1x≤1 and the graph is almost-surely dense. Assumption 1 is trivially satisfied with η = 1. Also, it follows from appendix D.1
that assumption 2 is satisfied with Γp,α ∝ α−1 : the risk is polynomially
decreasing on this example.
2Indeed, they state the proof for |V |, but it is easily seen that the result for N
α
1,α

follows from their proof by assuming W (x, x) = 0 for all x ∈ X .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

7

2.5.2. Sparse, almost dense graphs without power law. Consider the function
W (x, y) = exp(−x − y). Then µ(x) = exp(−x) and assumption 1 is trivially
satisfied with η = 1 and σ = 0. Moreover, it follows from appendix D.2 that
assumption 2 is satisfied with Γp,α ∝ 1/ log(α): the risk is logarithmically
decreasing on this example.
2.5.3. Sparse graphs with power law, separable. For 0 < σ < 1, consider the
function W (x, y) = (1 + x)−1/σ (1 + y)−1/σ . Then obviously µ(x) = σ(1 +
x)−1/σ /(1 − σ) and assumption 1 holds trivially with η = 1. Moreover, from
appendix D.3, assumption 2 holds with Γp,α ∝ α−σ : the risk is polynomially
decreasing on this example.
2.5.4. Sparse graphs with power law, non separable. For 0 < σ < 1, consider
the function W (x, y) = (1+x+y)−1/σ−1 . It is shown in Caron and Rousseau
(2017) that assumption 1 holds with η = (1 + σ)/2. We have µ(x) = σ(1 +
x)−1/σ , which is up to a constant the same marginal as the previous example,
so that assumption 2 is verified with Γp,α ∝ α−σ and the risk is polynomially
decreasing on this example.
2.5.5. Generalized Gamma Process. For 0 < σ ≤ 1, let consider ρ(dx) =
x−1−σ exp(−x)/Γ(1 − σ) and W (x, y) = 1 − exp(−xy). This corresponds to
the model considered in Caron and Fox (2017). Then,
µ(x) =

(1 + x)σ − 1
,
σ

and, as z → 0,
σ

Z

z F (z) =

1{x ≥ (1 + σz)1/σ − 1}

R+

1
x−1−σ e−x dx
→
.
Γ(1 − σ)
σΓ(1 − σ)

Not surprisingly, that means the graph is almost-surely sparse with a powerlaw degree distribution. Moreover,
Z
z −1−σ e−z dz
ν(x, y) =
(1 − e−xz )(1 − e−zy )
Γ(1 − σ)
R+
=

−1 + (1 + x)σ + (1 + y)σ − (1 + x + y)σ
.
σ

Hence assumption 1 is satisfied with η = 1, because,
ν(x, y)
−1 + (1 + x)σ + (1 + y)σ − (1 + x + y)σ
=σ
≤ 1 − σ.
µ(x)µ(y)
((1 + x)σ − 1)((1 + y)σ − 1)
Furthermore, the computations in appendix D.4 show that assumption 2 is
satisfied with Γp,α ∝ α−σ .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

8

3. Bipartite undirected graphs
The model for undirected graphs described in the previous section can also
be extended to bipartite graphs (Caron, 2012; Caron and Fox, 2017). Here we
understand an undirected bipartite graph g = (v, w, e) as an ordered triple
where u, v are sets of vertices, and e ⊆ v × w is a set of edges. Informally,
v and w are referred to as the parts of the graph, and only edges between
vertices belonging to different parts are allowed.
3.1. The model. The model for bipartite graphs we consider is a natural
extension of section 2.1 already considered in (Caron, 2012; Caron and Fox,
2017). Let (X , ρ) and (Y, ψ) be measured spaces. By the mean of a random
bipartite graph G = (V, W, E), it is understood V ⊆ X , W ⊆ Y and E is a
point process over V × W , seen as a random edge set for G.
The model can be summarized as follows. First, draw independently,
Πv = {(X1 , U1 ), (X2 , U2 ), . . .} ∼ PP(ρ × λ),
Πw = {(Y1 , T1 ), (Y2 , T2 ), . . .} ∼ PP(ψ × λ).
The random variables {U1 , U2 , . . .} and {T1 , T2 , . . .} are potential labels for
vertices of the different parts. As for the unipartite case, let B = (Bi,j )(i,j)∈N2
be an array of binary variables that indicate the vertices Ui and Tj are
connected if Bi,j = 1 and not connected if Bi,j = 0. Then, conditional
on (Πv , Πw ), for a jointly measurable function W : X × Y → [0, 1], we let
independently for all (i, j) ∈ N2 ,
Bi,j | Πv , Πw ∼ Bernoulli(W (Xi , Yj )).
Note that W is no longer assumed to be symmetric, we in fact don’t necessarily have X = Y. However, we still assume that
Z Z
(4)
W (x, y) ρ(dx)ψ(dy) < +∞.
X

Y

P
P
The edge set of G is then the point process E :=
i∈N
j∈N Bi,j δUi ,Tj .
Equivalently, we write (Ui , Tj ) ∈ E if and only if Bi,j = 1. The vertex sets
(V, W ) are obtained from E according to the rule Ui ∈ V if and only if there
is j ∈ N such that (Ui , Tj ) ∈ E; similarly Tj ∈ W if and only if there is i ∈ N
such that (Ui , Tj ) ∈ E.
The previous process generates a bipartite graph with an infinite number of vertices in both parts. For real numbers s, α > 0, a subgraph
Gs,α = (Vs,α , Ws,α , Es,α ) with an almost-sure finite number of vertices (see
next section) is obtained from G by taking
XX
Es,α :=
Bi,j 1Ui ≤s 1Tj ≤α δUi ,Tj ,
i∈N j∈N

and Ui ∈ Vs,α if and only if Ui ≤ s and there exists j ∈ N such that Tj ≤ α
and (Ui , Tj ) ∈ Es,α ; similarly Tj ∈ Ws,α if and only if Tj ≤ α and there
exists i ∈ N such that Ui ≤ s and (Ui , Tj ) ∈ Es,α .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

9

3.2. Asymptotic behavior. We state here the counterparts of the results
of Caron and Rousseau (2017) for the bipartite situation. Proofs are given
in appendix B.
The first result is about the asymptotic behavior of |Es,α | in the large
graph limit.
Proposition 1. Suppose that W satisfies equation (1). Then, P-almostsurely as min(s, α) → ∞,
Z Z
|Es,α | ∼ sα
W (x, y) ψ(dy)ρ(dx).
X

Y

We now state the results for the behavior of |Vs,α | and |Ws,α | in the large
graph limit. As for the unipartite case, these behaviors are determined by
the tails of the graphex marginals µv : X → R+ and µw : Y → R+ defined
by
Z
Z
µv (x) :=
W (x, y) ψ(dy), and,
µw (y) :=
W (x, y) ρ(dx).
Y

X

We will state the results only for the v-part of the graph, because the corresponding statements for the w-part are obtained by a trivial symmetry
argument. We make use of the assumption that there is a constant σ ∈ [0, 1]
and a slowly-varying function `v , such that as z → 0,
(5)

Fv (z) := ρ{x ∈ X : µv (x) ≥ z} ∼ z −σ `v (z −1 ).

Then we have the following proposition. There, when σ = 1 it is assumed
that `v has enough decay at infinity so that the integral involved in the
proposition converges. Moreover, we make here use of the 2-points correlation functions νv : X × X → R+ defined by
Z
0
νv (x, x ) :=
W (x, y)W (x0 , y) ψ(y).
Y

Proposition 2. Suppose that W satisfies equation (4) and νv satisfies equation (5) and the same conditions as in assumption 1. Then P-almost-surely
as α → ∞,
(
sασ `v (α)Γ(1 − σ) if 0 ≤ σ < 1,
R∞
|Vs,α | ∼
sα α z −1 `v (z) dz if σ = 1.
Finally, we give the behavior of the degree distributions in the large graph
limit. We consider the degree distribution for the v-part of the graph; that
is for each k ∈ N the number of vertices belonging to the v-part that are
connected to k vertices belonging to the w-part. More specifically, for every
k ∈ N, we let
nP
o
X
(v)
Dk :=
1Ui ≤s 1
1
B
=
k
.
j∈N Tj ≤α i,j
i∈N

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

10

Proposition 3. Suppose that W satisfies equation (4) and νv satisfies equation (5) and the same conditions as in assumption 1. Then P-almost-surely
as α → ∞,

if σ = 0,

s × o(`v (α))
(v)
σ
Dk ∼ sα nσΓ(j − σ)`v (α)/k!
o if 0 < σ < 1,
R ∞ −1

`v (α)
sα 1
if σ = 1.
k=1 α z `v (z) dz + k(k−1) 1k≥2
We would like to emphasize that the results of propositions 2 and 3 only
require α → ∞ to hold, while proposition 1 is valid only if min(s, α) → ∞.
3.3. Tail-indexes estimation. As for the bipartite case, the parameters σ
plays a crucial role in the asymptotic behavior of the graphex process. Here
we show how the estimator proposed in section 2.3 translates to the bipartite
case. We assume for simplicity p = 1/2.

o
n
P
P
− T ∈Ws,α 1Es,α (U,T )
log |Vs,α | − log 2−1 U ∈Vs,α 1 − 2
σ̂s,α :=
log 2
Then we have the main theorem of this section, whose proof is to be found
in appendix C.
Theorem 2. Assume νv satisfies assumption 1 and that assumption 2 holds
with F replaced by Fv . Then there is a constant C 00 > 0 depending only on
W such that for all α, s ≥ 1 it holds


Γ21/2,α
1
00
2
1−2η
+
C
log(α)
max
,
α
.
E[(σ̂α,s − σ)2 ] ≤
(log 2)2
sασ
3.4. Discussion. Caron and Rousseau (2017) propose a naive estimator
for σ in the unipartite case. Their estimator can be tuned to handle the
bipartite
R Rcase as follows. Here we assume σ ∈ (0, 1) for simplicity. Let
W = X Y W (x, y) ψ(dy)ρ(dx). Then Caron and Rousseau’s estimator for
the parameters is based on the results of propositions 1 and 2, implying that
P-almost-surely as min(s, α) → ∞,
log |Vs,α |
log α
log(s`v (α)Γ(1 − σ))
∼σ
+
.
log |Es,α |
log(sαW )
log(sαW )
If the behaviour of log s/ log α is known as min(s, α) → ∞, the previous
equation can be used to construct a consistent estimator of σ. The main
limitation of this approach is then clear: log s/ log α is usually not known,
and it is further unclear how to estimate this quantity from a single observation. That is, this naive estimator can not actually be computed in
practice.
A second limitation of these estimators comes from the fact that they only
use information about the graph size. Doing so, one cannot hope to achieve
a rapidly decreasing risk of estimating σ as min(s, α) → ∞, even when
log s/ log α is known: the risk is necessarily bounded by a multiple constant

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

11

of 1/ log min(α, s). Note that this limitation is also true in the unipartite
case. Our estimator overcomes this issue by incorporating information from
the degree distribution of the graph.
Finally, observe that our estimator in the bipartite case only requires
α → ∞, but not necessarily min(s, α) → ∞.
4. Simulation results
We test our estimator for simple graphs in practice by simulating from the
examples of section 2.5. For each example, we generate Monte Carlo (MC)
samples according to the following procedure. For each sample:
(1) Generate the first n jumps {X1 , . . . , Xn } of a fresh new α-rate Poisson
process on R+ . This is done by drawing n independents Gamma(1, α)
random variables and letting X1 = Γ1 , X2 = Γ1 +Γ2 , ... For the Generalized Gamma Process (GGP) example, we transform {X1 , . . . , Xn }
according to Ferguson and Klass (1972)’s inverse Lévy tail trick. In
all cases, this generates the jumps in increasing order. We take advantage of the fact that µ is monotonically decreasing in all the examples to stop whenever µ(Xn ) ≤ 10−6 .
(2) We generate the graph according to the procedure of section 2.1.
It is unnecessary to store the whole graph in memory, because our
statistics of interest involve only the number of edges, the number of
vertices, and the degree distribution of the graph.
Notice that this is a rather inefficient way of getting MC samples, especially when µ is slowly decaying (i.e. in the sparse case). Labels {U1 , U2 , . . .}
can be obtained by sampling iid uniformly from [0, α], although we don’t need
them in general.
For different sets of parameters, we simulated MC samples to get estimates
of E|Eα |, E|Vα | and E[(σ̂p,α − σ)2 ]1/2 . We also compare our estimator with
the naive estimator from Caron and Rousseau (2017). We recall that their
estimator is defined by
σ̂CR :=

2 log |Vα |
− 1.
log |Eα |

In all simulations we picked σ = 0.3 for the sparse separable and sparse
non-separable example, while the GGP example corresponds to a choice of
σ = 0.5. Results are summarized in the next sections.
4.1. Number of edges and number of vertices. We estimated E|Eα |
and E|Vα | on the examples for various values of α. The raw numbers are
given in tables 1 and 2. Of course, these results are only of little interest
since these expectations are available in closed form and computable either
exactly, or at least with high precision using numerical integration. However,
we believe having these numbers in mind is helpful to interpret the result of
the next section in term of |Eα | and |Vα | instead of α.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

12

Table 1. Average number of edges over 10 000 MC samples
for the examples described in section 2.5 and various values
of α.
α

25

50

100

200

400

800

Dense
155.35 626.15 2509.99 9999.26 40016.50 160226
624.97 2495.29 9976.05 39988.50 159967
639409
Almost-dense
Sparse sep.,
114.79 457.36 1833.48 7328.27 29395.90 117414
Sparse non-sep. 80.12
320.62 1283.55 5132.66 20523.20 82068.90
GGP
572.735 2286.04 9140.48 36424.4
145682
582214
Table 2. Average number of vertices over 10 000 MC samples for the examples described in section 2.5 and various
values of α.
α

25

50

100

200

400

800

Dense
22.94 47.98 98.08 198.11 397.93 798.19
Almost-dense
94.93 224.54 517.63 1174.88 2626.10 5804.23
Sparse sep.
41.06 112.38 299.82 782.73 2017.87 5137.58
Sparse non-sep. 34.20 95.54 257.71 677.67 1749.09 4445.46
GGP
200.92 598.13 1748.8 5031.92 14333 40408.5
106

105

104

104

103

103

Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

102
102

103

α

Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

102

102

103

α

Figure 1. Average number of edges (left) and number of
vertices (right) over 10 000 MC samples for the examples
described in section 2.5.
Figure 1 displays E|Eα | and E|Vα | as a function of α. We find here clearly
that E|Eα |  α2 and E|Vα |  α1+σ `(α).
4.2. Risk estimation for varying α. We also estimated E[(σ̂0.5,α − σ)2 ]1/2
and E[(σ̂CR − σ)2 ]1/2 on the examples for various values of α. The raw
numbers are given in tables 3 and 4.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

13

Table 3. Estimation of E[(σ̂0.5,α − σ)2 ]1/2 using 10 000 MC
samples for the examples described in section 2.5 and various
values of α.
α
Dense
Almost-dense
Sparse sep.
Sparse non-sep.
GGP

25

50

100

200

400

800

0.1620
0.2971
0.2440
0.2947
0.1219

0.0698
0.2440
0.1658
0.1945
0.0801

0.0327
0.2081
0.1186
0.1356
0.0502

0.0150
0.1814
0.0875
0.0966
0.0283

0.0079
0.1608
0.0654
0.0686
0.0110

0.0039
0.1443
0.0488
0.0462
0.0050

Table 4. Estimation of E[(σ̂CR − σ)2 ]1/2 using 10 000 MC
samples for the examples described in section 2.5 and various
values of α.
α
Dense
Almost-dense
Sparse sep.
Sparse non-sep.
GGP

25

50

100

200

400

800

0.2719
0.4240
0.2963
0.3483
0.1805

0.2125
0.3882
0.2535
0.2947
0.1577

0.1757
0.3590
0.2230
0.2575
0.1392

0.1500
0.3349
0.1994
0.2285
0.1239

0.1305
0.3144
0.1802
0.2051
0.1103

0.1154
0.2967
0.1643
0.1851
0.0982

We pictured in fig. 2 the risk of σ̂0.5,α and σ̂CR as functions of α for all the
simulated examples. As expected, the risk of σ̂0.5,α has polynomial decay
every-time but the almost dense example, while the risk of σ̂CR remains
logarithmically decreasing on all examples. We note, however, that even
in the situation when the risk has logarithm decay, σ̂0.5,α seems to perform
slightly better than σ̂CR .
Figure 3 shows the risks for both estimators as functions of α, normalized so that the risk equal 1 when α = 25. It is seen from the figure that
the simulation results are consistent with the results of section 2.5 for the
dense, almost dense, sparse separable and GGP examples. For the sparse
non-separable example, however, because η = (1 + σ)/2 < 1, we expected
to observe a risk decaying slower than the separable example, which is not
the case. There’s at least two explanations for that. First of all, maybe the
difference becomes visible only for larger values of α. Second, it is plausible that bounding the variance of σ̂p,α using assumption 1 on the 2-points
correlation function is too pessimistic, and the true variance is indeed much
smaller than the upper bound derived in theorem 1.
Figure 4 is similar to fig. 3, but this time the normalized risk is plotted as
a function of |Vα |.
4.3. Risk estimation for various values of p. Finally, we ran the simulations for a fixed value of α = 50, but estimated E[(σ̂p,50 − σ)2 ]1/2 for

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

Dense

14

Almost dense
10−0.4

Risk

10−1

10−0.6
10−2

σ̂0.5,α
σ̂CR

10−0.8

102

σ̂0.5,α
σ̂CR
102

103

103

α

α

Sparse sep., σ = 0.3

Sparse non-sep., σ = 0.3

10−0.5

Risk

10−0.5

10−1

10−1

σ̂0.5,α
σ̂CR

σ̂0.5,α
σ̂CR
102

103

102

103

α

α
GGP, σ = 0.5

Risk

10−1

10−2

σ̂0.5,α
σ̂CR
102

103

α
Figure 2. Comparative plot of E[(σ̂0.5,α − σ)2 ]1/2 against
E[(σ̂CR − σ)2 ]1/2 using 10 000 MC samples for the examples
described in section 2.5.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

Normalized risk

100

15

100

10−0.2
10−1
Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

102

103

10−0.4

102

α

103

α

Figure 3. Comparative plot of E[(σ̂0.5,α − σ)2 ]1/2 (left)
against E[(σ̂CR − σ)2 ]1/2 (right) as functions of α using 10
000 MC samples for the examples described in section 2.5.
Here the risks are normalized to equal 1 when α = 25.

Normalized risk

100

100

10−0.2
10−1
Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

102

Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

103

|Vα |

104

10−0.4

102

103

104

|Vα |

Figure 4. Comparative plot of E[(σ̂0.5,α − σ)2 ]1/2 (left)
against E[(σ̂CR − σ)2 ]1/2 (right) as functions of |Vα | using
10 000 MC samples for the examples described in section 2.5.
Here the risks are normalized to equal 1 when α = 25.

various values of p ranging from 0.1 to 0.99. Raw numbers are given in table 5 and illustration on fig. 5. It is not surprising to find here that the risk
is slightly better for values of p close to one, since this tends to reduce the
ratio Γp,α / log(1/p) on these examples. There is no guarantee, however, that
in general Γp,α / log(1/p) is minimized for p → 1. Nevertheless, we would
recommend to compute the estimator for large value of p (say p = 0.9) to
not deteriorate too much Γp,α .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

16

Table 5. Estimation of E[(σ̂p,50 − σ)2 ]1/2 using 10 000 MC
samples for the examples described in section 2.5 and various
values of p.
p
Dense
Almost-dense
Sparse sep.
Sparse non-sep.
GGP

0.1

0.3

0.5

0.7

0.9

0.99

0.1938
0.3148
0.2552
0.3026
0.1296

0.0941
0.2617
0.1880
0.2229
0.0927

0.0698
0.2440
0.1658
0.1945
0.0801

0.0594
0.2345
0.1531
0.1800
0.0727

0.0547
0.2276
0.1478
0.1695
0.0674

0.0539
0.2257
0.1438
0.1671
0.0658
Dense
Almost dense
Sparse sep.
Sparse non-sep.
GGP

Risk

0.3

0.2

0.1

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1

p
Figure 5. Estimation of E[(σ̂p,50 − σ)2 ]1/2 using 10 000 MC
samples for the examples described in section 2.5 and various
values of p.
Appendix A. Proof of theorem 1
The starting point of the proof is to decompose the risk onto a deterministic bias term and some stochastic variance terms. Then, when Np,α = 0 we
have
(σ̂p,α − σ)2 = σ 2 ≤ 1.

(6)

In the situation where Np,α ≥ 1, we have
EN1,α
+ log p
ENp,α




N1,α − EN1,α
Np,α − ENp,α
+ log 1 +
− log 1 +
.
EN1,α
ENp,α

− log(p)σ̂p,α = log

To ease notations, we define,
bσ,α :=

log(EN1,α /ENp,α )
− 1 − σ,
− log p

Zp :=

Np,α − ENp,α
.
ENp,α

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

17

Note that Z1 , Zp > −1 because N1,α ≥ Np,α ≥ 1. Then when Np,α ≥ 1,


log(1 + Z1 ) log(1 + Zp ) 2
2
(σ̂p,α − σ) = bσ,α +
−
− log p
− log p
log(1 + Zp )
log(1 + Z1 )
= b2σ,α + 2bσ,α
− 2bσ,α
− log p
− log p
2
2
log(1 + Z1 ) log(1 + Zp )
log (1 + Z1 ) log (1 + Zp )
+
−2
.
+
2
2
(− log p)
(− log p)
(− log p)2
We now introduce functions ϕ1 , ϕ2 : (−1, ∞) → R+ such that,
ϕ1 (z) :=

log(1 + z)
,
z

ϕ2 (z) := −

log(1 + z) − z
.
z2

The functions ϕ1 and ϕ2 are non-negative and monotonically decreasing on
(−1, ∞). We can therefore write when Np,α ≥ 1,
Z1 Zp ϕ1 (Z1 )ϕ1 (Zp )
Z12 ϕ1 (Z1 )2 Zp2 ϕ1 (Zp )2
(7) (σ̂p,α − σ) =
+
+
−2
(− log p)2
(− log p)2
(− log p)2
2bσ,α Z1 2bσ,α Z12 ϕ2 (Z1 ) 2bσ,α Zp 2bσ,α Zp2 ϕ2 (Zp )
+
−
−
+
.
− log p
− log p
− log p
− log p
2

b2σ,α

But, by Young’s inequality we have 2|Z1 Zp ϕ1 (Z1 )ϕ1 (Zp )| ≤ Z12 ϕ1 (Z1 )2 +
Zp2 ϕ2 (Zp )2 . Combining the Young inequality estimate with equations (6)
and (11) gives
E[(σ̂p,α − σ)2 ] = E[(σ̂p,α − σ)2 1Np,α =0 ] + E[(σ̂p,α − σ)2 1Np,α ≥1 ]
2E[Z12 ϕ1 (Z1 )2 1Np,α ≥1 ] 2bσ,α E[Z1 1Np,α ≥1 ]
+
(− log p)2
− log p
2
2
2E[Zp ϕ1 (Zp ) 1Np,α ≥1 ] 2bσ,α E[Zp 1Np,α ≥1 ]
+
−
(− log p)2
− log p
2
2bσ,α E[Zp ϕ2 (Zp )1Np,α ≥1 ] 2bσ,α E[Z12 ϕ2 (Z1 )1Np,α ≥1 ]
+
−
.
− log p
− log p

≤ P(Np,α = 0) + b2σ,α +

Moreover, because E[Z1 ] = E[Zp ] = 0 we get by Hölder’s inequality the
following estimates.
q
E[Z1 1Np,α ≥1 ] = E[Z1 (1 − 1Np,α =0 )] ≤ E[|Z1 |1Np,α =0 ] ≤ E[Z12 ]P(Np,α = 0)
E[Zp 1Np,α ≥1 ] = E[Zp (1 − 1Np,α = 0)] = P(Np,α = 0).
Also, because E[Np,α ] > 0 (see proposition 4 below), by Chebychev inequality, for any t < 1,
P(Np,α = 0) ≤ P(Np,α < ENp,α (1 − t)) ≤ P(Zp < −t) ≤

E[Zp2 ]
.
t2

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

18

Since this is true for all t < 1, we certainly have P(Np,α = 0) ≤ E[Zp2 ].
Furthermore, N1,α ≥ Np,α ≥ 1 implies that Z1 ≥ −1 + (EN1,α )−1 , then
log EN1,α
.
1 − (EN1,α )−1

ϕ1 (Z1 )1Np,α ≥1 ≤
Also,
ϕ2 (Z1 ) = ϕ1 (Z1 ) −

(1 + Z1 ) log(1 + Z1 ) − Z1
≤ ϕ1 (Z1 ).
Z12

Obviously, the same estimates hold for Zp . Combining all the previous estimates yield the bound (where (x)+ = x if x ≥ 0 and (x)+ = 0 if x < 0),


2(−bσ,α )+
2(bσ,α )+ q
2
2
E[(σ̂p,α − σ) ] ≤ bσ,α + 1 +
E[Zp2 ] +
E[Z12 ]E[Zp2 ]
− log p
− log p

2


log EN1,α
log EN1,α
2(−bσ,α )+ E[Z12 ]
2E[Z12 ]
+
+
−1
2
−1
1 − (EN1,α )
(− log p)
1 − (EN1,α )
− log p
2



2
2E[Zp ]
2(bσ,α )+ E[Zp2 ]
log ENp,α
log ENp,α
+
.
+
1 − (ENp,α )−1 (− log p)2
1 − (ENp,α )−1
− log p
Then the conclusion of theorem 1 follows from the estimates in appendices A.1 and A.2.
A.1. Study of the bias term bσ,α . The estimate for the bias term follows
from the expectation of Np,α for p ∈ [0, 1] given in the next proposition.
Remark that from the definition of Np,α , we have


P
( P
B 1
p i 1Ui ≤α 1 − (1 − p) j6=i i,j Uj ≤α
if 0 ≤ p < 1,
Np,α = P
P
if p = 1.
i 1Ui ≤α 1{ j6=i Bi,j 1Uj ≤α > 0}
Proposition 4. For any p ∈ [0, 1] and α > 0 it holds,
Z 

E[Np,α ] = pα
1 − e−pαµ(x) ρ(dx).
X

Proof. We assume here that p 6= 1. The case p = 1 follows from the steps,
or by taking cautiously the limit p → 1 in the proof. Then we have,
"
#


P
X
B
1
E[Np,α ] = pE
1Ui ≤α 1 − (1 − p) j6=i i,j Uj ≤α
i

= pE

"
X



h

P

1Ui ≤α 1 − E (1 − p)

j6=i

Bi,j 1Uj ≤α

|Π

i

#

i

= pE

"
X
i



1Ui ≤α 1 −

Q

h
j6=i E

Bi,j 1Uj ≤α

(1 − p)

#
i
|Π
,

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

19

where the last line follows from independence and dominated convergence
theorem to take care of the infinite product. It is easily seen from the definition of B that for all i 6= j,
Bi,j 1Uj ≤α

E[(1 − p)

| Π] = 1 − pW (Xi , Xj )1Uj ≤α .

It follows, invoking the Slyvniak-Mecke formula (Daley and Vere-Jones, 2003b,
Chapter 13),
"
#

X

Q
E[Np,α ] = pE
1Ui ≤α 1 − j6=i 1 − pW (Xi , Xj )1Uj ≤α
= pα

Z i
X

1−E

hQ

j

1 − pW (x, Xj )1Uj ≤α

i

ρ(dx).

Then the conclusion of the proposition follows by Campbell’s formula (Kingman, 1993, Section 3.2) because,
hQ
h
nP
oi
i
E
1
−
pW
(x,
X
)1
=
E
exp
1
log(1
−
pW
(x,
x
))
j Uj ≤α
j
j
j Uj ≤α

R
= exp −pα X W (x, x0 ) ρ(dx0 ) .

It is clear from the result of the previous proposition that we have,
#
" R
−αz ) F (dz)
E[N1,α ]
R+ (1 − e
R
= log
log
E[Np,α ]
p R+ (1 − e−pαz ) F (dz)
" R
#
−pαz ) F (dz)
R+ (1 − e
= −(1 + σ) log p − log σ R
.
p R+ (1 − e−αz ) F (dz)
It then follows from assumption 2 that,
|bσ,α | ≤

Γp,α
.
− log p

A.2. Variance estimates for Np,α . We now compute the estimate for
E[Z12 ] and E[Zp2 ] in the proof of the main theorem. We assume here that
p 6= 1. The case p = 1 follows by taking cautiously the limit p → 1 in the
proof. To shorten coming equations, we write q := 1 − p. We then have,
2
Np,α
= p2

X


2
P
B 1
1Ui ≤α 1 − q j6=i i,j Uj ≤α

i
2

+p

XX
i

k6=i




P
P
B 1
B 1
1Ui ≤α 1Uk ≤α 1 − q j6=i i,j Uj ≤α 1 − q j6=k k,j Uj ≤α .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

20

We call p2 S1 the first term of the rhs of the previous equation, and p2 S2 the
2 = p2 S + p2 S . That is,
second term, so that Np,α
1
2
S1 :=

X


2
P
B 1
1Ui ≤α 1 − q j6=i i,j Uj ≤α

i

S2 :=

XX
i




P
P
B 1
B 1
1Ui ≤α 1Uk ≤α 1 − q j6=i i,j Uj ≤α 1 − q j6=k k,j Uj ≤α ,

k6=i

A.2.1. Computation of E[S1 ]. Expanding the square,


P
P
X
B 1
2
B 1
S1 =
1Ui ≤α 1 − 2q j6=i i,j Uj ≤α + q j6=i i,j Uj ≤α
i

By independence, and using the dominated convergence theorem to take care
of the infinite product,
E[S1 | Π] =

X


h
i
Q
B 1
1Ui ≤α 1 − 2 j6=i E q i,j Uj ≤α | Π

i

+

Q

h
i
2Bi,j 1Uj ≤α
E
q
|
Π
.
j6=i

From the definition of B we get that,
(8)
(9)

E[q
E[q

Bi,j 1Uj ≤α

2Bi,j 1Uj ≤α

| Π] = 1 − pW (Xi , Xj )1Uj ≤α ,

| Π] = 1 − p(1 + q)W (Xi , Xj )1Uj ≤α .

Therefore,
hX
n
Q
E[S1 ] = E
1Ui ≤α 1 − 2 j6=i (1 − pW (Xi , Xj )1Uj ≤α )
i

+

Q

oi
(1
−
p(1
+
q)W
(X
,
X
)1
)
.
i
j Uj ≤α
j6=i

Invoking the Slyvniak-Mecke theorem (Daley and Vere-Jones, 2003b, Chapter 13),
Z n
Q
E[S1 ] = α
1 − 2E[ j (1 − pW (x, Xj )1Uj ≤α )]
X

+ E[

Q

j (1

o
− p(1 + q)W (x, Xj )1Uj ≤α )] ρ(dx).

Therefore, by Campbell’s formula (Kingman, 1993, Section 3.2) (see also the
proof of proposition 4),
Z n
o
E[S1 ] = α
1 − 2e−pαµ(x) + e−p(1+q)αµ(x) ρ(dx)
X

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

21

That is,
E[S1 ] = α

Z n
o2
1 − e−pαµ(x) ρ(dx)
X
Z
n
o
−p(1+q)αµ(x)
−p2 αµ(x)
e
1−e
ρ(dx).
+α
X

A.2.2. Computation of E[S2 ]. We start with the expansion of the product in
the expression of S2 ,

P
P
XX
B 1
B 1
S2 =
1Ui ≤α 1Uk ≤α 1 − q j6=i i,j Uj ≤α − q j6=k k,j Uj ≤α
i

k6=i

+q
=

j6=i


P
Bi,j 1Uj ≤α + j6=k Bk,j 1Uj ≤α


P
P
B 1
B 1
1Ui ≤α 1Uk ≤α 1 − q j6=i i,j Uj ≤α − q j6=k k,j Uj ≤α

XX
i

P

k6=i

+q


P
P
2Bi,k + j6=i,j6=k Bi,j 1Uj ≤α + j6=k,j6=i Bk,j 1Uj ≤α

.

The following is justified by independence and dominated convergence theorem,

XX
Q
B 1
E[S2 | Π] =
1Uk ≤α 1Uj ≤α 1 − j6=i E[q i,j Uj ≤α | Π]
i

−

Q

j6=k E[q

k6=i

Bk,j 1Uj ≤α

| Π] + E[q 2Bi,k | Π]

Q

j6=i,k E[q

(Bi,j +Bk,j )1Uj ≤α


| Π] ,

That is, because of equations (8) and (9),

XX
Q
E[S2 | Π] =
1Ui ≤α 1Uk ≤α 1 − j6=i (1 − pW (Xi , Xj )1Uj ≤α )
i

−

Q

k6=i

− pW (Xk , Xj )1Uj ≤α ) + (1 − p(1 + q)W (Xi , Xk ))

Q
× j6=i,k (1 − pW (Xi , Xj )1Uj ≤α )(1 − pW (Xk , Xj )1Uj ≤α ) .

j6=k (1

We rewrite the previous in a slightly different form in order to be able to use
the Slyvniak-Mecke theorem (Daley and Vere-Jones, 2003b, Chapter 13),

XX
Q
E[S2 | Π] =
1Ui ≤α 1Uk ≤α 1 − j6=i (1 − pW (Xi , Xj )1Uj ≤α )
i

k6=i

1 − pW (Xk , Xi ) Q
−
(1 − pW (Xk , Xj )1Uj ≤α )
1 − pW (Xk , Xk ) j6=i
+ (1 − p(1 + q)W (Xi , Xk ))
Q

j6=i (1 − pW (Xi , Xj )1Uj ≤α )(1 − pW (Xk , Xj )1Uj ≤α )
×
.
(1 − pW (Xi , Xk ))(1 − pW (Xk , Xk ))

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

22

Then we can apply the Slyvniak-Mecke theorem to find that,
Z
hX

Q
E
1Uk ≤α 1 − j (1 − pW (x, Xj )1Uj ≤α )
E[S2 ] = α
X

×

k

1 − pW (Xk , x) Q
−
(1 − pW (Xk , Xj )1Uj ≤α )
1 − pW (Xk , Xk ) j
+ (1 − p(1 + q)W (x, Xk ))
Q
i
j (1 − pW (x, Xj )1Uj ≤α )(1 − pW (Xk , Xj )1Uj ≤α )

ρ(dx).
(1 − pW (x, Xk ))(1 − pW (Xk , Xk ))
Again, we rewrite the previous in a more convenient form to apply the
Slyvniak-Mecke theorem a second time,
Z
hX

E[S2 ] = α
E
1Uk ≤α
X

k

Q
1 − (1 − pW (x, Xk ) j6=k (1 − pW (x, Xj )1Uj ≤α )
Q
− (1 − pW (Xk , x)) j6=k (1 − pW (Xk , Xj )1Uj ≤α )
+ (1 − p(1 + q)W (x, Xk ))
×

Q

i
(1
−
pW
(x,
X
)1
)(1
−
pW
(X
,
X
)1
)
ρ(dx).
j Uj ≤α
j Uj ≤α
k
j6=k

Applying the Slyvniak-Mecke theorem to the previous,
Z Z n
Q
2
E[S2 ] = α
1 − (1 − pW (x, x0 ))E[ j (1 − pW (x, Xj )1Uj ≤α )]
X X
Q
− (1 − pW (x, x0 ))E[ j (1 − pW (x0 , Xk )1Uj ≤α )]
+ (1 − p(1 + q)W (x, x0 ))
× E[

Q

j (1

o
− pW (x, Xj )1Uj ≤α )(1 − pW (x0 , Xj )1Uj ≤α )] ρ(dx)ρ(dx0 )

Using Campbell’s formula (Kingman, 1993,
R Section 3.2) (see also the proof
of proposition 4), and defining ν(x, x0 ) = X W (x, y)W (y, x0 ) ρ(dy),
Z Z n
0
2
E[S2 ] = α
1 − (1 − pW (x, x0 ))e−pαµ(x) − (1 − pW (x, x0 ))e−pαµ(x )
X X
o
0
2
0
+ (1 − p(1 + q)W (x, x0 ))e−pαµ(x)−pαµ(x )+p αν(x,x ) ρ(dx)ρ(dx0 ).
A.2.3. Bound on the variance. We now provide the bound for E[Zp2 ] using
the expression of E[S1 ], E[S2 ] and proposition 4. Proposition 4 gives
E[Np,α ]2
Z Z 


0
= (pα)2
1 − e−pαµ(x) 1 − e−pαµ(x ) ρ(dx)ρ(dx0 )
ZX ZX n
o
0
0
2
= (pα)
1 − e−pαµ(x) − e−pαµ(x ) + e−pαµ(x)−pαµ(x ) ρ(dx)ρ(dx0 ).
X

X

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

23

Combining this with the expression for E[S1 ] and E[S2 ], we get
Z
n
o
2
2
2
e−p(1+q)αµ(x) 1 − e−p αµ(x) ρ(dx)
E[Np,α ] − E[Np,α ] = α
X
Z
Z n
o2
µ(x)e−pαµ(x) ρ(dx)
+α
1 − e−pαµ(x) ρ(dx) + 2p3 α2
X
Z XZ
n
o
2
0
−pαµ(x)−pαµ(x0 )+p2 αν(x,x0 )
2 2
e
1 − e−p αν(x,x ) ρ(dx)ρ(dx0 )
+p α
X X
Z Z
0
2
0
3
2
W (x, x0 )e−pαµ(x)−pαµ(x )+p αν(x,x ) ρ(dx)ρ(dx0 ).
− p (1 + q)α
X

X

p
By Hölder’s and Young’s inequality, we have 2ν(x, x0 ) ≤ 2 µ(x)µ(x0 ) ≤
µ(x) + µ(x0 ). Moreover, p2 ≤ p, and 1 − e−x ≤ x imply,
Z Z
o
n
2
0
0
2
0
e−pαµ(x)−pαµ(x )+p αν(x,x ) 1 − e−p αν(x,x ) ρ(dx)ρ(dx0 )
X X
Z Z
pα
pα
0
2
≤p α
e− 2 µ(x) e− 2 µ(x ) ν(x, x0 ) ρ(dx)ρ(dx0 )
X

X

If σ = 1 it follows from assumption 1 that,
Z Z
o
n
2
0
0
2
0
e−pαµ(x)−pαµ(x )+p αν(x,x ) 1 − e−p αν(x,x ) ρ(dx)ρ(dx0 )
X

X
2

Z

≤ Cp α

2
µ(x) ρ(dx) ,

X

which is finite because of equation (1). Now if 0 ≤ σ < 1, it follows from
assumption 1 and Caron and Rousseau (2017, Lemma B.4) that,
Z Z
o
n
2
0
0
2
0
e−pαµ(x)−pαµ(x )+p αν(x,x ) 1 − e−p αν(x,x ) ρ(dx)ρ(dx0 )
X

X
2 1−2η

Z

≤ Cp α

η

η − pα
µ(x)
2

α µ(x) e

2
ρ(dx) . α1−2η+2σ `(α)2 .

X

Moreover, using Caron and Rousseau (2017, Lemma B.4), it is easily seen
2 ] − E[N
2
that all other terms involved in E[Np,α
p,α ] are bounded by a multiple
constant of α1+σ for any σ ∈ [0, 1]. Since we set η = 1 when σ = 1, it follows
the estimate,
2
E[Np,α
] − E[Np,α ]2 . α1+σ + α3−2η+2σ `(α)2 .

The conclusion follows because E[Np,α ]2 & α2+2σ `(α)2 by proposition 4.
Appendix B. Proofs of asymptotic results for bipartite graphs
The results in section 3.2 are straightforward adaptions of the proofs in
Caron and Rousseau (2017). We then just give the proof for proposition 3
since the argument for the bipartite version can be made more direct.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

24

The argument runs as follows. We first provide the asymptotic behavior
(v)
of E[Dk ] in appendix B.1 and then the asymptotic behavior of the variance
in appendix B.2. The conclusion follows by Caron and Rousseau (2017,
(v)
Lemma B.1), which provides the sufficient conditions under which Dk ∼
(v)
E[Dk ] P-almost-surely as α → ∞.
In the whole section, we sill use the random variables (Ni )i∈N defined as
follows. For every i ∈ N,
X
Ni :=
1Tj ≤α Bi,j .
j∈N

(v)

B.1. Expectation of Dk . It is easily seen that,
(v)

P

= k | Πv , Πw )

P
=E
i∈N 1Ui ≤s P (Ni = k | Πv )

E[Dk ] = E

i∈N 1Ui ≤s P (Ni




αk P
k
E
i∈N 1Ui ≤s µv (Xi ) exp {−αµv (Xi )} ,
k!

=

where the last line follows by lemma 1 below. By Campbell’s formula (Kingman, 1993, Section 3.2),
Z
sαk
(v)
E[Dk ] =
µv (x)k e−αµv (x) ρ(dx).
k! X
Then the conclusion follows by straightforward adaption of Caron and Rousseau
(2017, Lemma B.2).
(v)

B.2. Variance of Dk . Proceeding as for the expectation, we find that,
(v)

E[(Dk )2 ] = E

P

i∈N

P

i0 ∈N 1Ui ≤s 1Ui0 ≤s P (Ni


= k, Ni0 = k | Πv ) .

Then using the Slyvniak-Mecke theorem, (Daley and Vere-Jones, 2003b,
Chapter 13),
P P
(v)
(v)
E[(Dk )2 ] = E[Dk ] + E[ i i0 6=i 1Ui ≤s 1Ui0 ≤s P (Ni = k, Ni0 = k | Πv )]
Then from the result of lemma 2 below,
(v)
E[(Dk )2 ]

≤

(v)
E[Dk ]

×

k
X
m=0

Z
+s
X

hX
E
1Ui ≤s e−αµv (x)−αµv (Xi )+ανv (x,Xi )
i

i
αk+m
m
m
k−m
0
0
µ
(X
)
µ
(x)
ν
(x,
X
)
ρ(dx).
v
v
v
i
i
(m!)2 (k − m)!

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

25

By Campbell’s formula (Kingman, 1993, Section 3.2),
Z Z
0
0
(v) 2
(v)
2
e−αµv (x)−αµv (x )+ανv (x,x )
E[(Dk ) ] ≤ E[Dk ] + s
X

×

k
X

X

αk+m
µv (x0 )m µv (x)m νv (x, x0 )k−m ρ(dx)ρ(dx0 ).
(m!)2 (k − m)!

m=0

Using the expression for the expectation obtained in appendix B.1, we deduce
that
(v)

(v)

(v)

E[(Dk )2 ] − E[Dk ]2 ≤ E[Dk ]
Z Z
s2 α2k
0
0
+
e−αµv (x)−αµv (x )+ανv (x,x )
(k!)2 X X
o
n
0
× µv (x)k µv (x0 )k 1 − e−ανv (x,x ) ρ(dx)ρ(dx0 )
k−1
X

+ s2

m=0

αk+m
(m!)2 (k − m)!

Z Z
X

0

0

e−αµv (x)−αµv (x )+ανv (x,x )

X

× µv (x0 )m µv (x)m νv (x, x0 )k−m ρ(dx)ρ(dx0 ).
But ν(x, x0 ) ≤ (µ(x) + µ(x0 ))/2 by Hölder’s inequality, 1 − e−x ≤ x for any
x ≥ 0, and νv (x, x0 ) ≤ Cµv (x)η µv (x0 )η under assumption 1. Then,
(v)

(v)

(v)

E[(Dk )2 ] − E[Dk ]2 ≤ E[Dk ]
Z
2
αµ (x)
s2 α1−2η
− v2
k+η
+C
e
[αµv (x)]
ρ(dx)
(k!)2
X
2
Z
k−1
X
αµ (x)
C k−m α−(2η−1)(k−m)
m(1−η)+ηk
2
− v2
[αµv (x)]
ρ(dx).
+s
e
(m!)2 (k − m)!
X
m=0

By straightforward adaption of Caron and Rousseau (2017, Lemma B.4),
(v)
(v)
we conclude that there exists a c > 0 such that E[(Dk )2 ] − E[Dk ]2 .
(v)
α−c E[Dk ]2 .
B.3. Auxiliary results. In this section, we state a certain number of auxiliary results that are used in appendices B.1 and B.2.
Notice that conditional on (Πv , Πv ), the law of {Ni }i∈I for every finite
subset I ⊂ N is characterized by the following Laplace transform, for every
t ∈ CI for which the rhs is defined,
(10) E[e−

P

i∈I ti Ni

| Πv , Πw ]
Y Y

1 + (e−ti − 1)W (Xi , Yj )1Tj ≤α
=
j∈N i∈I

= exp

nP

i∈I

o
−ti − 1)W (X , Y )] .
1
log[1
+
(e
i j
j∈N Tj ≤α

P

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

26

We use the previous result to characterize (by Fourier inversion) the distribution of Ni and the joint distribution of (Ni , Ni0 ) for i 6= i0 , conditional on
Πv .
Lemma 1. Assume that k ∈ Z+ . Then, for every i ∈ N,
P(Ni = k | Πv ) = e−αµv (Xi )

αk µv (Xi )k
.
k!

Proof. It is easily seen from equation (10) and Campbell’s formula (Kingman,
1993, Section 3.2) that Ni has Laplace transform (conditional on Πv ), for all
t ∈ C that makes sense,

t 7→ exp αµv (Xi )(e−t − 1) .
One recognize the Laplace transform of a Poisson distribution. Hence the
results follows.

Lemma 2. For any k ∈ N,
P(Ni = k1 , Ni0 = k2 | Πv ) ≤ e−αµv (Xi )−αµv (Xi0 )+ανv (Xi ,Xi0 )
×

k
X
m=0

αk+m
µv (Xi0 )m µv (Xi )m νv (Xi , Xi0 )k−m .
(m!)2 (k − m)!

Proof. From Campbell’s formula (Kingman, 1993, Section 3.2), we deduce
from equation (10) that for any (ξ1 , ξ2 ) ∈ R2 ,
n
E[eiξ1 Ni +iξ2 Ni0 | Πv ] = exp αµv (Xi )(eiξ1 − 1) + αµv (Xi0 )(eiξ2 − 1)
o
+ ανv (Xi , Xi0 )(eiξ1 − 1)(eiξ2 − 1) .
Using orthogonality of trigonometric polynomials, it is easily seen that
(11) P(Ni = k, Ni0 = k | Πv )
Z 2π Z 2π
1
E[eiξ1 Ni +iξ2 Ni0 | Πv ]e−i(ξ1 k+ξ2 k) dξ1 dξ2 .
=
(2π)2 0
0
We first compute the inner integral in equation (11). To do so, write the
intermediate integral
Z 2π
n
o
1
I(ξ2 ) :=
exp αµv (Xi )eiξ + ανv (Xi , Xi0 )(eiξ2 − 1)eiξ − iξk dξ.
2π 0
It is convenient to remark that I(ξ2 ) is a contour integral along Γ := {z ∈
C : |z| = 1}. Then,

Z
exp α[µv (Xi ) + νv (Xi , Xi0 )(eiξ2 − 1)]z
1
I(ξ2 ) =
dz
2π Γ
iz k+1
The complex exponential is analytic in the whole complex plane, thus the
integrand in the previous is holomorphic everywhere except at zero where it

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

27

has a pole of order k + 1. Thus, by the residue theorem we have
n
o
1
dk
I(ξ2 ) =
lim k exp α[µv (Xi ) + νv (Xi , Xi0 )(eiξ2 − 1)]z
k! z→0 dz
αk
=
[µv (Xi ) + νv (Xi , Xi0 )(eiξ2 − 1)]k .
k!
We introduce the new intermediate integral,
Z 2π
n
o
1
I(ξ) exp αµv (Xi0 )eiξ − ανv (Xi , Xi0 )eiξ − iξk dξ
J :=
2π 0
Z
αk
K(z)
=:
dz,
2πk! Γ iz k+1
where,
K(z) := [µv (Xi ) − νv (Xi , Xi0 ) + zνv (Xi , Xi0 )]k
× exp {αµv (Xi0 )z − ανv (Xi , Xi0 )z} .
Again, the integrand z 7→ −iK(z)z −(k+1) is holomorphic in the whole complex plane, except at zero where it has a pole of order k + 1. This time,
however, the computation of the residue at zero is more involved, but still
doable. Near z = 0, we have the Taylor series expansion,
exp {αµv (Xi0 )z − ανv (Xi , Xi0 )z}
=

k
X
αm z m
[µv (Xi0 ) − νv (Xi , Xi0 )]m + o(z k ),
m!

m=0

and by Newton’s binomial formula,
[µv (Xi ) − νv (Xi , Xi0 ) + νv (Xi , Xi0 )z]k
k  
X
k
=
[µv (Xi ) − νv (Xi , Xi0 )]k−p νv (Xi , Xi0 )p z p .
p
p=0

Therefore, as z → 0,
k

K(z) = o(z ) +

k X
k   m
X
k α
m=0 p=0

p m!

[µv (Xi0 ) − νv (Xi , Xi0 )]m

× [µv (Xi ) − νv (Xi , Xi0 )]k−p νv (Xi , Xi0 )p z m+p .
Using the previous expression, it is easily seen that
X k  αm
dk
K(z) = k!
lim
[µv (Xi0 ) − νv (Xi , Xi0 )]m
z→0 dz k
p m!
m+p=k
i≥0,p≥0

× [µv (Xi ) − νv (Xi , Xi0 )]k−p νv (Xi , Xi0 )p .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

28

Then,
k

X
dk
lim k K(z) ≤ k!
z→0 dz

m=0

  m
k α
µv (Xi0 )m µv (Xi )m νv (Xi , Xi0 )k−m .
m m!

Therefore, by the residue theorem and after simple algebra,
J≤

k
X
m=0

αk+m
µv (Xi0 )m µv (Xi )m νv (Xi , Xi0 )]k−m .
(m!)2 (k − m)!

Using this last result and equation (11), we get the following expression for
the joint distribution at (k, k).


Appendix C. Proof of the risk bound for the bipartite
estimator
The proof of theorem 2 follows the exact same line as for the theorem 1.
Here we only state the expectation and variance estimate for the random
variable


P
1X
− j∈N 1Tj ≤α Bi,j
.
1Ui ≤α 1 − 2
Ms,α :=
2
i∈N

C.1. Expectation of Ms,α . By definition of the model and applying Campbell’s formula (Kingman, 1993, Section 3.2) a couple of times,

h
ii
Q
1 hP
−Bi,j 1Tj ≤α
1
1
−
E
2
|
Π
,
Π
E[Ms,α ] = E
v
w
U
≤s
i
i∈N
j∈N
2
h

i

Q
1 P
1
= E
j∈N 1 − 2 W (Xi , Yj )1Tj ≤α
i∈N 1Ui ≤s 1 −
2

i

Q
1 hP
1
1
−
1
1
−
W
(X
,
Y
)1
= E
i j Tj ≤α
i∈N Ui ≤s
j∈N
2
2


1 P
−αµv (Xi )/2
= E
i∈N 1Ui ≤s 1 − e
2
Therefore,
(12)

E[Ms,α ] =

s
2

Z 


α
1 − e− 2 µv (x) ρ(dx).

X

As α → ∞, under our assumptions and by Caron and Rousseau (2017,
Lemma B.2),
(
sασ `v (α)Γ(1 − σ)/2
if 0 ≤ σ < 1,
R ∞ −1
E[Ms,α ] ∼
(sα/2) α z `v (z) dz if σ = 1.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

29

C.2. Variance of Ms,α . We write that,


 
P
1 P
− j 1Tj ≤α Bi,j 2
= E
i∈N 1Ui ≤s 1 − 2
4


P
P
i
P
1 hP
− j 1Tj ≤α Bi,j
+ E
1 − 2− m 1Tm ≤α Bk,m .
i∈N
k6=i 1Ui ≤s 1Uk ≤s 1 − 2
4
2
E[Ms,α
]

The first term in the rhs of the previous equation is obviously bounded by
E[Ms,α ]/4. We now take care of the second term. It is clear that,
h
E



i
P
1 − 2− m 1Tm ≤α Bk,m | Πv , Πw
Y
Y
−B 1
=1−
E[2 i,j Tj ≤α | Πv , Πw ] −
E[2−Bk,m 1Tm ≤α | Πv , Πw ]
−

1−2

P

j

1Tj ≤α Bi,j

m

j

+

Y

−Bi,j 1Tj ≤α

E[2

| Πv , Πw ]

Y

E[2−Bk,m 1Tm ≤α | Πv , Πw ]

m

j

 Y

Y
1
1
1 − W (Xk , Ym )1Tm ≤α
=1−
1 − W (Xi , Yj )1Tj ≤α −
2
2
m
j




Y
Y
1
1
+
1 − W (Xk , Ym )1Tm ≤α .
1 − W (Xi , Yj )1Tj ≤α
2
2
m
j

Note that the computation here are made slightly simpler as for the unipartite case since B is not a symmetric array and Πv and Πw are independent.
By Campbell’s formula (Kingman, 1993, Section 3.2),
h
E

−

1−2

P

j

1Tj ≤α Bi,j

= 1 − e−


i

P
1 − 2− m 1Tm ≤α Bk,m | Πv

αµv (Xi )
2

− e−

αµv (Xk )
2

+ e−

αµ (X )
αν (X ,X )
αµv (Xi )
− v2 k + v 4i k
2

.

Then, by the Slyvniak-Mecke theorem (Daley and Vere-Jones, 2003b, Chapter 13),
Z
hX
1
s
≤ E[Ms,α ] +
E
1Ui ≤s
4
4 X
i∈N

i
αµv (Xi )
αµv (Xi )
ανv (Xi ,x)
αµv (x)
αµv (x)
4
− e− 2 + e− 2 − 2 +
ρ(dx).
× 1 − e− 2

2
E[Ms,α
]

By Campbell’s formula again,
2
E[Ms,α
]

1
s2
≤ E[Ms,α ] +
4
4

Z Z

X X


αµv (x0 )
αµv (x)
αµv (x0 )
αµv (x)
ανv (x0 ,x)
× 1 − e− 2 − e− 2 + e− 2 − 2 + 4
ρ(dx)ρ(dx0 ).

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

30

Using equation (12), we find that,
1
2
E[Ms,α
] − E[Ms,α ]2 ≤ E[Ms,α ]
4


Z Z
αµ (x0 )
αν (x0 ,x)
αµ (x)
αν (x0 ,x)
s2
− v2
− v4
− v2 + v 4
+
e
1−e
ρ(dx)ρ(dx0 ).
4 X X
Moreover, νv (x0 , x) ≤ (µv (x) + µv (x0 ))/2 by Hölder’s inequality, 1 − e−x ≤ x
for all x ≥ 0, and νv (x0 , x) ≤ Cµv (x)η µv (x0 )η by assumption 2. Then,
2
E[Ms,α
] − E[Ms,α ]2

1
Cαs2
≤ E[Ms,α ] +
4
16



8
3α

2η Z

−

e

3αµv (x)
8

X



3αµv (x)
8

η

2
ρ(dx) .

Henceforth, bu a simple adaption of Caron and Rousseau (2017, Lemma B.2
and B.4), for α large enough,
(
sασ `v (α) + s2 α1−2η+2σ `v (α)2 if 0 ≤ σ < 1,
2
R∞
E[Ms,α
] − E[Ms,α ]2 .
sα α z −1 `v (z) dz + αs2
if σ = 1.
Appendix D. Proof of examples rates bounds
Here we prove the bound on Γp,α for the various examples considered in
section 2.5.
D.1. Dense graphs example. For any α > 0,
Z 
Z 


−αµ(x)
1 − e−pαµ(x) dx
dx −
1−e
R+

R+

Z

1

=

o
n
e−pαu/2 1 − e−(1−p)αu/2 du . α−1 .

0

On the other hand, we have for α large enough,
Z 1

1 − e−αu/2 du & 1.
0

Hence, Γp,α ∝

α−1 .

D.2. Sparse, almost dense graphs without power law. For any α > 0,
Z 
Z 


1 − e−αµ(x) dx −
1 − e−pαµ(x) dx
R+

R+

Z

1

n
o du
e−pαu 1 − e−(1−p)αu
u
0
Z 1/α
Z 1
du
≤ α(1 − p)
e−pαu du +
e−pαu
u
0
1/α
Z α −pv
e
≤ (1 − p) +
dv . 1.
v
1
=

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

31

On the other hand, when α > 0 is large enough,
Z 1
Z α
 du
1 − e−αu
= (1 − e−α ) log(α) −
log(v)e−v dv
u
0
0
Z
α
−α
log(v)e−v dv
≥ (1 − e ) log(pα) −
1
Z α
−α
e−v dv & log(α).
≥ (1 − e ) log(α) − log(α)
1

Hence Γp,α ∝ 1/ log α.
D.3. Sparse graphs with power law. Let b := 1/(1 − σ), then for any
α > 1,

p

σ

Z



1−e

−αµ(x)



Z
dx −

=σ

=σ


1 − e−pαµ(x) dx

R+

R+





σ
1−σ

σ

σ
1−σ

σ

(
α

σ

σ

Z

p

σα
1−σ

(1 − e

−u

−1−σ

)u

Z
du −

0

pσ α σ

Z

σα
1−σ
pσα
1−σ

σα
1−σ

)
−pu

(1 − e

−1−σ

)u

du

0

(1 − e−u ) u−1−σ du ≤

σ(1 − p)
.
p

On the other hand, when α is large enough,

σ Z σα
Z 

1−σ
σ
σ
−αµ(x)
dx = α σ
1−e
(1 − e−v )v −1−σ dv
1−σ
R+
0

σ Z σα
1−σ
σ
σ
≥α σ
e−v v −σ dv & ασ .
1−σ
0
Hence Γp,α ∝ α−σ .
D.4. Generalized Gamma Process. Note that in this example, we have
for any p ∈ [0, 1],


Z 
Z

σu −1+1/σ
(13)
1 − e−pαµ(x) ρ(dx) =
(1 − e−u ) 1 +
pα
R+
R+
!
(
!)
−1−σ




σu 1/σ
du
σu 1/σ
×
1+
−1
exp −
1+
−1
.
pα
pα
pα
We will find a bound on Γp,α by first lower bounding,
Z 

A :=
1 − e−αµ(x) ρ(dx),
R+

and then upper bounding,
Z
Z 

σ
−αµ(x)
B= p
1−e
ρ(dx) −
R+

R+




1 − e−pαµ(x) ρ(dx) .

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

32

From the two bounds in appendices D.4.1 and D.4.2, we will conclude that
Γp,α ∝ α−σ .
D.4.1. Lower bound on A. Since the integrand is a positive function, we
lower bound A by integrating on a smaller set. it is clear that when u ∈ [0, α],


σu −1+1/σ
σu 1/σ
u
1+
≥ 1, and
1+
−1. .
α
α
α
Therefore, from equation (13) we deduce that,
Z
σ
(1 − e−u )u−1−σ du & ασ .
A&α
[0,α]

D.4.2. Upper bound on B. We first write,
Z 

1 − e−pαµ(x) ρ(dx)
R+
Z
Z α

−pαµ(x)
ρ(dx) +
=
1−e
0

∞


1 − e−pαµ(x) ρ(dx)

α

=: Cp,α + Dp,α .
It is easily seen from equation (13) that for some constant c > 0 (eventually
depending on σ and p, but not α),
Z ∞
 u −1+1/σ  u (−1−σ)/σ
1/σ du
(1 − e−u )
Dp,α .
e−c(u/α)
α
α
α
α
Z ∞
1/σ
=α
(1 − e−u )u−2 e−c(u/α) du
Z ∞α
1/σ
≤
u−2 e−cu du . 1.
1

It turns out that B . |pσ C1,α − Cp,α | + 1. We now consider the function,


σu −1+1/σ
1
:=
F (p, σ, α, u)
1+
pα
pα
!−1−σ
(
!)




σu 1/σ
σu 1/σ
×
1+
−1
exp −
1+
−1
.
pα
pα
With a little bit of effort, it is seen that for any u ∈ [0, α],
F (p, σ, α, u) = u−1−σ (αp)σ + u−σ O(α−1+σ ).
Hence, pσ F (1, σ, α, u) − F (p, σ, αu) = u−σ O(α−1+σ ) whenever u ∈ [0, α]. It
follows that,
Z α
σ
−1+σ
|p C1,α − Cp,α | . α
(1 − e−u )u−σ du
0
Z 1
1
=
(1 − e−αu )u−σ du ≤
.
1
−
σ
0

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

33

Henceforth, B . 1.

References
C. Borgs, J. T. Chayes, H. Cohn, and N. Holden. Sparse exchangeable graphs
and their limits via graphon processes. ArXiv e-prints, 1 2016.
C. Borgs, J. Chayes, H. Cohn, and V. Veitch. Sampling perspectives on
sparse exchangeable graphs. Preprint, 2017.
Francois Caron. Bayesian nonparametric models for bipartite graphs. In
F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 2051–2059.
Curran Associates, Inc., 2012. URL http://papers.nips.cc/paper/
4837-bayesian-nonparametric-models-for-bipartite-graphs.pdf.
François Caron and Judith Rousseau. On sparsity and power-law properties of graphs based on exchangeable point processes. arXiv preprint
arXiv:1708.03120, 2017.
François Caron and Emily B. Fox. Sparse graphs using exchangeable random
measures. Journal of the Royal Statistical Society: Series B (Statistical
Methodology), 79(5):1295–1366, 2017. ISSN 1467-9868. doi: 10.1111/rssb.
12233. URL http://dx.doi.org/10.1111/rssb.12233.
Daryl J Daley and David Vere-Jones. An introduction to the theory of point
processes: volume I: elementary theory and methods. Springer Science &
Business Media, second edition, 2003a.
Daryl J Daley and David Vere-Jones. An introduction to the theory of point
processes: volume II: general theory and structure. Springer Science &
Business Media, second edition, 2003b.
William Feller. An introduction to probability theory and its applications,
volume II, volume 2. Wiley, New York, 1971.
Thomas S Ferguson and Michael J Klass. A representation of independent
increment processes without gaussian components. The Annals of Mathematical Statistics, 43(5):1634–1643, 1972.
Tue Herlau, Mikkel N Schmidt, and Morten Mørup.
Completely random measures for modelling block-structured sparse networks.
In D. D. Lee, M. Sugiyama, U. V. Luxburg, I. Guyon,
and R. Garnett, editors, Advances in Neural Information Processing Systems 29, pages 4260–4268. Curran Associates, Inc.,
2016. URL http://papers.nips.cc/paper/6521-completely-randommeasures-for-modelling-block-structured-sparse-networks.pdf.
S. Janson. On convergence for graphexes. ArXiv e-prints, 2 2017.
J. F. C. Kingman. Poisson Processes. Oxford University Press, 1993.
P. Orbanz and D.M. Roy. Bayesian models of graphs, arrays and other
exchangeable random structures. Pattern Analysis and Machine Intelligence, IEEE Transactions on, 37(2):437–461, 2 2015. ISSN 0162-8828. doi:
10.1109/TPAMI.2014.2334607.

AN ESTIMATOR FOR THE TAIL-INDEX OF GRAPHEX PROCESSES

34

A. Todeschini and F. Caron. Exchangeable Random Measures for Sparse
and Modular Graphs with Overlapping Communities. ArXiv e-prints, 2
2016.
V. Veitch and D. M. Roy. The class of random graphs arising from exchangeable random measures. ArXiv e-prints, 12 2015.
V. Veitch and D. M. Roy. Sampling and Estimation for (Sparse) Exchangeable Graphs. ArXiv e-prints, 11 2016.
V. Veitch, E. Sharma, Z. Naulet, and D.M. Roy. Exchangeable modelling of
relational data: Checking sparsity, data splitting, and sparse exchangeable
poisson matrix factorization. arXiv, 11 2017.

