基于路径的梯度提升在图级预测中的应用

# 基于路径的梯度提升用于图级预测

来源: https://arxiv.org/html/2605.08102
Claudio Meggio 通信作者: [email protected] 奥斯陆大学数学系, 挪威奥斯陆 Riccardo De Bin 奥斯陆大学数学系, 挪威奥斯陆

###### 摘要

我们提出了 **PathBoost**，一种用于图级分类和回归的梯度树提升方法，该方法直接从输入图结构中学习判别性的基于路径的特征。在先前的工作（针对特定化学应用定制）基础上，**PathBoost** 引入了三个关键扩展：(i) 通过带有逻辑损失的梯度提升适配二元分类，(ii) 通过基于前缀的分解将多个节点和边属性纳入路径特征空间，以及 (iii) 基于类别属性多样性的自动锚点节点选择，消除了用户指定所考虑路径特征起始点的需求。我们在几个基准数据集上将 **PathBoost** 与图神经网络（GNNs）和图核方法进行了比较，在其中一半的数据集上获得了更好的结果，在其余数据集上获得了可比的结果。**PathBoost** 在平均节点数较多的图上表现更好。总体而言，结果表明基于路径的提升方法可以与更复杂的黑盒方法相竞争。

## 亮点

- • 使用路径特征进行图级预测的梯度提升框架
- • 前缀分解丰富了包含节点和边属性的路径
- • 自动锚点节点选择无需领域知识
- • 实证研究表明与现有方法相比具有竞争力

关键词：图分类，梯度树提升，路径特征，可解释机器学习，基准评估

## 1 引言

图级分类是机器学习中的一个基本问题，应用范围从分子性质预测和药物发现到社交网络分析和程序验证。挑战在于学习整个图的有意义表示，既要捕捉局部结构模式又要捕捉全局拓扑特性，同时保持计算效率和可解释性。

近年来，图神经网络（GNNs）在图分类基准测试中占据主导地位。这些模型利用消息传递机制 [Gilmer et al., 2017](https://arxiv.org/html/2605.08102#bib.bib13) 学习节点嵌入，然后聚合以产生图级表示。在每一层中，节点从其邻居聚合信息并更新其表示。图卷积网络 [Kipf and Welling, 2017](https://arxiv.org/html/2605.08102#bib.bib10) 在图上引入了受频谱启发的卷积滤波器，而图注意力网络 [Veličković et al., 2018](https://arxiv.org/html/2605.08102#bib.bib11) 引入了注意力机制以学习自适应的邻域加权。GraphSAGE [Hamilton et al., 2017](https://arxiv.org/html/2605.08102#bib.bib12) 提出了基于采样的聚合方法，用于大图上的归纳学习。虽然 GNNs 取得了令人印象深刻的实证结果，但它们存在几个局限性：(i) 它们通常需要大量的训练数据才能有效泛化 [Ding et al., 2024](https://arxiv.org/html/2605.08102#bib.bib23)，(ii) 它们的学习表示难以解释，使得理解哪些图子结构驱动预测变得具有挑战性 [Agarwal et al., 2023](https://arxiv.org/html/2605.08102#bib.bib21)，以及 (iii) 它们在样本有限的小数据集上的表现不一致 [Rakaraddi et al., 2024](https://arxiv.org/html/2605.08102#bib.bib22)。

在 GNNs 兴起之前，结合支持向量机（SVMs）的图核是图分类和回归的标准方法。这些方法基于领域知识显式地工程化图特征，例如计数特定的子结构、比较最短路径或测量图编辑距离。Weisfeiler–Leman (WL) 子树核 [Shervashidze et al., 2011](https://arxiv.org/html/2605.08102#bib.bib2) 通过哈希邻域信息迭代地细化节点标签，产生近似于 WL 同构测试的子树模式特征。WL 最优分配变体 [Kriege et al., 2016](https://arxiv.org/html/2605.08102#bib.bib15) 通过标签节点层次结构之间的最优分配匹配节点特征，从而改进了原始变体。最短路径核 [Borgwardt and Kriegel, 2005](https://arxiv.org/html/2605.08102#bib.bib5) 基于节点对之间最短路径长度的分布比较图，而图let核 [Shervashidze et al., 2009](https://arxiv.org/html/2605.08102#bib.bib4) 计数小诱导子图以捕捉局部结构基序。Morris 等人 [2020](https://arxiv.org/html/2605.08102#bib.bib1) 的系统比较表明，图核在小规模数据集上仍然具有高度竞争力，通常匹配或超过当代 GNN 的性能。这一发现激励了继续探索非神经网络方法，这些方法可以结合显式特征构建的优势与灵活的学习算法。虽然图核方法在理论上可解释且基础扎实，但它们面临自身的挑战：(i) 如果没有合适的核选择，它们可能无法捕捉复杂的模式，以及 (ii) 对于大图或大数据集，计算成本可能变得过高 [Kriege et al., 2020](https://arxiv.org/html/2605.08102#bib.bib24)。

梯度提升代表了连接这两种方法的替代范式：它将显式特征构建的可解释性与基于梯度的方法的自适应学习相结合。几种方法已将提升应用于图或基于子结构的分类和回归。Kudo 等人 [2004](https://arxiv.org/html/2605.08102#bib.bib16) 提出了一种基于标签子图的提升方法，使用模式生长挖掘算法，其中子图特征首先被枚举，然后作为弱学习者在 AdaBoost 框架中使用。Saigo 等人 [2009](https://arxiv.org/html/2605.08102#bib.bib17) 将其扩展为 gBoost，该方法将数学规划与提升集成以选择判别性子图模式。前者仅适用于分类任务，而后者也已实现用于回归。

这些提升方法的一个共同特征是它们遵循两阶段方法：首先枚举候选图模式，然后在枚举的特征上应用提升。在最近一项关于过渡金属化合物的分析中，Meggio 等人 [2026](https://arxiv.org/html/2605.08102#bib.bib20) 开发了一种用于分子图回归的提升方法，该方法*同时*处理图探索和模型拟合。在每次提升迭代中，算法选择最有信息量的路径，然后仅通过考虑该路径的单节点扩展来扩展特征空间。这种惰性扩展避免了预先枚举的组合成本，并自然地使搜索集中在图的有信息量区域。然而，Meggio 等人 [2026](https://arxiv.org/html/2605.08102#bib.bib20) 的方法是为分析一类特定图（已知为过渡金属化合物，TMCs）及其特定特性而开发的。具体来说，TMC 包含一个金属中心，可用作指定的锚点节点，即所考虑路径特征的起点。此外，原始方法侧重于回归设置，不允许使用节点或边属性。

在本文中，我们将原始算法扩展到更一般的设置，如下所示：(i) 我们通过在带有逻辑损失的梯度提升中启用分类，(ii) 我们将多个节点和边属性作为路径特征的一部分纳入，以及 (iii) 我们基于节点标签多样性自动选择锚点节点。这些扩展使我们的方法能够在图分类基准上与最先进的 GNNs 和图核竞争，同时保留原始框架的可解释性优势。在 TUDatasets 基准上的实证评估表明，我们的新方法在多个数据集上实现了与现有竞争对手相比具有竞争力或更优越的性能。

本文的其余部分组织如下。第 2 节 [2](https://arxiv.org/html/2605.08102#S2) 首先简要回顾原始算法，然后介绍新的扩展，即属性丰富路径特征的正式化、自动锚点节点选择以及适配分类设置。第 3 节 [3](https://arxiv.org/html/2605.08102#S3) 描述了实验设置，包括用于比较的数据集和竞争方法。第 4 节 [4](https://arxiv.org/html/2605.08102#S4) 报告实证结果并对发现进行评论。最后，第 5 节 [5](https://arxiv.org/html/2605.08102#S5) 总结本文，讨论所提出方法的优势和劣势。

## 2 方法

我们首先总结 Meggio 等人 [2026](https://arxiv.org/html/2605.08102#bib.bib20) 的原始方法，然后介绍新方法 **PathBoost** 背后的扩展，这是一种用于图结构输入数据的一般监督学习方法。

### 2.1 背景

Meggio 等人 [2026](https://arxiv.org/html/2605.08102#bib.bib20) 介绍了一种用于图结构数据回归任务的基于提升的框架，特别关注代表过渡金属化合物的分子图。我们在此总结该框架的关键要素，使用相同的符号，我们在后续章节中将其扩展到 **PathBoost** 的分类和属性丰富设置。

#### 图表示。

我们考虑定义为三元组 $G=(V,E,L)$ 的带节点标签的无向图，其中 $V=\{v_1,\dots,v_d\}$ 是节点集，$E \subset V \times V$ 是无向边集，$L: V \to \mathcal{L}$ 是标记函数，为每个节点分配来自有限集 $\mathcal{L}=\{l^{(1)},\dots,l^{(K)}\}$ 的标签。在原始应用中，节点代表原子，边代表键，标签对应于原子符号。

#### 路径和带标签的路径。

图中长度为 $m-1$ 的路径是不同节点序列 $(v_{j_1}, v_{j_2}, \dots, v_{j_m})$，其中索引 $j_1, \dots, j_m$ 形成 $\{1, \dots, d\}$ 的子集，使得每对连续节点由边连接。对应的*带标签路径*是节点标签序列：

$$
\boldsymbol{l}_u = (L(v_{j_1}), L(v_{j_2}), \dots, L(v_{j_m})), \quad (1)
$$

其中 $u$ 索引带标签路径。我们写 $M[G_i, \boldsymbol{l}_u]$ 表示带标签路径 $\boldsymbol{l}_u$ 在图 $G_i$ 中出现的次数。

#### 锚点节点。

原始框架假设每个图中有一个指定的锚点节点 $v^*$，所有路径都源自于此。在原始工作的分子设置中，此锚点节点是化合物的金属中心。

#### 特征映射和加性模型。

给定一系列带标签路径 $\mathcal{P}=\{\boldsymbol{l}_u\}_{u=1}^p$，每个图 $G_i$ 被映射到一个计数向量：

$$
h(G_i; \mathcal{P}) = (M[G_i, \boldsymbol{l}_1], \dots, M[G_i, \boldsymbol{l}_p]). \quad (2)
$$

基于计数的表示，预测模型在路径上采取加性形式：

$$
F(G_i; \beta) = \sum_{u=1}^p \sum_{c=0}^{c_u^{\max}} \beta_{u,c} \cdot \mathds{1}[\min(M[G_i, \boldsymbol{l}_u], c_u^{\max}) = c], \quad (3)
$$

其中 $\beta_{u,c}$ 是与观察到路径 $\boldsymbol{l}_u$ 恰好 $c$ 次相关联的系数，$c_u^{\max}$ 是训练数据中观察到的最大计数。

#### 学习过程。

学习算法背后的关键思想是在标准的梯度提升过程 [Friedman, 2001](https://arxiv.org/html/2605.08102#bib.bib18), [2002](https://arxiv.org/html/2605.08102#bib.bib25) 中迭代地扩展基于路径的特征空间，使用树桩作为基础学习者。在每次迭代中，算法：(i) 计算损失的负梯度；(ii) 拟合树桩以选择最有信息量的路径；(iii) 更新模型。至关重要的是，当首次选择一条路径时，算法通过添加在训练数据中发现的所有该路径的单节点扩展来扩展特征矩阵。具体而言，对于训练集中的每个图，算法扫描所选路径的出现情况并记录哪些节点立即扩展它；在数据集中找到的每个不同扩展成为后续迭代中特征空间中的新候选路径。特征空间的这种迭代扩展允许算法在不进行详尽枚举的情况下发现信息丰富的子结构。该框架的核心思想——自适应路径选择、在结构化特征上的提升以及可解释建模——构成了 **PathBoost** 的基础。

#### 变量重要性。

作为一种提升算法，Meggio 等人 [2026](https://arxiv.org/html/2605.08102#bib.bib20) 的框架具有评估最终模型中每条路径重要性的自然机制。在每次提升迭代中，记录所选路径实现的损失函数减少量。然后通过对给定路径被选择的所有迭代中的这些贡献进行聚合来定义路径重要性。Meggio 等人 [2026](https://arxiv.org/html/2605.08102#bib.bib20) 提出了两种互补的变体：一种将所有迭代中归因于每条路径的绝对损失减少量相加；另一种测量*相对*减少量，定义为每次迭代中选定路径与第二佳候选路径之间的损失改进差异。相对变体避免了因可被相关替代品替换而夸大路径重要性，代价是可能低估类似信息丰富路径组的重要性。两种度量都相对于最重要的路径缩放到范围 $[0, 100]$。

### 2.2 属性丰富的路径特征

**PathBoost** 的一个核心增强是其能够将多个节点和边属性作为基于路径特征的一部分纳入。虽然原始框架侧重于带标签路径的频率基表示，但 **PathBoost** 包含属性级信息，从而实现更丰富且更具判别性的图表示。

在许多图分类任务中，节点和边标注有多种属性（例如，原子序数、键类型、电负性）。这些属性通常携带补充纯结构信息的预测信号。为了利用这一点，**PathBoost** 构建了一个特征空间，其中每个特征不仅对应于带标签路径的存在，还对应于与该路径相关联的额外属性。**PathBoost** 采用两步方法。首先，仅基于频率选择候选路径，遵循原始方法的原则。只有在路径被选择后，其关联的属性才会用于拟合。我们现在形式化这一过程。

#### 属性函数。

我们扩展图...