Sound Logical Explanations for Mean Aggregation Graph Neural Networks¶

会议: NeurIPS 2025
arXiv: 2511.11593
代码: 无
领域: graph_neural_networks / AI_theory
关键词: 图神经网络, 可解释性, 逻辑规则, 均值聚合, 知识图谱补全

一句话总结¶

针对使用均值聚合函数的 GNN（MAGNN，即非负权重的 mean-GNN），证明了能够作为其 sound 解释的单调逻辑规则的精确类别，并构造了一个一阶逻辑的受限片段来解释任意 MAGNN 预测，实验表明限制非负权重不显著影响性能且能有效提取 sound 规则。

研究背景与动机¶

领域现状: GNN 广泛用于知识图谱补全（KGC）、药物组合预测、推荐系统等任务。为保证输出可信，需要用 sound 逻辑规则来解释 GNN 的预测——即规则产生的推断必须是模型预测的子集。

现有痛点: 已有工作为 max 和 sum 聚合的非负权重 GNN 提供了 sound Datalog 规则和等价程序（Tena Cucala et al.），但 均值聚合（mean aggregation） 是实践中最常用的默认选择（R-GCN 等），却缺乏可解释性和表达力的理论分析。

核心矛盾: Mean-GNN 因其简洁性和训练稳定性被广泛使用，但其非单调性（即加入更多邻居可能降低聚合值）使得无法直接套用 sum/max-GNN 的理论框架，也无法找到等价的一阶逻辑程序。

本文目标: 为 mean 聚合的 GNN 建立 sound 逻辑规则的理论基础，并提供实际可用的规则提取方法。

切入角度: 限制权重为非负（与 sum/max-GNN 工作一致），将非单调性来源隔离到聚合函数本身，从而简化分析。

核心 idea: MAGNN 能表达超越 FOL 的逻辑函数，但其 sound 单调规则形式非常受限——所有 sound ELUQ 规则都可被一组极简规则子覆盖（subsume），并可用有限搜索空间枚举验证。

方法详解¶

整体框架¶

工作分为两大理论贡献： 1. Theorem 3：精确刻画哪些单调规则（ELUQ 规则）可以是 MAGNN 的 sound 规则——任何 sound ELUQ 规则都可被一组形如 ∃P₁.⊤ ⊓ ... ⊓ ∃Pⱼ.⊤ ⊓ A₁ ⊓ ... ⊓ Aₖ ⊑ Aₖ₊₁ 的简单规则子覆盖 2. Theorem 6：为任意 MAGNN 预测提供一个 sound 的解释性规则，使用受限的 FOL 片段 Ω

关键设计¶

ELUQ 规则语言（Theorem 3）:
- 定义 ELUQ = EL + union(⊔) + 数量限制(≥n)，作为 ALCQ 与 EL 之间的描述逻辑
- 核心发现：对 MAGNN 而言，任何 sound ELUQ 规则都可退化为仅包含 ∃P.⊤（存在某种关系的邻居）和原子概念 A 的合取
- 证明关键：利用 mean 聚合的性质——当邻居数趋于无穷时，mean 趋近于单个邻居的值，因此 ≥n 可退化为 ∃
- 这意味着 sound 单调规则空间是有限的（δ·2^(δ·|Col|) 条），可以穷举搜索
规则 soundness 验证（Proposition 4）:
- 给定一条简单规则，只需在一个最小数据集 D_base 上运行 MAGNN 并检查输出即可判断 soundness
- D_base 仅包含规则体要求的最少事实，验证成本极低
- 利用 MAGNN 的单调性：D_base 的任何扩展都不会降低目标节点的输出
解释性规则（Theorem 6, Ω 语言）:
- 由于 MAGNN 无法用 FOL 等价表示（Proposition 1：判断"至少一半邻居满足条件"超越 FOL），转向提供 sound 解释
- 定义 Ω 语言：引入新算子 ∃ₙP.(C₁,...,Cₙ)（存在 n 个不同邻居分别满足不同条件）+ ≤mP.⊤（至多 m 个邻居）
- 对给定预测 A(a)，沿 L 层 GNN 的 L-hop 邻域递归构造规则体 C_L^a
- 保证：规则既能在原数据集上产生该预测（explain），又对所有数据集 sound
链接预测适配:
- 通过与 Tena Cucala et al. 的编码方案结合，将节点级规则展开为链接预测规则
- 链接预测场景下 sound 单调规则退化为 R₁(x,y) ∧ ... ∧ Rₘ₋₁(x,y) → Rₘ(x,y) 的形式

损失函数 / 训练策略¶

使用 Binary Cross Entropy loss + Adam 优化器（lr=0.001）
训练 8000 epochs，50 epochs early stopping
非负权重约束：每步优化后将负权重 clamp 到 0
2 层 GNN, ReLU + Sigmoid 激活, 隐藏维度 = 2×输入维度
分类阈值在验证集上网格搜索（10⁸ 个候选）

实验关键数据¶

主实验¶

模型性能（Mean-GNN, 标准 vs 非负权重）:

数据集	权重类型	Acc(%)	Prec(%)	Rec(%)	F1(%)
LUBM	Standard	97.1	96.9	97.2	97.1
LUBM	Non-Neg	91.5	87.8	96.4	91.9
WN18RRv1	Standard	93.7	98.5	88.8	93.4
WN18RRv1	Non-Neg	95.5	98.1	92.7	95.3
FB237v1	Standard	68.7	95.4	39.3	55.7
FB237v1	Non-Neg	71.8	75.4	64.8	69.7
NELLv1	Standard	75.2	93.8	53.4	65.7
NELLv1	Non-Neg	93.4	88.8	99.4	93.8

非负权重限制在基准数据集上反而提升性能（WN18RRv1、FB237v1、NELLv1）。

消融实验¶

提取的 sound 单调规则数量:

数据集	总数	仅一元	仅二元	混合
LUBM	11.6	1.4	9.8	0.4
WN-hier	22.6	15.6	0	7
FB237v1	136	136	0	0
WN18RRv1	0	0	0	0
NELLv1	1	1	0	0

LUBM 解释性规则统计: - 1990 个 true positive 预测中，仅 22 个无法用 Theorem 3 形式解释 - 未优化规则平均 25 个体原子，优化后平均 11 个

关键发现¶

限制非负权重对 mean-GNN 性能影响较小，在部分基准（WN18RRv1, FB237v1, NELLv1）上甚至提升性能——可能因正则化效应
FB237v1 提取 136 条 sound 规则但包含 29 条空体规则（如 ⊤ → R(x,y)），暴露了模型学到的荒谬推理
WN18RRv1 和 NELLv1 几乎无 sound 单调规则，表明 mean-GNN 的单调规则表达力确实受限
LUBM 上发现模型学到 ⊤ ⊑ Publication（万物皆论文）和 GraduateStudent ⊑ ResearchAssistant（所有研究生都是助研）等荒谬规则，证明了可解释性的重要性
与 sum-GNN 对比：sum-GNN 可恢复 WN-sym 的全部单调规则，但 mean-GNN 几乎不能，说明在需要可证 soundness 时 sum/max 可能更优

亮点与洞察¶

理论深度: Theorem 3 揭示 MAGNN 的 sound 单调规则空间极其受限——这是关于 mean 聚合的首个刻画性结果
实用价值: 提供了可操作的规则验证流程（Proposition 4, 单次前向传播即可验证）和解释生成方法
反直觉发现: 尽管 mean-GNN 在测试集上表现良好，提取的 sound 规则却暴露了模型学到的荒谬推理——说明准确率不等于可信度
联结理论与实践: 理论证明 MAGNN 超越 FOL（Proposition 1），但在实际基准上仍可有效提取解释

局限与展望¶

搜索空间指数增长: 规则空间 δ·2^(δ·|Col|) 随关系数增长指数爆炸，FB237v1 已需限制为仅 1 个体原子
ELUQ 是否为最大单调片段？ 这是开放问题，可能存在其他可 sound 的非 ELUQ 单调规则
分类阈值的选择: 使用 ≥ 而非 > 会产生完全不同的理论结果，论文仅处理了一种
解释性规则可能很长: 未优化时平均 25 个体原子，可读性较差
仅考虑 2 层 GNN，更深模型的规则提取尚未探索

评分¶

新颖性: ⭐⭐⭐⭐ 首次为最常用的 mean 聚合 GNN 建立 sound 规则理论
实验充分度: ⭐⭐⭐ 覆盖多个基准但数据集规模有限且仅 2 层模型
写作质量: ⭐⭐⭐⭐ 理论叙述严谨清晰，证明草图有助理解
价值: ⭐⭐⭐⭐ 填补重要理论空白，sound 解释对可信 AI 意义重大