点击上方 “ 小白学视觉 ”，选择加" 星标 "或“ 置顶 ”

重磅干货，第一时间送达

1. 图论(Graph Theory)

1.1 什么是图(graph)？

在图论的上下文中，图是一种结构化数据类型，具有节点(nodes)（保存信息的实体）和边缘(edges)（连接节点的连接，也可以保存信息）。

图是一种数据结构的方式，但它本身可以是一个数据点。图是一种非欧几里得数据类型，这意味着它们存在于三维空间，不像其他数据类型，比如图像、文本和音频。

图可以具有某些属性，这些属性限制了可以对其执行的可能操作和分析。这些属性可以被定义。

1.2 图的定义

首先，让我们介绍一些定义。

在计算机科学中，我们经常谈论一种称为图的数据结构：

图的边缘和/或节点上可以有标签，让我们给它一些边缘和节点的标签。

标签也可以被视为权重，但这取决于图的设计者。

标签不必是数字，它们可以是文本的。

标签不必是唯一的；给多个节点相同的标签是完全可能的，有时也是有用的。例如，氢分子就是一个例子：

注意混合了数值和文本数据类型

图可以具有特征（也称为属性）。

要小心不要混淆特征和标签。一个简单的思考方式是使用名称、角色和人的类比：

一个节点就是一个人，一个节点的标签就是一个人的名字，而节点的特征就是这个人的特点。

图可以是有向的或无向的：

请注意，有向图也可以具有无向边

图中的一个节点甚至可以有指向自身的边缘。这被称为自环(self-loop)。

图可以是：

• 异构的(Heterogeneous) — 由不同类型的节点组成
• 同构的(Homogeneous) — 由相同类型的节点组成

并且可以是：

• 静态的(Static) — 节点和边不变，没有添加或删除
• 动态的(Dynamic) — 节点和边发生变化，添加、删除、移动等

粗略地说，图可以模糊地描述为：

• 密集的(Dense) — 由许多节点和边组成
• 稀疏的(Sparse) — 由较少的节点和边组成

通过将它们转化为平面形式，可以使图看起来更整洁，这基本上意味着重新排列节点，使边不相交。

当我们探索目前在各种GNN架构中使用的许多不同方法时，这些概念和术语将会派上用场。其中一些基本方法在以下方面进行了描述：

1.3 图分析

有各种不同的图结构可供ML模型学习（Wheel，Cycle，Star，Grid，Lollipop，Dense，Sparse等）。

你可以遍历一个图：

Jon在4个时间步骤内从Bob到Bic；他最好希望不下雪！

在这种情况下，我们正在遍历一个无向图。显然，如果图是有向的，那么只需按照边的方向前进。有几种不同类型的遍历，所以要注意措辞。以下是一些最常见的图遍历术语及其含义：

• 行走（Walk）：图的遍历 —— 闭合行走是指目标节点与源节点相同
• 小径（Trail）：没有重复边的行走 —— 电路（Circuit）是闭合小径
• 路径（Path）：没有重复节点的行走 —— 循环（Cycle）是闭合路径

在遍历的概念基础上，人们还可以在图上发送消息。

Sam？更像是S-p-am（垃圾邮件）...

所有的Sam的邻居都给他发送了一条消息，其中t代表时间步骤。Sam可以选择打开他的邮箱并更新自己的信息。在具有注意机制的模型中，信息在网络中传播的概念非常重要。在图中，消息传递是我们泛化卷积的一种方式。稍后会详细讨论。

1.4 E-图 — 计算机上的图

通过学习所有这些，你现在对图理论有了基本的理解！任何对GNNs重要的其他概念将会随着它们的出现而进行解释，但与此同时，还有一个关于图的最后一个主题我们需要涵盖。我们必须学会如何在计算中表达图。

有几种方法可以将图转化为计算机可以处理的格式；它们都是不同类型的矩阵。

关联矩阵Incidence Matrix（I）：

关联矩阵通常在研究论文中用大写字母I表示，由1、0和-1组成，关联矩阵可以按照以下简单的模式制作：

从图到关联矩阵

（带权重的）邻接矩阵Adjacency Matrix（A）：

图的邻接矩阵由1和0组成，除非它是加权或带标签的。在任何情况下，A都可以按照以下规则构建：

无向图的邻接矩阵因此在其对角线上是对称的，从左上角对象到右下角：

有向图的邻接矩阵只覆盖对角线线的一侧，因为有向图的边只朝一个方向。

邻接矩阵可以是“带权重的”，这基本上意味着每条边都有与之关联的值，所以不是1，而是将值放在相应的矩阵坐标中。这些权重可以代表任何你想要的东西。例如，在分子的情况下，它们可以表示两个节点（原子）之间的键的类型。在LinkedIn这样的社交网络中，它们可以表示两个节点（人）之间的1st、2nd或3rd级连接。

边的权重概念是使GNNs如此强大的一个属性；它们允许我们考虑结构性（依赖性）和独立性信息。对于实际应用，这意味着我们可以考虑外部和内部信息。

度矩阵（D）：

图的度矩阵可以通过之前介绍的度概念来找到。D本质上是一个对角矩阵，其中对角线的每个值都是其对应节点的度数。

各种类型的图和矩阵（由欧洲生物信息学研究所提供）

不要忘记度数只是邻接矩阵的每一行的总和。然后，这些度数被放在矩阵的对角线上（邻接矩阵的对称线）。这很好地引出了最后的矩阵：

拉普拉斯矩阵（L）：

图的拉普拉斯矩阵是通过从邻接矩阵中减去度矩阵而得到的：

度矩阵中的每个值都减去了相应的邻接矩阵中的值，如下所示：

图矩阵三合一（由维基百科提供）

还有其他图矩阵表示法，如关联矩阵，但绝大多数应用于图类型数据的GNN应用都使用这三个矩阵中的一个、两个或全部。这是因为它们，尤其是拉普拉斯矩阵，提供了关于实体（具有属性的元素）和关系（实体之间的连接）的重要信息。

唯一缺失的是一个规则（将实体通过关系映射到其他实体的函数）。这就是神经网络派上用场的地方。

2. 深度学习

神经网络模型 （或简称NN）及其扩展家族，包括卷积神经网络、循环神经网络，当然还有图神经网络，都是深度学习算法的一种类型。

深度学习是一种机器学习算法，而机器学习又是人工智能的一个子集。

一切都始于谦卑的线性方程。

如果我们将这个方程结构化为一个感知器，我们可以看到：

其中输出( )是偏差( )与输入( )乘以权重( )的和( )。

神经网络通常具有激活函数，它基本上决定了一个给定神经元的输出（ ）是否应该被认为是“激活的”，并将感知器的输出值保持在一个合理的可计算范围内（例如，sigmoid函数用于 范围，tanh函数用于 范围，ReLU函数用于 或 等）。这就是为什么我们在感知器的末端附加激活函数的原因。

当我们将一堆感知器放在一起时，我们得到了一个类似于神经网络开端的东西！这些感知器将数值值从一层传递到另一层，每一次传递都将该数值值接近网络经过训练的目标/标签。

当你把一堆感知器放在一起时，你会得到：

一个普通的NN（由Digital Trends提供）

要训练神经网络，我们首先需要计算我们需要调整模型权重的量。我们使用损失函数来做到这一点，它计算误差。

其中 是误差， 是期望的输出， 是实际输出。在高层次上，误差计算为实际输出（神经网络的预测）减去期望输出（目标）。目标是最小化误差。通过使用称为反向传播的过程来调整每一层的权重来最小化误差。

基本上，反向传播将调整从输出层传播到输入层的整个网络。所调整的量由接收误差作为输入的优化函数确定。优化函数可以被想象成一个球在山上滚动，球的位置就是误差。因此，当球滚到山底时，误差达到最小值。

此外，还有一些必须定义的超参数，其中最重要的之一是学习率。学习率调整了优化函数应用的速率。学习率就像重力设置；重力越大（学习率越高），球滚得越快，反之亦然。

神经网络具有许多不同的宏观和微观自定义选项，使每个模型都具有独特的特点，性能各异，但它们都是基于这个基本模型的。稍后我们将看到，这对于图学习尤其如此。根据需要将介绍卷积和重复等操作。

3. 深度神经网络就是一种图

文章到此，你可能已经注意到一个微妙但显而易见的事实：

神经网络实际上就是图！

神经网络是一种特殊的图，但它们具有相同的结构，因此具有相同的术语、概念和规则。

回想一下感知器的结构本质。我们可以将输入值（ ）、偏差值（ ）和求和运算（