摘要

本文是对两位机器学习领军人物的新作“Graph Structure of Neural Networks”[1]的解析。该论文从神经网络连接关系的视角重新定义了一种图结构来表达神经网络模型，并从图结构本身的属性来分析什么样的神经网络模型会具有好的预测性能。

本研究由相关领域的顶尖学者发起，并非传统意义的DNN新方法研究，而是探索了神经网络性能分析的新方向。几位作者开创性地提出用图结构(graph structure)而非计算结构(computation structure)来分析神经网络的性能。这项工作可以说是开拓了一个新的研究方向，可能会对DNN的设计、评估、结构优化与提升性能带来一些全新的思路。它对于DNN结构探索、自动DNN构建等工作也将会起到促进作用。

我们从这项研究本身的内容和所涉及的相关图理论背景进行了深入理解。因篇幅较长，将介绍分为两部分：（1）对文章内容的理解；（2）结合图理论背景知识进一步理解文章的主要概念及重要意义。本篇是第一部分。
 

1 介绍

通过探索不同网络结构及性能来得到最优的神经网络模型是目前机器学习的重要探索方向。主流的思路是用大算力暴力探索不同网络结构组合来达到目标。这对计算资源提出了巨大的挑战。与这种归纳的方法不同，基于一定理论通过推演得到最优的模型设计可以降低计算的需求。

众所周知，神经网络可以用计算图来表示，其中神经元为节点，层与层之间的神经元有向连接为边。同时许多研究也证实神经网络的性能与其结构相关。很自然，研究者会联想到更进一步的问题：是否存在优化网络性能的结构特征？是否可以通过网络结构判断其性能？回答这些问题，则需要进一步系统性研究神经网络性能与其内含图结构关系。

ICML2020收录了一篇有趣的文章“Graph Structure of Neural Networks”[1]，由Kaiming He和Jure Leskovec等合作完成。二位分别是机器视觉与图网络领域的领军人物。文章尝试用图结构而不是传统的计算架构来分析上述问题，即：神经网络的结构与其性能的关系如何？根据提出的图分析方法，作者进一步分析了好的模型应该具有什么样的结构特征。

文[1]思路新颖，已经有同学对该文做了初步的介绍[2]。我们结合作者提供的开源代码，从文章本身的内容和所涉及的相关图理论背景进行了深入理解。介绍分为两部分：本篇主要是对文章的思路、实现及结论进行理解。在下一篇中，我们将针对文章的几个重要概念深入分析。

2 用图结构来表达神经网络

如前述，神经网络天然可以看作是一个图结构，但目前缺乏一个有效的方法实现神经网络到图结构间的映射。而通常用于神经网络表达的计算图是有向无环图，这限制了图理论在神经网络结构分析中的应用。

针对现有计算图表达的缺点，本文作者提出了"关系图"(relational graph)的概念来表达层间组合神经元的互动，并设计了一种图产生器将各类神经网络转换为关系图，进而系统性研究了神经网络结构与性能的关系。这篇文章直接运用了许多图领域的知识，对于专注神经网络的人来说，需要了解一些Graph理论背景。

关系图是神经网络的一种表达，它代表神经网络模型在图结构上的特性。与计算图类似，关系图也包括多个节点。但不同的是，关系图中的一个节点是神经网络两层间的一对输入与输出通道，多个节点代表多个通道，如图1所示。节点间的边表达了神经元对于其它对之间的数据输入输出双向关系：消息交换（message exchange）。

图1关系图（source:文[1]图1(a)）

如图1所示，在关系图中，多层神经网络并不表达为多层图结构。对于结构类似的多层神经网络层，每层关系图结构是一样的。所不同的是每层的消息交换。每一层神经网络完成一轮（round）消息交换。对于深度网络，关系图的结构不变，而进行多轮消息交换。

因此作者将边由消息交换表达的图结构定义为关系图。更具体的，消息交换有两个函数组成：message function和aggregation function。Message function的输入是节点特征，输出是message，而aggregation function的输入是一组messages，输出为更新的节点。

一般地，对于第r+1轮的节点x的特征有：

其中，

是节点v的邻域，即与其直接相连的节点的集合。

表1 不同NN的消息与聚合函数(source:文[1]表1)

很显然，对于不同神经网络，其消息与聚合函数的定义有所不同。文中表1列出了几种神经网络（多层感知器，ResNet）的消息与聚合函数的定义，并重点介绍了由关系图构建几种DNN的方法。

（1）固定宽度MLP

对于固定宽度MLP，每层输入输出维度不变时，关系图所有节点均与其它节点连结，称之为完全关系图。此时节点为单个输入输出通道，message function是输入节点的权积，聚合函数为消息和的非线性变换，二者合并为消息聚合函数：

对于完全关系图，该函数与MLP神经元计算公式一致。

（2）变宽MLP

对于变宽MLP，其关系图的节点为向量代表多个通道，对应消息函数的权重是矩阵，矩阵可以不为方阵，即节点输入输出通道数量可以不同。

作者采用了一个简单策略来划分神经网络层的节点。假定节点数为n,神经网络层的维度为m，对于m mod n个数的节点分配[m/n]+1维，其余节点分配[m/n]维。相信其它方案也适用于节点划分。

文中还提到其它几种神经网络如Resnet，可参照表1的映射来构建，此处不再赘述。

3 如何根据图结构生成NN模型

在构建神经网络的关系图后，作者也给出了一套利用关系图生成NN模型的方法。其关键步骤有三：图度量、图生成和复杂度控制。

（1）图度量

作者列举了多种用于graph的度量，选取全局度量平均路径长度(average path length)和局域度量聚合系数(clustering efficient)作为关系图特性的度量。这是两个图网络理论的概念：

平均路径长度（L）：

两个节点间的路径长度是连通两节点的最少边数。Graph的平均路径长度是所有节点对路径长度的平均。

网络聚合系数（C）：

一个节点的聚合系数定义为其邻域节点间的实际边数与所有可能边数的比值。网络的聚合系数则是所有节点聚合系数的均值。

（2）关系图生成

图生成器的目的是由给出的图度量值产生对应的关系图。在比较了现有多种图生成方法后，作者提出放松约束的Watts-Strogatz(WS)模型产生期望的关系图。

上述两部分内容涉及较多图分析理论，但也是本文分析NN模型的基础框架之一。我们将在下一篇中讨论相关知识及概念。

（3）模型复杂度控制

关系图生成后，由上节介绍的图与神经网络的映射可产生关系图对应的神经网络模型。如前述，一个关系图节点可以对应不同数量的NN维度（神经元），因此同一结构的关系图可以对应不同复杂度的神经网络。本文用NN模型的乘加次数作为复杂度度量，通过每次调整关系图生成NN模型的维度数量（比如MLP中神经元连接数量）使得所有生成模型的复杂度与预设的基准模型保持一致。

简单来说，通过这些准备工作，作者可以遍历不同的graph度量组合，每个组合用WS-flex方法产生关系图，由关系图生成DNN模型，通过调整DNN模型复杂度，最终产生符合要求的DNN模型。

4 实验及分析

作者用Cifar-10和imagenet这两个数据集测试了关系图生成的NN模型的性能。作者遍历平均路径长度(L)和聚合系数(C)的二维参数空间，每个参数根据网络类型(MLP, ResNet)生成相应DNN模型。每个模型用上述数据集训练，并记录每个模型的预测准确率（Top-1 Error）。

热力图

针对每类模型结果，以L和C为坐标展开，生成二维热点图。

图2 部分NN模型性能热力图（source: 文[1]图4f）

由图2可以看出本文的一个重要发现：a sweet spot for top NNs。对所有测试的网络类型，热力图上均存在一个对应NN性能最佳区域（红框区域），更进一步这个区域在不同类型模型和训练集上位置基本是一致的。换句话说，性能好的神经网络的关系图结构存在共性特征。

这一现象也表现在单个度量与NN模型性能的图上。如图3，两个度量上的性能都可拟合为U型曲线。在度量的中间某处的NN模型性能最佳。有趣的是在附件中作者还发现其它图度量与NN模型性能也呈现U性曲线趋势。

这个曲线似乎说明图特征度量太大太小的神经网络性能都不好。通俗理解，图结构太简单太复杂的神经网络性能不好。从直觉上来理解，似乎符合Occam’s razor原则，即所谓‘如无必要，勿增实体’。或者说性能好的神经网络的图结构也符合过犹不及的中庸之道？

图3 部分图度量与NN模型的性能（source: 文[1]Appendix图1）

作者也研究了如何快速确定sweet spot的问题。通过实验，他们发现将参数空间分为52块，每块取样，得到分布与3942个取样的结果高度一致。此外，作者还发现关系图上性能好的NN模型在训练起始阶段就已表现了这一趋势。

图神经网络与一般神经网络

文章最后讨论了图神经网络与一般神经网络的关系。很显然，本文定义的message exchange function与GNN中节点更新操作有相似之处。在关系图表达的框架下，作者认为GNN是一类特殊的一般神经网络结构。特殊之处在于，在GNN中，图结构是网络的输入而不是网络结构本身的一部分，并且所有边共享消息函数以满足图结构不变的条件。

总结

本篇介绍了由Kaiming He和Jure Leskovec等合作完成的新文章“Graph Structure of Neural Networks”。本篇主要分析了这篇文章的思路、提出的新概念、实现及结论。在下一篇介绍中，我们将针对文章提出的新概念，结合图理论，深入理解这篇文章的新概念及重要意义，探讨其目前的局限与可能的方向。本文希望能够起到抛砖引玉的作用，由于水平有限，文中存在不足的地方，请各位读者批评指正，也欢迎大家参与我们的讨论。

参考文献

1.Jiaxuan You, Jure Leskovec, Kaiming He and Saining Xie，Graph Structure of Neural Networks，ICML20202、原来神经网络是一种图？https://zhuanlan.zhihu.com/p/191080820

题图来自网络，版权归原作者所有