Reinforcement Learning for Microcanonical Graph Ensemble with Assortativity Constraints

• URL: http://arxiv.org/abs/2605.23285v1
• Date: Fri, 22 May 2026 06:57:41 GMT
• Title: Reinforcement Learning for Microcanonical Graph Ensemble with Assortativity Constraints
• Abstract summary: How network structure determines function is a fundamental question, and it can be investigated by graph ensembles with precisely controlled structural properties.<n>Here we introduce the Deep Microcanonical Graph Generator (DMGG), a reinforcement learning framework that transforms any given graph through degree-preserving rewirings.
• Score: 1.0896567381206717
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Deep Gaussian Processes on Directed Acyclic Graphs [11.74273181198187]
  Many real-world processes can be represented as compositions of functions along a directed acyclic graph (DAG)<n>These functions are partially observed across the DAG, with noisy and heterogeneously sampled measurements.<n>We theoretically study their prior-collapse behaviour, and the effect of graph topology and intermediate observations on information preservation.<n>We offer a structured variational approximation that retains graph dependencies, preserves compositional uncertainty, and captures the explaining-away behaviour of colliders.
  arXiv  Detail & Related papers  (2026-07-10T17:41:11Z)
• Differentiable Tripartite Modularity for Clustering Heterogeneous Graphs [0.0]
  We introduce a differentiable formulation of tripartite modularity for graphs composed of three node types connected through mediated interactions.<n>Community structure is defined in terms of weighted co-paths across the tripartite graph, together with an exact factorized computation that avoids the explicit construction of dense third-order tensors.<n>We validate the proposed framework on large-scale urban cadastral data, where it exhibits robust convergence behavior and produces spatially coherent partitions.
  arXiv  Detail & Related papers  (2026-02-10T15:06:53Z)
• Pruning at Initialisation through the lens of Graphon Limit: Convergence, Expressivity, and Generalisation [16.628325681877556]
  Pruning at Initialisation methods discover sparse, trainableworks before training, but their theoretical mechanisms remain elusive.<n>In this work, we connect discrete intrinsic prunings to graph limit theory via graphons, establishing the graphon limit of PaI masks.<n>We derive two fundamental theoretical results: (i) a Universal Approximation Theorem for sparse networks that depends only on the dimension of active coordinate subspaces; and (ii) a Graphon-NTK generalisation bound demonstrating how the limit graphon geometry to align with informative features.
  arXiv  Detail & Related papers  (2026-02-06T13:02:47Z)
• Variational Bayesian Flow Network for Graph Generation [54.94088904387278]
  We propose Variational Bayesian Flow Network (VBFN) for graph generation.<n>VBFN performs variational lifting to a tractable joint Gaussian variational belief family governed by structured precisions.<n>On synthetic and molecular graph datasets, VBFN improves fidelity and diversity, and surpasses baseline methods.
  arXiv  Detail & Related papers  (2026-01-30T03:59:38Z)
• SIGMA: Scalable Spectral Insights for LLM Collapse [51.863164847253366]
  We introduce SIGMA (Spectral Inequalities for Gram Matrix Analysis), a unified framework for model collapse.<n>By utilizing benchmarks that deriving and deterministic bounds on the matrix's spectrum, SIGMA provides a mathematically grounded metric to track the contraction of the representation space.<n>We demonstrate that SIGMA effectively captures the transition towards states, offering both theoretical insights into the mechanics of collapse.
  arXiv  Detail & Related papers  (2026-01-06T19:47:11Z)
• Transformers Provably Learn Directed Acyclic Graphs via Kernel-Guided Mutual Information [91.66597637613263]
  transformer-based models leveraging the attention mechanism have demonstrated strong empirical success in capturing complex dependencies within graphs.<n>We introduce a novel information-theoretic metric: the kernel-guided mutual information (KG-MI) based on the $f$-divergence.<n>We prove that, given sequences generated by a $K$-parent DAG, training a single-layer, multi-head transformer via a gradient ascent converges to the global optimum time.
  arXiv  Detail & Related papers  (2025-10-29T14:07:12Z)
• Composable Score-based Graph Diffusion Model for Multi-Conditional Molecular Generation [85.58520120011269]
  We propose Composable Score-based Graph Diffusion model (CSGD), which extends score matching to discrete graphs via concrete scores.<n>We show that CSGD achieves state-of-the-art performance with a 15.3% average improvement in controllability over prior methods.<n>Our findings highlight the practical advantages of score-based modeling for discrete graph generation and its capacity for flexible, multi-property molecular design.
  arXiv  Detail & Related papers  (2025-09-11T13:37:56Z)
• Energy-Based Coarse-Graining in Molecular Dynamics: A Flow-Based Framework without Data [0.0]
  Coarse-grained (CG) models provide an effective route to reducing the complexity of molecular simulations.<n>We introduce a fully data-free, generative framework for CG that directly targets the all-atom Boltzmann distribution.<n>We show that the method captures all relevant modes of the Boltzmann distribution, reconstructs atomic configurations, and automatically learns physically meaningful CG representations.
  arXiv  Detail & Related papers  (2025-04-29T17:05:27Z)
• Last-Iterate Convergence of Adaptive Riemannian Gradient Descent for Equilibrium Computation [52.73824786627612]
  This paper establishes new convergence results for textitgeodesic strongly monotone games.<n>Our key result shows that RGD attains last-iterate linear convergence in a textitgeometry-agnostic fashion.<n>Overall, this paper presents the first geometry-agnostic last-iterate convergence analysis for games beyond the Euclidean settings.
  arXiv  Detail & Related papers  (2023-06-29T01:20:44Z)
• Regularization of Mixture Models for Robust Principal Graph Learning [0.0]
  A regularized version of Mixture Models is proposed to learn a principal graph from a distribution of $D$-dimensional data points. Parameters of the model are iteratively estimated through an Expectation-Maximization procedure.
  arXiv  Detail & Related papers  (2021-06-16T18:00:02Z)
• Adversarial Graph Disentanglement [47.27978741175575]
  A real-world graph has a complex topological structure, which is often formed by the interaction of different latent factors. We propose an underlinetextbfAdversarial underlinetextbfDisentangled underlinetextbfGraph underlinetextbfConvolutional underlinetextbfNetwork (ADGCN) for disentangled graph representation learning.
  arXiv  Detail & Related papers  (2021-03-12T14:11:36Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.