神经网络的图结构
摘要
本文是对两位机器学习领军人物在2020年ICML上的文章Graph Structure of Neural Networks的再解析。该论文从神经网络连接关系的视角重新定义了一种图结构来表达神经网络模型，并从图结构本身的属性来分析什么样的神经网络模型会具有好的预测性能。去年我们结合图理论背景知识理解了文章的主要概念和重要意义。时隔半年，回头再阅读这篇文章，我们对文章整体有了一个更完整的理解。
介绍
众所周知，神经网络可以用计算图来表示，其中神经元为节点，层与层之间的神经元有向连接为边。同时许多研究也证实神经网络的性能与其结构相关。很自然，研究者会联想到更进一步的问题：是否存在优化网络性能的结构特征？是否可以通过网络结构判断其性能？回答这些问题，则需要步系统性研究神经网络性能与其内含图结构关系。
ICML2020收录了一篇有趣的文章“Graph Structure of Neural Networks”[1]，由Kaiming He和Jure Leskovec等合作完成。二位分别是机器视觉与图网络领域的领军人物。文章尝试用图结构而不是传统的计算架构来分析上述问题，即：神经网络的结构与其性能的关系如何？根据提出的图分析方法，作者进一步分析了好的模型应该具有什么样的结构特征。
我们之前已经对文章的相关概念做了解读。本文回顾了之前的理解，并对文章的不足做出点评。
用图结构来表达神经网络
如前述，神经网络天然可以看作是一个图结构，但目前缺乏一个有效的方法实现任意神经网络到图结构间的映射。而通常用于神经网络表达的计算图是有向无环图，这限制了图理论在神经网络结构分析中的应用。
针对现有计算图表达的缺点，本文作者提出了”关系图”(relational graph)的概念来表达层间组合神经元的互动，并设计了一种图产生器将各类神经网络转换为关系图，进而系统性研究了神经网络结构与性能的关系。这篇文章直接运用了许多图领域的知识，对于专注神经网络的人来说，需要了解一些Graph理论背景。
与计算图类似，关系图中包括多个节点，但不同的是，关系图中的一个节点是神经网络两层间的一对输入与输出通道，多个节点代表多个通道，如图1所示。节点间的边表达了神经元对于其它对之间的数据输入输出双向关系：消息交换（message exchange）。
图1 关系图（source: 原文图1(a)）
如图所示，在关系图中，多层神经网络并不表达为多层图结构。对于结构类似的多层神经网络层，每层关系图结构是一样的。所不同的是每层的消息交换。每一层神经网络完成一轮（round）消息交换。对于深度网络，关系图的结构不变，而进行多轮消息交换。
因此作者将边由消息交换表达的图结构定义为关系图。更具体的，消息交换有两个函数组成：message function和aggregation function。Message function的输入是节点特征，输出是message，而aggregation function的输入是一组messages，输出为更新的节点。
一般地，对于第r+1轮的节点x的特征有：
很显然，对于不同神经网络，其消息与聚合函数的定义有所不同。文中表1列出了几种神经网络（多层感知器，Resnet）的消息与聚合函数的定义，并重点介绍了由关系图构建几种DNN的方法。
对于固定宽度MLP，每层输入输出维度不变时，关系图所有节点均与其它节点连结，称之为完全关系图。此时节点为单个输入输出通道，message function是输入节点的权积，聚合函数为消息和的非线性变换，二者合并为消息聚合函数：
对于完全关系图，该函数与MLP神经元计算公式一致。
2.变宽MLP
对于变宽MLP，其关系图的节点为向量代表多个通道，对应消息函数的权重是矩阵，矩阵可以不为方阵，即节点输入输出通道可以不等。
作者采用了一个简单策略来划分神经网络层的节点。假定节点数为n, 神经网络层的维度为m，对于m mod n个数的节点分配 [m/n]+1维，其余节点分配[m/n]维。相信其它方案也适用于节点划分。
文中还提到其它几种神经网络如Resnet，可参照表1的映射来构建，此处不再赘述。值得注意的是，尽管文章中没有列出，作者提供的开源代码还包括了对efficientnet的实验。
基于关系图的NN模型生成
在构建神经网络的关系图后，作者也给出了一套利用关系图生成NN模型的方法。其关键步骤有三：图度量，图生成和复杂度控制。
作者列举了多种用于graph的度量，选取全局度量平均路径长度(average path length)和局域度量聚合系数(clustering efficient)作为关系图特性的度量。这是两个图网络理论的概念：
平均路径长度（L）：两个节点间的路径长度是连通两节点的最少边数。Graph的平均路径长度是所有节点对路径长度的平均。
网络聚合系数（C）：一个节点的聚合系数定义为其邻域节点间的实际边数与所有可能边数的比值。网络的聚合系数则是所有节点聚合系数的均值。
2.图生成
图生成器的目的是有给出的图度量值产生对应的关系图。在比较了现有多种图生成方法后，作者提出放松约束的Watts-Strogatz(WS)模型产生期望的关系图。
3.模型复杂度控制
如前述，通过改变节点对应的NN维度数量，同一结构的关系图可以对应不同复杂度的神经网络。本文用NN模型的乘加次数作为复杂度度量，通过每次调整关系图生成NN模型的维度数量（比如MLP中channel数）使得所有生成模型的复杂度与预设的基准模型保持一致。
简单来说，通过这些准备工作，作者可以遍历不同的graph度量组合，每个组合用WS-flex方法产生关系图，由关系图生成DNN模型，通过调整DNN模型复杂度，最终产生符合要求的DNN模型。
实验及结果
作者在Cifar-10和imagenet这两个数据集测试了关系图生成的NN模型的性能。作者遍历平均路径长度(L)和聚合系数(C)的二维参数空间，每个参数根据网络类型(MLP, Resnet)生成相应DNN模型。每个模型一数据集训练，并记录每个模型的预测准确率（Top-1 Error）。针对每类模型结果，以L和C为坐标展开，生成二维热力图。
图2 NN模型性能热力图（source:原文图4f）
由图2可以看出本文的一个重要发现：a sweet spot for top NN。对所有测试的网络类型，热力图上均存在一个对应NN性能最佳区域（红框区域），更进一步这个区域在不同类型模型和训练集上位置基本是一致的。换句话说，性能好的神经网络的关系图结构存在共性特征。
这一现象也表现在单个度量与NN模型性能的图上。如图3，两个度量上的性能都可拟合为U型曲线。在度量的中间某处的NN模型性能最佳。有趣的是在附件中作者还发现其它图度量与NN模型性能也呈现U性曲线趋势。
这个曲线似乎说明图特征度量太大太小的神经网络性能都不好。通俗理解，图结构太简单太复杂的神经网络性能不好。从直觉上来理解，似乎符合Occam’s razor原则，即所谓‘如无必要，勿增实体’。或者说性能好的神经网络的图结构也符合过犹不及的中庸之道？
图3 单个图度量与NN模型的性能（source原文Appendix 图1）
作者也研究了如何快速确定sweet spot的问题。通过实验，他们发现将参数空间分为52块，每块取样，得到分布与3942个取样的结果高度一致。此外，作者还发现关系图上性能好的NN模型在训练起始阶段就已表现了这一趋势。
图神经网络与一般神经网络结构
图神经网络是这两年的研究热点之一。文章也讨论了图神经网络与一般神经网络的关系。很显然，文中定义的message exchange function与GNN中节点更新操作有相似之处。在关系图表达的框架下，作者认为GNN是一类特殊的一般神经网络结构。特殊之处在于，在GNN中，图结构是网络的输入而不是网络结构本身的一部分，并且所有边共享消息函数以满足图结构不变的条件。
思考与总结
本篇介绍了由Kaiming He和Jure Leskovec等合作完成的新文章“Graph Structure of Neural Networks”。本篇主要分析了这篇文章的思路、提出的新概念、实现及结论。半年多后，我们回过头在理解这篇文章，也能看到一些不足之处。
（1）由于计算量的限制，本文的结论来自于有限的小数据集。对于大尺度数据或非图像数据，“最佳点”是否成立是需要研究的。
（2）本文度量“平均度量长度”和“网络聚合函数”似乎是一种经验的选择，理论上是否可以证明这些度量和神经网络模型的相关性？是否存在其它合适的度量？
此外，本文尝试了从神经网络分析最优结构。一个自然的推想就是：给定某个sweet spot，可否建立有效方法构建期望的神经网络模型？
本文的工作相对较新，目前尚未看到太多相关的后续工作。相信作者和其他研究者后续会有更详实的分析与研究。
参考文献
往期推荐
壁仞科技研究院作为壁仞科技的前沿研究部门，旨在研究新型智能计算系统的关键技术，重点关注新型架构，先进编译技术和设计方法学，并将逐渐拓展研究方向，探索未来智能系统的各种可能。壁仞科技研究院秉持开放的原则，将积极投入各类产学研合作并参与开源社区的建设，为相关领域的技术进步做出自己的贡献。