Source-linked AI summary
Graph limits and exchangeable random graphs
Persi Diaconis, Svante Janson
TL;DR
The paper addresses how deFinetti-style representation theorems for exchangeable arrays relate to graph-limit theory. It develops probabilistic formulations and proves correspondences between exchangeable random graphs and proper graph limits. The framework also covers graph, bipartite, and directed settings, while recognizing non-uniqueness in representing functions.
Problem
Two-dimensional exchangeability and large-graph convergence require a common framework connecting Aldous–Hoover–Kallenberg representations with graph limits.
Method
The paper translates graph convergence into probability and compares graph-limit objects with exchangeable-array constructions based on latent variables and W.
Results
Theorem 5.3 gives a one-to-one correspondence between distributions of random proper graph limits and exchangeable random graphs.
Takeaways & Limitations
Symmetric, separately permuted, and directed exchangeable-array constructions correspond respectively to graph, bipartite, and directed graph-limit theories.
Takeaways & Limitations
Representing W is non-unique under measure-preserving transformations, and the transformation relation need not be symmetric.
Abstract
from arXiv · showhide
We develop a clear connection between deFinetti's theorem for exchangeable arrays (work of Aldous--Hoover--Kallenberg) and the emerging area of graph limits (work of Lovasz and many coauthors). Along the way, we translate the graph theory into more classical probability.
1. Introduction
The paper connects exchangeable-array representation theorems with graph-limit theory, translating graph convergence into probability and making correspondences precise across undirected, bipartite, and directed settings.
- Motivation: The paper links deFinetti’s theory of partial exchangeability to the limiting theory of large graphs.It recalls exchangeable arrays, outlines graph limits, and develops the connection between them.
- Exchangeable arrays: Aldous–Hoover represents separately exchangeable binary arrays as mixtures generated from independent latent variables and a function W.The construction samples independent uniform Ui and Vj values and uses W(Ui,Vj) as Bernoulli probabilities.
- Graph limits: Graph limits describe convergent graph sequences through limiting objects that approximate graph properties and support graph testing and parameter estimation.The theory applies to dense graphs and includes practical approximation by fixed-size graphs.
- Main connection: Symmetric W corresponds to graph limits, general W to bipartite limits, and nonsymmetric W under one permutation to directed graphs.The paper also discusses non-uniqueness of representing W and reciprocal contributions between graph theory and exchangeability theory.
- Main connection: The paper gives a one-to-one correspondence between infinite exchangeable random graphs and distributions on proper graph limits.Proper graph limits correspond to extreme points among distributions of exchangeable random graphs.
2. Definitions and basic properties
This section defines graph convergence using homomorphism densities and embeds finite graphs into compact spaces whose closures contain proper graph limits.
- Graph functionals: For graphs F and G, t(F,G) is the proportion of vertex mappings from F to G that are graph homomorphisms.Equivalent injective and induced densities are introduced, and asymptotically they contain the same information as t.
- Convergence: A graph sequence converges when t(F,Gn) converges for every fixed graph F.This is equivalent to convergence of the associated functional vectors in a compact metric space.
- Limit space: The closure U* of the embedded graph space is compact and contains limit objects of graph sequences.Proper graph limits are the limits of sequences whose vertex counts tend to infinity.
- Identification: The embedding based on homomorphism densities is not injective, so distinct finite graphs can have the same image.Complete bipartite graphs Kn,n provide an example of this identification.
- Alternative embeddings: An augmented embedding τ+ restores injectivity by adding a coordinate that distinguishes graphs with the same density data.The resulting closure avoids identifying non-isomorphic finite graphs of different orders with one another or with limit objects.
3. Convergence of random graphs
For random graph sequences with growing order, convergence can be characterized equivalently through graph-density vectors, finite families of densities, individual densities, or their expectations.
- Equivalent criteria: When vertex counts tend to infinity, convergence in the compact graph-limit space is equivalent to convergence of the density coordinates.The assumptions include growth in probability for the random graph orders.
- Equivalent criteria: Theorem 3.1 equates convergence of random graphs through joint distributions, individual density distributions, and expected homomorphism densities.The same equivalences hold with injective or induced densities replacing t.
- Modes of convergence: Almost-sure convergence of random graphs is equivalent to almost-sure convergence of t(F,Gn) for every fixed graph F.This specializes the general convergence framework to a non-random limiting graph.
- Moment characterization: The distribution of a random proper graph limit is uniquely determined by the expectations E t(F,Γ) over all finite graphs F.Expected induced densities determine the same distribution through their relation to homomorphism densities.
4. Convergence to infinite graphs
The section relates graph-limit convergence to convergence of finite restrictions of randomly labelled graphs toward an exchangeable infinite graph.
- Infinite graphs: Infinite labelled graphs are represented as edge subsets on the vertex set N and equipped with the product topology.This makes the space of infinite labelled graphs compact and metrizable.
- Finite restrictions: Finite graphs can be embedded into the infinite space by adding isolated vertices, while infinite graphs yield induced restrictions H|[n].Random relabelling provides the finite-to-infinite comparison used in the convergence arguments.
- Restriction limits: Theorem 4.1 identifies finite restriction limits through P(H|[k]=F)=E tind(F,Γ) for every F in Lk.Under the stated assumptions, the limiting graph-limit object Γ is proper almost surely.
- Restriction limits: Convergence of sampled finite restrictions is tied to induced subgraph densities computed from sampling vertices without replacement.The finite restriction distribution converges to the restriction law of the infinite graph.
5. Exchangeable random graphs
This section establishes exchangeable infinite random graphs and connects their distributions to graph-limit objects. It characterizes extremality through independence and tail-triviality.
- Definition: An exchangeable infinite graph has a distribution invariant under every permutation of its vertices.Equivalently, its edge-indicator array is jointly exchangeable.
- Correspondence: The limiting graph H is exchangeable, so its finite restrictions inherit permutation-invariant distributions.The construction also identifies convergence of finite random graphs with the exchangeable infinite-graph limit.
- Correspondence: Theorem 5.3 gives a one-to-one correspondence between distributions of random graph limits and distributions of exchangeable random infinite graphs.Finite restrictions converge to the corresponding random graph-limit object, and the limiting distribution determines the infinite graph.
- Extreme points: Theorem 5.5 characterizes extreme exchangeable distributions by equivalent independence conditions for disjoint finite vertex sets and finite-versus-tail restrictions.It also identifies extremality with triviality of the tail σ-field.
- Extreme points: For an extreme distribution, the corresponding graph-limit object is non-random, whereas non-extremality permits a random limit object.The proof shows that all homomorphism densities of the random limit have zero variance in the extreme case.
6. Representations of graph limits and exchangeable graphs
This section makes explicit that graph-limit representations and Aldous–Hoover representations describe the same exchangeable-graph objects. Symmetric measurable functions generate exchangeable graphs whose finite restrictions converge almost surely to graph limits.
- Connection: The paper’s main connection identifies the representation theorems of Aldous–Hoover and Lovász–Szegedy as equivalent characterizations.The correspondence is mediated by the paper’s results on exchangeable random graphs and graph limits.
- Graphon representation: A symmetric measurable function W on [0,1]^2 generates an infinite random graph by sampling i.i.d. latent variables and conditionally independent edges.The finite graph G(n, W) is the restriction to the first n sampled vertices.
- Graphon representation: Every exchangeable infinite random graph is a mixture of graphs G(∞, W), equivalently generated using a random W.This is the Aldous–Hoover representation in the symmetric setting.
- Limits: For deterministic W, G(n, W) converges almost surely to a graph-limit object ΓW, with subgraph densities represented by integrals of products of W.The resulting ΓW is the graph-limit counterpart of the exchangeable random graph generated by W.
- Representation equivalence: Representations by W are not unique, and identifying functions at cut-distance zero yields a compact metric quotient corresponding bijectively to graph limits.More general probability spaces can represent the same limit objects without producing new limits.
7. Non-uniqueness
This section characterizes when two functions represent the same graph limit or exchangeable random graph. Equality is equivalent across graph limits, subgraph densities, finite and infinite graph distributions, measure-preserving transformations, and cut-distance.
- Source of non-uniqueness: Non-uniqueness is complicated by the fact that a measure-preserving map need not be bijective, making the relation W′ = W ◦ ϕ non-symmetric.The paper gives one- and two-dimensional examples where the reverse measure-preserving transformation need not exist.
- Equivalent criteria: Theorem 7.1 states that equality of graph limits is equivalent to equality of every graph density and equality in distribution of the associated exchangeable graphs.The equivalence includes both infinite graphs and all finite graphs G(n, W).
- Equivalent criteria: The theorem also includes representation criteria using measure-preserving maps and an auxiliary-variable formulation.These probabilistic criteria connect the non-uniqueness of graph-limit functions with exchangeable-array equivalence.
- Conclusion: The equivalence between the cut-distance criterion and the exchangeable-array criteria completes the correspondence between graph-limit and probabilistic notions of representation.The proof derives the remaining equivalences using the exchangeable-array representation theorem and the graph-limit cut-distance result.
- Source of non-uniqueness: Measure-preserving changes of variables preserve the generated graph distribution and therefore the graph limit.If X_i are i.i.d. uniform, then applying a measure-preserving map preserves their joint distribution.
8. Bipartite graphs
The bipartite extension establishes graph-limit convergence criteria and connects bipartite limits with exchangeable random infinite bipartite graphs. It also characterizes these objects through measurable graphon representations and identifies additional degenerate limits outside the main setting.
- Definitions: A bipartite graph has two explicit vertex sets, with edges forming a subset of their Cartesian product; labelled and unlabelled versions are considered.
- Degenerate limits: When one bipartition remains fixed while the other grows, additional degenerate limit objects arise; the simplest one-vertex case identifies such limits with [0,1] via edge proportions.These degenerate limits are explicitly excluded from further consideration in the section.
- Graph limits: Convergence of finite bipartite graphs with both parts growing is equivalent to convergence of homomorphism, injective, and induced subgraph densities.The limiting object lies in B∞∞, and the three density limits are represented by the corresponding functions evaluated at that object.
- Random convergence: For random bipartite graphs, convergence of finite families of densities, individual densities, and their expectations provides equivalent distributional descriptions, likewise for injective and induced densities.
- Exchangeability: Distributions of bipartite graph limits correspond one-to-one with distributions of exchangeable random infinite bipartite graphs, while extreme points correspond to extremal exchangeable distributions.The distribution of a random limit is uniquely determined by the expectations of its homomorphism densities.
- Representations: Every exchangeable infinite random bipartite graph is a mixture of graphon-generated models using independent latent variables on the two vertex classes and conditionally independent edges.The representing graphon need not be unique, and the construction yields the bipartite version of the Lovász–Szegedy characterization.
9. Directed graphs
The directed-graph extension adapts graph limits and exchangeability to loops and dependent opposite-direction edges. Its representation theorem uses either a quintuple of measurable functions or an equivalent quadruple-plus-loop-probability formulation.
- Definitions: Directed graphs permit loops and encode edges as an arbitrary zero–one matrix; the graph-limit definitions and earlier results extend with mainly notational changes.
- Representations: A single graphon is insufficient for directed graphs because opposite directed edges may both occur and be dependent, so several measurable functions are required.
- Representations: The construction samples i.i.d. latent variables, assigns loops through a measurable function, and samples each ordered edge pair conditionally according to joint probabilities Wαβ.An alternative construction separates loop indicators as independent Bernoulli variables with parameter p.
- Graph limits: For every directed graphon representation, the finite restrictions G(n,W) and G(n,W,p) converge almost surely to the corresponding directed graph limits.
- Main theorem: Every exchangeable random infinite directed graph is a mixture of G(∞,W), equivalently of G(∞,W,p) with random representation parameters.Conversely, every directed graph limit is represented by some W in W5 or by some W in W4 together with p.
- Connection to de Finetti: The directed representation recovers de Finetti’s theorem through the loop indicators, which form a binary exchangeable sequence represented as a mixture of i.i.d. Bernoulli variables.