The Class of Random Graphs Arising from Exchangeable Random Measures

Introduction

Random graph models are a key tool for understanding the structure of real-world networks, especially through data. In particular, a random graph model can serve as the foundation for a statistical analysis: observed link structure is modeled as a realization from the random graph model, whose parameters are in some unknown configuration. The goal is to then infer the configuration of the parameters, and in doing so, understand properties of the network that gave rise to the observed link structure.

The quality of the inferences we can make depends in part on the fidelity of the model, but building realistic models of networks is challenging: the models must be simple enough to be tractable, yet flexible enough to accurately represent a wide range of phenomena. In the setting of densely connected networks, the well-known exchangeable graph model provides a tractable yet general framework. However, the vast majority of real-world networks are sparsely connected—two nodes chosen at random are very unlikely to be directly connected by a link. Accordingly, for some configuration of their parameters, realistic random graph models for networks must be sparse, exhibiting only a vanishing fraction of all possible edges as they become large. At the same time, the link structure of real-world networks is rich: e.g., in social networks, phenomena such as homophily (informally, friends of friends are more likely to be friends), “small-world” connectivity (two randomly chosen individuals are likely to be connected by a short path of friendship), and power law degree distributions (the number of friends an individual may have varies across many orders of magnitude) are common [New09, Dur06]. It is a remarkable gap in modern statistical practice that there is no general framework for the statistical analysis of real-world networks.

There is no shortage of proposals for random graph models of real-world networks; however, these models tend to be ad hoc, exhibiting certain properties of real-world networks by design, but behaving pathologically in other aspects. It is difficult to assess the statistical applicability of such models.

One approach to identifying large but tractable families of random graphs is to consider the family of all random graphs satisfying a small number of natural assumptions. In this paper, we define a class of random graph models in terms of a single invariance principle: that the distribution of a graph should be invariant to an arbitrary relabeling of its vertices. From this assumption, we derive and study a general class of random graphs suitable for modeling network structures. We show that these random graphs admit a simple, tractable specification and give rise to complex structures of the kinds observed in real world networks. Moreover, our derivation is closely analogous to an approach that has been used to define broadly useful statistical models in other settings. For instance, the classical i.i.d. setting and the graphon setting for densely connected networks are both derived from analogous invariance assumptions [OR15]. Indeed, we show that the exchangeable graph models are a special case of the models we derive here. These observations suggest that the models we identify in this paper may be broadly useful for the statistical analysis of real-world networks.

To explain our approach we begin by reviewing a closely related approach used to define models for the statistical analysis of densely connected networks. In this setting, networks are modeled as random graphs represented by their adjacency matrices; an observed $n\times n$ adjacency matrix is modeled as the leading size-$n$ principal submatrix of some infinite array of random variables. The infinite structure automatically provides consistent models for datasets of different size. The foundational structural assumption by which the dense graph framework is defined is a probabilistic symmetry: joint exchangeability of the infinite array. This is the requirement that the distribution of the infinite array is invariant under joint permutations of the indices of the array; intuitively, this means that the labeling of the vertices of a graph does not carry information about its structure.

The derivation of the dense graph framework is a particular instance of a general recipe for constructing statistical models: a probabilistic symmetry is assumed on some infinite random structure and an associated representation theorem characterizes the ergodic measures, forming the foundation of a framework for statistical analysis. The first main contribution of the present paper is the analogous representation theorem for the sparse (and dense) graph setting, which we arrive at by a straightforward adaptation of a result of Kallenberg [Kal90, Kal05]. Our inspiration comes from recent paper of Caron and Fox [CF14] that exploits a connection between random measures and random graphs to exhibit a class of sparse random graphs. In their paper, they observe that their random graphs satisfy a natural analogue of joint exchangeability when considered as a point process and make use of an associated representation theorem to study the model. The present paper reverses this chain of reasoning, beginning with the symmetry on point processes and elucidating the full family of random graphs that arise from the associated representation theorem. In the graph context, joint exchangeability of point processes retains the interpretation that the labels of vertices carry no information about the structure of the graph.

Finite size graphs are given by restricting to only edges $(\theta_{i},\theta_{j})$ such that $\theta_{i},\theta_{j}<\nu$ and including vertices only if they participate in at least one such edge. These distributions are consistent for datasets of different sizes and admit sparse graphs, allowing for the realistic modeling of physical networks. Moreover, in a sense we make precise in Section 3.1, the exchangeable graphs derived from the Aldous–Hoover theory are contained as a subfamily of the Kallenberg exchangeable graphs, and correspond those graphs generated by graphexes of the form $(0,0,W)$ where $W$ is compactly supported, and therefore equal to the dilation of some graphon. Thus the KEG framework is a generalization of the exchangeable graph framework to the sparse graph regime.

Given a point $(\theta,\vartheta)$ in the latent Poisson process, the degree of the vertex labeled $\theta$ is Poisson distributed with mean $\nu\mu_{W}(\vartheta)$.

The expected number of edges $e_{\nu}=\lvert e\left(G_{\nu}\right)\rvert$ is

The expected number of vertices $v_{\nu}=\lvert v\left(G_{\nu}\right)\rvert$ is

Subject to some technical constraints, the scaling limit of the asymptotic degree distribution has an explicit expression in terms of $W$. Let $k_{\nu}$ be some non-decreasing function of $\nu$ and let $D_{\nu}$ be the degree of a randomly selected vertex of $G_{\nu}$, then

This result establishes that the random graph construction in this paper can give rise to sparse graphs.

Certain choices of $W$ admit highly connected graphs. Suppose $W(x,y)=f(x)f(y)$, let $C_{1}(G_{\nu})$ be the largest connected component of $G_{\nu}$, and let $\epsilon>0$, then

This means that the sparse structure can arise in an interesting way: it is not simply a consequence of having a collection of disjoint dense graphs.

We begin by giving background on random graph modeling and the use of probabilistic symmetry in Section 2. In Section 3, we give a number of illustrative examples of Kallenberg exchangeable graphs to make the construction concrete. In Section 4, we establish the representation theorem and give a formal characterization of the models we derive. In Section 5, we derive the first moments of several graph statistics of $G_{\nu}$ using point process techniques, allowing self edges. An expression for asymptotic degree distribution of these graphs in terms of the graphex is derived in Section 6. Finally, in Section 7, we study the structure of the Kallenberg exchangeable graphs generated by graphexes of the form $W(x,y)=f(x)f(y)1[x\neq y]$ with the goal of establishing the asymptotic connectivity structure. Several other interesting features of these random graphs are uncovered in the course of establishing this result. In particular, we show that degree power law distributions and “small-world” phenomena arise naturally in this framework.

Background

In order to relate the Kallenberg exchangeable graph model to a diverse range of existing random graph models, it will be useful to have a general definition for the term ‘random graph model’. In this paper, a random graph model is an indexed family of graph-valued random variables $G_{s,\phi}$, where $s$ specifies the “size” of the graph and takes values in a totally ordered set $S$, and where $\phi\in\Phi$ determines some distributional properties (and so could play the role of a parameter in a statistical model). We will write $\mu_{s,\phi}$ for the distribution of $G_{s,\phi}$.In a statistical setting, the family of distributions $\mu_{s,\phi}$ would be the natural structure to call a model. Here we adopt the language of graph theorists. Our definition is deliberately vague about the meaning of ‘graph-valued’ as different models will naturally be described in terms of different concrete spaces.

The Erdős–Rényi–Gilbert model can be seen as special case of the more general random graph model that arises from the graphon theory or from the Aldous–Hoover representation theorem. In this case, the size again determines the number of vertices, but the parameter is a graphon, i.e., a symmetric, measurable function $W:^{2}\to$. (The Erdős–Rényi–Gilbert model corresponds with constant graphons $W(x,y)=p$ for some $p\in$.) This class of random graphs are known as the exchangeable graphs, although we will sometimes refer to them as the (dense) exchangeable graphs to distinguish them from the Kallenberg exchangeable graphs.

In the exchangeable graph model, the size parameter is the number of vertices. This is the typical approach to indexing random graph models. In contrast, the size parameter of a Kallenberg exchangeable graph model is a non-negative real $\nu$ that is proportional to the square root of the expected number of edges.

For the purpose of modeling real-world networks, one of the key properties of a random graph model is the relationship between the number of edges and vertices. Consider a random graph model $G_{s,\phi}$, fix a parameter $\phi$, and let $s_{n}\!\uparrow\!\infty$ be some diverging sequence of sizes. For a graph $G$, let $\lvert e\left(G\right)\rvert$ and $\lvert v\left(G\right)\rvert$ denote the number of edges and vertices, respectively. To avoid pathologies, we will assume that $\lvert v\left(G\right)\rvert\to\infty$ as $n\to\infty$. Then the sequence $(G_{s_{n},\phi})$ is sparse or not dense if, with probability one,

This condition states that, asymptotically, graphs with $v$ vertices have $o(v^{2})$ edges. More generally, it is interesting to identify whether there is a (potentially random) exponent $k$ such that, asymptotically, there are $\Theta(v^{k})$ edges.

For statistical applications, it is desirable to impose a desideratum in addition to sparsity. The prototypical statistical network analysis has the following structure: an observed network $g_{s}$ is modeled as a realization of a random graph $G_{s,\phi}$ for some size $s$ and for some unknown parameter $\phi$; the goal is to infer the parameter $\phi$. In some random graph models, the sequence $G_{s_{1},\phi},G_{s_{2},\phi},\dotsc$ of graphs is a model of the dynamics by which a network grows and evolves. In the statistical problems motivating this paper, however, the size parameter $s$ is akin to sample size in the sense that collecting more data corresponds to choosing larger values of $s$. It is therefore natural to demand that the distributions associated with different sizes are “consistent” with one another in the sense that moving from $G_{s,\phi}$ to $G_{t,\phi}$, for $t>s$, can be understood as collecting additional data.

One way to formalize this notion of consistency is to demand that the distributions of the random graphs $G_{s,\phi}$ be projective. Projectivity is defined in terms of a projective system, i.e., a family of measurable maps $(f_{s,t};\,s\leq t\in S)$ where $f_{s,t}$ maps graphs of size $t$ to graphs of size $s\leq t$, $f_{s,s}$ is the identity, and $f_{r,t}=f_{r,s}\circ f_{s,t}$ for all $r\leq s\leq t$. A random graph model is projective if, for some projective system $(f_{s,t};\,s\leq t\in S)$, it holds that $G_{s,\phi}\overset{d}{=}f_{s,t}(G_{t,\phi})$ for every $s<t\in S$ and parameter $\phi$.

Intuitively, this is simply the requirement that a data set of size $t$ can be understood as a data set of size $s<t$ augmented with some additional observations. Indeed, if a random graph model $(G_{s,\phi})$ is projective with respect to a projective system $(f_{s,t};\,s\leq t\in S)$, then it is possible to construct the random variables $G_{s,\phi}$ in such a way that the identity $G_{s,\phi}=f_{s,t}(G_{t,\phi})$ holds almost surely, and not only in distribution. In view of this, the connection with the idea of $s$ as sample size is clear. The graphs $G_{s_{j},\phi}$ for an increasing sequence $s_{1},s_{2},\dotsc$ of sizes are nested.

The projectivity of the KEG model sets it apart from random graph models that achieve sparsity by percolating dense random graph models such as the exchangeable graph model, i.e., a sparse graph model is produced by randomly deleting each edge in a dense graph model independently with a probability that grows with the number of vertices. Examples of such models abound [BJR07, BR07, BCCZ14, BCCZ14a], and in some cases consistent estimators have been developed [WO13, BCCG15, BCS15]. Each of these random graph models is parametrized by a size $n$ that determines the number of vertices, and, for every size $n$, these random graph models are also jointly exchangeable. It then follows from the Aldous–Hoover and graphon theory, as well as the fact that they are not dense, that these random graph models are not projective.

While dropping projectivity allowed for sparse random graph models, the lack of projectivity complicates the statistical applicability of these models. At the very least, the interpretation of the aforementioned consistency results is not straightforward. Indeed, these models are usually understood to generate the size $n$ graphs independently of each other. Even an adaptation of these models designed to impose some consistency between datasets of different size seems inappropriate for modeling data observation as, for instance, every time a new vertex is observed some fraction of the edges already in the graph will be randomly deleted.

2. Models from symmetries

Up until this point, we have focused on very general desiderata for random graph models. Merely requiring sparsity and projectivity, however, does not alone lead to a tractable class of models. Indeed, without any restrictions on the model, data will convey no information as to the process that gave rise to it. To enable statistical inference, it is necessary to make some structural assumptions on the parametrization of the random graph model. At the same time, we want a flexible model to serve as the foundation of a broadly applicable framework for the statistical analysis of network data, and so we want to impose as few assumptions as possible.

A general approach towards identifying large tractable families of distributions is to consider the class of all distributions satisfying a particular invariance. The structure of such invariant classes can be understood in general terms using very general results on ergodic decompositions, or, in some cases, via explicit characterizations given by so-called representation theorems. Both (dense) exchangeable graphs and KEGs are examples of such families, but to clarify the idea of defining a class of models by an invariance principle, we will review a fundamental class of examples: the exchangeable sequences. (The following development owes much to [OR15], where the reader can find more details.)

The distribution $\mu$ is uniquely determined by $\mathcal{P}$, and vice versa. From Eq. 2.5, we can see that the space of distributions of exchangeable sequences is a convex set. It is known that every such distribution can be written as a unique mixture of the infinite product measures of the form $m^{\infty}$, which are the extreme points. These extreme points are precisely the ergodic measures.

The statistical utility of exchangeability is obvious: it follows from the disintegration theorem [Kal01] and the law of large numbers that

The statistical utility of exchangeability is not merely a matter of theoretical convenience; the vast majority of statistical practice falls under the remit of this framework. Inference of the kind taught in introductory statistics courses is recovered by restricting $\mathcal{P}$ to have support only on families of models with finite dimensional parameterizations, e.g., the normal distributions. The case where $\mathcal{P}$ has support on distributions without finite dimensional parameterizations are so called non-parametric models, of which there are many practical examples.

3. Models for graphs from symmetries

We have seen how the assumption that an idealized infinite sequence of observations is exchangeable leads to a considerable simplification of the space of distributions under consideration. Moreover, it is clear that finite samples can be used to make inferences about the generating process. We now turn to related results for networks. In particular, we derive the traditional exchangeable graph model from exchangeability and then connect it to the Kallenberg exchangeable graph model.

Let us now consider probabilistic symmetries on this infinite idealized network observation. The class of exchangeable sequences has a literal—if naïve—counterpart in the graph setting: the class of edge-exchangeable graphs. The assumption that the edges are exchangeable is the assumption that

The natural analogue of exchangeability in the graph setting is to assume that the labels of the vertices are exchangeable. Informally, this is the assumption that the vertex labels carry no information. Given that we are representing an observed adjacency matrix as a prefix of an idealized infinite symmetric binary array, vertex-exchangeability is formalized as the requirement that distribution of the array is invariant under simultaneous permutation of its rows and columns. More carefully, an array of random variables $X_{i,j}$ is jointly exchangeable when

where $\mu$ is a measure on the space of symmetric functions from the unit square to the unit interval with zero diagonal. The fact that projective and jointly exchangeable adjacency matrices cannot be sparse is a simple consequence of this generative model and the law of large numbers. In particular, any nondiagonal entry is one with probability $\|W\|_{1}$. This framework is the exchangeable graph model, whose nomenclature is now self explanatory. Comparing the generative model for the exchangeable graph model with the KEG generative model (see Fig. 1) makes it clear that the distinction that allows for more general graphs in the KEG setting is that the latent variables associated with each vertex are not independent, and the sizes of the graphs are random.

4. Random graphs as random measures

It is important to note that the graph corresponding to the restriction $G_{s}$ to $[0,s]^{2}$ has as its vertex set only those vertices $x\in[0,s]$ that appear in some edge $(x,y)$ where $y\in[0,s]$. In particular, there will, in general, be vertices in $[0,s]$ that appear for the first time in a restriction $[0,t]$, for $t>s$. This is an essential property of this representation, and is the way that the seeming equivalence between exchangeability and density can be relaxed. The point labeled 2.7 in Fig. 1 provides a concrete example of this phenomena.

Examples

The above argument suggests that the most densest graphs will correspond to those $W$ that are compactly supported. Let $\widetilde{W}:^{2}\to$ be a graphon and consider the graphex given by the dilation

In this case, points $(\theta,\vartheta)\in\Pi$ of the latent Poisson process will fail to connect to an edge if $\vartheta>c$, and so such points they never participate in the graph and can be discarded. This means that for finite size graph $G_{\nu}$ given by restricting $\theta\leq\nu$ the relevant underlying process is the unit rate Poisson process on $[0,\nu]\times[0,c]$. The generative model for the graph can be expressed as:

In fact, these are the only dense KEGs arising from (integrable) graphexes: Theorem 5.6 shows that $G$ is dense iff the generating (integrable) graphex has compact support.

2. Slow Decay

We next consider a graphex with tails that go to 0 slowly:

By Theorem 5.5 the number of vertices with degree $k$ has expectation:

By Theorem 6.1 it follows that the degree $D_{\nu}$ of a uniformly selected vertex of $G_{\nu}$ satisfies

so in particular a randomly selected vertex of $G_{\nu}$ will have finite degree even in the infinite graph limit. For large $k$

so this is an example of a random graph model with power-law degree distribution. Note that, in the limit, while the degree of a randomly chosen vertex is finite almost surely, it is infinite in expectation.

3. Fast Decay

Next we consider a graphex with quickly decaying tails. Let

Then $\mu(x)=e^{-x}$ and so by Theorem 5.4

As expected, the rapidly decaying graphex gives rise to a graph that is much more dense than one from the slowly decaying graphex.

By Theorem 5.5 the number of vertices with degree $k$ has expectation:

so that for fixed $k$ only a vanishing fraction of the vertices will have degree $k$ as $\nu\to\infty$. More precisely, since $\sum_{k=1}^{\nu^{\beta}}\frac{\nu}{k}\sim\beta\nu\log\nu,\ \nu\rightarrow\infty$ we have by Theorem 6.1 that for $0<\beta<1$

where $D_{\nu}$ is a random vertex of $G_{\nu}$.

4. Caron and Fox

As already alluded to, the family of random graph models considered by Caron and Fox in [CF14] is a special case of the one considered here. Indeed, in their paper they prove their model satisfies joint exchangeability when considered as a random measure and use Kallenberg’s representation theorem to derive some model properties. Nevertheless, the connection is opaque because their model is constructed from products of completely random measures and they cast their model in terms of Lévy process intensities. If the $\bm{\theta}\times\bm{\theta}$ measure they had studied had been a product of completely random measures, that model would have corresponded to a graphex of the form $W(x,y)=f(x)f(y)$. Instead, they actually consider a measure on $\bm{\theta}\times\bm{\theta}$ given by using the product of completely random measures as a base measure for a Cox process. This gives rise to a directed multigraph which is then transformed into a simple graph by including edge $\{\theta_{i},\theta_{j}\}$ if and only if there is at least one directed edge between $\theta_{i}$ and $\theta_{j}$. A little algebra shows this model corresponds to the graphex

Representation Theorem for Random Graphs represented by Exchangeable Symmetric Simple Point Processes

Note that the adjacency measures of a graphs $G$ and $G^{\prime}$ coincide if and only if their edge sets do. In particular, vertices that do not participate in an edge are “forgotten”. We will be interested in the smallest graph corresponding to an adjacency measure $\xi$, which is necessarily the graph with the same edge set and no isolated vertices. (See Fig. 3 for an illustration.)

This correspondence extends to directed weighted graphs in an obvious way by dropping the requirement that the adjacency measure be symmetric and allowing the adjacency measure to assign a mass other than one to each of its atoms; i.e., a directed weighted adjacency measure is a locally finite purely atomic measure, and so would have the form $\xi=\sum_{ij}\omega_{ij}\delta_{(\theta_{i},\theta_{j})}$.

A random adjacency measure is an (a.s. locally finite) symmetric simple point process. We will represent random graphs by their random adjacency measures, noting that only nonisolated vertices are captured by this representation.

The task is to translate this into a statement about random graphs, or more specifically, their adjacency measures. Because adjacency measures are purely atomic, all terms with a Lebesgue component (Eq. 4.5) must have measure zero. The remaining purely atomic terms underlying a jointly exchangeable random measure have the following interpretation for adjacency measures:

$\sum_{i,j}f(\alpha,\vartheta_{i},\vartheta_{j},\zeta_{\{i,j\}})\delta_{\theta_{i},\theta_{j}}$: this term contributes most of the interesting structure for the random graph models. The random measure $\xi$ will be symmetric and simple if and only if $f$ is a.e. $\{0,1\}$-valued and symmetric in its second and third arguments, for a.e. fixed first and fourth argument. (It is clear that this can easily be strengthened to hold everywhere.) This leads to the correspondence illustrated in Fig. 1. (General $f$ could be used to model directed, weighted graphs in an obvious way.) The tuples $(\theta_{i},\theta_{j})$ are possible edges of the graph and the points $\theta_{i}$ are candidate vertices.

$\sum_{j,k}(g(\alpha,\vartheta_{j},\chi_{jk})\delta_{\theta_{j},\sigma_{jk}}+g^{\prime}(\alpha,\vartheta_{j},\chi_{jk})\delta_{\sigma_{jk},\theta_{j}})$: this term contributes stars. To see this, note that each candidate vertex $\theta_{j}$ has an associated Poisson process $\{\sigma_{jk}\}$. The points are a.s. distinct: i.e., $\{\theta_{l}\}\cap\{\sigma_{jk}\}=\emptyset$ and $\{\sigma_{jk}\}\cap\{\sigma_{lk}\}$ for $j\neq l$ with probability one. This means the candidate vertices $\{\sigma_{jk}\}$ will only ever participate in edges with $\theta_{j}$, hence the star structure. The random measure $\xi$ will be a.s. symmetric and simple iff $g=g^{\prime}$ and $g$ is $\{0,1\}$-valued.

The following theorem characterizes the space of exchangeable adjacency measures as well as its extreme points:

Let $\xi$ be a random adjacency measure. Then $\xi$ is jointly exchangeable iff almost surely

The second term of this measure corresponds to stars centered at the points $\{\theta_{j}\}$ and the third term corresponds to isolated edges that do not connect to the rest of the graph.

Most of this result is immediate from the text preceding the theorem. One direction of the correspondence is immediate: the random measure $\xi$ is obviously jointly exchangeable.

In the other direction, let $f$, $\alpha$, $\{\theta_{i},\vartheta_{i}\}$, and $\{\zeta_{\{i,j\}}\}$ be as in Theorem 4.6, and let

Similarly, letting $g$ and $l$ be as in Theorem 4.6, define

A similar argument to above can be used to show that the terms involving $S$ and $I$ agree with their counterparts in Theorem 4.6. ∎

In general, an exchangeable simple point process $\xi$ of the form above may not be finite when restricted to a finite region $[0,t]^{2}$. We want finite restrictions of the adjacency measure to correspond to finite size observations, and so we must isolate conditions on the triple $(I,S,W)$ so that the random measure is a.s. finite on bounded sets. The following result, due to Kallenberg, gives necessary and sufficient conditions for a jointly exchangeable measure to be a.s. locally finite.

Let $\xi$ be as in Theorem 4.6, write $\hat{f}=f\wedge 1$, and let

where $\Lambda_{23}^{2}$ denotes two-dimensional Lebesgue measure in the second and third coordinates, and similarly for $\Lambda_{13}^{2}$ and $\Lambda_{2}$. For fixed $\alpha$, the random measure $\xi$ is a.s. locally finite iff these five conditions are fulfilled:

$\Lambda(\hat{l}+\hat{h}+\hat{h}^{\prime})<\infty$,

$\Lambda(\hat{g}_{1}+\hat{g}_{1}^{\prime})<\infty$,

$\Lambda\{f_{i}=\infty\}=0$ and $\Lambda\{f_{i}>1\}<\infty$ for $i=1,2$,

$\Lambda^{2}[\hat{f};f_{1}\vee f_{2}\leq 1]<\infty$,

$\Lambda\hat{l}^{\prime}+\Lambda_{D}\Lambda\hat{f}<\infty$.

(Note that we have corrected a typo in part (iv), where the integral was taking w.r.t. $\Lambda$ not $\Lambda^{2}$.) The consequences for adjacency measures is as follows:

$\Lambda\{\mu_{W}=\infty\}=0$ and $\Lambda\{\mu_{W}>1\}<\infty$,

In particular, $\xi$ is a.s. locally finite if $S$ and $W$ are integrable and $I<\infty$.

An example showing that there are nonintegrable $W$ admitting a.s. locally finite exchangeable adjacency measures is the function $W(x,y)=1[xy\leq 1]$. Its marginal is $\mu_{W}(x)=\frac{1}{x}$, which obviously satisfies (iii). Moreover, $W=0$ a.e. on the set $\{(x,y):\mu_{W}(x)\wedge\mu_{W}(y)\leq 1\}=\{(x,y):x,y\geq 1\}$, satisfying (iv).

These conditions leads us to the following definition:

In situations where there is no risk of confusion, we will abuse nomenclature and use the term graphex to refer to the $W$ component alone, with the understanding that the corresponding triple is $(0,0,W)$.

The name graphex is chosen in analogy to graphon, the limit object in the dense graph setting, and graphing, the limit objects in the bounded degree graph setting [Lov13].

The marginal $\mu_{W}$ of the graphex component $W$ arises in the characterization of a.s. finite undirected graph point processes. This function will turn out to be an important quantity in a number of different contexts.

We now define the class of Kallenberg exchangeable graphs:

The first term of Eq. 4.2 gives essentially all of the interesting graph structure, and so for the rest of the paper, we will restrict attention to models that take $S=I=0$. Before doing so, we note that the natural analogue of Erdős–Rényi–Gilbert graphs in the KEG model corresponds to graphs for which $I\geq 0$, $S=0$, and $W$ is constant on a set of the form $[0,c]^{2}$ and 0 otherwise. In this case, if $W$ is not identically zero, then later results will imply that the truncated graph sequence is dense.

Consider now the structure arising from $W$ alone. Because $I=S=0$, we will refer to $W$ as the graphex without any risk of confusion. Let $\Pi$ be a unit rate Poisson process on $\bm{\theta}\times\bm{\vartheta}$ as in Theorem 4.7. A Kallenberg exchangeable graph $G$ associated with $W$ has vertex set

Notice that if $G$ is a KEG associated to $W$ and $G_{\nu}$ is $G$ restricted to $\left[0,\nu\right]$ then $G_{\nu}$ is not the same as the induced subgraph of $G$ given by restricting to vertices of $G$ with labels $\leq\nu$. The reason for this is that the induced subgraph includes an (infinite) collection of vertices that do not connect to any edges. However, it is true that $G_{\nu}\!\uparrow\!G$ in the sense that $v(G_{\nu})\!\uparrow\!v(G)$ and $e(G_{\nu})\!\uparrow\!e(G)$ as $\nu\!\uparrow\!\infty$.

The model can be extended to weighted graphs by replacing the indicator term $1[W(\alpha,\vartheta_{i},\vartheta_{j})\leq\zeta_{\{i,j\}}]$ by a general random variable parameterized by $W(\alpha,\vartheta_{i},\vartheta_{j})$. The model can be extended to directed graphs by mimicking the 4-graphon approach used by [CAF15] to extend the exchangeable graph model to directed graphs.

We will often refer to $\Pi$ as the latent Poisson process. For a point of the latent Poisson process $(\theta_{i},\vartheta_{i})\in\Pi$ the label of the point is $\theta_{i}$ and the latent value is $\vartheta_{i}$.

We close this section with a word of warning about point process notation:

Point processes are central to our construction. For a point process $\bm{P}$ we will often refer to points $p_{i}\in\bm{P}$ where the index $i$ is given by some unspecified measurable function of $\bm{P}$. For example, if $\bm{P}$ is a Poisson process then the points could be indexed by the ordering of their Euclidean distances to the origin. This is convenient for writing summations across the point process and for unambiguously associating dimensions when the points are multidimensional (e.g., $p_{i}=(a_{i},b_{i})$ then we understand $a_{i}$ and $b_{i}$ are part of the same tuple in $\bm{P}$). However, there is a small subtlety here: any choice of indexing function will be informative about the value of the point of the process. For example, if the points of a Poisson process are indexed by their distance to the origin then the value of the index is informative about the value of the point. As a result, some care must be taken when making statements of (conditional) independence.

Expected Number of Edges and Vertices

In this section we derive the expected values of the number of vertices and edges of Kallenberg exchangeable graphs restricted to $[0,\nu]$, in terms of their underlying graphex. We focus on those graphexes where $I=0$ and $S=0$ so we refer to $W$ as the graphex without any risk of confusion. Throughout this section we implicitly assume $W$ is non-random; in the case of random $W$ the results can be understood as conditional statements.

The intuition for the main proof idea is to find the distribution of the degree of a single point in the latent Poisson process, write the statistics of interest as sums of functions of the degrees of the points and appeal to the linearity of expectation to evaluate these expressions. For example, the number of edges in a graph is the sum of the degrees of all of the vertices divided by 2. This perspective allows the use of powerful techniques for computing expectations of sums over point processes.

is the degree of a point $(\theta,\vartheta)\in\Pi_{\nu}$ under a KEG process, conditional on $(\theta,\vartheta)\in\Pi_{\nu}$.

With probability 1, $\lambda\notin\Pi_{\nu}^{P}$ so

Since $\zeta_{{\scriptscriptstyle i}(\lambda){\scriptscriptstyle i}(\lambda)}\sim U$ independent of everything else letting

where the a.s. finiteness is one of the defining conditions of the graphex $W$. It then follows by a version of Campbell’s theorem [Kin93], the characteristic function of $D_{\mbox{ext}}$ is

We would now like to access the first moments of various graph quantities by writing them as sums of (functions of) the degree and exploiting the linearity of expectation to circumvent dependencies. For example, the total number of edges of the graph is

where the equality is in distribution (as opposed to almost sure) because the indexing $\scriptscriptstyle i(x)$ of the latent Poisson process used by the degree function is not the same as the indexing used in Theorem 4.7.

Standard point process formulas deal with computing expressions of the form

By the independence of $U$ and $\Phi$, the non-negativity of $f$, and Tonelli’s theorem, we have

By the usual Palm calculus, the inner expectation satisfies

where $P_{x}$ is the local Palm distribution of a unit rate Poisson process. Letting $P$ be the distribution of a unit rate Poisson process, the Slivnyak–Mecke theorem gives:

The result then follows by a second application of Tonelli’s theorem to change the order of integration. ∎

The main results of this section now follow easily:

The expected number of edges $e_{\nu}=|e\left(G_{\nu}\right)|$ is

The expected number of visible vertices $v_{\nu}=|v\left(G_{\nu}\right)|$ is

where $D_{\mbox{ext}}$ and $D_{\mbox{self}}$ are defined as in Lemma 5.1. Splitting up the integral is justified since $1-\exp(-\nu\mu_{W}(x))\geq 0$ and $\exp(-\nu\mu_{W}(x))W(x,x)\geq 0$ for all $x$. ∎

A nearly identical argument can be used to find the expected number of vertices of a specified degree. This result is interesting in its own right and is used as a lemma in Section 6.

The expected number of vertices of degree $k$ in $G_{\nu}$, $N_{\nu,k}$, is

The result follows from essentially the same argument as the previous two theorems and some straightforward algebraic manipulations. ∎

Notice that in the limit as $\nu\to\infty$ the contribution of self edges ($W(\lambda,\lambda)\neq 0$) is negligible in the sense that terms due to the edges between distinct vertices dominate asymptotically for Theorems 5.3, 5.4 and 5.5.

We end this section by applying our results on the expected number of vertices and edges to show that a KEG is dense iff the generating graphex is compactly supported.

Let $G$ be Kallenberg exchangeable graph with graphex $(0,0,W)$. If $W$ is compactly supported, then $G$ is dense with probability 1. Conversely, if $W$ is integrable and not compactly supported, then $G$ is sparse with probability 1.

We have already shown in Section 3.1 that if $W$ is compactly supported then the corresponding KEG is dense (or empty) with probability 1 because these models correspond exactly to graphon models.

Conversely, suppose that the KEG $G$ generated by $W$ is dense with positive probability. This means that there are constants $c,p>0$ such that

where $e_{\nu}=e\left(G_{\nu}\right)$ and $v_{\nu}=v\left(G_{\nu}\right)$. With

Degree Distribution in the Asymptotic Limit

One of the major advantage of KEGs over previous exchangeable graph models is that they allow for sparse graphs of the kind typically seen in application; in particular this means the KEG models should allow for a variety of degree (scaling) behaviours. Caron and Fox [CF14] characterized the degree distribution in the large graph limit for the particular case of directed graphs based on generalized gamma processes. We now describe the limiting degree distribution of Kallenberg exchangeable graphs. We focus on those graphexes where $I=S=0$ so we refer to $W$ as the graphex without any risk of confusion. To formalize the notion of limiting degree distribution, let $G_{\nu}$ be a Kallenberg exchangeable graph on $[0,\nu)$ with graphex $W$, and let $D_{\nu}$ be the degree of a vertex chosen uniformly at random from $v\left(G_{\nu}\right)$. The central object of study is then the random distribution function $k\mapsto P(D_{\nu}\leq k\mid G_{\nu})$ and its scaling limit. The primary aim of this section is to prove the following theorem:

Let $W$ be an integrable graphex such that

There is some $\chi>0$ such that for all $x>\chi$ holds that $\frac{\mu_{W}(x)}{\mu_{W}^{\prime}(x)}\frac{1}{x}\geq-1$.

In the case $\mu_{W}(\lambda)=(1+\lambda)^{-2}$ the right hand side of this expression is in $(0,1)$ for $k_{\nu}=k$ for any choice of $k$. That is, even in the infinite graph limit a constant fraction of the vertices will have degree $\leq k$ for a fixed integer $k$. By contrast, for $\mu_{W}(\lambda)=e^{-\lambda}$ the degree of a randomly chosen vertex goes to $\infty$ so, for fixed $k$, $\mbox{P}(D_{\nu}>k\mid G_{\nu})\xrightarrow{\,p\,}1$. However, we saw that $\mbox{P}(D_{\nu}>\nu^{\beta}\mid G_{\nu})\to 1-\beta$ for $\beta\in(0,1)$; i.e., taking $k_{\nu}=\nu^{\beta}$ results in a non-trivial limit on the right hand side. That is, this theorem can be understood intuitively as characterizing the rate of growth of the degree of a typical vertex. This scaling limit affords a precise notion of “how dense” the graph associated to a particular graphex is.

Let $n_{>l}^{{}_{(\nu)}}$ denote the number of vertices of $G_{\nu}$ with degree greater than $l$. It is immediate that

i.e., the probability of choosing a vertex of degree greater than $k_{\nu}$ is the proportion of such vertices among all vertices. Notice that, even for fixed $l$, the random variable $n_{>l}^{{}_{(\nu)}}$ grows with $\nu$. Further notice that like $D_{\nu}$ the random variable $n_{>k_{\nu}}^{{}_{(\nu)}}/n_{>0}^{{}_{(\nu)}}$ is ill defined for the event $n_{>0}^{{}_{(\nu)}}=0$; however this is a measure event in the limit $\nu\to\infty$. The content of Theorem 6.1 can be understood as saying that the limit of the ratio $\frac{n_{>l}^{{}_{(\nu)}}}{n_{>0}^{{}_{(\nu)}}}$ is the limit of the ratio of the expectations,

Reasoning about the degree of a randomly selected vertex is substantially simplified by selecting only from those with label $\theta\in$ and ignoring the contribution of edges $(\theta_{i},\theta_{j})$ with $\theta_{i},\theta_{j}\leq 1$. The reason for this is that it allows us to eliminate one form of dependence between the degrees of distinct points; namely the dependence arising from the requirement that each terminus attached to a vertex has a matching terminus attached to some other vertex in the set. Intuitively, studying this simplification is valid because the $\theta$ labels of the points of the latent Poisson process are independent of their degrees and as the graph becomes large only a negligible number of edges have both termini with labels $\theta\leq 1$. Let $N_{>l}^{{}_{(\nu)}}$ be the number of vertices of $G_{\nu}$ with label $\theta_{i}<1$ and greater than $l$ neighbours $\{\theta_{j}\}$ where $\theta_{j}>1$. The following lemma establishes the claimed equivalence:

The limiting distribution of $n_{>l}^{{}_{(\nu)}}/n_{>0}^{{}_{(\nu)}}$ is the same as the limiting distribution of the ratio that considers only vertices with label $\theta_{i}\leq 1$ and counts only edges $(\theta_{i},\theta_{j})$ with $\theta_{j}>1$,

The validity of this equality is a consequence of the following three observations:

$\lim_{\nu\to\infty}\mbox{P}(N_{>0}^{{}_{(\nu)}}=0)=0$ so $\lim_{\nu\to\infty}\frac{N_{>l}^{{}_{(\nu)}}}{N_{>0}^{{}_{(\nu)}}}$ is well defined.

The number of edges $(\theta_{i},\theta_{j})$ with $\theta_{i},\theta_{j}\leq 1$ is almost surely finite and $N_{>0}^{{}_{(\nu)}}\!\uparrow\!\infty$ almost surely, so the probability of randomly choosing a vertex that participates in at least one of the neglected edges goes to as $\nu\to\infty$, thus

To treat the limiting distribution of this ratio we introduce

i.e., we break the latent Poisson process into the component with $\theta\leq 1$ and the component with $\theta>1$ and then project out the $\theta$ value of $\Pi_{0}$ since it contains no useful information. Notice that $\Pi_{0}$ and $\Pi_{(1,\nu+1]}$ are independent Poisson processes.

There exists a marking $(\lambda_{i},\bar{\zeta}_{i})$ of $\Pi_{0}$ where each $\bar{\zeta}_{i}=(\zeta_{j}^{i})$ is a sequence of independent $U$ random variables such that

is the degree of the point $\lambda\in\Pi_{0}$. Let $\bar{U}_{j}=(U_{i}^{j})$ be independent sequences of independent $U$ random variables and define

These random variables will arise naturally in the course of the proof.

It follows by mimicking the proof of Lemma 5.1 that

marginally. The importance of $D_{\nu}(\lambda,\bar{\zeta}_{i},\Pi_{(1,\infty)})$ in the context of the present section comes from the relation

where $(U_{i})^{\lambda}$ is a marking of $\Pi_{0}$. We will make heavy use of the observation that, by Campbell’s formula,

The idea of the proof of Theorem 6.1 is to show that

Using Chebyshev’s inequality, a sufficient condition for Eq. 6.16 to hold is

The majority of the proof is aimed at characterizing the growth rate of $\mbox{var}\left[N_{>k_{\nu}}^{{}_{(\nu)}}\right]$.

In order to do this, we will need to make an assumption about the graphex $W$ that controls the average dependence between the degrees of different vertices of $G_{\nu}$:

We do not know of any examples of an integrable graphex that violates this assumption, although $W(x,y)=1[xy<1]$ does. To understand what the assumption means, let $L(\lambda,\omega)$ be the number of common neighbours of points $(l,\lambda),(w,\omega)\in\Pi_{\nu}$ under $G_{\nu}$ and observe that for a graphex $W$ that is on the diagonal (i.e., forbidding self-edges),

with respect to the Palm measure $P_{\lambda,\omega}$Recall this is just the measure that guarantees that $\lambda,\omega$ are elements of the point process.. This can be shown by an argument very similar to Lemma 5.1. Thus the assumption can be understood as requiring that the average number of common neighbours between a pair of vertices is at most a constant factor larger than it would be in the case $W(x,y)=\mu_{W}(x)\mu_{W}(y)$.

We further assume for simplicity that $\mu_{W}(x)$ is strictly monotonically decreasing, differentiable and that there is some $\chi>0$ such that for all $x>\chi$ holds that $\frac{\mu_{W}(x)}{\mu_{W}^{\prime}(x)}\frac{1}{x}\geq-1$. It is not clear which, if any, of these assumptions are necessary for the result to hold. The last condition in particular may already be implied by the other assumptions. Moreover, the result will hold automatically for a graphex $W$ if there is some other graphex $W^{{}^{\prime}}$ such that $W^{{}^{\prime}}$ satisfies the conditions of the theorem and the KEGs corresponding to $W$ and $W^{{}^{\prime}}$ are equal in distribution.

Invertibility implies that $W$ does not have compact support; i.e., the graph is sparse (Theorem 5.6). A particular consequence of this last assumption is that for any function $l(\nu)\to 0$ as $\nu\to\infty$ it holds that $\mu_{W}^{-1}(l(\nu))\to\infty$, a fact that will be used heavily in this section and the next.

Subject to these assumptions we may now begin the argument to bound $\mbox{var}\left[N_{>k_{\nu}}^{{}_{(\nu)}}\right]$.

Let $\{(\lambda_{i},\bar{\zeta}_{i})\}$ be a marking of $\Pi_{0}$ such that each $\bar{\zeta}_{i}=(\zeta_{j}^{i})$ is a sequence of independent identically distributed $U$ random variables and

is the degree of point $\lambda$. Conditional on $\Pi_{(1,\infty)}$ the degrees $D_{\nu}(\lambda,\bar{\zeta}_{i},\Pi_{(1,\infty)})$ of each point $\lambda\in\Pi_{0}$ are a marking of $\Pi_{0}$ so

Using this, the formula for conditional variance is

An application of Campbell’s formula to the second term gives:

Bounding the variance requires controlling the average dependence between $D_{1,\nu}(x)$ and $D_{2,\nu}(y)$, as captured by the second term in the lemma above. The degree of a point $\lambda$ gives information about the degree of a point $\omega$ only through $\Pi_{(1,\nu+1]}$. Intuitively, as $\nu\to\infty$, the degree of $\lambda$ gives very little information about $\Pi_{(1,\nu+1]}$ so the pairwise dependence between degrees is weak and the variance of $N_{>l}^{{}_{(\nu)}}$ is small. Formalizing this intuition proves to be somewhat tricky. Essentially, the strategy is to find a bound of the form

Let $T$ be a value such that for $y>T$ it holds that

It is conceptually helpful to think of $a,b$ as points of the latent Poisson process with $\vartheta$ values $x,y$ respectively, but the proof does not make formal use of this. The expression

makes it clear that $g(y)$ is a bound on $\mbox{P}(D_{b}>k_{\nu}|D_{a}>k_{\nu})-\mbox{P}(D_{b}>k_{\nu})$. The focus will be on bounding $\mbox{P}(D_{b}>k_{\nu}|D_{a}>k_{\nu})$. To do this, introduce a marking $\{((\theta_{i},\vartheta_{i}),M_{i})\}$ of $\Pi_{(1,\infty)}$ where

indicates whether each point connects to $a$. This induces the obvious markingthe full marking is defined on $\Pi_{(1,\infty)}$ for consistency of the indices of the points $(\theta_{i},\vartheta_{i}).$ on $\Pi_{(1,\nu+1]}$ that breaks $\Pi_{(1,\nu+1]}$ into two independent sets:

the non-neighbours of $a$. By construction $\lvert N_{a}\rvert=D_{a}$ and the neighbours $N_{a}=\{\vartheta_{i}\}_{i=1}^{D_{a}}$ are, conditional on $D_{a}$, independently and identically distributed with probability density

where, by an application of Campbell’s theorem,

It is now clear that the dependence of $D_{b}$ on $D_{a}$ comes in only through the number of trials of $D_{b}^{(N_{a})}\mid D_{a}$.

To treat $D_{b}^{(N_{a})}$ conditional on the event $D_{a}>k_{\nu}$ we introduce random variables $L_{1},L_{2}$ such that on the event $\{D_{a}>k_{\nu}\}$

and implicitly specify the joint distribution of $L_{1},L_{2}$ by requiring $L_{1}$ to have marginal distribution

conditional on $\{D_{a}>k_{\nu}\}$. Intuitively, $L_{1}$ is the number of neighbours of $a$ that would exist without conditioning on $D_{a}>k_{\nu}$ and $L_{2}$ is the number of additional neighbours that are present as a result of the conditioning. Therefore on the event $\{D_{a}>k_{\nu}\}$ there are random variables $B_{1},B_{2}$ such that:

independently conditional on $L_{1},L_{2}$. The point of introducing these auxiliary random now becomes clear as:

Intuitively, conditional on $\{D_{a}>k_{\nu}\}$, $D_{b}$ splits into a term

with the unconditional distribution of $D_{b}$ plus a term $B_{2}$ that accounts for the ’extra’ neighbours of $b$ that one expects to see as a result of learning that the degree of $a$ is large.

so that to complete the proof it remains to show that $R\leq g(y)$. For $\nu\mu_{W}(y)$ large the crude bound

suffices. This establishes the claim for $y\leq T$ in the lemma statement. The remaining task is to find a good bound in the regime of $y$ where $\nu\mu_{W}(y)$ is not large. In particular, it suffices to find a bound for $B_{2}$ independent of $H$ with a distribution that does not depend on $x$. To that end, let $b>0$ and write

The salient fact here is that $\varphi(l)=\sum_{n=0}^{b}{l\choose n}p(x,y)^{n}(1-p(x,y)^{l-n}$ is a convex function in $l$ and so by a conditional Jensen’s inequality

This can be understood as the following sampling scheme for a truncated Poisson distribution:

Draw $l_{1}$ from the Poisson distribution. If $l_{1}>k_{\nu}$ stop.

Otherwise sample $y$ from the truncated distribution, so that $l_{1}+(y-l_{1})$ is a trivially a correct sample.

The definitions above can be used to derive:

which can be seen by noting that there is some random variable $G$ such that

For $\nu\mu_{W}(x)\leq 2k_{\nu}$, it immediately follows that

where the final line uses $2C\mu_{W}(y)\leq 1-\log 2$. It then follows that

Putting together Eqs. 6.72, 6.74, 6.80 and 6.89:

where, conditional on $D_{a}>k_{\nu}$, $H$ and $B(y)$ are independent with

Roughly speaking, the content of the previous two lemmas amounts to

Let $g(y)$ be as in Lemma 6.4 and suppose $W$ is integrable. If the sequence $k_{\nu}$ is bounded then

The case $k\!\uparrow\!\infty$ is substantially trickier. Essentially the strategy here is to break up to domain of $y$ into three components and use a different tractable and reasonably tight bound on $g(y)$ in each region, see Table 1. An important intermediate step is the observation

Because $\mbox{P}(D_{2,\nu}(y)\leq k_{\nu})$ is monotonically increasing in $y$ over the domain of integration, the integral is bounded by

The next lemma controls the second term in this bound.

Suppose there is some $\chi>0$ such that for all $x>\chi$ it holds that

then, for $\nu$ sufficiently large such that $\frac{k_{\nu}}{\nu}\leq\mu_{W}(\chi)$ and $\epsilon$ such that $0<\epsilon<1$,

Because $\mu_{W}(y)$ is strictly monotonic the component of the bound that depends on $y$ may be integrated by substitution. For notational simplicity, let $f(x)=\mu_{W}^{-1}(y)$, then

so by assumption for $x\leq\mu_{W}(\chi)$ holds that $x\frac{f^{\prime}(x)}{f(x)}\geq-1$. Thus for $\nu$ sufficiently large that $\frac{k_{\nu}}{\nu}\leq\mu_{W}(\chi)$ it holds that

Moreover, $xf(x)$ is a monotonically non-decreasing function on $x\leq\mu_{W}(\chi)$, which may be established by:

The next lemma establishes the other half of the tail bound for $g(y)$:

Suppose there is some $\chi>0$ such that, for all $x>\chi$,

and let $B$ and $C$ be as in Lemma 6.4. For $\nu$ sufficiently large such that $\frac{k_{\nu}}{\nu}\leq\mu_{W}(\chi)$ and $\epsilon$ such that $10C\frac{k_{\nu}}{\nu}\leq\epsilon<1$,

The condition $10C\frac{k_{\nu}}{\nu}\leq\epsilon$ ensures that

It remains to integrate this bound. Let $f(x)=\mu_{W}^{-1}(x)$ then

Following the same reasoning as in the proof of Lemma 6.7,

In particular, the last several lemmas combine to show that for $\epsilon_{\nu}\leq 1$ such that $\epsilon_{\nu}=\omega(\frac{1}{k_{\nu}})$ and $\epsilon_{\nu}=\omega(\frac{k_{\nu}}{\nu})$ it holds that

Suppose that $\mu_{W}$ is differentiable and that there is some $\chi>0$ such that for all $x>\chi$ it holds that

Then for $\epsilon>0$ and $\nu$ sufficiently large such that $(1+\epsilon)\frac{k_{\nu}}{\nu}\leq\mu_{W}(\chi)$, it holds that

Let $f(x)=\mu_{W}^{-1}(x)$. Since $\mu_{W}$ is differentiable so is $f$. By the mean value theorem there is some point $(1-\epsilon)\frac{k_{\nu}}{\nu}\leq x^{*}\leq(1+\epsilon)\frac{k_{\nu}}{\nu}$ such that

where the final line follows as in Lemma 6.7. ∎

We can now complete our intermediate goal:

Let $g(y),\ T$ and $C$ be as in Lemma 6.4. Suppose $k_{\nu}\!\uparrow\!\infty$ and $k_{\nu}=o(\nu).$ Suppose that $\mu_{W}$ is differentiable and that there is some $\chi>0$ such that for all $x>\chi$ it holds that

Let $\epsilon_{\nu}\!\downarrow\!0$ such that $\epsilon_{\nu}=\omega(\sqrt{\frac{1}{k_{\nu}}})$ and $\epsilon_{\nu}=\omega(\sqrt{\frac{k_{\nu}}{\nu}})$. Let

Because $\mu_{W}$ is not compactly supported, for $\nu$ sufficiently large $\mu_{W}^{-1}((1+\epsilon_{\nu})\frac{k_{\nu}}{\nu})>T$ and in this regime it is immediate that

Moreover, it is straightforward to verify that the conditions on $\epsilon_{\nu}$ with Lemmas 6.6, 6.7, 6.8 and 6.9 imply

(For Lemma 6.6 it suffices to consider the worst case $\epsilon_{\nu}=\sqrt{\frac{1}{k_{\nu}}}$.)

We are now equipped to give the proof of the main result:

where $g(y)$ is as defined in Lemma 6.4. Lemma 6.5, for bounded $k_{\nu}$, and Lemma 6.10, for $k_{\nu}\!\uparrow\!\infty$, establish

Connectivity for Separable KEGs

A serious omission in the results presented thus far is that they give virtually no information about the global structure of the KEGs. In particular, we have as yet made no statements about the connectivity structure of these graphs. The sparse structure that we explore here could, in principle, arise from graphs that consist of large numbers of disconnected dense components. If this were to be the case then these graphs would be uninteresting for physical applications. Our aim in this section is to give a preliminary result showing that this is not the case.

We call a KEG separable if the associated graphex has $I=S=0$ and $W$ of the form

We prove that separable KEGs have an arbitrarily large fraction of the vertices contained in a single connected component in the large graph limit. (As usual, because there is no risk of confusion, we will use the term graphex to refer to the function $W$. )

Separability in combination with the graphex integrability conditions immediately implies that $f$ and hence $W$ is integrable and thus that this result only applies for graphs that have a finite expected number of edges when restricted to finite support $\nu$.

The main obstacle to the study of connectivity in the KEG setting is that the graphs are naturally defined in terms of the infinite collection of points in the latent Poisson process with only a finite number of these participating as points in a sampled graph. The difficulty is that traditional tools (e.g. [Bol01]) for studying connectivity begin with a fixed set of vertices of the graph and examine how they become connected as edges are randomly introduced, an approach that is apparently futile in the present setting where we must specify the edge set in order to specify the vertex set. The tactic we use to circumvent this problem hinges on the division of the KEG into three parts based on the latent $\vartheta$ values of the vertices: the induced subgraph below some threshold value, the induced subgraph above this threshold and the bi-graph between them; see Fig. 4. The first piece intuition is that for fixed $\nu$ we can set the threshold $T_{\nu}$ such that nearly every point of the latent Poisson process with $\vartheta$ below $T_{\nu}$ will have an edge connected to it; because of this we can treat the connectivity of the below $T_{\nu}$ induced subgraph using the traditional random graph machinery. The connectivity of vertices lying above $T_{\nu}$ that participate in at least one edge connecting below $T_{\nu}$ then follows straightforwardly. This leaves only the vertices in the induced subgraph above $T_{\nu}$ that do not connect to a point below $T_{\nu}$ and it will turn out that these constitute a negligible fraction of the graph.

We begin by showing we can take $f(x)$ to be monotone decreasing without loss of generality:

Let $W(x,y)=f(x)f(y)1[x\neq y]$ be a separable graphex, then there is some other separable graphex $W^{{}^{\prime}}=h(x)h(y)1[x\neq y]$ such that $h$ is monotone decreasing and the KEGs associated to $W$ and $W^{{}^{\prime}}$ are equal in distribution.

If $f(x)$ has bounded domain (i.e., $W$ is a graphon) then the result follows immediately from [Lov13], which shows that for any bounded $f$ with compact support there is some measure preserving transformation $\varphi$ on the domain of $f$ and monotone decreasing $h$ such that $f=h\circ\varphi$.

We take $f$ to be monotone decreasing for the remainder of the section. Because the result is trivial for $f$ with bounded domain (the KEG is dense) we also take $f$ to have unbounded domain. Denote the left continuous inverse of $f$ by $f^{-1}(t)=\inf\{\lambda\,:\,f(\lambda)=t\}$. We will make frequent use of the observation that for $l_{\nu}\in o(1)$ it holds that $f^{-1}(l_{\nu})\in\omega(1)$. Let $G$ be a Kallenberg Exchangeable Graph associated with $W$ and let $G_{\nu}$ be the restriction to $\left[0,\nu\right]$.

Let $t_{\nu}$ be a function of $\nu$ such that $t_{\nu}\in o(1)$ and $t_{\nu}\in\omega(\frac{1}{\nu})$ and define the threshold $T_{\nu}=f^{-1}(\frac{1}{\nu}+t_{\nu})$.

This notation for the threshold suppresses the dependence on $t_{\nu}$, which should be thought of as going to as quickly as possible consistent with $t_{\nu}\in\omega(\frac{1}{\nu})$.

The proof now proceeds roughly as follows:

We establish the existence of a connected core that we will show nearly every vertex of the graph connects to (Lemma 7.6)

We show that nearly every point of $\Pi_{\nu,\leq T_{\nu}}$ participates in an edge connecting to the connected core (Lemma 7.7)

We lower bound the number of points of $\Pi_{\nu,>T_{\nu}}$ that connect to the connected core (Lemma 7.8)

We consider the induced subgraph of $G_{\nu}$ given by $\{\theta_{i}\in v\left(G_{\nu}\right)\mid\vartheta_{i}>T_{\nu}\}$ and show that the number of points in this subgraph that fail to connect to the connected core is an arbitrarily small fraction of the number of vertices in the graph (Lemma 7.10)

Suppose $f$ does not have compact support. Let $T_{\nu,\mbox{pop}}=f^{-1}(\sqrt{\frac{\log\nu}{\nu}})$ and let $P_{\nu}$ be the induced subgraph of $G_{\nu}$ given by including only vertices in $\Pi_{\nu,<T_{\nu,\mbox{pop}}}$, then:

Every element of $\Pi_{\nu,\leq T_{\nu,\mbox{pop}}}$ connects to an edge; $\lim_{\nu\to\infty}\lvert\Pi_{\nu,\leq T_{\nu,\mbox{pop}}}\backslash v\left(P_{\nu}\right)\rvert=0\textrm{ a.s.}$

$P_{\nu}$ is almost surely connected; let $C(P_{\nu})=1$ if $P_{\nu}$ is connected and otherwise, then $\lim_{\nu\to\infty}C(P_{\nu})=1\textrm{ a.s.}$

$P_{\nu}$ is “ultra-popular” almost surely; letting $S_{\nu}=\sum_{p\in P_{\nu}}f(p)$ we have for $\epsilon>0$ that $\lim_{\nu\to\infty}\frac{S_{\nu}}{\nu}\geq(1-\epsilon)\|f\|_{1}\textrm{ a.s.}$

For arbitrary $\gamma>0$, it holds that $\lim_{\nu\to\infty}N_{\nu}/\nu T_{\nu,\mbox{pop}}\geq(1-\gamma)\mbox{ a.s.}$ and so we have that:

Thus in the limit as $\nu\to\infty$, the random graph with vertices $\Pi_{\nu,\leq T_{\nu,\mbox{pop}}}$ and independent edge probabilities $f(\vartheta_{i})f(\vartheta_{j})$ is connected and, in particular, every vertex is contained in an edge, thereby establishing claims $1$ and $2$.

It remains to show that $S_{\nu}$ grows as claimed. For $\gamma>0$, by Hoeffding’s inequality we have:

for $\nu$ sufficiently large since $T_{\nu,\mbox{pop}}\to\infty\mbox{ as }\nu\to\infty$. Whence,

Using that $f(x)$ is monotonic and must be integrable we have that $f(x)=o(\frac{1}{x})$ so $\nu/T_{\nu,\mbox{pop}}\geq(\nu\log\nu)^{1/2}$ and

Finally, using $\lim_{\nu\to\infty}\frac{N_{\nu}}{\nu T_{\nu,\mbox{pop}}}\geq(1-\gamma)\mbox{ a.s.}$ and the Borel–Cantelli lemma establishes

and the result follows since $\gamma>0$ is arbitrary. ∎

We now have a promise that every point of the latent Poisson process $\Pi_{\nu,\leq T_{\nu,\mbox{pop}}}$ participates in the graph. We now establish that, with high probability, as $\nu\to\infty$ an arbitrarily large fraction of the points in $\Pi_{\nu,\leq T_{\nu}}$ connect to the popular connected core $P_{\nu}$. In particular, this means an arbitrarily large fraction of the points of $\Pi_{\nu,\leq T_{\nu}}$ participate in a single connected component of $G_{\nu}$.

Suppose $f$ does not have compact support. Let a point $(\theta_{i},\vartheta_{i})\in\Pi_{\nu,\leq T_{\nu}}$ be visible if $\theta_{i}\in v\left(G_{\nu}\right)$ and it participates in an edge connecting to $P_{\nu}$, and call a point invisible otherwise. Let $N_{\mbox{invis},\leq T_{\nu}}$ be the number of points in $\Pi_{\nu,\leq T_{\nu}}$ that are invisible and let $N_{\mbox{vis},\leq T_{\nu}}$ be the number of points in $\Pi_{\nu,\leq T_{\nu}}$ that are visible, then for $\epsilon>0$

By Lemma 7.6 it follows that as $\nu\to\infty$ there are no invisible vertices below $T_{\nu,\mbox{pop}}=f^{-1}(\sqrt{\frac{\log\nu}{\nu}})$ so it suffices to bound the number of invisible vertices between $T_{\nu,\mbox{pop}}$ and $T_{\nu}$. Conditional on $P_{\nu}$, each point $(\theta_{i},\vartheta_{i})\in\Pi_{\nu,>T_{\nu,\mbox{pop}}}$ connects to $P_{\nu}$ independently with probability $1-\prod_{p\in P_{\nu}}(1-f(\vartheta_{i})f(p))\geq 1-e^{-f(\vartheta_{i})S_{\nu}}$ where $S_{\nu}=\sum_{p\in P_{\nu}}f(p)$. Since labeling each point of the Poisson process $\Pi_{\nu,>T_{\nu,\mbox{pop}}}$ by whether or not it connects to $T_{\nu,\mbox{pop}}$ is, conditional on $P_{\nu}$, a marking of the Poisson process, we immediately have that the number of visible and invisible points in $\{(\theta_{i},\vartheta_{i})\in\Pi_{\nu}\mid T_{\nu,\mbox{pop}}<T_{\nu}\}$ are independent random variables and that there exists random variables $N_{\nu,\mbox{ub}}$ and $N_{\nu,\mbox{vis}}$ such that,