Source-linked AI summary
Exponential random graph models with soft clique constraints
Yasmin Tousinejad, Vera Koponen
TL;DR
The paper asks how soft penalties on clique counts shape dense random graphs when violating graphs remain possible. Using graphon methods, it analyzes exponential random graph models with one or several weighted clique penalties and proves that the limiting structure is balanced (r−1)-partite, largely independent of positive weights, subject to stated iterated-limit and concentration-scope boundaries.
Problem
The paper investigates the structural properties of exponential random graph models that penalize r-cliques without excluding graphs containing them.
Method
The paper uses graphons to analyze dense-graph limits and applies the framework to models with one or several weighted clique penalties.
Results
Positive clique penalties yield asymptotically balanced (r−1)-partite graphs with cross-part edge density near 1/2, sparse within-part edges, and structure independent of positive weights.
Takeaways & Limitations
For multiple clique sizes, the asymptotic behavior is determined by the smallest clique size, while fixed induced subgraphs converge to a corresponding stochastic block model.
Takeaways & Limitations
Some arguments concern an iterated limit with n tending to infinity before an auxiliary parameter L, and fixed-weight concentration is not uniform in L.
Abstract
from arXiv · showhide
Let $r\geq3$ be fixed, and let $\mathbf{G}_n$ be the set of all simple graphs with vertex set $[n]=\{1,\ldots,n\}$. We consider an exponential random graph model which gives higher probability to $G \in \mathbf{G}_n$ than to $H \in \mathbf{G}_n$ if $G$ has fewer $r$-cliques than $H$. But all graphs in $\mathbf{G}_n$ have positive probability. The degree to which graphs with fewer $r$-cliques are given higher probability is determined by a positive weight $w$. We prove that, asymptotically almost surely as $n \to \infty$, a random graph from $\mathbf{G}_n$ has a vertex partition into $r-1$ parts of roughly equal size, the density of edges between the parts is close to $1/2$, and for every $\varepsilon > 0$ the density of edges within any part is less than $\varepsilon$. The asymptotic structural properties are independent of the weight $w$ as long as it is positive. We also extend the result to the context of several clique sizes, each one with its own weight.
1. Introduction
The paper studies soft clique constraints in exponential random graph models, where graphs with more r-cliques are less likely but remain possible. It shows that positive clique penalties yield asymptotically balanced (r−1)-partite structure, with sparse within-part edges and cross-part density near 1/2, and extends this behavior to multiple clique sizes.
- Model: Soft constraints penalize graphs with more r-cliques while assigning positive probability to every graph.This contrasts with hard-constraint models, which assign probability zero to violating graphs.
- Main result: With probability tending to 1, vertices can be partitioned into r−1 parts of size close to n/(r−1).
- Main result: The density of edges between distinct parts is close to 1/2, while within-part edge density is below every fixed ε for sufficiently large n.
- Main result: The asymptotic structure is independent of the positive weight w used to penalize r-cliques.
- Extension: Fixed induced subgraphs converge to a stochastic block model with r−1 uniformly assigned classes, no within-class edges, and cross-class edges included independently with probability 1/2.
- Extension: For multiple clique sizes with positive weights, the asymptotic behavior is determined by the smallest clique size.
2. The probability model and the main results
The paper defines a soft-clique ERGM that weights graphs according to the number of non-clique r-tuples, then proves that typical graphs exhibit balanced (r−1)-partite structure with sparse within-part edges and near-half between-part densities.
- Probability model: The model assigns unnormalized mass through the number of ordered r-tuples that do not form an r-clique, allowing tuples with repeated vertices.The resulting probability measure favors graphs with fewer r-cliques while assigning positive probability to every graph.
- Probability model: Counting only pairwise-distinct ordered tuples yields exactly the same probability measure because the convention change contributes a graph-independent factor.The factor changes the partition function but disappears upon normalization.
- Probability model: The model is an exponential random graph model in which a positive parameter rewards larger values of the non-clique tuple statistic.The paper identifies the distribution with an ERGM and with a Markov logic network containing one soft constraint.
- Main results: The partition has balanced part sizes, between-part edge densities close to 1/2, and total within-part edge density at most ε.Deleting all edges internal to the parts produces a q-partite graph, and the associated balanced block-graphon family has zero diagonal blocks and one-half off-diagonal blocks.
- Relation to prior work: The paper notes that bounded-statistic ERGM results cited from prior work do not apply because the maximum non-clique tuple statistic grows unboundedly with n.For an (r−1)-partite graph, the statistic equals n^r, so its maximum is unbounded.
3. Graphon preliminaries
This section introduces graphons as measurable symmetric limit objects, empirical graphons for finite graphs, and homomorphism densities for cliques. It develops cut-based comparison tools and proves that clique density is continuous in cut distance.
- Basic definitions: Graphons are measurable symmetric functions on [0, 1]^2, while empirical graphons encode a finite graph’s adjacency matrix on equal-sized rectangles.Empirical graphons take value a_ij on the rectangle I_i × I_j and vanish on diagonal rectangles because a_ii = 0.
- Homomorphism densities: The homomorphism density t(K_r, W) averages the product of W(x_i, x_j) over all clique-edge pairs and vertex variables.Each clique vertex receives one variable, each edge contributes one graphon factor, and the integral averages over [0, 1]^r.
- Cut distance: Cut norm and cut distance compare graphons through measurable subsets and measure-preserving relabelings.Relabeling preserves cut norm, and the induced cut distance is a metric on graphons modulo zero-distance equivalence.
- Cut distance: Graphons at zero cut distance represent the same graph limit, even when no single measure-preserving bijection makes them almost everywhere equal.The characterization may use measure-preserving maps that are not bijections.
- Clique-density continuity: Clique density is Lipschitz in cut distance, so the map W 7→t(K_r, W) is continuous.The proof compares clique-product factors one edge at a time and estimates the resulting integrals using Cauchy–Schwarz-type bounds.
4. Entropy maximizers and stability
The section identifies balanced q-partite graphons, with q=r−1, as the entropy maximizers under zero Kr-density and establishes stability away from this maximizer class.
- Entropy maximizers: Balanced q-partite graphons maximize entropy among graphons with t(Kr,W)=0.Here q=r−1, and the maximizers are characterized explicitly.
- Balanced structure: For {0,1}-valued graphons with zero Kr-density, the support is constrained by the graphon Turán theorem to be q-partite.The equality case yields vanishing diagonal blocks.
- Entropy maximizers: The maximizer set is represented, modulo graphon equivalence, by the singleton eB⋆q.Equality holds exactly for graphons in this reduced maximizer class.
- Balanced structure: The canonical maximizers have zero values on diagonal blocks and value 1/2 on off-diagonal blocks.The corresponding blocks are balanced, so each has measure 1/q.
- Stability: Graphs or graphons remaining a fixed cut distance from the maximizer class incur a strict entropy loss.This strict loss supports exponential concentration around the balanced maximizer family.
5. Proof of Theorem 2.7
The proof combines clique-density estimates, graphon entropy bounds, and labeled-graph counting to control the fixed-weight model and prepare the structural theorem.
- Clique-density control: For fixed positive w and r≥3, the empirical Kr-homomorphism density converges to zero in probability.A positive clique density receives an exponent penalty of order n^r, dominating the exp(O(n^2)) graph count.
- Clique-density control: Graphs with any fixed positive Kr-density have negligible total reduced mass on the n^2 scale.Thus the dominant contribution comes from graphs with small empirical Kr-density.
- Counting transfer: Cut-closed graphon families yield labeled-graph counting bounds governed by their maximal entropy.The argument transfers large-deviation upper bounds from reduced graphon space to finite graphs.
- Graphon framework: The proof uses compactness and cut-distance continuity for clique density, edge density, and entropy-related functionals.These properties allow subsequential graphon limits to inherit the relevant constraints.
2. Hence
The proof establishes the free-energy limit and then derives exponential concentration near balanced (r−1)-partite graphons, while addressing the nonuniformity of fixed-penalty estimates.
- Free-energy limit: The lower bound comes from balanced q-partite graphs, which are Kr-free and contribute reduced mass 1.Here q=r−1, so arbitrary between-part edges produce no copy of Kr.
- Free-energy limit: The auxiliary fixed-L model is analyzed by maximizing Ent(W)−L t(Kr,W), followed by L→∞.This identifies the limiting constrained variational value.
- Free-energy limit: The upper and lower bounds agree, yielding the claimed reduced free-energy limit.The upper bound retains only the entropy contribution near zero clique density.
- Diagonal sequence: Fixed-L concentration is not uniform in L, so the proof establishes a direct uniform estimate along the diagonal sequence L_n=w n^(r−2).The parameters n and L_n grow together, preventing direct use of fixed-coefficient bounds.
- Exponential concentration: For every ε>0, graphs outside the required balanced structure have probability at most exp(−c n^2) for sufficiently large n.The constant c depends on ε and r, while the threshold may also depend on w.
6. Examples and consequences
The consequences include a stochastic block-model limit for fixed induced subgraphs, explicit clique-density behavior, exponential non-colorability bounds, and an extension to multiple clique penalties.
- Stochastic block-model limit: Fixed induced subgraphs converge in distribution to a stochastic block model with q=r−1 latent classes.Labels are sampled independently and uniformly, with edge probabilities 0 within classes and 1/2 between classes.
- Stochastic block-model limit: The limiting model has pairwise independent edge indicators but dependent triangle indicators, so it is not Erdős-Rényi for m≥3.The dependence appears at the level of triples of edges forming a triangle.
- Clique densities: Every fixed clique Ks with 2≤s≤r−1 has positive limiting density, whereas every fixed clique Ks with s≥r has limiting density zero.For r=4, a positive proportion of triples form triangles even though K4 density tends to zero.
- Colorability: For every k<r−1, the probability that the sampled graph is k-colorable decays exponentially in n^2.In particular, for r≥4, the probability of being (r−2)-partite tends to zero exponentially.
- Several clique penalties: With several clique penalties, the smallest positively weighted clique determines the limiting partition structure.Once r and its positive weight are fixed, the relevant concentration constants are independent of larger clique sizes and their weights.