首发于Scalable GNN
论文笔记:arXiv'21 Graph Attention Multi-Layer Perceptron

论文笔记:arXiv'21 Graph Attention Multi-Layer Perceptron

前言

近年来图表示学习一度成为了 GNN 领域的热点,从最初的 GCN、GAT 不断升级演化,现有性能最优的 GNN 模型通常结合 MLP (Multi-Layer Perceptron)完成 Embedding 学习。好久不看相关的论文,以此文梳理一下近年来效果比较好的图表示学习的 GNN Model 和论文中提到的注重 GNN 表达能力的多类方法

现有的图表示学习方法尽管性能很高,但通常需要在每个 epoch 内进行昂贵的递归邻域扩展,并存在可扩展性问题。此外,由于固定的邻居节点信息传递范围,导致 GNN 模型在训练过程中对节点实际感知域不敏感。本文提出 Graph Attention Multi-Layer Perceptron(GAMLP)。GAMLP 符合解耦 GNN 的特点,特征传播的计算与神经网络的训练分离,保证了 GAMLP 的可扩展性。通过三个 receptive field attention,GAMLP 中的每个节点都可以灵活地利用在不同大小的感知域上传播的特征。(本文的目的是实现高性能且可扩展)。

如果大家对大图数据上高效可扩展的 GNN 和基于图的隐私计算感兴趣,欢迎关注我的 Github,之后会不断更新相关的论文和代码的学习笔记。


1. Motivation

GNN 遵循信息传播范式实现了迭代的学习,即使是在分布式环境下 GNN 需要读取大量的相邻节点来计算单个目标节点的表示,虽然有效提升了模型性能但是导致了高的通信成本。同时GNN 中对邻域信息的利用导致了在大图上训练的可扩展性问题。

SGC 将特征传播和非线性变换过程解耦,前者在预处理过程中执行。SGC 只有训练集的节点参与到模型训练中且在模型训练过程中不需要获取相邻节点的特征。因此,SGC 在单台机器上的计算和内存效率很高,而且在分布式环境中可以扩展。尽管具有可扩展性,SGC 采用了固定的特征传播层,导致所有节点的 Receptive Field(RF)固定。这样的特征传播方式缺乏灵活性,无法对不同 RF 下的关联节点进行建模,会产生两种结果:

  • 长距离的依赖性由于 RF 过小而不能被充分利用;
  • 由于RF过大而引入过平滑的噪声而失去了局部信息。

为了更好地利用 GNN 中层与层之间及不同 RF 下的特征信息,SIGN 提出在没有信息损失的情况下将所有这些特征串联起来,而 S2GC 则对所有这些特征进行平均。SIGN 和 S2GC 没有考虑不同 RF 的重要程度。GBP 通过在传播特征中采用恒定的加权平均衰减因子来解决这个问题。受 Personalized PageRank 的启发,具有较大 RF 的传播特征面临较高的过平滑风险,在 GBP 中对最终平均特征的贡献较小。所有这些方法都采用了分层传播的机制,并考虑了不同传播层后的特征。上述方法没有考虑节点上的特征组合。

如图1(a)所示,不同节点需要不同的节点感知域以达到最佳的表现。此外,由于图1(b)所示的 RF 扩展速度不一致,同质和非自适应的特征平均可能不适合所有节点。

Sampling

解决 GNN 中可扩展性问题(递归邻域扩展)常用方法是采样。对于 Neighbor sampling,GraphSAGE 在每个 mini-batch 中随机抽出固定大小的邻居集进行计算。VR-GCN 分析了2个方差的减少,因此它可以在增加内存成本的情况下减少样本的大小。对于 Layer-wise sampling,FastGCN 在每一层对固定数量的节点进行采样,ASGCN 提出了具有更好方差控制的自适应分层采样。对于 Subgraph sampling,Cluster- GCN 对节点进行聚类,然后对聚类节点进行采样,GraphSAINT 直接对一个子图进行采样,进行 mini-batch 训练。

Graph-wise Propagation

\mathbf{X}^{(K)} = \hat{\mathbf{A}}^{K}\mathbf{X}^{(0)},\;\mathbf{Y} = \mathbf{softmax}(\mathbf{\Theta X}^{(K)})\tag{1}

以 SGC 为代表,这种 Graph-wise Propagation 传播限制了每个节点的相同特征传播过程和固定的 RF。由于 RF 扩展速度不一致,一些节点的特征可能过平滑或平滑不足。

Layer-wise Propagation

SIGN 将特征传播过程生成结果与线性变换集合: [\mathbf{X}^{(0)}\mathbf{W}_0,\mathbf{X}^{(1)}\mathbf{W}_1,\dots,\mathbf{X}^{(K)}\mathbf{W}_K] ,S2GC 使用简单的谱图卷积来平均不同迭代中的传播特征: \mathbf{X}^{(K)} = \sum_{l=0}^K\hat{\mathbf{A}}^l\mathbf{X}^{(0)} ,GBP 通过加权平均进一步优化特征聚合过程: \mathbf{X}^{(K)} = \sum_{l=0}^Kw_l\hat{\mathbf{A}}\mathbf{X}^{(0)} ,其中受 Personalized PageRank 的启发 w_l 是一个衰减的权重参数: w_l = \beta(1-\beta)^l 。本文提出的 GAMLP 也使用线性模型以获得更高的训练可扩展性。不同之处在于,GAMLP 从节点的角度考虑传播,其中每个节点都有一个对于特征传播过程中产生结果的个性化特征聚合过程。

Self Supervision on GNN

自监督在 GNN 中被广泛使用,主要方法可以分为以下几类:pretraining & finetuning、self-training、self knowledge distillation 和 multi-task learning。

pretraining & finetuning:使用自监督任务训练一个 GNN,然后用学到的模型参数来初始化其他网络。

self-training:一些研究提出将 "伪标签(Pseudo-Label)" 分配给具有高信心模型预测的节点。SAGN 认为如果一个未标记的节点的相应类别概率大于预定的阈值,则该节点是有信心的。

self knowledge distillation:与 self-training 中使用的 one hot label 不同,基于知识蒸馏的 GNN Model 直接提炼出模型预测的软标签或嵌入。

本文使用一个预定义的阈值来过滤可靠的软标签实现 GNN 的模型蒸馏。最后,多任务学习将 GNN 的 self-supervised 视为整个网络训练的正则化项,从而提高模型的通用性。

Label Utilization on GNN

在大多数图学习方法中,训练节点的标签通常只被用作损失函数的监督信号。然而,也有一些图学习方法直接利用了训练节点的标签,例如标签传播算法(label propagation)。它将部分观察到的标签矩阵 \mathbf{Y} \in \mathbb{R}^{N\times C} 视为图中节点的输入特征,基于图结构进行特征传播,其中 C 是候选类的数量。

UniMP 提出将部分观察到的标签矩阵 \mathbf{Y} 映射到节点特征矩阵 \mathbf{X} 的维度,并将这两个矩阵加在一起作为新的输入特征。为了应对标签泄漏问题,UniMP 在 epoch 中随机遮掩训练节点。

Correct & Smooth 不是使用 hard training labels,而是先训练一个简单的模型,如MLP,并获得这个简单模型对未标记节点的预测软标签。然后将标签节点上的学习误差传播到连接节点上,并像 APPNP 那样以 Personalized PageRank 方式平滑输出,基于图结构进行传播。此外,SLE 将 UniMP 中的处理标签的过程进行解耦,并提前执行传播过程。相较于 UniMP ,label reuse 将部分观察到的标签矩阵 \mathbf{Y} 与节点特征矩阵 \mathbf{X} 连接起来,形成新的输入矩阵。具体来说,它用模型预测的软标签来填补部分观察到的标签矩阵 \mathbf{Y} 中的缺失元素,这个新生成的 \mathbf{Y}^{'} 再次与 \mathbf{X} 串联,然后送入模型以产生新的预测。

2. Graph Attention Multi-Layer Perceptron(GAMLP)

2.1 Feature Propagation

\mathbf{X}^{(l)}\leftarrow \mathbf{TX}^{(l-1)},\forall l = 1,\dots,K\tag{2}

特征传播过程去除了冗余的权重矩阵 \Theta 和非线性激活函数 \delta ,其中 \mathbf{X}^{(l)} 的 RF 感知域包含其本身和 l -hop 的邻居节点。经过 K 的特征传播之后,可以得到一系列特征传播的输出结果: [\mathbf{X}^{(0)},\mathbf{X}^{(1)},\mathbf{X}^{(k)},\dots,\mathbf{X}^{(K)}] ,使用注意力机制实现每层的加权平均得到输出:

\mathbf{H} = \sum_{l=0}^K\mathbf{W}_l\mathbf{X}^{(l)}\tag{3}

为了权衡基于 RF 的注意力集中,作者提出三个 RF 机制来得到 w_i(l)

2.2 Receptive Field Attention

Smoothing Attention

假设经过 \infty 次的特征传播,其本质上是一种低通滤波器,作用于图节点信号上时会不可避免地产生过平滑现象(over-smoothing),当 \hat{\mathbf{A}} = \tilde{\mathbf{D}}^{r-1}\tilde{\mathbf{A}}\tilde{\mathbf{D}}^{-r} ,无限次传播状态如下:

\hat{\mathbf{A}}_{i,j}^{\infty} = \frac{(d_i+1)^r(d_j+1)^{1-r}}{2m+n}\tag{4}

为了避免由于特征传播次数过大,RF 变广导致的 over-smoothing(空域角度),本文提出的应对方法为 Smoothing Attention,对于节点 i 在第 k 次传播时的注意力定义如下:

\tilde{\mathbf{X}}_i^{(l)} = \mathbf{X}_i^{ (l)}||\mathbf{X}_i^{(\infty)},\;\tilde{w}_i(l) = \delta(\tilde{\mathbf{X}}_i^{(l)}\cdot s),\;w_i(l) = e^{\tilde{w}_i(l)}/\sum_{k=0}^Ke^{\tilde{w}_i(k)}\tag{5}

s\in\mathbb{R}^{1\times d} 可训练,较大的 w_i(k) 意味着节点 v_il -step 传播特征与无限次传播状态距离较远,成为噪声的风险较小。具有较大 w_i(k) 的传播特征对特征组合的贡献应该更大。

Recursive Attention

递归计算特征传播过程中的信息增益:

\tilde{\mathbf{X}}_i^{(l)} = \mathbf{X}_i^{(l)}||\sum_{k=0}^{l-1}w_i(k)\mathbf{X}_i^{(k)},\;\tilde{w}_i(l) = \delta(\tilde{\mathbf{X}}_i^{(l)}\cdot s),\;w_i(l) = e^{\tilde{w}_i(l)}/\sum_{k=0}^Ke^{\tilde{w}_i(k)}\tag{6}

较大的 w_i(l) 意味特征 \mathbf{X}_i^{(l)}v_i 的当前状态更为重要(相较于前层组合特征占比更高)。

JK Attention

JK-Net 采用层聚合的方式将不同 GCN 层的节点嵌入结合,JK-Net 可以利用不同 RF 所获得的特征信息。基于此本文提出利用在所有传播特征上训练的模型预测来指导特征组合过程:

其中 JK Attention 的组合权重机制定义如下:

\tilde{\mathbf{X}}_i^{(l)} = \mathbf{X}_i^{(l)}||\mathbf{E}_i,\;\tilde{w}_i(l) = \delta(\tilde{\mathbf{X}_i}^{(l)}\cdot s),\;w_i(l) = e^{\tilde{w}_i(l)}/\sum_{k=0}^Ke^{\tilde{w}_i(k)}\tag{7}

其中 \mathbf{E}_i = \mathbf{MLP}(\mathbf{X}_i^{(1)}||\mathbf{X}_i^{(2)}||\dots||\mathbf{X}_i^{(K)}) ,JK 机制旨在为每个节点创建一个多尺度特征表示,这有助于注意力机制学习权重 w_i(k) 。学到的权重被送入基于注意力的组合分支,以生成每个节点的精炼注意力特征表示。随着训练过程的继续,基于注意力的组合分支将逐渐强调那些对目标节点更有帮助的邻近区域。JK Attention 可以模拟更广泛的邻域,同时增强相关性,为每个节点带来更好的特征表示。

2.3 Model Training

2.3.1 Incorporating Label Propagation

标签嵌入矩阵 \hat{\mathbf{Y}}^{(0)} 首先被初始化为 0。然后使用 hard training labels \mathbf{Y}_{\mathcal{V}_l} 来填充矩阵,并基于归一化邻接矩阵 \hat{\mathbf{A}} 进行传播:

\hat{\mathbf{Y}}_{\mathcal{V}_l}^{(0)} = \mathbf{Y}_{\mathcal{V}_l},\;\hat{\mathbf{Y}}^{(k+1)} = \hat{\mathbf{A}}\hat{\mathbf{Y}}^{(k)}\tag{8}

其中 \mathcal{V}_l 为有标签节点集合,得到最终的标签嵌入 \hat{\mathbf{Y}}^{(K)}后,使用其加强模型预测结果。

基于注意力的特征传播可以在不同大小的 RF 上自适应利用传播的特征,避免过度平滑问题。大规模图数据需要多步非线性变换过程,其可能会导致模型退化的问题,为了应对该问题,本文提出使用初始残差机制:

\hat{\mathbf{H}}^{(l)}\leftarrow\delta(\mathbf{W}^{(l)}\hat{\mathbf{H}}^{(l-1)}+\mathbf{X}^{(0)}),\;l=1,\dots,L\tag{9}

L 代表 \mathbf{MLP} 的层数, \mathbf{H}^{(0)} = \hat{\mathbf{H}} 代表组合后的特征矩阵(注意力机制作用后)。

这个 L\mathbf{MLP} 的输出与标签嵌入相加,得到最终的输出嵌入:

\tilde{\mathbf{H}} = \hat{\mathbf{H}}^{(L)}+\mathbf{MLP}(\hat{\mathbf{Y}}^{(K)})\tag{10}

损失函数为 Cross-Entropy (CE)( \mathbf{Y}_i 为 one-hot 标签向量):

\mathcal{L}_{CE} = -\sum_{i\in\mathcal{V}_i}\sum_j\mathbf{Y}_{ij}\log(\mathbf{softmax}(\tilde{\mathbf{H}}_{ij}))\tag{11}

2.3.2 Reliable Label Utilization (RLU)

Reliable Label Propagation

为了更好地利用预测的软标签(即softmax输出),作者将整个训练过程分成多个阶段,

在第一阶段,GAMLP 模型是按照上述过程训练的。

在之后,GAMLP 利用最后阶段预测的可靠软标签来改进标签嵌入 \hat{\mathbf{Y}}^{(0)}

\mathbf{P}^{(m)} = \mathbf{softmax}(\hat{\mathbf{H}}/T),\;\;T\in(0,1]\tag{12}

其中参数 T 控制 softmax 分布。较低的 T 值会得到更加 hardened 的分布。

假设现在处于整个训练过程的第 m -step( m>1 )的开始。不仅仅使用训练标签来构建初始标签嵌入 \hat{\mathbf{Y}}^{(0)} ,而是在最后阶段也采用验证集和测试集中节点的预测结果。为了保证预测的软标签的可靠性,使用一个阈值来过滤掉验证集和测试集中的低置信度的节点:

\hat{\mathbf{Y}}_i^{(0)} = \left\{ \begin{align*} &\mathbf{Y}_i,\;if\;\;i\in\mathcal{V}_l,\\ &\mathbf{P}_i^{(m-1)}\;if\;\;i\in\mathcal{V}_r,\;\hat{\mathbf{Y}} ^{(k+1)} = \hat{\mathbf{A}}\hat{\mathbf{Y}}^{(k)}\\ &0,\;\;otherwise \end{align*}\tag{13} \right.

可靠的节点集 \mathcal{V}_r 是由在第 (m-1) -step 中属于最可能的类别的预测概率大于阈值 \epsilon 的节点组成。

Reliable Label Distillation

为了充分利用最后阶段的有用信息,GAMLP 中加入了一个知识蒸馏模块。为保证知识蒸馏模块的可靠性,第 m -step( m>1 )只包括可靠节点集 \mathcal{V}_r ,然后定义加权 KL 散度:

\mathcal{L}_{KD} = \sum_{i \in \mathcal{V}_r}\sum_j\alpha_i\mathbf{P}_{ij}^{(m-1)}\log\frac{\mathbf{P}_{ij}^{(m-1)}}{\mathbf{P}_{ij}^{(m)}}\tag{14}

其中 \alpha_i 为可靠节点 i 的在第 (m-1) -step 最可能类别预测的概率所设置。加入 \alpha_i 以更好地指导知识蒸馏过程,给更有信心的节点分配更高的权重。

对于第 m -step 的完整训练损失为(超参控制知识蒸馏模块):

\mathcal{L} = \mathcal{L}_{CE} + \gamma\mathcal{L}_{KD}\tag{15}

3. Experiments

参数设置可见附件 B

编辑于 2022-07-22 09:06