Source-linked AI summary
Mixing time of exponential random graphs
Shankar Bhamidi, Guy Bresler, Allan Sly
TL;DR
Exponential random graphs aim to model reciprocal network structure, but sampling them rigorously and efficiently had not been established. The paper analyzes Glauber dynamics across temperature regimes and finds rapid high-temperature mixing versus exponentially slow local-chain mixing at low temperature, while high-temperature samples become asymptotically similar to Erdős-Rényi graphs.
Problem
Exponential random graphs support inference and network analysis through local subgraph counts, yet rigorous mixing-time results for their MCMC samplers were lacking.
Method
The paper analyzes Glauber dynamics and the Gibbs distributions of exponential random graphs across high- and low-temperature regimes.
Results
High temperature has Glauber mixing time Θ(n^2 log n), whereas low temperature has mixing time eΩ(n) for any local dynamics; high-temperature edges are asymptotically independent.
Takeaways & Limitations
Where MCMC sampling is possible, the model lacks its intended reciprocity and is not appreciably different from an Erdős-Rényi random graph.
Takeaways & Limitations
The path-coupling approach can fail in part of the high-temperature regime when sup0≤p≤1 ϕ′(p) > 1.
Abstract
from arXiv · showhide
Exponential random graphs are used extensively in the sociology literature. This model seeks to incorporate in random graphs the notion of reciprocity, that is, the larger than expected number of triangles and other small subgraphs. Sampling from these distributions is crucial for parameter estimation hypothesis testing, and more generally for understanding basic features of the network model itself. In practice sampling is typically carried out using Markov chain Monte Carlo, in particular either the Glauber dynamics or the Metropolis-Hasting procedure. In this paper we characterize the high and low temperature regimes of the exponential random graph model. We establish that in the high temperature regime the mixing time of the Glauber dynamics is $Θ(n^2 \log n)$, where $n$ is the number of vertices in the graph; in contrast, we show that in the low temperature regime the mixing is exponentially slow for any local Markov chain. Our results, moreover, give a rigorous basis for criticisms made of such models. In the high temperature regime, where sampling with MCMC is possible, we show that any finite collection of edges are asymptotically independent; thus, the model does not possess the desired reciprocity property, and is not appreciably different from the Erdős-Rényi random graph.
1 Introduction
The paper rigorously analyzes sampling from exponential random graphs across high- and low-temperature regimes. It shows when local MCMC mixes efficiently and demonstrates that, where sampling is feasible, the model loses its intended reciprocity and resembles Erdős-Rényi graphs.
- Motivation: Exponential random graphs model clustering or reciprocity through elevated prevalence of triangles and other small subgraphs.They are used for statistical inference and for studying how local subgraph structure relates to global network properties.
- Contribution: The paper provides the first rigorous, general analysis of Glauber-dynamics mixing times for exponential random graph distributions.It defines high temperature through unimodality and rapid convergence, and low temperature through multimodality and slow convergence.
- Results: Θ(n^2 log n) is the Glauber-dynamics mixing time in the high-temperature regime.This is the regime where the Gibbs distribution is unimodal and convergence is rapid.
- Results: eΩ(n) is the mixing time in the low-temperature regime for Glauber dynamics and any local dynamics on Gn.The proof uses poor conductance to establish exponentially slow mixing for local chains.
- Results: In high temperature, any finite collection of edges is asymptotically independent, and sampled graphs are weakly pseudorandom like Erdős-Rényi graphs.Consequently, the model does not exhibit the intended reciprocity and is not appreciably different from Erdős-Rényi random graphs.
- Proof strategy: The high-temperature proof combines a burn-in phase reaching good configurations with a path-coupling argument, although basic path coupling alone can fail in part of that regime.The failure occurs when sup0≤p≤1 ϕ′(p) > 1.
2 Proof of the main results
The proofs analyze Glauber dynamics through subgraph-count statistics, drift bounds, coupling, and monotonicity. They establish rapid convergence in the high-temperature phase and exponential slow mixing for local chains in the low-temperature phase.
- Proof strategy: The proof controls subgraph-count statistics NG(X,e) and their expected one-step changes under Glauber dynamics.These statistics are coupled to biased random walks and analyzed through drift and moment-generating-function bounds.
- Burn-in period: After T = cn^2 steps, rmax decreases by δ with probability 1 − e^-Ω(n) under the stated high-temperature conditions.The result applies when the initial statistic lies between p* + µ and the next fixed point minus µ.
- Low-temperature mixing: The same analysis establishes exponentially slow mixing for any local Markov chain in the low-temperature phase.The low-temperature argument uses separation between stable regimes and the resulting obstruction to local-chain convergence.
- High-temperature mixing: Monotone coupling of chains started from the complete and empty graphs bounds the high-temperature mixing time once the two chains coalesce with high probability.The coupling uses the contraction established for configurations differing at one edge.
3 Asymptotic independence of edges and weak pseudo-randomness
In the high-temperature phase, any fixed collection of edge indicators becomes asymptotically independent, and sampled graphs are weakly pseudo-random with probability 1 + o(1).
- Asymptotic independence: For any fixed collection of edges, their indicator variables are asymptotically independent in the high-temperature phase.The indicators are asymptotically distributed as Bernoulli(p*).
- Weak pseudo-randomness: The weak pseudo-randomness conclusion follows from the asymptotic independence of fixed edge collections.The paper relates this property to the equivalent pseudo-random graph conditions.
- Asymptotic independence: The proof estimates joint edge probabilities by conditioning on a high-probability good set where local response statistics are close to p*.Inclusion-exclusion and subgraph configurations yield the required joint-probability bounds.
- Weak pseudo-randomness: With probability 1 + o(1), an exponential random graph is weakly pseudo-random.Weak pseudo-randomness is characterized by equivalent conditions involving induced subgraph counts, eigenvalues, vertex subsets, and cycles.