随机连线神经网络：用图论替代 NAS 的新思路

Kaiming He 和 Ross 刚出了一篇文章，简单说就是把网络结构的产生方式从手工设计或NAS直接换成一个随机图生成器，用这个生成器直接生成随机的计算图，连筛选都省了——随机出来什么就用什么。

核心思路

这个方法和NAS里的Random Search有本质区别。Random Search是随机搜索一批结构，然后挑里面最好的那个；而这里的做法是直接随机生成，不做任何挑选。实验表明，同一个生成器参数下，不同随机种子生成的网络性能方差很小，效果都差不多——这就意味着根本不需要挑选。

作者的结论是：与其花精力去设计或搜索某个具体的网络结构，不如去设计更好的网络生成器（即采样器）。让生成器采出来的结构普遍都好，比优化单一结构或搜索过程更重要。这个方向值得认真想一想。

不同随机图生成器（ER、BA、WS）在多组参数下的 ImageNet top-1 准确率柱状图，每个柱表示 5 个随机网络实例的均值与标准差 — 图 1：ER、BA、WS 三种生成器在不同参数下的 ImageNet top-1 准确率对比，误差棒为 5 个随机实例的标准差，方差极小

三种随机图生成算法

论文用了图论中的三种经典随机图生成算法：Erdős–Rényi（ER）、Barabási–Albert（BA）和 Watts–Strogatz（WS）。生成的图样例如下：

ER、BA、WS 三种随机图生成器在不同参数设置下生成的图样例可视化 — 图 2：ER、BA、WS 生成的随机图样例，节点数固定为 N=32，展示不同生成器和参数下的拓扑差异

这些随机图不一定是有向无环图（DAG），而神经网络的计算图必须是DAG，否则前向传播会有环。论文的处理方式是对节点做拓扑排序编码，把生成的图转换成DAG。

Erdős–Rényi（ER）

两个参数：节点数N和连边概率P。

遍历所有节点对，每对之间以概率P独立地连一条边。任何含N个节点的图都有可能通过ER生成，没有任何结构偏好，完全随机。

Barabási–Albert（BA）

两个参数：节点数N和每步新增边数M。

初始时有M个孤立节点，无边。之后每次插入一个新节点，为其连接M条边，连接目标按已有节点的入度成比例地随机选取——度数越高的节点被选中的概率越大。总共插入（N - M）个节点，生成 M(N - M) 条边。

Watts–Strogatz（WS）

三个参数：节点数N、初始近邻数K（偶数）和重连概率P。

初始时N个节点排成一个环，每个节点与其左右各K/2个邻居相连。然后对每个节点，在顺时针方向上依次选择那些尚未连接且不是自身的节点，以概率P连一条额外的边。按此算法生成的图恰好有 N×K 条边。

网络整体结构：保留了多少人工先验

随机化只在计算图的拓扑上，整个网络仍然需要一些人工设计的先验知识。

整体结构沿用了多stage的经典范式（下图中的conv层），不同stage之间用卷积做下采样，控制特征图分辨率。随机连线发生在每个stage内部。

stage	output	small regime	regular regime
conv $_1$	112×112	3×3 conv, $C/2$	3×3 conv, $C/2$
conv $_2$	56×56	3×3 conv, $C$	random wiring, $N/2,\ C$
conv $_3$	28×28	random wiring, $N,\ C$	random wiring, $N,\ 2C$
conv $_4$	14×14	random wiring, $N,\ 2C$	random wiring, $N,\ 4C$
conv $_5$	7×7	random wiring, $N,\ 4C$	random wiring, $N,\ 8C$
classifier	1×1	1×1 conv, 1280-d; global average pool, 1000-d $fc$ , softmax	1×1 conv, 1280-d; global average pool, 1000-d $fc$ , softmax

每个节点上的操作固定为3×3 depthwise separable convolution（sep conv）。

在每个随机子图的首尾各加一个特殊节点：

输入节点：连接到原始图中所有入度为零的节点，把输入tensor复制并分发给它们。
输出节点：连接到图中所有出度为零的节点，将这些输出加权求和，得到该stage的最终输出。

图内部，当一个节点有多个输入时，同样做加权求和。整体结构如下图所示：

三个随机连线网络的整体结构示意，从顶部的 conv 层经过多个随机子图阶段到底部的 classifier — 图 3：随机连线网络的整体结构，从 conv $_1$ 到 classifier，每个 stage 内部是一张随机生成的有向无环图

超参数极少

整个网络的超参主要用来控制规模大小：随机图的节点数、Channel数、输入图片分辨率。各生成算法内部的参数只有一两个。作者在ImageNet上对不同算法和不同超参做了系统对比：

实验结果

ImageNet

实验分大、中、小三种规模，在相同计算量和参数量下，随机生成的网络几乎能达到当时state-of-the-art的水平：

network	top-1 acc.	top-5 acc.	FLOPs (M)	params (M)
MobileNet [15]	70.6	89.5	569	4.2
MobileNet v2 [40]	74.7	–	585	6.9
ShuffleNet [54]	70.9	89.8	524	~5
ShuffleNet v2 [30]	73.7	–	524	~5
NASNet-A [56]	74.0	91.6	564	5.3
NASNet-B [56]	72.8	91.3	488	5.3
NASNet-C [56]	72.5	91.0	558	4.9
Amoeba-A [34]	74.5	92.0	555	5.1
Amoeba-B [34]	74.0	91.5	555	5.3
Amoeba-C [34]	75.7	92.4	570	6.4
PNAS [26]	74.2	91.9	588	5.1
DARTS [27]	73.1	91.0	595	4.9
RandWire-WS	74.7±0.25	92.2±0.15	583±6.2	5.6±0.1

表 2. ImageNet：小计算量regime（&lt；600M FLOPs）。RandWire 结果为 5 个随机网络实例的平均准确率（±std），采用 WS(4, 0.75)；训练 250 epochs，与 [56, 34, 26, 27] 一致，以便公平对比。

network	top-1 acc.	top-5 acc.	FLOPs (B)	params (M)
ResNet-50 [11]	77.1	93.5	4.1	25.6
ResNeXt-50 [52]	78.4	94.0	4.2	25.0
RandWire-WS, $C=109$	79.0±0.17	94.4±0.11	4.0±0.09	31.9±0.66
ResNet-101 [11]	78.8	94.4	7.8	44.6
ResNeXt-101 [52]	80.1	95.2	8.0	44.2
RandWire-WS, $C=154$	80.1±0.19	94.8±0.18	7.9±0.18	61.5±1.32

表 3. ImageNet：常规计算量regime，FLOPs 与 ResNet-50（上）、ResNet-101（下）相当。ResNeXt 为 32×4 版本 [52]，RandWire 为 WS(4, 0.75)。

network	test size	epochs	top-1 acc.	top-5 acc.	FLOPs (B)	params (M)
NASNet-A [56]	331²	>250	82.7	96.2	23.8	88.9
Amoeba-B [34]	331²	>250	82.3	96.1	22.3	84.0
Amoeba-A [34]	331²	>250	82.8	96.1	23.1	86.7
PNASNet-5 [26]	331²	>250	82.9	96.2	25.0	86.1
RandWire-WS	320²	100	81.6±0.13	95.6±0.07	16.0±0.36	61.5±1.32

表 4. ImageNet：大计算量regime。网络与表 3（ $C=154$ ）相同，但在 320×320 图像上评测（而非 224×224），且仅训练 100 epochs。

COCO目标检测

将backbone替换成随机生成的网络，检测精度比ResNet-50和ResNeXt-50要好：

backbone	AP	AP $_{50}$	AP $_{75}$	AP $_S$	AP $_M$	AP $_L$
ResNet-50 [11]	37.1	58.8	39.7	21.9	40.8	47.6
ResNeXt-50 [52]	38.2	60.5	41.3	23.0	41.5	48.8
RandWire-WS, $C=109$	39.6	61.9	43.3	23.6	43.5	52.7
ResNet-101 [11]	39.8	61.7	43.3	23.7	43.9	51.7
ResNeXt-101 [52]	40.7	62.9	44.5	24.4	44.8	52.6
RandWire-WS, $C=154$	41.1	63.1	44.6	24.6	45.1	53.0

表 5. COCO 目标检测结果，由表 3 中的网络微调而来，在 val2017 上报告。这些 backbone 的 FLOPs 与 ResNet-50 / ResNet-101 相当。

鲁棒性实验

网络训练完成后，随机删掉一些节点和边，测试准确率的下降幅度。不同生成算法下，鲁棒性表现有差异：

对训练好的网络随机删除一个节点（上）或一条边（下）后，ImageNet top-1 准确率下降幅度的散点图，分 ER、BA、WS 三种生成器 — 图 5：图损伤消融——随机删除一个节点（上）或一条边（下）后准确率的下降幅度，红圈为均值、橙框为四分位距、蓝点为单个损伤实例

说实话我觉得这组实验意义不大——为什么要人为去掉已经训练好的网络中的节点和边？这个设定的实际应用场景不太清楚。

节点操作消融

将节点操作从3×3 sep conv换成3×3普通conv，或者pooling后接1×1 conv，最终3×3 sep conv效果最好：

同一组随机图换用不同节点操作（3×3 sep conv、3×3 conv、max-pool、avg-pool 接 1×1 conv）后的 top-1 准确率对比散点图 — 图 6：节点操作消融——同一组随机图换用不同节点操作后的准确率对比，3×3 separable conv 整体最优，且生成器之间的准确率排序大致保持不变

一点工程疑虑

论文里的FLOPs和参数量都比较小，但我怀疑实际训练时内存开销会很大。原因是随机图中存在大量tensor的copy和分发操作（输入节点把tensor复制分发给多个子节点，多分支汇聚时也要保存中间激活）。这部分运行时显存开销不体现在FLOPs和参数量里。

当然也有可能不会——如果框架对不可变tensor的「复制」只是传引用而非真实拷贝，额外开销可能没那么大。但这一点在当前框架下并不能保证，值得实际跑一跑验证。

小结

这篇论文的主要贡献在于提出了一个新的思路：网络设计的未来方向应该从传统的结构设计或NAS，转变为设计更好的网络生成器。如果一个生成器采出来的结构性能普遍都好、方差极小，那么优化这个生成器（采样分布）比优化单一结构或搜索过程更为根本。超参少、先验知识少，是这个方向相比NAS的明显优势。这个思路值得继续跟进。

论文笔记
NAS
网络结构

2019 · 04 · 07