图神经网络

是什么

图神经网络（graph neural network）是一类为图结构输入设计的人工神经网络^[1]。所谓图结构，指的是由节点以及连接节点的边所组成的数据。2018年的一篇综述把图神经网络描述为通过在节点之间传递消息来刻画图上依赖关系的神经模型^[2]。因此这个词指的是一族架构，而不是某一个固定的模型。

怎么工作

图的节点没有天然的顺序：把节点重新编号，图本身并没有变化。所以图上的架构通常被设计成置换等变（permutation equivariant）的——输入如何重排，输出就按同样的方式重排；而针对整张图的任务则使用置换不变（permutation-invariant）的读出函数（readout function），无论节点顺序如何，输出都相同^[1]。

现代图网络大多采用消息传递（message passing）：每个节点的表示，由它自身的特征和来自邻居的消息的聚合一起更新^[1]。聚合算子（aggregation operator）是置换不变的，通常是求和、求平均或取最大值^[1]。每经过一层，节点就多看到一圈邻居，因此每一层都把节点的感受野（receptive field）扩大一跳^[1]。

一个小例子可以把这件事说清楚。假设有一张图，每个节点是一个人，每条边表示两人是朋友。第一层里，一个节点的向量由它自己的属性，加上它朋友们向量的平均值（也可以换成求和或取最大值）共同决定。第二层把同样的操作作用在刚刚得到的结果上，于是这个节点间接地看到了朋友的朋友。层数堆得足够多，一个节点的表示就可以依赖图上很大的一片区域；最后，读出函数把全部节点向量汇总成一个代表整张图的向量。

从哪来

Scarselli 等人在2009年发表了《The Graph Neural Network Model》，以递归的方式给出了这一模型的表述^[1]。同在2009年，Micheli 提出了图上的卷积构造^[1]。此后这些想法被广泛采用：Kipf 与 Welling 在2017年提出的 GCN 是局部谱滤波器的一阶近似^[1]；Hamilton 等人在2017年提出的 GraphSAGE 为大规模图引入了归纳式表示学习（inductive representation learning）^[1]；Velickovic 等人在2018年提出的 GAT 加入了注意力系数，用来给不同邻居的重要性加权^[1]。

影响

2018年的那篇综述指出，图卷积网络、图注意力网络、图循环网络等变体在许多深度学习任务上表现出了突破性的性能^[2]。该综述提出了图神经网络模型的一般设计流程，系统地对其应用做了分类，并给出了四个留待未来研究解决的问题^[2]。对这样一个架构繁多的领域来说，把应用集中梳理一遍本身就有用：它说明同一套底层机制被用来处理哪些类型的任务。

局限

消息传递并不是万能的。标准消息传递图网络的表达能力不超过 Weisfeiler-Leman 图同构测试^[1]，也就是说，存在它区分不开的图。加深层数也会带来麻烦：过平滑（oversmoothing）会让深度图网络中的节点表示趋于一致，变得难以区分^[1]；过挤压（oversquashing）则把长距离的依赖压缩进固定大小的表示里，形成瓶颈^[1]。