从溯因解释到SGCs中节点分类的全局逻辑规则

# 从溯因解释到SGC节点分类的全局逻辑规则
来源：https://arxiv.org/html/2608.17103
###### 摘要

图神经网络（GNNs）在节点分类任务中取得了卓越性能，这激发了人们对其预测解释方法日益增长的兴趣。近期基于逻辑的方法（如LogicXGNN）从解释性子图集合中为图神经网络推导出全局逻辑规则。然而，这些子图虽具信息量，却可能包含冗余的、针对特定节点的结构信息，从而限制了所提取规则的泛化能力。本文针对简单图卷积（SGC）网络中的节点分类问题，提出了一种基于逻辑的框架，该框架采用最小溯因解释作为规则提取的中间表示。对于每个节点，我们计算一个足以保持预测类别的最小节点-特征对集合。随后利用这些解释训练决策树，进而提取全局逻辑规则。在基准数据集上的实验表明，所提框架能在保持与原始SGC模型高度保真度的同时，生成紧凑的全局规则。

## 1 引言

图神经网络已成为属性图节点分类的标准工具，其应用涵盖从引用网络中的文档分类到知识图中的实体分类[6, 4]。随着这些模型在科学与操作流程决策中的应用，解释单个节点预测并刻画模型整体行为已成为核心关注点。近期的综述文献围绕两个维度展开：实例级方法解释单个预测，模型级方法刻画全局行为[13]。

近期一条研究路径通过符号逻辑来解决此问题。LogicXGNN[3]等方法通过为每个节点定义两个互补谓词来推导GNN的全局逻辑规则。第一个是结构组件，通过对节点的局部多跳感受野进行Weisfeiler–Lehman哈希得到；第二个是嵌入组件，通过将学习到的节点表示中一组信息丰富的维度根据阈值二值化得到；这些维度和阈值由拟合在图级平均池化嵌入及模型预测上的决策树选择。随后，正确分类的实例被编码为这些谓词上的二元向量，一个针对模型预测训练的决策树提炼出每类一组的逻辑规则，每条规则都是谓词合取的析取。随后的接地步骤通过收集代表性子图（即激活该谓词的节点局部邻域）将每个谓词关联回输入；然后在一个规范化的、结构感知的子图内节点特征拼接上拟合每个谓词的决策树，得到将谓词连接到输入特征的接地规则。然而，该系列研究的主要论述和实验均针对图分类任务进行，报告的基准方法如GLGExplainer和GraphTrail[2, 1]也在相同设置下评估。LogicXGNN草拟了向节点级任务的扩展，但未开发或评估它。因此，基于规则的节点分类全局解释仍相对未被探索，并且该类方法使用的谓词在节点级别没有形式上的充分性保证。

简单图卷积（SGC）[12]是本情境下基于规则解释的自然目标。SGC在标准节点分类基准上与GCN及其他最先进的图神经网络性能相当，尽管它移除了消息传递层之间的非线性，并将得到的变换折叠为应用于固定特征传播的单一线性分类器。因此，SGC的对数几率是节点特征的线性函数。这一特性已被近期工作利用，即将非线性GNN蒸馏为SGC，并从中提取节点级解释而非从原始模型提取[10, 11]；类似地，围绕SGC构建的解释流程原则上可通过先结合一个蒸馏步骤应用于其他节点分类GNN，代价是额外的近似。

另一条并行工作线使用溯因解释（AXps）[5, 9]。AXp是一个最小的输入特征赋值子集，它与模型一起蕴含预测类别：一旦这个子集被固定，无论其余输入如何变化，模型的输出都不会改变。因此，AXps为预测提供了形式化的充分性和不可约性保证，并且对于输入为线性的分类器，AXp可以通过多项式时间计算，而非通过组合搜索[8]。然而，这些方法尚未直接应用于GNN。

为解决这些先前工作的局限性，我们提出了AXSGC（基于溯因的SGC解释），一种用于SGC节点分类的基于逻辑的方法。对于每个节点，我们从SGC分类器中提取节点-特征级别的AXp，并使用这些AXp作为推导全局规则的中间表示。规则提取应用于决定每个节点预测的节点-特征对集合，其不可约性由AXp公式保证。我们通过利用SGC分数的线性性质，在多项式时间内计算这些AXps。

总体而言，我们的方法分三个阶段运行。首先，对于每个节点，我们计算一个节点-特征对子集，其本身足以固定SGC的预测。其次，将得到的集合编码为基于距离索引谓词的向量，形式为“目标节点给定跳数距离处的节点特征”，它抽象了贡献邻居的身份，同时保留其与目标节点的距离。这些向量与SGC预测（作为标签）配对，用于训练决策树，从中读出每类规则。第三，全局逻辑规则直接从决策树的根到叶路径读出，每个叶节点标记其预测类别，每条路径被解读为基于距离索引谓词的合取式。

因此，每个AXp充当局部和全局阶段之间的桥梁：它既是为单个节点返回的节点-特征AXp（NF-AXp），同时也是推导全局每类规则的输入。

我们在基准节点分类数据集上评估AXSGC，并报告其相对于LogicXGNN[3]的内在保真度，LogicXGNN是GNN的一个代表性近期基于规则的全局解释方法。我们的实验报告了AXps的大小、所得每类规则的大小，以及规则在所考虑的基准上对SGC模型的内在保真度。在这些基准上，我们的方法在保真度上比LogicXGNN最高提升30.2%，并提取出最多减少83.8%的规则。

## 2 预备知识

本节固定后续章节中使用的符号。我们首先回顾SGC分类器，并指出使其适合形式化解释的性质。然后回顾形式化可解释性中的溯因解释抽象概念，这为下一节开发的方法提供了概念基础。

### 2.1 简单图卷积

令 $G=(V,E)$ 是一个无向图，包含 $n=|V|$ 个节点，邻接矩阵 $\mathbf{A} \in \{0,1\}^{n \times n}$，以及节点特征矩阵 $\mathbf{X} \in \mathbb{R}^{n \times d}$，其中 $d$ 是节点特征数量，$X_{u,j}$ 是节点 $u$ 处特征 $j$ 的值。在本工作考虑的大多数数据集中，节点属性表示为二值词袋向量。因此，$X_{u,j} \in \{0,1\}$，其中 $X_{u,j}=1$ 表示项 $j$ 出现在与节点 $u$ 关联的文档中，$X_{u,j}=0$ 表示其缺失。因此，在本文中，我们假设节点特征是布尔型的。令 $\mathbf{I} \in \mathbb{R}^{n \times n}$ 为单位矩阵。增广邻接矩阵 $\mathbf{A} + \mathbf{I}$ 为每个节点添加了自环，因此每个节点除了聚合其邻居的特征外，也聚合其自身的特征。令 $\tilde{\mathbf{D}}$ 为 $\mathbf{A} + \mathbf{I}$ 的对角度数矩阵，其中 $\tilde{D}_{ii} = \sum_{k=1}^{n} (\mathbf{A} + \mathbf{I})_{ik}$，这里 $\tilde{D}_{ii}$ 是节点 $i$ 在增广图中的度数。通过对称归一化 $\tilde{\mathbf{D}}^{-1/2}$ 作用于两侧，将传播算子的谱界限定在

$$
\hat{\mathbf{A}} \;=\; \tilde{\mathbf{D}}^{-1/2}\,(\mathbf{A} + \mathbf{I})\,\tilde{\mathbf{D}}^{-1/2}. \tag{1}
$$

条目 $\hat{A}_{v,u}$ 编码了节点 $u$ 在经过自环增强和对称归一化后对节点 $v$ 的一步加权影响。

令 $\boldsymbol{\Theta} \in \mathbb{R}^{d \times C}$ 为学习到的权重矩阵，其中 $C$ 是类别数，每列 $\boldsymbol{\Theta}_{:,c} \in \mathbb{R}^{d}$ 是针对类别 $c$ 的线性分类器，其中 $\Theta_{j,c}$ 是在为类别 $c$ 评分时分配给特征 $j$ 的权重。令 $K \in \mathbb{N}$ 为特征传播的次数；$K$ 与 GCN 中消息传递层的数量作用相同，控制信息在分类前能传播多远。分数矩阵由下式给出

$$
\hat{\mathbf{Y}} \;=\; \mathrm{softmax}\bigl(\hat{\mathbf{A}}^{K}\,\mathbf{X}\,\boldsymbol{\Theta}\bigr), \tag{2}
$$

其中按行进行 softmax，$\hat{\mathbf{Y}}$ 的第 $v$ 行是节点 $v$ 处的预测类别分布。节点 $v$ 的预测类别为

$$
c^{*}(v) \;=\; \arg\max_{c \in \{1,\dots,C\}}\bigl(\hat{\mathbf{A}}^{K}\,\mathbf{X}\,\boldsymbol{\Theta}\bigr)_{v,c}, \tag{3}
$$

其中 $c^{*}(v)$ 是 SGC 分配给节点 $v$ 的类别。

### 2.2 溯因解释

溯因解释（AXp）[5, 9] 是一个最小的输入赋值子集，其值决定了模型的预测。

###### 定义 1（溯因解释）。

令 $\phi: \mathcal{X} \to \mathcal{Y}$ 是一个分类器，其特征空间分解为 $\mathcal{X} = \prod_{i \in F} \mathcal{X}_i$，其中 $F$ 是特征的有限索引集，$\mathcal{X}_i$ 是特征 $i$ 的定义域，并令 $x \in \mathcal{X}$ 是一个输入，其预测为 $y = \phi(x)$。子集 $H \subseteq F$ 是 $\phi(x)=y$ 的一个 *溯因解释*（AXp），如果 (a) 对于每个 $x' \in \mathcal{X}$ 满足 $x'_i = x_i$（对所有 $i \in H$），都有 $\phi(x') = y$，且 (b) $H$ 的任何真子集都不满足 (a)。

在定义 1 中，$\phi$ 是被解释预测的分类器，$F$ 是可解释输入的集合，$\mathcal{X}_i$ 是输入 $i$ 的定义域，$x$ 是观测输入，$y = \phi(x)$ 是在 $x$ 处的预测，$H$ 是解释固定的输入子集，$x'$ 遍历所有在 $H$ 上与 $x$ 一致的替代输入。条款 (a) 表明，只要 $H$ 上的值被固定，对剩余输入 $F \setminus H$ 的任何扰动都不会改变预测。条款 (b) 识别了模型实际依赖的输入，而非碰巧也足够大的超集：没有 (b)，$H=F$ 将平凡地满足 (a)。

## 3 用于选择节点-特征对的 AXps

本节开发的构造将定义 1 的充分性和最小性条件转化为解释 SGC 节点预测的具体过程。我们分两步进行。第 3.1 小节将 SGC 分类规则重新表述为节点-特征对上的线性不等式组，揭示了 AXp 计算所利用的结构。第 3.2 小节将定义 1 适配到 SGC 分类器的节点 $v$，并给出一个贪心删除过程，该过程使用与候选集大小成线性关系的模型查询次数返回一个节点-特征级别的 AXp。

### 3.1 用于 SGC 预测的线性不等式

固定 $\hat{\mathbf{A}}$ 和 $\boldsymbol{\Theta}$。条目 $(\hat{\mathbf{A}}^{K})_{v,u}$ 是在 $K$ 步传播后节点 $u$ 的特征向量进入节点 $v$ 处分数的总权重；当且仅当 $u$ 在增广图上最多 $K$ 跳可达 $v$ 时，该条目非零。此条目仅通过增广图的结构量（度数和从 $v$ 到 $u$ 长度不超过 $K$ 的游走数）依赖于 $u$，特别是当 $v$ 到 $u$ 的最短路径距离超过 $K$ 时它为零。我们用 $\mathcal{N}_K(v) := \{u \in V : (\hat{\mathbf{A}}^{K})_{v,u} \neq 0\}$ 表示 $v$ 的 $K$ 跳感受野，并注意到 $v \in \mathcal{N}_K(v)$。只有 $\mathcal{N}_K(v)$ 中节点的特征值可以改变 $v$ 处的分数，因此它们是 $c^{*}(v)$ 解释的唯一候选者。

将 $\hat{\mathbf{A}}^{K}\,\mathbf{X}$ 逐项展开为 $(\hat{\mathbf{A}}^{K}\,\mathbf{X})_{v,j} = \sum_{u \in V} (\hat{\mathbf{A}}^{K})_{v,u}\,X_{u,j}$ 并与 $\boldsymbol{\Theta}$ 收缩，节点 $v$ 处类别 $c$ 的未归一化分数可分解为节点-特征对上的线性组合：

$$
(\hat{\mathbf{A}}^{K}\,\mathbf{X}\,\boldsymbol{\Theta})_{v,c} \;=\; \sum_{(u,j) \in \mathcal{N}_K(v) \times \{1,\dots,d\}} \alpha^{v,c}_{u,j}\,X_{u,j}, \qquad \alpha^{v,c}_{u,j} := (\hat{\mathbf{A}}^{K})_{v,u}\,\Theta_{j,c}. \tag{4}
$$

系数 $\alpha^{v,c}_{u,j}$ 是布尔输入 $X_{u,j}$ 进入节点 $v$ 处类别 $c$ 未归一化分数的固定权重。它分解为一个结构项 $(\hat{\mathbf{A}}^{K})_{v,u}$（记录 $u$ 到达 $v$ 的强度）和一个语义项 $\Theta_{j,c}$（记录特征 $j$ 对类别 $c$ 的投票强度）。这些系数仅依赖于 $\hat{\mathbf{A}}$ 和 $\boldsymbol{\Theta}$，不依赖于输入特征，因此可以为每个节点预先计算一次，并在每个 $v$ 的每次解释查询中重用。Softmax 是严格单调的，因此预测类别由未归一化分数的 argmax 决定。因此，预测 $c^{*}(v) = c$ 成立当且仅当，对于每个竞争类别 $c' \neq c$，由列 $\boldsymbol{\Theta}_{:,c}$ 诱导的线性分数在相同的感受野特征值 $X_{u,j}$ 上超过由列 $\boldsymbol{\Theta}_{:,c'}$ 诱导的线性分数。因此，$v$ 处的分类规则是在布尔输入 $\{X_{u,j}\}_{(u,j) \in \mathcal{N}_K(v) \times \{1,\dots,d\}}$ 上的 $C-1$ 个线性不等式系统：

$$
\sum_{(u,j) \in \mathcal{N}_K(v) \times \{1,\dots,d\}} \bigl(\alpha^{v,c}_{u,j} - \alpha^{v,c'}_{u,j}\bigr)\,X_{u,j} \;>\; 0, \qquad \forall c' \neq c. \tag{5}
$$

**