1. 图论(Graph Theory)
1.1 什么是图(graph)？
在图论的上下文中，图是一种结构化数据类型，具有节点(nodes)（保存信息的实体）和边缘(edges)（连接节点的连接，也可以保存信息）。图是一种数据结构的方式，但它本身可以是一个数据点。图是一种非欧几里得数据类型，这意味着它们存在于三维空间，不像其他数据类型，比如图像、文本和音频。图可以具有某些属性，这些属性限制了可以对其执行的可能操作和分析。这些属性可以被定义。1.2 图的定义
在计算机科学中，我们经常谈论一种称为图的数据结构：图的边缘和/或节点上可以有标签，让我们给它一些边缘和节点的标签。标签不必是唯一的；给多个节点相同的标签是完全可能的，有时也是有用的。例如，氢分子就是一个例子：要小心不要混淆特征和标签。一个简单的思考方式是使用名称、角色和人的类比：一个节点就是一个人，一个节点的标签就是一个人的名字，而节点的特征就是这个人的特点。
图中的一个节点甚至可以有指向自身的边缘。这被称为自环(self-loop)。- 异构的(Heterogeneous) — 由不同类型的节点组成
- 同构的(Homogeneous) — 由相同类型的节点组成
并且可以是：
- 静态的(Static) — 节点和边不变，没有添加或删除
- 动态的(Dynamic) — 节点和边发生变化，添加、删除、移动等
粗略地说，图可以模糊地描述为：
通过将它们转化为平面形式，可以使图看起来更整洁，这基本上意味着重新排列节点，使边不相交。
当我们探索目前在各种GNN架构中使用的许多不同方法时，这些概念和术语将会派上用场。其中一些基本方法在以下方面进行了描述：1.3 图分析
有各种不同的图结构可供ML模型学习（Wheel，Cycle，Star，Grid，Lollipop，Dense，Sparse等）。
Jon在4个时间步骤内从Bob到Bic；他最好希望不下雪！在这种情况下，我们正在遍历一个无向图。显然，如果图是有向的，那么只需按照边的方向前进。有几种不同类型的遍历，所以要注意措辞。以下是一些最常见的图遍历术语及其含义：- 行走（Walk）：图的遍历 —— 闭合行走是指目标节点与源节点相同
- 小径（Trail）：没有重复边的行走 —— 电路（Circuit）是闭合小径
- 路径（Path）：没有重复节点的行走 —— 循环（Cycle）是闭合路径
在遍历的概念基础上，人们还可以在图上发送消息。
所有的Sam的邻居都给他发送了一条消息，其中t代表时间步骤。Sam可以选择打开他的邮箱并更新自己的信息。在具有注意机制的模型中，信息在网络中传播的概念非常重要。在图中，消息传递是我们泛化卷积的一种方式。稍后会详细讨论。1.4 E-图 — 计算机上的图
通过学习所有这些，你现在对图理论有了基本的理解！任何对GNNs重要的其他概念将会随着它们的出现而进行解释，但与此同时，还有一个关于图的最后一个主题我们需要涵盖。我们必须学会如何在计算中表达图。
有几种方法可以将图转化为计算机可以处理的格式；它们都是不同类型的矩阵。关联矩阵通常在研究论文中用大写字母I表示，由1、0和-1组成，关联矩阵可以按照以下简单的模式制作：（带权重的）邻接矩阵Adjacency Matrix（A）：图的邻接矩阵由1和0组成，除非它是加权或带标签的。在任何情况下，A都可以按照以下规则构建：无向图的邻接矩阵因此在其对角线上是对称的，从左上角对象到右下角：有向图的邻接矩阵只覆盖对角线线的一侧，因为有向图的边只朝一个方向。邻接矩阵可以是“带权重的”，这基本上意味着每条边都有与之关联的值，所以不是1，而是将值放在相应的矩阵坐标中。这些权重可以代表任何你想要的东西。例如，在分子的情况下，它们可以表示两个节点（原子）之间的键的类型。在LinkedIn这样的社交网络中，它们可以表示两个节点（人）之间的1st、2nd或3rd级连接。边的权重概念是使GNNs如此强大的一个属性；它们允许我们考虑结构性（依赖性）和独立性信息。对于实际应用，这意味着我们可以考虑外部和内部信息。图的度矩阵可以通过之前介绍的度概念来找到。D本质上是一个对角矩阵，其中对角线的每个值都是其对应节点的度数。不要忘记度数只是邻接矩阵的每一行的总和。然后，这些度数被放在矩阵的对角线上（邻接矩阵的对称线）。这很好地引出了最后的矩阵：图的拉普拉斯矩阵是通过从邻接矩阵中减去度矩阵而得到的：度矩阵中的每个值都减去了相应的邻接矩阵中的值，如下所示：![]()
图矩阵三合一（由维基百科提供）还有其他图矩阵表示法，如关联矩阵，但绝大多数应用于图类型数据的GNN应用都使用这三个矩阵中的一个、两个或全部。这是因为它们，尤其是拉普拉斯矩阵，提供了关于实体（具有属性的元素）和关系（实体之间的连接）的重要信息。唯一缺失的是一个规则（将实体通过关系映射到其他实体的函数）。这就是神经网络派上用场的地方。2. 深度学习
神经网络模型（或简称NN）及其扩展家族，包括卷积神经网络、循环神经网络，当然还有图神经网络，都是深度学习算法的一种类型。
深度学习是一种机器学习算法，而机器学习又是人工智能的一个子集。
一切都始于谦卑的线性方程。
如果我们将这个方程结构化为一个感知器，我们可以看到：其中输出( )是偏差( )与输入( )乘以权重( )的和( )。神经网络通常具有激活函数，它基本上决定了一个给定神经元的输出（ ）是否应该被认为是“激活的”，并将感知器的输出值保持在一个合理的可计算范围内（例如，sigmoid函数用于 范围，tanh函数用于 范围，ReLU函数用于 或 等）。这就是为什么我们在感知器的末端附加激活函数的原因。当我们将一堆感知器放在一起时，我们得到了一个类似于神经网络开端的东西！这些感知器将数值值从一层传递到另一层，每一次传递都将该数值值接近网络经过训练的目标/标签。一个普通的NN（由Digital Trends提供）要训练神经网络，我们首先需要计算我们需要调整模型权重的量。我们使用损失函数来做到这一点，它计算误差。 其中 是误差， 是期望的输出， 是实际输出。在高层次上，误差计算为实际输出（神经网络的预测）减去期望输出（目标）。目标是最小化误差。通过使用称为反向传播的过程来调整每一层的权重来最小化误差。基本上，反向传播将调整从输出层传播到输入层的整个网络。所调整的量由接收误差作为输入的优化函数确定。优化函数可以被想象成一个球在山上滚动，球的位置就是误差。因此，当球滚到山底时，误差达到最小值。此外，还有一些必须定义的超参数，其中最重要的之一是学习率。学习率调整了优化函数应用的速率。学习率就像重力设置；重力越大（学习率越高），球滚得越快，反之亦然。神经网络具有许多不同的宏观和微观自定义选项，使每个模型都具有独特的特点，性能各异，但它们都是基于这个基本模型的。稍后我们将看到，这对于图学习尤其如此。根据需要将介绍卷积和重复等操作。3. 深度神经网络就是一种图
文章到此，你可能已经注意到一个微妙但显而易见的事实：神经网络是一种特殊的图，但它们具有相同的结构，因此具有相同的术语、概念和规则。回想一下感知器的结构本质。我们可以将输入值（ ）、偏差值（ ）和求和运算（ ）视为图中的3个节点。我们可以将权重（ ）视为连接输入值（ ）和求和运算（ ）的边。神经网络最相似的具体类型是多部分图。多部分图是可以分成不同节点集的图。每个节点集中的节点可以在节点集之间共享边，但不能在每个节点集内部共享边。同构二分图（由Wolfram MathWorld提供）有些神经网络甚至具有完全连接的节点、条件节点和其他疯狂的架构，这些架构赋予了神经网络其特有的多功能性和强大性能；以下是一些最流行的架构：神经网络动物园（由Asimov Institute提供）每种颜色对应于不同类型的节点，可以以多种不同的方式排列。通过网络中的数据前向或后向传播类似于图中的消息传递。图中的边缘或节点特征类似于神经网络中的权重。请注意，一些节点甚至具有我们之前提到的自环（RNNs — 循环神经网络中的特性）。如上模型，它们本身都具有图形结构，或者以图形结构输出数据。
4. 本质上
我们涵盖了很多内容，但回顾一下，我们深入探讨了3个概念：有了这些先决条件，人们可以充分理解和欣赏图学习。在高层次上，图学习进一步探索并利用了深度学习和图理论之间的关系，使用一系列设计用于处理非欧几里德数据的神经网络。
