图神经网络的模型操作与带来的挑战之探讨

图神经网络的一个最重要的分支是图卷积神经网络（Graph Convolutional Network，GCN）。一般而言，图卷积神经网络采用邻域聚合方案，通过迭代聚合并变换其邻域节点的特征向量来为每个节点计算新的特征向量。图卷积神经网络的Aggregate操作为每个节点进行邻居节点的遍历，聚合邻居节点的特征向量。Combine操作利用同一个多层感知机模型对所有节点的特征向量进行变换。图神经网络包含两个主要的执行阶段，第一个阶段是图遍历阶段，主要执行Aggregate操作；第二个阶段是神经网络变换阶段，主要执行Combine操作。

除了上述的两种主要操作，图神经网络还包含Sample、Pool和Readout这3种操作。Sample操作用于降低计算复杂度，从邻居节点集合中抽取一个子集作为新邻居节点集合；Pool操作用于将原始图转换为更小的图；Readout操作在最后一次迭代中进一步聚合所有节点的特征向量以获得整个图的表征向量。

虽然图神经网络具有强大的认知能力，但其独特的执行行为特征为传统处理器结构带来了新的挑战。为了明确这些新挑战，首先在执行行为上将图神经网络算法与图计算算法（即PageRank等）和神经网络算法进行比较，以指出图神经网络独特的执行行为。从计算和访存两方面对图神经网络的两个主要执行阶段可以进行执行行为的特征分析，以指出图神经网络具有混合的执行行为特征。最后，基于图神经网络的执行行为特征，可以给出高效执行图神经网络的处理器结构设计需求，以及指出现有结构设计无法高效满足这些设计需求的原因。

图神经网络算法、图计算算法以及神经网络算法的执行行为比较如下：

1. 图计算算法和图神经网络算法的相同点在于它们的每一次迭代或者层的执行都包含了遍历邻居和更新节点属性两个阶段：（1）无论是图计算算 法，还是新兴的图神经网络算法都通过遍历边收集1-hop或者多hop邻居节点的信息作为中间结果。（2）中间结果会被用于更新节点属性。

2. 图计算算法和图神经网络算法的不同有3点：（1）在图计算算法中，节点属性一般只有单个元素，且在计算过程中只有值在变而元素数量不变；然而在图神经网络算法中，节点属性一般是一个特征向量或者是更高维的张量数据，元素数量在数千个以 上。除此之外，不同图数据集的维度和元素个数也不尽相同，并且在执行过程中，由于神经网络的变换，不仅节点的属性值在变，元素个数和维度也在变化。（2）图计算算法收集的邻居信息是单个元素，并对每个元素进行归约操作；而图神经网络算法收集的是向量或者更高维的数据，对每个元素进行element-wise的归约操作。（3）图计算算法的更新操作较为简单，一般是累加或者比较等操作，所以计算访存比低；然而在图神经网络算法中，每个节点的属性更新操作是进行神经网络变换，具有非常 高的计算访存比。

3. 传统神经网络算法与图神经网络算法的相同点在于两者都有训练和推断的过程。训练过程是对模型中使用的参数进行训练，利用测试样本不断对参数进行更新和校准，以获得更高的推断精度。推断过程是在获得模型的所有校准参数之后，将模型用于对新数据进行推断，以获得新数据的推断结果。

4. 传统神经网络与图神经网络的不同之处有如下两点：（1）传统神经网络的输入数据一般是大小规则且结构规则的图片或者序列数据等，而图神经网络算法的输入数据通常为结构不规则的图数据。（2）传统神经网络只有使用批处理（batch）技术之 后才能将神经网络的参数共享于多个样本，然而图神经网络算法天然地将同一个神经网络模型应用于所有节点的特征向量变换中。在执行过程中，模型参数具有非常高的复用率。

图神经网络的两个主要执行阶段的执行行为特征分析如下所述。图遍历阶段的执行行为极其 不规则，即计算图不规则且访存不规则，主要受访存约束。而神经网络变换阶段的执行行为非常规则，即计算图规则且访存规则，主要受计算约束。综上所述，混合的执行行为存在于图神经网络中。图神经网络的混合执行行为导致现有通用处理器芯片在计算和访存两个方面都面临巨大挑战。在计算方面，计算单元面临着负载不均衡、密集读改写冲突、如何高效挖掘潜在的并行性和复用高 复用率数据等问题；在访存方面，不规则的粗粒度访存造成了节点特征向量在缓存（cache）与动态随机存取存储器（DRAM）之间的频繁替换，导致缓存的缺失率非常高。

图神经网络执行行为对处理器的高效执行提出了更高的结构设计需求。首先，高效执行图遍历阶段需要应对负载不均衡、不规则访存等问题；另一方面，高效执行神经网络变换阶段需要利用神经网络的规则执行行为，以提高执行效率。其次，需要挖掘节点内的高度并行性，充分复用节点间高度可重用的参数数据。最后，为了达到更高的性能和能效，需要有效地融合图遍历阶段和神经网络变换阶段的执行。

不幸的是，现有的处理器芯片设计无法完全满足这些需求，因而导致执行低效。对于CPU而言，图遍历阶段的不规则访存使图神经网络无法从当前的缓存层次结构和数据预取技术中受益，并且很难有效地在计算单元之间重用高度可重用的参数数据。GPU从本质上是为加速具有规则执行行为且计算密集型的应用而设计的，因此处理具有不规则计算图和不规则内存访问的图遍历阶段时极为低效。此外，GPU处理具有大量参数共享的神经网络变换阶段，会导致昂贵的数据复制和线程同步开销。CPU和GPU都难以融合图遍历阶段和神经网络变换阶段的执行。为了利用硬件优化函数，当前的图神经网络编程框架通常采用粗粒度的执行方式，即直接执行矩阵乘法等硬件优化函数。粗粒度的执行方式导 致图遍历阶段和神经网络变换阶段需要轮流执行，因此错过了跨阶段的优化改进。与通用处理器相比，为图计算算法或深度学习算法量身定制的加速芯片 可显著提高图计算算法和深度学习算法的性能并节省能耗。然而，鉴于以下原因，上述两类加速芯片在执行图神经网络时仍效率低下：（1）它们通常仅针对应对不规则执行行为或利用规则执行行为的单一方面进行芯片定制优化，从而提高执行效率；而图神经网络加速芯片则需要两者兼备。（2）它们无法挖掘图神经网络展现的新并行性和数据重用，难以进一步提高性能。（3）独立分开的加速芯片使它们难以实现两个阶段的融合执行。