来源：pythonic生物人
本文约6500字，建议阅读10分钟
本文为你深入探讨了3个概念：图论、深度学习和使用图理论的机器学习。

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. 深度神经网络就是一种图

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

神经网络实际上就是图！

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

回想一下感知器的结构本质。我们可以将输入值（  ）、偏差值（  ）和求和运算（  ）视为图中的3个节点。我们可以将权重（  ）视为连接输入值（  ）和求和运算（  ）的边。

神经网络最相似的具体类型是多部分图。多部分图是可以分成不同节点集的图。每个节点集中的节点可以在节点集之间共享边，但不能在每个节点集内部共享边。

同构二分图（由Wolfram MathWorld提供）

有些神经网络甚至具有完全连接的节点、条件节点和其他疯狂的架构，这些架构赋予了神经网络其特有的多功能性和强大性能；以下是一些最流行的架构：

神经网络动物园（由Asimov Institute提供）

每种颜色对应于不同类型的节点，可以以多种不同的方式排列。通过网络中的数据前向或后向传播类似于图中的消息传递。图中的边缘或节点特征类似于神经网络中的权重。请注意，一些节点甚至具有我们之前提到的自环（RNNs — 循环神经网络中的特性）。

神经网络并不是唯一具有类似图结构的机器学习模型。

• K均值

• K最近邻

• 决策树

• 随机森林

• 马尔可夫链

如上模型，它们本身都具有图形结构，或者以图形结构输出数据。

4. 本质上

我们涵盖了很多内容，但回顾一下，我们深入探讨了3个概念：

• 图论

• 深度学习

• 使用图理论的机器学习

有了这些先决条件，人们可以充分理解和欣赏图学习。在高层次上，图学习进一步探索并利用了深度学习和图理论之间的关系，使用一系列设计用于处理非欧几里德数据的神经网络。

5. 关键要点

有许多关键要点，但要点是：

• 所有图都具有定义其可用或可分析操作的属性。
• 图是使用各种矩阵来进行计算表示的。每个矩阵提供不同数量或类型的信息。
• 深度学习是机器学习的一个子集，大致模拟人类大脑中神经元工作的方式。
• 深度学习通过在网络中前向传递信息并向后传播神经元调整来进行迭代学习。
• 神经网络（以及其他机器学习算法）与图理论有密切联系；

现在你具备了深入了解图学习的所有先决条件。一个好的起点是研究迄今为止已经开发的各种图神经网络的种类。

本文来源网络。仅用于传递和分享更多信息，并不代表本平台赞同其观点和对其真实性负责，版权归原作者所有，如有侵权请联系我们删除。

编辑：黄继彦

原文始发于微信公众号（数据派THU）：深度学习图论(Graph Theory)