图神经网络(GNN)和神经网络的关系

1 介绍

深度神经网络由神经元组成，组织成层并相互连接，通过计算图捕捉其架构，其中神经元表示为节点，有向边连接不同层神经元。神经网络性能取决于其架构，但目前对神经网络精度与底层图结构之间的关系尚缺乏系统理解。这直接影响到设计更高效和更精确的架构，并可告知新的硬件架构设计。建立神经网络架构与它精度之间的关系具有重要科学和实际意义，但尚不清楚如何将神经网络映射到图。计算图表示有许多局限性，如缺乏通用性、与生物学/神经科学脱节等。

斯坦福 Jure Leskovec 和 Facebook 的何凯明等人工作开发了一种将神经网络表示为图的新方法，称为关系图，关注消息交换，而不仅仅是数据流向。这种表示可以表示许多类型的神经网络层，同时摆脱计算图的许多约束。

该工作设计了一个名为WS-flex的图生成器，能够系统地探索神经网络的设计空间，如图1。并使用标准的图像分类数据集CIFAR-10和ImageNet，对神经网络的架构如何影响其预测性能进行了系统性的研究，并得出了几个重要的经验观察结果：

（1）关系图的特定点能够显著提升神经网络的预测性能；

（2）神经网络的性能表现与其关系图的聚类系数和平均路径长度存在密切关联，呈现平滑的函数关系；

（3）本文的发现适用于多种不同的任务和数据集，具有广泛的适用性；

（4）能够有效地识别出最佳点；

（5）表现最佳的神经网络在图结构上与真实的生物神经网络呈现出高度的相似性。

这些结果对于设计神经网络结构，推进深度学习科学，提高对神经网络的理解具有重要的启示意义。

图1 我们的方法概述。(a)神经网络的一层可以视为一个关系图，我们在其中连接交换消息的节点。(b)神经网络层和关系图的更多示例。(c)我们根据关系图的图度量（包括平均路径长度和聚类系数）探索关系图的设计空间，其中完整的图对应于全连接层。(d)我们将这些关系图转化为神经网络，并研究它们的预测性能如何取决于其相应关系图的图测量。

2 作为关系图的神经网络

本节介绍了关系图表示的概念及其实例化，展示了如何用统一的框架捕捉不同的神经网络架构。在深度学习背景下使用图语言有助于将两个世界结合，并为研究奠定了基础。

2.1 通过图进行消息交换

本文定义了神经网络图G=(V,E)，其中V为节点集，E为边集。假设节点v具有特征向量xv。当图G与神经元消息交换相关时，称为关系图。消息交换由消息函数和聚合函数定义，每轮消息交换中，每个节点向邻居发送消息，并聚合来自邻居的传入消息。每个消息在每个边缘通过消息函数f(·)转换，然后在每个节点通过聚合函数AGG(·)聚合。假设进行R轮消息交换，则节点v的第r轮消息交换可描述为

其中u，v是图G中的节点，N(v)是节点v的邻域，包含自边。x(v)是输入节点特征，x(v+1)是输出节点特征。此方法可在任何图G上定义，本文仅考虑无向图。

公式1定义了消息交换，下文讨论如何将其应用于不同神经架构。表1总结了各种实例化，图2展示了4层65维MLP的具体示例。

表1 用关系图语言表达的多种神经架构。这些架构通常被实现为完整的关系图，而我们系统地探索这些架构的更多图结构

图2 将4节点关系图转换为4层65维MLP的示例。我们突出显示节点x1的消息交换。使用xi、fi(·)、AGG(·)和R的不同定义（表1中定义的定义），关系图可以转换为不同的神经架构。

2.2 作为关系图的固定宽度MLP

多层感知器(MLP)由计算单元(神经元)层组成，每个神经元对标量输入和输出执行加权求和，然后进行非线性处理。假设MLP的第r层将x(r)作为输入，x(r+1)作为输出，则神经元计算：

其中w(r)ij是可训练权重，x(r)j是输入x(r)的第j维，x(r+1)i是输出x(r+1)的第i维，σ是非线性。

在特殊条件下，所有层x(r)的输入和输出具有相同特征维度。此时，全连接、固定宽度的MLP层可以用关系图表示，每个节点xi连接所有其他节点。全连接固定宽度MLP层具有特殊消息交换定义，消息函数为fi(xj)=wijxi，聚合函数为AGG({xi})=σ(P{xi})。

上述讨论表明，固定宽度的MLP可视为具有特殊消息交换功能的完整关系图，是更通用模型族下的特殊情况，其中消息函数、聚合函数和关系图结构可变。

这种见解将固定宽度MLP推广到任何一般关系图G，基于公式1中消息交换的一般定义：

其中i，j是G中的节点N(i)由G定义。

2.3 作为关系图的通用神经网络

本节讨论了如何将关系图推广到通用神经网络，特别是可变宽度MLP。在CNN中，层宽度（特征通道数）会变化，因此需要将节点特征从标量x(r)i推广到向量x(r)i，由MLP的输入x(r)的某些维度组成，并将消息函数fi(·)从标量乘法推广到矩阵乘法：

其中，W(r)ij是权重矩阵，允许不同层中同一节点和同一层中不同节点具有不同维度，导致神经网络灵活图形表示。例如，用4节点关系图表示2层神经网络，第一层宽度5，第二层宽度9，则4个节点在第一层的尺寸为{2,1,1,1}，在第二层的尺寸为{3,2,2,2}。

关系图最大节点数受神经网络中最窄层宽度限制，每个节点的特征维度至少为1。

作为关系图的CNN。将节点特征从向量x(r)i推广到由输入图像的一些通道组成的张量X(r)i。然后用卷积算子概括消息交换定义，具体来说：

其中∗是卷积算子，W(r)ij是卷积滤波器。在这个定义下，广泛使用的密集卷积再次被表示为完整图。

现代神经架构作为关系图。我们使用关系图来描绘复杂设计的现代神经架构，例如ResNet和具有瓶颈变换的神经网络。ResNet的残差连接被保留，瓶颈变换的神经网络则交替应用3×3和1×1卷积的消息交换。在计算效率高的设置中，可分离卷积（交替应用3×3深度卷积和1×1卷积）被广泛使用。

关系图是神经网络的通用表示，通过定义节点特征和消息交换，可以表示各种神经架构，如表1所示。

3 探索关系图

本节探讨如何设计并探索神经网络图结构与预测性能的关系，通过三个关键部分：(1)图形测量以表征图结构属性；(2)图形生成器以生成不同图形；(3)控制计算预算的方法，以归因于不同神经网络性能的差异。

3.1 图形度量的选择

鉴于图结构的复杂性，图度量通常用于表征图。本文主要介绍全局的平均路径长度和局部的聚类系数这两种度量。这两种度量在神经科学和网络科学中广泛应用。平均路径长度是测量任意一对节点之间的平均最短路径距离；聚类系数则是测量给定节点的邻居中的节点之间的边的比例，并平均到所有节点上。附录中还有其他图形度量可供分析。

3.2 图生成器的设计

我们的目标是使用图形生成器生成多样化图形，覆盖大范围图形度量。然而，这需要精心设计生成器，因为经典图生成器只能生成有限类别的图，而基于学习的图生成器旨在模仿给定示例图。

现有图形生成器的局限性。我们研究了ER、WS、BA、Harary、环形图和完整图等经典图生成器，发现它们生成的图在平均路径长度和聚类系数的空间中具有有限的跨度，这表明现有图生成器存在局限性，如图3。

图3 不同图形生成器生成的图形。所提出的图形生成器WS-flex可以覆盖更大的图形设计空间区域。WS(WattsStrogatz)、BA(Barab´asi-Albert)、ER(Erd˝os-R´enyi)。

WS-flex图形生成器。WS-flex图生成器能生成广泛图度量覆盖的图，几乎涵盖所有经典随机生成器生成的图，如图3。WS-flex通过放宽WS模型中节点具有相同度数的约束实现。WS-flex由节点n、平均度k和重新布线概率p参数化，边的数量为e=bn*k/2c。生成器首先创建环形图，然后随机选择节点并连接到最近相邻节点，最后以概率p随机重新连接边。WS-flex在聚类系数和平均路径长度空间内平滑采样，对3942个图进行实验，如图1(c)。

3.3 控制计算预算

为了比较不同图转换神经网络的性能差异，我们确保所有网络具有大致相同的复杂性，使用FLOPS作为衡量标准。首先计算基线网络实例化的FLOPS作为参考复杂度，然后通过调整神经网络的宽度以匹配参考复杂度，而无需更改关系图结构。

4 实验设置

我们研究了CIFAR-10和ImageNet数据集上MLP的图结构，CIFAR-10包含50K训练图像和10K验证图像，ImageNet则由1K图像类、128万个训练图像和50K个验证图像组成。

4.1 基础架构

对于CIFAR-10实验，我们使用一个具有512个隐藏单元的5层MLP，其输入为(32×32×3)图像的3072维展平向量，输出为10维预测。每一层都配备了ReLU非线性层和BatchNorm层。我们采用余弦学习率计划，初始学习率为0.1，退火至0，不重新启动，批量大小为128，训练了200个epoch。我们使用5个不同的随机种子训练所有MLP模型，并报告平均结果。

在ImageNet实验中，我们使用了三种ResNet系列架构，包括ResNet-34、ResNet-34-sep和ResNet-50，以及EfficientNet-B0和8层CNN。所有模型都使用余弦学习率计划进行100个时期的训练，初始学习率为0.1。在NVIDIA Tesla V100 GPU上，训练MLP模型需要5分钟，训练ImageNet上的ResNet模型需要一天。

4.2 使用关系图进行探索

我们使用表1中的定义将采样关系图实例化为神经网络，替换所有密集层。保持输入和输出层不变，并保留其他设计。然后，我们匹配所有模型的参考计算复杂度，如第3.3节所述。

在CIFAR-10 MLP实验中，我们研究了64个节点的3942个采样关系图，如第3.2节所述。在ImageNet实验中，由于计算成本较高，我们从3942个图中均匀地子采样了52个图。对于EfficientNet-B0，我们重新采样了48个具有16个节点的关系图。

5 结果

本节总结了实验结果，包括不同任务和架构上的采样关系图top-1错误，以及每个采样图的图度量（平均路径长度L和聚类系数C）。结果以图形测量与预测性能的热图形式呈现（图4(a)(c)(f)）。

图4 关键结果。所有实验的计算预算都受到严格控制。每个可视化结果都是至少3个随机种子的平均值。将C=1且L=1（右下角）的完整图视为基线。(a)(c)图测量与神经网络性能。最好的图表明显优于基线完整图表。(b)(d)单图测量与神经网络性能。落在给定范围内的关系图显示为灰点。整体平滑函数由蓝色回归线表示。(e)跨架构的一致性。显示了同一组52个关系图在转换为不同神经架构时的性能相关性。(f)所有实验的总结。在不同的设置中，最佳关系图（红叉）始终优于基线完整图。此外，我们突出显示了“最佳点”（红色矩形区域），其中关系图在统计上并不比最佳关系图（带有红叉的区域）差。CIFAR-10上5层MLP的bin值是C和L落入给定bin的所有关系图的平均值。

5.1 顶级神经网络的最佳选择

热图（图4(f)）显示，某些图结构可超越完整图基线，提升性能。最佳关系图在CIFAR-10和ImageNet上的top-1误差分别比完整图基线高1.4%和0.5%-1.2%。最佳图聚集在C和L定义的空间中的最佳位置（图4(f)中的红色矩形）。通过下采样、聚合、确定平均性能最佳bin、单尾t检验和记录不明显差的bin，确定最佳点。对于CIFAR-10上的5层MLP，最佳点是Cε[0.10,0.50]，Lε[1.82,2.75]。

5.2 神经网络性能作为图测量的平滑函数

图4(f)显示，神经网络预测性能与关系图聚类系数和平均路径长度呈平滑函数关系。在图4(b)(d)中，固定一个图测量值，根据其他测量值可视化网络性能。使用二次多项式回归可视化总体趋势，发现聚类系数和平均路径长度均显示神经网络性能呈平滑U形相关性。

5.3 跨架构的一致性

关系图定义了跨神经架构的共享设计空间，具有某些图度量的关系图可能始终表现良好，无论其如何实例化。

质量的一致性。图4(f)可以观察到，不同架构的最佳点大致一致，跨架构的一致最佳点为C∈[0.43,0.50],L∈[1.82,2.28]，图4(b)(d)中测量值与神经网络性能之间的U形趋势一致。

定量一致性。为了进一步量化跨任务和架构的一致性，在图4(f)的热图中选择了52个bin，其中bin值表示其图度量落入该bin范围的关系图的平均性能。观察到，具有某些图度量的关系图的性能在不同的任务和架构之间相关。

5.4 快速识别最佳位置

我们提出了一种方法，通过减少样本图数量和训练周期数，以更低的计算成本识别最佳点。

需要多少张图表？CIFAR-10上5层MLP的热图（图4(f)）分析显示，3942个图形样本计算得出的52个bin热图，仅使用52个样本计算的bin值与使用完整3942个图形样本计算的bin值具有高达0.90的Pearson相关性，如图5（左）所示。这表明，进行类似分析所需的图表要少得多。

图5 快速识别最佳位置。左：使用较少的关系图样本和使用所有3942个图确定的最佳点之间的相关性。右图：在中间训练时期和最终时期（100个时期）确定的最佳点之间的相关性。

需要多少个训练周期？我们以ImageNet上的ResNet-34为例，计算了部分训练模型的验证top-1误差与训练了100个epoch的模型的验证top-1误差之间的相关性，如图5（右）所示。结果发现，在3个epoch后训练的模型已经具有很高的相关性(0.93)。这一发现表明，良好的关系图在早期的训练epoch就表现良好，因此可以大大降低确定关系图是否有前途的计算成本。

5.5 网络科学和神经科学的联系

网络科学。我们测量的平均路径长度反映了信息在网络中的交换程度，这与我们对关系图的定义一致。图4(b)(d)中的U形相关性可能表明消息交换效率和学习分布式表示能力之间的权衡。

神经科学。我们研究发现，表现最佳的关系图与生物神经网络惊人地相似，如表2和图6所示。顶级人工神经网络的图度量与生物神经网络高度相似，且关系图表示能将生物神经网络转化为5层MLP，优于基线完整图。我们的方法为网络科学、神经科学和深度学习的跨学科研究开辟了新可能性。

表2 顶级人工神经网络可以类似于生物神经网络

图6 生物（左）和人工（右）神经网络图结构的可视化。

6 相关工作

神经网络连接。神经网络连接模式设计主要关注宏观结构和微观结构。宏观结构关注跨层连接，微观结构关注层内连通性。Deep Expander Networks和RandWire分别采用扩展图和图形生成器生成结构，但未探讨图结构与网络性能的统计关系。跨通道通信网络则鼓励神经元通过消息传递进行通信，仅考虑完整的图结构。

神经架构搜索。研究在微观或宏观层面改进学习/搜索算法，以学习连接模式。NAS-Bench-101通过枚举具有约束大小的DAG定义图搜索空间。新路径是使用图生成器和图度量定义一个平滑空间，从而降低搜索成本，无需详尽搜索所有可能的连接模式。

7 讨论

神经网络的层次图结构。我们的工作重点是层级别的图结构，这是神经网络的基础。虽然探索这个领域在计算上具有挑战性，但我们希望我们的方法和发现能够推广。

高效实施。我们使用标准CUDA内核，导致性能低于基线完整图。然而，我们正在研究块稀疏内核和快速稀疏ConvNet，以缩小理论FLOPS与实际收益差距，并为新硬件架构设计提供信息。

先验与学习。我们使用关系图表示作为结构先验，将图结构硬连接到神经网络上。深度ReLU神经网络可以自动学习稀疏表示。问题是，在没有图先验的情况下，训练全连接神经网络是否会出现任何图结构。

我们对经过训练的神经网络进行“逆向工程”，研究其关系图结构。在CIFAR-10上训练全连接的5层MLP，通过特定步骤推断网络底层关系图结构。结果（图7）发现，训练收敛后提取的图不再是E-R随机图，而是朝着最佳点区域移动。这些学习到的图与作为结构强加的性能最佳图之间仍然存在差距，这可能解释了全连接的MLP性能较差的原因。

图7 先验与学习。CIFAR-10上5层MLP的结果。我们突出显示用作结构先验时表现最佳的图。此外，我们训练一个完全连接的MLP，并将学习到的权重可视化为关系图（不同的点是不同阈值下的图）。训练后学习到的图结构向“最佳点”移动，但并没有缩小差距。

我们的实验发现，在任务简单且网络容量丰富的情况下，学习图结构可以更优越。这表明研究神经网络的图结构对于理解其预测性能至关重要。我们提出了图神经网络(GNN)和通用神经架构的统一视图，将神经网络定义为图上的消息交换函数。我们指出GNN是通用神经架构的一类特殊形式，其中图结构被视为输入，而不是神经架构的一部分。我们的工作为GNN和通用神经架构设计的统一视图提供了基础，有望激发新的创新。