当前位置：首页 > news >正文

MAG-GNN: Reinforcement Learning Boosted Graph Neural Network | 代码 |

news 2025/9/14 15:41:53

论文信息

论文标题：MAG-GNN: Reinforcement Learning Boosted Graph Neural Network
论文作者：
论文来源：
论文地址：link
论文代码：link

Abstract

一、段落核心背景：GNN 领域的核心矛盾

1.1 GNN 的发展现状与痛点

GNN 的重要地位：近年来，图神经网络（GNNs）已成为图学习任务中的强大工具，在分子属性预测、推荐系统、自动驾驶等领域发挥关键作用。

核心优化方向：尽管 GNN 性能优异，但学界仍投入大量精力提升其结构编码能力—— 即 GNN 对图中节点连接模式、子结构（如循环、路径）的捕捉能力，这是决定 GNN 在复杂任务中表现的关键。

1.2 子图 GNN 的改进与局限

改进思路：一类主流研究方向提出 “子图 GNN”（Subgraph GNNs），通过引入子图信息提升 GNN 的表达能力（Expressivity）—— 即区分不同图结构、捕捉细分子结构的能力，且已在实验中取得显著成功（如能区分传统 GNN 无法识别的正则图）。

致命缺陷：子图 GNN 的有效性以牺牲效率为代价。为覆盖所有潜在有用的子结构，它需枚举图中所有可能的子图，导致计算复杂度随子图维度（如节点元组阶数 k）呈指数增长，难以应用于中等规模以上的图（如节点数～100 的图）。

二、本文核心贡献：破解 “表达能力 - 效率” 矛盾

2.1 关键发现：无需全量子图枚举

核心结论：通过分析全量子图枚举的必要性，本文证明 —— 模型无需枚举所有子图，仅需考虑一小部分具有判别性的子图，即可达到与全量子图枚举相近的表达能力。

示例支撑（后续章节补充）：在区分特定 2 - 正则图时，单个非三角形子图的判别效果，等价于枚举该图中所有子图的效果，大幅减少计算量。

2.2 问题建模：转化为组合优化问题

建模逻辑：将 “寻找最优判别性子图集” 这一目标，转化为组合优化问题—— 即在给定子图数量预算（如最多选择 m 个子图）的约束下，筛选出能最大化模型表达能力（最小化预测损失）的子图集。

2.3 解决方案：MAG-GNN 模型设计

模型定位：提出 “磁性图神经网络（MAG-GNN）”，这是一种由强化学习（RL）增强的 GNN，专门用于解决上述组合优化问题。

核心流程：

初始化：从图中随机选择一组候选子图，作为初始子图集；

迭代优化：通过 RL 智能体（Agent）对候选子图进行迭代更新—— 不断替换子图集中的低效子图，逐步定位到对预测最具表达能力的子图集；

复杂度降低：将子图枚举的 “指数级复杂度”，降至子图搜索算法的 “常数级复杂度”（仅需固定次数的子图更新与 MPNN 运行），同时保持优异的表达能力。

三、实验验证：性能与效率双重保障

3.1 性能表现

竞争力：在多个数据集（含合成图与真实分子图）上的大量实验表明，MAG-GNN 的性能与当前最先进（SOTA）方法相当；

优越性：在部分任务中，MAG-GNN 甚至优于许多子图 GNN—— 证明少量判别性子图足以支撑高表达能力。

3.2 效率优势

核心成果：实验明确验证，MAG-GNN 能有效降低子图 GNN 的运行时间，解决了子图 GNN “效率低下” 的核心痛点，为其在中大规模图任务中的应用奠定基础。

四、段落核心价值总结

维度	核心信息	意义
问题提出	点明 GNN “提升表达能力” 的需求，及子图 GNN “高表达 - 低效率” 的矛盾	明确研究必要性，为 MAG-GNN 的提出铺垫场景
核心创新	发现 “少量判别性子图足够” 的规律，将问题转化为组合优化，用 RL 实现高效求解	突破传统子图 GNN 的效率瓶颈，提供新的技术路径
结果验证	性能比肩 SOTA、优于部分子图 GNN，同时大幅提升效率	证明方法的实用性与优越性，为后续应用提供依据

1 Introduction

一、GNN 的发展基础与核心优势

1.1 GNN 的广泛应用

近年来，图神经网络（GNNs）取得显著进展，有力推动了多个领域的快速发展，具体应用场景包括：

药物发现：辅助分子结构分析与新型药物设计 [2]

推荐系统：优化用户 - 物品关联推荐逻辑 [31]

自动驾驶：支持多智能体协同控制等任务 [6]

1.2 GNN 的核心能力来源

GNN 的强大性能主要源于其消息传递范式（Message-Passing Paradigm） ：

该范式模拟 1 维 Weisfeiler-Lehman（1-WL）算法，用于图同构测试

通过消息传递，GNN 能够编码图中丰富的结构信息，而结构信息对判断图的属性至关重要（如分子图的化学性质、社交图的社区结构）

二、传统 GNN 的表达能力局限

2.1 核心局限：受限于 1-WL 测试

正如 Xu 等人 [32] 指出，GNN 的结构编码能力（即表达能力）存在上限，且该上限由 1-WL 测试决定，具体缺陷包括：

- 无法识别多种关键子结构：如循环（Cycles）、路径（Paths）等

- 难以区分正则图：无法对结构相似的正则图进行有效学习和辨别

- 应用痛点：上述子结构在化学（分子环结构）、生物学（蛋白质相互作用网络）等领域意义重大，传统 GNN 的局限制约了其在这些领域的深度应用

2.2 突破局限的尝试：子图 GNN 的兴起

为克服 1-WL 测试的限制，学界投入大量精力研发更具表达能力的 GNN，其中子图 GNN（Subgraph GNNs） 是极具代表性的研究方向 [33, 34, 37]，其工作原理与优势如下：

核心流程：

提取图中每个节点周围的根节点子图（Rooted Subgraphs）

将 MPNN 应用于这些子图，得到子图表示

对所有子图表示进行汇总，形成图的最终表示

理论与实践优势：

理论上已证明，子图 GNN 的表达能力优于传统 MPNN

在实验中取得了更优的实证结果，能处理部分传统 GNN 无法应对的任务

2.3 子图 GNN 的进一步局限

尽管子图 GNN 优于传统 GNN，但后续研究发现其表达能力仍存在边界：

- 受限于 3 维 Weisfeiler-Lehman（3-WL）测试 [10]，无法突破更高维度的结构识别限制

- 为进一步提升表达能力，研究方向扩展至边根子图 GNN（Edge-rooted Subgraph GNNs） [15]，试图突破 3-WL 的局限

三、子图 GNN 的效率瓶颈与研究动机

3.1 表达能力与计算成本的矛盾

通过将子图 GNN 与 k 维 WL（k-WL）测试层级关联分析，发现关键问题：

- 若要让子图 GNN 的表达能力突破 k-WL 测试的限制，需枚举与 k 呈指数级数量的子图，并对每个子图应用 MPNN [26, 10]

- 更高的表达能力伴随指数级增长的计算成本，导致子图 GNN 难以应用于中等规模的图（例如节点数约 100 的图）

3.2 核心研究疑问的提出

基于上述矛盾，本文提出关键疑问：子图 GNN 是否必须枚举所有根节点子图，才能实现更高的表达能力？

3.3 疑问的实例支撑

以图 1 中两个简单图（A 和 B）的对比为例，佐证 “无需全量子图枚举” 的可能性：

- 传统 MPNN 无法区分图 A 和图 B：二者均为 2 - 正则图，且具有相同的 1 跳子树（1-Hop Subtrees）

- 子图 GNN 可区分：通过观察两图中节点周围不同的子图，MPNN 能辨别子图差异，进而区分两图

- 关键发现：同一图中大量子图存在重复性 —— 图 A 仅含 2 种类型子图，图 B 仅含三角形子图。仅需定位图 A 中的 1 个非三角形子图，用 MPNN 处理 1 次即可区分两图；而子图 GNN 需额外对其余节点运行 8 次 MPNN

- 延伸验证：文中指出在 3.2 节将提供更复杂结构的进阶示例，进一步证明该规律的普适性

四、本文解决方案与核心贡献预告

4.1 解决方案：MAG-GNN 模型

为利用 “少量子图即可保证表达能力” 的特性，本文提出磁性图神经网络（MAG-GNN） —— 一种基于强化学习（RL）的 GNN 方法，核心设计如下：

初始化：从所有根节点子图中随机选择一组候选子图，为每个子图的根节点特征赋予唯一初始化值

迭代优化：通过 RL 智能体对候选子图集中的每个目标子图进行迭代替换，逐步筛选出更具辨别力的新子图

优化机制：将每个目标子图映射到 Q-Table（记录用潜在子图替换目标子图的期望奖励），选择能最大化奖励的子图

终止条件：重复迭代过程，直至定位到具有最高辨别力的子图集，将其输入预测 GNN 用于下游任务

4.2 模型的核心优势

复杂度降低：将子图 GNN 的指数级枚举过程，转化为常数步骤的 RL 搜索过程

效率与表达能力平衡：在严格控制计算成本的同时，保持优异的表达能力

4.3 实验成果预告

本文通过在合成图和真实世界图数据集上的大量实验，将证明：

- 性能竞争力：MAG-GNN 的性能与当前最先进（SOTA）方法相当，且在多个数据集上优于子图 GNN

- 效率优势：MAG-GNN 能有效缩短子图 GNN 的运行时间

- 核心结论：部分子图信息已足够支撑良好的表达能力，MAG-GNN 可智能定位具有表达能力的子图，以更高效率实现目标

2 Method

2.1 章节核心定位

本节是全文的核心技术章节，围绕 “如何高效筛选判别性子图” 这一核心问题，将其转化为组合优化问题，并提出 MAG-GNN 模型的完整设计方案 —— 通过强化学习（RL）框架实现子图集的迭代优化，在降低计算复杂度的同时保持高表达能力，为后续实验验证提供技术支撑。

2.2 问题建模：从 “全量子图枚举” 到 “组合优化”

2.2.1 核心优化目标

将 “寻找最具判别性的子图集” 形式化为组合优化问题，核心约束与目标如下：

- 输入参数：

- - 子图数量预算 $ m $ （最多选择 $ m $ 个子图，控制计算成本）；

- - 节点元组阶数 $ k $ （子图由 $ k $ 个节点构成，决定子图结构复杂度）；

- - 子图嵌入 MPNN $ g_p $ （用于生成单个子图的嵌入表示）；

- - 图 $ G $ 及对应标签 $ y $ 。

- 优化目标：在所有可能的 $ m $ 个 $ k $ - 阶节点元组构成的集合中，找到使预测损失最小的子图集 $ U $ ，公式如下：

$\begin{aligned} \min _{U=\left( v_{1},... ,v_{m}\right) \in \left( V^{k}(G)\right)^{m}} &\mathcal {L}\left(MLP\left(f_{p}(G, U)\right) , y\right) \\ &f_{p}(G, U)=R^{(P)}\left( \left\{ g_{p}(G(v)) \mid \forall v \in U\right\} \right) \end{aligned}$

符号说明：

- - - $ V^k(G) $ ：图 $ G $ 中所有 $ k $ - 阶节点元组的集合；

- - - $ f_p(G,U) $ ：子图集 $ U $ 的聚合表示（通过池化函数 $ R^{(P)} $ 汇总子图嵌入）；

- - - $ MLP $ ：用于最终预测的多层感知机；

- - - $ \mathcal{L} $ ：预测损失函数（如分类任务的交叉熵、回归任务的 MAE）；

2.2.2 与子图 GNN 的关联与差异

关联：公式形式与子图 GNN 的表示生成（公式 3）一致，均通过子图嵌入 + 池化得到图表示；

差异：将子图 GNN 中 “全量 $ V^k(G) $ 子图” 替换为 “小规模子图集 $ U $ ”，核心目标是通过减少子图数量降低计算复杂度（从 $ O(|V|^k) $ 降至 $ O(m) $ ）。

2.3 MAG-GNN 的强化学习（RL）框架设计

基于深度 Q 学习（DQN）在组合优化任务中的优异表现，MAG-GNN 采用 DQN 构建 RL 框架，具体包含状态空间、动作空间、奖励函数、Q 网络四大核心组件，各组件设计紧密贴合 “子图筛选” 任务需求。

2.3.1 状态空间（State Space）：定义 RL 智能体的观察对象

2.3.1.1 状态构成

核心定义：对图 $ G $ ，一个状态 $ s $ 由三部分构成：

$s=(G, U, W)=\left(G,\left(v_{1}, ..., v_{m}\right), W\right), \quad s \in S=\mathcal{G} \times\left(\mathcal{V}^{k}\right)^{m} \times\left(\mathbb{R}^{m \times w}\right)$

各部分含义：

- - $ G $ ：当前处理的图， $ \mathcal{G} $ 表示所有可能图的集合；

- - $ U=(v_1,...,v_m) $ ：当前选中的 $ m $ 个 $ k $ - 阶节点元组（即待优化的子图集）；

- - $ W \in \mathbb{R}^{m \times w} $ ：状态矩阵，用于记录子图集 $ U $ 的更新历史（如过去动作、子图性能等），辅助智能体学习长期策略。

初始状态生成：

从训练集中随机采样 1 个图 $ G $ ；

从 $ V^k(G) $ 中随机采样 $ m $ 个节点元组，作为初始子图集 $ U $ ；

状态矩阵 $ W $ 初始化为全 0 矩阵。

2.3.1.2 节点元组阶数 $ k $ 的选择考量

表达能力与训练难度的权衡：

优势： $ k $ 越大，子图结构越复杂，模型表达能力越强，可能需要更小的 $ m $ 和更少的 RL 步骤即可表征图，推理效率更高；

劣势： $ k $ 过大会扩大节点元组的搜索空间，增加训练难度；对部分数据集，过高的表达能力可能 “冗余”，导致训练不稳定；

实践建议：根据数据集复杂度动态选择 $ k $ —— 简单数据集用小 $ k $ 稳定训练，复杂数据集用大 $ k $ 提升表达能力。

2.3.2 动作空间（Action Space）：定义 RL 智能体的操作方式

2.3.2.1 动作定义

核心操作：1 个 RL 动作定义为 “选择 1 个节点元组中的 1 个位置，将该位置的节点替换为图中其他节点”，实现子图的迭代更新（用更具判别性的子图替换低效子图）。

数学表达：对状态 $ s=(G,U,W) $ ，动作 $ a_{i,j,l} $ 对 $ U $ 的更新如下：

$U'=a_{i,j,l}(U)=\left(v_{1} ..., v_{i-1}, v_{i}', v_{i+1}, ... v_{m}\right), \quad v_{i}'=\left(\left[v_{i}\right]_{1}, ...,\left[v_{i}\right]_{j-1}, v_{l},\left[v_{i}\right]_{j+1}, ...\left[v_{i}\right]_{k}\right)$

动作参数含义：

- - $ i $ ：目标节点元组的索引（从 $ U $ 中选择第 $ i $ 个元组进行更新）；

- - $ j $ ：目标节点元组中待替换节点的位置（选择第 $ i $ 个元组的第 $ j $ 个节点）；

- - $ l $ ：替换节点的索引（用图 $ G $ 中的第 $ l $ 个节点替换原节点）。

状态更新：动作执行后，状态矩阵 $ W $ 通过更新函数 $ W'=f_W(s,U') $ 更新（ $ f_W $ 可非可训练，如子图嵌入的池化函数），新状态为 $ s'=(G,U',W') $ 。

2.3.2.2 动作空间的复杂度优势

规模控制：动作空间规模为 $ A=[m] \times [k] \times V $ ，即 $ O(mk|V|) $ ，与节点数 $ |V| $ 线性相关（ $ m $ 为常数， $ k $ 通常较小，如 $ k=2 $ 已优于多数子图 GNN）；

进一步优化：可移除 “选择目标元组 $ i $ ” 的步骤，让 Q 网络直接对所有元组执行更新，动作空间规模降至 $ O(k|V|) $ ；智能体将学习 “不更新无需优化的元组”，不会损失性能，且支持并行更新，提升计算效率；

确定性优势：与随机 RL 系统不同，MAG-GNN 的动作结果是确定的（给定动作 $ a_{i,j,l} $ ，子图集 $ U $ 的更新结果唯一），便于训练稳定。

3.3 奖励函数（Reward）：定义 RL 智能体的优化方向

3.3.1 奖励设计逻辑

核心挑战：“子图的表达能力” 难以直接量化，需通过其对最终任务的贡献间接衡量；

设计思路：以 “动作对预测损失的改进幅度” 作为即时奖励，直接关联优化目标，确保智能体学习方向与任务目标一致。

3.3.2 奖励计算公式

设当前状态 $ s=(G,U,W) $ ，动作 $ a $ 执行后的新状态 $ s'=(G,U',W') $ ，则奖励 $ r(s,a,s') $ 为：

$r\left(s, a, s'\right)=\mathcal{L}\left(MLP\left(f_{p}(G, U)\right), y\right)-\mathcal{L}\left(MLP\left(f_{p}\left(G, U'\right)\right), y\right)$

奖励含义：若动作后损失减少（ $ r>0 $ ），则给予正奖励，动作越有效，奖励值越大；若损失增加（ $ r<0 $ ），则给予负奖励，避免智能体学习该动作；

灵活性：奖励函数与具体任务（分类 / 回归）绑定，可适配不同下游任务，通用性强。

3.4 Q 网络（Q-Network）：定义 RL 智能体的决策模型

3.4.1 Q 网络的核心作用

Q 网络用于近似 “状态 - 动作” 的 Q 值（执行动作的期望累积奖励），是智能体选择最优动作的核心依据。由于状态包含图结构，需保证 Q 网络对同构图形输出一致的 Q 值，因此采用equivariant MPNN（等变 MPNN）参数化。

3.4.2 Q 值计算方式

对当前状态 $ s=(G,U,W) $ 及目标节点元组 $ v \in U $ ，Q 表（记录所有可能动作的 Q 值）的计算如下：

$[Q(s, v)]_{l}=MLP\left(\left[g_{r l}(G(v))\right]_{l} \oplus \sum_{v \in U} R^{(G)}\left(g_{r l}(G(v))\right) \oplus R^{(W)}(W)\right)$

输入组件：

子图嵌入： $ [g_{rl}(G(v))]_l $ ，由 RL 专用 MPNN $ g_{rl} $ 生成目标子图 $ G(v) $ 中节点 $ v_l $ 的嵌入；

整体图表示： $ \sum_{v \in U} R^{(G)}(g_{rl}(G(v))) $ ，对所有子图的嵌入进行图级池化（如求和），捕捉子图间的关联；

状态矩阵汇总： $ R^{(W)}(W) $ ，对状态矩阵 $ W $ 进行池化，融入历史更新信息；

$ \oplus $ 表示特征拼接，将三类信息融合为 Q 网络的输入。

Q 表含义： $ [Q(s,v)]_{l,j} $ 表示 “将目标元组 $ v $ 的第 $ j $ 个节点替换为节点 $ v_l $ ” 这一动作的期望奖励。

3.4.3 最优动作选择

智能体通过最大化 Q 值选择最优动作，公式如下：

$\underset{j, l}{arg max }[Q(s, v)]_{l, j}$

关键细节：通过为不同节点元组分配唯一的初始嵌入，MPNN 能够区分原本同构的图，确保 Q 网络能捕捉子图的判别性差异。

3.5 MAG-GNN 的核心工作流程（结合图 3）

初始化：生成初始状态 —— 随机采样 $ m $ 个节点元组及对应子图，状态矩阵 $ W $ 初始化为 0；

迭代更新：

对当前子图集 $ U $ ，通过 Q 网络计算所有可能动作的 Q 值；

选择最优动作，更新子图集 $ U $ 为 $ U' $ ，同步更新状态矩阵 $ W $ ；

重复上述步骤固定次数 $ t $ ，逐步筛选出判别性子图；

终止条件：无需显式终端状态 —— 当所有动作均导致损失增加时，Q 网络将学习到 “停止更新” 的稳定策略；

下游预测：将最终筛选出的子图集 $ U $ 输入预测 GNN，生成图表示并完成下游任务（分类 / 回归）。

3.5.1 模型命名由来

MAG-GNN（Magnetic GNN）的命名类比 “磁场效应”：将标记节点（子图的节点元组）视为 “铁球”，图的几何结构视为 “磁场”，Q 网络计算 “铁球” 受到的 “磁力”（动作的 Q 值），智能体通过移动 “铁球”（更新子图）学习磁场的特性（图的结构信息），形象体现子图迭代优化的过程。

2.4 理论支撑：MAG-GNN 的优越性证明

2.4.1 定理 2：MAG-GNN 优于随机动作

核心结论：存在一种 MAG-GNN，其识别判别性子图的能力强于随机动作；

证明逻辑：

最坏情况：MAG-GNN 可采用输出均匀分布的 MPNN，等价于随机动作；

优势场景：在特定图结构（如超图判别任务）中，MAG-GNN 通过学习 “移动节点元组至关键位置”，仅需常数步骤即可定位判别性子图，而随机动作需 $ O(n) $ 步（ $ n $ 为节点数），证明其效率优势；

意义：从理论上保证 MAG-GNN 的子图筛选能力不弱于随机采样，且在多数场景下更优。

2.4.2 定理 3：MAG-GNN 可覆盖 PF-GNN

核心结论：采用与 PF-GNN（粒子滤波 GNN）相同的重采样方法时，MAG-GNN 可复现 PF-GNN 的功能；

证明逻辑：

映射关系：将 PF-GNN 的 “粒子” 对应 MAG-GNN 的 “节点元组”，“粒子权重” 对应 MAG-GNN 的 “状态矩阵 $ W $ ”；

行为复现：通过设计 Q 网络的更新规则（如固定已优化的节点元组）和 MPNN 结构（模拟 PF-GNN 的节点个性化与嵌入更新），MAG-GNN 可生成与 PF-GNN 完全一致的节点表示；

意义：说明 MAG-GNN 是更通用的框架，可兼容现有采样 - based 方法的优势。

2.5 MAG-GNN 与现有采样方法的差异

对比维度	MAG-GNN	现有采样方法（如 PF-GNN [7]、k-OSAN [26]）
采样策略	RL 驱动，学习子图间的关联，动态优化采样分布	随机采样（PF-GNN 在正则图无特征时退化为均匀分布）或数据驱动（k-OSAN 依赖节点特征，无特征时失效）
子图关联性	建模子图间的依赖关系（通过 Q 网络融合整体图表示）	子图独立采样，忽略关联性
无特征场景适配性	无需节点特征，通过节点元组标记捕捉结构信息	k-OSAN 失效，PF-GNN 效率低
表达能力与样本量权衡	少量样本即可达到高表达能力	需更多样本才能接近同等表达能力

2.6 MAG-GNN 的复杂度分析

2.6.1 核心复杂度公式

MAG-GNN 的总复杂度由 “MPNN 运行成本” 和 “Q 表计算成本” 构成，最终简化为：

$O(m t T|V|^2)$

- 各参数含义：

- - $ m $ ：子图数量预算（常数）；

- - $ t $ ：RL 迭代步骤数（常数）；

- - $ T $ ：MPNN 的层数（常数）；

- - $ |V|^2 $ ：单 MPNN 的复杂度（与节点数平方相关，因需处理所有边）；

与子图 GNN 的对比：子图 GNN 的复杂度为 $ O(T|V|^k) $ （ $ k $ 为节点元组阶数），随 $ k $ 指数增长；而 MAG-GNN 的复杂度随 $ k $ 线性增长（ $ k $ 仅影响动作空间规模，且通常较小），在 $ k \geq 2 $ 时优势显著。

2.7 章节总结：MAG-GNN 的核心价值

价值维度	具体表现
问题转化	将 “子图筛选” 从 “暴力枚举” 转化为 “组合优化”，突破复杂度瓶颈
框架设计	RL 四大组件（状态 / 动作 / 奖励 / Q 网络）紧密贴合图任务，保证有效性与通用性
理论保障	定理证明其优于随机动作、可覆盖现有方法，增强可信度
效率优势	复杂度从指数级降至常数级，

3 Experiment

3.1 实验核心目标与设计思路

3.1.1 核心待解答问题（Q1-Q4）

实验围绕 4 个关键问题展开，验证 MAG-GNN 的表达能力、泛化性、实用性能及效率优势：

- Q1：MAG-GNN 是否具备优异的表达能力？其 RL 智能体输出的子图是否比随机子图更具判别性？

- Q2：MAG-GNN 的图级表达能力能否泛化到节点级任务？

- Q3：RL 驱动的子图筛选策略在真实世界数据集上表现如何？

- Q4：MAG-GNN 是否具备文中声称的计算效率优势？

3.1.2 实验设计细节

- 子图更新方式：采用 “所有节点元组同时更新” 策略，支持并行计算，提升实验效率；

- 参数控制：为保证公平性，固定 GNN 层数为 5、嵌入维度为 100，所有模型设置 1GB 内存预算；MAG-GNN 的子图数量预算$m=2$、MPNN 层数$T=2$；

- 重复性验证：因 MAG-GNN 初始节点元组存在随机性，所有实验重复 10 次，取平均值作为最终结果；

- 代码与补充信息：实验代码开源（https://github.com/LechengKong/MAG-GNN），数据集与超参数细节见附录 F。

3.2 实验基础信息：数据集与基线方法

3.2.1 数据集汇总（含合成与真实世界数据集）

数据集类型	数据集名称	数据规模 / 结构	任务类型	核心用途（验证目标）
合成数据集（验证表达能力）	EXP	600 对非同构图，无法被 1-WL/2-WL 受限 GNN 区分	图分类（区分图对）	Q1：验证突破低维 WL 限制的能力
	SR25	15 个强正则图，相同配置，无法被 3-WL 受限 GNN 区分	多分类（15 类）	Q1：验证突破 3-WL 限制的能力
	CSL	150 个循环跳链图，分 10 个同构类	图分类（10 类）	Q1：验证对复杂循环结构的判别能力
	BREC	400 对合成图，含基础图与正则图子集	图分类（区分图对）	Q1：验证细粒度表达能力
	CYCLE	5000 个图，含 3-6 阶循环	节点回归（计数循环数）	Q2：验证节点级任务适配性
真实世界数据集（验证实用性能）	QM9	130k 分子图，12 个回归目标（如偶极矩、 HOMO 能量）	图回归（分子属性预测）	Q3：验证分子属性预测性能
	ZINC	12k 化合物图	图回归（分子性质预测）	Q3：验证中小规模分子任务性能
	ZINC-FULL	250k 化合物图	图回归（分子性质预测）	Q3：验证大规模分子任务性能
	OGBG-MOLHIV	41k 分子图	图分类（判断是否抑制 HIV）	Q3：验证分子分类任务性能

3.2.2 基线方法汇总（覆盖不同类型 GNN）

基线类型	模型名称	核心特点	对比意义
传统 MPNN	GIN[32]	基于 1-WL 测试，表达能力有限	验证 MAG-GNN 对传统 GNN 的性能提升
非等变 GNN	RNI[1]	随机节点初始化，理论上通用但训练困难	验证 MAG-GNN 的训练稳定性与实用性
	PF-GNN[7]	粒子滤波采样，非等变框架	验证 MAG-GNN 在非等变方法中的优势
子图 GNN	NGNN[35]	节点根子图，受限于 3-WL	验证 MAG-GNN 在低复杂度下的表达能力优势
	GNNAK+[37]	子图感知，受限于 3-WL	验证 MAG-GNN 对主流子图 GNN 的性能对比
	SSWL+[36]	子图 WL 测试增强，受限于 3-WL	验证 MAG-GNN 突破 3-WL 的能力
	I²-GNN[15]	边根子图，突破 3-WL，但复杂度高	验证 MAG-GNN 在高表达能力下的效率优势
随机采样方法	RNM（随机节点标记）	与 MAG-GNN 同超参，随机选子图	验证 RL 筛选子图的有效性
其他高表达 GNN	1-2-3-GNN[23]	模拟 3-WL，表达能力强但易过拟合	验证 MAG-GNN 的过拟合控制能力
	PPGN[20]	高阶消息传递，复杂度高	验证 MAG-GNN 的效率 - 性能平衡优势

3.3 实验 1：判别能力验证（回答 Q1）

3.3.1 实验设置

数据集：EXP、CSL、SR25（合成数据集，均需突破低维 WL 限制）；

训练范式：采用 ORD 范式（先固定子图嵌入 MPNN，再训练 RL agent），确保环境稳定；

评价指标：准确率（Accuracy），越高表示判别能力越强。

3.3.2 实验结果（表 1）

模型	EXP 准确率	CSL 准确率	SR25 准确率	关键观察
GIN	50.0%	10.0%	6.7%	传统 MPNN 受限于 1-WL，无法区分多数图
RNI	99.7%	16.0%	6.7%	理论通用但训练困难，SR25 上仅随机猜测水平
NGNN	100%	100%	6.7%	节点根子图受限于 3-WL，无法区分强正则图
GNNAK+/SSWL+	100%	100%	6.7%	同 NGNN，3-WL 限制导致 SR25 失效
RNM	100%	100%	93.8%	随机选子图有一定效果，但 SR25 仍有误差
I²-GNN	100%	100%	100%	突破 3-WL，但需$O(\|V\|^2)$次 MPNN 运行
MAG-GNN	100%	100%	100%	仅需常数次 MPNN 运行，突破 3-WL 且性能最优

3.3.3 补充实验：RL 步骤对性能的影响（图 5）

实验设计：固定 MAG-GNN 的子图数量$m=1$、节点元组阶数$k=2$，观察 RL 迭代步骤与准确率的关系；

关键结果：

EXP/CSL：1-2 步即可达到 100% 准确率，远快于随机动作（步骤 0 时为 RNM 水平）；

SR25：6 步达到 100% 准确率，且准确率随步骤稳步提升，证明 RL agent 持续学习优化子图；

结论：MAG-GNN 的 RL 迭代能有效提升子图判别性，步骤越多（在收敛前），性能越优。

3.3.4 实验结论（Q1 答案）

MAG-GNN 具备优异的表达能力，在所有合成数据集上均达到 100% 准确率，突破 3-WL 限制；

RL agent 输出的子图显著优于随机子图（RNM），尤其在强正则图（SR25）上优势明显；

与子图 GNN（如 I²-GNN）相比，MAG-GNN 仅需常数次 MPNN 运行，在保持高表达能力的同时大幅降低复杂度。

3.4 实验 2：节点级任务验证（回答 Q2）

3.4.1 实验设置

数据集：CYCLE（节点级循环计数任务，需计数 3-6 阶循环，仅突破 3-WL 的模型可完成所有计数）；

训练范式：ORD 范式；

评价指标：平均绝对误差（MAE，越低越好），误差 < 0.01 视为具备有效计数能力。

3.4.2 实验结果（表 2）

模型	3 - 循环 MAE	4 - 循环 MAE	5 - 循环 MAE	6 - 循环 MAE	关键观察
GIN	0.3515	0.2742	0.2088	0.1555	传统 MPNN 无法计数循环，误差极大
RNM	0.0041	0.0129	0.0351	0.0327	随机子图可计数 3-4 阶循环，5-6 阶误差大
ID-GNN[33]	0.0006	0.0022	0.0490	0.0495	节点根子图可计数 3-4 阶，5-6 阶失效
NGNN[35]	0.0003	0.0013	0.0402	0.0439	同 ID-GNN，3-WL 限制导致高阶循环计数失效
GNNAK+[37]	0.0004	0.0041	0.0133	0.0238	5 阶循环计数提升，但 6 阶仍有误差
I²-GNN[15]	0.0003	0.0016	0.0028	0.0082	突破 3-WL，所有循环计数误差均 < 0.01
MAG-GNN	0.0029	0.0037	0.0097	0.0286	3-5 阶循环计数误差 < 0.01，6 阶误差较高

3.4.3 实验结论（Q2 答案）

MAG-GNN 的表达能力可泛化到节点级任务，能准确计数 3-5 阶循环，证明子图筛选策略对节点级信息捕捉的有效性；

6 阶循环计数性能欠佳，推测原因是当前奖励函数基于图级损失平均，未针对节点级任务优化（未来可设计节点级专属奖励）；

尽管 6 阶计数有误差，MAG-GNN 仍优于 NGNN 等节点根子图 GNN，证明高阶节点元组（$k>2$）提升了表达能力。

3.5 实验 3：真实世界数据集验证（回答 Q3）

3.5.1 实验 1：QM9 分子属性预测

实验设置：12 个回归目标，评价指标 MAE（越低越好），训练范式 SIMUL（同步训练 agent 与嵌入 MPNN）；

核心结果（表 5）：

与 NGNN 对比：MAG-GNN 在所有目标上均优于 NGNN，平均 MAE 降低 33%，证明少量判别性子图优于全量节点根子图；

与 I²-GNN 对比：MAG-GNN 在多数目标上优于 I²-GNN（平均 MAE 降低 16%），且 MPNN 运行次数远少于 I²-GNN；

与 1-2-3-GNN 对比：MAG-GNN 在局部属性（如$\mu$、$\epsilon_{HOMO}$）上更优，1-2-3-GNN 在全局属性（如$C_v$）上稍优，推测因 1-2-3-GNN 易过拟合，而 MAG-GNN 通过子图筛选降低过拟合风险；

结论：MAG-GNN 在分子属性预测任务上性能优异，兼顾表达能力与过拟合控制。

3.5.2 实验 2：ZINC、ZINC-FULL、OGBG-MOLHIV

实验设置：ZINC/ZINC-FULL 为分子回归任务（MAE），OGBG-MOLHIV 为分子分类任务（AUROC），训练范式含 SIMUL 与 PRE（预训练）；

核心结果（表 6、表 3）：

与基础 GNN 对比：MAG-GNN（MAE 0.106）显著优于 GIN（0.163）、PNA（0.188），证明高表达能力的优势；

与非等变 GNN 对比：MAG-GNN（PRE 范式 MAE 0.096）优于 PF-GNN（0.122）、RNM（0.128），证明 RL 捕捉子图关联的有效性；

迁移学习（表 3）：在合成数据集（如 6-CYCLES、SR25）预训练后，MAG-GNN 在 ZINC 上 MAE 从 0.106 降至 0.096，ZINC-FULL 从 0.030 降至 0.023，MOLHIV AUROC 从 77.12 升至 78.30，证明预训练能提升泛化性；

OGBG-MOLHIV 特殊情况：MAG-GNN（AUROC 78.30）稍逊于 I²-GNN（78.68）、PF-GNN（80.15），推测因该任务性能更依赖基础 GNN 实现（而非表达能力），MAG-GNN 可通过替换更优基础 GNN 改进；

结论：MAG-GNN 在真实分子任务上性能竞争力强，预训练范式能进一步提升泛化性，适配不同规模与类型的真实任务。

3.6 实验 4：效率验证（回答 Q4）

3.6.1 实验设置

数据集：ZINC-FULL、CYCLE、QM9（覆盖节点级与图级任务，不同规模数据集）；

评价指标：推理时间（ms，越低越好），固定所有模型参数规模（GNN 层数 5、嵌入维度 100）与内存预算（1GB）；

核心对比对象：传统 MPNN（GIN）、子图 GNN（NGNN、I²-GNN）、高阶 GNN（PPGN）。

3.6.2 实验结果（表 4）

模型	ZINC-FULL 推理时间（ms）	CYCLE 推理时间（ms）	QM9 推理时间（ms）	关键观察
GIN	100.1	58.4	222.9	传统 MPNN 效率最高，但表达能力有限
NGNN	402.9	211.7	776.8	节点根子图效率中等，表达能力受限
I²-GNN	1864.1	1170.4	3524.0	边根子图表达能力强，但效率极低（指数级复杂度）
PPGN	2097.3	1196.8	4108.7	高阶 GNN 效率最差
MAG-GNN	385.8	155.1	704.9	效率优于所有子图 GNN 与高阶 GNN，接近 NGNN 且表达能力更优