定义图上的各向异性、动态、频谱和多尺度滤波器

雷锋网AI科技评论编者按：本篇文章的内容是“计算机视觉及图神经网络教程”的一部分，将概述重要的图神经网络方面的工作进展。通过提取关键思想并解释使用Python和PyTorch这样经典的方法背后的所思所想。

本文来自Boris Knyazev的文章《Anisotropic, Dynamic, Spectral and Multiscale Filters Defined on Graphs》在不改变原文意思的基础上，雷锋网AI科技评论的编译如下：

图1：图神经网络图（GNN）及其相关工作进展。为了避免造成进一步的混乱，有一部分研究成果的边缘并没有突出显示，例如，有关动态图所做的大量工作值得单独概述。

20多年的图神经网络历程

在之前的“图神经网络图（GNN）以及相关的成果”中，添加了我去年遇到的关于图的论文。在这个图中，两项研究成果之间的有向边表示一篇文章是以另一篇文章为基础的，而这个图的颜色则表示：

• 红色-频谱方法（需要对拉普拉斯图进行特征分解，将在下面进行解释）

• 绿色-在空间域中的有效方法（不需要对拉普拉斯图进行特征分解）

• 蓝色-等效于频谱方法，但不需要进行特征分解（因此，真正有效的是空间方法）

• 黑色-是GNN的补充方法，但与GNN本身的选择无关(也就是池化和关注点的问题)。

请注意，有一部分其他重要的研究成果的边缘没有突出显示，是为了避免造成进一步的混乱，其中一小部分用粗体框标出来的，将在这篇文章中进行重点讨论。免责声明：我仍然找到了提炼我们近期研究成果的空间。

这里有一份简单的研究成果清单涵盖了大多数重要方法：

•  知识图的关系机器学习综述（Nicket 等人, 2015）https://arxiv.org/abs/1503.00759

• 几何深度学习:超越欧几里德数据（Hamilton等人，2017）https://arxiv.org/abs/1611.08097

• 结构化的深度模型：在图上进行深度学习以及其他内容（Kipf等人，2018 ） 通过演示幻灯片的形式进行展现。http://tkipf.github.io/misc/SlidesCambridge.pdf

• 归纳关系偏差，深度学习和图网络（Battaglia等人，2018）https://arxiv.org/abs/1806.01261

• 在图上进行深度学习：一项调查（Zhang等人，2018）https://arxiv.org/abs/1812.04202

• 图神经网络：方法与应用综述（Zhou等人，2018）https://arxiv.org/abs/1812.08434

• 图神经网络的综合研究（Wu等人，2019）https://arxiv.org/abs/1901.00596

• 深度神经网络中结构的复兴（Petar Veličković, 2019）博士论文https://www.repository.cam.ac.uk/handle/1810/292230

• NIPS和CVPR视频教程https://sungsoo.github.io/2018/02/01/geometric-deep-learning.html

第一次出现使用神经网络对图进行分类工作的似乎是Alessandro Sperduti和Antonina Starita在1997年发表的关于“结构分类的监督神经网络”的论文中提出的（https://ieeexplore.ieee.org/document/572108）。 

图2：这是Sperduti和Starita在1997提供一组的数字，与20多年后我们现在正在做的工作不谋而合。

Sperduti和Starita在1997指出：“到目前为止，神经网络已经被用来对非结构化模式和序列进行分类。然而，由于它们是基于特征产生的方法，在处理复杂结构的时候，标准的神经网络和统计方法还存在着些许不足。”

自1997年起，从图中进行学习的研究成果在数量上已经增长了很多，而且涉及到了很多不同的方向，如果没有一些智能化的自动化系统，就很难找到它们。我相信我们正在趋于使用基于神经网络的方法（基于本教程第一部分中解释的公式（2）），或者将神经网络与其他方法结合使用。

图3：这是在本教程的第一部分中制作出来的图神经层的公式(2)，在这一部分中我们也会用到。请记住，如果我们需要计算输出特性的特定损耗，或者需要将这些图层堆叠起来，那么就可以应用诸如ReLU或Softmax之类的激活方法。

回顾一下我们在第一部分中使用的表示法，我们有一些具有N个节点的无向图G。图中的每个节点都有一个C维特征向量，所有节点的特征表示为N×C维矩阵X⁽ˡ⁾。在典型的图网络中，例如GCN(Kipf和Wling，ICLR，2017)，我们将这些特征X⁽ˡ⁾提供给具有C×F维可训练权值W⁽ˡ⁾的图神经层，从而使该层的输出是一个N×F矩阵中X⁽l+1⁾编码更新的节点特征(希望在某种意义上能更好)。?是一个N×N的矩阵，其中?ᵢⱼ表示节点i是否连接到（相邻）节点j，这个矩阵称为相邻矩阵。我使用?而不是普通的A来强调这个矩阵可以被规范化，以便于在深度网络中的特征传播。就本教程而言，我们可以假设?=A，也就是矩阵乘积?X⁽ˡ⁾的每i行都包含节点i相邻数据特征的和。

在本教程的其余部分中，我将简要解释一些研究成果，它们在概览图中用粗体标记出来了。我建议对Bronstein等人的综述进行更全面、更正式的分析。

请注意，尽管我在下文中详细介绍了频谱图卷积的一些技术细节，但是最近的很多研究成果(如Xu等人的GIN, ICLR, 2019)都是在没有频谱卷积的情况下构建的，并且还在一些任务中取得了很好的效果。但是，了解谱卷积的工作原理仍然有助于我们理解和避免出现其他方法存在的潜在问题。

 一. 频谱图卷积

Bruna 等人, 2014, ICLR 2014（https://arxiv.org/abs/1312.6203）

我在另一篇文章中详细的解释了频谱图卷积。

在本教程的这一部分中，我将简要地总结一下。频谱图卷积的正式定义与信号/图像处理中的卷积定理非常相似，可以写成：

图4：频谱图卷积，其中⊙表示按特征方向的乘积。

公式中的V表示特征向量，Λ是拉普拉斯图 L的特征值，通过特征分解可以发现：l=VΛVᵀ；W_频谱是滤波器。在本教程中，我假设将“拉普拉斯算子对称归一化”。它仅基于图的相邻矩阵A进行计算，可以通过几行Python代码完成，如下所示：

在这里，我们假设A是对称的，即A=Aᵀ，并且我们的图是无向的，否则节点度不能明确的定义，并且在计算拉普拉斯算子的时候必须要做一些假设。在计算机视觉和机器学习的背景中，拉普拉斯图定义了如果我们以公式(2)的形式叠加多个图神经层，那么节点特征应当如何更新。

因此，给定拉普拉斯图L，节点特征X和滤波器w_频谱，在Python中，图的频谱卷积看起来非常简单：

 

假设我们的节点特征X⁽ˡ⁾是一维的，例如MNIST像素，但是它可以扩展到C维的情况：我们只需要对每个信息通道重复这个卷积，然后像信号或图像卷积一样在C上求和。

公式（3）在本质上与使用傅立叶变换的规则网格上对信号进行的频谱卷积是一样的，因此也为机器学习带来了一些问题：

1.可训练权值(滤波器)w_频谱的维数取决于图中的节点数N;

2. W_频谱也取决于以特征向量V编码的图结构。

这些问题有助于防止数据扩展到具有大型可变结构的图的数据集中。

为了解决第一个问题，Bruna等人根据频谱理论，提出了在频谱域中滑动滤波器的方法，使滤波器在空间域上更具有局部性。其主题思想就是，你可以将公式(3)中的滤波器W_频谱表示为?个预定义函数(如样条曲线)的和，并不是学习N个W的值，而是学习K系数α的总和：

图5：我们可以将N维滤波器W_频谱近似为K个函数f的有限和，如下所示。因此，我们可以学习这些函数的K个系数（alpha），而不是学习W_频谱的N个值。 当K << N时，它变得有效。

尽管fk的维数取决于节点N的数量，但这些函数是固定的，因此我们不需要学习它们。我们唯一需要了解的是系数α，所以W_频谱也不再依赖于N。为了使我们在公式(4)中的近似值变得合理，我们希望K<<N能将可训练参数的数量从N减少到K，更重要的是使它独立于N，这样我们的GNN就可以消化任意大小的图。

在解决第一个问题所用到的这种平滑方法并不适用于解决第二个问题。

二.Chebyshev图卷积

Defferrard等人，NeurIPS, 2016（https://arxiv.org/abs/1606.09375）

频谱卷积及其平滑形式的主要缺点在于，它仍然需要对N×N维拉普拉斯图L进行特征分解，这就产生了两个主要问题：

1.本征分解是非常复杂的，O（N³）。 另外，对于比较大的图，在RAM中保持拉普拉斯图的密集格式是不可行的。其中一种解决方案是使用稀疏矩阵并使用Python中的scipy.sparse.linalg.eigs查找特征向量。此外，你可以在具有大量RAM和CPU内核的专用服务器上预处理所有的训练图。在很多的应用程序中，你的测试图都可以预先进行预处理，但是如果不断有大量新的大型图涌入，特征分解的效果可能也会不那么好。

2. 另一个问题是，你训练的模型最终与图的特征向量V会紧密的联系起来。如果你的训练图和测试图的结构相差很大（节点和边的数量），那么这可能是一个大问题。另一方面，如果所有图都非常相似，那么所遇到的问题就小得多了。而且，如果你在频域中使用的是某些平滑的滤波器，例如上面讨论的样条，那么滤波器会变得更加局部化，并且在适应新图的问题上似乎就更加不明显了。然而，这些模型仍然非常有限。

那么，到现在为止Chebyshev图卷积与所有这些内容又有什么关系呢？

事实证明，它可以同时解决这两个问题！

也就是说，它避免了计算代价高昂的特征分解，滤波器也不再“附加”于特征向量(但它们仍然是特征值Λ的函数)。此外，它具有非常有用的参数，通常表示为K，凭直觉讲应该与我们上面公式(4)中的K相似，它决定了滤波器的位置。通俗地讲：对于K=1，我们只将节点特征X⁽ˡ⁾提供给我们的GNN；对于K=2，我们输入X⁽ˡ⁾和?X⁽ˡ⁾；对于K = 3，我们输入X⁽ˡ⁾，?X⁽ˡ⁾和?²X⁽ˡ⁾； 对于较大的K，依此类推（希望你也注意到了这种模式）请查看Defferrard等人提出的更准确和正式的定义。下面是我的代码，以及其他分析，参见(Knyazev等人，NeurIPS-W，2018)。

由于相邻矩阵的功率特性，当我们在执行?2×⁽ˡ⁾的时候，我们实际上是对2-hop相邻的数据求平均值(或与?的归一化方式有关)，类似于?ⁿX⁽ˡ⁾中的任意n，如下图所示，这里我们就是对n-hop的相邻数据求平均值。

图6：对于节点1(深蓝色)，是K=3的Chebyshev卷积。带圆圈的节点表示影响节点1特征表示的节点，[，]运算符表示特征维度上的连接。W⁽ˡ⁾为3C×F维权值。

请注意，为了满足Chebyshev基的正交性，?假定在图中不设循环，因此在矩阵乘积?X⁽ˡ⁾中的每i行中，我们将具有节点i的邻域特征，而不是节点i本身的特征。单独提供给矩阵X⁽ˡ⁾。

如果K等于节点数N,那么Chebyshev卷积近似于频谱卷积，滤波器的接收域就是整个图。但是，就卷积网络而言，我们不希望我们的滤波器和输入的图像一样大，原因很久之前我就已经讨论过了，所以实际上，K取的值会比较小。

以我的经验来看，这是功能最强大的GNN之一，在很多的关于图的任务中都取得了很好的效果。主要缺点是在前进或者后退的时候需要循环遍历K（由于Chebyshev多项式是递归的，因此无法并行化它们），这会减慢模型的速度。

和上面讨论一样，我们不需要训练滤波器，只需训练系数，这次训练的是Chebyshev多项式的系数。

图7：Chebyshev基用于近似频谱域中的卷积。

要生成Chebyshev基，可以使用以下Python代码：

 生成的样条和Chebyshev基的完整代码在我的 github repo中。

为了说明Chebyshev滤波器是如何在不规则网格上显示的，我遵循Bruna等人的实验。再次以与我展示拉普拉斯图的特征向量相同的方式，从MNIST网格中抽取400个随机点，我在这400个位置采样的MNIST图像上训练了Chebyshev图卷积模型(所有图像都使用相同的不规则网格)，下面显示了当K=1和K=20时的滤波器之一。

 

图8：在MNIST上训练了一个单独的Chebyshev滤波器(左侧k=3，右侧K=20)，并将其应用于具有400个点的不规则网格中的不同位置(显示为红色像素)。与标准ConvNets的过滤器相比，GNN过滤器根据应用节点的不同而具有不同的形状，因为每个节点都具有不同的邻域结构。

二. GCN

Kipf 和 Welling, ICLR, 2017（https://arxiv.org/abs/1609.02907）

你们可能已经注意到了，如果增加Chebyshev卷积的K，可训练参数的总数就会相应增加。例如,对于K = 2,我们的权值W⁽ˡ⁾将会是2C×F，而不仅仅是C×F。这是因为我们将特征X⁽ˡ⁾和?X⁽ˡ⁾连接到了单个N×2C的矩阵中。更多的训练参数也就意味着模型会更加难以训练，必须标记更多的数据进行训练。图的数据集通常会非常小。

在计算机视觉领域中，MNIST被认为是一个很小的数据集，因为图像只有28×28维，并且只有60k训练图像，但是对于图网络而言，MNIST却是相当大的，因为每个图有N=784个节点，60k是大量的训练图。与计算机视觉任务相比，很多图数据集只有大约20-100个节点和200-1000个训练示例。这些图可以表示特定的小分子，而标记化学或生物数据通常比标记图像的成本更昂贵。

因此，训练Chebyshev卷积模型可能会导致训练集严重过拟合(即模型的训练损失接近于0，但验证或测试误差较大)。因此，Kipf和Welling的GCN本质上将节点特征X⁽ˡ⁾和?X⁽ˡ⁾的矩阵“合并”为单个N×C矩阵。结果，与K = 2的Chebyshev卷积相比，该模型要训练的参数少了两倍，但具有相同的1 hop接受域。主要技巧是通过添加一个由I到?的单位矩阵并以特定方式对其进行规范化将自循环添加到图中，因此，现在在矩阵乘积?X?的每i行中，我们将拥有节点i及其相邻数据的特征。

由于这个模型具有轻量级、良好的性能和对较大图的延展性，因此该模型似乎是适合许多应用程序的标准基线选择。

1. GCN与Chebyshev图层

GCN与Chebyshev卷积的区别如下

上面的代码遵循与教程第一部分相同的结构，在第一部分中，我比较了经典的NN和GNN。GCN和Chebyshev卷积的主要步骤之一是计算重新缩放拉普拉斯图L。进行重新缩放的目的是使特征值在[-1,1]范围内进行，以方便训练(这在实践中可能不是很重要的步骤，因为权值可以在训练过程中适应)。在GCN中，在计算拉普拉斯算子之前，先通过添加单位矩阵将自循环添加到图中。两种方法的主要区别在于，在Chebyshev卷积中，我们递归地在K上循环，以捕获K-hop附近的特征。我们可以将这样的GCN层或Chebyshev图层与非线性层叠加，建立一个图神经网络。

现在,请允许我礼貌地打断一下频谱的讨论，并给出其他两个令人兴奋的方法背后的总体思路: ：Simonovsky和Komodakis，CVPR，2017年的边缘条件滤波器（https://arxiv.org/abs/1704.02901）和Monti等人，CVPR，2017年的MoNet（https://arxiv.org/abs/1611.08402），它们具有相似的概念。

四. 边缘条件滤波器

Simonovsky 和 Komodakis, CVPR, 2017（https://arxiv.org/abs/1704.02901）

就像你知道的那样，在ConvNets中，我们通过优化诸如交叉熵之类的损失来学习权值(滤波器)。同样，我们在GNN中学习W⁽ˡ⁾。想象一下，你不用学习这些权值，而是拥有另外一个可以预测权值的网络。因此，在训练过程中，我们将学习该辅助网络的权值，它以图像或图作为输入，并返回工作中的权值W⁽ˡ⁾(Θ)作为输出。这一想法基于动态滤波器网络(Brabandere等人，NIP，2016)，其中“动态”意味着滤波器W⁽ˡ⁾将因输入不同而有所不同，不再是训练结束后固定(或静态)滤波器的标准模型。

图9：使用辅助“滤波器生成网络”Fˡ预测主要网络的边缘特定权值Θ。Xˡ⁻¹是输入节点的特性，Xˡ是输出特性。这个图显示了节点1的“动态卷积”的单次迭代(黄色)。标准GNN通常只会平均(或求和)节点1相邻的节点(节点2、3、4、5)的特征,这相当于各向同性滤波器(Θ将是一个常数向量)。相比之下,这个模型还具有各向异性滤波器,因为它基于边缘标签L可以预测节点1及其所有相邻数据之间的不同边缘值,因此将特征Xˡ(1)计算为相邻数据特征的加权平均值。图来自(Simonovsky 和 Komodakis, CVPR, 2017)。

这是一种非常普遍的卷积形式，除了图像以外，还可以很容易地应用到图或点云上，就像他们在CVPR论文中所做的那样，而且还获得了很好的效果。但是，没有“免费的午餐”，训练这样的模型是相当具有挑战性的，因为现在对常规的网格约束已经放松，并且解决方案的范围显著扩大。

对于有许多边的较大图，或者对于更深层次的卷积尤其如此，这些图通常有数百个通道(特征数量，C)，所以你可能最终会为每个输入生成数千个数字!在这方面，标准的ConvNets的表现就非常好，因为我们没有浪费模型的功能来预测这些权值，而是直接强制所有输入的滤波器都相同。但是，这种先验条件也使ConvNets受到了限制，我们不能直接将它们应用于图或点云。因此，与往常一样，在特定的任务中，灵活性和性能之间需要权衡取舍。

当模型需要应用于像MNIST这样的图像时，边缘条件模型可以学习预测各向异性滤波器例如对方向敏感的滤波器，边缘检测器。与我在本教程第一部分中讨论的高斯滤波器相比，这些滤波器能够更好地捕捉图像中的某些模式，比如数字笔画。

图10：在MNIST上学习的卷积滤波器以低（左）和高（右）的分辨率采样。图来自(Simonovsky和Komodakis, CVPR, 2017)。

我想再强调一次，每当我们有了一个带有辅助网络的复杂模型时，从某种意义上讲，它就变成了先有鸡还是先有蛋的问题。为了解决这个问题，其中一个网络（辅助网络或主要网络）应该接收到非常强的信号，以便它可以隐蔽地监控另一个网络。 在我们的BMVC论文中，有类似于Simonovsky和Komodakis的研究工作的内容，为了促进训练，我们对边缘生成网络添加了额外的限制条件。 我将在以后的文章中详细描述我们的研究工作。

五.MoNet

Monti 等人, CVPR, 2017（https://arxiv.org/abs/1688.08420）

MoNet与本文讨论的其他研究工作不同，因为MoNet假定了具有节点坐标的概念，因此它更适合诸如3D网格分析或图像/视频推理之类的几何任务。这有点类似于Simonovsky和Komodakis的边缘条件滤波器，因为他们还引入了一个辅助可学的函数?(?,?ρ)可以预测权值（?，?，ρ）。

不同之处在于这些权值取决于节点的极坐标（?角和半径ρ）；高斯的均值和方差可以约束这个具有可训练参数为w的函数，因此我们不需要学习N×N矩阵，而仅需要学习独立于图大小，N的固定大小向量（均值和方差）。对于ConvNets，这与为每个滤波器仅学习2个值（高斯的均值和方差）相同，而不是分别为3×3、5×5或11×11维滤波器学习9、25或121个值。这种参数化将大大减少ConvNet中的参数数量，但滤波器捕捉图像特征的能力将非常有限。

Monti等人。训练?高斯的均值和方差，以及节点坐标的转换过程类似于将它们拟合到高斯混合模型中。如果我们希望我们的滤波器能够更加全局化，那么该模型需要大量的计算训练，但它对于可视任务来说会是一个不错的选择（请参阅我们的BMVC文章进行比较），但是在非可视任务上它的表现比简单的GCN还要差。（Knyazev等人，NeurIPS-W，2018）。 由于函数D取决于坐标，因此生成的滤波器也是各向异性的，并且具有定向和拉长高斯曲线的形状，如下图所示。

 

图11：用MoNet训练的极坐标为?和ρ的滤波器。 每个椭圆对应于某个固定水平的高斯切片。这里有个想法是，如果第i个节点的坐标接近第j个高斯的中点，则在索引（i，j）处生成的权值将接近1。

 

总结：

尽管经过了这么长时间的讨论，但我们也只是了解到了一点皮毛。图神经网络的应用已经远远超出了典型的图推理任务，比如分子分类。不同的图神经层的数量正在迅速增加，就像是几年前卷积网络出现的情况，所以很难追踪它们。在这一点上，PyTorch geometry (PyG)是一个很好的学习图的工具，它经常使用新的图层和技巧填充它的集合。

雷锋网(公众号：雷锋网)扩展阅读：

手把手解释频谱图卷积https://www.leiphone.com/news/201909/UBlc5tduQD9yjnnC.html?type=preview&sign=rqhxr4R4oqeDpqKqg3V6koDLo5OBn4-WhIbMoQ

原文链接：https://towardsdatascience.com/tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-2-be6d71d70f49

。