arXiv:2606.18106cs.LG2026-06

用强化学习找最小零强迫集,提升图网络控制效率。

Deep Reinforcement Learning for Minimum Zero-Forcing Sets

论文配图:Deep Reinforcement Learning for Minimum Zero-Forcing Sets
图 1 · 摘自论文原文
  • 基于S2V-DQN架构设计强化学习框架SD-ZFS
  • 在多种图结构上优于贪心算法与最优解
  • 适合研究图神经网络与网络控制的学者

本文研究无向图上的最小零强迫集问题,该问题是通过初始节点颜色传播使全图着色的图着色问题。零强迫集可在网络科学、网络控制及逻辑电路设计中应用,但求解该问题被证明为NP难。本文提出一种改进的强化学习框架SD-ZFS,基于S2V-DQN架构适配零强迫集问题。在不同结构的图数据集上训练多个模型,分析其泛化性、可扩展性与跨网络迁移能力。实验表明,该框架性能优于最优解与贪心启发式方法,揭示了机器学习在解决此类图问题中的潜力,以及网络结构对问题复杂度的影响。

原文摘要 · Abstract (English)

This paper explores the problem of finding the minimum zero-forcing set on undirected graphs and proposes an adapted machine-learning framework to solve the problem. The minimum zero-forcing set problem is a graph coloring problem where the color of an initial set of nodes propagates throughout a network. The set of nodes is zero-forcing if it forces all uncolored nodes to change color under the constraint of the color-change rule. There are several applications to this problem across different domains such as network science, network control, and designing logical circuits. Finding the minimum zero-forcing set is shown to be NP-hard. We propose a reinforcement learning framework, SD-ZFS, that adapts the S2V-DQN architecture to the ZFS problem. We train several models on this adapted framework and analyze the performance across graph datasets that have varying structures. We evaluate how the models trained on the framework generalize, scale, and transfer to different network types. The results demonstrate the effectiveness of the framework when compared against the optimal solution and greedy heuristic. We provide further insight into how the ZFS problem can be solved through machine-learning and the influence of network structure on the problem.

强化学习图神经网络网络控制

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。