图神经网络(GNN)
这一讲我们将介绍一种特殊的神经网络——图神经网络。前面我们接触的神经网络处理的数据都具有简单规则的结构(如CNN的像素空间数据,RNN的序列数据),而它们无法处理复杂结构的数据(如社交网络、交通路网、分子结构等)。因此,2005年Gori等人首次提出图神经网络概念,并在2009年发表论文The graph neural network model 正式提出GNN。
在分析图神经网络的结构之前,首先需要引入一些图论的基本概念:
(关系)图的本质是无序的集合,通过节点和边表示(G = ( V , E ) G=(V,E) G = ( V , E ) ,这里假定为无向无自环图);每个节点的参数共享(类似CNN的卷积核与RNN的时间步)。
定义度数矩阵D = { d 1 , ⋯ , d ∣ v ∣ } D=\{d_1,\cdots,d_{|v|}\} D = { d 1 , ⋯ , d ∣ v ∣ } ,其中d i d_i d i 表示第i i i 个节点的度数(相连邻居节点N ( v i ) \mathcal{N}(v_i) N ( v i ) 数量),tr D = ∑ v d v = 2 ∣ E ∣ \displaystyle \text{tr}D=\sum_{v}d_v=2|E| tr D = v ∑ d v = 2∣ E ∣ ;邻接矩阵A A A (元素只有0 0 0 和1 1 1 )表示连接关系;节点之间的最短路径长度称为跳数。
图的每个节点自身用特征表示,得到节点特征矩阵X ∈ R ∣ V ∣ × d X\in\R^{|V|\times d} X ∈ R ∣ V ∣ × d ;图神经网络的任务就是基于这些特征预测节点的标签。
图具有置换等变性与置换不变性:考虑任意置换矩阵P ∈ R ∣ V ∣ × ∣ V ∣ P\in\R^{|V|\times |V|} P ∈ R ∣ V ∣ × ∣ V ∣ ,则节点输出预测F θ ( P X , P A P ⊤ ) = P F θ ( X , A ) F_\theta(PX,PAP^\top)=PF_\theta(X,A) F θ ( P X , P A P ⊤ ) = P F θ ( X , A ) ,整图预测g θ ( P X , P A P ⊤ ) = g θ ( X , A ) g_\theta(PX,PAP^\top)=g_\theta(X,A) g θ ( P X , P A P ⊤ ) = g θ ( X , A ) 。
GNN消息传递
如何刻画图神经网络的前向传播?GNN的前向传播(也称为消息传递)主要分为三步(初始化h v ( 0 ) = x v \boldsymbol{h}_v^{(0)}=\boldsymbol{x}_v h v ( 0 ) = x v ):
收集:获取邻近节点信息(特征)m v u ( t ) = M msg ( t ) ( x v ( t ) , x u ( t ) , e v u ) \boldsymbol{m}_{vu}^{(t)} = M_{\text{msg}}^{(t)}\left(\boldsymbol{x}_v^{(t)}, \boldsymbol{x}_u^{(t)}, \boldsymbol{e}_{vu}\right) m v u ( t ) = M msg ( t ) ( x v ( t ) , x u ( t ) , e v u ) 【x v \boldsymbol{x}_v x v 为节点v v v 的特征,e v u \boldsymbol{e}_{vu} e v u 为边的输入特征】
聚合:将收集到的信息压缩为摘要 m v ( t ) = AGG ( t ) { { m v u ( t ) : u ∈ N ( v ) } } \boldsymbol{m}_v^{(t)} = \text{AGG}^{(t)}\left\{\left\{\boldsymbol{m}_{vu}^{(t)} : u \in \mathcal{N}(v)\right\}\right\} m v ( t ) = AGG ( t ) { { m v u ( t ) : u ∈ N ( v ) } } 【保留重复特征】
聚合函数主要包括求和/均值/逐维最大值,它们的信息保留能力不尽相同。
更新:与自身已有信息结合得到新特征表示 h v ( t + 1 ) = UPDATE ( h v ( t ) , m v ( t ) ) \boldsymbol{h}_v^{(t+1)} = \text{UPDATE}\left(\boldsymbol{h}_v^{(t)}, \boldsymbol{m}_v^{(t)}\right) h v ( t + 1 ) = UPDATE ( h v ( t ) , m v ( t ) )
不过实际上,早期的GNN的迭代公式更接近RNN,可以概括为h v ( t ) = f w ( x v , ∑ u ∈ N ( v ) h v ( t − 1 ) ) \displaystyle\boldsymbol{h}_v^{(t)}=f_w\left(\boldsymbol{x}_v,\sum_{u\in\mathcal{N}(v)}\boldsymbol{h}_v^{(t-1)}\right) h v ( t ) = f w x v , u ∈ N ( v ) ∑ h v ( t − 1 ) ,重复迭代直到h v ( t ) \boldsymbol{h}_v^{(t)} h v ( t ) 收敛。上述框架是在2017年由Google团队总结归纳出的,称作消息传递神经网络,即MPNN。
图卷积网络(GCN)
早期的GNN计算效率低,且对超参数和网络结构极其敏感,因此并没有引起广泛关注。直到2017年Thomas N. Kipf和Max Welling提出图卷积网络才促成了GNN的爆发式发展(大概2019年开始)。下面我们就来简单了解其算法(原始论文里就较多复杂数学推导,这里就不详细展开了,感兴趣的可以看看这篇知乎文章 ):
首先,为了保留每个节点原始特征,GCN对图中所有节点“强行”引入了自环。此时记邻接矩阵A ~ = A + I \tilde{A}=A+I A ~ = A + I ,度数矩阵D ~ = diag ( A ~ 1 n ) = A + I \tilde{D}=\text{diag}(\tilde{A}\boldsymbol{1}_n)=A+I D ~ = diag ( A ~ 1 n ) = A + I 。
然后,再考虑计算聚合函数时,考虑两种方案:
行归一化:R = D ~ − 1 A ⟹ ( R X ) v = 1 d ~ v ∑ u ∈ N ( v ) ∪ { v } x u R=\tilde{D}^{-1}A\Longrightarrow (RX)_v=\displaystyle\frac{1}{\tilde{d}_v}\sum_{u\in\mathcal{N}(v)\cup\{v\}}\boldsymbol{x}_u R = D ~ − 1 A ⟹ ( R X ) v = d ~ v 1 u ∈ N ( v ) ∪ { v } ∑ x u
对称归一化:S = D ~ − 1 / 2 A D ~ − 1 / 2 ⟹ ( S X ) v = ∑ u ∈ N ( v ) ∪ { v } x u d ~ v d ~ u S=\tilde{D}^{-1/2}A\tilde{D}^{-1/2}\Longrightarrow (SX)_v = \displaystyle\sum_{u \in \mathcal{N}(v) \cup \{v\}} \frac{\boldsymbol{x}_u}{\sqrt{\tilde{d}_v \tilde{d}_u}} S = D ~ − 1/2 A D ~ − 1/2 ⟹ ( S X ) v = u ∈ N ( v ) ∪ { v } ∑ d ~ v d ~ u x u
相比行归一化,对称归一化同时考虑了消息两端的度数,同时因为S S S 是对称矩阵,因此相比R R R 具有更好的性质(如可以进行正交对角化)。
GCN的前向传播矩阵形式(第l l l 层到第l + 1 l+1 l + 1 层)可以表示为:
H ( l + 1 ) = σ ( S H ( l ) W ( l ) ) H^{(l+1)}=\sigma(SH^{(l)}W^{(l)}) H ( l + 1 ) = σ ( S H ( l ) W ( l ) )
特别地,H ( 0 ) = X H^{(0)}=X H ( 0 ) = X ,而W ( l ) W^{(l)} W ( l ) 在第l l l 层由所有节点共享。【此处省略了偏置,不过这在GCN中影响不大】
在实际配置中,原始GCN只设置了2至3层前向传播,这也导致每个节点最多聚合其两至三跳邻居节点的信息(类似CNN的局部感受野)。
最后我们讨论下GCN的算法复杂度。GCN的一层前向传播计算可以分解为特征变换(T = H W T=HW T = H W )和稀疏传播S T ST S T ,两者复杂度分别为O ( n ⋅ d i n ⋅ d o u t ) O(n\cdot d_{in}\cdot d_{out}) O ( n ⋅ d in ⋅ d o u t ) 和O ( ( 2 ∣ E ∣ + n ) d o u t ) = O ( ( ∣ E ∣ + n ) d o u t ) O((2|E|+n)d_{out})=O((|E|+n)d_{out}) O (( 2∣ E ∣ + n ) d o u t ) = O (( ∣ E ∣ + n ) d o u t ) (d i n , d o u t d_{in},d_{out} d in , d o u t 分别为W W W 的输入与输出维度),因此总复杂度为O ( n ⋅ d i n ⋅ d o u t + ( ∣ E ∣ + n ) d o u t ) O(n\cdot d_{in}\cdot d_{out}+(|E|+n)d_{out}) O ( n ⋅ d in ⋅ d o u t + ( ∣ E ∣ + n ) d o u t ) 。
为什么S T ST S T 称为稀疏传播?因为实际上处理的图数据中节点数往往远大于边数,这会使得S S S 变为一个极度稀疏的矩阵。
GraphSAGE与SAT
除了GCN之外,讨论图神经网络也离不开另外两个典型代表:GraphSAGE和SAT。它们都于2017年被提出,都在GCN的基础上进行了改进。
GraphSAGE中的SAGE表示采样(Sample)与聚合(Aggregate),其主要创新是对节点邻居进行随机采样,从而降低了处理大量节点图的计算量。具体的前向传播公式可表示为:
m v ( ℓ ) = 1 ∣ S ℓ ( v ) ∣ ∑ u ∈ S ℓ ( v ) h u ( ℓ ) h v ( ℓ + 1 ) = σ ( [ h v ( ℓ ) ∥ m v ( ℓ ) ] W ( ℓ ) + b ( ℓ ) ) \begin{aligned}
\boldsymbol{m}_v^{(\ell)} &= \frac{1}{|\mathcal{S}_\ell(v)|} \sum_{u \in \mathcal{S}_\ell(v)} \boldsymbol{h}_u^{(\ell)}\\
\boldsymbol{h}_v^{(\ell+1)} &= \sigma \left( [\boldsymbol{h}_v^{(\ell)} \| \boldsymbol{m}_v^{(\ell)}] W^{(\ell)} + b^{(\ell)} \right)
\end{aligned} m v ( ℓ ) h v ( ℓ + 1 ) = ∣ S ℓ ( v ) ∣ 1 u ∈ S ℓ ( v ) ∑ h u ( ℓ ) = σ ( [ h v ( ℓ ) ∥ m v ( ℓ ) ] W ( ℓ ) + b ( ℓ ) )
其中S ℓ ( v ) \mathcal{S}_\ell(v) S ℓ ( v ) 是本层采到的邻居集合,权重矩阵W ( ℓ ) ∈ R 2 d i n × d o u t W^{(\ell)}\in\R^{2d_{in}\times d_{out}} W ( ℓ ) ∈ R 2 d in × d o u t 。【自身特征与聚合邻居特征直接拼接,不叠加】
虽然模型可能会漏掉重要邻居,但由于多轮训练每次抽取的邻居不同,模型依然能学到泛化能力。
另一方面,与传统GCN训练目标为得到每个节点的表示(嵌入)不同,GraphSAGE的训练目标转变为权重W ( l ) W^{(l)} W ( l ) ,这使得其更擅长处理在线学习场景(如动态图)。
GAT则从另一个角度进行优化:借鉴了Transformer的注意力机制,用注意力分数取代聚合权重。具体公式(省略偏置):
z u = h u ( ℓ ) W ( ℓ ) e v u = LeakyReLU ( [ z v ∥ z u ] a ) α v u = softmax ( e v u ) = exp ( e v u ) ∑ k ∈ N ( v ) ∪ { v } exp ( e v k ) h v ( ℓ + 1 ) = σ ( ∑ u ∈ N ( v ) ∪ { v } α v u z u ) \begin{aligned}
\boldsymbol{z}_u &= \boldsymbol{h}_u^{(\ell)} W^{(\ell)} \\
\boldsymbol{e}_{vu} &= \operatorname{LeakyReLU}\left( [\boldsymbol{z}_v \| \boldsymbol{z}_u]\boldsymbol{a} \right) \\
\alpha_{vu} &= \operatorname{softmax}(\boldsymbol{e}_{vu})=\frac{\exp(\boldsymbol{e}_{vu})}{\sum_{k \in \mathcal{N}(v) \cup \{v\}} \exp(\boldsymbol{e}_{vk})} \\
\boldsymbol{h}_v^{(\ell+1)} &= \sigma \left( \sum_{u \in \mathcal{N}(v) \cup \{v\}} \alpha_{vu} \boldsymbol{z}_u \right)
\end{aligned} z u e v u α v u h v ( ℓ + 1 ) = h u ( ℓ ) W ( ℓ ) = LeakyReLU ( [ z v ∥ z u ] a ) = softmax ( e v u ) = ∑ k ∈ N ( v ) ∪ { v } exp ( e v k ) exp ( e v u ) = σ u ∈ N ( v ) ∪ { v } ∑ α v u z u
其中a \boldsymbol{a} a 为注意力打分权重(本质是加性注意力,与Transformer的缩放点积注意力不同),W W W 为可学习的特征变换矩阵。
GAT也适用于多头注意力,只需将每个头的输出拼接在一起即可:
r v ( k ) = σ ( ∑ u α v u ( k ) h u W ( k ) ) h v ′ = r v ( 1 ) ∥ ⋯ ∥ r v ( K ) \begin{aligned}
\boldsymbol{r}_v^{(k)} &= \sigma \left( \sum_{u} \alpha_{vu}^{(k)} \boldsymbol{h}_u W^{(k)} \right) \\
\boldsymbol{h}'_v &= \boldsymbol{r}_v^{(1)} \parallel \cdots \parallel \boldsymbol{r}_v^{(K)}
\end{aligned} r v ( k ) h v ′ = σ ( u ∑ α v u ( k ) h u W ( k ) ) = r v ( 1 ) ∥ ⋯ ∥ r v ( K )
当然输出也可以改为对每个头输出取平均。
2021年,另一团队提出了GATv2,在GAT的基础上将注意力打分权重a \boldsymbol{a} a 放到了激活函数外面,从而变为动态注意力,模型更加灵活。
预测任务与训练过程
在了解了GNN的基本结构与算法之后,下面就来介绍GNN如何与下游预测任务进行对接。
GNN适用的预测任务主要有三种:对节点的预测(预测某个节点属于什么类别)、对链接的预测(预测两个节点之间是否存在某种关系)和图级预测(预测整张图的属性)。
节点预测
在节点预测中,GNN的预测头与Transformer非常类似,就是一个线性层 + softmax:
\begin{aligned}
\boldsymbol{z}_v &= \boldsymbol{h}_v^{(L)} W_{\mathrm{cls}} + \boldsymbol{b}_{\mathrm{cls}} \in \mathbb{R}^{1 \times C} \\
p_{vc} &= \frac{\exp(z_{vc})}{\sum_{j=1}^C \exp(z_{vj})} \Longrightarrow \widehat{y}_v = \arg \max_c p_{vc}
\end{aligned}
$$
其中$W_{\text{cls}}\in\R^{d_{out}\times C}$,$C$为类别个数。
+ 对于监督分类预测任务,损失函数采用交叉熵损失即可。真实标签可以采用One-Hot编码,这样损失函数可转化为$\ell_v=-\log p_{v,y_v}$【$y_v$为真实类别】。
+ 在实际训练中,可以将节点划分为训练/验证/测试集,那么损失函数就是训练节点损失函数的平均:
$$
\mathcal{L}=-\frac{1}{|\mathcal{T}|}\sum_{v\in\mathcal{T}}\ell_v
$$
不过在消息传递过程中非训练节点的信息仍然会传递到训练节点。【但不会导致标签泄漏,因为非训练标签不参与消息传递】
### 链接预测
在链接预测中,首先对链接两侧节点表示进行内积计算得到链接打分(满足对称性,故默认无向),然后经过Sigmoid函数转化为概率即可:
$$
s_{uv}=\boldsymbol{h}_u^{(L)}(\boldsymbol{h}_v^{(L)})^\top\Longrightarrow p_{uv}=\sigma(s_{uv})=\frac{1}{1+e^{-s_{uv}}}
$$
真实标签采用0-1标签,1表示两节点间存在链接,没有记录的链接中取一部分标签0。
+ 损失函数采用二元交叉熵:$\ell_{uv} = -y_{uv} \log p_{uv} - (1 - y_{uv}) \log(1 - p_{uv})$
### 图级预测
图级预测的关键是将节点汇总成一个聚合表示,如:
$$
\boldsymbol{h}_G^{\text{sum}}=\sum_{v\in V}\boldsymbol{h}_v,\quad \boldsymbol{h}_G^{\text{mean}}=\frac{1}{|V|}\sum_{v\in V}\boldsymbol{h}_v
$$
具体聚合指标与损失函数需要根据实际预测目标进行选择。
## GNN的局限性
最后我们讨论GNN模型的两个局限性,这也是目前研究的发展方向:
+ 关于节点间的连接,虽然相邻的节点往往在某些方面相似(称为同配性),但某些场景下相邻节点可能会有完全不同的特征(如争议网络中支持者与反对者的连接),此时直接进行邻居聚合会导致信息的中和丢失。
+ 另一方面,GNN并不是层数越多越好,因为随着聚合次数增加,每个节点的最终表示会趋于相同,即“过平滑”问题。