ICLR'21 当图神经网络遇上传统机器学习 x 2

Houye

发布于 2021-07-08 16:00:18

4490

发布于 2021-07-08 16:00:18

文章被收录于专栏：图与推荐

介绍2篇ICLR 2021的文章，其均尝试将传统机器学习方法(如AdaBoost和GBDT)与GNN结合，非常好玩~ 尽管看起来像是A+B式的创新论文，看了之后感觉还是有点东西的~

1. AdaGCN

论文标题：AdaGCN: Adaboosting graph convolutional networks into deep models
论文作者：Ke Sun; Zhangxing Zhu; Zhouchen Lin
论文地址：https://openreview.net/pdf?id=QkRbdiiEjM

题目

首先介绍AdaGCN，是把AdaBoost加入到GCN里的一个文章，主要挖掘图上不同层的邻居节点上的信息，并且利用AdaBoost加以整合，使其能够一定程度缓解过平滑问题。

1.1. 方法总概

不同于直接叠加多个图卷积层，AdaGCN在所有层之间共享相同的基本神经网络结构，并进行递归优化，这点类似于RNN构造。模型整体如图所示，

\theta

和

分别表示参数和节点权重。

AdaGCN的结构

大体上，这个流程可以简化成：

\begin{aligned} &\hat{A}^{l} X=\hat{A} \cdot\left(\hat{A}^{l-1} X\right)\quad(1) \\ &Z^{(l)}=f_{\theta}^{(l)}\left(\hat{A}^{l} X\right)\quad(2) \\ &Z=\operatorname{AdaBoost}\left(Z^{(l)}\right)\quad(3) \end{aligned}

等式(1)(2)两步可以看做一个基本的图网络操作，(3)则是在说将多层网络的输出用AdaBoost进行筛选。

具体而言，等式(1)的推导可以从一个最基本的GCN开始：

Z=\hat{A} \operatorname{ReLU}\left(\hat{A} X W^{(0)}\right) W^{(1)}

在多层时，忽略激活函数，合并邻接矩阵和权重矩阵后，这个模型可以化简为：

Z=\hat{A}^{l} X W^{(0)} W^{(1)} \cdots W^{(l-1)}=\hat{A}^{l} X \tilde{W}

其中，

\hat{A}^{l}

表示了

阶的邻居信息，

W^{(l)}

是

层的权重。

等式（2）表现为预测时所需要的图特征，我们通常用一个非线性函数

f_{\theta}

来得到图的表示

，

Z^{(l)}=f_{\theta}\left(\hat{A}^{l} X\right)

在等式（3）中，作者结合了AdaBoost，将GCN的每一层看做一个弱分类，并且采用了SAMME来更新每个节点权重。

e r r^{(l)}=\sum_{i=1}^{n} w_{i} \mathbb{I}\left(c_{i} \neq f_{\theta}^{(l)}\left(x_{i}\right)\right) / \sum_{i=1}^{n} w_{i}

\alpha^{(l)}=\log \frac{1-e r r^{(l)}}{e r r^{(l)}}+\log (K-1)

w_{i} \leftarrow w_{i} \cdot \exp \left(\alpha^{(l)} \cdot \mathbb{I}\left(c_{i} \neq f_{\theta}^{(l)}\left(x_{i}\right)\right)\right), i=1, \ldots, n

为了保证每个弱分类的效果都会比较好，就需要

\alpha^{(l)}

为正，进而需要

\left(1-e r r^{(l)}\right)>1 / K

（这个是09年的AdaBoost里说过的）。

最后，反应到预测标签上的形式为:

C(A, X)=\arg \max _{k} \sum_{l=0}^{L} \alpha^{(l)} f_{\theta}^{(l)}\left(\hat{A}^{l} X\right)

由于加入了Adaboost，作者也给出了模型的更新方式，主要体现在第5步和第6步，由于代码暂时还未放出来，就暂时先看一下伪代码。。。

AdaGCN

1.2. 实验

实验部分主要说了两件事，一个是这个AdaGCN是能够处理由多层GCN导致的过平滑问题，另一个是这个模型速度很快。

准确率随着层数变化

值得注意的是，AdaGCN（红线）能够在三个数据集的层数增加的情况下一致地提高性能。这意味着AdaGCN在构造深图模型的过程中可以有效地融合不同阶邻域的知识，避免了原始GCN的过平滑问题。另外，在层数较大的情况下，AdaGCN的性能波动比GCN小得多。

模型时间的对比，k表示拟合线性回归中的斜率

左图作者重点比较了AdaGCN与目前GNN的运行时间，可以看出AdaGCN的效率非常高。从右图可以观察到SGC（绿线）和GCN（红线）都呈线性增长趋势，这是由于模型堆叠计算会造成运算时间上升，而AdaGCN由于每一层都用

f_{\theta}

进行计算，所以相当于这一步算是并行计算。

2. BGNN

论文标题：Boost then Convolve: Gradient Boosting Meets Graph Neural Networks
论文作者：Sergei Ivanov; Liudmila Prokhorenkova
论文地址：https://arxiv.org/pdf/2101.08543.pdf

题目

这个是把GDBT塞到GNN里，主要看上的是怎么用图来做异构表格数据 （heterogeneous tabular data），叫做BGNN。作者利用GBDT模型建立了异构数据通用的超平面决策边界，然后利用GNN关系信息对预测进行细化。该方法可以与任意消息传递神经网络和梯度增强方法结合。

2.1. 方法总概

GBDT能够对表格数据有良好预测，这样就可以想办法来增强图网络的表现。因此作者就让GBDT与图网络结合，直接进行端到端学习。

BGNN模型流程

在这篇文章里的图网络是针对节点定义的：

\mathbf{x}_{v}^{t}=\text { COMBINE }^{t}\left(\mathbf{x}_{v}^{t-1}, \text { AGGREGATE }^{t}\left(\left\{\left(\mathbf{x}_{w}^{t-1}, \mathbf{x}_{v}^{t-1}\right):(w, v) \in E\right\}\right)\right)

这里的

是指第

层。

同时，GBDT是根据多个弱分类器

h(x)

增强的一种模型，在第

次迭代时，式子可以被写成：

f^{t}(\mathbf{x})=f^{t-1}(\mathbf{x})+\epsilon h^{t}(\mathbf{x})

(PS：经过查证源码可以发现这里的两个

实际上并没有什么关系，在后续的表述中

更多指的是GBDT里的迭代更新。)

作者将

\mathcal{H}

定义为决策树，决策树将特征空间划分为不相交的叶子，这些叶子的表现由最小化损失构成。设

R_j

为子树，赋值为

a_j

来估计对应的

。在本文中，

a_j

为平均值叶子的负梯度值。

h^{t}=\underset{h \in \mathcal{H}}{\arg \min } \sum_{i}\left(-\frac{\partial L\left(f^{t-1}\left(\mathbf{x}_{i}\right), y_{i}\right)}{\partial f^{t-1}\left(\mathbf{x}_{i}\right)}-h\left(\mathbf{x}_{i}\right)\right)^{2}

实际上，这个模型的GNN根据loss更新和GBDT的

特征更新是在一个epoch里是分两步走的，互不影响，这个看源代码可以更清楚一些。如果先做GDBT的feature在扔进GNN，就会退化成作者说的Res-GNN。节点特征

的更新形式为：

\mathbf{X}_{n e w}^{\prime}=\mathbf{X}^{\prime}-\eta \frac{\partial L_{\mathrm{GNN}}\left(g_{\theta}\left(G, \mathbf{X}^{\prime}\right), Y\right)}{\partial \mathbf{X}^{\prime}}

注意由于使用了GDBT方法，所以这一块学习器本身也需要被更新为

f(x)=f_1(x)+f_2(x)

。