Abstract
Let r≥3 be fixed, and let Gn be the set of all simple graphs with vertex set [n]={1,…,n}. We consider an exponential random graph model which gives higher probability to G∈Gn than to H∈Gn if G has fewer r-cliques than H. But all graphs in Gn 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→∞, a random graph from Gn 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 ε>0 the density of edges within any part is less than ε. 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.
Explore similar work
May 22, 2026cs.LG
How network structure determines function is a fundamental question, and it can be investigated by graph ensembles with precisely controlled structural properties. Canonical approaches, formulated as exponential random graph models (ERGMs), enforce constraints only in expectation, allowing individual realizations to fluctuate around the target. Conversely, microcanonical ensembles impose hard constraints exactly, but practical sampling methods beyond fixing the degree sequence have remained out of reach. Here we introduce the Deep Microcanonical Graph Generator (DMGG), a reinforcement learning (RL) framework that transforms any given graph through degree-preserving rewirings to exactly reach a prescribed assortativity, which characterizes the degree--degree correlation of adjacent nodes. Instead of relying on the entropically dominated Metropolis--Hastings dynamics of the ERGM, DMGG employs a policy-guided search that maximally alters the joint-degree matrix. This eliminates exhaustive parameter tuning and accelerates generation by at least an order of magnitude while preserving configurational diversity. As DMGG generalizes across various graph sizes, sparsities, and topologies, it provides exact null models that allow for the quantitative isolation of secondary observables, such as the clustering coefficient. These results establish RL as a practical and powerful paradigm for generating hard-constrained graphs, opening avenues to investigate structure-function relationships free from ensemble artifacts.
Hoyun Choi, Junghyo Jo, Deok-Sun Lee
Oct 20, 2025cs.DS
Novel Markov Chain Monte Carlo (MCMC) methods have enabled the generation of large ensembles of redistricting plans modeled as a graph partitioning problem. However, existing algorithms such as Reversible Recombination (RevReCom) and Metropolized Forest Recombination (MFR) have strong preferences for distributions related to the spanning tree measure. In this paper we introduce the Marked Edge Walk (MEW), a novel Markov chain proposal for sampling from the space of graph partitions. The walk operates on the space of spanning trees with marked edges, allowing for calculable transition probabilities for use in the Metropolis-Hastings algorithm. Empirical results on real-world dual graphs show convergence under a broad class of target distributions less constrained by spanning tree counts, including policy-based distributions, such as competitiveness on New Hampshire that are independent of spanning trees, and compactness and partisan symmetry distributions on New Hampshire and Texas that, while related to spanning trees, can now be properly targeted with a smaller degree of spanning tree bias, which represents an advancement in flexible ensemble generation.
Atticus McWhorter, Daryl DeFord
May 23, 2026stat.ML
We generalize finite-sample bounds for convex clustering to the setting where affinity weights appearing in the objective correspond to a general connected graph. These bounds and their analysis lead to a better understanding of clustering behavior under various implied connectivity structures behind the data and to new rates of convergence for centroid recovery. The new theoretical framework is based on random walks, which allow application of concentration inequalities related to random graph models, and formalizes the relationship between the clustering performance and the connectivity of the graph structures. Through the form of the bound and empirical results, we argue proper tuning of hyperparameters to convex clustering problems should also include tuning of input affinity weights.
Sam Rosen, Jason Xu