雷锋网AI技术评论编者按:本文内容是《计算机视觉与图神经网络教程》的一部分,概述了重要的图神经网络工作的进展。使用Python 和PyTorch 等经典技术提取关键思想并解释其背后的思想。
本文改编自Boris Knyazev的文章《Anisotropic, Dynamic, Spectral and Multiscale Filters Defined on Graphs》,在不改变原意的情况下总结了雷锋网的AI技术评论:
图1:图神经网络(GNN)及相关研究进展。为了避免进一步混淆,一些外围发现没有被强调。例如,对动态图进行的广泛研究值得单独概述。
超过20 年的图神经网络经验在上一篇文章《图神经网络图(GNN) 和相关结果》中,我添加了一篇我去年遇到的关于图的论文。在此图中,两项研究之间的有向边表明一篇论文基于另一篇论文,并且该图中的颜色表示:
红色- 光谱方法(需要下述拉普拉斯图的特征分解)
绿色- 空间域中的有效方法(不需要拉普拉斯图的特征分解)
蓝色——相当于谱法,但不需要特征分解(因此空间法非常高效)
Black - 一种补充GNN 的方法,但与GNN 本身的选择无关(即池化和焦点问题)。
请注意,其他重要发现的边缘并未突出显示,以避免进一步混淆。其中一些标有粗体框,将在本文中进行解释。免责声明:最近的研究结果仍有进一步改进的空间。
以下是涵盖最重要方法的研究结果的简短列表。
知识图关系机器学习综述(Nicket et al. 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 et al. 2018)https://arxiv.org/abs/1812.08434
图神经网络的综合研究(Wu et al. 2019)https://arxiv.org/abs/1901.00596
深度神经网络结构的复兴(Petar Velikovi,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 等激活技术。
回顾我们在第1 部分中使用的符号,我们有一些带有N 个节点的无向图G。图中的每个节点都有一个C维特征向量,每个节点的特征表示为一个NC维矩阵X。典型的图网络,例如GCN(Kipf 和Wling,ICLR,2017),提供了这些特征。该层的输出是Xl+1 编码的更新节点特征的NF 矩阵(希望在某种意义上)。是一个NN矩阵,其中表示节点i是否与(邻居)节点j相连;这个矩阵称为邻接矩阵。我们使用这个矩阵而不是平面A 来强调它可以被归一化以促进深度网络中的特征传播。本教程假设=A。即矩阵乘积X 的每i 行包含与节点i 相邻的数据特征之和。
本教程的其余部分将简要讨论概述图中以粗体标记的一些研究结果。我建议对Bronstein 等人的评论进行更全面和正式的分析。
我们将在下面详细讨论频谱图卷积的技术细节,但是最近的许多工作(例如Xu 等人的GIN,ICLR,2019)都是在没有频谱图卷积的情况下构建的,这对于某些任务来说效果很好。请注意,类似的结果也得到了实现。然而,了解光谱卷积的工作原理可以帮助您理解并避免其他方法的潜在问题。
1. 谱图卷积Bruna 等人,2014,ICLR 2014 (https://arxiv.org/abs/1312.6203)
我将在另一篇文章中详细讨论谱图卷积。
本教程的这一部分提供了快速摘要。谱图卷积的形式定义与信号/图像处理中的卷积定理非常相似,可以写为:
图4:频谱图卷积。 按特征方向表示产品。
式中,V代表特征向量,是拉普拉斯图L的特征值。这是由特征分解给出的:l=VV;W_spectrum 是滤波器。本教程假设“拉普拉斯算子的对称正则化”。这是仅基于图的邻接矩阵A 计算的,并且可以使用几行Python 代码来完成,如下所示:
我们假设A 是对称的,即A=A,并且该图是无向的。否则,无法明确定义节点度,并且在计算拉普拉斯算子时必须做出一些假设。在计算机视觉和机器学习的背景下,拉普拉斯图定义了当多个图神经层以等式(2)的形式堆叠时节点特征如何更新。
因此,给定拉普拉斯图L、节点特征X 和滤波器w_spectrum,图的谱卷积在Python 中看起来非常简单。
假设我们的节点对C 求和。
方程(3)给机器学习带来了一些问题,因为它本质上与使用傅里叶变换在规则网格上对信号进行频谱卷积相同。
1. 可训练权重(滤波器)w_spectrum的维度取决于图N中的节点数量。
2. W_spectrum还取决于特征向量V编码的图结构。
这些问题有助于防止数据扩展到具有大型可变结构图的数据集。
为了解决第一个问题,Bruna等人提出了一种基于谱理论的方法,在谱域滑动滤波器,使滤波器在空间域更加局部化。主要思想是,方程(3)中的滤波器W_spectrum可以通过学习K个系数的和而不是学习W的N个值来表示为预定义函数(例如样条曲线)的和。
图5:N 维滤波器W_spectrum 可以近似为K 个函数f 的有限和,如下所示。因此,我们可以学习这些函数的K个系数(alpha),而不是学习W_spectrum的N个值。当K
fk 的维度取决于节点数N,但这些函数是固定的,不需要学习。我们只需要知道系数,因此W_spectrum不再依赖于N。需要K 才能使等式(4)的近似合理。
用于解决第一问题的平滑方法不适用于解决第二问题。
2. 切比雪夫图的卷积Defferrard 等人,NeurIPS,2016 (https://arxiv.org/abs/1606.09375)
谱卷积及其平滑形式的主要缺点是它仍然需要NN Veraplacian 图L 的特征分解,这引入了两个主要问题:
1.本征分解非常复杂,O(N)。此外,对于相对较大的图,在RAM 中维持拉普拉斯图的稠密形式是不切实际的。一种解决方案是使用稀疏矩阵并使用Python 的scipy.sparse.linalg.eigs 查找特征向量。此外,所有训练图都可以在具有大量RAM 和CPU 核心的专用服务器上进行预处理。在许多应用中,可以提前对测试图进行预处理,但如果不断涌入新的大图,特征分解可能不会那么有效。
2.还有一个问题是我们训练的模型最终是和图的特征向量V密切相关的。如果训练图和测试图具有非常不同的结构(节点和边的数量),这可能是一个大问题。另一方面,如果所有的情节都非常相似,那么问题就会少得多。此外,如果您在频域中使用平滑滤波器,例如上面讨论的样条曲线,则滤波器将更加局部化,并且在适应新图时似乎不会出现明显的问题。然而,这些模型仍然非常有限。
那么切比雪夫图的卷积与我们之前所说的一切有什么关系呢?
毕竟它可以同时解决这两个问题。
这意味着避免了计算上昂贵的特征分解,并且滤波器不再“应用于”特征向量(尽管它们仍然是特征值的函数)。此外,它还有一个非常有用的参数,通常表示为K。这直观上类似于上面等式(4)中的K,并确定滤波器的位置。简而言之,如果K=1,我们只将节点特征X 馈送到GNN 中。如果K=2,则喂入X和X。如果K=3,则喂X ,下面是我的代码。如需更多分析,请参阅(Knyazev 等人,NeurIPS-W,2018)。
由于邻接矩阵的幂特性,做2实际上减少了2跳邻居数据(或者任何与归一化方法相关的数据),如图所示,类似于X中的任意n ) 取平均值。下图中,我们对n 跳邻居数据进行平均。
图6:对于节点1(深蓝色),这是K=3 的切比雪夫卷积。带圆圈的节点表示影响节点1的特征表示的节点,[,]运算符表示特征维度上的连接。 W为3CF的尺寸权重值。
注意,为了满足切比雪夫基的正交性,假设图中不存在环,因此在矩阵的每i 行中都有乘积性质。它与矩阵X 分开提供。
如果K等于节点数N,切比雪夫卷积类似于谱卷积,滤波器的感受野是整个图。然而,对于卷积网络,我们不希望滤波器与输入图像一样大,原因我们之前讨论过,所以K 的值实际上会很小。
根据我的经验,这是最强大的GNN 之一,并且在许多与图相关的任务中取得了良好的结果。主要缺点是向前或向后时需要循环K(切比雪夫多项式是递归的,因此无法并行化)。这会减慢模型的速度。
如上所述,您不需要训练滤波器,只需训练系数即可。这次是切比雪夫多项式的系数。
图7:切比雪夫基用于近似谱域中的卷积。
要生成切比雪夫基,您可以使用以下Python 代码。
生成样条线和切比雪夫基的完整代码可以在我的github 存储库中找到。
为了说明切比雪夫滤波器在不规则网格上的表现,我们遵循Bruna 等人的实验。同样,以与我们显示拉普拉斯图的特征向量相同的方式,从MNIST 网格中采样了400 个随机点,并在这400 个位置采样的MNIST 图像上训练了切比雪夫图卷积模型。(所有图像都使用相同的不规则规则)网格)。K=1 和K=20 的滤波器之一如下所示。
图8:另一个切比雪夫滤波器(左侧k=3,右侧K=20)在MNIST 上进行训练,并应用于400 个点的不规则网格内的不同位置(显示为红色像素)。与标准ConvNet 滤波器相比,GNN 滤波器根据其所应用的节点而具有不同的形状。这是因为每个节点具有不同的邻域结构。
2. GCNKipf 和Welling,ICLR,2017 年(https://arxiv.org/abs/1609.02907)
您可能已经注意到,增加切比雪夫卷积中的K 会相应增加可训练参数的总数。例如,如果K=2,则权重W 为2CF,而不仅仅是CF。这是因为我们将特征X 和X 连接成单个N2C 矩阵。随着训练参数的增加,模型变得更加难以训练,需要更多的数据来标记进行训练。图形数据集通常非常小。
在计算机视觉领域,MNIST 被认为是一个小数据集,因为图像只有2828 维度,只有60k 训练图像,但对于图网络来说,每个图有N=784 个节点;如果有60k 个节点,MNIST 就非常大了。许多训练图。与计算机视觉任务相比,许多图数据集只有大约20-100 个节点和200-1000 个训练样本。这些图可能代表特定的小分子,标记化学或生物数据通常比标记图像更昂贵。
因此,训练切比雪夫卷积模型可能会导致训练集严重过拟合(即模型的训练损失接近0,但验证或测试误差很大)。因此,Kipf 和Welling 的GCN 本质上是将节点特征X 和X 的矩阵“合并”为单个NC 矩阵。因此,该模型训练的参数是K=2 的切比雪夫卷积的两倍,但具有相同的1 跳感受野。主要技巧是通过添加I 中的单位矩阵并以某种方式对其进行归一化来向图中添加自循环。也就是说,计算每i 行的矩阵乘积数据的特征。
由于其轻量级、良好的性能以及对更大图的可扩展性,该模型对于许多应用程序来说似乎是一个很好的标准基线选择。
1.GCN和Chebyshev层的区别GCN和Chebyshev卷积如下
上面的代码遵循与比较经典NN 和GNN 的教程第一部分相同的结构。 GCN 和切比雪夫卷积的主要步骤之一是计算重新缩放的拉普拉斯图L。重新缩放的目的是让特征值保持在[-1,1]范围内,以方便训练(这实际上不是一个非常重要的步骤,因为权重可以在训练过程中进行调整,有可能)。 GCN 通过在计算拉普拉斯算子之前添加单位矩阵来向图中添加自循环。两种方法之间的主要区别在于切比雪夫卷积在K 上递归循环以捕获K 跳附近的特征。您可以将此类GCN 和Chebyshev 层与非线性层叠加以构建图神经网络。
让我在此打断频谱讨论,解释一下另外两种令人兴奋的: 方法背后的总体思路。 Simonovsky 和Komodakis,边缘条件滤波器,CVPR,2017 (https://arxiv.org/abs /1704.02901) 和Monti 等人的MoNet。CVPR,2017 (https://arxiv.org/abs/1611.08402),共享类似的概念。
4. 边缘条件滤波器Simonovsky 和Komodakis,CVPR,2017 (https://arxiv.org/abs/1704.02901)
众所周知,ConvNet 通过优化交叉熵等损失来学习权重(过滤器)。类似地,用GNN 学习W。想象一下,我们有另一个可以预测权重的网络,而不是学习这些权重。因此,在训练过程中,我们学习这个辅助网络的权重。该辅助网络将图像或图形作为输入,并返回工作权重W() 作为输出。这个想法基于动态过滤网络(Brabandere 等人,NIP,2016)。这里,“动态”意味着滤波器W 根据输入而变化,并且在训练后不再像标准模型滤波器那样固定(或静态)。
图9:使用辅助“滤波器生成网络”F 预测主网络的边特定权重。 X是输入节点特征,X是输出特征。该图显示了节点1(黄色)的“动态卷积”的一次迭代。标准GNN 通常只是对与节点1 相邻的节点(节点2、3、4、5)的特征进行平均(或求和),这与各向同性滤波器( 将是常数向量)是等效的。相比之下,该模型还具有各向异性滤波器,因为它可以根据边缘标签L 预测节点1 与其所有邻居之间的不同边缘值。因此,特征X(1) 被计算为相邻数据的加权平均值。特征。插图来自(Simovsky 和Komodakis,CVPR,2017)。
这是一种非常常见的卷积格式,不仅可以轻松应用于图像,还可以应用于图形和点云,就像我们在CVPR 论文中所做的那样,并取得了很好的效果。然而,随着传统网格约束的放松和解决方案范围的极大扩展,没有“免费午餐”,训练此类模型极其困难。
对于具有许多边和更深卷积的大型图尤其如此,通常具有数百个通道(特征数量,C)。因此,您最终可能会为每个输入生成数千个数字。标准卷积网络在这方面表现非常好。它不会浪费模型的能力来预测这些权重,而是直接强制过滤器对所有输入都相同。然而,这个前提条件也限制了ConvNet,因此它不能直接应用于图或点云。因此,一如既往,对于给定任务,需要在灵活性和性能之间进行权衡。
如果您需要将模型应用于MNIST 等图像,边缘条件模型可以学习预测各向异性滤波器,例如方向相关滤波器和边缘检测器。与本教程第一部分中讨论的高斯滤波器相比,这些滤波器更擅长捕获图像中的特定模式,例如数字笔画。
图10:在MNIST 上训练的卷积滤波器,以低分辨率(左)和高分辨率(右)采样。插图来自(Simovsky 和Komodakis,CVPR,2017)。
我想再次强调,如果你有一个带有辅助网络的复杂模型,那么从某种意义上说,这是一个先有鸡还是先有蛋的问题。为了解决这个问题,其中一个网络(辅助或主要)必须接收非常强的信号,使其能够秘密监视另一个网络。在我们的BMVC 论文中,与Simonovsky 和Komodakis 的工作类似,我们向边缘生成网络添加了额外的约束以促进训练。我们将在以后的文章中更详细地讨论我们的研究活动。
5. MoNetMonti 等人,CVPR,2017 (https://arxiv.org/abs/1688.08420)
MoNet 与本文讨论的其他工作不同,因为它假设了节点坐标的概念,使其更适合3D 网格分析和图像/视频推理等几何任务。这类似于Simonovsky 和Komodakis 的边缘条件过滤器。这是因为他们还引入了一个可学习的辅助函数( , ) 可以预测权重( , )。
不同之处在于这些权重取决于节点的极坐标(角度和半径)。高斯均值和方差可用于使用可训练参数w 来约束该函数,因此无需学习NN 矩阵。然而,它只学习N 个固定大小的向量(均值和方差),而不管图的大小。对于ConvNet来说,这意味着每个过滤器有两个值(高斯均值和方差),而不是学习33、55或1111维度中的9、25或121个值。是一样的仅作为学习应用每个过滤器。虽然这种参数化大大减少了ConvNet中的参数数量,但它严重限制了滤波器捕捉图像特征的能力。
蒙蒂等人。高斯均值和方差的训练过程以及节点坐标的变换与将它们拟合到高斯混合模型类似。如果你希望你的过滤器更加全局化,这个模型需要大量的计算训练,但对于视觉任务来说是一个不错的选择(请参阅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=previewsign=rqhxr4R4oqeDpqKqg3V6koDLo5OBn4-WhIbMoQ
原文链接:https://towardsdatascience.com/tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-2-be6d71d70f49
【自范性和各向异性,泥岩的各向异性参数】相关文章: