简单理解图神经网络 GNN

前言

图神经网络(Graph Neural Networks,GNN)最早由The Graph Neural Network Model(Gori et al., 2005)提出。近年来,深度学习领域关于图神经网络的研究热情日益高涨,图神经网络已经成为各大深度学习顶会的研究热点。

本文主要介绍图神经网络的基本原理,通过简单的方式理解 GNN, GCN 是如何工作的,尽量把原理说清楚。

Overview

总的来说,GNN 就是做了这么一件事情:利用图的节点信息去生成节点(图)的 Embedding 表示

Graph Neural Network(GNN)

既然是 Graph,那么我们的数据就是一张

其中hA,hB,hC,hD,hEh_A, h_B, h_C, h_D, h_E分别是节点A,B,C,D,EA, B, C, D, E的所包含的信息,你也可以简单理解为是这个节点的特征

GNN 可分为三步:1. 聚合;2. 更新;3. 循环。

首先是聚合。通过观察上面的图我们可以发现,节点AA有三个邻居节点B,C,DB,C,D,显然这是一个非常重要的信息,节点AA与这三个节点有密切的联系。举个例子,如果我们不知道节点AA是否有钱,但是我们发现节点B,C,DB,C,D都非常有钱,那么很大程度上节点AA也非常有钱,也就是通过节点的邻居信息判断这个节点的信息。那么要如何利用这个特征呢?

就像在一开始说的,GNN 就是利用图的节点信息去生成节点(图)的 Embedding 表示,这也就是聚合。我们可以通过简单的方式获取邻居的信息:

NA=ahB+bhC+chD=a(2,2)+b(3,3)+c(4,4)\begin{aligned}N_A &= a \cdot h_B + b \cdot h_C + c \cdot h_D \\ &= a \cdot (2,2) + b \cdot (3,3) + c \cdot (4,4) \end{aligned}

其中a,b,ca,b,c为常数,也可以通过训练得到或者是手动设定,我们这里简单理解为常数。

好了,通过上面的简单的方式,我们得到了节点AA的邻居的信息,我们将这个信息作为节点AA信息的补充

再来是更新。当我们获取了邻居的信息后,自然也不能忘了节点AA本身的信息:

(hA+αNA)(h_A + \alpha \cdot N_A)

其中α\alpha为常数(同样也可以通过训练得到或者是手动设定,这里简单理解为常数)。当然了,肯定不能直接简单加起来就作为节点AA的新的信息,而是需要进行一些处理,其实也就是常规的线性变换,再过个激活函数:

hA=σ(W(hA+αNA))\begin{aligned}h_A = \sigma (W (h_A + \alpha \cdot N_A)) \end{aligned}

其中σ\sigma为激活函数,WW为权重矩阵,hAh_A为节点AA的信息,NAN_A为节点AA的邻居信息。

简而言之,聚合更新就是把节点的邻居的信息添加到这个节点中。

现在,一次聚合操作就完成了,经过一次聚合之后:

  • 节点AA中有B,C,DB,C,D的信息;
  • 节点BB中有A,CA,C的信息;
  • 节点CC中有A,B,D,EA,B,D,E的信息;
  • 节点DD中有A,CA,C的信息;
  • 节点EE中有CC的信息;

第二次聚合也是类似的,仍然以节点AA为例,计算节点AA的邻居信息。但此时当节点AA聚合节点CC的时候,由于节点CC中包含了节点EE的信息,所以这时节点AA获得了二阶邻居EE的信息。

归根结底,GNN 就是一个提取特征的方法。

Graph Convolutional Network(GCN)

好了,讲完了 GNN 的总体思路,让我们具体来看看 GCN 是怎么做的。还是以下面这幅图为例:

同样的,我们需要获取节点AA的邻居信息:

NA=ahB+bhC+chD=a(2,2)+b(3,3)+c(4,4)\begin{aligned}N_A &= a \cdot h_B + b \cdot h_C + c \cdot h_D \\ &= a \cdot (2,2) + b \cdot (3,3) + c \cdot (4,4) \end{aligned}

这里我们使用矩阵的方式来表示图,邻接矩阵AA,以及隐藏层矩阵HH

A=[0111010100110111010000100]H=[1122334455]A = \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{bmatrix} \quad H = \begin{bmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \end{bmatrix}

这里假设a=b=c=1a=b=c=1,那么,节点AA的邻居信息就可以表示为:

NA=[01110][1122334455]=[99]=A0,H\begin{aligned} N_A &= \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \end{bmatrix} = \begin{bmatrix}9 & 9\end{bmatrix} \\ &= A_{0,*}H \end{aligned}

其中A0,A_{0,*}表示矩阵AA的第一行,即节点AA的邻居关系。另外别忘了加上节点AA自身的信息,具体来说,可以通通过加上单位矩阵II的方式实现:

NA=([01110]+[10000])[1122334455]=[1010]=(A0,+I0,)H\begin{aligned} N_A &= \left( \begin{bmatrix} 0 & 1 & 1 & 1 & 0 \end{bmatrix} + \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \end{bmatrix}\right) \begin{bmatrix} 1 & 1 \\ 2 & 2 \\ 3 & 3 \\ 4 & 4 \\ 5 & 5 \end{bmatrix} = \begin{bmatrix}10 & 10\end{bmatrix} \\ &= (A_{0,*} + I_{0,*})H \end{aligned}

同理,我们可以得到所有节点的邻居信息NN:

N=(A+I)H:=A~H\begin{aligned}N &= (A + I)H \\ &:= \tilde{A}H \end{aligned}

A~=A+I\tilde{A} = A + I

现在,就可以写出隐藏层的更新方程了,与之前的思路类似,常规的线性变换,再过个激活函数:

H(l+1)=σ(A~H(l)W(l))H^{(l+1)} = \sigma (\tilde{A}H^{(l)}W^{(l)})

其中ll为循环层数,σ\sigma为激活函数,WW为隐藏层的权重矩阵。

现在还有最后一个问题,你会发现,现在我们的矩阵A~\tilde{A}中,非零元素均为11,即简单的将当前节点的邻居信息相加,可以想象的是它会越来越「膨胀」。

A~=[1111011100111111011000101]\tilde{A} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix}

实际上,解决这个问题并不麻烦,归一化就行了。在图 Graph 中,我们可以借助「度」来进行归一化。具体为什么这么做、为什么要进行归一化我们放在后面讲:关于归一化的一些问题

具体什么是这里就不赘述了,给出度矩阵:

D=[3000002000004000002000001]D~=[4000003000005000003000002]D = \begin{bmatrix} 3 & 0 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 4 & 0 & 0 \\ 0 & 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 0 & 1 \end{bmatrix} \quad \tilde{D} = \begin{bmatrix} 4 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 \\ 0 & 0 & 5 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 2 \end{bmatrix}

其中,D,D~D,\tilde{D}分别是A,A~A,\tilde{A}的度矩阵。

这里直接给出 GCN 论文 Semi-Supervised Classification with Graph Convolutional Networks 中的归一化方法,它的本质是对称归一化的拉普拉斯矩阵

D~1/2A~D~1/2\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}

关于上面的归一化方法,我们同样在后面具体讨论:关于归一化的一些问题,如果你不想了解细节也没关系,你只需要知道它的作用即可。

至此为止,我们可以得到完整的隐藏层的更新方程:

H(l+1)=σ(D~1/2A~D~1/2H(l)W(l))H^{(l+1)} = \sigma (\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})

其中ll为循环层数,σ\sigma为激活函数,WW为隐藏层的权重矩阵,A~=(A+I)\tilde{A} = (A + I)D~\tilde{D}A~\tilde{A}的度矩阵。虽然式子长得难看了点,但我想如果你了解了上面讲的内容,也就不难理解了。

关于归一化的一些问题

现在,让我们回到上面没解决的问题:

  1. 为什么要进行归一化?
  2. 论文中为什么使用D~1/2A~D~1/2\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}进行归一化?

问题一

首先,为什么要进行归一化?这个问题其实在上面也有简单的解释。矩阵A~\tilde{A}中,非零元素均为11,那么这就意味着,在计算A~H\tilde{A}H时,就是简单的将当前节点的邻居信息相加,各个邻居一视同仁。

问题二

归一化

一个直观的归一化方法是:平均化聚合每个节点的信息

A~=[1111011100111111011000101][1/41/41/41/401/31/31/3001/51/51/51/51/51/301/31/30001/201/2]=D~1A~\tilde{A} = \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \quad \rightarrow \quad \begin{bmatrix} 1/4 & 1/4 & 1/4 & 1/4 & 0 \\ 1/3 & 1/3 & 1/3 & 0 & 0 \\ 1/5 & 1/5 & 1/5 & 1/5 & 1/5 \\ 1/3 & 0 & 1/3 & 1/3 & 0 \\ 0 & 0 & 1/2 & 0 & 1/2 \end{bmatrix} =\tilde{D}^{-1}\tilde{A}

其中,D~1\tilde{D}^{-1}A~\tilde{A}的度矩阵的逆。从数学的角度,上面的平均化也就是D~1A~\tilde{D}^{-1}\tilde{A}的过程。现在我们已经将求和变成了加权平均,权值之后归一化为11了。

对称归一化

那么为什么不直接使用简单的平均化方法呢?第一个缺点就是D~1A~\tilde{D}^{-1}\tilde{A}不再是对称矩阵了,这不是我们想要看到的。

第二个缺点我们来看一个比较特殊的例子,在下面这幅图中,我们发现节点AA只有一个邻居节点CC,另一方面节点CC有着包括AA在内的 6 个邻居节点。

按照上面的平均化思路,当节点AA聚合节点CC时,节点CC所有的特征会完全加到节点AA上,但实际上,节点AA和节点CC的差距是很明显的。举个例子,节点AA是我,节点CC是老板,老板管着一票人,我只是一个苦命的打工人,不可能说把老板的工资完全加到我身上,然后我拿着一半我的工资,一半老板的工资,美滋滋。

那么一个科学的方法就是同时考虑节点AACC的邻居数量,即「度」,具体来说,可以考虑几何平均数D~iiD~jj\sqrt{\tilde{D}_{ii} \tilde{D}_{jj}},回到D~1/2A~D~1/2\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}

(D~1/2A~D~1/2H)i=(D~1/2A~)iD~1/2H=(kD~ik1/2A~i)D~1/2H=D~ii1/2jA~ijkD~jk1/2Hj=D~ii1/2jA~ijD~jj1/2Hj=j1D~iiD~jjA~ijHj\begin{aligned} (\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H)_i &= (\tilde{D}^{-1/2}\tilde{A})_i \tilde{D}^{-1/2}H \\ &= \left( \sum_k \tilde{D}_{ik}^{-1/2}\tilde{A}_i \right) \tilde{D}^{-1/2}H \\ &= \tilde{D}_{ii}^{-1/2} \sum_j \tilde{A}_{ij} \sum_k \tilde{D}_{jk}^{-1/2} H_j \\ &= \tilde{D}_{ii}^{-1/2} \sum_j \tilde{A}_{ij} \tilde{D}_{jj}^{-1/2} H_j \\ &= \sum_j \frac{1}{\sqrt{\tilde{D}_{ii} \tilde{D}_{jj}}} \tilde{A}_{ij} H_j \end{aligned}

不考虑复杂的推导过程,只看结论,论文中的对称归一化方法就是使用了上面说的结论,同时考虑两个节点的邻居数量。那么,前面的例子就变成了:

D~1/2A~D~1/2=[120000013000001500000130000012][1111011100111111011000101][120000013000001500000130000012]=[141231251230123131150012511515115110123011513000110012]\begin{aligned} \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} &= \begin{bmatrix} \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{5}} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{3}} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} \end{bmatrix} \begin{bmatrix} 1 & 1 & 1 & 1 & 0 \\ 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 1 \end{bmatrix} \begin{bmatrix} \frac{1}{2} & 0 & 0 & 0 & 0 \\ 0 & \frac{1}{\sqrt{3}} & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{\sqrt{5}} & 0 & 0 \\ 0 & 0 & 0 & \frac{1}{\sqrt{3}} & 0 \\ 0 & 0 & 0 & 0 & \frac{1}{\sqrt{2}} \end{bmatrix}\\ &= \begin{bmatrix} \frac{1}{4} & \frac{1}{2\sqrt{3}} & \frac{1}{2\sqrt{5}} & \frac{1}{2\sqrt{3}} & 0 \\ \frac{1}{2\sqrt{3}} & \frac{1}{3} & \frac{1}{\sqrt{15}} & 0 & 0 \\ \frac{1}{2\sqrt{5}} & \frac{1}{\sqrt{15}} & \frac{1}{5} & \frac{1}{\sqrt{15}} & \frac{1}{\sqrt{10}} \\ \frac{1}{2\sqrt{3}} & 0 & \frac{1}{\sqrt{15}} & \frac{1}{3} & 0 \\ 0 & 0 & \frac{1}{\sqrt{10}} & 0 & \frac{1}{2} \end{bmatrix} \end{aligned}

最后,大佬们是如何想出D~1/2A~D~1/2\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}的呢?其实,这个公式很接近对称归一化的拉普拉斯矩阵

Lsym=D1/2LD1/2=ID1/2AD1/2L^{sym} = D^{-1/2}LD^{-1/2} = I - D^{-1/2}AD^{-1/2}

Graph Attention Network(GAT)

如果你熟悉 Attention 机制,那么在了解了上面的内容之后,就不难理解 Graph Attention Network(GAT) 了,无非就是对邻居节点的权重进行自动学习,这里就不再细说了。

总结

最后,还是想强调一点,GNN 就是做了这么一件事情:利用图的节点信息去生成节点(图)的 Embedding 表示。就是那么一个 Embedding 的方法。

参考资料