企业官网建设流程全解析

MAG-GNN 论文总结与核心部分翻译

一、文章主要内容

1. 研究背景

图神经网络（GNNs）凭借消息传递范式在图学习任务中广泛应用，但传统GNN的表达能力受限于1维Weisfeiler-Lehman（1-WL）测试，无法识别环、路径等关键子结构。子图GNN通过枚举节点周围的根子图并应用MPNN提升表达能力，但其需遍历所有可能子图，导致计算复杂度呈指数级增长，难以应用于中大规模图。

2. 核心发现

无需枚举全部子图即可获得与子图GNN相当的表达能力——部分具有判别力的子图足以区分不同图结构。例如在正则图中，单个非三角形子图即可区分两个2-正则图，而传统子图GNN需额外运行8次MPNN。

3. 模型设计：MAG-GNN

提出基于强化学习（RL）的Magnetic Graph Neural Network（MAG-GNN），将最优子图选择转化为组合优化问题：

• 状态空间：包含图、候选子图集（节点元组）及状态矩阵（记录子图更新轨迹）；
• 动作空间：替换节点元组中某一位置的节点，保证动作复杂度与节点数线性相关；
• 奖励函数：以模型预测损失的降低量为即时奖励，直接关联任务目标；
• Q网络：采用MPNN参数化Q网络，输出替换子图的预期奖励，选择最优更