本文约4500字，建议阅读10+分钟

本文率先提出了无监督图结构学习的范式，旨在不依赖标签信息的条件下，从数据本身中学习更普适、更高质量的图结构。

作者 | Yuki

研究方向 | 推荐系统，图神经网络

论文题目：

Towards Unsupervised Deep Graph Structure Learning

论文链接：

https://arxiv.org/pdf/2201.06367.pdf

代码链接：

https://github.com/GRAND-Lab/SUBLIME

参考链接：

https://mp.weixin.qq.com/s/k66maMGcufw4svmIRC13zA

一、前言

近年来，图神经网络（graph neural networks，GNNs）被广泛应用于各种图数据相关的任务当中。然而，图神经网络的学习十分依赖于输入的图结构数据(即图数据中各节点的关联)，大大影响了其鲁棒性和普适性。一方面，现实系统中获取的图结构数据难免包含噪声信息，会存在多余边或缺失边的问题；在学习过程中，GNN 很容易受到这些噪声数据的影响，从而导致其性能下降。另一方面，对图结构的依赖也使得 GNN 无法应用于没有显式结构的非结构数据学习，尽管这些数据中可能存在隐性的结构信息。这种对输入结构的依赖，使得 GNN 难以应用于广泛存在于现实世界的非结构数据当中。

为了解决上述问题，现有方法对图结构学习（graph structure learning，GSL）进行研究，该技术旨在利用 GNN 对输入图结构本身进行学习和优化。目前的图结构学习主要遵循有监督范式，即：利用节点分类这一下游任务的标签信息，对图结构和 GNN 进行协同优化。这种范式虽被证明有效，却存在着一些局限性：

1. 依赖于标签信息，在有监督 GSL 方法中，在进行图结构优化时人工标注的标签在扮演了至关重要的角色，然而对标签数据的依赖限制了有监督 GSL 的在更广泛的无标签数据中的应用；

2. 学习到的边分布存在偏差，节点分类通常以半监督的形式进行，只有一小部分节点是有标签的（如在 Cora 数据集有标签节点的比例为 140/2708 ），因此这些标签节点之间的连接及其邻居会接收到更多的监督，从而造成学到的边分布存在不均匀和偏差；

3. 下游任务的局限性，在现有的方法中，结构学习通常依赖节点分类来提供监督信号，因此学习到的图结构通常是任务特定而不是通用的，可能对于下游其他任务没有帮助（如链接预测和节点聚类）。

为了解决上述局限，文中提出了一种新的用于 GSL 的无监督学习范式（unsupervised graph structure learning）。如图 1 所示，该学习范式不依靠任何额外的标签信息，仅根据输入数据本身对图结构进行学习或改进，因此学习到的图结构是通用的无偏的。针对新的学习范式，本文提出了一种基于结构自引导的自监督对比学习方法（StrUcture Bootstrapping Contrastive LearnIng fraMEwork, SUBLIME）。该方法主要有一下三点贡献：

1. 提出了一种新的用于 GSL 的无监督学习范式，相较于其他基于监督学习的 GSL，该范式更具有实践性。

2. 提出了一种新的无监督 GSL 方法——SUBLIME，该方法采用对比学习技术，从原数据本身中获取监督信号来引导结构学习，并同时利用学到的结构信息对监督信息进行更新。

3. 大量实验证明了 SUBLIME 的有效性。

二、问题定义

在介绍无监督 GSL 之前，先给出图的定义。给出一个属性图 ， 表示节点集合（）， 表示边集合（）， 表示特征矩阵， 表示邻接矩阵。

本文针对两种输入数据的情况，定义了两种无监督图结构学习问题，即“结构推理”（structure inference）和“结构改进”（structure refinement）。具体的，结构推理用于一般性的数据（图结构未定义或缺失），该任务目标是从非结构化的数据中（仅包含特征矩阵 ）学习出潜在的图结构 。

结构改进的目标则是从含噪声的图结构数据（包含特征矩阵 和邻接矩阵 ）中对原有的图结构进行改进得到改进后的图结构 。本文假设学习得到的图结构 能够更好的揭示节点之间的真实连接关系，并可被广泛应用于各种下游任务中。

三、方法

本文所提出的 SUBLIME 主要包含了两个组件：图结构学习模块（Graph Structure Learning Module）以及结构自引导对比学习模块（Structure Bootstrapping Contrastive Learning Module），SUBLIME 的结构图如图 2 所示，在图结构学习模块中，首先应用图学习器（Graph Learner）来建模图结构，然后通过后处理器（Post-Processor）对建模的图结构进行规范化。

在结构自引导对比学习模块中，首先定义了学习者视图（Learner view）和参考视角（Anchor View）用于对比。具体的，前者由学习到的图结构构成，后者则从原始数据中初始化而来。然后分别对两种视角应用数据增强（Data Augmentation）。

接下来最大化两种视角之间的互信息（Mutual Information），为图结构学习提供监督信号。此外，文中还设计了一种结构自引导机制，利用从学习者视角中学到的信息对参考视角进行优化。下面将对上述组件一一介绍。

3.1 图学习器

图学习器是 GSL 的关键组成部分，其用于学习一个粗略（sketched）邻接矩阵 ，大多数现有的方法通常采用单一的图学习器，无法适应不同数据的特性。为了适应不同输入数据的需要，本文采用了四种图学习器来建模图结构，包括一种全图参数化学习器（FGP Learner），和三种基于度量学习的学习器（Metric Learning-based Learners）。通常图学习器可以表示为 ， 为模型参数。

FGP 学习器对邻接矩阵的每个元素都用一个可学习的参数来建模，并应用一个非线性激活函数 来保证训练的稳定性：

而基于度量学习的学习器中，首先会由一个基于神经网络的嵌入函数来得到节点嵌入，然后通过无参数的度量函数（比如余弦相似度）来得到邻接矩阵中的而基于度量学习的学习器中，首先会由一个基于神经网络的嵌入函数 来得到节点嵌入，然后通过无参数的度量函数 （比如余弦相似度）来得到邻接矩阵中的值：

通过定义不同的嵌入函数 ，本文提供了三种不同的学习器：1）注意力学习器（Attentive Learner）；2）多层感知机学习器（MLP Learner）；3）图神经网络学习器（GNN Learner）：采用 GNN 进行节点嵌入的编码。

注意力学习器采用注意力机制来生成的节点嵌入：

多层感知机学习器采用多层堆叠的 MLP 层来计算节点嵌入：

图神经网络学习器采用 GNN 进行节点嵌入的编码：

在 SUBLIME 中根据数据集特性选择了最合适的学习器来建模图结构 。

3.2 后处理器

经由图学习器得到的邻接矩阵 通常比较粗糙，无法具备真实图结构的许多特性。因此，文中使用后处理对这个邻接矩阵进一步优化，从而产生一个精炼的图邻接矩阵。后处理器中的步骤主要分为 4 步：

1）稀疏化 Sparsification（基于kNN）：

2）对称化 Symmetrization（基于矩阵转置求平均）与 3）非负化 Activation（基于 ReLU 激活函数）：

4）归一化 Normalization（基于对称归一化处理）：

式中 表示 的都矩阵。

通过上述一系列后处理步骤，最终得到一个稀疏、非负、对称且正归一邻接矩阵 。

3.3 多视角图对比学习

当对学习到的图结构（邻接矩阵）进行建模后，文中采用多视角对比学习的方式，通过从原数据中获取监督信号来指导图结构的优化。基于学到的邻接矩阵，我们将其与特征矩阵 进行结合，得到学习者视角（Learner View），记为 。

文中利用原始数据对参考视角（Anchor View）进行初始化，该视角为图结构的学习提供指引。具体地，若原数据带有图结构，我们会将该视角初始化为原始特征矩阵和邻接矩阵：；若原数据不含图结构，将其中的邻接矩阵初始化为单位矩阵：。

视角构建完成后，文中设计两种数据增广方式：

1）随机遮掩特征（Feature Masking），对于给定的特征矩阵 ，首先采样遮掩向量 ，采样过程服从参数为 的伯努利分布，随机遮掩过程定义如下：

表示随机丢弃连接操作符。

2）随机丢弃连接（Edge Dropping），对于给定的邻接矩阵 ，首先采样遮掩矩阵 ，采样过程服从参数为 的伯努利分布，随机丢弃过程定义如下：

表示随机丢弃连接操作符。

通过增大对比学习任务的难度，使模型能够探索到更高质量的图结构。

在 SUBLIME 中对学习者视角和参考视角同时使用了上述两种增广方式：

值得一提的是为了提高两个视角间的差异性（上下文差异）。对于随机遮掩特征，采用了不同的 probabilities，。但是对于随机丢弃连接，文中使用了相同的 dropping probability，，因为两个视角的邻接矩阵本身差异明显。

下一步，采用节点级的对比学习模型来最大化两个视角的互信息。具体地，增广后两个视角图首先经由两层 GCN 的编码，得到每个节点的表征：

表示基于 GCN 的 encoder， 是 encoder 的模型参数。

然后，经过由两层 MLP 网络构成的投影网络，得到两个视角对应的投影矩阵：

最后，采用 NT-Xent 损失（Normalized Temperature-Scaled Cross-Entropy loss）函数来最大化两个投影矩阵中对应节点的相似度，从而最大化两个视角的互信息：

指代余弦相似度函数， 为温度系数， 与 同时计算。

3.4 结构自引导机制

通过固定的参考邻接矩阵 （定义为 或者 ）的指引，我们已经可以采用该模型进行结构学习。然而，这样的固定参考存在以下不足：1）原结构中包含的噪声边会对学到的图结构产生误导；2）固定的参考邻接矩阵包含的信息有限，很难提供持续的指引；3）在学习过程中，容易对固定的结构产生过拟合。

在自引导（Bootstrapping）的算法的启发下，我们设计了一种结构自引导机制（Structure Bootstrapping Mechanism）对参考邻接矩阵进行更新，从而提供可靠、持续、有效的结构学习指引。具体地，我们基于 slow-moving 的思想，利用学到的邻接矩阵 ，间歇地对参考邻接矩阵 进行更新 ：

一般来说

取值要大于 0.99，用来保证训练的稳定性。

受益与结构自引导机制，SUBLIME 可以很好的解决上述的问题。随着更新过程，一些 中的噪声边权重逐渐降低。与此同时，学习目标 随着训练过程发生改变，其吸收了更多的有益信息来指导图结构的学习，缓解了过拟合的问题。更重要的是，我们的结构自引导机制利用所学的知识，反过来改善学习目标，不断推动模型发现更优的图结构。

四、实验

4.1 实验设置

本文在 8 个数据集上展开实验，包括 4 个图结构数据集（Cora、CiteSeer、PubMed、ogbn-arxiv）以及 4 个非结构数据集（Wine、Cancer、Digits、20news）。我们在两个下游任务（节点分类和节点聚类）上评估学习结构的质量，并和一系列先进的方法进行对比。

4.2 性能对比

文中在三个场景进行对比：结构推理下的节点分类（表1），结构改进下的节点分类（表2），以及结构改进下的节点聚类（表3）。从实验结果可以看出，本文提出的方法在几乎所有场景和数据集中都能取得最优或次优的性能，说明了该方法能够学习到高质量且普适的图结构。

4.3 消融实验

通过改变超参数 的值，文中对结构自引导机制开展进一步研究。实验结果可以看出，当 时，SUBLIME 在三个数据集上都具有最佳的性能，说明适中的更新强度能够更好地更新参考视角。通过进一步分析准确率和损失函数的变化可以看出，当 时，此时结构自引导机制失效，在训练过程中会出现过拟合的情况，导致性能下降。当 时，此时会高强度地更新参考视角，导致训练过程非常不稳定，影响最终性能。

4.4 参数实验

本实验研究了两个超参数对性能的影响，包括随机遮掩特征的比率，以及 kNN 稀疏化中 k 的取值。从下图的实验结果可以看出，适中的超参数取值能带来最佳的性能，而过大/过小的取值都会导致模型性能的下降。

4.5 鲁棒性分析

为了研究 SUBLIME 在含噪声图结构下的性能，文中随机地增加或删除图结构中的边，并观测该方法在不同比率扰动下的性能。由下图可以看出，相比有监督的结构学习方法 Pro-GNN，SUBLIME 在两个场景下都能取得更好或相当的性能。尤其在大量边都被删除的情况下，SUBLIME 仍然能学习到高质量的图结构，远超其他方法的性能。

4.6 可视化

为了研究 SUBLIME 究竟学到了怎样的图结构，我们对学到的部分图结构进行可视化。我们考虑了两个类别（C 和 R）的节点，分别在训练集（L）和测试集（U）中选择了 10 个节点进行可视化。从下图可以看出，SUBLIME 可以学习到大量同类节点之间的连接。同时，相比有监督方法 Pro-GNN，我们的方法能够均匀地学习到每个节点之间潜在的连接，而不会出现边分布偏差的情况。

五、总结

本文率先提出了无监督图结构学习的范式，旨在不依赖标签信息的条件下，从数据本身中学习更普适、更高质量的图结构。为了解决无监督图结构学习问题，本文提出了一种基于结构自引导的自监督对比学习方法 SUBLIME，通过最大化两个视角的互信息的方式对结构进行建模、学习和优化。实验证明，相比有监督方法，我们的方法能够学习到更高质量的图结构。我们的方法有望应用于各种实际应用中，包括但不限于生物信息学研究，脑电波分析，交通流量预测以及计算机视觉等领域。