链接

论文题目：基于节点局部平滑的可扩展图学习（NDLS）（2021NIPS）

论文链接：2110.14377.pdf (arxiv.org)

代码链接：GitHub - zwt233/NDLS: Node Dependent Local Smoothing for Scalable Graph Learning (NeurIPS'21, Spotlight)

作者讲解：【AI Drive】第96期 - 北京大学张文涛：大规模图机器学习的可扩展性_哔哩哔哩_bilibili

一、摘要

最近的研究表明，特征或者标签的平滑处理是图神经网络(GNN)的核心。具体来说，这些研究展示了特征平滑与简单线性回归相结合的性能与精心设计的GNN相当，一个简单的MLP模型及其预测的标签平滑可以胜过普通GCN。尽管是一个有趣的发现，但平滑还没有被很好地理解，尤其是关于如何控制平滑程度。直观地说，太小或太大的平滑迭代可能会导致欠平滑或过平滑，并可能导致次优性能。此外，平滑程度是节点特定的，取决于节点的度和局部结构。为此，我们提出了一种称为基于节点局部平滑（NDLS）的新算法，旨在通过设置节点特定的平滑迭代次数来控制每个节点的平滑度。具体来说，NDLS根据邻接矩阵计算影响分数，并通过设置分数的阈值来选择迭代次数。选择后，迭代次数可以应用于特征平滑和标签平滑。实验结果表明，NDLS具有高精度——节点分类任务的最新性能、灵活性——可以与任何模型结合、可扩展性和效率——可以支持快速训练的大规模图。

摘要部分首先点名了特征平滑是图神经网络的核心，特征平滑简单来说就是对原节点属性做的变换，欠平滑指的是平滑结果不足以胜任后续的处理，过平滑指的是多次GCN操作后所有图中的节点特征趋向统一。作者的核心思想也很简单，通俗的讲，因为图中节点的度分布是不一样的，有的节点邻居比较多，有的节点邻居比较少，而之前的工作是赋予所有节点一样的平滑次数。举个例子，一个节点有5个邻居，经过平滑后刚好满足后续的处理，而另一个节点有10个邻居，就会造成过平滑，若一个节点只有1个邻居，则会欠平滑。作者就想给每个节点一个自适应的平滑次数，节点度比较大的次数少一点，度比较小的次数多一点。图1给出了形象化的解释。

二、引言

近年来，图神经网络(GNN)在许多基于图的任务上的最新性能引起了人们的极大兴趣。最近的工作发现，GNN的成功主要归功于平滑，无论是在特征级别还是标签级别。例如，SGC[32]表明，使用平滑特征作为简单线性回归模型的输入，可以与许多精心设计的复杂GNN实现相当的性能。在平滑阶段，将相邻节点的特征聚合并与当前节点的特征结合形成平滑特征。这个过程经常重复多次。平滑基于彼此靠近的节点的标签高度相关的假设，因此，附近节点的特征应该有助于预测当前节点的标签。

邻域特征聚合的一个关键且有趣的参数是平滑迭代k的数量，它控制着收集了多少信息。直观地说，k次迭代（或层）的聚合过程使节点能够利用来自k跳之外的节点的信息。k的选择与图的结构性质密切相关，并对模型性能产生重大影响。然而，大多数现有的GNN只考虑固定长度的传播范式——所有节点的统一k。这是有问题的，因为迭代次数应该取决于节点的度数和局部结构。例如，如图1(a)所示，两个节点的局部结构截然不同，左边的红色节点位于密集簇的中心，右边的红色节点位于外围，几乎没有连接。两个节点达到最佳平滑度的迭代次数是肯定不同的。理想情况下，连接不良的节点（例如右侧的红色节点）需要较大的迭代次数才能有效地从其他节点收集信息，而连接良好的节点（例如左侧的红色节点）应保持较小的迭代次数以避免过平滑。尽管一些基于学习的方法已经提出通过门/注意机制或强化学习 [29,21,40,27]自适应地聚合每个节点的信息，但性能提升是以增加训练复杂性为代价的，因此不适合可扩展图学习。

在本文中，我们提出了一个简单而有效的解决方案来解决这个问题。我们的方法称为节点局部平滑(NDLS)，它为每个节点计算节点特定的迭代次数，称为局部平滑迭代(LSI)。一旦计算出特定节点的LSI，相应的局部平滑算法只会将距离小于其LSI的节点的信息聚合为新特征。LSI是根据影响分数选择的，影响分数衡量其他节点如何影响当前节点。NDLS将特定节点的LSI设置为最小迭代次数，以使影响分数远离过度平滑分数，定义为无限迭代时的影响分数。需要注意的是每个节点的影响分数应该在一个合理的水平。由于具有不同局部结构的节点具有不同的“平滑速度”，我们期望迭代次数是自适应的。图1(b)说明了实际图中各个节点的LSI的累积分布函数(CDF)。所有数据集都存在异构和长尾属性，类似于真实图中节点的度分布特征。

图1：（左）密集区域的节点在两次传播迭代中具有较大的平滑区域。（右）三个引文数据集中LSI的CDF。

CDF，累积分布函数。这里的LSI指的是一个节点需要多少次平滑迭代才能达到一个较好的特征，CDF可以这样理解，需要0~10次LSI的节点在图中占比0.1（10%），需要0~20次LSI的节点在图中占比0.4（40%），那么需要10~20次LSI的节点在图中占比就是0.3（30%）。图中可以看出三个常用数据集都存在LSI长尾分布的问题。

三、前文

在本节中，我们首先介绍半监督节点分类任务并回顾先前的模型，并在此基础上推导出第 3 节中的方法。考虑一个图 $G= \left ( \nu ,\varepsilon \right )$ ，其中 $\left | \nu \right |= n$ 个节点以及 $\left | \varepsilon \right |= m$ 条边，邻接矩阵（包括自环）表示为 $\tilde{A}\in R^{n\ast n}$ ，特征矩阵表示为 $X= \left \{ x_{1},x_{2},...,x_{n} \right \}$ ，其中 $x_{i}= R^{f}$ 表示节点 $x_{i}$ 。此外， $Y= \left \{ y_{1},y_{2},...,y_{l} \right \}$ 是由one-hot标签指示向量组成的初始标签矩阵。目标是在标记集 $\nu _{l}$ 的监督下预测未标记集 $\nu _{u}$ 中节点的标签。

GCN 通过聚合它自己的表示和它的邻居的表示来平滑每个节点的表示。这个过程可以定义为:

$X^{\left(k+1\right)}= \delta \left ( \hat{A}X^{\left(k\right)}W^{\left(k\right)} \right ), \hat{A}=\tilde{D}^{r-1}\tilde{A}\tilde{D}^{-r}$

其中 ${\hat{A}}$ 是归一化的邻接矩阵， $r= \left [ 0,1 \right ]$ 是卷积系数， $\tilde{D}$ 是具有自环的对角节点度矩阵。这里 $X^{\left ( k \right )}$ 和 $X^{\left ( k+1 \right )}$ 分别是第k层和k+1层的平滑节点特征，而 $X^{0}$ 设置为节点原始特征矩阵 $X$ 。此外， $W^{\left ( k \right )}$ 是第k层的可训练权重矩阵， $\delta \left ( \cdot \right )$ 是激活函数。通过设置 $r= 0.5$ , $1$ 和 $0$ ，卷积矩阵 $\tilde{D}^{r-1}\tilde{A}\tilde{D}^{-r}$ 表示对称归一化邻接矩阵 $\tilde{D}^{-\frac{1}{2}}\tilde{A}\tilde{D}^{-\frac{1}{2}}$ [20]，转移概率矩阵 $\tilde{A}\tilde{D}^{-1}$ [37] 和反向转移概率矩阵 $\tilde{D}^{-1}\tilde{A}$ [35]。

SGC。对于公式(1)中定义的每个 GCN 层。如果非线性激活函数 $\delta \left ( \cdot \right )$ 是一个单位函数， $W^{\left ( k \right )}$ 是一个单位矩阵，我们得到 k 次迭代传播后的平滑特征为 $X^{\left ( k \right )}=\hat{A}^{k}X$ 。最近的研究观察到，GNN的好处主要来自于在图邻域上执行特征平滑，而不是像CNN类比所暗示的那样学习特征的非线性层次结构。通过假设GCN层之间的非线性变换并不重要，SGC[32]首先提取平滑特征 $X^{\left ( k \right )}$ ，然后将它们馈送到线性模型，从而提高可扩展性和效率。遵循SGC的设计原则，已经提出了大量工作来进一步提高SGC的性能，同时保持高可扩展性和效率，例如SIGN[28]、 $S^{2}GC$ [42] 和 GBP。

过平滑[22]问题。通过在SGC中以无限次传播来不断平滑节点特征，最终平滑特征 $X^{\left ( \infty \right )}$ 为：

$X^{\left ( \infty \right )}=\hat{A}^{\infty }X \qquad \hat{A}_{i,j}^{\infty }= \frac{\left ( d_{i}+1 \right )^{r}\left ( d_{j}+1 \right )^{1-r}}{2m+n}$

其中 $\hat{A}^\infty {}$ 是最终的平滑邻接矩阵， $\hat{A}_{i,j}^{\infty }$ 是节点 $v_{i}$ 和 $v_{j}$ 之间的权重， $d_{i}$ 和 $d_{j}$ 分别是 $v_{i}$ 和 $v_{j}$ 的节点度数。公式(2)表明，当我们在SGC中对具有无限次传播的节点特征进行平滑处理时，最终特征被过度平滑，无法捕获完整的图结构信息，因为它仅与目标节点和源节点的度有关。例如，如果我们设置 $r= 0$ 或 $1$ ，所有节点将具有相同的平滑特征，因为只考虑了源节点或目标节点的度。