图神经网络模型扩展5--3
以图卷积网络为例,在每一层卷积中,我们需要用到两个输入A∈Rn×n 和X∈Rn×d。 很容易想象,当输入的图数据很大时(n 很大),图卷积网络的计算量是很大的,所需要的内存也是很大的。推广到更一般的信息传递网络,在每一层中,需要将信息从中心点传给周围所有的邻居。经过很多层之后,这个信息到达的节点数会呈指数发展,这个现象被称为“邻居爆炸”。因此,当图很大或很稠密时,图神经网络的训练很容易出现内存爆炸或者训练缓慢的现象,这极大地限制了图神经网络的大规模应用。一个可行的解决方案 就是邻接点采样。
1.点采样
Hamilton等人用GraphSAGE模型做了一个探索性的尝试。在第3 章讲过这个模型,它在每一次信息传递的过程中,对每个中心节点随机采样固定数量的邻居节点进行信息聚合。这个措施使得GraphSAGE 的复杂度可以维持在一个固定的开销,与其他消息传递网络相比,更容易扩展到大规模的图上。PinSAGE基于GraphSAGE做了微小的改进,在采样的时候加入了邻居节点重要性的考虑,通过随机游走,被访问越多次的节点,被采样的概率就越大。VR-GCN进一步缩减了邻接点采样的数量,它保存了节点激活的历史记录,并用控制变量法使邻居采样的数量可以减少。
2.层采样
GraphSAGE这种对每个节点采样多层邻居的方式,在图卷积网络层数增多时仍然可能遭遇“邻居爆炸”的问题,因为每个节点、每层都采样了固定数量的点。不同于GraphSAGE的节点采样,Chen 等人则提出了一种新的层采样方法FastGCN。首先,我们介绍为什么采样是可行的。回到图卷积网络的公式:
我们把它写成信息传递的形式:
为了简洁,我们先忽略非线性的部分,并且不失一般性地将这个离散形式改写成概率积分的形式:
把u看成一个随机变量,而P(u)为它的分布概率。n 为图中的节点数,A^(v,u) 表示矩阵A中对应节点v和u的值。假设图卷积网络中的每一层相互独立,并且每个节点是独立同分布的,采用蒙特卡罗采样法,则可以采样t₁个独立同分布的样本节点
来近似这个积分,这样每层节点的更新最终近似为:
在实际应用中,我们把图中的节点分批,对每一批内的节点,采样同样的邻居, 这样可以将它重新写回矩阵形式:
需要注意的是,FastGCN的采样不是对单一点进行的,而是在整个batch 内, 或者对整个层采样同样的邻居节点,这样随着图卷积网络层数的增加,采样点的数量只是线性增加的,这就进一步减少了采样所需的邻接点数量。随后,我们可以对采样加上权重,来减少采样方差,提高效率。很容易想到,在一个图中,每个节点的重要性是不一样的。直观地讲,如果一个节点的度很大,即它连着很多节点,那么它的重要性和对其他节点的影响力可能会更大(以社交网络为例,一个有着众多社交连接的大V 节点显然是更具影响力的)。 因此,重新设计节点的采样概率:
并用它们进行带权重的采样:
与GraphSAGE一 样 ,FastGCN 在实验中通常也只用两层图卷积网络,在针对大图的实验(比如reddit) 中,它们都比传统的图卷积网络快一到两个数量级,同时保持了几乎相同的准确度。
FastGCN 有一个很强的独立性假设,导致相邻的两个图卷积网络层的采样是相互独立的,这会降低训练的效率,因为可能不同图卷积网络层独立采样出的节点之间,在信息传递时的路径是断掉的。ASGCN改进了FastGCN的层间采样依赖关系,并提出了一个新的、可学习的网络,直接优化重要性采样的方差,因此表现也更好。
3.图采样
尽管点采样和层采样在大规模图学习上取得了不错的进展,但是它们在图更大及图神经网络更深时还是会遇到不少的困难,如GraphSAGE 的邻接点爆炸导致内存消耗过多,VR-GCN 需要额外存储节点的历史激活记录,FastGCN的层间依赖不足导致效果稍差,ASGCN需要在采样时额外注意层间依赖关系。 最近,有研究者提出了一些基于子图采样的方法,这类方法的思想是通过限制子图的大小来解决邻居爆炸的问题。由于它们在采样到的子图上进行图神经网络的训练,这些方法也就不存在采样点之间缺失层间依赖的问题。
Cluster-GCN先采用图聚类算法把图分割成一个个小块,每次训练时随机选取一些小块组成子图,然后在这个子图上进行完整的图卷积网络计算,并直接得到损失函数。GraphSAINT也是先对原图进行采样,它使用了另外一 些子图采样的方法(如随机选取节点、随机选取边,随机游走等方法),然后在采样的子图上进行图卷积网络的计算。不同于Cluster-GCN,GraphSAINT与 FastGCN 和ASGCN 类似,还考虑了采样偏差问题,因此采用了重要性采样的方法来降低采样方差。具体来说,在GraphSAINT 中,在子图上运行的图卷积 网络在信息传递过程中,边的权重根据采样概率被重新归一化了:
其中,Gs为采样的子图,Lv为节点v上的预测损失,λv为节点v 对应的采样归一化系数,它与节点v 被采样到的概率成正比: λv=|V|*pv。
在Cluster-GCN中怎么避免邻接点数量爆炸问题呢?可以看出, 由于分割成了不同的类,消息的传递在Cluster-GCN中受到了很大的限制,也就减少了邻接点数量爆炸的问题。GraphSAINT的图采样过程,先通过一些随机方法采样到子图,然后在子图上运行修改了权重的图卷积络。 图采样相比点采样和层采样要更加灵活,可以应用不同的图采样方法和图神经网络模型,并且在运行效率和准确度上都取得了很好的效果。
4.不规则图的深度学习模型
早期,大部分图神经网络关注的都是一般的图结构,甚至很多模型中默认图中的边都是没有权重的。工业界真正关心的是有着多种类型节点和边的不规 则图(异构图)。例如,推荐系统中需要用户和商品两种节点;在药物反应预测中,我们需要在药物相互作用图中的边上处理不同的反应类型,这些任务也引发了对不规则图上图神经网络的很多研究。本节简要介绍两种不同思路的异构图学习方法。
首先,回顾前面学到的图神经网络的一种表示——消息传递网络,它的信息传递过程可以写成如下形式:
在信息收集的过程中,我们已经加入了边的信息evw, 所以消息传递网络框架是可以用来进行异构图的学习的。那么具体怎么实现呢? 关系图卷积网络给出了一种思路:
可以看出,上式和图卷积网络的公式非常相似,唯一的区别是根据边的类型r不同,选择了不同的参数W。
另一种异构图神经网络的思路则来源于图注意力网络。在传统的图注意力网络中,没有考虑到边的信息,但这并不是一个很难解决的问题。我们只需要将图注意力网络的公式稍加变换,加入边向量就可以了。假设节点i 和j 的边具有类型r, 则节点之间的注意力计算公式变为:
可以看出,上式和图注意力网络的唯一不同就是加入了边向量Wrer。
小结:
本章介绍了图神经网络的一些扩展任务和前沿课题,包括怎么训练更深的图卷积网络,怎么利用池化层次化地表示图,怎么在缺少标签的情况下无监督地训练图神经网络,怎么在图很大的时候进行快速的采样学习,以及怎么在不 规则的异构图上构建图神经网络。这些课题覆盖了大部分图表示学习的研究方向。有些方向由于种种原因没有进行介绍,如图上的对抗性攻击与防御、动态图的表示学习、图神经网络的理论分析(表达力、不变性与同变性等)、图神经网络的可解释性等。