一文详解图卷积神经网络

本文是文章 A Gentle Introduction to Graph Neural Networks 的个人笔记，强烈建议大家去体验原文的交互式阅读，以及李沐老师的讲解。我的宗旨是尽量使用浅显易懂的白话，而不是晦涩的术语，把概念和理论讲清楚。开始吧！

作为一枚资 (ruo) 深 (ji) NLPer，我常见的神经网络输入是一段文本序列并输出预测，但如果输入是一个图、要怎么传递参数并做出预测呢？

图的表示

这个问题可以确切地说成：我们该如何表示图，来放到神经网络中去？

可以看到图最多有四种信息，节点 (nodes)、边 (edges)、全局上下文 (global-context) 和连通性 (connectivity)。简单地，我们可以用索引 \(i\) 来表示不同的节点，用特征向量/嵌入来表示节点和边的属性，因此所有节点可以表示为一个 \([n_{nodes},node_{dim}]\) 大小的张量。

但是，图的连通性要怎么表示？

我们很容易想到邻接矩阵，但当节点数量 \(n\) 达到数百万时（注意此时矩阵元素达到\(n^2\)），矩阵会非常稀疏、空间占用效率很低。并且，对于同样的连通性，只要稍稍改变节点的排列顺序，邻接矩阵就会发生改变！这意味着这些矩阵并非是置换不变的。

因此，一种更优雅且内存高效的稀疏矩阵表示方法是邻接表，用元组\((i,j)\)来表示边 \(e_k\) 连接的节点 \(n_i\) 和 \(n_j\)。邻接表的条目数\(==\)边的数量，这避免了对图的未连接部分进行计算和存储。

现在，我们就可以用置换不变的格式来优雅地描述一个图了。

图预测任务

接下来的问题是：如何用图神经网络（GNN）来解决图预测任务（比如节点或边的分类）？

图神经网络采用“图入、图出”的架构，这意味着模型将为节点 (V)、边 (E) 和全局上下文 (U) 学习新的嵌入，而不改变图的连通性（邻接表）、节点和边的数量。

也就是说，我们对每个节点的特征向量应用任何一个可微分模型（比如最简单的多层感知器MLP），来学习一个新的节点向量；对每条边也是如此，学习一个新的边的嵌入；最后，对全局上下文向量执行同样的操作，为整个图学习一个嵌入。

我们输入一个图，得到这个图新的表示。

把上面这样的单层堆叠在一起，就构成了一个简单的GNN。

如何完成预测？

对于节点分类任务，我们可以简单地对每个节点的嵌入应用线性分类器。

当然，如果没有节点嵌入时（比如节点是用户信息需要保密），我们可以把边的嵌入加起来求和表示节点。这个步骤叫做汇聚，用字母 \(ρ\) 来表示，我们用 \(pE_n→V_n\) 表示从边收集节点的信息。

当然也可以反过来，如果只有节点级别的特征，那就用节点去预测边。

或者，如果只有节点级别的特征，需要为全局属性作二分类，那就把所有可用的节点信息汇聚在一起，这类似于CNN中的全局平均池化层。可以看到信息是如何通过 \(ρ\) 汇聚操作从一个属性传递到另一个属性的。

连起来，下面这张图可以很清晰地看到一个完整的GNN模型怎么做预测任务。

消息传递

除了以上的汇聚操作，我们还可以收集所有相邻节点的嵌入（消息）进行聚合，等等……这些操作统称为消息传递，使得 GNN 层内的节点和边之间可以共享信息。本质上，消息传递和卷积是聚合和处理元素邻居信息以更新元素值的操作。在图中，元素是节点；在图像中，元素是像素。然而，在图中，相邻节点的数量是可变的；但在图像中，每个像素都有一组相邻元素。

通过堆叠消息传递 GNN 层，节点最终可以整合整个图的信息：比如经过三层之后，节点具有关于距离它三步的节点的信息。不过节点和边的组合相对困难，因为两者不一定具有相同的形状，可以学习从边空间到节点空间的线性映射（反之亦然），或者在更新图属性之前将它们拼接起来。

GNN 需要研究的地方就在这里，更新哪些图属性？以什么顺序更新？在边嵌入之前更新节点嵌入，还是反过来？我们可以以“编织”方式进行更新：节点到节点（线性），边到边（线性），节点到边（边层），边到节点（节点层）。

然而，对于图中彼此相距很远的节点，可能永远无法有效进行信息的互相传输。这时我们可以用图的全局表示（U），有时称为主节点或上下文向量。该全局上下文向量已连接到网络中的所有其他节点和边缘，可以充当它们之间的桥梁传递信息，建立整个图的表示形式。

思考

图这种数据结构真的包罗万象，本质上，图像是网格状的图（每个像素点是一个节点）、文本是序列状的图（每个字符是一个节点），还有视频、化学分子、事件、人际交往……图无处不在，因为任何事物都是彼此关联的，这些东西就是节点，这些关系就是边！