许多系统，如社交网络、分子、组织、引用、物理模型、交易等，可以很自然地表示为图。那么，我们如何在这些系统中进行推理和预测呢？

我们知道，神经网络在各种学习任务中显示出巨大的预测能力。然而，神经网络传统上一直用于对规则结构的输入（例如文本、图像和视频）进行操作，这使得神经网络无法直接处理图结构的数据。

1图计算的挑战

+1、缺乏一致的结构

图是极其灵活的数据结构以及数学模型，这同时也意味着它们缺乏超越具体实例的一致结构。例如，考虑预测给定化学分子是否有毒的任务：

这可能要涉及到如下一些情况，

分子可能有不同数量的原子。
分子中的原子可能是不同类型的。
这些原子中的每一个都可能有不同数量的链接。
这些链接可以有不同的强度。

以可计算的格式表示图并非易事，最终选择的表示通常在很大程度上取决于实际问题。

+2、节点顺序等变性

图通常在节点之间没有固有的编号或者排序。这点与图像不同，图像中每个像素都由其在图像中的绝对位置唯一确定！

将图表示为一个向量需要我们确定节点上的顺序。但是当节点没有固有顺序时我们该怎么办？比如下图，我们可以拿两种不同方式标记的同一张图，其中字母指示节点的顺序。

我们自然要求算法不依赖于节点的顺序。如果我们以某种方式置换节点，则由我们的算法计算的节点的结果表示也应该以相同的方式置换。

2图上的具体任务

有许多有用的问题可以通过图来表述，

节点分类：对单个节点进行分类。
图分类：对整个图进行分类。
节点聚类：根据连通性将节点分组。
链接预测：预测丢失的链接。
影响最大化：识别有影响的节点。

许多这些问题往往有赖于一个先导任务，那就是节点表示学习：将单个节点映射到固定大小的实值向量，可以称为表示或者嵌入。

不同的 GNN 变体往往以不同方式来计算这些节点的表示。然而，一般来说，GNN 以迭代的方式计算节点的表示。我们将使用符号来表示第次迭代后节点的表示。迭代一次相当于标准神经网络中的一层。

我们将图定义为一组节点，以及将它们连接起来的一组边。节点可以具有单独的特征作为输入的一部分：我们将用表示节点的单独特征。例如，彩色图像中像素的节点特征将是该像素的红色、绿色和蓝色通道 (RGB) 值。

为了便于说明，我们假设是无向的，并且所有节点都具有相同类型。

3将卷积扩展到图

卷积神经网络被认为在从图像中提取特征方面非常强大。然而，图像本身可以被视为具有非常规则的网格状结构的图形，其中单个像素是节点，每个像素的 RGB 通道值作为节点特征。

那么，一个自然的想法是考虑将卷积推广到任意图上。然而，回想一下上面列出的挑战：

普通卷积不是节点顺序不变的，因为它们取决于像素的绝对位置。
图上邻域结构因节点而异，如何统一将网格上的卷积推广到一般图上的卷积。

可以执行某种填充和排序来确保跨节点的邻域结构的一致性。这已经取得了一些成功，但我们将在这里看到的技术更加通用和强大。

CNN 中的卷积是为了提取局部特征，因此 fliter 往往只涉及局部区域中的数据，比如上图中在中心像素处参与卷积的相邻点以灰色显示。

+GNN 中的局部卷积

GNN 也自然要求可以执行类似于 CNN 的局部卷积。

首先，介绍在节点邻域上构建多项式滤波器的想法，就像 CNN 计算相邻像素上的局部滤波器一样。然后，将介绍新的方法以更强大的机制来扩展这个想法。最后，我们将讨论可以使用全局图级信息来计算节点表示的方法。

4图上的多项式滤波器

+图拉普拉斯算子

给定一个图，我们不妨固定上的个节点的顺序。我们用表示的邻接矩阵，我们可以构造的度矩阵，其对角线上的元素为，

D_{vv}=\sum_{u} A_{v u}

其中，表示矩阵中对应的行和对应的列中的元素。图拉普拉斯算子定义为，是一个对称矩阵，也可以直接将它叫作拉普拉斯矩阵。

图拉普拉斯算子这个名字是从微积分中的拉普拉斯算子得来的，可以看作后者的离散版本。

尽管它编码的信息与邻接矩阵完全相同。当给定矩阵或中的一个，则可以构造另一个。图拉普拉斯算子有很多有趣的性质。图拉普拉斯算子出现在许多涉及图的数学问题中：随机游走、谱聚类和扩散等。

+例子

我们来一个有个节点的图，

它的邻接矩阵、度矩阵和拉普拉斯矩阵分别为，

\begin{array}{cccccc} \left[\begin{array}{llllll} 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{array}\right]\\[1em] \left[\begin{array}{cccccccc} 2 & 0 & 0 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 & 0 & 0 \\ 0 & 0 & 2 & 0 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right] \\[1em] \left[\begin{array}{rrrrrr} 2 & -1 & 0 & 0 & -1 & 0 \\ -1 & 3 & -1 & 0 & -1 & 0 \\ 0 & -1 & 2 & -1 & 0 & 0 \\ 0 & 0 & -1 & 3 & -1 & -1 \\ -1 & -1 & 0 & -1 & 3 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 \end{array}\right] \end{array}

+拉普拉斯算子多项式

现在我们已经了解了拉普拉斯图是什么，我们可以构建以下形式的多项式：

\begin{aligned} p_{w}(L)&=w_{0} I_{n}+w_{1} L+w_{2} L^{2}+\ldots+w_{d} L^{d}\\[0.66em]&=\sum_{i=0}^{d} w_{i} L^{i} \end{aligned}

这种形式的每个多项式可以由其系数向量表示。请注意，对于每个来说，都是一个矩阵。

这些多项式相当于 CNN 中的 filter，而系数则是 filter 的权重。

为了便于说明，这里重点关注节点具有一维特征的情况：的特征只是一个实数。而这里的想法可以直接推广到每个都是高维向量时的情况。

使用先前选择的节点排序，我们可以堆叠所有节点特征以获得向量。

固定节点顺序（图中由字母表示），并将所有节点特征汇聚到单个向量中。

一旦我们构建了特征向量，可以将其与多项式滤波器的卷积定义为：

x^{\prime}=p_{w}(L) x

要了解系数是如何影响卷积的，可以考虑最简单的多项式，即当以及其它系数都为时，就是。

x^{\prime}=p_{w}(L) x=\sum_{i=0}^{d} w_{i} L^{i} x=w_{0} I_{n} x=x

接着考虑以及其他系数都为的情况。此时，就是，于是有

\begin{aligned} x_{v}^{\prime}=(L x)_{v} &=L_{v} x \\[0.8em] &=\sum_{u \in G} L_{v u} x_{u} \\[0.758em] &=\sum_{u \in G}\left(D_{v u}-A_{v u}\right) x_{u} \\[0.758em] &=D_{v} x_{v}-\sum_{u \in \mathcal{N}(v)} x_{u} \end{aligned}

我们看到每个节点的特征与其 1 阶邻域点的特征以一致方式相结合。其实与图像的拉普拉斯滤波是一样的。当是图像时，正是将拉普拉斯滤波器应用于的结果。

此时，我们自然要问：这个多项式的次数是如何决定或者影响卷积的行为呢？事实上，不难证明如下性质

\operatorname{dist}_{G}(v, u)>i \quad \Longrightarrow \quad L_{v u}^{i}=0

这意思是指当两个节点之间的距离超过时，这两个节点间即使用作用次也互不影响。

更具体地说，当我们将与次多项式滤波器进行卷积以获得时：

\begin{aligned} x_{v}^{\prime}=\left(p_{w}(L) x\right)_{v} &=\left(p_{w}(L)\right)_{v} x \\[0.6em] &=\sum_{i=0}^{d} w_{i} L_{v}^{i} x \\ &=\sum_{i=0}^{d} w_{i} \sum_{u \in G} L_{v u}^{i} x_{u} \\ &=\sum_{i=0}^{d} w_{i} \sum_{u \in G \atop dist_{G\;}(v, u) \leq i} L_{v u}^{i} x_{u} \end{aligned}

实际上，节点处的卷积仅发生在距离不超过的节点上。因此，这些多项式滤波器是局部的，局部范围完全可以由控制。

+ChebNet

ChebNet 通过以下形式的多项式滤波器来改进多项式滤波器：

p_{w}(L)=\sum_{i=1}^{d} w_{i} T_{i}(\tilde{L})

其中是第一类次切比雪夫（Chebyshev）多项式，是使用的最大特征值定义的归一化拉普拉斯算子：

\tilde{L}=\frac{2 L}{\lambda_{\max }(L)}-I_{n}

这样做背后的动机是什么呢？

实际上是半正定的：的所有特征值都不小于 0 。如果是，则的幂矩阵的元素大小会迅速增大，俗称元素爆炸。
而上面的相当于是的值缩小版本，特征值保证在范围内，这可以防止的幂矩阵的元素爆炸。实际上，在使用未归一化的 Laplacian 时往往需要限制高次项的系数，但在选择归一化的 Laplacian 时允许更大的值。
切比雪夫多项式具有某些有趣的特性，可以使插值在数值上更加稳定。

本文主要针对图上卷积的难点寻找解决方案的总体思路，因此先不对拉普拉斯算子作过多的解读。

+切比雪夫多项式

第一类切比雪夫多项式可以递归定义为，

\begin{aligned} T_{0}(x) &=1 \\[0.6em] T_{1}(x) &=x \\[0.6em] T_{n+1}(x) &=2 x T_{n}(x)-T_{n-1}(x) \end{aligned}

+节点顺序等变性

我们在这里考虑的多项式滤波器实际上要求不依赖于节点的顺序。当多项式的次数为时，这一点特别容易看出：其中每个节点的特征与其相邻点特征的总和聚合。显然，这个局部总和不取决于相邻点的顺序。

更高次多项式也有类似结论，即矩阵的幂中的元素与节点的顺序等变。

关于这点，我们来证明一下。首先，假定图上个节点按某个顺序编号。任何其他节点顺序都可以被认为是这个原始节点顺序的重新排列。我们可以用置换矩阵来表示某个置换，它是一个元素为的正交矩阵：

P P^{\top}=P^{\top} P=I_{n}

然后，我们称算法为节点顺序等变的，当且仅当对于所有排列，均有

f(P x)=P f(x)

成立。

当使用置换改变节点顺序后，下面左边的向量或矩阵也将按以下方式变换，

\begin{aligned} x & \longrightarrow P x \\ L & \longrightarrow P L P^{\top} \\ L^{i} & \longrightarrow P L^{i} P^{\top} \end{aligned}

其中，第二行左右两个矩阵开弓，左边的是置换的行，右边的是置换列。这正是矩阵乘法中所谓的左行右列。

同时，这也说明原来顺序的节点对应的拉普拉斯矩阵与置换顺序以后的节点对应的拉普拉斯矩阵是合同的，也就是

是对称矩阵，其表示的二次型为；
令，得；
将上式代入二次型，得。

我们再回到滤波器关于节点顺序等变性的证明上，代入多项式滤波器，得

\begin{aligned} f(P x) &=\sum_{i=0}^{d} w_{i}\left(P L^{i} P^{\top}\right)(P x) \\ &=P \sum_{i=0}^{d} w_{i} L^{i} x \\[0.6em] &=P f(x) \end{aligned}

+表示/嵌入计算

我们现在描述如何通过将 ChebNet（或任何多项式滤波器）层与非线性层一个接一个地堆叠起来构建图神经网络，就像标准的 CNN 那样。

特别是，如果我们有个不同的多项式滤波器层，其中第个层有自己的可学习权重，我们将执行以下计算：

；根据参数计算的多项式，得矩阵。
；乘以：一个标准的矩阵向量运算。
；使用非线性函数计算，得新特征。

请注意，这些网络在不同节点上重用相同的滤波器权重，完全模仿了卷积神经网络 (CNN) 中的权重共享机制。

5图神经网络原型

ChebNet 可以认为是在图上学习局部滤波器的一个突破，它启发了大家从不同的角度来思考图卷积。

我们回到多项式核对进行卷积的结果，这里关注特定的顶点，得

\begin{aligned} (L x)_{v} &=L_{v} x \\[0.8em] &=\sum_{u \in G} L_{v u} x_{u} \\[0.758em] &=\sum_{u \in G}\left(D_{v u}-A_{v u}\right) x_{u} \\[0.758em] &=D_{v} x_{v}-\sum_{u \in \mathcal{N}(v)} x_{u} \end{aligned}

正如我们之前提到的，这是一个邻域局部卷积。

但更重要的是，我们可以将这种卷积看作是由两个步骤生成的，

聚合邻域节点的特征。
再结合节点自身特征作差。

实际上，改写一下上面的最后一步，得

\begin{aligned} &D_{v} x_{v}-\sum_{u \in \mathcal{N}(v)} x_{u}\\[0.758em] = &\sum_{u \in \mathcal{N}(v)} (x_{v}- x_{u}) \end{aligned}

因此，拉普拉斯算子是在图上计算每个节点处的一阶差分，如果再将作用到整个图的差分结果上，将得到节点处差分的差分，也就是说次拉普拉斯算子是计算阶差分。

通过确保聚合是节点顺序等变的，可以得到整个卷积滤波变为节点顺序等变。

这些卷积可以被认为是相邻节点之间的消息传递：在每一步之后，每个节点都会从其相邻点那里接收一些信息。

通过迭代地重复邻域局部卷积次（即重复消息传递次），卷积的感受野有效地包括了邻域之内的所有节点。

6小结

通过图上拉普拉斯算子来计算节点间的信息差分；结合拉普拉斯算子的多项式滤波器处理图上邻域局部性聚合以及权重共享问题，模拟了图像数据上的卷积运算。
通过置换矩阵变换节点顺序，得到的拉普拉斯矩阵与原顺序节点的拉普拉斯矩阵是合同的，从而保证了节点顺序等变性。
消息传递构成了当今许多 GNN 架构的支柱，我们将在后面再逐一深入描述经典的图卷积方案，如图卷积网络（GCN）、图注意力网络（GAT）、图采样和聚合（GraphSAGE），以及图同构网络（GIN）等。

参考文献

[1]

https://distill.pub/2021/understanding-gnns/

相关阅读

GNN 入门系列: 直观理解和应用介绍

GNN 入门系列: 图卷积网络原来是这么回事

GNN 入门系列: 矩阵的谱与图卷积网络是这样结合的

图（Graph）上作卷积到底有哪些痛点？

1图计算的挑战

+1、缺乏一致的结构

+2、节点顺序等变性

2图上的具体任务

3将卷积扩展到图

+GNN 中的局部卷积

4图上的多项式滤波器

+图拉普拉斯算子

+例子

+拉普拉斯算子多项式

+ChebNet

+切比雪夫多项式

+节点顺序等变性

+表示/嵌入计算

5图神经网络原型

6小结

参考文献

GNN 入门系列: 直观理解和应用介绍

GNN 入门系列: 图卷积网络原来是这么回事

GNN 入门系列: 矩阵的谱与图卷积网络是这样结合的

矩阵特征值与机器学习之谱聚类

图网络（GNN）前传 : 图与矩阵的兄弟情结

图（Graph）上作卷积到底有哪些痛点？

1图计算的挑战

+1、缺乏一致的结构

+2、节点顺序等变性

2图上的具体任务

3将卷积扩展到图

+GNN 中的局部卷积

4图上的多项式滤波器

+图拉普拉斯算子

+例子

+拉普拉斯算子多项式

+ChebNet

+切比雪夫多项式

+节点顺序等变性

+表示/嵌入计算

5图神经网络原型

6小结

参考文献

GNN 入门系列: 直观理解和应用介绍

GNN 入门系列: 图卷积网络原来是这么回事

GNN 入门系列: 矩阵的谱与图卷积网络是这样结合的

矩阵特征值与机器学习 之 谱聚类

图网络（GNN）前传 : 图与矩阵的兄弟情结

矩阵特征值与机器学习之谱聚类