H5W3
当前位置:H5W3 > 其他技术问题 > 正文

图表示学习:图神经网络

这是图表示学习(representation learning)的第二部分——图神经网络(graph neural network, gnn),主要涉及GCN [ICLR’17]、GraphSAGE [NeurIPS’17]、GAT [ICLR’18]和C&S [Arxiv:2010.13993]三篇论文。

关于图数据挖掘/表示学习的内容强烈建议去看Stanford Jure LeskovecTutorial – Representation Learning on Networks (WWW’18)

前一节的图嵌入方法都是非常浅(shallow)的,通过学习得到一个矩阵/查找表,来得到结点的嵌入向量。但是这种方法有以下几点缺陷:

  • 需要$O(\vert V\vert)$的参数量:没有任何参数的共享,所有结点都只有它自己的嵌入向量
  • 内在传导(transductive):很难生成一个没见过的结点的嵌入
  • 无监督方法:没有将结点特征有机整合,而只是关注于图结构

因此我们希望采用更深的方法来得到结点嵌入,最好是直接学习得到一个连续函数,而不是表格映射(这个发展路径其实跟当年强化学习到深度强化学习的过程是类似的)。


回忆稠密网格下的卷积1,原来格点上的数据通过与卷积核的参数分别相乘求和,最后邻居格点的加权和都会汇总到中心格点上。由于卷积核滑过整个图片,而其中的参数多次被使用(参数共享),因此可以更好捕获图片的细节特征。

February 10, 2020 - 图表示学习(2)- 图神经网络


类比到图数据也是一样的,核心思想是从邻居结点整合特征,只是邻居不再是原来的网格紧邻,且每个结点的邻居数目也不一定相同。

聚合特征之后通过黑箱网络,对输出拟合。如下图所示,0层即输入层,也即输入特征。

February 10, 2020 - 图表示学习(2)- 图神经网络

所以关键在于黑箱中是什么,也即聚合信息的方法。

最简单的方式,取平均然后过神经网络。

February 10, 2020 - 图表示学习(2)- 图神经网络

或用矩阵的形式表示($H^{(0)}=X$)

\[H^{(k+1)}=f(H^{(k)},A)=\sigma(AH^{(k)}W^{(k)})\]

其中$A\in\mathbb{R}^{n\times n}$为邻接阵,$H\in\mathbb{R}^{n\times d_{in}}$为特征阵(注意这里一行为一个结点的嵌入向量,与前面的向量写法不同),$W\in\mathbb{R}^{d_{in}\times d_{out}}$为每一层的训练权重矩阵(注意到这里是全层共享参数)。这里可划分为两个步骤:消息聚合特征更新

第一部分消息聚合,即$A$与$H$左乘(稀疏矩阵乘稠密矩阵,图计算),相当于考虑$A$的第$i$行,即第$i$个结点$v_i$,与其邻接的结点的第$j$个特征进行聚合,得到$(i,j)$矩阵元素。

\[(AH^{(k)})_{ij}=\sum_{l}a_{il}h_{lj}=\sum_{v_l\in \mathcal{N}(v_i)}h_{v_l j}
\implies \mathbf{h}_i=\sum_{v_l\in \mathcal{N}(v_i)}\mathbf{h}_{l}\]

第二部分特征更新,将聚合的特征与参数矩阵相乘(稠密阵乘稠密阵,深度学习)

\[\mathbf{h}_i^{(k+1)}=\left(\sum_{v_l\in \mathcal{N}(v_i)}\mathbf{h}_{l}^{(k)}\right)W^{(k)}
=\sum_{v_l\in \mathcal{N}(v_i)}\mathbf{h}_{l}^{(k)}W^{(k)}\]

由于矩阵乘符合结合律,故消息聚合与特征更新顺序可以互换。
如果先聚合再算更新,则对于结点$i$来说需要做$d_i$次维度$d_{in}$的加法与$1$次乘法$d_{in}\mapsto d_{out}$,由握手定理,全图一共是$2|E|$次加法与$|V|$次矩阵向量乘(或$1$次矩阵矩阵乘);而先更新再聚合,对于结点$i$需要做$d_i$次维度$d_{out}$的加法与$d_i$次乘法,全图则是$O(|E|)$的时间复杂度。但事实上由于邻居结点会被多个结点共享,因此用矩阵矩阵乘提前算出$H^{(k)}W^{(k)}$,再去索引聚合,乘法次数同样是$1$次。

这里就可以采用前面的无监督方法作为损失函数,或者用有监督的模型来构造。

总的来说,GNN的模型构造分为以下四步走:

  1. 定义邻居聚集函数(黑箱中是什么)
  2. 定义结点嵌入上的损失函数$L(z_u)$
  3. 对一系列的结点计算图进行训练
  4. 生成结点嵌入

注意到$W_k$和$B_k$都是共享参数,因此模型参数的复杂度是关于$\vert V\vert$次线性的。同时,这种方法可以扩展到未见过的结点。

GCN2

关于GCN的详细介绍,可见论文一作的博客

依照上文的矩阵表示法,

\[H^{(k+1)}=f(H^{(k)},A)=\sigma(AH^{(k)}W^{(k)})\]

尽管该模型已经很强大,但是仍然存在以下两个问题,这也是文2所要解决的:

  1. 注意到$AH^{(k)}$消息聚合时并未将自身考虑进去,因此可以简单地给每个结点添加自环,即$\hat{A}=A+I$
  2. 每个结点的度并不相同,导致$AH^{(k)}$计算时会改变特征向量的比例(scale),那么简单的想法是类似PageRank一样对邻接阵$A$的每一行归一化,即$D^{-1}A$,其中$D$是度对角阵(取逆相当于对角线上元素,即每个结点的度数,直接取倒数)。而如果采用对称的归一化技术(即出入度都考虑),那就得到$D^{-1/2}AD^{-1/2}$。(对称阵的计算可见图论基础

进而得到GCN的传播规则

\[H^{(k+1)}=f(H^{(k)},A)=\sigma\left(\hat{D}^{-\frac{1}{2}}\hat{A}\hat{D}^{-\frac{1}{2}}H^{(k)}W^{(k)}\right)\]

用向量形式来写即

\[\mathbf{h}_v^{(k+1)}=\sigma\left(\sum_{u\in N(v)\cup v}\frac{\mathbf{h}_u^{(k)}}{\sqrt{|N(u)||N(v)|}}W^{(k)}\right)\]

总的时间复杂度是$O(\vert E\vert)$。

GCN很强的一点在于,它还没训练就已经达到DeepWalk的水准了。比如下图展示的是未训练的3层GCN结点嵌入情况,矩阵都是随机初始化的。

February 10, 2020 - 图表示学习(2)- 图神经网络 February 10, 2020 - 图表示学习(2)- 图神经网络

至于为什么是卷积,想想卷积核在稀疏邻接矩阵上划过,聚合时实际上就相当于做卷积了。

GraphSAGE3

GraphSAGE (SAmple & aggreGatE)则是进一步将聚合的思想一般化,之前的聚合函数都是取平均,那现在我采用任意的聚合函数,得到

\[h_v^{(k+1)}=\sigma([W_k\cdot \mathop{AGG}(\{\mathbb{h}_{u}^{(k)},\forall u\in N(v)\}),B_k\mathbb{h}_v^{(k)}])\]

注意中括号表示两个向量(自嵌入+邻居嵌入)直接合并,邻居在GraphSAGE中并不取全部,而是随机取固定数目的邻居。

聚合函数就可以取

  • 平均:最原始方案

\[\mathop{AGG}=\sum_{u\in N(u)}\frac{\mathbb{h}_{u}^{(k)}}{|N(v)|}\]

  • 池化:$\gamma$为元素间(element-wise)平均/最值

\[\mathop{AGG}=\gamma(\{Q\mathbb{h}_{u}^{(k)},\forall u\in N(v)\})\]

  • LSTM:$\pi$为随机置换(permutation)

\[\mathop{AGG}=LSTM([\mathbb{h}_{u}^{(k)},\forall u\in\pi(N(v))])\]

通常GCN和GraphSAGE只需两三层深即可。

从某种意义上,GCN有点像循环神经网络,因为GCN在每一层上都是共享参数的,而每一层就是一整个graph平展开来,每一层的计算都是传播一hop的计算,只有当这一层计算完了(图遍历完了),才进入到下一层的计算。

February 10, 2020 - 图表示学习(2)- 图神经网络

从GraphSAGE的伪代码就更加能体会到这一点:外层做$K$次循环,内层遍历所有结点做消息传递(这其实相当于对整个无向图做一次BFS)

February 10, 2020 - 图表示学习(2)- 图神经网络

GAT 4

回忆NLP中的encoder-decoder模型,由于encoder需要将一整个句子的信息压缩到一个高维空间向量,再送入decoder进行解码,这一个高维空间向量的负担将会非常大,因此研究者就考虑让机器学会判断句子中的不同部分的重要性,从而在解码时更加有针对性地获取特征,此即attention的思想5

February 10, 2020 - 图表示学习(2)- 图神经网络

放到graph中也是类似,原始聚合公式中将不同结点等同对待,因此可以添加一个attention模块,让机器自己学习不同结点的重要性$\alpha_{il}$($v_l$对$v_i$的重要性)。

\[\mathbf{h}_i^{(k+1)}=\sum_{v_l\in \mathcal{N}(v_i)}\alpha_{il}\mathbf{h}_{l}^{(k)}W^{(k)}\]

重要性度量可以是$\phi(h_i,h_l)$(注意这里用了原始特征向量$h_\cdot$),其中$\phi$为可学习的函数,GAT论文中直接采用了单层神经网络。

由于重要性的scale可能不同,因此可以通过归一化方法得到合理的重要性度量指标,这里采用了softmax

\[\alpha_{il}=\frac{\exp(\phi(h_i,h_l))}{\sum_{k\in\mathcal{N}(v_i)}\exp(\phi(h_i,h_k))}\]

更进一步,可以采用多头(multi-head)的attention机制,不同head采用不同$\alpha$,最后再将这些结果合并起来或者取平均。

February 10, 2020 - 图表示学习(2)- 图神经网络

Correct & Smooth (C&S) 6

这篇paper在2020年10月的时候霸榜了OGB的几个数据集,核心是在claim我们不需要GNN这么复杂的模型,用简单的MLP加上一些后处理技巧就可以做到很好的效果了。

分为三步走,第一步用MLP直接暴力拟合(不考虑图结构),第二步correct,第三步smooth。

假设特征矩阵为$X\in\mathbb{R}^{n\times p}$,目标矩阵$Y\in\mathbb{R}^{n\times c}$为one-hot encoding,第一步MLP则是学一个函数$f$使得最小化损失函数之和

\[\sum l(f(X_i),Y_i)\]

可以想象经过$f$得到的是一个softmax的概率,即为各个类别的预测值$\hat{Y}_i$,此为base prediction。

第二步correct,即算预测值和真实值的残差$E=\hat{Y}-Y$,然后用标签传播优化$E$(此时引入图结构,具体优化目标见论文)。这里的idea在于误差应该沿着图的边正相关(base prediction to be positively correlated along edges in the graph),换句话说结点$i$有误差,则其邻居也应该有相似的误差。这一步会得到一个新的估计$\hat{Y}^{(r)}$

第三步smooth,idea是相邻的点应该有相似的label,这样又可以得到另外一个优化函数,再通过另一轮label propagation得到最终结果。

Other Resources

Reference

  1. Petar Veličković, https://petar-v.com/GAT/ 
  2. Thomas N. Kipf, Max Welling (Amsterdam), Semisupervised Classification with Graph Convolutional Networks, ICLR, 2017 (Most cited publication 2
  3. William L. Hamilton, Rex Ying, Jure Leskovec (Stanford), Inductive Representation Learning on Large Graphs, NeurIPS, 2017 
  4. Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò and Yoshua Bengio, Graph Attention Networks, ICLR, 2018 
  5. Stanford CS224n: Natural Language Processing with Deep Learning, Machine Translation 
  6. Qian Huang, Horace He, Abhay Singh, Ser-Nam Lim, Austin R. Benson (Cornell), Combining Label Propagation and Simple Models Outperforms Graph Neural Networks, Arxiv:2010.13993, 2020 (Code

本文地址:H5W3 » 图表示学习:图神经网络