Graph limits and exchangeable random graphs

Abstract

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.

26 pages

References in corpus (2)

• Convergent Sequences of Dense Graphs I: Subgraph Frequencies, Metric Properties and Testing
• Sparse graphs: metrics and random models

Cited by in corpus (107)

• Matrix estimation by Universal Singular Value Thresholding
• Estimating and understanding exponential random graph models
• Rate-optimal graphon estimation
• Sparse graphs using exchangeable random measures
• Random graphs with a given degree sequence
• Nonparametric graphon estimation
• Consistency under sampling of exponential random graph models
• Sparse exchangeable graphs and their limits via graphon processes
• Maximum lilkelihood estimation in the $\beta$-model
• On exchangeable random variables and the statistics of large graphs and hypergraphs
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Optimal Estimation and Completion of Matrices with Biclustering Structures
• Subsampling bootstrap of count features of networks
• Universally consistent vertex classification for latent positions graphs
• Co-clustering separately exchangeable network data
• A Consistent Histogram Estimator for Exchangeable Graph Models
• Private Graphon Estimation for Sparse Graphs
• Relational Pooling for Graph Representations
• A central limit theorem for an omnibus embedding of multiple random graphs and implications for multiscale network inference
• Generating hierarchial scale free graphs from fractals
• A nonparametric two-sample hypothesis testing problem for random dot product graphs
• Co-clustering for directed graphs: the Stochastic co-Blockmodel and spectral algorithm Di-Sim
• Graphons, cut norm and distance, couplings and rearrangements
• Sampling perspectives on sparse exchangeable graphs
• Computable de Finetti measures
• A General Framework for Bayes Structured Linear Models
• A unified approach to structural limits, and limits of graphs with bounded tree-depth
• On edge exchangeable random graphs
• Weakly interacting oscillators on dense random graphs
• Degree-based network models
• Rates of convergence for multivariate normal approximation with applications to dense graphs and doubly indexed permutation statistics
• Limits of discrete distributions and Gibbs measures on random graphs
• Network cross-validation by edge sampling
• Differential Calculus on Graphon Space
• Subsampling large graphs and invariance in networks
• Iterative Collaborative Filtering for Sparse Matrix Estimation
• On sparsity, power-law and clustering properties of graphex processes
• Multiscale network renormalization: scale-invariance without geometry
• A central limit theorem for scaled eigenvectors of random dot product graphs
• Connectedness in graph limits
• Asymptotic quantization of exponential random graphs
• Tree limits and limits of random trees
• Decomposition of tournament limits
• No additional tournaments are quasirandom-forcing
• Joint Network Topology Inference via a Shared Graphon Model
• EM-Based Smooth Graphon Estimation Using Bayesian and Spline-Based Approaches
• Monotone graph limits and quasimonotone graphs
• Goodness of fit of logistic models for random graphs
• Replica Symmetry Breaking without Replicas
• A note on Fokker-Planck equations and graphons
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Topology reveals universal features for network comparison
• Linear embeddings of graphs and graph limits
• Random Permutations -- A geometric point of view
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• Limit theorems for eigenvectors of the normalized Laplacian for random graphs
• An example of graph limits of growing sequences of random graphs
• On Two Distinct Sources of Nonidentifiability in Latent Position Random Graph Models
• The structure of combinatorial Markov processes
• Dense graph limits under respondent-driven sampling
• Cut distance identifying graphon parameters over weak* limits
• Limits of permutation sequences
• Priors on exchangeable directed graphs
• On the Theoretical Properties of the Network Jackknife
• Invariant measures via inverse limits of finite structures
• Graph limits and hereditary properties
• Limits of Structures and the Example of Tree-Semilattices
• Multicoloured Random Graphs: Constructions and Symmetry
• Searching for Stage-wise Neural Graphs In the Limit
• Projectivity revisited
• Limit theorems for invariant distributions
• Projective, Sparse, and Learnable Latent Position Network Models
• Cut-norm and entropy minimization over weak* limits
• A note on limits of sequences of binary trees
• Out-of-sample Extension for Latent Position Graphs
• On the computability of graphons
• Interval graph limits
• Threshold graph limits and random threshold graphs
• Learning Graphons via Structured Gromov-Wasserstein Barycenters
• Gradient flows on graphons: existence, convergence, continuity equations
• Identifiability and consistency of network inference using the hub model and variants
• Complexity of Nondeterministic Graph Parameter Testing
• Root and community inference on the latent growth process of a network
• Nonparametric Two-Sample Test for Networks Using Joint Graphon Estimation
• From flip processes to dynamical systems on graphons
• Another Conversation with Persi Diaconis
• Nonparametric regression for multiple heterogeneous networks
• Poset limits can be totally ordered
• Dense multigraphon-valued stochastic processes and edge-changing dynamics in the configuration model
• Tournament limits: Degree distributions, score functions and self-converseness
• Distributed Cartesian Power Graph Segmentation for Graphon Estimation
• On the Estimation of Network Complexity: Dimension of Graphons
• On the Density of Transitive Tournaments
• A graphon counter example
• Hoeffding-type decomposition for $U$-statistics on bipartite networks
• The dimension of the feasible region of pattern densities
• Sharp Total Variation Bounds for Finitely Exchangeable Arrays
• Asymptotic Behavior of Common Connections in Sparse Random Networks
• Representations of Aut(M)-Invariant Measures
• A Note on Jointly Modeling Edges and Node Attributes of a Network
• Robustness on Networks
• A sample size heuristic for network scale-up studies
• Exchangeable and Sampling Consistent Distributions on Rooted Binary Trees
• Random Networks, Graphical Models, and Exchangeability
• Multiway empirical likelihood
• A de Finetti-type representation of joint hierarchically exchangeable arrays on directed acyclic graphs
• From Quasirandom graphs to Graph Limits and Graphlets