在日常用语中，图通常用来表示图形、图表和数据可视化。然而，从严格量化角度来看，“图”是指非常特殊的数据结构，由一些N-sized的节点集合组成，一些边缘集合，以及可以附加到节点或边缘的属性。虽然某些类型的信息本质上是图形式的，但更常见的是，图是有意选择的组织某种信息的方式，以便捕获和强调数据元素之间的关系。

图可用于表示社交网络和家庭关系，网络流量和分子结构。但是当我们以图的形式提供网络数据时，我们会给它一个归纳偏置（inductive bias）。机器学习中的归纳偏置的概念是，即使模型可以访问相同的信息（来自统计内容，信息理论POV），为模型学习某些类型的模式的优先级可以帮助它执行更好。在传统模型正则化中可以看到最简单的形式：降低系数的绝对值，导致更平滑的函数，并反映一个隐含的先验，即更平滑的函数更可能是真的、可泛化的函数，而锐利、跳跃的函数更容易过度拟合。但是，如果先验错误，我们可能会将我们的机器学习模型引向错误的方向。

当我们专门设计一个处理图的网络时，隐含地告诉它节点之间的关系是有意义的，前提是我们想要从图中提取的信息被这些模式关系所吸引，并且最有效地通过考虑到它们。如果结果不是这样，那你肯定是找错地方了。但是，如果是这种情况，您先前的关于模型的有用概念将大大缩小了它的算法搜索空间。

卷积网络的目标是处理图像——一种复杂的结构化数据——并将其“消化”成一些压缩的特征集。图网络具有相同的目标，只不过它的目标是摄取和获得图中包含的有用的高级形式的信息。人们可能想要从图中提出的问题可能是多种多样的，比如“这个分子结构似乎有可能作为治疗X疾病的药物”，或者“这个社会图表中的X个人有多大可能支持某个特定观点”。在前者情况下,我们想学习完整的图的属性。在类似于后者的情况下，我们希望预测图中特定节点或边缘的属性。

这篇文章将对两大类方法进行简要概述，这两类方法用于向网络提供这种面向图形的归纳偏置。

根据数学定义，图具有一些属性，在构建要摄取这些属性的操作符时需要考虑这些属性:

• 图可以具有任意数量的节点
• 每个节点可以具有任意数量的相邻节点
• 没有空间和方向的概念;考虑图形节点的“左”或“右”相邻节点是不明智的，就像在常规网格中布局图像像素一样。

最后两点结合起来使得简单的卷积方法变得不可行 - 当每个节点具有任意数量的相邻节点时，你不能对上，下，左，对角等方向的相邻节点应用具有固定权重的filter ，而不是存在于相对于中心像素的固定位置的离散数。此外，还没有一种明确定义的方法来沿着图滑动(或“translate”)一个过滤器。

在理解图处理时，一个重要的概念区别是

• 信息至少部分地包含在图本身的结构中的问题，并且您希望馈送到网络的每个示例可能具有不同的连接模式。这种情况的一个例子是试图对不同分子进行分类的情况，每种分子具有不同的键结构。

当表示为图时，原子被视为具有与元素类型对应的属性的节点，以及具有与键类型对应的属性的边

• 图的连通性结构在所有示例中都是固定的，但是图的各个部分的属性不同，定义的函数具有一些我们可能想要学习的特性或模式匹配的特性。“在图上定义的函数”的概念，在同一个图上可以定义不同的函数，对于本文和阅读任何关于图分析的文章来说，这都是一个需要理解的关键概念。这方面的一个例子可能是有关通过道路网络连接的一组城市中每个城市的受感染人数的信息，您希望了解该疾病传播的速度：城市之间的道路连接不会随着场景的变化而变化，而只是每个城市的属性值。您还可以将图像视为在相同（非常无聊）像素图上定义的不同像素值函数，例如左上角的节点连接在其右侧和底部。

美国的道路连通图

在比较可以应用不同方法的哪些类型的问题时，这种区别将特别有用。

寻找非常规卷积

卷积是现代神经网络设计中的一项重大创新。卷积是一种特殊的设计，用于以一种更有效地处理图像的方式来处理图像，相对于简单的模型，它似乎具有有价值的归纳偏置。围绕图网络的构思围绕着这个关键问题建立起来的:我们能对图做同样的事情吗?我们能否设计出一种结构，利用卷积网络最有价值的特性（以一种图可以使用的方式）。

这一领域的两种主要方法都试图回答这个问题，即如何将卷积推广到图上，它们都随意地称自己为“图形卷积”，但它们采用的方法却截然不同。第一种方法试图复制卷积的字面数学运算，而第二种方法只是对特定于图像的卷积所扮演的角色进行启发式分析，并试图重新创建它。

检查Spectrum

首先是完美主义者:他们通过问“卷积是什么，在深层数学层面上，以及我们如何将它复制到图形上”来找到答案。这个解释会让你暂时偏离图，但我保证它会回来的。

这种运算在原始数据的许多不同偏移量下计算相同模式的点积匹配，通常需要在大的“循环矩阵”中以不同的偏移量重复你的模式多次，就像下面这个，然后乘以包含数据的向量(或矩阵)。

这是一个计算1D向量上的简单卷积的矩阵 - 向量的每一行都是filter的副本，shifted 了一些量。当我们将它乘以右边的向量时(类似地，与filter匹配的数据)，我们在每个偏移处得到不同的激活，这取决于数据与filter最接近的对齐方式(向量越相似，点积就越高)

但是，可以对数据和过滤器进行转换，使每个过滤器都由一个简单的对角线矩阵表示(除了沿对角线的值之外，所有的0)，该矩阵与数据的转换版本相乘。当你对数据进行傅里叶变换时，这种简化就会发生。傅里叶变换通常被认为是在函数的上下文中，并且(在非常高的层次上)，它们将任何函数表示为简单的“频率”函数的加权组合;从低频开始解释数据的粗线条模式，到高频结束（填充较细)。

在进行任何变换之前，连续函数可以由无限长矢量完全表示，只需指定每个点的值。（顺便说一句：在许多卷积和傅立叶变换都讨论函数运算的情况下，更容易想象它发生在固定长度的向量上）。当转换为傅立叶空间时，在最坏的情况下，你的函数可能仍然需要一个无限长的向量来正确表示，但是向量的项将代表构成函数的每个频率的大小，而对于更简单的函数，你仅通过查看频率加权矢量的第一个（例如10个项），就能够捕获函数的良好近似值。对这个事实给出直观或数学解释是太过分散，但是关于卷积的数学上真实的事实是，操作者可以通过将单个(对角化)投影到傅立叶域，并将其乘以你的数据，也在傅立叶域中计算。

您可以看到，上面的矩阵是您的过滤器在每行中的一个above — offset版本的有效副本，乘以一个矩阵。下面的版本是φ矩阵。

Spectral Convolution的支持者认为他们应该从以下角度来处理问题:如果他们能找到一组数据的Fourier basis ，然后他们可以把权重和数据都投射到这个basis上，通过这个定义途径，它们得到了一个卷积，即使没有定义明确的沿图移动或“平移”)滤波器的能力。这组矩阵乘法的结果是一个n维向量。

我们沿着这条有点曲折的路走下去，得到了一个数学上有效的卷积的不同的推导表达式。这和图有什么关系呢?我们可以在图上定义一个Fourier basis，通过取Graph Laplacian的特征值 - 一个由度矩阵D（由每个节点沿对角线的度数构成）构造的矩阵并减去权重或邻接矩阵，用于捕获所有边缘的权重。

Laplacian用于计算“图梯度”，即根据每个相邻节点的权重，度量每个节点的函数值相对于邻近节点的函数值的变化量。当你计算拉普拉斯算子的特征向量时，你最终得到了这个图的Fourier basis，以及一种将图上定义的函数投影到n维欧几里得空间中定义的函数上的方法。这些轴也称为图的“spectrum”，因此称为“谱聚类”。它们在概念上对应的方向，作为一维投影，沿着图捕捉最大的距离。默认情况下，特征向量和图节点一样多，每个节点都由所有这些向量定义的轴上的值表示。注意特征向量是图的连接性的表示，并且与图上定义的函数无关。这就是为什么我们可以在图上把不同的函数表示成沿着eigenvector basis的不同形式的值。

对应于最大特征值的特征向量/特征函数。你可以看到(a)是一个沿对角线从左上角到右下角的梯度，这是一维的压缩它可以很好地捕捉到图像上的距离。(b)是一个从中心向外大致呈放射状的轴线，这是考虑到(a)的次优单维表示，依此类推。

要通过此方法计算spectral 卷积，首先需要计算图的完整NxN拉普拉斯特征向量矩阵，然后将每个filter以及数据本身乘以该矩阵。对于大型图，这是非常计算密集的，因为它对于每个filter按比例缩放（N²）。除了计算复杂性之外，spectral 卷积方法的一个显著缺点是，它们只对学习固定图上的模式有用，不能有效地学习或考虑到每个观察图有不同连接结构的情况。这是因为每一组计算出的特征值只适用于它被计算出的特定图形。

另外，spectral 卷积本身不是局部的（即，在中心节点周围的一小组邻居上定义），而是匹配图形的全局连接结构的模式。默认情况下，它们会更加严格，并导致他们需要了解更多参数。这个问题可以通过学习过滤器来解决，这些过滤器是每个特征向量的简单多项式变换，因为它们需要更少的参数并匹配更小，更局部化的模式。然而，事实仍然是，Spectral Convolutions本身并未精心设计为局部模式匹配器。

Pass the Word Along

因此，Spectral Convolutions的优点是允许我们在图上执行数学上正确的卷积，但是它们在实际应用中有很大的缺点。

考虑到图像卷积的优点，以及如何用图形作为输入来复制它们。广义的消息传递神经网络(MPNN)试图模仿普通卷积的许多优点，但其过程在数学上是不同的。

提醒一下，我们需要图形计算的基本属性是a)它可以对称地应用于每个节点，作为该节点属性的函数;B)它可以跨任意数量的邻居聚合信息

一些论文提出了基本上类似的方法。每一种方法都有它们自己的稍微不同的组合。最一般的框架，看起来像:

来自DeepMind Graph Networks论文的图，说明了从节点拉取信息的边缘的迭代过程，从边缘拉入信息的节点，然后从两者一起更新全局网络属性。

• 节点、边和全局网络作为一个整体，都具有附加在它们上的向量值属性。您还可以设置所有这些都具有属性向量和“隐藏”向量(即RNN)，以便提供一种方法使信息保持更灵活，但目前，我们将坚持使用单个属性向量模型。
• 边缘属性通过计算它们的发送节点、接收节点、全局属性和它们自己的过去值的一些转换来更新它们自己。注意，对于“接收节点属性”和“发送节点属性”，可以使用特定的权重矩阵，因为给定的边缘只有一个发送方和接收方。
• 节点属性根据所有传入边缘邻居(以及全局属性值和它们自己的过去值)的聚合信息更新自己。因为节点可以有任意多条边，所以这种聚合通常通过最基本的输入大小不变的操作和来完成，但是也可以使用基于内容的注意力加权来完成。
• 最后，“全局属性”被计算为某种节点值的聚合 - 再次，可以是一个总和，可以是注意力，只要它适用于不同大小的输入。
• 现在，节点通过边缘从所有相邻节点中提取信息。如果此过程重复多次，则信息将能够产生多个“hops”，并且每个节点将提取关于图的其余部分的更宽字段的上下文信息。这与具有更宽的感受野的卷积堆叠中的后期层相当。
• 最后，在对此更新过程进行了一些迭代之后，您现在拥有了从图的其余部分收集了一定量上下文的节点，边和全局属性。

这种结构很有趣，因为它既有卷积结构又有循环结构。它的启发式类似于普通的卷积，因为它在网络上的任何地方都使用相同的共享转换集，而且它假设图上有趣的结构是连续的，因此优先从同心圆中提取信息。这种逐渐扩展的接收场函数更接近于一个接收场逐层扩大的图像卷积网络。这里有一个有趣的注意事项，正如前面所暗示的那样:像这样的图操作从根本上来说不如图像卷积灵活，因为它们平等地从每个邻居提取信息。你可以把它想象成一个离散的径向卷积，你从不同的点提取信息取决于它们的距离，使用离散的距离单位。

如果您假定使用相同的转换，不仅在图中的所有点上，而且在扩散过程的后续迭代中，该结构也开始变得非常像一个循环网络。在这种情况下，你几乎可以把它想象成一个径向循环网络，向外处理所有的方向。在这个节点到节点信息扩散的高级框架中，您可以沿着这个spectrum 定义许多网络子类型——对于每个看起来more convolutional的“层”，或者迭代地重新计算看起来更重复的相同转换的网络，具有不同转换的网络;仅在节点、边缘或全局上预测值的模型。但它们都使用相同的基本构建块。

这些方法比spectral 卷积要灵活得多，因为这些操作可以在不同的连通性结构上执行，而且仍然可以得到一致的结果，如果你试图将一个图的函数投影到另一个图的Laplacian Fourier basis上，就不会出现这种情况。它们本质上也是局部的，因为每个转换只从邻居那里获取信息。然而，这个堆栈并不是真正意义上的卷积，它只是一组模拟卷积的一些优点的启发式操作。

最后

与图像相比，图网络的设计仍处于早期：它的用途更小，缺乏像ImageNet那样的标准化数据集。现代模型设计倾向于通过从现有领域中大量借用，然后将这些直觉导入神经网络; 图网络方法的研究人员似乎仍然处于调查其他领域的阶段 - spectral 分析和消息传递算法 - 试图找出可以找到有价值的见解的地方

这两种方法都试图推广卷积的成功，但是一个人用数学家的证明和精确度来做，而另一个用工程师的实用启发式算法。

从外部的角度来看，虽然我很欣赏spectral 卷积背后的聪明才智，但我认为MPNN具有相当大的优势，特别是在涉及非固定图形问题时。