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
Generating graph ensembles with precisely controlled structural properties is central to investigating how network structure shapes function. Canonical ensembles impose constraints only in expectation (soft constraints), letting individual realizations fluctuate around the target, whereas enforcing hard constraints with prescribed precision in every realization remains challenging beyond fixing the degree sequence. Here we show that a reinforcement learning framework can drive a graph through degree-preserving rewirings to satisfy a prescribed assortativity, which characterizes the degree--degree correlation of adjacent nodes. By replacing the entropically dominated Metropolis--Hastings random walk with directed transport, the learned policy reduces generation cost by at least an order of magnitude while retaining over 98% of configurational diversity. Trained on small graphs, the framework generalizes across sizes and topologies without retraining, enabling quantitative isolation of secondary observables such as the clustering coefficient. These results establish reinforcement learning as a practical paradigm for hard-constrained graph generation.
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