【ICLR 2021】BOOST THEN CONVOLVE: GRADIENT BOOSTING MEETS GRAPH NEURAL NETWORKS

type

status

date

slug

summary

摘要

图神经网络（GNNs）是处理图表示学习任务的强大模型，在许多应用中取得了成功。而梯度提升决策树（GBDT）在处理异构表格数据时，往往比其他机器学习方法表现更优。那么，对于具有表格化节点特征的图数据，该使用什么方法呢？以往的 GNN 模型大多聚焦于具有同质稀疏特征的网络，而我们发现，这些模型在异构场景下表现并不理想。在这项工作中，我们提出了一种新颖的架构，将 GBDT 和 GNN 联合训练，从而结合两者的优势：GBDT 模型处理异构特征，而 GNN 负责建模图结构。通过允许新树拟合 GNN 的梯度更新，我们实现了端到端的优化。在与当前最先进的 GBDT 和 GNN 模型的广泛实验对比中，我们证明了在多种具有表格化特征的图数据上，该方法显著提升了性能。代码已开源：https://github.com/nd7141/bgnn。

Intro 概要

Intro 的核心在于强调目前 GNN 的研究局限性，指出它们主要处理稀疏、同质数据，而现实中的图数据往往包含复杂的表格化特征（异构数据，节点属性丰富）。针对这种场景，GBDT 目前表现更优，但 GNN 在此方向上仍有很大的研究潜力。

这种问题的研究不仅有理论意义（扩展 GNN 的适用范围），也有实际价值（更好地解决现实中的 AI 问题）

该工作尝试将GNN和GBDT结合起来：“毫无疑问，GBDT 和 GNN 方法各有显著优势。那么是否可以同时利用两者的优点？此前所有试图结合梯度提升和神经网络的方法（Arik & Pfister, 2020；Popov et al., 2019；Badirli et al., 2020）都存在计算开销大、不考虑图结构数据，并且缺乏 GNN 架构中引入的关系偏置等问题。有关相关文献的更详细比较，请参阅附录 A。据我们所知，目前的工作是首次探索将 GBDT 模型用于图结构数据的研究。”

在本文中，我们提出了一种用于具有表格数据的图的全新学习架构——BGNN，该架构结合了 GBDT 在表格化节点特征上的学习能力和 GNN 利用图拓扑结构优化预测的能力。这使得 BGNN 能够继承梯度提升方法的优势（异构学习和可解释性）以及图神经网络的优势（表示学习和端到端训练）。总体而言，我们的贡献如下：
我们设计了一种新颖的通用架构，将 GBDT 和 GNN 结合到一个独特的流程中。 据我们所知，这是首次系统性地研究 GBDT 在图结构数据上的应用的工作。
我们通过迭代添加新树来拟合 GNN 的梯度更新，克服了 GBDT 端到端训练的挑战。 这使我们能够将网络拓扑结构中的误差信号反向传播至 GBDT。
我们对该方法进行了广泛的评估，并与强基线模型进行了比较，解决了节点预测任务。 结果表明，在具有表格数据的各种真实图上，我们的方法在异构节点回归和节点分类任务中表现出了一致的显著性能提升。
我们证明了我们的方法在训练过程中具有比最先进 GNN 模型更快的损失收敛速度，因此效率更高。 此外，学习到的表示在潜在空间中表现出明显的结构性，这进一步证明了我们方法的表达能力。

难点

除了节点特征之外，如何在本来是针对表型数据设计的模型中传播节点之间的关系信号？

GBDT和GNN的训练方法截然不同，如何让GBFT与GNN一起进行端到端训练呢？

数据流：

一个循环：经过GBDT 变为 , 经过GNN变为
不断重复这个循环。每一次循环，GBDT的输入均为（Original input features）

Objective

GBDT:
GNN: Minimizing with steps of gradient desent.

一些概念

1. 梯度提升

概念

梯度提升是一种机器学习技术，通常用于构建高性能的回归和分类模型。它属于 集成学习 的范畴，通过结合多个弱学习器（通常是决策树）来构建一个更强的模型。

核心思想

梯度提升的核心思想是：

逐步改进：模型是逐步构建的，每一步都会在前一步的基础上进行改进。

加权学习错误：每个新模型都会特别关注已训练模型中表现较差的样本（即误差较大的样本）。

基于梯度优化：新模型的训练目标是最小化损失函数的梯度，即找到能够最大程度降低当前残差的方向。

工作原理

初始化一个简单的模型（比如常数值预测）。

计算当前模型的残差（即目标值与预测值之间的误差）。

训练一个新的弱学习器（通常是浅层决策树）来拟合这些残差。

将新模型的预测值加权后叠加到原始模型中。

重复步骤 2-4，直到达到预设的迭代次数或误差收敛。

梯度提升的特性

弱学习器：通常是浅层决策树。

高效性：能够在低偏差和低方差之间取得平衡。

灵活性：可以处理回归、分类和排序问题。

常见的梯度提升工具

XGBoost（极端梯度提升）：高效、常用于比赛。

LightGBM：速度更快，适合大规模数据。

CatBoost：对分类特征处理更友好。

梯度提升的优缺点

优点：

强大的预测能力。
对特征工程的依赖较少。
能有效处理非线性关系。

缺点：

训练时间可能较长。
对超参数比较敏感，需要精心调试。

2. 图神经网络（Graph Neural Networks, GNNs）

概念

图神经网络是一种深度学习架构，专门用于处理 图结构数据（如社交网络、知识图谱、分子结构等）。图是一种复杂的数据结构，包含节点（Nodes）和边（Edges）的关系。

GNN 的目标是通过捕获图中节点之间的关系及其属性，学习节点、边或整个图的有意义表示。

核心思想

图神经网络的核心思想是：

消息传递（Message Passing）：节点通过与邻居节点交换信息更新自身的表示。

聚合特征（Feature Aggregation）：每个节点的表示是其自身特征与邻居特征的聚合（如求和、平均或加权求和）。

图特征学习：通过多个图卷积层逐步捕获更深层次的图结构信息。

工作原理

输入：图的结构信息（邻接表或邻接矩阵）以及每个节点或边的特征。

消息传递：每个节点与其邻居节点进行信息交互，更新节点的隐藏状态。

特征聚合：通过聚合函数（如求和或平均）将邻居节点的特征聚合到当前节点。

多层传播：重复消息传递和聚合过程，捕获远距离节点之间的关系。

输出：学习到的节点嵌入（Node Embedding）、边嵌入（Edge Embedding）或整个图的嵌入（Graph Embedding）。

GNN 的特性

能够同时处理图的拓扑结构和节点/边的特征。

可以学习高维嵌入，适用于下游任务（如分类、回归、聚类等）。

常见的图神经网络模型

GCN（Graph Convolutional Networks）：

基于图卷积操作，通过邻接矩阵传播和聚合信息。

广泛应用于节点分类任务。

GraphSAGE：

使用采样的方法对邻居节点进行聚合，适合大规模图结构。

GAT（Graph Attention Networks）：

引入注意力机制，赋予不同邻居节点不同的重要性权重。

GIN（Graph Isomorphism Networks）：

对图同构问题有更强的表征能力。

Transformer on Graphs：

将 Transformer 的注意力机制引入到图结构处理中。

GNN 的优缺点

优点：

能够处理复杂的图结构数据。
适用于多种任务，如节点分类、图分类、链接预测等。
灵活性强，可处理异构图、多模态数据等。

缺点：

对大规模图的计算效率较低，可能需要采样方法。
过度叠加层数时可能导致过平滑（Over-smoothing）问题。

3. Sparse Data (稀疏数据)

解释：

稀疏数据指数据中大部分值为零或空值的情况。例如，独热编码（one-hot encoding）生成的高维特征向量中，只有一个位置为 1，其他位置均为 0。
稀疏数据通常出现在特征表示简单的场景，比如词袋模型或独热编码。

这里的应用背景：

当前 GNN 的研究更多聚焦于稀疏数据，例如简单的节点嵌入或基于词袋的统计特征，而非复杂的表格数据。

4. Homogeneous Node Embeddings (同质节点嵌入)

解释：

同质节点嵌入指节点的特征是统一类型的，比如所有节点都用同样的维度和表示方法（例如独热编码）进行编码。
这通常用于简单的图结构，比如每个节点只有一个类别标签，而无更多详细信息。

这里的应用背景：

当前的 GNN 通常假设节点嵌入是同质的（例如独热编码或图统计数据），但在现实中，节点的特征往往是复杂且多样的。

5. Bag-of-Words Representations (词袋表示)

解释：

词袋模型是一种简单的文本表示方法，它忽略了词序，仅统计每个词在文档中出现的频率。
这种方法也可以扩展到其他场景，例如统计节点的某些属性特征。

这里的应用背景：

词袋表示是一种稀疏数据形式，当前 GNN 研究常用它来表示节点特征，但这种表示方法缺乏语义信息，无法很好地表示复杂的节点属性。

6. Gradient Boosted Decision Trees (GBDT, 梯度提升决策树)

解释：

GBDT 是一种强大的机器学习方法，尤其适用于异构表格数据。它通过将多个弱学习器（通常是决策树）集成起来，逐步优化模型性能。
GBDT 擅长处理特征类型多样、缺失值多的情况，在许多实际应用中表现优异。

这里的应用背景：

在处理具有表格特征的图数据时，GBDT 比现有 GNN 模型更具优势，因此在这种异构场景中占据主导地位。