A Survey on Graph Neural Network

作者: 魔法少女玛格姬 | 来源:发表于2023-02-23 18:17 被阅读0次

论文地址：2209.13232.pdf (arxiv.org)
香港大学2022年发表的一篇关于GNN和Graph Transformer在视觉领域的综述。

摘要

图神经网络（GNNs）在图表示学习中获得了动力，并在许多领域推动了最新技术的发展，例如数据挖掘（如社交网络分析和推荐系统）、计算机视觉（如物体检测和点云学习）以及自然语言处理（如关系提取和序列学习）等等。随着自然语言处理和计算机视觉中Transformer的出现，图Transformer将图结构嵌入到Transformer架构中，以克服局部邻域聚合的局限性，同时避免严格的结构归纳偏差。本文从任务导向的角度全面评估了GNN和图Transformer在计算机视觉中的应用。具体来说，我们根据输入数据的模态，即2D自然图像、视频、3D数据、视觉+语言和医学图像，将它们在计算机视觉中的应用分为五类。在每个类别中，我们进一步根据一组视觉任务将应用程序分成不同的类别。这样的任务导向分类方式使我们能够检查不同基于GNN的方法如何处理每个任务以及这些方法的性能如何。基于必要的基础知识，我们提供了任务的定义和挑战，代表性方法的深入介绍以及关于洞察、限制和未来方向的讨论。

1. 引言

深度学习[1]为计算机视觉带来了许多突破，其中卷积神经网络(CNN)占据主导地位，并成为许多现代视觉系统的基本架构。特别是过去十年中，提出了许多最先进的CNN模型，如AlexNet[2]、ResNet[3]和EfficientNet[4]，在包括图像分类、目标检测、语义分割和图像处理等多种视觉问题上取得了前所未有的进展。另一方面，现有的视觉系统像人类一样采用各种输入模态，例如2D图像（例如自然和医学图像）、视频、3D数据（例如点云和网格）以及多模态输入（例如图像+文本）。
尽管基于CNN的方法在处理定义在规则网格上的输入数据（例如图像）方面表现出色，但计算机视觉界普遍认为，具有不规则拓扑结构的视觉信息对于表示学习至关重要，但尚未得到深入研究。观察到人类对于组合泛化的能力在很大程度上依赖于他们表示结构和推理关系的认知机制[5]，模仿人类的学习和决策过程可以提高视觉模型的性能。例如，在目标识别任务中，最先进的神经网络更喜欢集中注意力于感知单独的对象，而对于不同对象之间的依赖关系和交互作用关注不足。
此外，与具有固有边缘连接和节点概念的自然图形数据（例如社交网络和生物蛋白质-蛋白质网络）相比，从规则网格数据（例如图像和时间信号）构建图形（例如关系图）的基本方法不足，领域知识对于成功至关重要。另一方面，某些视觉数据格式，如点云和网格，自然上并没有定义在笛卡尔网格上，并涉及复杂的关系信息。从这个意义上说，无论是规则的还是不规则的视觉数据格式，都将受益于探索拓扑结构和关系，特别是对于挑战性的场景，如理解复杂场景、从有限的经验中学习和跨领域传递知识。
近年来，GNN [6] 在深度学习的最新进展的支持下，在建模图结构方面表现出了开创性的性能。在计算机视觉领域，当前大部分与GNN相关的研究都有以下两个目标之一：（1）混合GNN和CNN骨干，以及（2）用于表示学习的纯GNN架构。前者通常旨在改善CNN特征的长程建模能力，并适用于以前使用纯CNN架构解决的视觉任务，例如图像分类和语义分割。后者作为某些视觉数据格式的特征提取器，例如点云，并与其他方法并行发展。例如，对于以点云表示的三维形状的分类[7]，存在三种主要方法，即点式MLP方法、基于卷积的方法和基于图的方法。
尽管已经取得了丰硕的成果，但仍不存在一个系统的和及时的综述，来系统地回顾GNN在计算机视觉领域的进展。因此，我们从任务导向的角度，将本文文献综述作为GNN在计算机视觉中的完整介绍，包括（i）任务的定义和挑战，（ii）代表性方法的深入介绍，以及（iii）关于洞察和未来方向的系统讨论。具体来说，我们将GNN在计算机视觉中的应用根据输入数据的模态分为五个类别。在每个类别中，我们进一步根据它们执行的计算机视觉任务将应用程序进行分割。我们还回顾了图Transformer在视觉任务中的使用，考虑到它们在架构方面与GNN的相似性[8]，[9]。本综述的组织如图1所示。

图1：该综述总体架构

2. 背景和分类

在本节中，我们回顾了在计算机视觉中使用的GNN和图Transformer。读者可以参考几篇以前的GNN综述[10]，[11]，[12]，这些综述全面介绍了GNN的发展。此外，我们想强调，许多现有的基于GNN的视觉方法实际上使用了CNN和GNN的混合，而我们着重于GNN的一侧。

2.1. 循环GNN

GNN最初是以循环GNN的形式开发的。在这种范例下，早期的工作[6]试图通过在迭代过程中重复使用相同的权重集合，从有向无环图中提取节点表示。Scarselli等人[13]将这种神经网络扩展到处理更多类型的图，例如循环和无向图。他们通过以下方式循环更新节点的隐藏状态 $h$ ：

(1)
其中

N(v_i)

表示节点

v_i

的邻域，

f(·)

是一个前馈神经网络，

x_i∈R^d

表示

v_i

处的特征，

x_{ij}^e∈R^c

表示

v_i

和

v_j

之间边缘的特征，

t

是迭代次数。

2.2. 卷积GNN

受CNN在深度学习时代的惊人进展启发，许多研究努力致力于将卷积推广到图领域。其中，最近几年引起最大关注的是两个系列的方法（参见图2），即频谱方法[14]，[15]，[16]，[17]，[18]，[19]和空间方法[20]，[21]，[22]，[23]，[24]，[25]。

图2：两种类型的图卷积运算。

2.2.1. 频谱方法

频谱方法依赖于拉普拉斯谱来定义图卷积。对于一个无向图 $G = \{V, E\}$ ， $A$ 是邻接矩阵， $D$ 是对角度量矩阵， $D_{ii} = \sum_{j}^N A_{ij}$ 。 $L = I - D^{-1/2}AD^{-1/2}$ 表示 $G$ 的归一化拉普拉斯矩阵， $L$ 可以分解为 $L = U\Lambda U^T$ ，其中 $U$ 是特征向量矩阵， $\Lambda = \text{diag}[\lambda_1, ..., \lambda_N]$ 是特征值的对角矩阵。设 $Z \in \mathbb{R}^{N \times d}$ （ $N=|V|$ ）是 $G$ 的特征矩阵， $z \in \mathbb{R}^N$ 是 $Z$ 的一列（ $d=1$ ）。 $z$ 的图傅里叶变换被表示为 $F(z) = U^T z$ ，逆图傅里叶变换被表示为 $F^{-1}(\hat{z}) = U\hat{z}$ ，其中 $\hat{z} = F(z)$ 。然后，将 $z$ 与一个滤波器 $g \in \mathbb{R}^N$ 卷积定义为 $z _{G} g = F^{-1}(F(z) \odot F(g)) = U((U^T z) \odot (U^T g))$ ，其中 ${G}$ 是图卷积算子， $\odot$ 是阿达玛积。通过定义 $g{\theta} = \text{diag}(U^T g)$ ，它是 $\Lambda$ 的函数，我们有如下公式：

(2)
切比雪夫频谱CNN （ChebNet）[16]使用切比雪夫多项式来逼近滤波操作

g_{\theta}

。

g_{\theta} \approx \sum_{i=0}^K \theta_i T_k(\tilde{L})

，其中

\tilde{L} = 2L/\lambda_{\max} - I

是缩放后的拉普拉斯矩阵，

\lambda_{\max}

是

L

的最大特征值，

\theta_i

是可学习的参数。切比雪夫多项式可以递归地定义为

T_i(z) = 2zT_{i-1}(z) - T_{i-2}(z)

，其中

T_0(z) = 1

，

T_1(z) = z

。然后，滤波操作被表述为：

(3)
图卷积网络（GCN）[17]引入了ChebNet的一阶近似（

K=1

）。GCN迭代地从邻居节点中聚合信息，针对节点

v_i

的前向传播被表述为：

(4)
其中，

\sigma(\cdot)

是一个非线性激活函数，

\hat{A} = (\hat{a}(v_i, u_j))

表示重新归一化的邻接矩阵

A

，

W(l)

是第

l

层的可学习的转换矩阵。GCN还可以从空间视角解释 [12]。

2.2.2. 空间方法

GraphSAGE [22] 是一种通用的归纳框架，它通过对固定数量的本地邻居节点的隐藏状态进行采样和聚合来更新节点状态。形式上，它在空间域中执行图卷积：

(5)
其中，

N_s(v_i)

是从全局邻域

N(v_i)

中采样的节点子集，

\oplus

是连接操作符。如[22]所建议的，聚合函数

Aggregator_l

可以是平均聚合器、LSTM聚合器或池化聚合器。
图注意力网络（GAT）[23]引入了一个自注意机制，用于学习连接节点之间的动态权重。它通过关注邻居节点来更新节点的隐藏状态：

(6)
其中，

\alpha_{ij}

是成对的注意权重，

a

是可学习参数的向量。为了增加模型的容量并使自注意的过程稳定，GAT在实践中采用了多头自注意。
Regenerate response

2.2.3. New GNN Techniques

更深层的GNN。一些最近的工作[26]，[27]，[28]专注于构建深层GCN用于各种基本的图导向任务，例如节点预测和链接预测。DeepGCNs [27]介绍了在CNN中常用的概念——残差连接、密集连接和扩张卷积——来使GCN与CNN一样深入。通过这样做，他们可以为点云语义分割实现一个56层的GCN。Rong等人[28]提出了DropEdge训练策略，以缓解深层GCN的过拟合和平滑问题。从技术上讲，DropEdge在每次训练迭代中随机删除输入图的某些比例的边缘。此外，Li等人[29]系统地研究了可逆连接、分组卷积、权重绑定和平衡模型对提高GNN的内存和参数效率的影响，实证地揭示了将可逆连接与深层网络结构相结合可以实现极深和宽的GNN的训练（每个有80个通道的1001层和每个有224个通道的448层）。

图池化。图池化是现代GNN体系结构中的关键操作。受传统基于CNN的池化方法的启发，大多数方法将图池化作为聚类分配问题来形式化，将规则网格中的局部块的想法扩展到图形中。Defferrard等人[16]使用图割算法产生预定义的子图来实现图池化。Ying等人[30]提出了一个可微的图池化模块，名为DIFFPOOL，它可以生成图的分层表示，并可以与各种GNN体系结构以端到端的方式组合使用。Mao等人[31]引入了EigenPooling，它将节点特征和局部结构结合起来，以获得更好的分配矩阵。Gao等人[32]提出了一种称为图U-Net的U形体系结构，用于实现GNN的池化和上采样操作。

Vision GNN。最近，Han等人[33]提出了一种名为Vision GNN（ViG）的架构，用于将图像表示为图，旨在学习下游视觉任务的图级特征。ViG首先将输入图像分成一组具有规则形状的图块，并将每个图块视为图节点。接下来，使用每个节点的K个最近邻构建图边。然后，在每个节点处执行多头图卷积和位置编码，以联合学习拓扑结构和节点特征，并使用前馈网络（FFN）来减轻节点特征的过度平滑并增强特征转换能力。所提出的ViG在识别和检测基准测试中取得了竞争性的结果。例如，在ImageNet分类任务上，ViG的top-1准确率比DeiT高1.7％，在MSCOCO目标检测任务中，ViG的mAP比Swin-T高0.3％。

2.3. Graph Transformers for 3D Data

Point Transformer [34] 设计了一个用于点云分析的局部向量自注意力机制。相比之下，相关工作Point Cloud Transformer [35]采用了全局注意力。Point Transformer中每个Transformer块中的局部向量自注意力操作定义为：

(7)
其中

W_Q

、

W_K

、

W_V

是用于计算查询、键和值的共享参数矩阵，

\odot

表示按元素相乘，

\delta

是位置编码函数，

\gamma

是非线性映射函数（例如 MLP），

\rho

是归一化函数（例如 softmax）。最近，Fast Point Transformer [36] 引入了轻量级的局部自注意力架构和体素哈希，以显著提高效率。Stratified Transformer [37] 采样远离的点作为额外的键以扩大感受野，从而建模长距离依赖关系。Point Transformer V2 [38] 引入了分组向量注意力、改进的位置编码和基于分区的池化以增强效率。
Mesh Graphormer [39] 开发了一种用于从图像重建网格的图形Transformer。它分别利用图卷积和自注意力机制来学习邻域内的局部交互和非局部关系。每个Graphormer编码器块由五个组件组成，即一个Layer Norm、一个多头自注意力（MHSA）模块、一个图形残差块、一个第二个Layer Norm和一个MLP。具体而言，具有P个头的MHSA模块接受输入序列

H = {hi} ∈ Rn×d

，其中

i ∈ {1, 2, · · · , n}

表示

n

个标记，并为每个标记输出

{h_p^i}

，其中

p ∈ {1, 2, · · · , P}

是头索引。每个

h_p&i

计算如下：

A Survey on Graph Neural Network

摘要

1. 引言

2. 背景和分类

2.1. 循环GNN

2.2. 卷积GNN

2.2.1. 频谱方法

2.2.2. 空间方法

2.2.3. New GNN Techniques

2.3. Graph Transformers for 3D Data

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读