Sparse exchangeable graphs and their limits via graphon processes

1. Introduction

• Generalized graphons are symmetric integrable functions on σ-finite spaces, and the framework also accommodates mixed-membership structures.For mixed membership, a vertex feature combines community proportions with a within-community role, while graphons encode interactions between communities.Source: §1 · pp. 2, 7
• A graphon process samples vertex features from a Poisson point process of intensity tµ and connects each pair with probability W(x, x′).Removing isolated vertices yields almost surely finite graphs under appropriate integrability conditions, including W ∈ L1.Source: §1 · pp. 2–4
• Graphon processes are characterized by joint exchangeability and uniform regularity of tails, extending the Aldous–Hoover characterization to this setting.The process also includes classical dense W-random graphs and sparse models as special cases.Source: §1 · p. 4
• These processes are projective and need no explicit density-rescaling parameter; they are suited to sparsity from later vertices having lower connectivity.The introduction contrasts this with models where sparsity comes from approximately uniform degree scaling.Source: §1 · p. 4
• Two graphons have cut distance zero exactly when their graphon processes have the same distribution.The paper therefore identifies the generating graphon only up to this equivalence.Source: §1 · p. 6
• Stretched graphons provide sparse-graph limits, and graphon processes converge to their generating graphon in the stretched cut metric.The construction rescales the step-function graphon’s input arguments so its L1 norm is 1.Source: §1 · p. 6
• Every graphon is equivalent to one on R+ with Lebesgue measure, while sparse cut-metric convergence is not equivalent to subgraph-frequency convergence.Randomly sampled graphs nevertheless satisfy a notion of left convergence.Source: §1 · p. 8
• A graph sequence has a convergent subsequence exactly when it has a subsequence with uniform regularity of tails.The result is stated for simple graphs in the introduction.Source: §1 · p. 8

2.1 Measure-theoretic Preliminaries

• For σ-finite measure spaces, a coupling is a measure on the product space with the two given measures as marginals, and the paper establishes that such couplings exist.The measures must have equal total mass in (0, ∞].Source: §2.1 · p. 10

2.2 Graphons and Cut Metric

• A graphon is a symmetric, measurable, integrable real-valued function on a σ-finite measure space of positive measure, which may have infinite measure.The underlying measure space is part of the graphon definition; restricting its function values to [0, 1] is required only for some results.Source: §2.2 · pp. 10–11
• Two graphons have cut distance zero exactly when their invariant L1 distance is zero; on σ-finite Borel spaces, suitable restrictions can also be coupled to agree almost everywhere.The restrictions are to the sets where the respective graphons have positive integrated absolute mass.Source: §2.2 · pp. 12–13
• Every graphon is cut-distance equivalent to one over R+, and graphons on probability spaces recover the classical theory as a special case.The cut distance is a pseudometric on graphons and a metric on their equivalence classes.Source: §2.2 · p. 13

2.3 Graph Convergence

• Finite weighted graphs are represented by canonical graphons, while sparse graph sequences converge trivially to zero under the ordinary cut metric when their graphon L1 norms vanish.The paper introduces a different rescaling for sparse graph convergence: stretch the canonical graphon to L1 norm one by rescaling its arguments, equivalently the underlying measure.Source: §2.3 · p. 14
• For graphons on general measure spaces, the stretched-distance construction rescales the underlying measure rather than the function, extending the stretched-graphon approach beyond R+.For a graphon of zero L1 norm, the stretched graphon is defined to be zero.Source: §2.3 · pp. 15–16
• The stretched cut metric distinguishes sparse graph sequences that classical sparse convergence can treat alike: an Erdős–Rényi sequence converges to W1 classically but not in the stretched metric, while a clique-plus-isolates sequence does the reverse.Both sequences’ canonical graphons converge to zero in the classical cut metric; the second sequence converges to W1 in the stretched cut metric.Source: §2.3 · p. 16
• A uniformly bounded graphon sequence with uniformly regular tails has a cut-metric convergent subsequence; for non-negative graphons, every Cauchy sequence has uniformly regular tails.For finite graphs with non-negative, uniformly bounded edge weights and finite edge sets, uniformly regular tails likewise yield a subsequence converging in the stretched cut metric, while a stretched-cut-Cauchy sequence has uniformly regular tails and converges.Source: §2.3 · pp. 17–18
• The set of all [0, 1]-valued graphons is complete under the cut metric, and therefore also under the stretched cut metric.Convergence in this setting requires uniformly regular tails, so completeness does not imply compactness.Source: §2.3 · p. 18
• For sparse graph sequences, uniform upper regularity and uniformly regular tails cannot both hold.The proposition also states that for dense sequences with convergent edge density, the sequence is Cauchy under the rescaled cut metric.Source: §2.3 · p. 19
• If graphons converge in cut metric, their measures of vertices with degree-function value above λ converge at every continuity point of the limiting degree distribution.For finite simple graphs with o(|E(Gn)|) isolated vertices and |E(Gn)| tending to infinity, stretched-cut convergence to a graphon implies unbounded average degree.Source: §2.3 · p. 20

2.4 Random Graph Models

• A graphon process is built from a Poisson random measure on R+ × S with intensity λ × μ, connecting each distinct vertex pair independently with probability W(x1, x2).At time t, retaining points with time coordinate at most t and then removing isolated vertices gives Gt; when μ(S) is infinite, the graph before removing isolates has infinitely many vertices but finitely many edges almost surely.Source: §2.4 · p. 21
• The graphon process is the random family generated by W, defined up to relabeling of vertices, with or without isolated vertices.The with-isolates version retains the induced graphs eGt; the version without isolates retains Gt.Source: §2.4 · p. 22
• For projective graph processes with empty-start, single-vertex births, joint exchangeability and uniformly regular tails are equivalent to a random graphon representation on R+, conditional on a random α and up to permanently isolated vertices.Source: §2.4 · p. 23
• Two graphons have cut distance zero exactly when their graphon processes have the same law, up to relabeling and removal of vertices isolated for all times.Source: §2.4 · pp. 23–24
• Theorem 28 extends graphon convergence results to graphon processes and a sequential feature-sampling model; for the latter, nested finite-measure sets covering S and a nonzero W give almost-sure metric convergence.Source: §2.4 · p. 24

2.5 Left Convergence

• Graphon processes have convergent rescaled subgraph densities for connected test graphs, possibly with infinite limits; if the graphon degree function lies in every finite Lp space, these densities are finite and the process is almost surely left convergent.Source: §2.5 · p. 26
• Unlike for dense graphs, left convergence and metric convergence are not equivalent here; bounded-degree graph sequences are left convergent, with rescaled densities tending to zero for connected test graphs on at least three vertices.Source: §2.5 · p. 26

• For non-negative graphons in Lp, p ∈ (1, ∞), δp is well defined, independent of extension choices, and a pseudometric.Source: Appendix A · p. 27
• Every atomless σ-finite Borel space is isomorphic to [0, µ(S)) with its Borel σ-algebra and Lebesgue measure.Source: Appendix A · p. 27
• Step functions are dense in L1, so every graphon can be approximated arbitrarily closely in the cut metric by a step function.Source: Appendix A · p. 30
• For step-function graphons, equal coupling masses on each partition cell yield the same cut and Lp norms under either coupling.Source: Appendix A · p. 30
• For graphons on equal-total-measure spaces, both δ□ and δp satisfy the triangle inequality.Source: Appendix A · p. 31
• δ□ and δ1 are unchanged by trivial extensions; the same holds for δp when p > 1 and both graphons are non-negative.Non-negativity is necessary for the δp extension result when p > 1.Source: Appendix A · p. 32

Appendix A. Cut Metric and Invariant Lp Metric

• The cut distance is independent of the choice of extensions and is a pseudometric; the same argument establishes the invariant Lp metric result for nonnegative graphons in L1 and Lp.The Lp result applies for p > 1; the graphons must be nonnegative and belong to both spaces.Source: Appendix A · p. 36
• When µ ≤ µ′ ≤ (1 + ε)µ and the graphon function is unchanged, Lemma 44 gives δ□(W, W′) ≤ 3ε∥W∥1,µ.The measures are on the same measurable space, and ε ∈ (0, 1).Source: Appendix A · p. 36
• If δ□(W, W′) ≤ ε²/2, Lemma 45 bounds µ′({DW′ > λ + ε}) between µ({DW > λ + 2ε}) − ε and µ({DW > λ}) + ε.The proof of Proposition 21 uses this bound at continuity points of µ({DW > λ}) and establishes matching upper and lower bounds.Source: Appendix A · pp. 37–38

Representation of graphons over R+

• Every graphon is equivalent to one over R+, and atomless Borel graphons can be represented over an interval with Lebesgue measure.An arbitrary graphon is a pullback of one on a σ-finite Borel space; if the original space is atomless, that Borel space can also be atomless.Source: Appendix B · pp. 38–40

Equivalent definitions of the cut metric

• For infinite-measure graphons, Proposition 48 gives alternative definitions of the cut metric under Borel, atomless Borel, or R+ assumptions.In the R+ case, one formulation uses interval permutations that permute equal-length intervals.Source: Appendix B · p. 40

Zero-distance and coupling results

• For Lp graphons with p ≥ 1, zero δ1 distance is equivalent to zero cut distance, and the cut-metric argument extends to δ1 and, under conditions, δp.The δp extension applies to non-negative graphons in Lp.Source: Appendix B · pp. 41–42
• If two Borel-space graphons have zero cut distance and equal total measure, a measure with dominated marginals exists; it is a coupling when both exceptional sets are null.The appendix notes that these additional assumptions are necessary for the coupling conclusion.Source: Appendix B · p. 42
• Examples show the coupling conclusion can fail without zero cut distance or when the exceptional-set condition is not met.The appendix gives one example where every coupling has a larger cut-based discrepancy than the cut distance, and another with zero cut distance but positive coupling discrepancy.Source: Appendix B · p. 43

Appendix B. Representation of Graphons Over R+

• Because the limits satisfy μ_{M+1}|[0,M]^2 = μ_M, they define a measure μ on R_+^2, and a subsequence of μ_n converges weakly to μ, with restrictions converging weakly on each [0,M]^2.Source: Appendix B · p. 45
• If δ□(W1, W2) = 0, then δ1(W1, W2) = 0 for graphons over R_+ and general measure spaces.The proof extends the R_+ result using Proposition 10, the triangle inequality, and pullbacks.Source: Appendix B · p. 46
• For graphons over R_+, δ□(W1, W2) = 0 implies δp(W1, W2) = 0 when δ□ and δp use measure-preserving transformations.The proof uses Proposition 51 to construct a measure and coupling measures.Source: Appendix B · p. 47
• Conversely, δp(W1, W2) = 0 implies δ□(W1, W2) = 0 under the stated transformation or coupling definitions, including for general σ-finite spaces.For transformations, the proof first establishes δ1(W1, W2) = 0; the coupling and general-space cases use Proposition 48, Remark 49, and Lemma 47.Source: Appendix B · p. 47

Appendix C. Measurability properties of graph processes

• For càdlàg graph processes, measurability of specified vertex-and-edge-state time sets follows by testing intersections with Q.This yields measurability of permanent isolation and vertex birth times.Source: Appendix C · pp. 47–48
• Equality up to relabeling of two graph processes is a measurable event.The proof constructs a bijection from finite partial maps, stabilizing images and inverse images along subsequences.Source: Appendix C · pp. 48–49
• The equality test reduces to processes without permanently isolated vertices, with matching cardinalities of equivalence classes of such vertices.The proof then constructs a relabeling as a bijection between the remaining vertices.Source: Appendix C · p. 48

Proposition 56

• For any simple graph F with no isolated vertices, Proposition 56 relates its normalized count in the graphon process almost surely to the corresponding integral of W, allowing infinite values.The result requires measurability but not integrability; the appendix notes that triangle densities can converge even when the process has infinitely many edges, and gives an example with infinite vertex degrees and zero frequencies for non-bipartite graphs.Source: Appendix D · p. 50

Proof of Theorem 28 (i)

• Graphon processes converge to their generating graphon in the sparse cut metric, for feature spaces of finite or infinite total mass.For infinite-mass spaces, the proof truncates the graphon to a finite-measure region and controls the contribution of edges outside it.Source: Appendix D · pp. 52–53

Proof of Theorem 28 (ii)

• The condition that the sum of inverse feature-space masses diverges is necessary for the convergence asserted in Theorem 28(ii).The proof derives a finite-measure support for an equivalent step graphon and uses it to obtain positive probability that no edges occur; it then begins a coupling construction for the divergent-sum case.Source: Appendix D · pp. 54–55

• The normalized graphon discrepancy is at most o_n(1) + ε, yielding cut distance below 4ε for sufficiently small ε and large n.The proof compares edge sets after rescaling vertex intervals to equal lengths and applies the cut-distance bound for that rescaling.Source: Appendix D · p. 56
• For each fixed feature x, deg(v; eGtn)/t converges almost surely to ∫S W(x,y)dμ(y), while |E(Gn)\E(eGtn)| = o(|E(eGtn)|) and |E(eGtn)| = Θ(t_n^2).The convergence follows from the Kolmogorov 0-1 law.Source: Appendix D · p. 56
• For finite active-feature measures, restricting each graphon to its positive-degree feature set gives equal finite-measure spaces, where the process implication follows from Janson (2013, Theorem 8.10).Almost surely, the graphon processes have no isolated vertices after this restriction.Source: Appendix D · p. 57
• For infinite active-feature measures, a coupling measure on the product feature space lets both graphon processes be sampled from one Poisson point process while preserving their respective feature marginals.The construction uses a Poisson point process on (S1 × S2) × R+ with intensity μ × λ.Source: Appendix D · p. 57
• If the coupled graphon processes agree for all t ≥ 0, their convergence to the generating graphons and the triangle inequality imply that the graphons have cut distance zero.The proof invokes Theorem 28(i) for convergence of each process graphon.Source: Appendix D · p. 57

Appendix E. Compactness

• Uniform regularity of tails is invariant under the stated near-L1 graphon transformations, including bimeasurable bijections and a product-space projection.The equivalence assumes the transformations and convergence conditions specified in Lemma 58.Source: Appendix E · p. 57
• The proof constructs uniformly bounded-measure truncation sets and transfers them between graphon representations while controlling their L1 error.For the projection case, the proof enlarges the truncation set to preserve the measure bound.Source: Appendix E · p. 58
• For non-negative graphons, every cut-Cauchy sequence has uniformly regular tails, completing the compactness argument's converse direction.The proof bounds truncation error on sets of uniformly bounded measure.Source: Appendix E · p. 59
• Uniformly regular tails yield a subsequence converging in the cut metric, constructed through finite-support step graphons and a limiting graphon.The proof uses increasingly refined partitions and obtains the limit through martingale convergence.Source: Appendix E · pp. 60–61

Appendix F. Basic Properties of Metric Convergent Sequences of Graphs

• Uniformly regular tails let each graph be truncated to a bounded-measure set of vertices with arbitrarily small L1 error.The truncation set can be chosen to correspond to vertices, with a common measure bound across the graph family.Source: Appendix F · pp. 61–62
• A sparse graph sequence with uniformly regular tails must retain more than half its stretched graphon mass in a fixed bounded square after suitable vertex ordering.The bounded region is guaranteed by the tail-regularity condition.Source: Appendix F · p. 62
• For dense graphs with convergent edge density bounded away from zero, Cauchy convergence in the stretched or rescaled cut metric is equivalent to convergence of the associated graphons in the cut metric.The equivalence uses the positive limit of the edge density.Source: Appendix F · p. 63
• Dense graph sequences can be Cauchy in one cut metric but not the other, and the appendix gives examples in both directions.One example alternates complete graphs with complete graphs plus isolated vertices; another alternates complete graphs with Erdős–Rényi graphs of edge probability 1/2.Source: Appendix F · p. 63

Appendix G. Exchangeability of Graphon Processes

• Removing vertices of degree at most d from graphs with uniformly regular tails preserves asymptotically all edges.If a nonvanishing edge fraction were removed, the corresponding intervals in the stretched canonical graphon would violate uniform regularity of tails.Source: Appendix G · pp. 63–64
• Joint exchangeability and uniformly regular tails characterize graphon processes with isolated vertices.The converse uses the representation of jointly exchangeable random measures; the forward direction follows from graphon-process properties.Source: Appendix G · pp. 64, 67
• The proof also shows that the representing graphon is integrable almost surely, deriving a contradiction from the assumption that it is not.It splits features according to whether their integrated connection probability is at least one, then uses local finiteness and tail regularity.Source: Appendix G · pp. 65–66
• Under the tail condition, the proof eliminates the extra terms and concludes that the process has a graphon-process representation.It rules out positive-measure supports for the terms corresponding to isolated edges and stars, completing the representation argument.Source: Appendix G · pp. 66–67
• The representation proof identifies extra terms as isolated edges or stars, which exchangeability alone does not rule out.The paper leaves further analysis of these more general exchangeable graphs outside its scope.Source: Appendix G · pp. 65, 67

Appendix H. Left Convergence of Graphon Processes

• For bounded graphons, finite density for a star with k leaves implies finite density for every connected graph with maximal degree at most k.The proof reduces to trees and applies induction after splitting off a star.Source: Appendix H · p. 67
• For a connected graph F with at least three vertices, bounded-degree graphs satisfy h(F, Gn) ≤ |V(Gn)|^(1−|V(F)|/2)d^|V(F)|−1.With degrees bounded by d, this bound tends to zero as the vertex count grows.Source: Appendix H · p. 68
• Adding degree-one vertices to alternating terms of a convergent dense sequence yields stretched cut convergence but not left convergence.For a three-vertex path, the normalized homomorphism count diverges along odd indices while remaining finite along even indices.Source: Appendix H · p. 68
• Left convergence and stretched cut convergence do not imply one another.One constructed sequence converges for the stretched cut metric but is not left convergent; another is left convergent but fails stretched cut convergence.Source: Appendix H · p. 68
• Adding |E(eGn)| isolated edges preserves left convergence but prevents convergence for the stretched cut metric.For connected F with at least three vertices, hom(F, Gn) is unchanged; the sequence fails uniform regularity of tails.Source: Appendix H · p. 68