图神经网络（Graph Neural Networks）

参考资料：

A Gentle Introduction to Graph Neural Networks (distill.pub)

图论基础

基本概念

二维坐标中，两点可以连成线，多个点连成的线就构成了图。我们通常用$G=(V,E)$来表示图，其中$V$表示节点的集合、$E$表示边的集合。对于两个相邻节点$u,v$,使用$e=(u,v)$表示这两个节点之间的边。两个节点之间边既可能是有向，也可能无向。若有向，则称之有向图(Directed Graph), 反之，称之为无向图(Undirected Graph)。

度

无向图中有几条边连接该节点，该节点就有几度。

在有向图中，每个节点有出度和入度。

出度：从该节点出发的边的个数。

入度：指向该节点边的个数。

连通性

连通图

在无向图中，任何两个节点都是可以到达的，我们称之为连通图

如果有节点不能到达其他节点，则为非连通图，如图：

如图所示，节点1并不能到达节点4

强连通图

在有向图中，任何两个节点是可以相互到达的，我们称之为 强连通图。强连通图如下图所示

连通分量

在无向图中的极大连通子图称之为该图的一个连通分量。

该无向图中 节点1、节点2、节点5 构成的子图就是 该无向图中的一个连通分量，该子图所有节点都是相互可达到的。

同理，节点3、节点4、节点6 构成的子图 也是该无向图中的一个连通分量。

那么无向图中 节点3 、节点4 构成的子图 是该无向图的联通分量吗？

不是！

因为必须是极大联通子图才能是连通分量，所以 必须是节点3、节点4、节点6 构成的子图才是连通分量。

在图论中，连通分量是一个很重要的概念，例如岛屿问题（后面章节会有专门讲解）其实就是求连通分量。

强连通分量

在有向图中极大强连通子图称之为该图的强连通分量。

如图：

节点1、节点2、节点3、节点4、节点5 构成的子图是强连通分量，因为这是强连通图，也是极大图。

节点6、节点7、节点8 构成的子图 不是强连通分量，因为这不是强连通图，节点8 不能达到节点6。

节点1、节点2、节点5 构成的子图 也不是 强连通分量，因为这不是极大图。

图的表示

邻接矩阵 使用 二维数组来表示图结构。 邻接矩阵是从节点的角度来表示图，有多少节点就申请多大的二维数组。

例如：

有向图：grid[1][2]= 5，表示 节点 1 连接 节点2 为有向图，节点1 指向 节点2，边的权值为5。

同构图与异构图

• 同构图：在图里面，节点的类型和边的类型只有一种的图
• 异构图：在图里面，节点的类型+边的类型>2的一种图

图神经网络

背景

传统的深度学习方法被应用在提取欧氏空间数据的特征方面取得了巨大的成功，但许多实际应用场景中的数据是从非欧式空间生成的，传统的深度学习方法在处理非欧式空间数据上的表现却仍难以使人满意。欧式空间就是中学学的平面几何、立体几何，例如$x_1、x_2$两点间的距离。那么非欧式空间是如何定义的呢？我们来看这样一个例子

想象你是一只蚂蚁，生活在地球这个大球面上。对你这只蚂蚁来说，地球表面就是一个非欧几里得空间的例子。在你日常“行走”中，你可能会发现“直线”行走最终能回到起点，这是因为在球面上最短的路径实际上是大圆路径。此外，如果你在地球的一点画一个三角形，其内角和会超过180度，这违反了欧氏几何中平面三角形内角和为180度的规则。这些现象对蚂蚁而言是不易察觉的，因为它们的尺度太小，无法感知到空间的这种全局弯曲。这个例子中的空间就是非欧氏空间中，直观的“直觉”如“直线最短”和“三角形内角和定理”都不再适用了。

图就是一种非欧氏空间，图是不规则的，每个图都有一个大小可变的无序节点，图中的每个节点都有不同数量的相邻节点，导致一些重要的操作（例如卷积在图像（Image）上很容易计算，但不再适合直接用于图。此外，现有深度学习算法的一个核心假设是数据样本之间彼此独立。然而，对于图来说，情况并非如此，图中的每个数据样本（节点）都会有边与图中其他实数据样本（节点）相关，这些信息可用于捕获实例之间的相互依赖关系。

与传统的CNN相比，右侧GCN的边和节点是可变化的，这就需要你自适应产生一个专门的卷积核去做局部的聚合操作。在GCN（图卷积神经网络）中需要设计专门的数据结构（如何在图上定义卷积算子），以针对特殊的非欧空间。下图可以看到图神经网络的学习与传统的深度学习存在较大的差异点。

图神经网络的任务

• Node-level的任务

节点级任务涉及预测图形中每个节点的属性，如下图所示，图中的节点代表一个俱乐部里的成员，边代表这些成员在俱乐部的社交联系或互动

有一天俱乐部内部发生了冲突，导致了分裂。这场冲突主要是教练 老Hi 同志和管理员 John 同志之间的矛盾，发生冲突后，俱乐部分裂成了两个派系，成员们分别选择效忠于老Hi 或者John。如果你是俱乐部的一员，想在这场冲突里占好队，应该选择哪一方呢？

这是一个经典的二分类任务，任务目标是预测每个成员在冲突后会加入哪个派系，我们不考虑其他情况，唯一的特征就是图的结构本身，即成员之间的连接。那么节点与Hi 或 John 之间的距离就是预测节点标签的关键因素。距离 Mr. Hi 较近的节点更有可能效忠于他，反之亦然。我们根据预测的标签为节点着色，如下图所示

• Graph-level的任务

在图级别，我们的目标是预测整个图形的属性，也就是区分不同的图形状。此时，任务不依赖于某个节点或某条边的属性，而是，需要考虑整个图的信息。例如，对于以图表表示的分子，我们可能想要预测分子的气味，或者它是否会与与疾病相关的受体结合。

• Edge-level的任务

剩余的一个任务是图的边预测问题，它涉及边预测以及图中节点之间的关系和连接，比如经典的深度学习模型可以在图像中识别物体，而在图神经网络中还可以用于预测这些物体之间的关系。例如：给定代表图像中物体的节点，如下图所示，我们希望预测哪些节点之间存在边，或者这些边的具体值是什么。

如果想找到实体之间的连接，我们完全可以假设图是完全连接的，即每个节点都与其他所有节点有潜在的连接。然后，通过预测每条边的存在概率或边的权重，我们可以决定保留哪些边，从而构建一个稀疏图，如下图所示。

卷积图神经网络

卷积

这里不去深入探讨卷积的概念，仅仅用一个例子来简单说明卷积

小例子：

假设你在山谷中大喊一声，声音会在山谷中反射回来，形成回声。这个过程可以用卷积来建模。

假设你的喊声可以用一个简化的信号表示，比如一个脉冲信号$f(t)$：

$f(t)=\{\begin{array}{ll}1& \text{ if }t=0\\ 0& \text{ otherwise }\end{array}$

这表示在时间$t=0$时，你发出了一声短暂的喊声。

山谷的反射特性可以用一个冲激响应函数$h(t)$ 来表示。假设山谷的反射特性是这样的：

$h(t)=\{\begin{array}{ll}1& \text{ if }t=0\\ 0.5& \text{ if }t=1\\ 0.25& \text{ if }t=2\\ 0& \text{ otherwise }\end{array}$

这表示：

• 在时间$t=0$时，声音直接传到你的耳朵。
• 在时间$t=1$时，声音经过一次反射传到你的耳朵，强度减弱了一半。
• 在时间$t=2$时，声音经过两次反射传到你的耳朵，强度减弱了四分之一。

回声的形成可以通过卷积来计算。卷积$(f\ast h)(t)$表示你听到的声音信号：

$$(f\ast h)(t)={\int }_{-\mathrm{\infty }}^{\mathrm{\infty }}f(\tau )h(t-\tau )d\tau$$

在离散情况下，可以简化为：

$$(f\ast h)[n]=\sum _{m=-\mathrm{\infty }}^{\mathrm{\infty }}f[m]h[n-m]$$

具体计算如下：

• 当 $n=0$ 时:

$$(f\ast h)[0]=f[0]h[0]+f[1]h[-1]+f[2]h[-2]+\cdots =1\cdot 1+0\cdot 0.5+0\cdot 0.25+\cdots =1$$

• 当 $n=1$ 时:

$$(f\ast h)[1]=f[0]h[1]+f[1]h[0]+f[2]h[-1]+\cdots =1\cdot 0.5+0\cdot 1+0\cdot 0.5+\cdots =0.5$$

• 当 $n=2$ 时:

$$(f\ast h)[2]=f[0]h[2]+f[1]h[1]+f[2]h[0]+\cdots =1\cdot 0.25+0\cdot 0.5+0\cdot 1+\cdots =0.25$$

• 当 $n>2$ 时:

$$(f\ast h)[n]=0$$

将所有计算结果汇总，得到卷积结果：

$(f\ast h)[n]=[1,0.5,0.25,0,0,\dots ]$

• 在时间$t=0$时，你直接听到自己的喊声，强度为1。
• 在时间$t=1$时，你听到第一次反射的回声，强度为0.5。
• 在时间$t=2$时，你听到第二次反射的回声，强度为0.25。
• 之后的时间，没有更多的回声。

你在山谷中大喊一声，声音经过多次反射后逐渐减弱的过程。每一步的反射都可以看作是原始信号 ( f(t) ) 与反射特性 ( h(t) ) 的卷积，最终形成了你听到的回声信号。

谱方法

首先给出一个图$G=(V,E,W)$的定义：

• 其中$V$表示节点集合， $E$表示边集合， $W\in R^{n\times n}$ 则是权重邻接矩阵，它描述了节点之间的连接强度。

• 每个节点都关联着 $d$个特征，并且有一个特征矩阵$X\in R^{n\times d}$，矩阵的每一列就对应于一个特定的特征（信号），每一行则对应于一个特定的节点。

图拉普拉斯矩阵（Graph Laplacian）

它是图的一种重要属性，可以通过以下方式计算：$L=D-W$ 其中 $D$ 是一个对角矩阵，它的对角线上元素是节点的度（即与节点相连的边的数量）。$W$是上文所述的权重邻接矩阵。图拉普拉斯矩阵描述了图的结构信息，反映了节点间的相对位置和连接强度。

归一化图拉普拉斯矩阵的定义：

$$L=I-D^{-\frac{1}{2}}W{D}^{-\frac{1}{2}}$$

其中 ( I ) 是单位矩阵，$D^{-\frac{1}{2}}$表示$D$的平方根倒数。

图傅立叶变换（Graph Fourier Transform

• 傅立叶基（Fourier basis of graph）

傅立叶基指的是图拉普拉斯矩阵$L$的完整正交基，也就是所有非负特征值对应的特征向量。这些特征向量构成一个正交矩阵 $U$，并且按照特征值的大小排列。换句话说，$U$中的每一列都是图拉普拉斯矩阵的一个特征向量，这些特征向量组成了图的傅立叶基。特征值 ${\lambda }_i$ 对应于每个特征向量$u_i$。

• 图拉普拉斯矩阵的对角化

图拉普拉斯矩阵$L$ 可以通过对角化来表示为： $L=U\mathrm{\Lambda }{U}^T$ 其中$U$是包含所有特征向量的正交矩阵，$\mathrm{\Lambda }$是一个对角矩阵，对角线上的元素是相应的特征值。这个方程说明图拉普拉斯矩阵可以被分解为其特征向量和特征值的组合。

• 图傅立叶变换

图傅立叶变换是对图上的信号进行变换的过程，它可以将信号从原空间转换到特征空间。对于一个信号 $x\in {\mathbb{R}}^n$，它的图傅立叶变换定义为： $\hat{x}=U^{T}x$ 这里 $\hat{x}$是信号 $x$在特征空间的表示，它是由特征向量$U$将信号投影到特征空间的结果。

• 图傅立叶逆变换

图傅立叶逆变换是将信号从特征空间转换回原空间的过程。对于一个在特征空间的信号$\hat{x}$，它的图傅立叶逆变换定义为： $x=U\hat{x}$

图卷积方法

卷积定理

两个信号的卷积在傅立叶变换下的结果是这两个信号的傅立叶变换的点积（point-wise product）。也就是说，在频域中，卷积操作变成了点积操作。在经典傅立叶变换中，这个定理表述为：

$$\text{FT}(f\ast g)=\text{FT}(f)\cdot \text{FT}(g)$$

这里的$f\ast g$表示两个信号 $f$ 和$g$的卷积，$ \text{FT} $ 表示傅立叶变换，$\cdot$ 表示点积。

图卷积定理

在图傅立叶变换中，卷积定理也成立。给定一个输入信号 $x$ 和一个滤波器（或核）信号$y$，图卷积 $x{\ast }_{G}y$可以表示为：

$$x{\ast }_{G}y=U((U^{T}x)\odot (U^{T}y))$$

这里，$ \odot $ 表示元素级乘法（Hadamard product），$U$ 是图的特征向量矩阵，$U^T$ 是其转置，$x$和 $y$分别是输入信号和滤波器信号的图傅立叶变换。它是图卷积的一个基本表达式。

有了上面这个基本表达式，为了将图卷积方法表述的更为清楚，我们对公式9中的变量重新定义一下有：

${\mathit{U}}^{T}y={[{\theta }_0,\cdots ,{\theta }_{n-1}]}^T$ and ${\mathit{g}}_{\mathit{\theta }}=\mathrm{diag}\left([{\theta }_0,\cdots ,{\mathit{\theta }}_{n-1}]\right)$

$$\mathit{x}{\ast }_G\mathit{y}=\mathit{U}{\mathit{g}}_{\theta }{\mathit{U}}^T\mathit{x}$$

则图卷积的过程可以分为三个步骤：

将节点上的信号 $x$ 在图傅立叶变换后得到谱域 $U^{T}x$。

应用滤波器 $g_{\theta }$ 到变换后的信号上，得到 $g_{\theta }{U}^{T}x$。

最后，将结果通过图傅立叶逆变换转换回原空间，得到 $U{g}_{\theta }{U}^{T}x$。

ChebyNet模型

此模型在上述图卷积方法中做出了优化，具体优化如下图所示：

空间方法

引入

我们再来回顾一下卷积神经网络的架构，仔细看看如何能把卷积神经网络的架构方法迁移到图上

Determine neighborhood（确定邻居关系）：在 CNN 中，卷积核滑动并作用于固定大小的窗口（通常为正方形），以捕获局部特征。对于图，我们需要确定每个节点的邻居，并且这些邻居可能不是规则排列的。上图的左边展示了如何选择一个节点的邻居，中间的箭头表示随着层数增加，邻居范围扩大。

Impose an order in neighborhood（在邻居间施加顺序）：在 CNN 中，卷积核按顺序作用于像素。对于图，我们需要找到一种方式来对邻居节点排序。右图显示了一个树状结构，其中节点按照某种顺序排列。

Parameter sharing（参数共享）：在 CNN 中，同一层内的卷积核共享相同的权重。这对于减少参数数量和避免过拟合非常重要。在 GCN 中，我们也需要类似的参数共享机制。

我们根据上文CNN的方法，做如下迁移

Determine Neighborhood（确定邻域）：首先，为每个节点选择一定数量的相邻节点作为其邻域。这可以通过特定的距离度量（poximity metric）来完成，例如：图中节点的最短路径距离作为poximity metric。上图展示了一个例子，红色圆圈代表当前节点，绿色圆圈代表选定的邻域节点。在这个阶段，我们确定了每个节点与其邻域之间的连接。

Impose an Order in Neighborhood（在邻域内施加顺序）：一旦选择了邻域节点，就需要给这些节点排序。这是因为卷积操作通常需要一个固定的顺序。在图中，我们可以看到一个子图，其中节点按照一定的顺序排列。这种顺序也是由上文提到的距离度量决定的。

Parameter Sharing：在图中，我们使用一个树形结构，表示参数共享的概念，所有的邻域节点都共享相同的卷积核。

空间方法下的图卷积神经网络

有了上述一系列的基础和铺垫，我们终于可以开始定义图卷积神经网络的网络架构，定义过程如下：

• 特征变换

将节点特征矩阵 $X$ 与第一层的权重矩阵 $W^{(0)}$ 相乘，进行特征变换：

$$H^{(0)}=X{W}^{(0)}$$

这里， $H^{(0)}$ 是第一层的隐藏特征表示，大小为 $N\times D^{\prime }$ ，其中 $D^{\prime }$ 是第一层的输出特征维度。

• 邻域聚合

将每个节点的特征与其邻居的特征进行聚合。通过归一化邻接矩阵 $\tilde{A}$ 来实现。为了简化计算，我们通常使用归一化后的邻接矩阵 ${\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$ :

$$H^{(1)}={\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(0)}$$

这里， $H^{(1)}$ 是经过邻域聚合后的特征表示。

• 激活函数

为了引入非线性，我们在聚合后的特征上应用ReLU激活函数：

$$H^{(1)}=\mathrm{ReLU}\left({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}{H}^{(0)}\right)$$

• 再次特征变换

将聚合后的特征 $H^{(1)}$ 与第二层的权重矩阵 $W^{(1)}$ 相乘，进行第二次特征变换：

$$H^{(2)}=H^{(1)}{W}^{(1)}$$

这里， $H^{(2)}$ 是第二层的隐藏特征表示，大小为 $N\times D^{\prime \prime }$ ，其中 $D^{\prime \prime }$ 是第二层的输出特征维度。

• 归一化

最后，我们使用softmax函数对输出进行归一化，使其适用于多分类任务:

$$Z=\mathrm{softmax}\left(H^{(2)}\right)$$

将上面的每一步展开，我们终于得到了完整的GCN公式

$$Z=\mathrm{softmax}\left(\mathrm{ReLU}\left({\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}X{W}^{(0)}\right)W^{(1)}\right)$$

为了简化表示，通常写作:

$$Z=\mathrm{softmax}\left(\mathrm{Adj}\left(\mathrm{ReLU}\left(\tilde{A}X{W}^{(0)}\right)\right)W^{(1)}\right)$$

其中， $\mathrm{Adj}$ 表示归一化邻接矩阵的操作，即 ${\tilde{D}}^{-\frac{1}{2}}\tilde{A}{\tilde{D}}^{-\frac{1}{2}}$ 。

图注意力网络(Graph Attention Network)

未完待续....