Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint

arXiv:2605.23285 · cs.LG, cond-mat.stat-mech, cs.AI · Submitted 2026-05-22 · Read on arXiv

cs.LG, cond-mat.stat-mech, cs.AI

Submitted: 2026-05-22

Updated: 2026-09-17

License: http://creativecommons.org/licenses/by/4.0/

The gist: Generating graph ensembles with precisely controlled structural properties is central to investigating how network structure shapes function.

Terminology

Abstract

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.

Sources

Related papers