图表示学习方法概述

发表于 分类于 本文字数： 3.5k 阅读时长 ≈ 6 分钟

图表示学习将稀疏的图数据表征为稠密的较低维向量以用于后续任务。 例如，在基于“用户-商品”二部图的推荐系统两侧分别补充用户与商品的异构图信息，并利用GNN来捕捉用户与商品间的高阶关联[1]。

基本定义

  • 图节点数量为\(N\)，每个节点的特征向量长度为\(F\)
  • 邻接矩阵\(A \in \mathbb{R}^{N \times N}\)表示图结构
  • 属性矩阵\(X \in \mathbb{R}^{N \times F}\)表示节点的特征

需要指出，此处的邻接矩阵只用于概念的表达，在实践中会使用更优雅的邻接列表（一个由若干具备两个元素的列表构成的列表）表示图的结构。 原因有两点：

  • 空间复杂度：邻接列表的为\(O(n_{edge})\)，一般来说会显著低于稀疏的邻接矩阵的\(O(n_{node}^2)\)；
  • 当元素的排列顺序发生变化时，邻接矩阵也会发生变化，而不同的邻接矩阵对应的学习结果可能是不同的。

基于序列处理的方法

在图中随机游走以搜索序列，将它们看作句子，节点看作词，这样就可以利用NLP的方法来表示图中的节点。典型的方法比如 DeepWalk、Node2Vec等。

DeepWalk 通过随机游走将图转化成节点序列，设置中心节点左右距离为 w 的节点为 上下文 ( context )。同词向量方法一样，DeepWalk 本质上建模了中心节点与上下文节点之间的共现关系，这种关系的学习也采用了负采样的优化手段。

基于随机游走的方法相比上一类方法，最大的优点是通过将图转化为序列的方式从而实现了大规模图的表示学习。但是这也导致了两个缺点：一是将图转化成序列集合，图本身的结构信息没有被充分利用；二是该学习框架很难自然地融合进图中的属性信息进行表示学习。

基于神经网络的方法

图神经网络（Graph Neural Networks，GNN）的最初的构想是由Scarselli等人在2009年提出的[2]。 它依赖于一个事实，即每个节点都可以用它的邻域来描述。 来自邻域的信息可以聚合并用于计算更复杂和高级的特征，而节点脱离了其邻域将丢失其所有信息。 因此，在不考虑节点连接性的前提下，使用任意可微分模型（如MLP）分别对每个节点进行嵌入，最后再对邻域或整张图进行某种池化（如最简单的求和），即可基于节点的嵌入实现上游的任务（如，基于邻域的池化结果做节点或边的预测，或基于整张图的池化结果做图的分类）。 在上述训练过程中没有使用图的连通性信息，每个节点都是独立处理的，仅在汇集信息时使用了连通性信息。 尽管简单，然而这个模型已经是一个GNN。

在此基础上，我们让GNN在学习嵌入的过程中吸收图的连通性信息。 以学习节点嵌入为例，一开始，每个节点\(v_i\)都与一个状态相关联。 某个节点一开始可能拥有一个随机的嵌入\(h_i^t\)（为了简单起见，忽略节点属性）。 在算法的每次迭代（对应到模型，即每层消息传递函数）中，节点使用一个简单的神经网络层积累来自其邻居\(\mathcal{N}(v_i)\)的输入:

\[h_i^t=\sum_{v_j \in \mathcal{N}(v_i)}\sigma(Wh_j^{t−1}+b)\]

其中，\(W \in \mathbb{R}^{d \times d}\)和\(b \in \mathbb{R}^d\)是可训练参数（其中\(d\)为嵌入的维数），\(\sigma\)是非线性函数，\(t\)表示算法的第\(t\)次迭代。 这个方程可以递归地应用，直到达到一个特定的目标。 在每次迭代中，之前的状态（在之前的迭代中计算的状态）被用来计算新的状态，而每增加一次迭代，参与表征节点的节点范围就再向外扩大一跳。 比如，当迭代轮数为3时，每个节点的嵌入是基于其三跳范围内的邻域优化的。 从上面的式子中还可以看出，GNN的每一层对图进行了更新，但保持了图结构的不变性。

在实践中，节点信息的维度可能和边的不同，因此会产生将节点信息“路由”到边缘（即，用节点表示的池化表征边缘，以在缺失边缘信息的情况下对边缘进行预测等）或将边缘信息“路由”到节点等不同的GNN用法。 甚至还可以学习节点到节点、边到边、节点到边、边到节点的映射，将它们四个组合以得到新的节点和边的表征；还可以把图的全局信息融入到节点或边的表示中去。

总的来说，

  1. 并不是模型越复杂、参数量越多，效果就一定越好。 一般来说，对于GNN的层数或模型的嵌入维度，更高的值会提升性能的下限和均值。 性能的上限提升的概率则相对更低。例如，可能在某些任务中发现2个GNN层的表现好于3个，这可能是因为对于某些数据，多层的GNN在更大的范围内广播信息，“稀释”了节点的表达。

  2. 某些选项对GNN的效果影响取决于数据。 增多参与学习的图组件（节点、边、全局）并丰富它们之间消息传递的类型对结果的改善可能是有限的。 例如，当边本身具备的语义（属性）十分匮乏时，将边的表征作为最终训练目标的一部分仍会对结果产生的增益，但十分有限。

不论如何，对于一个基于学习的模型而言，比起改进模型的细节，在图中加入更多有效（明确、可学习）的语义（属性）可能对结果的提升更有帮助。

上述GNN原型可以轻松拓展到存在异构边或节点的图，具体办法是为不同类型指定不同的消息传递步骤，或对图进行分层，在不同的层（例如，最底层由原始的图节点构成；中间层包含一些表征某些抽象语义的节点，它们与底层节点之间的边用来表征节点之间复杂的语义共享关系；最上层则是代表图全局属性的节点，该节点和中间层节点同样存在边的联系）上分别进行学习，在训练期间让它们进行交替或融合。最后，当应用到批处理（mini batch）时，可以选用的采样方式主要包括随机选取若干节点+拓展邻域、随机游走、随机游走+拓展邻域、随机选取单个节点+拓展邻域等。当图的度较高时，也有基于边进行批采样的方法。

损失函数

1. 重构损失（Reconstruction Loss）

定义一个适用于图的自编码器（Graph AutoEncoder）如下：

\[Z=GNN(X,A), \hat{A}=\sigma(ZZ^T)\]

其中使用了GNN模型同时对图的属性（\(X\)）与结构（\(A\)）进行编码学习，得到一个对所有节点集合的嵌入（embedding，即\(Z\)）。 随后，使用向量的内积表示节点之间的邻接关系，以此得到一个重构的邻接矩阵\(\hat{A}\)。 其中，内积本质上收集（池化）了与每个节点存在边的所有节点的特征。 因此，自编码器的重构损失可以定义为：

\[\mathcal{L}_{recon}=\Vert \hat{A}-A \Vert^2\]

2. 对比损失（Contrastive Loss）

自监督学习中常用的对比损失形式为： \[L=-log\left[\frac{exp(s_{i,i}/\tau)}{\sum_{k\neq i}exp(s_{i,k}/\tau)+exp(s_{i,i}/\tau)}\right]\]

该损失函数要求第\(i\)个样本和它的另一个正样本之间的相似度\(s_{i,i}\)尽可能大，而与其他负样本之间的相似度尽可能小。其中，温度系数\(\tau\)的引入使得距离更近的负样本可以拥有更大的惩罚（这种性质也成为 Hardness-Awareness，困难样本感知）。

特别地，孪生神经网络中的对比损失函数常见为如下形式： \[L=1/2N\sum^N_{n=1}yd^2+(1-y)max(margin-d, 0)^2, d=\left\|a_n-b_n\right\|^2\]

其中，\(d\)是两个样本的欧氏距离，\(y\)是一个标签，指示两样本的相似（匹配）程度（1为相似，0为不相似）。当\(y=1\)时，损失函数只留第一项，即相似的样本的距离应尽可能小。当\(y=0\)时，损失函数只留后一项。对于不相似的样本，\(d\)越小，损失越大，即不相似的样本的距离应尽可能大。

参考文献

本文主要参考
A Gentle Introduction to Graph Neural Networks. https://distill.pub/2021/gnn-intro/ （包含PlayGround）

其他参考文献包括
[1] 基于GNN的图表示学习及其应用. https://zhuanlan.zhihu.com/p/113235806
[2] The Graph Neural Network Model. IEEE Transactions on Neural Networks, 2009.
[3] CVPR2021自监督学习论文: 理解对比损失的性质以及温度系数的作用. https://zhuanlan.zhihu.com/p/357071960