The Class of Random Graphs Arising from Exchangeable Random Measures

Abstract

We introduce a class of random graphs that we argue meets many of the desiderata one would demand of a model to serve as the foundation for a statistical analysis of real-world networks. The class of random graphs is defined by a probabilistic symmetry: invariance of the distribution of each graph to an arbitrary relabelings of its vertices. In particular, following Caron and Fox, we interpret a symmetric simple point process on ${\mathbb{R}}_{+}^2$ as the edge set of a random graph, and formalize the probabilistic symmetry as joint exchangeability of the point process. We give a representation theorem for the class of random graphs satisfying this symmetry via a straightforward specialization of Kallenberg's representation theorem for jointly exchangeable random measures on ${\mathbb{R}}_{+}^2$. The distribution of every such random graph is characterized by three (potentially random) components: a nonnegative real $I\in {\mathbb{R}}_{+}$, an integrable function $S:{\mathbb{R}}_{+}\to {\mathbb{R}}_{+}$, and a symmetric measurable function $W:{\mathbb{R}}_{+}^2\to [0,1]$ that satisfies several weak integrability conditions. We call the triple $(I,S,W)$ a graphex, in analogy to graphons, which characterize the (dense) exchangeable graphs on $\mathbb{N}$. Indeed, the model we introduce here contains the exchangeable graphs as a special case, as well as the "sparse exchangeable" model of Caron and Fox. We study the structure of these random graphs, and show that they can give rise to interesting structure, including sparse graph sequences. We give explicit equations for expectations of certain graph statistics, as well as the limiting degree distribution. We also show that certain families of graphexes give rise to random graphs that, asymptotically, contain an arbitrarily large fraction of the vertices in a single connected component.

52 pages, 5 figures

References in corpus (4)

• Graph limits and exchangeable random graphs
• Private Graphon Estimation for Sparse Graphs
• Completely random measures for modelling block-structured networks
• Priors on exchangeable directed graphs

Cited by in corpus (37)

• Network Geometry
• Sparse exchangeable graphs and their limits via graphon processes
• Exponential-Family Models of Random Graphs: Inference in Finite-, Super-, and Infinite Population Scenarios
• Edge exchangeable models for network data
• Sampling perspectives on sparse exchangeable graphs
• On edge exchangeable random graphs
• A framework for statistical network modeling
• Using Embeddings to Correct for Unobserved Confounding in Networks
• 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
• Grand canonical ensembles of sparse networks and Bayesian inference
• Graphons and cut metric on sigma-finite measure spaces
• Preferential Attachment and Vertex Arrival Times
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Hierarchical network models for structured exchangeable interaction processes
• Node Copying: A Random Graph Model for Effective Graph Sampling
• Priors on exchangeable directed graphs
• Order Matters: Probabilistic Modeling of Node Sequence for Graph Generation
• Next Waves in Veridical Network Embedding
• Projective, Sparse, and Learnable Latent Position Network Models
• Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data
• Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification
• Manifold structure in graph embeddings
• A Nonparametric Bayesian Model for Sparse Dynamic Multigraphs
• Local Exchangeability
• Classification on Large Networks: A Quantitative Bound via Motifs and Graphons
• Random Function Priors for Correlation Modeling
• Asymptotics of Network Embeddings Learned via Subsampling
• A correction to Kallenberg's theorem for jointly exchangeable random measures
• Stochastic Blockmodels with Edge Information
• Exchangeable modelling of relational data: checking sparsity, train-test splitting, and sparse exchangeable Poisson matrix factorization
• Asymptotic Behavior of Common Connections in Sparse Random Networks
• Robustness on Networks
• Tractably Modelling Dependence in Networks Beyond Exchangeability
• Generalizing the de Finetti--Hewitt--Savage theorem