图神经网络（GNN）因其分析图结构数据的能力而收到了不小的关注。

本文将对图神经网络进行简要介绍，不仅包含不同形式的图神经网络及其原理、应用还包含了图论基础，让大家可以轻松理解图及图分析中的问题。

图论基础

首先，我们需要了解什么是图。

图是由顶点（节点）和边组成的数据结构，用于作为数学结构来分析对象与实体之间的成对关系。

通常，图被定义为G=(V, E)，其中V是节点集合，E是节点之间的边。

一个简单的图表

图常用邻接矩阵A表示，如果图有N个节点，则A的维度为(NxN)。

还可以用另一个特征矩阵来描述图中的节点，如果每个节点有F个特征，那么特征矩阵X的维度为(NxF)。

为何图难以分析？

首先，图不存在于欧几里得空间中，这意味着它无法用我们熟悉的任何坐标系表示。

与其他类型的数据（如波、图像或时间序列信号，“文本”也可视为时间序列）相比，图数据的解释要困难得多，因为这些其他类型的数据可以轻松地映射到二维或三维欧几里得空间。

其次，图没有固定形式。

为什么？以下面的例子为例，图（A）和图（B）的结构完全不同，视觉效果也不同。

但是，当我们将其转换为邻接矩阵表示时，如果不考虑边的权重，这两个图的邻接矩阵是相同的，这时我们应该认为这两个图是相同还是不同？

而且图通常难以进行可视化，来方便人类解读。

注意这里所说的并非像上面例子中的小型图，而是涉及数百或数千个节点的大型图。

维度非常高，节点密集分布，使得人类甚至难以理解该图，因此，训练机器执行此任务具有挑战性。

下面的例子展示了建模集成电路中逻辑门的图。

为何使用图？

人们选择研究图的原因可概括如下：

• 图能够更好地处理关系和交互等抽象概念，并为这些概念提供直观的思维方式。图还是分析社交环境中关系的自然基础。

• 图通过将问题简化为更简单的表示或将问题转换为从不同角度的表示，能够解决更复杂的问题。

• 图论和概念用于研究和建模社交网络、欺诈模式、电力消耗模式、社交媒体中的病毒式传播和影响，社交网络分析（SNA）可能是数据科学中图论最著名的应用。

传统图分析方法

传统方法大多基于算法，例如：

• 搜索算法，如广度优先搜索（BFS）、深度优先搜索（DFS）

• 最短路径算法，如迪杰斯特拉算法、最近邻算法

• 生成树算法，如普里姆算法

• 聚类方法，如高连通分量、k均值算法

此类算法的局限性在于，我们需要在一定置信度下获得图的先验知识后才能应用算法。

换句话说，它无法让我们研究图本身，而且，最重要的是，无法进行图级分类。

图神经网络

顾名思义，图神经网络是能够直接应用于图的神经网络，为节点级、边级和图级预测任务提供了便捷方式。

本文中主要有三种图神经网络：

• 递归图神经网络

• 空间卷积网络

• 谱卷积网络

GNN的直观理解是，节点由其邻居和连接自然定义，为了理解这一点，我们可以简单地想象，如果我们移除一个节点周围的邻居和连接，那么该节点将丢失所有信息。

因此，节点的邻居及与邻居的连接定义了节点的概念。

鉴于此，我们为每个节点赋予一个状态（x）来表示其概念，我们可以使用节点状态（x）来产生输出（o），即关于该概念的决策。节点的最终状态（x_n）通常称为“节点嵌入”。

所有GNN的任务都是通过查看其相邻节点的信息来确定每个节点的“节点嵌入”。

我们将从最早的图神经网络版本——递归图神经网络（RecGNN）开始介绍。

另外我们精心打磨了一套基于数据与模型方法的 AI科研入门学习方案（已经迭代过5次），对于人工智能来说，任何专业，要处理的都只是实验数据，所以我们根据实验数据将课程分为了三种方向的针对性课程，包含时序、图结构、影像三大实验室，我们会根据你的数据类型来帮助你选择合适的实验室，根据规划好的路线学习 只需 4 个月左右（很多同学通过学习已经发表了 sci 一区及以下、和同等级别的会议论文）学习形式为 直播＋ 录播，多位老师为你的论文保驾护航，如果需要发高区也有其他形式。

还有时序、影像两个实验室（根据你的数据类型来选择）

大家感兴趣可以直接添加下方小助手微信，通过后回复咨询既可！

AI for science

递归图神经网络

如原始GNN论文所述，

https://ieeexplore.ieee.org/document/4700287

RecGNN 基于 Banach 不动点定理构建，Banach 不动点定理指出：设(X,d)为完备度量空间，(T:X→X)为压缩映射。

则T有唯一的不动点(x∗)，且对于X中的任意x，序列T_n(x)（n→∞）收敛于(x∗)。

这意味着如果对x应用映射T  k次，则xk应几乎等于x(k-1)，即：

RecGNN定义了一个参数化函数f_w：

其中，l_n、l_co、x_ne、l_ne分别表示当前节点[n]的特征、节点[n]的边、相邻节点的状态以及相邻节点的特征。（在原始论文中，作者将节点特征称为节点标签）

最后，经过k次迭代后，使用最终节点状态产生输出，以对每个节点做出决策。

输出函数定义为：

空间卷积网络

空间卷积网络的直观理解与在图像分类和分割任务文献中占主导地位的著名卷积神经网络（CNN）相似。

简而言之，图像上卷积的想法是将中心像素周围相邻像素相加，由具有参数化大小和可学习权重的滤波器指定。

空间卷积网络采用相同的思想，通过将相邻节点的特征聚合到中心节点中。

谱卷积网络

与其他类型的GNN相比，这种图卷积网络具有非常坚实的数学基础。

谱卷积网络建立在图信号处理理论之上，并通过图卷积的简化和近似来实现。

通过切比雪夫多项式近似（Hammond等，2011年），图卷积可以简化为以下形式：

经过进一步简化，图卷积网络（GCN）论文提出了一种两层神经网络结构，该结构可以用以下一个公式来描述：

其中，A_head是原始图邻接矩阵A的预处理拉普拉斯矩阵。

如果大家有一定的机器学习经验，这个公式看起来会非常熟悉。它无非就是我们常用的两层全连接层结构，但在这个场景下，它实现了图卷积的功能，下面将解释为什么它能执行图卷积。

假设我们有一个包含4个节点的简单图，每个节点都被赋予了一个特征矩阵，如图示。

很容易就能得出一个图邻接矩阵和一个特征矩阵，如下所示：

注意，邻接矩阵的对角线被特意改为Ƈ'（某个特定符号，原文如此，实际使用中可能需要替换为具体数学符号或说明），以便为每个节点添加一个自环。这样，在进行特征聚合时，就能包含每个节点自身的特征。

然后我们执行AxX（为了简化说明，我们先忽略A的拉普拉斯矩阵和权重矩阵W）。

矩阵乘法的结果如最右侧的矩阵所示，以第一个节点的结果特征为例。

不难看出，结果是[节点1]所有特征（包括[节点1]自身的特征）的和，而[节点4]的特征并未包含在内，因为它不是[节点1]的邻居。

从数学上讲，图的邻接矩阵只有在存在边时才具有值Ƈ'，否则为其他值，这使得矩阵乘法变成了对与参考节点相连的节点特征的求和。

因此，尽管谱卷积网络和空间卷积网络出发点不同，但它们却遵循相同的传播规则。

目前所有可用的卷积图神经网络都遵循相同的格式，它们都试图学习一个函数，通过该函数传递节点信息，并通过消息传递过程更新节点状态。

任何图神经网络都可以表示为消息传递神经网络（J. Gilmer等人，2017），包含消息传递函数、节点更新函数和读出函数。

图神经网络（GNN）能做什么？
GNN解决的问题大致可以分为三类：

• 节点分类

• 链接预测

• 图分类

在节点分类中，任务是为图中的每个节点预测节点嵌入，这类问题通常采用半监督方式训练，即只有图的一部分被标记。

节点分类的典型应用包括引文网络、Reddit帖子、Youtube视频和Facebook好友关系。

在链接预测中，任务是理解图中实体之间的关系，并预测两个实体之间是否存在连接。

例如，推荐系统可以视为链接预测问题，其中模型接收一组用户对不同产品的评论，任务是预测用户偏好，并根据用户兴趣调整推荐系统以推送更多相关产品。

在图分类中，任务是将整个图分类到不同的类别中,这与图像分类类似，但目标变为了图领域。

图分类可以应用于广泛的工业问题，例如在化学、生物医学、物理学中，模型接收分子结构并要求将目标分类为有意义的类别。这加速了原子、分子或其他结构化数据类型的分析。

GNN在自然语言处理中的应用
GNN在自然语言处理（NLP）中得到了广泛应用，事实上，这也是GNN的起点。

如果大家对NLP有过研究，你可能会认为文本应该是一种顺序或时间数据，最好由RNN或LSTM来描述。

然而，GNN从完全不同的角度来解决这个问题，GNN利用单词或文档之间的内部关系来预测类别。

例如，引文网络试图根据论文引用关系和在其他论文中被引用的单词来预测网络中每篇论文的标签。

它还可以通过查看句子的不同部分而不是像RNN或LSTM那样纯粹按顺序来构建句法模型。

GNN在计算机视觉中的应用
许多基于CNN的方法在图像中的目标检测方面取得了最先进的性能，但我们仍然不知道目标之间的关系。

GNN在计算机视觉中的一个成功应用是使用图来模拟由基于CNN的检测器检测到的目标之间的关系。

从图像中检测到目标后，它们被输入到GNN中进行关系预测。GNN推理的结果是生成的图，该图模拟了不同目标之间的关系。

CV中另一个有趣的应用是从图描述生成图像。这可以解释为上面提到的应用的几乎反向过程。

传统的图像生成方式是使用GAN或自编码器进行文本到图像的生成。

与使用文本描述图像不同，图到图像的生成提供了更多关于图像语义结构的信息。

零样本学习（ZSL）试图在没有目标类的任何训练样本的情况下学习分类目标类。

这颇具挑战性，因为如果没有给出训练样本，我们需要让模型以逻辑方式“思考”以识别目标。

例如，如果我们得到三张图像（如下图所示），并被要求在其中找到“okapi”。

我们可能以前从未见过“okapi”，但是，如果我们还被告知“okapi”是一种长着鹿脸、有四条腿且皮肤有斑马条纹的动物，那么要找出哪一个是“okapi”就不难了。

典型的方法是通过将检测到的特征转换为文本来模拟这个“思考过程”。

然而，文本编码是相互独立的，很难对文本描述之间的关系进行建模。

换句话说，图表示很好地对这些关系进行了建模，使机器能够以更“类似人类”的方式思考。

GNN在其他领域的应用
GNN的更实际应用包括人类行为检测、交通控制、分子结构研究、推荐系统、程序验证、逻辑推理、社会影响预测和对抗攻击防御。

下面显示了一个模拟社交网络中人物关系的图，GNN可以应用于将人们聚类到不同的社区群体中。

结论
本文介绍了一些图论知识，并强调了分析图的重要性，人们总是将机器学习算法视为“黑箱”，大多数机器学习算法只从训练数据的特征中学习，而没有实际的逻辑来执行。

有了图，我们或许能够将一些“逻辑”传递给机器，让它更自然地“思考”。

GNN是分析图数据的强大工具，但它不仅限于图中的问题，它可以很容易地推广到任何可以用图建模的研究中，而图建模是分析问题的自然方式。

另外我们精心打磨了一套基于数据与模型方法的 AI科研入门学习方案（已经迭代过5次），对于人工智能来说，任何专业，要处理的都只是实验数据，所以我们根据实验数据将课程分为了三种方向的针对性课程，包含时序、图结构、影像三大实验室，我们会根据你的数据类型来帮助你选择合适的实验室，根据规划好的路线学习 只需 4 个月左右（很多同学通过学习已经发表了 sci 一区及以下、和同等级别的会议论文）学习形式为 直播＋ 录播，多位老师为你的论文保驾护航，如果需要发高区也有其他形式。

还有时序、影像两个实验室（根据你的数据类型来选择）

大家感兴趣可以直接添加下方小助手微信，通过后回复咨询既可！

AI for science