【论文解读|NeurIPS2020】IDGL - 用于图神经网络的迭代深度图学习:更好和鲁棒的节点嵌入_iterative deep graph learning for graph neural net

论文链接：Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings
代码链接： https://github.com/hugochan/IDGL
关键词：图结构学习

摘要

本文提出了一种端到端图学习框架，即迭代深度图学习(IDGL)，用于联合迭代学习图结构和图嵌入。IDGL的关键原理是基于更好的节点嵌入来学习更好的图结构，反之亦然(即基于更好的图结构来学习更好的节点嵌入)。当学习到的图结构足够接近为下游预测任务优化的图时，我们的迭代方法会动态停止。此外，我们将图学习问题作为一个相似度度量学习问题，并利用自适应图正则化来控制学习图的质量。最后，结合锚定逼近技术，我们进一步提出了IDGL的可扩展版本，即IDGL-ANCH，该版本在不影响性能的前提下，显著降低了IDGL的时间和空间复杂度。我们在九个基准上的广泛实验表明，我们提出的IDGL模型可以始终优于或匹配最先进的基准。此外，IDGL对对抗性图具有更强的鲁棒性，并能同时处理转导和归纳学习。

1 引言

近年来，人们对图神经网络(gnn)的兴趣显著增加，特别是致力于开发更有效的gnn用于节点分类[29,36,17,52]、图分类[60,43]和图生成[47,37,61]。尽管gnn具有学习表达节点嵌入的强大能力，但不幸的是，它们只能在有图结构数据时使用。许多真实世界的应用程序自然承认网络结构的数据(例如，社交网络)。然而，这些内在的图结构对于下游任务并不总是最优的。这部分是因为原始图是在原始特征空间上构造的，经过特征提取和变换后，可能无法反映“真实”的图拓扑。另一个潜在的原因是，由于不可避免地容易出错的数据测量或收集，现实世界的图表经常是嘈杂的，甚至是不完整的。此外，许多应用，如自然语言处理[7,57,58]可能只有顺序数据，甚至只有原始特征矩阵，需要从原始数据矩阵中额外构建图。
为了解决这些限制，我们提出了一个端到端图学习框架，即迭代深度图学习(IDGL)，联合迭代学习的图结构和GNN参数，优化为下游预测任务。IDGL的关键原理是基于更好的节点嵌入来学习更好的图结构，同时，基于更好的图结构来学习更好的节点嵌入。特别是，IDGL是一种新的迭代方法，旨在搜索隐式图结构，增加初始图结构(如果不可用，我们使用kNN图)，并为下游预测任务优化图的目标。当学习到的图结构足够接近为下游任务优化的图时，迭代方法调整在每个小批处理中停止的时间。
此外，我们提出了一种利用多头自注意和邻域稀疏化构造图的图学习神经网络。此外，与[25]中直接优化邻接矩阵而不考虑下游任务的工作不同，我们通过优化结合任务特定预测损失和图正则化损失的联合损失来学习图度量学习函数。最后，我们进一步提出了IDGL框架的一个可扩展版本，即IDGL-ANCH，通过结合基于锚点的近似技术，将时间和内存复杂度从图节点数的二次型降低为线性型。

---

总之，我们将主要贡献总结如下：

• 提出了一种新的端到端图学习框架(IDGL)，用于联合迭代学习图结构和图嵌入。当学习到的图结构接近优化图(用于预测)时，IDGL动态停止。据我们所知，我们是第一个将迭代学习引入图结构学习的人。
• 结合基于锚点的近似技术，我们进一步提出了一个可扩展的IDGL版本，即IDGL-ANCH，它在计算时间和内存消耗方面都达到了与图节点数量相关的线性复杂度。
• 实验结果表明，我们的模型在各种下游任务上始终优于或匹配最先进的基线。更重要的是，IDGL对对抗性图例子更健壮，并能同时处理转导和归纳学习。

2 IDGL框架

2.1 问题定义

2.2 图学习和图嵌入

图拓扑是GNN学习表达性图节点嵌入的关键。大多数现有的GNN方法只是简单地假设输入图拓扑是完美的，这在实际中并不一定是正确的，因为现实世界的图通常是有噪声的或不完整的。更重要的是，所提供的输入图可能并不适合被监督的下游任务，因为大部分原始图是由原始特征空间构造的，而原始特征空间在经过高级特征转换后可能无法反映“真实”的图拓扑。先前的一些研究[52]通过使用自注意对先前学习的节点嵌入重新加权邻域节点嵌入的重要性来缓解这个问题，该研究仍然假设原始图连接信息是无噪声的。
为了处理潜在的噪声输入图，我们提出了新的IDGL框架，该框架将该问题定义为一个迭代学习问题，该问题将联合学习图结构和GNN参数。我们的IDGL框架的关键原理是在更好的节点嵌入基础上学习更好的图结构，同时，在更好的图结构基础上学习更好的节点嵌入，如图2所示。与大多数现有的基于原始节点特征构造图的方法不同，GNN学习到的节点嵌入(向下游任务优化)可以为更好地学习图结构提供有用的信息。另一方面，新学习到的图结构可以作为GNN更好的图输入来学习更好的节点嵌入。
特别是，IDGL是一种新的迭代方法，旨在搜索隐式图结构，增加初始图结构(如果不可用，我们使用kNN图)的下游预测任务。根据我们提出的停止准则，当学习到的图结构足够接近优化的图(关于下游任务)时，迭代方法在每个小批处理中动态停止。此外，图的构建过程可以端到端向下游任务进行优化。

2.3 图学习作为相似度度量学习

先前的方法(例如，[15])将图学习问题建模为在图的边缘上学习联合离散概率分布，这些方法表现出了良好的性能。然而，由于它们通过假设图节点是已知的来优化边缘连接，它们无法处理归纳设置(在测试期间使用新节点)。为了克服这一问题，我们将图结构学习问题转换为相似度度量学习，并将其与专门用于下游任务的预测模型联合训练。
图相似性度量学习 虽然我们的框架是未知的各种相似度量函数，但不失一般性，我们设计了一个加权余弦相似度作为我们的度量函数：$s_{ij}=cos(w\odot v_i,w\odot v_j)$，其中⊙代表哈达玛积，w是一个可学习的权重向量，其与输入向量$v_i,v_j$具有相同的维数并且学习突出显示向量的不同维度。注意，这两个输入向量可以是原始的节点特征，也可以是计算的节点嵌入。
为了稳定学习过程并增加表达能力，我们将相似度度量函数扩展到多头版本(类似于[51,52]中的观察)。具体来说，我们使用m个权向量(每个权向量代表一个视角)，利用上述相似性函数计算m个独立的相似性矩阵，并取其平均值作为最终的相似性:

直观上，$s_{ij}^p$计算的是两个输入向量$v_i和v_j$在第p视角下的余弦相似度。
Graph sparsification via ε-neighborhood. 一般来说，邻接矩阵(由度规计算)是非负的，但$s_{ij}$的范围在[-1, 1]之间。此外，许多底层图结构比完全连通图稀疏得多，这不仅计算开销大，而且可能引入噪声(即不重要的边)。因此，考虑到每个结点的 $\epsilon$-邻居， 我们继续从$S$中提取对称稀疏非负邻接矩阵$A$。具体来说，我们将S中小于非负阈值ε的元素屏蔽(即设为零)。
基于锚点的伸缩性度量学习Anchor-based scalable metric learning 上述相似度度量函数(如Eq.(1))计算所有图节点对的相似度得分，这在计算时间和内存消耗方面都要求$O(n^2)$复杂度，对于大型图来说具有显著的可伸缩性问题。为了解决可伸缩性问题，受以前基于锚点的方法的启发[41,55]，我们设计了一种基于锚点的可伸缩性度量学习技术，该技术学习节点集V和锚点集U之间的node-anchor 关联矩阵(node-anchor affinity matrix)$R\in R^{n\ast s}$(即，需要$O(ns)$的时间和空间复杂性，其中s是锚点的数量)。注意，s是一个超参数，它是在开发集上调整的。
锚嵌入因此被设置为相应的节点嵌入。因此，方程(1)可写作下式：

其中，$a_{ik}$是结点$v_i和v_j$之间的关联分数。同样，我们应用ε-neighborhood技巧在结点-锚点关联分数$a_{ik}$上来获得稀疏非负的节点-锚点关联矩阵R.

2.4 图结点嵌入和预测

虽然初始图可能有噪声，但它通常仍然携带关于真正的图拓扑的丰富而有用的信息。理想情况下，学习到的图结构A可以作为原始图$A^{(0)}$的补充构造一个关于下游任务的gnn的优化图。因此，在温和的假设下，优化的图结构可能是从初始图结构“转移”出来的，我们将学习到的图与初始图结合起来，

因此，我们将最终学习到的图结构作为它们的超参数$\eta$加权后的线性组合，从而结合两者的优点。最后，利用另一个超参数λ来平衡学习图结构和初始图结构之间的平衡。如果这种初始图结构不可用，我们将使用基于原始节点特征X的利用余弦相似度构造的kNN图。
我们的图学习框架对各种GNN架构(将节点特征矩阵和邻接矩阵作为输入来计算节点嵌入)和预测任务是不可知的。本文采用双层GCN[29]，第一层(记为GNN1)将原始节点特征X映射到中间嵌入空间，第二层(记为GNN2)进一步将中间节点嵌入Z映射到输出空间。

其中，分别是任务依赖的输出函数和损失函数。
Node-anchor消息传递
如果我们把节点和锚点之间的直接移动看作是由R描述的一步过渡，建立在平稳马尔可夫随机游动[42]理论的基础上

2.5 图正则化

虽然将学习到的图$A^{(t)}$与初始图$A^{(0)}$结合起来是一种逼近优化图的有效方法，但学习到的图$A^{(t)}$的质量对提高最终图${\tilde{A}}^{(t)}$的质量起着重要的作用。在实践中，重要的是控制得到的学习图$A^{(t)}$的平滑性、连通性和稀疏性，它忠实地反映了关于初始节点属性X和下游任务的图拓扑。
让特征矩阵X的每一列看做一个图信号。图信号的一个广泛采用的假设是值在相邻节点之间平滑变化。给定一个具有对称加权邻接矩阵$A$的无向图，

稀疏性：现实的网络大部分都是稀疏的
平滑性：平滑指的是特征信息不相似的节点不应该链接，如果每一条边两端的节点都是相似的，我们会说整个网络是平滑的
连通性：网络应该是连通的
平滑性：

连通性和稀疏性

第一项惩罚不连通性，第二项惩罚稀疏性

然后，我们将总体图正则化损失定义为上述损失的总和 LG“ αΩpA,Xq`
fpAq能否控制学习图的平滑性、连通性和稀疏性

3 实验

4 相关工作

5 结论

我们提出了一种新的IDGL框架，用于联合迭代学习面向下游任务优化的图结构和嵌入。实验结果验证了该模型的有效性和有效性。在未来，我们计划探索有效的技术来处理更具挑战性的场景，其中图拓扑和节点特性都是嘈杂的。

广泛影响
我们研究的基本目标是开发一种联合学习图结构和嵌入的方法，以优化(半)监督下游任务。我们的技术可以广泛应用于广泛的应用领域，包括社会网络分析，自然语言处理(例如，问答和文本生成)，药物发现和社区检测。从概念上讲，任何以共同学习图结构和嵌入为目的的应用程序，以便在下游任务中表现良好。这些潜在的应用范围包括计算机视觉、自然语言处理和网络分析。例如，我们的研究可能用于帮助在自然语言处理中更好地捕获单词标记(超出标记序列)之间的语义关系
将我们的方法作为工具使用有许多好处，例如将图神经网络应用于非图结构数据，而无需手动构造图，以及学习节点/图嵌入，从而对有噪声的输入图更有鲁棒性。那些可能被大量潜在应用所利用的好处可能会产生一系列的社会影响

• 使用我们的研究可以改进和加快从嘈杂/不完整的图(如社交网络)甚至非图结构数据(如文本和图像)中学习有意义的图的过程。
• 利用我们的研究可以提高图神经网络对噪声/不完整的图结构数据的鲁棒性，为下游任务学习良好的节点/图嵌入。