用强化学习精准生成指定同配性的图,突破传统方法局限。
Reinforcement Learning for Microcanonical Graph Ensemble with Assortativity Constraints

- 通过强化学习驱动度不变重连,精确控制图的同配性
- 生成速度比传统方法快一个数量级,且保持结构多样性
- 适合研究网络结构与功能关系,排除统计偏差
网络结构如何决定功能是基础科学问题,可通过精确控制结构属性的图集来研究。经典方法如指数随机图模型(ERGM)仅在期望上施加约束,允许个体实现波动;而微正则图集要求严格满足约束,但除度序列外,实用采样方法长期缺失。本文提出深度微正则图生成器(DMGG),一种基于强化学习的框架,通过保持度不变的重连操作,将任意图精确调整至目标同配性(衡量相邻节点度相关性的指标)。不同于依赖熵主导的梅特罗波利斯-哈斯廷斯动力学,DMGG采用策略引导搜索,最大程度改变联合度矩阵。该方法避免了繁琐参数调优,生成效率提升至少一个数量级,同时保留配置多样性。由于可泛化于不同规模、稀疏度和拓扑,该方法提供了精确的零模型,可用于定量分离次级可观测量(如聚类系数)。结果表明,强化学习是生成硬约束图的可行且强大的范式,为无集合伪影地研究结构-功能关系开辟新路径。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。