图神经网络模型扩展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。

小结：

        本章介绍了图神经网络的一些扩展任务和前沿课题，包括怎么训练更深的图卷积网络，怎么利用池化层次化地表示图，怎么在缺少标签的情况下无监督地训练图神经网络，怎么在图很大的时候进行快速的采样学习，以及怎么在不 规则的异构图上构建图神经网络。这些课题覆盖了大部分图表示学习的研究方向。有些方向由于种种原因没有进行介绍，如图上的对抗性攻击与防御、动态图的表示学习、图神经网络的理论分析(表达力、不变性与同变性等)、图神经网络的可解释性等。