Sparse graphs using exchangeable random measures

Abstract

Statistical network modeling has focused on representing the graph as a discrete structure, namely the adjacency matrix, and considering the exchangeability of this array. In such cases, the Aldous-Hoover representation theorem (Aldous, 1981;Hoover, 1979} applies and informs us that the graph is necessarily either dense or empty. In this paper, we instead consider representing the graph as a measure on ${\mathbb{R}}_{+}^2$. For the associated definition of exchangeability in this continuous space, we rely on the Kallenberg representation theorem (Kallenberg, 2005). We show that for certain choices of such exchangeable random measures underlying our graph construction, our network process is sparse with power-law degree distribution. In particular, we build on the framework of completely random measures (CRMs) and use the theory associated with such processes to derive important network properties, such as an urn representation for our analysis and network simulation. Our theoretical results are explored empirically and compared to common network models. We then present a Hamiltonian Monte Carlo algorithm for efficient exploration of the posterior distribution and demonstrate that we are able to recover graphs ranging from dense to sparse--and perform associated tests--based on our flexible CRM-based formulation. We explore network properties in a range of real datasets, including Facebook social circles, a political blogosphere, protein networks, citation networks, and world wide web networks, including networks with hundreds of thousands of nodes and millions of edges.

New title. Extended version

References in corpus (28)

• Power-law distributions in empirical data
• Stochastic blockmodels and community structure in networks
• Reaction-diffusion processes and metapopulation models in heterogeneous networks
• Communicability in complex networks
• On the Complexity of Best Arm Identification in Multi-Armed Bandit Models
• Stochastic Gradient Hamiltonian Monte Carlo
• Generating simple random graphs with prescribed degree distribution
• Graph limits and exchangeable random graphs
• Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws
• An $L^p$ theory of sparse graph convergence I: limits, sparse random graph models, and power law distributions
• Poisson Process Partition Calculus with applications to Exchangeable models and Bayesian Nonparametrics
• Sparse exchangeable graphs and their limits via graphon processes
• Infinite Edge Partition Models for Overlapping Community Detection and Link Prediction
• Extreme events on complex networks
• Scale-free networks with an exponent less than two
• Structural Transitions in Dense Networks
• Communicability Graph and Community Structures in Complex Networks
• The Class of Random Graphs Arising from Exchangeable Random Measures
• Asymptotic laws for compositions derived from transformed subordinators
• An Infinite Latent Attribute Model for Network Data
• Scale-free networks with exponent one
• Private Graphon Estimation for Sparse Graphs
• Testing Network Structure Using Relations Between Small Subgraph Probabilities
• Statistical Modelling of Citation Exchange Between Statistics Journals
• Edge exchangeable models for network data
• On edge exchangeable random graphs
• A geometric view on Pearson's correlation coefficient and a generalization of it to non-linear dependencies
• A unified view of generative models for networks: models, methods, opportunities, and challenges

Cited by in corpus (68)

• 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
• Dense Power-law Networks and Simplicial Complexes
• Sampling perspectives on sparse exchangeable graphs
• Bridging the gap between graphs and networks
• On edge exchangeable random graphs
• Random Walk Models of Network Formation and Sequential Monte Carlo Methods for Graphs
• Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities
• Subsampling large graphs and invariance in networks
• Network Representation Using Graph Root Distributions
• On sparsity, power-law and clustering properties of graphex processes
• Consistency of adjacency spectral embedding for the mixed membership stochastic blockmodel
• Multiscale network renormalization: scale-invariance without geometry
• Grand canonical ensembles of sparse networks and Bayesian inference
• Network science Ising states of matter
• Infinite-color randomly reinforced urns with dominant colors
• Preferential Attachment and Vertex Arrival Times
• Graphons and cut metric on sigma-finite measure spaces
• Beyond the Chinese Restaurant and Pitman-Yor processes: Statistical Models with Double Power-law Behavior
• Sparse power-law network model for reliable statistical predictions based on sampled data
• Minimax Rates in Network Analysis: Graphon Estimation, Community Detection and Hypothesis Testing
• A unified construction for series representations and finite approximations of completely random measures
• Statistical physics of exchangeable sparse simple networks, multiplex networks and simplicial complexes
• Bayesian Learning of Graph Substructures
• Multiresolution Tensor Decomposition for Multiple Spatial Passing Networks
• Efficient Estimation for Random Dot Product Graphs via a One-step Procedure
• Nonparametric Modeling of Higher-Order Interactions via Hypergraphons
• An Annotated Graph Model with Differential Degree Heterogeneity for Directed Networks
• Next Waves in Veridical Network Embedding
• Anomalous Edge Detection in Edge Exchangeable Social Network Models
• Node Copying: A Random Graph Model for Effective Graph Sampling
• Random clique covers for graphs with local density and global sparsity
• Priors on exchangeable directed graphs
• Projective, Sparse, and Learnable Latent Position Network Models
• Pseudo-likelihood-based $M$-estimation of random graphs with dependent edges and parameter vectors of increasing dimension
• Inference of a universal social scale and segregation measures using social connectivity kernels
• Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets
• Limit theorems for invariant distributions
• Empirical Risk Minimization and Stochastic Gradient Descent for Relational Data
• A Bayesian model for sparse graphs with flexible degree distribution and overlapping community structure
• Nonnegative Bayesian nonparametric factor models with completely random measures for community detection
• Dissecting Ethereum Blockchain Analytics: What We Learn from Topology and Geometry of Ethereum Graph
• Asymptotic Analysis of Statistical Estimators related to MultiGraphex Processes under Misspecification
• Manifold structure in graph embeddings
• Sampling and Inference for Beta Neutral-to-the-Left Models of Sparse Networks
• A Nonparametric Bayesian Model for Sparse Dynamic Multigraphs
• Local Exchangeability
• Posterior distributions for Hierarchical Spike and Slab Indian Buffet processes
• A correction to Kallenberg's theorem for jointly exchangeable random measures
• Sequential Edge Clustering in Temporal Multigraphs
• Asymptotics of Network Embeddings Learned via Subsampling
• Random Function Priors for Correlation Modeling
• Bayesian mixture models (in)consistency for the number of clusters
• Regular Partitions and Their Use in Structural Pattern Recognition
• Exchangeable modelling of relational data: checking sparsity, train-test splitting, and sparse exchangeable Poisson matrix factorization
• Analysis of large sparse graphs using regular decomposition of graph distance matrices
• Bayesian Model Selection on Random Networks
• Robustness on Networks
• Nondiagonal Mixture of Dirichlet Network Distributions for Analyzing a Stock Ownership Network
• Nonparametric Sparse Tensor Factorization with Hierarchical Gamma Processes
• Asymptotic Behavior of Common Connections in Sparse Random Networks
• A Cluster Model for Growth of Random Trees
• Multiway empirical likelihood
• Generalizing the de Finetti--Hewitt--Savage theorem
• Spiked Laplacian Graphs: Bayesian Community Detection in Heterogeneous Networks
• The Four Point Permutation Test for Latent Block Structure in Incidence Matrices
• Gibbs Partitions, Riemann-Liouville Fractional Operators, Mittag-Leffler Functions, and Fragmentations Derived From Stable Subordinators