Sparse exchangeable graphs and their limits via graphon processes

Abstract

In a recent paper, Caron and Fox suggest a probabilistic model for sparse graphs which are exchangeable when associating each vertex with a time parameter in ${\mathbb{R}}_{+}$. Here we show that by generalizing the classical definition of graphons as functions over probability spaces to functions over $\sigma$-finite measure spaces, we can model a large family of exchangeable graphs, including the Caron-Fox graphs and the traditional exchangeable dense graphs as special cases. Explicitly, modelling the underlying space of features by a $\sigma$-finite measure space $(S,\mathcal{S},\mu )$ and the connection probabilities by an integrable function $W:S\times S\to [0,1]$, we construct a random family $(G_t{)}_{t\ge 0}$ of growing graphs such that the vertices of $G_t$ are given by a Poisson point process on $S$ with intensity $t\mu$, with two points $x,y$ of the point process connected with probability $W(x,y)$. We call such a random family a graphon process. We prove that a graphon process has convergent subgraph frequencies (with possibly infinite limits) and that, in the natural extension of the cut metric to our setting, the sequence converges to the generating graphon. We also show that the underlying graphon is identifiable only as an equivalence class over graphons with cut distance zero. More generally, we study metric convergence for arbitrary (not necessarily random) sequences of graphs, and show that a sequence of graphs has a convergent subsequence if and only if it has a subsequence satisfying a property we call uniform regularity of tails. Finally, we prove that every graphon is equivalent to a graphon on ${\mathbb{R}}_{+}$ equipped with Lebesgue measure.

71 pages, 3 figures

References in corpus (3)

• Graph limits and exchangeable random graphs
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Graphons, cut norm and distance, couplings and rearrangements

Cited by in corpus (27)

• Graphon Filters: Graph Signal Processing in the Limit
• Sampling perspectives on sparse exchangeable graphs
• On edge exchangeable random graphs
• A framework for statistical network modeling
• On the reorderability of node-filtered order complexes
• Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• Graphons: A Nonparametric Method to Model, Estimate, and Design Algorithms for Massive Networks
• On sparsity, power-law and clustering properties of graphex processes
• Pattern Formation in Random Networks Using Graphons
• Grand canonical ensembles of sparse networks and Bayesian inference
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Next Waves in Veridical Network Embedding
• Priors on exchangeable directed graphs
• Random clique covers for graphs with local density and global sparsity
• Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data
• A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure
• Limit theorems for invariant distributions
• Projective, Sparse, and Learnable Latent Position Network Models
• Gradient flows on graphons: existence, convergence, continuity equations
• Manifold structure in graph embeddings
• Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification
• Local Exchangeability
• Asymptotics of Network Embeddings Learned via Subsampling
• Random Geometric Graphs on Euclidean Balls
• The Four Point Permutation Test for Latent Block Structure in Incidence Matrices