文章来源：https://towardsdatascience.com/graph-theory-and-deep-learning-know-hows-6556b0e9891b

1. 图论(Graph Theory) —— 简明教程

1.1 什么是图(graph)？

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. 深度学习 —— 简明教程

现在让我们快速了解图神经网络(Graph Neural Networks)的另一半。神经网络是我们谈论"深度学习"时所说的架构。

神经网络架构是建立在感知器的概念之上的，感知器受到人类大脑中神经元相互作用的启发。

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

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

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

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

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

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

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

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

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

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

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

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

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

3. 深度学习是图论

为了总结我们所研究的一切并将我们的知识付诸实践，我们将解决房间里的大象。如果你一直在关注，你可能已经注意到一个微妙但显而易见的事实：

人工神经网络实际上只是图！

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

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

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

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

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

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

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

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

• K均值
• K最近邻
• 决策树
• 随机森林
• 马尔可夫链

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

因此，图学习模型可以用于从这些机器学习算法本身中学习。在超参数优化方面存在潜在应用。这正是这篇令人惊叹的论文的作者所做的。

随着我们对在几何数据上泛化深度学习的了解越来越多，可能性才刚刚开始浮出水面。

4. 本质上

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

• 图论
• 深度学习
• 使用图理论的机器学习

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