Source-linked AI summary
Sparse graphs using exchangeable random measures
François Caron, Emily B. Fox
TL;DR
The paper tackles the difficulty of modeling sparse, power-law networks while retaining exchangeability and projectivity. It uses exchangeable random measures built from completely random measures and develops theory, simulation, and scalable inference. Under suitable Lévy measures, the resulting graphs are sparse with power-law degree behavior and can range from dense to sparse.
Problem
Adjacency-matrix exchangeability does not provide the sparse network behavior commonly observed in real-world graphs, while rescaling-based sparse models lack projectivity.
Method
The authors represent graphs as exchangeable point processes on R+^2, construct sociability parameters from CRMs, and use CRM theory for analysis, simulation, and Hamiltonian Monte Carlo inference.
Results
Suitable infinite-activity Lévy measures yield sparse graphs with sub-quadratic edge growth and power-law degree distributions, while the inference methods scale to very large graphs.
Takeaways & Limitations
The CRM formulation provides a projective, exchangeable framework that covers dense and sparse graphs and supports interpretable, scalable network analysis.
Takeaways & Limitations
The current approach does not explicitly model dense spots or community structure, which the authors leave for future research.
Abstract
from arXiv · showhide
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.
1. Introduction
The paper addresses the tension between exchangeable network modeling and the sparsity and power-law behavior observed in real-world graphs. It replaces the adjacency-matrix representation with an exchangeable point process on R+^2, using CRMs to obtain sparse, interpretable, and scalable models.
- Motivation: Classical exchangeable adjacency-matrix models are associated with dense or empty infinite graphs, limiting their ability to represent many real-world networks.Alternative approaches may sacrifice exchangeability or projectivity to obtain sparsity.
- Representation: The paper represents networks as point processes on R+^2 and defines exchangeability through the continuous-space Kallenberg representation theorem.Nodes have locations and sociability parameters, while edges are represented by points in the continuous space.
- CRM construction: Poisson-process sociability parameters form the jumps of a CRM, whose Lévy measure determines whether the resulting graph is sparse or dense.Infinite-activity CRMs yield sparse graphs, whereas finite-activity CRMs yield dense graphs.
- Network properties: Regularly varying infinite-activity CRMs produce sub-quadratic edge growth and power-law degree distributions.The edge count grows below n^a for 1 < a < 2, with a depending on the Lévy measure.
- Inference and scope: The CRM framework supports theoretical analysis, simulation, and an efficient Hamiltonian Monte Carlo procedure that scales to large graphs.The authors report applicability to graphs with hundreds of thousands of nodes and millions of edges.
- Contribution: The framework extends prior CRM-based graph work to bipartite graphs, directed multigraphs, and undirected graphs while proving sparsity under specified conditions.The paper also develops posterior computations that apply to undirected graphs and demonstrates scalability on large real-world networks.
2. Background
The paper reviews exchangeability for sequences, processes, and graph arrays before introducing continuous-space random-measure representations. It also defines completely random measures, whose jumps provide the node-specific weights used in the network models.
- Exchangeability: Aldous-Hoover represents jointly exchangeable adjacency matrices using measurable transformations of shared and pair-specific uniform variables.
- Exchangeability: Exchangeability makes graph probabilities depend on structural features rather than the locations of those features in the network.
- Continuous-space representations: The paper represents networks as point processes on R_+^2 and studies joint exchangeability of the resulting random measures.
- Continuous-space representations: Kallenberg’s theorem characterizes jointly exchangeable random measures through unit-rate Poisson processes, uniform random variables, measurable functions, and independent nonnegative parameters.
- Completely random measures: A completely random measure has independent values on disjoint measurable sets and, with homogeneous increments, is characterized by its Lévy measure ρ.
- Completely random measures: CRM activity determines whether finitely bounded intervals contain finitely or infinitely many jumps, which map directly to graph nodes.
3. Statistical network models
The model assigns sociability weights from a homogeneous CRM and generates directed edge counts with a Poisson process, then converts them into undirected edges. It also supports bipartite graphs, normalized-CRM urn representations, and extensions to interaction types and counts.
- Directed multigraphs: The framework models directed integer-weighted multigraphs, allowing interaction direction, counts, and potentially interaction types.
- Directed multigraphs: Each node receives a positive sociability weight from a homogeneous CRM, and directed edge counts are generated with Poisson(w_iw_j) rates.
- Undirected graphs: An undirected edge is formed whenever at least one directed interaction exists between two nodes, including self-edges under the stated definition.
- Graph restrictions: Graph restrictions to [0, α]^2 produce finite-mean Poisson measures and finite graphs for practical simulation and inference.
- Urn representation: The construction can be rewritten using normalized CRMs, enabling urn-based representations and, for suitable CRMs, exact graph samplers.
- Bipartite graphs: The bipartite extension uses two CRMs for the two node sets and generates cross-set edges from their product measure.
4. General properties and simulation
The CRM construction is jointly exchangeable under Kallenberg’s representation, while sparsity depends on the Lévy intensity and CRM activity. Simulation uses truncation or more efficient Cox-process sampling, with exact urn schemes available for some generalized gamma processes.
- Exchangeability: For any CRM W ∼ CRM(ρ, λ), the constructed undirected graph measure is jointly exchangeable.
- Exchangeability: The Kallenberg formulation gives an analytic representation in which node weights are obtained from a unit-rate Poisson process through the inverse Lévy intensity.
- Sparsity: Finite-activity CRMs produce graphs whose edge counts grow quadratically with α and are dense, whereas infinite-activity CRMs yield sub-quadratic growth and sparse graphs.
- Sparsity: For infinite-activity CRMs, the number of nodes scales superlinearly with α; for finite-activity CRMs, it scales linearly.
- Graph properties: The probability of a connection between disjoint node groups depends on the sums of their sociability weights.
- Simulation: Simulation can truncate CRM weights above ε and then sample edges, while Cox-process sampling avoids considering every possible node pair.
- Simulation: For generalized gamma processes, including the standard gamma process, an urn scheme can sample graphs exactly.
5. Special cases
The generalized gamma process links graph density and degree behavior to its Lévy measure and hyperparameters, while special CRM choices recover classical dense graphs. Its models support sparse growth, power-law degree patterns, and empirical control through σ and τ.
- Generalized gamma process: The generalized gamma process can produce either dense or sparse graphs, with sparsity tuned by the hyperparameter σ.The undirected case is emphasized, though analogous results apply to directed multigraphs and bipartite graphs.
- Poisson process: The compound Poisson choice produces an Erdős-Rényi graph with Poisson-distributed node count and quadratically growing edges.Its connection probability is p = 1 − exp(−2w_0^2).
- Compound Poisson process: The Kallenberg-based compound Poisson representation is either trivially empty or dense, paralleling the classical graphon-based exchangeable construction.The number of nodes is random and Poisson distributed.
- Power-law properties: The GGP directed multigraph has a power-law degree distribution, while undirected empirical results suggest the same property.The degree tail is theoretically power-law for directed graphs; the undirected claim is supported empirically in Figure 6.
- Sparsity: For the GGP, σ < 0 gives dense graphs, while σ ≥ 0 gives sparse graphs asymptotically.The proof uses finite activity for σ < 0 and infinite activity for σ ≥ 0.
- Empirical analysis: Empirical GGP graphs show heavy-tailed or exponentially truncated degree distributions, and larger σ yields sparser network growth.The simulations compare GGP graphs with Erdős-Rényi, preferential attachment, and Lloyd models.
- Hyperparameter interpretation: Increasing σ raises the power-law exponent and produces sparser networks, whereas τ controls exponential tail decay.The parameter α sets the overall network scale, with larger α producing larger networks.
6. Posterior characterization and inference
The inference framework characterizes the CRM posterior by separating observed-node weights from unobserved-node mass, then uses MCMC updates tailored to the GGP. Its computational cost scales with nodes and edges, and experiments report scalability to large networks.
- Posterior characterization: The posterior targets sociability weights, the restriction value α, and GGP hyperparameters σ and τ.For simple graphs, missing directed edge counts are imputed with latent variables.
- Empirical comparison: Figure 6 compares GGP degree distributions, degree-one nodes, and edge growth with Erdős-Rényi, preferential attachment, and Lloyd models.The GGP edge count grows o(n^2), unlike the Θ(n^2) growth of the dense Erdős-Rényi and Lloyd models.
- Posterior characterization: The conditional CRM given the directed graph decomposes into observed-node weights and a residual measure for nodes without observed connections.The residual component is summarized by its total mass w* and has random weights and atoms.
- Posterior characterization: The conditional representation uses fixed locations for observed nodes and Poisson-Kingman-distributed normalized residual weights conditional on w*.The normalized weights and residual locations are part of the CRM decomposition used for posterior characterization.
- MCMC inference: The sampler updates node weights with Hamiltonian Monte Carlo, total mass and hyperparameters with Metropolis-Hastings, and undirected latent counts separately.The update sequence is embedded within a Gibbs framework.
- Scalability: The sampler has overall complexity O(niter(LN_α + N^(e)_α)) and roughly linear bottlenecks in nodes and edges.The edge-count update can be parallelized over edges.
- Scalability: The algorithm is reported to scale well to networks with hundreds of thousands of nodes and edges.Further scaling of HMC is suggested through methods designed for larger collections of nodes and edges.
- GGP specialization: The GGP sampler uses exponentially tilted stable distributions for exact or specialized sampling of the residual total mass.The total mass w* is sampled through proposals that avoid direct evaluation of its generally unavailable density.
7. Experiments
Experiments assess parameter recovery, sparsity testing, and posterior predictive fit on simulated and real-world graphs. The CRM-based approach is evaluated across graphs spanning sparse and dense regimes.
- Simulated data: 13,995 nodes and 76,605 edges were sampled from a sparse GGP undirected graph with α = 300, σ = 0.5, and τ = 1.Three MCMC chains were run for 40,000 iterations each.
- Simulated data: Posterior intervals accurately recover sociability parameters for both high-degree and low-degree nodes in the simulated GGP graph.The high-degree parameters are shown directly, while low-degree parameters are represented on the log scale.
- Simulated data: The Erdős-Rényi test graph contains 1,000 nodes and 5,058 edges, providing a dense-regime evaluation of the model.For this regime, transformed parameters are more informative because σ and τ are only weakly identifiable.
- Testing for sparsity of real-world graphs: The sparsity test evaluates H0: σ < 0 against H1: σ ≥ 0 using posterior Pr(H1|z) and MCMC output.The experiments use a GGP-based graph model with parameters α, σ, and τ.
- Testing for sparsity of real-world graphs: USairport, Enron, and www are clearly inferred as sparse, while smaller networks often lack evidence of sparsity and internet remains inconclusive.The datasets range from a few hundred nodes and edges to a million.
- Testing for sparsity of real-world graphs: Dense subgraphs or spots can weaken sparsity evidence because the current approach does not explicitly model such structure.The authors identify modeling dense spots as a direction for future research.
- Testing for sparsity of real-world graphs: Posterior predictive degree distributions generally fit the observed distributions, but slightly underestimate high-degree tails in the largest networks.The framework captures power-law behavior with a possible exponential cutoff, but does not explicitly model cutoff effects or dense spots.
8. Discussion
The discussion places the CRM network model within Bayesian nonparametric and classical graph-modeling literature. It emphasizes scalable sparse-graph modeling while identifying extensions such as community structure and node attributes.
- Related models: Existing Bayesian nonparametric network models fit the Aldous-Hoover framework and therefore produce dense graphs.This motivates alternatives that retain flexible latent modeling while supporting sparse networks.
- Related models: The model shares sociability-based structure with Poissonian multigraph and degree-corrected random graph models.When sociability parameters are i.i.d., the degree-corrected model yields an exchangeable matrix and a dense graph.
- Related models: Unlike latent-space models, this framework does not use node positions to determine edge probabilities, although inhomogeneous CRMs could introduce location dependence.The proposed extension would support location-dependent connections.
- Related models: The urn construction connects the model to the configuration model, which generates graphs from specified degree sequences using paired stubs.Simple graphs can be obtained by discarding multiple edges and self-loops or repeating the sampling.
- Discussion: The authors present the approach as a fully generative and projective sparse-graph model with an exchangeability notion supporting scalable estimation.The sampler is described as scaling to large real-world networks.
- Discussion: The framework is positioned as a building block for future incorporation of community structure and node attributes.The discussion also notes asymptotic notation and growth-rate terminology used in the theoretical analysis.
A.2. Proof of Theorems 5, 6 and 7 in the finite-activity case
The finite-activity proof analyzes the point-process construction through Poisson-process representations and asymptotic growth arguments. It derives graph quantities using laws of large numbers and theorem-based limits.
- Finite-activity construction: A finite-activity CRM is represented using a homogeneous Poisson process of rate T for the node locations.The point process construction then samples connections using the CRM-induced mechanism.
- Asymptotic analysis: The proof studies the restriction Jα = Π ∩ [0, α] as α grows and applies almost-sure asymptotic arguments.The number of Poisson points diverges almost surely as α → ∞.
- Asymptotic analysis: A law of large numbers for V-statistics is used to establish limits involving the connection kernel W.The argument assumes the relevant integral of W is finite.
- Asymptotic analysis: The proof combines theorem-based limits with Equation (56) to derive the asymptotic behavior of N(e).The resulting relation is stated as an almost-sure conclusion.
A.3. Proof of Theorem 6 in the infinite-activity case
The infinite-activity proof converts the point process into a jointly exchangeable binary adjacency matrix and combines CRM identities with regular-variation assumptions. These steps yield the stated asymptotic conclusion.
- Graph representation: The graph adjacency indicators are defined by whether the point process places mass in unit-square cells of R_+^2.This converts the continuous-space point process into a binary matrix.
- Graph representation: Joint exchangeability of the point process implies joint exchangeability of the resulting binary adjacency matrix.The proof invokes the relevant exchangeability representation theorem.
- CRM decomposition: The argument partitions R_+ into disjoint sets and uses complete randomness of the CRM to combine contributions across the partition.The Laplace exponent appears in the corresponding CRM calculation.
- Asymptotic analysis: The proof combines Equation (69) with Theorem 17 and Equation (65) to obtain the target asymptotic relation.The intermediate result is presented as a conclusion after these theorem applications.
- Asymptotic analysis: Regular variation assumes x↓0 ∼ ℓ(1/x)x^-σ, with ℓ slowly varying, leading to ψ(t) = Ω(t^σ) as t → ∞.The slowly varying function satisfies the stated scaling and positivity conditions.
Appendix B: Technical lemmas
This appendix develops technical lemmas using exchangeability, U- and V-statistics, martingales, convergence arguments, and Tauberian results. It also establishes theorem-level properties for random measures and derives bounds for the gamma-process case.
- The appendix invokes the Aldous-Hoover representation for infinitely exchangeable binary symmetric arrays.
- Strong laws for U- and V-statistics support asymptotic arguments involving exchangeable random variables and measurable symmetric functions.
- A martingale construction, square-integrability arguments, and Kronecker’s lemma establish almost-sure convergence statements.
- Theorem 17 defines an integer-valued random measure from an almost surely positive random measure.
- Tauberian arguments relate Levy intensity tails and Laplace exponents under slowly varying-function conditions.
- Gamma-process bounds: The gamma-process analysis combines Jensen, Markov, and Chebyshev-type inequalities to derive bounds involving α and D*α.
C.2. Proof of Theorem 9
The proof uses a conditional Poisson construction and normalized generalized gamma-process sampling to analyze cluster counts in the directed graph. These counts correspond to nodes with specified incoming and outgoing edge totals.
- The conditional Poisson construction yields infinitely many points in bounded intervals as α tends to infinity.
- The resulting samples are analyzed using asymptotic results for normalized generalized gamma processes.
- Nα,j counts clusters of size j, corresponding in the directed graph to nodes with j incoming or outgoing edges.Self-edges count twice for a given node.
- As α tends to infinity, the normalized cluster counts converge almost surely to pσ,j = σΓ(j −σ)/(Γ(1 −σ)Γ(j + 1)).
Appendix D: Proofs of results on posterior characterization
These proofs derive posterior characterizations using generalized Palm formulas and Poisson random measures, then describe sampler updates for latent weights, parameters, and edge counts.
- Posterior characterization: The generalized Palm formula is established for Poisson random measures with non-atomic mean measures and disjointly supported functions.
- Posterior characterization: The conditional Laplace functional of Wα given Dα is derived by representing Wα through a Poisson random measure on (0, ∞) × [0, α].
- Posterior characterization: Applying the Palm formula to the numerator and setting f = 0 for the denominator yields the posterior expression.
- Sampling algorithms: The undirected sampler updates node weights with Hamiltonian Monte Carlo, model parameters with Metropolis-Hastings, and latent counts using truncated Poisson or Metropolis-Hastings steps.
- Sampling algorithms: The proposal for w* uses exponential tilting so intractable density terms cancel in the Metropolis-Hastings ratio.
- Sampling algorithms: The bipartite sampler alternates parameter proposals, weight updates, latent-count sampling, and additional parameter and weight proposals.