AutoGO: Automated Computation Graph Optimization for Neural Network Evolution
Authors: Mohammad Salameh
Keith G. Mills
Negar Hassanpour
Fred X. Han
Shuting Zhang
Wei Lu
SHANGLING JUI
CHUNHUA ZHOU
Fengyu Sun
Di Niu
Venue: NeurIPS 2023 poster (2023)
Keywords: Neural Architecture Search
Optimization Framework
Performance Prediction
TL;DR: We develop a framework for optimizing the performance and hardware-friendliness of architectures using a segment database extracted from existing NAS benchmarks.

Abstract: Optimizing Deep Neural Networks (DNNs) to obtain high-quality models for efficient real-world deployment has posed multi-faceted challenges to machine learning engineers. Existing methods either search for neural architectures in heuristic design spaces or apply low-level adjustments to computation primitives to improve inference efficiency on hardware. We present Automated Graph Optimization (AutoGO), a framework to evolve neural networks in a low-level Computation Graph (CG) of primitive operations to improve both its performance and hardware friendliness. Through a tokenization scheme, AutoGO performs variable-sized segment mutations, making both primitive changes and larger-grained changes to CGs. We introduce our segmentation and mutation algorithms, efficient frequent segment mining technique, as well as a pretrained context-aware predictor to estimate the impact of segment replacements. Extensive experimental results show that AutoGO can automatically evolve several typical large convolutional networks to achieve significant task performance improvement and FLOPs reduction on a range of CV tasks, ranging from Classification, Semantic Segmentation, Human Pose Estimation, to Super Resolution, yet without introducing any newer primitive operations. We also demonstrate the lightweight deployment results of AutoGO-optimized super-resolution and denoising U-Nets on a cycle simulator for a Neural Processing Unit (NPU), achieving PSNR improvement and latency/power reduction simultaneously. Code available at https://github.com/Ascend-Research/AutoGO.

AutoGO: Automated Computation Graph Optimization for Neural Network Evolution
Mohammad Salameh', Keith G. Mills!.2-f Negar Hassanpour's Fred X. Han', Shuting Zhang', Wei Lu Shangling Jui Chunhua Zhou², Fengyu Sun Di Niu²
Huawei Technologies Canada. 'Dept. ECE, University of Alberta. 'Huawei Kirin Solution, China.
(mohammad., salameh, negar. haaaanaussm,,,, shangling zhouchunhuaa@huuxeei. Okgmills, dnin/Qualberta.ca, (zhangshuting3, robin. luwei, sunfengy/dhhsiilicon.com (etegy/m@@iiiliionnnomm
Abstract
Optimizing Deep Neural Networks (DNNs) to obtain high-quality models for efficient real-world deployment has posed multi-faceted challenges machine learning engineers. Existing methods either search for neural architectures in heuristic design spaces or apply low-level adjustments computation primitives improve inference efficiency on hardware. We present Automated Graph Optimiza- tion (AutoGO), a framework to evolve neural networks low-level Computation Graph (CG) of primitive operations to improve both its performance and hardware friendliness. Through a tokenization scheme, AutoGO performs variable-sin sized segment mutations, making both primitive changes and larger-grained changes CGs. We introduce our segmentation and mutation algorithms, efficient frequent segment mining technique, well pretrained context-aware predictor to timate the impact of segment replacements. Extensive experimental results show that AutoGO automatically evolve several typical large convolutional networks to achieve significant task performance improvement and FLOPs reduction on a range of CV tasks, ranging from Classification, Semantic Segmentation, Human Pose Estimation, to Super Resolution, yet without introducing any newer primitive operations. We also demonstrate the lightweight deployment results of AutoGo- optimized super-resolution and denoising U-Nets on a cycle simulator for a Neural Processing Unit (NPU), achieving PSNR improvement and latency/power reduction simultaneously. Code available at https://gituub.com/AAA Aaweendd-eeearcc/Auutoooo
Introduction
Deep Neural Networks (DNNs) have achieved great success Computer Vision (CV) and Natural Language Processing (NLP) tasks. A major trend toward achieving better performance on benchmarks is adopting large and computationally demanding deep models [7]. However, successful and efficient deployment of deep neural networks onto diverse and specific hardware devices, including neural processing units on the edge, significantly hinges upon engineering proper neural architectures that are both excellent in task performance while meeting hardware friendliness objectives.
range of techniques have been proposed by academia and industry to solve the hardware-frieende deployment challenges of DNNs [46]. Neural Architecture Search (NAS) replaces the manual design process of DNNs, achieving remarkable performance in several applications CV 67
9
and NLP 32 10 [2].
While NAS can utilize flexible range of search algorithms 53
47
the search space adopted by NAS is based on heuristics, either searching for an optimal macro-net
"quual contribution.
i Work done during an internship at Huawei.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

construction based on predefined blocks, e.g. MBCony blocks in MobileNets [59 26], or stacking searchable cells by heuristic rules [39 73.. These heuristic rules may not be efficient the target hardware device for deployment and may limit the potential gain from NAS methods. On the other hand, graph rewriting [70 3D) operates on the tensor computation graph of DNN to improve its inference efficiency on hardware. Rewriting involves applying set of subgraph substitution rules that preserve mathematical functionality of the original DNN, which does not alter or reduce the neural architecture achieve better task performance or fitness to hardware.
In this paper, we propose Automated Graph Optimization (AutoGO). a generic graph optimization framework to evolve a given neural architecture for efficient and low-power deployment onto a specific hardware device. Unlike traditional NAS which builds networks from scratch in a heuristic search space or from hand-crafted building blocks [39 63 [5], AutoGO enhances both hardware- friendliness and task performance of a DNN, by evolving its underlying Computation Graph (CG) using computational units composed of operations extracted from NAS benchmarks. AutoGO automatically improves typical neural networks in terms of benchmark performance on several CV tasks ranging from classification, semantic segmentation, to super-resolution without relying on newer operations. It also automates lightweight DNN deployment onto mobile neural processing units while preserving task performance, hence replacing manual tweaking efforts by ML engineers. We present the following key contributions in designing the AutoGO framework:
AutoGO optimizes DNNs on a Computation Graph (CG) of low-level primitives extracted from TensorFlow [ models, which allow us to optimize all types of operations and their hy- perparameters like filter size and latent tensor dimensions and thus offer a holistic fine-grained view of DNNs. Unlike graph rewriting which preserves mathematical equivalence, AutoGO alters the CG of a DNN for task performance and fitness to hardware.
Clome
Figure 1: A DNN can be partitioned into disjoint subgraphs (segments). Segments contain a variable number of inputs, outputs, and nodes ranging from primitive operations to complex subgraphs.
Rather than relying on predefined blocks, the basic units for mutation in AutoGO are com- putation subgraphs. which we call segments, as illustrated in Figure[]] Segments are mined from large number of CGs from several NAS bench- marks based on frequent subgraph mining in a data-driven manner. We use Byte Pair Encoding (BPE), an efficient tokenization technique (20) from NLP, to segment CGs and merge frequent operations into segments. By extracting and including segments of variable sizes into our database, AutoGO enables both primitive operation changes and scaled block changes to a DNN.
AutoGO leverages an evolutionary algorithm to mutate our BPE-segmented source network. The segment mutation process is guided by hardware friendliness metrics and a pre-trained neural predictor to estimate the performance of the mutant network resulting from segment replacement. We propose a neural predictor which explicitly considers the positional and contextual information of a segment replacement made CG and directly models the performance gain. Mutations are also coupled with resolution propagation scheme that solves for the tensor shapes in the replacement segment to ensure architectural validity.
Extensive experiments demonstrate that AutoGO can enhance the performance of the best architec- tures in several public architecture benchmarks, e.g., NAS- 101 (7I). NAS-Bench-201 (17). HiAML, Inception, and Two-Path [8). Additionally, AutoGO can automatically optimize several typical large CNN architectures, including ResNets (24. VGG [1], and EDSR (88 on a breadth CV tasks including Classification, Semantic Segmentation, Human Pose Estimation, and Super Resolution. We show that AutoGO can improve their performance while making them lightweight, without using newer generations of operations that do not appear in the original network. Finally, to demonstrate the real-world applicability of our framework, we show results of AutoGO-optimized FSRCNN [16] (for super-resolution) and image denoising U-Net (55) for low-power or low-latency deployment using a cycle simulator for a Huawei mobile Neural Processing Unit (NPU).
2

---

2
Related Work
NAS Benchmarks and Neural Predictors. NAS-Benchmarks comprise architectures from a given
search space and their accuracy performance. NAS-Bench-10) 101 [71] and NAS-Bench-201 [17] provide the performance of 423k and 15.6k architectures, respectively, on CIFAR-10. Benchmarks enable the rapid development of search algorithms and neural predictors. Neural predictors 43
54 41 73
65 40) treat NAS benchmarks as datasets and learn to estimate the performance of architectures in a given search space, and thus constitute low-cost avenue for performance evaluation.
However, NAS benchmarks suffer from several drawbacks. First, benchmarks only provide per- formance annotations for architectures inside a manually designed fixed search space. Thus, any tweaks decrease FLOPs or latency beyond the search space requires training the new architecture from scratch. Second, existing NAS Benchmarks are mostly cell-based [39 and compose network by stacking the same cell structure multiple times. This structure forms a high-level architecture representation that is insensitive to spatial details such as latent tensor dimensions, which vary along the depth of the network and influence learn using high-level cell representations, these drawbacks hamper their deployment generalizability. In contrast, AutoGO can mutate an architecture beyond its original, manually-defined design space by utilizing a low-level, spatially- spatially-sensitive sensitive representation.
[49]. As most existing neural predictors
Computational Graphs for DNN Hardware Friendliness. Multiple subfields explore how to reduce the carbon footprint and time cost of DNNs. Pruning and quantization methods [36] aim to reduce the number of parameters or lower the bit precision of model weights, respectively. Graph rewriting methods like TASO 300 and TENSAT 70) consider mathematically equivalent substitutions, e.g.. merging or splitting parallel convolutions and applying the associativ//distributvve properties. These schemes usually require spatial details like resolution and channel size to perform rewrites. Hence, they represent DNNs using Computation Graphs (CG) [50] 222, which treat each primitive operation as node and use the network forward pass to define edge connectivity. Similarly, AutoGO also uses a low-level CG representation. But different from these approaches, it aims to evolve the architecture of untrained DNN to improve performance while also optimizing hardware friendliness.
Neural Architecture Design Space. Several works employ NAS over large spaces by jointly searching over macro and micro-structures for both block type and tensor dimensions [64] 15 Human expertise at the core of these design choices to constrain the search for aeg-pperforming architectures.
57 model a search space as 3-level hierarchical graph to overcome the reliance on expert knowledge. [13] propose Neural Search Space Evolution, which progressively grows a current search space by adding unseen operation candidates. Unlike the above work, we do not limit ourselves to a pre-designed skeleton with spatial or topological constraints at any network position. Rather, we incorporate search space and architectural knowledge into a neural predictor. Also, instead of manually defining the search units [7 [59 62 42), we mine these units from NAS benchmarks. In particular, utilize Frequent Subgraph Mining (FSM) [1] to discover interesting and frequent patterns in the computation graphs in a data-driven way. FSM requires conducting expensive steps when graphs are large such extracting patterns, inspecting isomorphism, and checking if subgraphs are frequent enough to be considered interesting. Algorithms (68 69 (7 trade result completeness and accuracy for efficiency to overcome run time and memory inefficiency 19] In NAS, (56) utilize Weisfeiler-Lehman (WL) graph kernel to extract useful network features but only applies it shallow cell-based DAG structure of NAS-Bench-201. In contrast, we propose an efficient approach to mine frequent subgraphs by converting CGs to sequences and applying BPE 20 to extract subsequences, which produces a fixed-size vocabulary of subgraphs of varying sizes.
3 AutoGO: Automated Computation Graph Optimization
The AutoGO framework operates on the Computation Graph (CG) of an input DNN architecture extracted from the in-memory graph structure of tensorflow. keras model or pb file. CGs are directed acyclic graphs (DAGs), where nodes represent primitive operations that are indecompos- able computation operations in deep learning frameworks like ONNX 55] and PyTorch [52), e.g., Convolutions, Pooling, ReLU, Add, etc., while edges represent poward-passes between operations. Specifically, node features include operation type, input and output tensor resolution dimensions and weight tensor shape if applicable.
3

---

Segrmnt
OO
Select Reslesement
Segmerts
Outou Parata fronser
Resolution Propagation
Evelucto Performance
Eval. HM nilliess
Input OG
-
8"
PSC Predictor
FLOPs Power Calc.
Bogment BPE Vooao
00
Selest parenis from Parosu franterr
Figure 2: AutoGO takes the CG of a neural network as input and improves it using an algorithm- mined segment database and pre-trained mutation performance predictor.
Figure 2 provides an overview of the proposed AutoGO operating on the CG level. AutoGO mutates the CG of input DNN by utilizing database of segments (Sec. 3.1) which are frequent subgraphs mined from a variety of NAS-Benchmarks via an efficient tokenization method. A Pareto front evolution strategy (Sec. (.2) performs segment mutations the CG, while using resolution propagation to ensure network validity. Finally, a pretrained
(PSC) neural predictor (Sec. 3.3) together with selected hardware metries will guide the evolution by assessing the performance gain when a certain segment is stitched into the architecture.
3.1 Computation Graph Segmentation via Tokenization
We partition a CG into a contiguous sequence of subgraphs, which we call segments. A segment, denoted by 8, may have multiple input and output nodes, could even be single primitive operation. For to be a valid neural network, any two contiguous segments and 83 in g must maintain the correctly matched height, width and channel (H, W, C*) resolutions. The resolutions of output nodes of s;, have to match the resolutions of input nodes of its succeeding segment sj. Our definition of segment spans wider range of topologies and provides flexible operation grouping than predefined or handcrafted blocks, e.g., ResNet and MBConv blocks or DARTS cells [39]]
The Segment Database D is the core component that stores the segment units that AutoGO mutations are based on. AutoGO uses the segment database D (or vocabulary) to either partition an input CG into segment units select segment from D to replace existing segment in input CG. To alleviate the memory and time complexities of mining common subgraphs from a large number of CGs, we relax the problem into mining segments from sequences. This allows utilize much more efficient tokenization techniques over sequences.
Given set of neural networks represented in CG format G [g) , 9u J. we convert each CG into a topologically sorted sequence of nodes. We enrich node representation by labeling a node in the form of [current op, incoming ops, outgoing ops]. I Each unique node label is further encoded into a single character symbol. Thus, a topologically sorted CG can be mapped into a string of character symbols, where each character encodes operation and its neighboring operations. By converting all graphs in G into sequences, we essentially have built a corpus for training a tokenizer extract common segments of character symbols. Specifically, we Byte-Pair Encoding (BPH), data compression
(20) technique with a wide use for text tokenization in NLP [60], to tokenize the string representations of CGs. BPE operates iteratively by collecting frequent pairs of consecutive symbols to build a vocabulary of tokens (segments). Using BPE, we extract the most common subsequences from the string representation of the CGs and build vocabulary of size [V. We revert each discovered subsequence in the vocabulary back to its corresponding subgraph representation from the CG to form a segment database D. Given a new CG, BPE utilizes built vocabulary and applies a greedy algorithm to segment it. Figure [ provides an example of a segmented CG. Our approach brings several benefits over mining on large graphs with WL-kernels. The extraction process on sequences is efficient. Using BPE enables segment extraction from all benchmark families simultaneously without facing memory inefficiencies like WL--eenel.
$ For example, we label Conv 3x3 node with incoming edges from Add and BatchNorm operations and an outgoing edge to ReLU operation (conv2d3,in.add, inw.aadd.bacccoomm......r

---

3.2 Computation Graph Mutation
We an evolutionary search strategy perform segment mutations the CG of input architec- ture and iteratively update a Pareto front of architectures in terms of predicted accuracy and a chosen hurdwwrr--riendlinee objective, e.g., FLOPs, latency, and power. The mutation made parent architecture comprises the following steps: segmentation, source segment selection, replacement segment selection, tensor resolution (shape) propagation, and performance evaluation. First, AutoGO partitions the parent architecture into segments using the BPE-generated vocabulary V. BPE adopts greedy segmentation approach, which will lead to deterministic partitioning. To diversify the segmentation outcome, we select a subset of vocabulary V' C V that BPE uses during segmentation, thus leading to different partitioning outcomes every time the CG is segmented. After segmentation. we select a set of candidate source segments to mutate. For each source segment 8y, we randomly select multiple replacement segments S E 'D that have the same number of inputs and outputs as the corresponding source segment. If st has multiple inputs and/or outputs, AutoGO randomly maps these to the outputs and/or inputs created by removing 8;.
The mutation process must maintain a valid architecture, by correctly combining the replacement segment with the rest of the model. Given CG g. let Sg {so, 81, ...y 8n-13 } be the of disjoint segment subgraphs generated by applying BPE to Let 8;, 0 S S n - 1 be a source segment within g that we wish to replace. We partition the segments within Sg into three distinct groups that reflect their positions within g:
The Predecessor group denotes all segments P {spi 0 < i} between the input and 8t-
The specific Segment 81 E 'D that we are aiming to replace by mutating g-
The suCessor group denotes all the remaining network segments C {so5 c S n 1}.
Let (P,S,C) C refer a CG partitioned in this manner, denoted by grey, purple and orange blocks in Fig- 3 Hence, for a mutation to be valid, the shape of the out-
Predecessorr-
Proposed Mutation
put tensor from the Predecessor P must match that of
ReLU
the input to the replacement segment se and the out-
Pool
put shape of 8 must match the shape of the expected input to suCcessor C. AutoGO adapts replacement segment s the remainder of the architecture P and C' by adjusting the hyperparameters of operations in of to achieve the desired resolutions. Adjustments are applied to mutable operations, e.g.. increasing the stride of convolutions and pooling operations induce downsampling, whereas operations such as activations and batch normalization are immutable. Depending on the P. C' and sf subgraphs, stitching the replacement segment into the overall CG may be infeasible. We cast this "resolution propagation" task as Mixed Mixed-Integer Linear Program (MILP) over the adjustable hyperparameters of mutable nodes within s7 which is optimization problem with linear objectives and constraints, and integer-valued decision variables. We define MILP constraints that regulate the correct resolution propagation within sf when stitched to the rest of the architecture.
Conv
Concat
BN
-Successor
BN
Conv
Add
Figure An example of segment mutation. AutoGO takes an input CG (left) and replaces source segment s; with sf. The predecessor (grey) and successor (yellow) are unchanged.
At the end of each mutation iteration, we retain all the segment replacements that have feasible solution to the resolution propagation MILP, and profile these valid segment mutations in terms of the predicted accuracy gain given by the PSC predictor (Sec. (3.3 and selected hardware friendliness metric, based on which Pareto front O [2 of architectures is maintained and updated. During the first iteration, we only mutate the input architecture. At the beginning of each successive iteration, AutoGO selects the k architectures from the Pareto front as parents to mutate. If the Pareto front contains less than architectures, AutoGO will select additional non-Parett optimal architectures having the minimum sum of accuracy and FLOPs ranks. Further technical details on the (P, S, C)} partitioning scheme, resolution propagation, parent selection process and overall algorithm, including examples, illustrations and pseudocode, are provided in supplementary Sections A.3.I and A.5
5

---

3.3 Context-Aware Mutation Performance Estimation
AutoGO uses a neural predictor to estimate the performance of mutant architectures in order to search for high-quality networks. We propose a novel predictor that assesses the potential performance benefit from a segment mutation, based on its topology, context and its location within the architecture.
Just as we can construct subgraphs from the individual segments produced by BPE. we can construct larger predecessor and successor subgraphs from all segments within P and C, respectively. We use this format to train a PSC neural predictor. Let h- denote a fixed-length graph embedding for an arbitrary graph produced by a graph neural network (GNN) [5T]. The PSC predictor operates by separately encoding the predecessor, segment, and successor CGs into distinct graph embeddings. These embeddings are then concatenated and fed into a multi-layer perceptron (MLP) regressor to predict the performance y of g. Stated more formally:
hp GN)(P);; h, GNN(s:); hc GNN(C); y= MLP((oncat(hr, lisc hc))-
It is also possible to predict performance using the entire CG, y MLP(GNN(2)), However, PSC predictor enjoys several advantages over this approach. By separately encoding the (P.S. C partitions, the PSC predictor is sensitive to the position and context of the segment 8; within the overall network. This allows us to more directly estimate the performance impact that mutating s; will have. As shown in Figure 3. we considering mutating y into g by replacing the source segment 8; with a segment S We want the mutant network to outperform the original, i.e., y² > Our training process emphasizes learning a separate embedding for each 8; in our segment database D. It encodes the required knowledge to estimate the effect of small changes from segment to any replacement segment st given fixed and C.
Experimental Results
We construct our database by extracting segments from CIFAR-10 33
benchmark families: NAS- Bench-101 (0B- 771. NAS Ben-heenhh-201 (NB-201) [17]. HiAML, Inception, and Two-Path [48]. Initially, we set the BPE vocabulary size 2000 and obtain database with 428 unique segments after filtering out isomorphisms. Segments vary in size ranging from primitives (containing single operation node) to blocks with up to 16 nodes and edges. The average segment contains 5 nodes and 3 edges, and some segments are disconnected subgraphs spanning parallel branches of a CG. We provide in-depth statistics and visualizations in Section A.I
In the remainder of this section, we apply AutoGO and our Segment Database to search for better architectures on several NAS benchmarking families to demonstrate the benefits of our framework. We further use AutoGO to improve several open-sourced, popular network architectures. We consider various high-resolution CV tasks, including Classification. Semantic Segmentation and Human Pose Estimation, with the aim of improving hardware friendliness in terms of FLOPs. We also provide examples of deployment where AutoGO minimizes the energy consumption or on-chip latency of already lightweight neural networks for Super Resolution and Image Denoising using cycle simulator for a Huawei Neural Processing Unit (NPU). We provide implementation details, dataset metrics, and training setup in Sections A.2 and A.4
4.1 Rank Correlation of Performance Predictors
AutoGO uses a neural predictor to esti- mate the performance of mutated archi- tectures. We train and evaluate our PSC predictor on five CIFAR-IO benchmarks. Our CG format provides the advantage of training simultaneously on multiple benchmark architecture families. We split each family into training, valida- tion, and testing partitions containing 80%, 10% and 10% of the overall CGs in that family. We combine the training
Table 1: Test SRCC of all 5 architecture families for the PSC predictor and baselines. Results averaged over runs.
Arch. Family
GNN
PSC 1:1 Ratio
PSC
NB-101
0.627 + 0.031
0.666 + 0.025
0.849
0.054
NB-201
0.809 1 0.016
0.865 1 0.015
0.983 1 0.003
HIAML
0.010 + 0.013
0.170 + 0.042
0.734
+ 0.031
Inception
0.209 + 0.037
0.066
+ 0.071
0.496
0.022
Two-Path
0.023 1 0.018
0.236 0.043
0.724 0.022

---

Table 2: AutoGO results across all 5 CIFAR-I0 architecture families while aiming to increase accuracy [%]] and reduce FLOPs [1e6]. We consider experimental configurations that vary in unit of mutation and predictor used. We bold and italicize the best and second best result per family.
Baseline Architectures
Operator + GNN
Segment
GNN
Segment PSC
Family
Acc.
FLOPs
Acc.
FLOPs
Acc.
FLOPs
Acc.
FLOPs
NB-101
95.18%
11722
95.16%
9407
95.31%
10817
95.45%
11118
-0.02%
-19.75%
+0.13%
-7.72%
+0.27%
-5.15%
NB-201
93.50%
313
93.37%
232
93.57%
294
93.84%
303
-0.13%
-25.88%
+0.07%
-6.07%
+0.34%
-3.19%
NiAML
92.32%
246
92.00%
198
92.62%
168
92.75%
198
-0.32%
-19.51%
+0.30%
-31.7%%
+0.43%
19.51%
Inception 93.20%
494
92.97%
319
93.31%
467
93.52%
474
-0.23%
-35,43%
+0.11%
-6.68%
+0.32%
4.05%
Two-Path 87.90%
116
88.63%
106
89.16%
48
88, 9.%
97
+0.73%
-8 6..2%%
+1.26%
-58.62%
+1.04%
-21.55%
partitions for each family to form an overall training set for the predictors while setting the test partitions aside individually, When training the PSC predictor, we partition each CG into multiple S. C} instances to use as training samples. We compare our proposed PSC predictor with two baselines: As each CG contains multiple (P. C}} instances. we consider an intermediate setting, PSC 1:1 Ratio, where we only consider one random S. C} instance per CG in the training set. Moreover, we also consider a baseline GNN that estimates the performance of whole unpartitioned CGs but is not sensitive to segment-level changes.
We measure the Spearman's Rank Correlation Coefficient (SRCC) of each predictor on the test partitions for each benchmark family. SRCC is defined in the range [-1, 1] and higher values are better. Table Soobee[ssmmne summarizze our results. We note the exceptional performance of the PSC predictor as it can obtain SRCC above 0.72 on HiAML and Two-Path while the GNN barely achieves positive SRCC. Moreover, while the GNN and PSC 1:1 predictors can obtain SRCC above 0.8 and 0.6 for NB-201 and NB-101, respectively, if we train the PSC predictors on all (P. S. C} samples, we can obtain a near perfect SRCC of 0.98 on NB-201 and almost 0.85 on NB- 101. Overall. these findings demonstrate the merit of our segment decomposition and PSC encoding scheme for CGs.
4.2 Improving CIFAR-10 NAS Benchmark Architectures
We test the effectiveness of AutoGO by refining the best architectures from each family. Specifically, AutoGO aims to increase accuracy while reducing FL.OPs. We consider three scenarios that allow us to ablate the effectiveness of our PSC predictor when applied to search. We also compare our segment-level mutation to a simpler, operation-leved mutation that mutates single primitive operation.
We run AutoGO for 10 iterations in the segment-level mutation, and 50 iterations for the operation- level mutation for fair comparison since segments have nodes on average. At the end of each iteration, we randomly select 10 architectures from the accuracy-FL.O for the next iteration as parent architectures. For each parent candidate, we consider up to 100 replacement mutations. We allow AutoGO to mutate sequences of simultaneously. We randomly mask out 50% of segments with more than node in our segment database and force BPE to segment the input with the remaining ones. Further, we consider two search settings that limit the FI.OPs decrease of child architectures. In the first case, we allow AutoGO to freely reduce FLOPs, while in the second case, we do not allow FLOPs to fall by more than 20% relative to the original network we optimizing. After the search is complete, we train architectures on the accuracy-FL -FOPS Pareto frontier times on CIFAR- 10 [33. We report the accuracy and FLOPs of the overall best architecture found across both FLOPs constraint settings. Finally, it takes 45 to 90 minutes to execute the search depending on the size of the input architecture CG. We provide an ablation study across FLOPs constraints, a detailed breakdown of wall-clock time cost, and enumerate our hardware platform in Sections A.6 A.7 and A.9 respectively.
Pareto frontier to qualify
contiguous source segments
Table 2 reports our findings across all 5 architectures families. We observe that the segment-level mutation a better fit for finding high-performance architectures, as the best architectures are found using it. For example, on HiAML, it can increase the accuracy by up by 0.43% while reducing
7

---

Table 3: Results running AutoGO Computation Graphs for ResNet-50, 101 and VGG-16. Specifi-
cally, we compare ImageNet [58] Top- 1pp-1/Top-5 accuracy, Cityscapes test mloU [4 using a PSPNet head (761, MPII [4] PCK as well as FLOPs. For performance metrics, higher is better. We measure latency on an Nvidia RTX 2080 Ti GPU using an input resolution size of 224 x 224.
Architecture
ImageNet Top-1/5
Cityseapes mloU
MPII PCK
FLOPs [1e9]
Lat. [ms]
ResNet-50 Original
74.02%/991.255
63.42%
82.36%
6.29
7.18
ResNet-50 AutoGO Arch
75.34% 16%
65.88%
84.07%
6.71
7.50
ResNet-50 AutoGO Arch 2
75.66%/92.45%%
66.65%
82.70%
5.88
6.92
ResNet-101 Original
75.09%%/91 .94%
65. 65.92%
82.77%
13.76
15.86
ResNet-101 AutoGO Arch
76.56%/93.095
67.12%
83.59%
13.66
15,56
ResNet-101 AutoGO Arch 2
75.699//92. 15%
66.38%
84.64%
13.35
15.36
VGG-16 Original
74.18%/91 83%
65.36%
85.92%
30.81
4.65
VGG-16 AutoGO
74.91%//3.239%
66.91% %
85.99%
24.34
4.20
FLOPs by -9..76%. By contrast, the operation-level mutation only manages to improve performance on Two-Path. However this gain of +0.73% is substantially less than what segment mutation. On MAAs-Bench- 101, operation mutation manages to break even with the baseline architecture, while incurring accuracy drop of more than 0.10% all other families.
achieve using
Next, we compare the effectiveness of the PSC and GNN predictors. The PSC predictor finds the best architecture of the 5 architecture families. PSC improves accuracy on NB-101 and NB-201 by 0.34% and 0.27%, respectively. By contrast, the GNN only achieves the best performance on Two-Path, which is the smallest benchmark family with a baseline architecture of only 116 MegaFLOPS: Thus, considerable changes
ResNect Block
ReLU
Maintainn 1024 channels-
Conv
BN
segment-level mutations span that are distinguishable with GNN and PSC predictors. sum, the segment-aware encoding is better increasing performance while reducing FLOPs than the operation- level mutation. Moreover, results demonstrate the superiority of the PSC predictor compared to the GNN in most cases.
ReLU
Pool
Reduce to 256 channels
Conv
BN
ResNet Block
AutoGO
Segment
ReLU
Mutation
+
Conv
+
BN
4.3 Application to High-Resole Resolutio Classification, Segmentation and Pose Estimation
To demonstrate the extensibility and generalizability of our framework, apply several stand-alon, architectures for higher-resolution computer vision tasks. Specifically, perform NAS using AutoGO with the PSC predictor and segment-leve mutation for iterations on ResNet-50, ResNet- 101 2 and VGG-16 [61]. For fair comparison, we do not allow AutoGO to select segments containing operations that were not available or popularized when the network was first proposed, e.g., depthwise convolu- tions (59
Conv
HiAML Block
ResiNet Block
ReLU
Conv
Add
Figure 4: Example of segment mu- tation from that helped create ResNet- 50 AutoGO Arch 2 (Tab. B A ResNet block is replaced by HiAML block.
After the search, we examine the architectures on the Pareto frontier and select 1-2 with noticeably different FLOPs reductions to train and evaluate against the original architecture. To form the first point of comparison, we train each network on ImageNet [58] Then, we fine-tune the network on different tasks. For Semantic Segmentation (SS), we use a PSPNet [76 head structure and fine-tune Cityscapes [14] to obtain mean Intersection over Union (mloU) performance. For Human Pose Estimation (HPE), we adopt the method of (78) to fine-tune on MPIT 4 to measure the Percentage of Correct Keypoints (PCK) of architecture.
Table 3 shows our results on ImageNet, Cityscapes, and MPII. First, we note how every case, the architectures generated by AutoGO consistently outperform the original on all 3 CV benchmarks.

---

Table 4: Peak Signal-to-Noise Ratio (PSNR) for EDSR the DIV2K validation set and several SR
benchmarks in the 2x upscaling setting. Higher is better. We measure latency on an RTX 2080 Ti.
SR Architecture
DIV2K
Set5
Set14
BSD100
Urban 100
Mangal09
FLOPs [1e9]
Lat. [ms]]
EDSR Original
36.19
36.86
32.57
31.39
29.14
36.09
141
18.04
EDSR AutoGO Arch I
37.28
38.01
33.62
32.18
31.56
38.49
118
15.38
EDSR AutoGO Arch 2
37.27
37.97
33.55
32.16
31.53
38.47
110
14.52
EDSR AutoGO Arch 3
37.25
38.01
33.58
32.16
31.46
38.44
105
13.81
Table SR PSNR results on Proprietary FSRCNN networks. FSRCNN- (3, 4) denotes the number of Conv3x3 operations in the middle of the architecture. We report change in power according to a cycle-accurate simulation model that uses a 64x640 input resolution. FLOPs [1e9] are measured using input resolution of 640x360.
SR Architecture
Set5
Set14
BSD100
Urban100
Manga109
Power [mW]
APower
FLOPs
FSRCNN-3 Original
35.12
31.43
30.56
27.65
32.75
774.77
2.67
FSRCNN-3 AutoGO
35.12
31.43
30.56
27.64
32.60
644.10
-16.87%
2.09
FSRCNN-1 Original
35.22
31.50
30.60
27.71
32.88
892.89
3.74
FSRCNN-4 AutOOO
35.17
31.52
30.60
27.71
32.77
508.37
-4306%%
2.07
For example, ResNet-50 AutoGO Arch outperforms the original by over 1.64% ImageNet top-1 accuracy, while the found architecture VGG outperforms the original Cityscapes by 1.55% mloU. Also, we measure inference latency on an RTX 2080 Ti GPU. We note some correlation between FLOOPs and GPU latency; as metric increases decreases, so does the other metric.
Figure 4 illustrates how AutoGO splices HiAML segment into ResNet-50 to create a new architec- ture. The longer branch performs multiple convolutions at reduced channels, while the shorter branch applies lightweight operations on the original number channels, and the MILP performs resolution propagation to ensure functionality.
4.4 Application to Super Resolution with EDSR
We use AutoGO to optimize networks for Super Resolution (SR). Specifically, we optimize the backbone feature extractors of EDSR 38 As the original EDSR only uses convolution and ReLU operations, we not let AutoGO select segments that contain depthwise, pooling, or batch nor- malization. Figure [ (Sec. (A8) (.8)....)))))))))) provides sample illustrations of the mutations AutoGO performs on
the 2x resolution setting and evaluate on several Table demonstrates how EDSR architectures produced by AutoGO can handily outperform the original network while substantially reducing FLOPs and GPU latency, e.g., AutoGO Arch 3 is 36 gigaFLOPs smaller and 4.2ms faster.
EDSR. We train SR networks on DIV2K 2
29
public benchmarks [8] [4 44 28 45 3
4.5 Using AutoGO to Automate Neural Network Deployment on a Neural Processing Unit
We demonstrate the real- world deployment capabili- ties of AutoGO by optimiz- ing neural network perfor- mance using cycle-accurate counter that simulates Huawei NPU performance for cell- phones [37]. We optimize for power or on-chip latency by pairing pretrained PSC ac- curacy predictor with power/latency measurements fed back by either a hardware profiling tool or the cycle-accurate hardware simulator.
Table 6: Results of using AutoGO to optimize a Proprietary U-Net Denoising network to improve PSNR and minimize on-chip latency. We report changes in latency and power measured on a mobile NPÚ using a cycle simulation model.
Denoising
PSNR
ATatency
Power [mW]
APower
FL.Pss [1e9]
Base Model
139.4
724.59
17.05
AutoGIO 139.9
-24.94%
657.82
-9.21% %
16.26
Super Resolution Power Optimization We use AutoGO to optimize proprietary lightweight SR models similar to FSRCNN (16). as well as the change in power and FL.OPs. We note the effectiveness of AutoGO at optimizing the energy efficiency of even small network, e,g., the FSRCNN-4 AutoGO variant can reduce the
the network performance on several public datasets

---

instantaneous power of an already small FSRCNN (with 4 Conv3x3 in the body network) by over 43%, while the FSRCNN-3 AutoGO variant reduces it by over 16%. Moreover, AutoGO maintains or even enhances the PSNR performance as compared to the original networks, demonstrating the generalizability of the pretrained PSC predictor to other tasks.
Image Denoising Latency Optimization We use AutoGO to optimize a proprictary Image Denoising U-Net similar [55] to reduce on-chip latency. Table 6 reports our findings on an in-house dataset. We observe how the mutated network can exceed the original denoising PSNR by 0.5. While substantially improving latency, we have also reduced other resouree consumption metries including power and FLOPs.
Limitations and Future Discussions
The AutoGO framework consists of many components: frequent subgraph mining (FSM) via topolog- ical sorting and BPE tokenization, the position-awand PSC predictor, the mutation- based evolutionary strategy and use of Computational Graphs. Each of these components has its own strengths and weaknesses. Our paper demonstrates the feasibility of using topological sorting and BPE to per- form FSM, although it faces limitations due to the non-deterministic nature of topological sorting, resulting in generation of segments for isomorphic subgraphs that must be filtered out from database. However, the primary strength of FSM through topological sorting and BPE is the economic advantage of speed, neither BPE-based segment extraction nor isomorphic segment filtering is time-consumingg even on large Computational Graphs. Morcover, FSM only considers the frequency of a given subgraph (represented as segment) while ignoring its contribution to performance and hardware-friendlig
metrics. Extracting frequent subgraphs that can explain performance is a subject for further studies.
The quality of our segment database depends on the types of operations and subgraphs present in the benchmark families we extract from. For example, a few segments in our database use depthwise convolutions (see Fig.55p in Sec.[A.]] as the only DAS-Benchmark we consider that contains them is Inception, and in limited quantity. These were not widely used in experiments, since achieve a fair comparison with the baseline architectures that AutoGO aimed to improve, we constrained the vocabulary of AutoGO during the search to use only same generation of operations. On the flip side, one could use AutoGO to mine newer operations like depthwise convolutions, StarReLU (72), even older operations that have gained popularity like GELU [25). Segments containing these operations could then be used to further refine older architectures like ResNets, EDSR, and FSRCNN for performance improvement.
future variant of AutoGO could replace the mutation-driven search with a policy network [35] to select replacement segments. Another avenue for future research is performing frequent and important computational subgraph mining for Transformer and attention- based models for their hardware- hardware-friendly deployment, as the Computational Graph representation and subgraph mining presented in this paper are principally designed for convolutional neural networks currently.
6 Conclusion
We propose AutoGO, or Automatic Graph Optimization, new framework for optimizing neural networks outside the bounds of predefined, fixed search spaces. AutoGO represents architectures using computation graph format of primitive operations. We partition computation graphs into segment subgraphs using Byte-Pair Encoding. Using segment database and guided by a predictor which sensitive to segment size and position, AutoGO modifies the network by incrementally mutating its segments while a resolution propagation MILP ensures network functionality. We build segment database by extracting vocabulary of segments from 5 open-source NAS benchmarks using Frequent Subgraph Mining. We use AutoGO to improve the accuracy of the best architectures from each of the 5 CIFAR-10 search spaces while reducing FLOPs. Furthermore, we use AutoGO to evolve several oper-sourced large CNNs, including ResNets, VGG-16, 16, and EDSR, and successfully improve their performance on a breadth of CV tasks with reduced or comparable FLOPs. Finally, we demonstrate how to utilize AutoGO to automatically reduce the hardware energy consumption and on-chip latency of realistic convolutional neural network applications, when deployed onto a mobile Neural Processing Unit
10

---

References
[1] Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: A system for large-scale machine learning. In OSDI, number 2016, pages 265-283. Savannah, GA, USA, 2016.
[2] Eirikur Agustsson and Radu Timofte. Ntire 2017 challenge on single image super-resolution: Dataset and study. In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
[3] Kiyoharu Aizawa, Azuma Fujimoto, Atsushi Otsubo, Toru Ogawa, Yusuke Matsui, Koki Tsub- ota, and Hikaru Ikuta. Building manga dataset "mangal09 109" with annotations for multimedia applications. IEEE MultiMedia, 27(2):8-11)) 18, 2020.
[4] Mykhaylo Andriluka, Leonid Pishchulin, Peter Gehler, and Bernt Schiele. 2d human pose estimation: New benchmark and state of the analysis. In IEEE Conference on Computer Vision and Puttern Recognition (CVPR), June 2014.
[5] Junjie Bai, Fang Lu, Zhang, et al. Onnx: Open neural network exchange. https://githa: com htte//onx/ooe onnx
2019.
[6] Gabriel Bender, Hanxiao Liu, Bo Chen, Grace Chu, Shuyang Cheng, Pieter-Jan Kindermans, and Quoc V Le. Can weight sharing outperform random architecture search? investigation with tunas. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14323-14332, 2020.
[7] Hadjer Benmeziane, Kaoutar El Maghraoui, Hamza Ouarnoughi, Smail Niar, Martin Wistuba, and Naigang Wang. A comprehensive survey on hardware-aware neural architecture search. CoRR, abs/2101.09333 00933,, 2021.
[8] Marco Bevilacqua, Aline Roumy, Christine Guillemot, and Marie Line Alberi-Morel. Low- complexity single-image super-resolution based on nonnegative neighbor embedding. 2012.
[9] Han Cai, Chuang Gan, Tianzhe Wang. Zhekai Zhang, and Song Han. Once for all: Train one network and specialize it for efficient deployment. In International Conference on Learning Representations, 2020.
[10] Daoyuan Chen, Yaliang Li, Minghui Qiu, Zhen Wang, Bofang Li, Bolin Ding, Hongbo Deng, Jun Huang, Wei Lin, and Jingren Zhou. Adabert: Task-adaptive bert compression with differentiable neural architecture search. arXiv preprint 2.Xi::0011.04246 2020.
[11] Xin Chen, Lingxi Xie, Jun Wu, and Qi Tian. Progressive differentiable architecture search: Bridging the depth gap between search and evaluation. In Proceedings of the IEEE International Conference on Computer Vision, pages 1294-1303, 2019.
[12] Krishna Teja Shitty-Venkata, Murali Emani, Venkatram Vishwanath, and Arun K Somani. Neural architecture search for transformers: A survey. IEEE Access, 10:108374-108412, 2022.
[13] Yuanzheng Ci, Chen Lin, Ming Sun, Boyu Chen, Hongwen Zhang, and Wanli Ouyang, Evolving search space for neural architecture search. 2021 IEEE/CVF International Conference on Computer Vision (ICCV), pages 6639-6649, 2021.
[14] Marius Cordts, Mohamed Omran, Sebastian Ramos, Timo Rehfeld, Markus Enzweiler, Rodrigo Benenson, Uwe Franke, Stefan Roth, and Bemt Schiele. The cityscapes dataset for semantic urban scene understanding. In Proc. of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
[15] Xiaoliang Dai, Alvin Wan, Peizhao Zhang, Bichen Wu, Zijian He, Zhen Wei, Kan Chen, Yuandong Tian, Matthew Yu, Péter Vajda, and Joseph E. Gonzalez. Fbnetv3: Joint architecture- recipe search using predictor pretraining. 2021 IEEF/CVE Conference on Computer Vision and Pattern Recognition (CVPR), pages 16271 (6271-16282 162800, 2021.

---

[16] Chao Dong, Chen Change Loy, and Xiaoou Tang. Accelerating the suser-resolution convolu- tional neural network. European conference on computer vision, pages 391-407. Springer, 2016.
[17] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In International Conference on Learning Representations, 2020.
[18] John Forrest and Robin Lougee. CBC User Guide, pages 257-277. 09 2005.
[19] Philippe Fournier- Viger. Chao Cheng, Jerry Chun-Wei Lin, Unil Yun, and R Uday Kiran. Tkg: Efficient mining of top-k frequent subgraphs. In Big Data Analytics: 7th International Conference, BDA 2019, Ahmedabad, India, December 17-20, 2019, Proceedings pages 209-226. Springer, 2019.
[20] Philip Gage. A new algorithm for data compression. Users Journal, 12(2):23-38, 1994.
[21] Ehsan Goodarzi, Mina Ziaci, and Edward Zia Hosscinipour. Introduction to optimization analysis in hydrosystem engineering. Springer, 2014.
[22] Fred X. Han, Keith G. Mills, Fabian Chudak, Parsa Riahi, Mohammad Salameh, Jialin Zhang, Wei Lu, Shangling Jui, and Di Niu. general-purpost transferable predictor for neural architecture search. In Proceedings of the 2023 SIAM International Conference on Data Mining (SDM). SIAM, 2023.
[23]
William E. Hart, Carl D. Laird, Jean-Paul Watson, and David L. Woodruff. Pyomo - optimiza- tion modeling in python. Springer Optimization and Its Applications, 2012.
[24] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770-778, 2016.
[25] Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint arXiv:1606.084. 08415, 2016.
[26] Andrew Howard, Mark Sandler, Grace Chu, Liang-Chieh Chen, Bo Chen, Mingxing Tan, Weijun Wang, Yukun Zhu, Ruoming Pang, Vijay Vasudevan, et al. Searching for mobilenetv3. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 1314-1324, 2019.
[27] Jun Huan, Wei Wang, Jan Prins, and Jiong Yang. Spin: mining maximal frequent subgraphs from graph databases. Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, 2004.
[28) Jia-Bin Huang, Abhishek Singh, and Narendra Ahuja. Single image super-resolution from transformed self-exemplars. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 5197-5206, 2015.
[29] Andrey Ignatov, Radu Timofte, et al. Pirm challenge on perceptual image enhancement on smartphones: report. In European Conference on Computer Vision (ECCV) Workshops, January 2019.
[30] Zhihao Jia, Oded Padon, James Thomas, Todd Warszawski, Matei Zaharia, and Alex Aiken. Taso: optimizing deep learning computation with automatic generation of graph substitutions. In Proceedings of the 27th ACM Symposium on Operating Systems Principles, pages 47-62, 2019.
[31] Chuntao Jiang, Frans Coenen, and Michele A. A. Zito. A survey of frequent subgraph mining algorithms. The Knowledge Engineering Review, 28:75 105, 2012.
[32] Nikita Klyuchnikov, Ilya Trofimov, Ekaterina Artemova, Mikhail Salnikov, Maxim Fedorov, Alexander Filippov, and Evgeny Burnaev. Nas-bench-nlpy neural architecture search benchmark for natural language processing. IEEE Access, 10:45736-45747 2022.
[33] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical Report, 2009.
12

---

[34] Taku Kudo and John Richardson. SentencePiece: A simple and language independent subword tokenizer and detokenizer for neural text processing. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 66-71, Brussels, Belgium, November 2018. Association for Computational Linguisties.
[35] Kwei-Herng Lai, Daochen Zha, Kaixiong Zhou, and Xia Hu. Policy-gnn, Aggregation opti- mization for graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 461-471, 2020.
[36] Zhuo Li, Hengyi Li, and Lin Meng. Model compression for deep neural networks: A survey. Computers, 12(3):60, 2023.
[37] Heng Liao, Jiajin Tu, Jing Xia, Hu Liu, Xiping Zhou, Honghui Yuan, and Yuxing Hu. Ascend: a scalable and unified architecture for ubiquitous deep neural network computing Industry track paper. 2021 IEEE International Symposium on High- PirforPereo Computer Architecture (HPCA), pages 789-801, 2021.
[38] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee. Enhanced deep residual networks for single image super-resolution. In Proceedings of the IEEE conference on computer vision and pattern recognition workshops, pages 136-144, 2017.
[39] Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.
[40] Shun Lu, Yu Hu, Peihao Wang, Yan Han, Jianchao Tan, Jixiang Li, Sen Yang, and Ji Liu. Pinat: A permutation invariance augmented transformer for nas predictor. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2023.
[41] Shun Lu, Jixiang Li, Jianchao Tan, Sen Yang, and Ji Liu. Tnasp: A transformer-based nas predictor with a self-evolution framework. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 15125-15133 Curran Associates, Inc., 2021.
[42] Zhichao Lu, Ian Whalen, Vishnu Boddeti, Yashesh Dhebar, Kalyanmoy Deb, Erik Goodman, and Wolfgang Banzhaf. Nsga-net: neural architecture search using multi-objective genetic algorithm. In Proceedings of the genetic and evolutionary computation conference, pages 419-427,2011
[43] Renqian Luo, Xu Tan, Rui Wang, Tao Qin, Enhong Chen, and Tie- Yan Liu. Semi-supervised neural architecture search. Advances in Neural Information Processing Systems, 33:10547- 10557, 2020.
[44] David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A database of human seg- mented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In Proceedings Eighth IEEE International Conference on Computer Vision. ICCV 2001, volume 2, pages 116-423. IEEE, 2001.
[45] Yusuke Matsui, Kota Ito, Yuji Aramaki, Azuma Fujimoto, Toru Ogawa, Toshihiko Yamasaki, and Kiyoharu Aizawa. Sketch- kketch-based manga retrieval using mangal09 dataset. Multimedia Tools and Applications, 21420)22111-21183 2017.
[46] Gaurav Menghani. Efficient deep learning: A survey making deep learning models smaller, faster, and better. ACM Computing Surveys, 55(12):1-37, 2023.
[47] Keith G Mills, Fred X Han, Mohammad Salameh, Seyed Saeed Changiz Rezaei, Linglong Kong, Wei Lu, Shuo Lian, Shangling Jui, and Di Niu. 1.2nas: Learning to optimize neural architectures via continuous-action reinforcement learning. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2284-1293, 2021.
[48] Keith G. Mills, Fred X. Han, Jialin Zhang, Fabian Chudak, Ali Safari Mamaghani, Mohammad Salameh, Wei Lu, Shangling Jui, and Di Niu. Gennape: Towards generalized neural architecture performance estimators. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023,
13

---

[49] Keith G. Mills, Fred X. Han, Jialin Zhang. Seyed Saeed Changiz Rezaci, Fabián A. Chudak, Wei Lu, Shuo Lian, Shangling Jui, and Di Niu. Profiling neural blocks and design spaces for mobile neural architecture search. Proceedings of the 30th ACM International Conference on Information & Knowledge Management, 2021.
[50] Keith G. Mills, Di Niu, Mohammad Salameh, Weichen Qiu, Fred X. Han, Puyuan Liu, Jialin Zhang, Wei Lu, and Shangling Jui. Aio-p: Expanding neural performance predictors beyond image classification. In Proceedings of the AAAI Conference on Artificial Intelligence, 2023.
[51] Christopher Morris, Martin Ritzert, Matthias Fey, William Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe, Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 4602-4609 2019.
[52] Adam Paszke. Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024-8035. Curran Associates, Inc., 2019.
[53] Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pages
2019.
[54] Seyed Saced Changiz Rezaci, Fred X Han, Di Niu, Mohammad Salameh, Keith Mills, Shuo Lian, Wei Lu, and Shangling Jui. Generative adversarial neural architecture search. Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 2227- 2234. International Joint Conferences on Artificial Intelligence Organization, 8 2021. Main Track.
[55] Olaf Ronneberger, Philipp Fischer, and Thomas Brox. U-net: Convolutional networks for biomedical image segmentation. In Medical Image Computing and Computer-Assisted Intervention 2015: 18th International Conference, Munich, Germany, October 5-9, 2015, Proceedings, Part III 18, pages 234 241. Springer, 2015.
[56] Binxin Ru, Xingchen Wan, Xiaowen Dong, and Michael A. Osborne. Interpretable neural architecture search via bayesian optimisation with weisfeiler-lehman kernels. In ICLR, 2021.
[57] Robin Ru, Pedro Esperança, and Fabio Maria Carlucci. Neural architecture generator optimiza- tion. In Advances in Neural Information Processing Systems, volume 33, pages 12057-12069, 2020.
[58] Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. Imagenet large scale visual recognition challenge. International journaa of computer vision, 1 115(3)2111-55) 2015.
[59] Mark Sandler, Andrew Howard, Menglong Zhu, Andrey Zhmoginov, and Liang- Chieh Chen. Mobilenetv2: Inverted residuals and linear bottlenckks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 45 4510-4520, 2018.
[60] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. ArXiv, abs/1500 50990999999 2015.
[61] Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409. 2014.
[62] Yanan Sun, Handing Wang, Bing Xue, Yaochu Jin, Gary G. Yen, and Mengjic Zhang. Surrogate- assisted evolutionary deep learning using end-to-end random forest-based performance predictor. IEEE Transactions on Evolutionary Computation, 24(2):350-364, 2020.
[63] Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pages 6105-6114, PMLR, 2019.
14

---

[64] Alvin Wan, Xiaoliang Dai, Peizhao Zhang, Zijian He, Yuandong Tian, Saining Xie. Bichen Wu, Matthew Yu. Tao Xu, Kan Chen, Péter Vajda, and Joseph Gonzalez. Fbnetv2: Differentiable neural architecture search for spatial and channel dimensions. 2020 IEEE/CVF Conference on Computer Vision and Puttern Recognition (CVPR), pages 12962-12971, 2020.
[65] Colin White, Arber Zela, Robin Ru, Yang Liu, and Frank Hutter. How powerful are performance predictors in neural architecture search? Advances in Neural Information Processing Systems, 34:28454-28469, 2021.
[66] Ross Wightman. Pytorch image models. 2019.
pytorch-image-mode
[67] Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. Pe-darts: Partial channel connections for memory-efficient architecture search. In International Conference on Learning Representations, 2020.
[68] Xifeng Yan and Jiawei Han. gspan: graph- based substructure pattern mining. 2002 IEEE International Conference on Data Mining, 2002. Proceedings. pages 721-724, 2002.
[69] Xifeng Yan and Jiawei Han. Closegraph: mining closed frequent graph patterns. In Knowledge Discovery and Data Mining, 2003.
[70] Yichen Yang, Phitchaya Phothilimthana, Yisu Wang, Max Willsey, Sudip Roy, and Jacques Pienaar. Equality saturation for tensor graph superoptimization. Proceedings of Machine Learning and Systems, 3:255-268, 2021.
[71] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. 10s-bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pages 7105-71144 14, 2019.
[72] Weihao Yu, Chenyang Si, Pan Zhou, Mi Luo, Yichen Zhou, Jiashi Feng, Shuicheng Yan, and Xinchao Wang. Metaformer baselines for vision. arXiv preprint arXiv:2210. 13452,, 2022.
[73] Arber Zela, Julien Niklas Siems, Lucas Zimmer, Jovita Lukasik, Margret Keuper, and Frank Hutter. Surrogate NAS benchmarks: Going beyond the limited search spaces of tabular NAS benchmarks. In International Conference on Learning Representations, 2022.
[74] Roman Zeyde, Michael Elad, and Matan Protter. On single image scale-up using sparse- representations. In International conference on curves and surfaces, pages 711-730. Springer, 2012.
[75] Hengshuang Zhao. semseg.
semseg 2019.
[76] Hengshuang Zhao, Jianping Shi, Xiaojuan Qi. Xiaogang Wang, and Jiaya Jia. Pyramid scene parsing network. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2881-2890, 2017.
[77] Ce Zheng, Wenhan Wu, Chen Chen, Taojiannan Yang, Sijie Zhu, Ju Shen, Nasser Kehtarnavaz, and Mubarak Shah. Deep learning-based human pose estimation: A survey, ACM Computing Surveys, (6(1):11130016 2023.
[78] Xingyi Zhou, Qixing Huang, Xiao Sun, Xiangyang Xue, and Yichen Wei. Towards 3d human pose estimation in the wild: A weakly-superrised approach. In The IEEE International Conference on Computer Vision (ICCV), Oct 2017.
[79] Barret Zoph and Quoe V Le. Neural architecture search with reinforcement learning. In International Conference Learning Representations, 2017.
15

---

Input Segment
Output Segment
Degree Segment
Degree Segment
150
150
Segmeri
Segments
Segments
Segments
2.00
1.00
800
50
50
Input
Output Nodes
Degree
Degree
Node Histogram
Edge Histogram
Topologies Per Segment Size
Operation Frequency
Unique Toppologies
Sogments
Segments
Segments
60
Nodes per Segment
Edges Segment
Nodes per Segment
Cony
Droetweto Linear
daccistion
Ave. Fool Mak Pooo Add
Conca
Figure 5: Histograms of segment database statistics including number of input and output nodes/degrees, nodes/edges per segment, unique segment topologies and operation frequency.
A Supplementary Material
A.1
Additional Database Statistics
Figure 5
provides histograms regarding our segment database. Additionally, we enumerate the primitive operations that are only present in specific MAS-Benchmark families:
Depthwise: Inception.
Max Pool: NB-101, Inception and Two-Path.
Concat: N01,01, Inception and Two-Path.
All other operation primitives, e.g., Cony, ReLU, BatchNorm, etc., are present across all CIFAR-10 NAS- MAS-Benchmarrs.
A.2 Predictor and Dataset Details
We further elaborate on the baseline GNN and PSC predictors from Section 4.1 implementation details, dataset statistics and data pre-processing techniques. We train our predictors for 40 epochs with a batch size of 32 and an initial learning rate of le-4.
We provide
A.2.1 Baseline and PSC Predictor Setup
We use the same baseline GNN predictor GENNAPE 48
First, CGs are given input into an initial set of embedding layers that transform discrete node features, such as operation type, input/output tensor resolution, kernel size, and bias, into continuous vector. The node embeddings are then fed through series of 6 k-GNN [5]] layers. Next, an overall graph embedding is computed by taking the mean all node embeddings. A simple MLP with hidden layers predicts performance using the graph embedding.
The PSC predictor differs in that each CG sample is first split into its respective Predecessor, Segment, and suCcessor subgraphs before being fed into the predictor. All three subgraphs are processed as separate CGs by the node embedding and l:- G-G layers produce three distinct graph embeddings. We concatenate these graph embeddings feature-wise and feed them into an MLP to generate a prediction. Also, node embedding and k-GNN layer weights shared for each subgraph type.
16

---

A.2.2 Dataset Statisties and PSC Preprocessing
We train and evaluate the baseline GNN predictor ev- ery unique CG sample. Additional steps are required to train the PSC predictor since each CG comprises many segments and can decompose into many distinct {P, S, C}} subgraph sets.
Table Number of Computation Graphs (CG), segment samples and test SRCC folds for each family. We randomly sam- ple 5k NB-101 architectures and only con- sider NB-201 networks that do not have the "none' operation.
For the intermediate baseline, PSC 1:1 Ratio Table we randomly sample 1 {P. SP representation from each segmented CG in our training dataset. Hence, the number of samples equals the original number of training instances. For the full PSC predictor, we remove this restriction and consider all possible {P.S. C} decompo- sitions which drastically increases the number of samples.
Arch. Family
CGs
Segments
Folds
NB-101
5.0k
404.9k
42
NB-201
4096
252.8k
34
HiAML
4.6k
65.1k
10
Inception
580
222.4k
129
Two-Path 6.9k
193.1k
10
Table 7 lists the number of CGs and (P.S, C} samples per family. While each {P, C) sample for given CG focuses on a different network segment, they still describe the same overall architecture and thus retain the same accuracy label. Therefore, when measuring test SRCC on the PSC predictor, we divide the test data into folds. Each fold contains only one (P,SSC) C} instance of a given CG. This avoids introducing additional ties in the ground-truth labels when calculating SRCC. The number of folds is equal to the minimum number of segments in any test CGs or 10, whichever is smaller. Therefore, we calculate the overall test SRCC by averaging SRCC across each fold.
A.3 Segment Extraction with BPE
We compare our BPE subgraph extraction ap- proach to the Weisfeiler-Leman (WL) Kernel
method adopted by NAS-BOWL [56] in terms of efficiency. NAS-BOWL applied it on the orig- inal, shallow cell-based network representation of NAS- Ben---enchh000 with depth of 2. We use the WL-kernel on the CG-level and enumerate all subgraphs with maximum depth 5. The time and RAM costs of using the WL-kernel scale poorly increase the number of graphs and nodes per graph. For example, it takes at least hours extract and count subgraphs from each NAS-Benchmark family. Moreover, we could not use more than 1k CGs from the HiAML or NB-201 families (~110 and 250 nodes per CG, respectively) without facing memory issues on the rack server described in Section A.9
ReLU-1
Prai-1d
Donu2
BN
BN-16
BhA
Telllie
Pool-112
Cono7
BW--331
BN--a
Addd-i
Asdi-o
Pook-100
Pook-100
By contrast, approach brings several benefits over mining on large graphs with WL-kernels. The extraction process sequences is efficient. Using BPE enables segment extraction from all benchmark families (over 21k CGs per Tab. 7 simultaneouslyy in less than 20 minutes using around 10GB of RAM. Also, BPE provides seg- ments that are easier to mutate and alleviates lim- itations with WL-kernel extraction process by topologically ordering the nodes. Figure com- pares WL and BPE segmentations on a part of CG from the NAS MAS-Bench-201 family. The sub- graph extracted from the WL method (Fig. ((aa) cannot cover several nodes within its context (grey nodes of BN-8, Pool-10. BN-11. 1, and Add- 14) due to limited depth of 5 and several resid-
BK-11
Ad6-14
A05-14
Adc-17
WL-kernel
(b) BPE
Comparison between subgraphs ex- tracted with WL-kernel and BPE on a NAS-Bench- 201 cell. Nodes are numerically labeled by topo- logical ordering. Best viewed in color. Specifi- cally, WL-kernel extracts one large subgraph con- sisting of all highlighted nodes (greyed-out nodes are omitted). For BPE, all nodes are extracted into one subgraph, denoted by a unique color.
Figure 6:
17

---

AAA-
Add-0
Add-0
PALU-
Pook-16
Retuir
Piokli
Poak-13
PelDi
Posli
Pock-15
ReLLin
Pookl
Poos-13
Como>
BN-6
B1--88
F8A-5
AN-10
RK--10
BF4-3
Pooki ReLU-
BN-3
ReLLid
Pool-
BN-3
RaLLAG
Pooks
DN-3
ReLLid
Pos-
SP4-6
DK-a
Di-h
Addl
Add
Adole
Pool-10
Psok-10
BN-11
BN-11
BH:11
A43-14
AdS-17
AED-17
Asp-17
AGS-17
Figure 7: Example of how the BPE-segmented graph in Figure bb) is partitioned into Predecessor, Segment and suCcessor subgraphs based on the selected segment. Specifically, we highlight nodes of the selected segment in purple, the predecessor in grey and the successor in yellow.
This exacerbates the mutation process. In contrast, segmentation with BPE (Fig. 6(b)) spans different subgraph sizes denoted by separate colors.
connections.
A.3.1 PSC Partitioning with Parallel Branches
Figure illustrates how a Computational Graph with multiple branches can be cleanly partitioned into different S, C} based the choice of segment st. Although the input CG has multiple parallel branches, the use of topological sort to assign ordered numerical labels to each node. The numerical labels of each node in segment contiguous, while parallel branches assigned to either the Predecessor or suCcessor according to their numerical labels.
A.4 Architecture Training Hyperparameters
We elaborate the training recipes evaluate input baseline architectures well those found by AutoGO.
A.4.1 CIFAR-10 Families
We the CG representation of the initial and mutated architectures instantiate networks and train them using TensorFlow. We evaluate CIFAR-10 networks by training them times for 200 epochs with batch size of 256. We optimize the models using RMSProp with an initial learning rate of le and a momentum factor of 0.9. We anneal the learning rate according to a cosine schedule.
A.4.2 ImageNet, Segmentation and Pose Estimation
When evaluating ResNet and VGG architectures, we first train on ImageNet [58 using timm 666 with a batch size of 1024. We use an initial learning rate of 0.1 which we anneal using cosine schedule. We optimize the model using Stochastic Gradient Descent (SGD) with momentum factor of 0.9 and a weight decay of 1e-1, We set gradient clipping value of 5.0 and use label smoothing with 0.1. We train ResNets for 200 epochs and VGG-16 for 100 epochs. We save the trained weights to fine-tune on other tasks.
We evaluate Semantic Segmentation performance using semseg 75 The PSPNet 766 head requires two inputs to implement properly. The first is the final latent tensor that originally feeds into the
Base model batch normalization
18

---

classifier head, while the second requires grafting an auxiliary residual connection 3/ 3/4ths of the way through the network feature extractor. Furthermore, we adjust the dilation factor and strides of all convolution and pooling operations in the later part of the network to limit downsampling. After loading the pretrained ImageNet weights, we fine-tune on Cityscapes [4 images cropped to 713 for 200 epochs using batch size of 16. We use SDG with an initial learning rate of 0.01, momentum factor of 0.9, and a weight decay of 1e-
We implement 2D Human Pose Estimation using 78 To convert an ImageNet network, we remove the classifier layers and then append series of 'Deconvolution
wrronooltiio--BacchNrrm-- BatchNorr--eer Re blocks which gradually upsample the latent tensors from 8 to 64². We train on MPII [4] images cropped to 256² 140 epochs with batch size of 32. We optimize our networks using Adam, setting an initial learning rate of 1e" 3 for ResNet-50 and VGG-16, and 5e for ResNet- 101. We reduce the learning rate by factor of 10 at epochs 90 and 120. Finally, we report performance in terms of the Percentage of Correct Keypoints (PCK), specifically the Percentage of Correct Keypoints at a head-neck distance
of 0.5 (PCK (h0.5) 77
A.4.3 Super Resolution
We train networks on DIV2K in the 2x upsampling setting for 1000 epochs with a batch size of 16. We set an input patch size of 64 for EDSR and 48 for FSRCNN. We minimize the L1 loss using the Adam optimizer with initial learning rate of le-4, which we reduce using cosine decay schedule.
A.4.4 Image Denoising
We train networks on a custom in-house patch size of 128 for all networks. We train each network for 2k epochs under a batch size of 128. We minimize the L1 loss using the Adam optimizer with an initial learning rate le and a final learning rate of Te reduced over polynomial schedule.
dataset with 7k images. We set an input
A.5 Additional AutoGO Search Details
We provide additional details on the AutoGO search algorithm from Section 3.2
Algorithm 1 Sample AutoGO pseudocode for one iteration
1: Input: Pareto frontier O
Only contains the input architecture at iteration 0.
2: Input: Segment Database
3: Input: Performance Predictor p and FLOPs counter f.
4: Gş =Sample(O, k)
> Sample l architectures
5: for g G do
6: PSC, =
b Empty list of mutants
7: S,y Segmenl D)
8:
for E Sample(SS,) do
D Source segments
9:
{P, Purlition for s* SSample(s, D) do (P.s", C} M uttate(P, if MILP (C)) finds a solution then Add (P.s*, C) to PSC,
10:
>> Sample replacement segments
12:
Resolution propagation
14:
end if end for end for
16:
17:
for All mutated (P.8", 8", C} PSC, do
18:
Profile (P. 8* C} using p and f Update O using (P,s", P7 " C) and profiled information.
20:
end for
21:
end for
19

---

A.5.1 AutoGO Pseudocode Algorithm
Algorithm I provides example of how the AutoGO search procedure executes one iteration. AutoGO selects parent architectures from the Pareto frontier O. It then uses the segment database D to select source and replacement segments to create mutant child architectures. The resolution propagation MILP ensures the mutants constitute valid architectures. Finally, AutoGO places the child architectures on the Pareto frontier O according to their performance and hardware- www.warr-ffeeelnnsss.s.
A.5.2 Node Labeling
Before segmentation with BPE, we label nodes in the CG in the form of [current operation, incoming operations, outgoing operations]. We encode each unique node label with a single Chinese character symbol, as they span wide range of symbols compared to other languages.
A.5.3 Selecting a Sparse BPE Vocabulary
When generating V' as vocabulary set utilized by BPE to segment CGs, we include all single-node segments as these represent the irreducible primitive operations that must exist within the vocabulary in some form and only filter out multi-node segments.
A.5.4 Selecting Non-Pareto Optimal Architectures
When transitioning from iteration to 1, select k architectures from the Pareto frontier O and search history serve as parents. If we have suffi- cient architectures on the Pareto fron- tier, |O] 2 k, we randomly sample from it. However, if |O] < k. there is an ar- chitecture deficit. We compensate for this deficit by selecting non-Pareto op- timal architectures that aim achieve our search objective. We select these ar- chitectures by ranking them in terms of predicted accuracy and FLOPs, where higher and lower are better, respectively. We then sum these ranks and select the non-Pare non-Pareto optimal architectures with the lowest rank sum. provides a simple example of this process. Note how the selection mechanism excludes architectures that have high performance but are too large, as well as underperforming architectures.
Table 8: Example of the minimum sum of ranks selection algorithm with deficit architectures.
Acc. [%]
Rank
FLOPs
Rank
Rank Sum
Selected?
91.21
0
260
5
5
No
91.10
|
215
2
3
Yes
91.02
2
200
0
2
Yes
90.75
3
210
Yes
90.35
220
No
89.05
5
250
4
9
No
A.5.5 Segment Selection
For each CG g, we sample a set of m source segments 8;. We sort the segments Sy by FLOOPs and then we select the m/2 segments with the lowest FLOPs while randomly sampling the rest.
A.5.6 Accuracy Predictions and FLOPs Constraints
Once we have set of valid source and replacement segments, we use the PSC predictor to select mutations that yield the most significant accuracy gain. We use FLOPs calculator proprietary profiling tool for measuring NPU latency/power) to further filter these mutations by rejecting child architectures whose FLOPs deviate too far from the FLOPs of the input architecture.
A.5.7 Resolution Propagation
always lead to solution, meaning the replacement segment for mutation at this position and generate a valid CG. We cast this task as a search problem over the height, width, and channel resolution values the replacement segment operations. The search spans mutable operations such as convolutions and pooling, The rest of the operations are immutable and only forward the resolution without changing its sizes, such as add, activation functions, and batch normalization. During the search, we limit the adjustments on the values of height, width, and channel sizes doubling, halving, or keeping the same.
Adjustment
be used
20

---

Our solution is based on Mixed Integer Linear Programming (MILP). MILP is an optimiza- tion problem formulated with linear objectives, linear constraints, and integer-valued variables. The input to MILP is the replacement segment DAG, Each node has two variables per each height, width, and channel dimension, denoting input and output resolutions. Each edge is asso- ciated with "flow" variable. We define MILP constraints that regulate the correct flow of reso- lution. Immutable nodes have imput resolutions equal to output resolutions. The output resolu- tion for mutable nodes is less than equal to the input resolution. The model is optimized to achieve the expected resolution at the output nodes. The model is proven infeasible if the search fails achieve expected output resolu- tions.
32,32,16
Predecessor
ReLU
32,32.16
32,32,16
Input resolutions: (32,32,16) and (32,32,16)
Conv 16,16.32
BN 32,32,16
+ BN
RelU 32.32,16
16,16.32
Replacement Segment
Conv 16, 16,32
We briefly illustrate the resolution propagation process. Figure [ shows a replacement segment (yellow) that is being put together with the Pre- decessor (blue) and Successor (green) partitions of the network. We provide the output reso- lution of each operation in the form of (height, width, channel). Notice how the number of input and output nodes of the replacement segment matches the number of output and input nodes of the Predecessor and Successor, respectively. Initially, the replacement segment expects input dimension sizes for its 'Conv' and 'BN' opera- tions of (32. 32, 16), which are the resolutions of the Predecessor's output nodes. Also, the Succe- sor expects an input size of (16, 16, 32), which demands the replacement segment to output feature map with this dimension at the 'Add' op- eration. This requires adjusting the resolution of the 2 mutable 'Conv' operations in the replacement segment (highlighted with red borders). Notice that adjusting one of them or leaving resolutions unadjusted will result in incorrect propagation because the 'Add' operations require its incoming tensors to have the exact same dimensions. We use MILP to solve this problem by finding the correct adjustment to mutable operations by halving, doubling, or maintaining resolution sizes.
16, 16,32
16,16,32
Expected output resolutions: (16,16,32)
16, 16,32
SuCcessor
Figure 8: Resolution propagation adjusts the res- olution of mutable operations in the replacement segment. The Height, Width, and Channel sizes are adjusted in both 'Conv' operations that the replacement segment yields the expected output resolution at the 'Add' operation.
A.6 CIFAR-10 FLOPs Restraint Ablation
Table provides a full ablation study of AutoGO on all 5 CIFAR-10 families in terms of FLOPs reduction constraint. We consider two settings where AutoGO can reduce FLOPss by most -20% relative to the baseline architecture, or can reduce them freely (-100%), while always limiting FLOPs increases to be at most + +10% We again note how the best architecture for each family was found using segment mutations.
We observe that the segment-level mutation is a better fit for finding pigh-peeformance architectures under wider FLOPs constraints. For example, on HiAML, the segment-mutation cannot improve the accuracy of the base architecture when we impose FLOPs reduction limit of -20%, yet it can increase the accuracy by up to 0.43% on average when we remove the restriction, even though the best architecture only reduces FLOPs by -1..76% From this result, we infer that FLOPs restrictions hamper the exploration of the segment-level mutation. The only family where the -20% FLOPS constraint produces a better architecture than the no-constraint setting is Inception, which is already the largest family with base model size of nearly 500 MegaFT .O.s. By contrast, the operation-level mutations require FLOPs reduction constraints to break even with the baseline
21

---

Table 9:
Full ablation study of AutoGO on all 5 CIFAR-10 families considering choice of mutation
unit [Operation, Segment), predictor [GNN, PSC) and FLOPs [1e6] reduction (6) constraint (-20%, -100%); 1, extending the results of T For each experiment, report the accuracy [%] and FLOPs [1e6] (raw and A relative to the baseline). We bold and italicize the best and second best result per family, respectively.
Baseline
Operator + GNN
Segment + GNN
Segment+ + PSC
Family (6FLOPs)
Acc.
FLOPs
Acc.
FLOPs
Acc.
FLOPs
Acc.
FLOPs
NB-101 (-20%)
95.18%
11722
95.16%
9407
95.31%
10817
95.06%
9606
A
-0.02%
-19.75%
+0.13%
-7.72%
-0.12%
-18.05%
NB-101 (-100%)
93.12%
1591
95.25%
10513
95.45%
11118
-2.06%
-86.43%
+0.07%
-10.31%
+0.27%
-5.15%
NB-201 (-20%)
93.50%
313
93.28%
250
92.86%
250
93.32%
251
A
-0.22%
-20133%
+0.34%
-0.13%%
-0.18%
-19.81%
NB-201 (-100%)
93.37%
232
93.57%
294
93.84%
303
A
-0.13%
-25 88%
+0,07%
-600%%
+0.34%
-3.19%
HiAML (-20%)
92.32%
246
92.00%
198
92.08%
198
92.22%
230
A
-0.32%
-19.51% %
-0,24%
19.51%
-0.10%
-6.50%
HiAMI. (-100.--100%
84.63%
28
92.62%
168
92.75%
198
A
-7 77.69%
-88.6 88.62%
+0.30%
-31.71%
+0.43%
-19.51%
Inception (-20%)
93.50%
494
92.97%
399
93.12%
399
93.52%
474
A
-0.23%
-9.23%%
-0.08%
-99 19.23%
+0.32%
-4.05%
Inception (-100%)
92.97%
319
93. 93.31%
461
93. .0%%0%%
A
-0.23%
-35.43%
+0.11%
-6.68%
10%
-3.24%
Two-Path (-20%)
87.90%
116
88.63%
106
88.31%
93
88 68%
A
+0.73%
-8.62%
+0.41%
-19.83%
+0.78%
-18.97%
Twn-PathCC (-100%)
88.63%
106
89.16%
48
88, 94%
91
+0.73%
-8.62%
+1.26%
-58.62%
+1.04%
-21.5%%
architectures. For example, when FLOPs constraint is imposed, the operation-level mutation will find HiAML and NB-101 architectures that remove enough convolution nodes to reduce the model size by more than 85%. These changes drastically reduce the accuracy by over 7.5% HiAML.
A.7 AutoGO Components Evaluation
We evaluate the search efficiency on the benchmark families by measuring the speed of each com- ponent. The time to execute the search largely depends the choice of input architecture, i.e., architectures with more nodes and complex topologies like Inception form large search spaces. On the HiAML and NB-201 families, it takes 15 minutes on average to execute search iteration using the PSC predictor and segment-level mutation. AutoGO visits over 1000 unique architectures per iteration and can find high-performance architectures in around an hour less.
Specifically, takes around 1.5 to minutes to segment a parent architecture using BPE, select source and replacement segments, perform resolution propagation, and rank the mutations using the predictor. The bulk of this time is spent between searching the database for replacement segments, confirming their validity and measuring the performance of each mutation, while the BPE segmentation and source segment selection processes take less than millisecond each. When gauging execution time, sequentially mutate each parent architecture per iteration, but note that this process be sped up with parallelization.
Resolution propagation with MILP takes 0.11 seconds on average to find solution or determine that the problem is infeasible. We compare it to an exhaustive search approach by enumerating all candidate solutions. It takes, average, 0.4 seconds to find solution and more than 4 seconds for infeasible solutions. Our subgraph extraction process for generating the segment vocabulary is very efficient as the BPE operates on a sequence representation of the CGs. It takes less than 20 minutes to sort all CG topologically, and extract subsequences with BPE.
To provide specific examples of the search time, consider the ResNet-50 Arch 2 and EDSR Arch 3 architectures from Tables and 4. respectively. Mutating the initial ResNet-50 and EDSR CGs takes 1.8 and 1.5 minutes, respectively, on our hardware. It takes longer to mutate ResNet-50 simply because the CG contains more nodes (108) than EDSR, whose CG only has 67 nodes. Moreover, since the base EDSR architecture only uses Convolutions and ReLU operations, exclude segments
22

---

Network input
EDER Block
RwLU
EDGR Block
Rat
Comn
Rec
CoIN
Cono
Come
Corry
2 Convarting input blocks
3
RALU
3 x
EDOSR
Cont
ReUu
Cony
Cort
Converling ling middle blocks
Converting outpul blocks
Corry
PeLL
Add
Add
Conw
EDSR Block
EDSR Block
Nettvrri Curput
Ad0
Figure 9: Example mutations performed by AutoGO to create EDSR Arch 2 in Table 8 EDSR blocks. Specifically, AutoGO will swap multiple, simple Conv-ReLU-Cowe residual blocks for larger blocks that have operations on both branches.
4 by swapping
that contain batchnorm and pooling operations, which reduces the number of replacement segments to consider during mutation.
The first iteration of AutoGO mutates the initial architecture while all subsequent iterations mutate 10 parent architectures. Given that ResNet-50 Arch 2 was found in iteration 3, it took AutoGO around
1.8min + 2iter * 10arch/iter * 1.8min/arch = 33..min
discover that architecture. Likewise, EDSR Arch found in iteration 5, which took
1.5min 4iter 10arch/iter 1.5min/arch 61.55mn
to find. Finally, we note that these measurements and calculations assume sequential processing of parent architectures. In practice (e-g.. runtime numbers in See 4.2), we use muoti-processing
techniques to mutate multiple parent architectures simultaneously to further speedup the process.
A.8
EDSR Mutation Example
Figure illustrates three distinct mutations that take place to produce an EDSR AutoGO architecture. Initially, the EDSR backbone contains 16 "Cov-Rel.U--oom residual blocks. To create the mutant network, AutoGO removed 8 of these blocks, denoting half the backbone structure, and replaced them with three Couble-brance structures that also consist of just convolutions and ReLU activations.
A.9 Hardware and Software Setup
We run our experiments rack servers using Intel Xeon Gold 6140 CPUs. Each server is equipped with 8 NVIDIA V100 32GB GPUs and 756GB RAM. We execute our search and experiments on Python 3 using PyTorch==1.0 and TensorFlow==1, 15. We implement our predictors using EeTorch-Geometiice 7..1. We use SentencePiece
34 to perform BPE, Finally, we implement our MILP using Coin-CBC solver [8 and pyomo==6
23


Reviews:
[{"review_id": "mxBRiwaWrT", "reviewer": "Reviewer_MAXz", "summary": "The paper proposes to optimise neural networks by exploiting common subgraphs mined from existing NAS benchmarks - this is achieved by building a vocabulary from networks encoded into topologically sorted sequences and using byte-pair encoding (BPE) to obtain common sequences of operations. After that, a given neural network is segmented and different mined segments are considered as replacement for different identified segments in the given network, all done while taking care of shape propagation. Searching for the best replacement segments is done with a variation of a multi-objective evolutionary algorithm which optimizes for Pareto-efficiency using a proposed (GNN-based) PSC predictor.", "questions": "See weaknesses, plus a bonus question:  is there a technical reason to stick to (Chinese) characters when representing neural networks? It seems like the method could easily work with just arbitrary numbers instead, so I'm wondering if I missed something or if that's just an arbitrary decision\n\nAlso, some typos:\n\n  - line 49: replace \":\" with \".\"?\n - line 160: change to just \"AutoGO uses D\"? Right now this parts reads like \"AutoGO uses D according to D\" (since earlier it is said that \"segment dataset\" == \"D\")", "limitations": "No discussion about limitations - the presentation is actually quite one-sided, by only considering benefits of the proposed method. For example, using BPE is said to \"bring several benefits\" over methods like WL but not a word about possible downsides (worse handling of isomorphic graphs).", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": " - generalizing blocks to segments is an interesting and sensible step towards more flexible NAS\n - the proposed system seems technically advanced, taking care of quite a few corner cases in a convincing way (e.g., solving resolution propagation with linear programming)\n - encoding neural networks as sequences and using BPE is an interesting take on representing neural networks (but could be studied in more details)\n - the proposed PSC predictor seems like an interesting variation of the more standard GNN-based predictors\n - experiments are designed to support claims made in the paper (but results are somewhat hard to interpret, see below)\n - the method (at least after all one-time cost) seems fast, finishing within a few of hours at most", "weaknesses": " - Clarity could be improved in certain places\n    - \"First, benchmarks (...) requires training the new architecture from scratch\" - why is this relevant for the presented work?\n    - \"(...) predictors learn using high-level cell representation (...), In contrast, AutoGO can mutate an architecture (...)\" - why are these two things compared to each other? The ability to mutate beyond an original design space (by the way, this is a tricky thing to formally define, I would appreciate an attempt at that) is orthogonal to a predictor's ability to capture spatial information of a network. Many NAS algorithms achieving similar (or even greater) coverage of architecture than the proposed work, e.g., LEMONADE or $\\mu$NAS seem particularly relatable since they utilise mutations towards a similar goal as AutoGO (mutating away from the original design).\n    - there seem to be some contradictory information presented regarding what operations are used, first we read (line 43): \"(...) by evolving its underlying computation graph (CG) using its original primitive operations.\", but then (line 58): \"A vocabulary of segments are mined from a large number of CGs from several NAS benchmarks\", please clarify\n    - The provided definition of PSC does not seem to properly cover nodes parallel to $s_i$.\n    - If $s*$ has more than one input, how does the method handle assigning P's outputs to a replacement's inputs? (and analogously for S) Is it a part of the LP problem?\n    - it is unclear if a randomly initialized or a pretrained architecture is expected; I couldn't find any information about pretraining a network, but then line 225 says \"we retrain all the segment replacements\" suggesting the original segments might be trained already (?); it is also unclear why this retraining of segments is needed, considering a performance predictor is used, and how it is done\n - there is some overlap between the proposed method and blockwise NAS works, such as DNA, DONNA or LANA; I think it would be better if the authors acknowledged existence of this line of work, right now it is completely ignored, despite high-level similarities\n - I think the authors should discuss in more details their choice of using toposort+BPE to mine for subgraphs - this approach is bound to fail to recognize many isomorphic subgraphs as the same segments (hinted at the beginning of Section 4), why do you think this is not a problem? How does this greedy approach compare to other alternatives?\n - Results are, generally speaking, hard to compare to the rest of the literature. More specifically:\n    - apart from the common benchmarks (NB101, NB201), the paper uses HiAML, Inception and Two-Path - to the best of my knowledge, these are only used by a single, very recent (AAAI'23) paper; however, I don't see any benefits stemming from this choice while it does make comparison to other works harder\n    - FSRCNN and U-Net experiments use proprietary networks and tools and, on top of that, only relative improvements are reported in some cases; rendering these experiments basically unverifiable and unusable by the community\n - at the same time, some of the reported results are not particularly convincing, such as:\n    - baseline EDSR 2x upscaling performance is actually significantly worse than reported in the original 2017 (!) paper, $\\Delta$ PSNR of: -1.25, -1.35, -0.93 and -3.79 for Set5, Set14, B100 and Urban100, respectively. Results are better for DIV2k (I have to assume the authors mean DIV2k validation set), but that's just one dataset out of 5 (and the one used for training), \n    - the proprietary FSRCNN also achieves significantly worse results than its parent model, while requiring approx. 150x more FLOPS (!!!)\n    - ResNet-50 and ResNet-101 baselines are also worse than reported in the original paper (ImageNet), not to mention any recent improved training recipes\n - it is actually not very clear, but following on the information presented in Section 4.1, it appears that the results in Table 2 were obtained by using a predictor pretrained on 80% of the data available for each benchmark (at least that's the only information we are presented about predictor training, so I'm assuming that's the case for subsequent sections as well); this means that the improvements presented are actually occupied by a very high, hidden cost of having lots of in-domain training data, while in many cases they are not significant\n - perhaps I missed that, but I couldn't find information about the cost of all the pretraining etc.\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1 Comparison to LEMONADE/uNAS/Blockwise NAS\nAutoGO differs from these works. LEMONADE uses network morphism (3.1) rules “Inserting a Conv-BatchNorm-ReLU block”. AutoGO uses diverse, data-driven subgraphs of up to 15 nodes for mutation. uNAS predefines a traditional macro NAS structure in Table 1. \nBlockwise NAS work in a predefined backbone structure, e.g., Fig. 2 of DONNA shows a defined search space over N blocks. DNA and LANA are both distillation teacher-student NAS frameworks that adjust layers/channels per block. The goal of AutoGO as a novel automated toolchain for ML engineers is to eliminate the predefined structure in NAS and to automatically edit the CG of an input architecture with fine-to-coarse segment vocab. It automates the inference acceleration of an architecture on the target hardware without reinventing or limiting the backbone to a manual choice.\n\n### W2 PSC Parallel Segments/Multiple Inputs\nThis is handled by topological sort applied prior to BPE. Numerical labels are assigned to each node, indicating its position in a sequence. Nodes/segments parallel to S would be allocated to P or C. See Figure 6(b) in the supplementary materials and Figure 9 in our global response PDF. Also, if there are multiple valid mappings from P to S (or S to C), then AutoGO chooses one at random.\n\n### W3 Toposort+BPE Isomorphisms/Comparisons\nThe choice of toposort+BPE is a tradeoff between result completeness (extract all subgraphs) and accuracy (estimate subgraph count) for efficiency (memory). While relaxing the problem into mining segments from sequences instead of graphs would hinder recognizing isomorphisms, it enables extracting subgraphs from a multiple CG families and overcome memory inefficiencies. By converting back the extracted subsequences into their original subgraph form, we are able to recognize isomorphism among extracted subgraphs. We compare to WL-Kernel and show the speedup of our approach compared to [1], who extract motifs. However, WL-kernel has disadvantages. Primarily, it does not scale well with the size of the graph in terms of RAM and execution time. This limited the number of CGs we could consider at a time so we couldn’t perform extraction over all CGs in a NAS benchmark dataset (we can with BPE). Even on a subset of graphs extraction took at least 6 hours (BPE takes less than half the time). We describe this comparison and provide a figure in Supp. Section A.3.\n\n### W4 Results hard to compare to the rest of the literature; use of newer benchmarks \n1.\tPrior literature finds architectures amongst a predefined search space. In Sec. 4.2, we show that even the best architectures from 5 existing NAS benchmarks can be edited by AutoGO for improved accuracy and lower FLOPS, showing the bottleneck in NAS is the manually designed search space in the first place, not the search algorithm. Therefore, the AutoGO concept is new; it can edit and mutate an existing architecture for better accuracy/faster inference, an ability that the prior works lack because they would define their own search space of backbones/blocks, which limits performance. \n2.\tUsing newer benchmarks increases the diversity/coverage of our segment database, which brings benefits to downstream tasks, e.g., Figure 4, where a HiAML block is adopted by a mutant of ResNet-50 by AutoGO. \n\n### W5 Comparing Tables 3-5 to the original papers\nWe want to clarify that rather than advancing the training performance of EDSR, ResNet50/101, the goal of experiments in 4.3 (Tabs. 3, 4)  is to show that even on established neural architectures and on GPUs, AutoGO can still automatically optimize these architectures for more efficient computation. This ability of automatically generating better architectures based off original architectures is no coincidence and is verified through extensive experiments on multiple networks.\n\nThe performance metrics we report are not directly comparable to the top-1 or PSNR numbers reported in the original papers for two reasons: To provide a fair comparison between our baseline architectures and the mutants optimized by AutoGO, we use a function provided by the CG API to instantiate a trainable model from the CG (as the mutant architectures returned from AutoGO use this format) which results in some implementation differences between the CG-instantiated model and the model definition in the original source code (as the CG API needs to be general enough to support many architectures). Second, our training hyperparameters (Supp. Section A.4) differ from the original papers, e.g., the original EDSR paper uses an input patch size of 48 and halves their learning rate at specific steps. We use a patch size of 64, a cosine scheduler, and train for less time.\n\nThese changes produce results which are not directly comparable to what is originally reported but not always worse, e.g., our baseline VGG16 exceeds the VGG16-BN result reported in torchvision (74.18% vs. 73.36%) and our AutoGO optimized architecture further improves this to 74.91%. Also, all of our CIFAR-10 results in Table 2 use the same training setup, and our baseline performance is higher on NB101 (94.24% vs. 95.18%) than what is originally reported.\n\n### Bonus Question\nBPE works best when applied to sequences of atomic characters, e.g., a single character like ‘A’, '1' or ‘壹’ represents a single meaningful entity (one node in the case of CGs). We originally tried representing nodes with English characters but found there were not enough of them given our “node|incoming|outgoing” format, so we simply switched to Unicode Chinese characters.\n\nReferences:\n\n[1] \"Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels\" - ICLR 2021."}, {"review_id": "hrRhTyjfjc", "reviewer": "Reviewer_sA4y", "summary": "This paper introduces AutoGO, an innovative method for evolving neural networks that addresses the challenges of efficiency, low power consumption, and hardware compatibility. AutoGO represents deep neural networks (DNNs) as computational graphs (CGs) comprised of low-level primitives and employs an evolutionary segment mutation algorithm. Notably, AutoGO employs subgraph mining from CGs while utilizing efficient tokenization through Byte Pair Encoding (BPE) from natural language processing (NLP) instead of Weisfeiler-Lehman (WL) kernels. For the evolutionary mutation process, AutoGO leverages neural prediction to explicitly consider positional and contextual information when replacing segments within a CG.\n\nThe experimental results demonstrate that AutoGO performs exceptionally well on NAS benchmarks and exhibits promising applications in various domains, including classification, semantic segmentation, human pose estimation, and super resolution.\n\nIn summary, this paper presents a novel and effective approach. The writing style is particularly engaging, making it a pleasure to read. I recommend accepting this paper.", "questions": "1. Can the mutation algorithm effectively handle the computational demands of scaling up to large computation graphs? I'm curious to know if it can cope with the complexities involved in processing massive graphs efficiently.\n\n2. When it comes to modeling PSC, does employing a more advanced graph neural network like Graph Transformer provide notable advantages? Or is the choice of GNN design less influential in this particular scenario?\n\n3. Is there a possibility to substitute the mutation algorithm with a GNN policy? I'm interested to hear about any experiences or insights regarding the potential applicability of GNN policies in this context.\n", "limitations": "Please provide a limitation section for future researchers!", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "\n1. The motivation behind this work is excellently articulated, providing a clear understanding of the research objectives and driving factors.\n\n2. The paper effectively describes recent works in the field, highlighting their significance and comparing their novelty to the proposed method. The related work section is comprehensive and enjoyable to read, showcasing a thorough understanding of the existing literature.\n\n3. This method is technically robust, demonstrating impressive performance across various evaluations. The experimental results validate its effectiveness and reliability, further strengthening the credibility of the approach.", "weaknesses": "\n1. Although the method presented in the paper is highly technical, the focus seems to be predominantly on the technical details rather than providing a comprehensive analysis and intuitive explanations. While I acknowledge the complexity of the method, I believe that enhancing the final manuscript with more analytical insights and intuitive discussions would significantly improve its overall quality.\n\n2. Consider including a simplified pseudocode or algorithmic representation of the method. This would greatly facilitate the understanding of the algorithmic steps and enhance clarity for readers. A concise and structured representation of the method's flow would be beneficial in aiding comprehension.\n\n3. I recommend revising Figure 1 to present the information in a horizontal format. This adjustment would enhance the visual clarity and make it easier for readers to follow the different components and relationships depicted in the figure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "First, we will add some intuitive explanations to the manuscript and more limitation discussions. The current framework effectively solves the AutoGO problem to mutate CNNs for faster inference and hardware-friendly deployment for a range of CV tasks/networks.\n\nNote that we do provide more information on the analytics of our segment database and a comparison with the WL-kernel of [1] for segment extraction. However, due to the page limit, we had to relegate that material to the supplementary while keeping experimental results that demonstrate the effectiveness of AutoGO on a wide range of tasks, networks and hardware-friendliness metrics in the main manuscript. \n\n### W2/3  Simplified pseudocode and Fig. 1\nThanks for the feedback. We have provided an algorithm latex float in the PDF attached to the global response and will definitely revise Figure 1 to give it a horizontal focus.\n\n### Q1 Handling large computation graphs. \nYes. In terms of CG size, the largest NAS benchmark we consider is Inception, where the average number of nodes per CG is 673 and the largest CG has over 1500 nodes. By contrast, the next largest benchmark is NB-201, whose largest CG has 336 nodes (half the mean number of nodes Inception has), so Inception contains many massive graphs, yet not only are we able to optimize the best Inception CG, we mine common segments across all Inception CGs to form our database. Granted, AutoGO execution time scales with number of nodes, so optimization on Inception does take longer than NB-201. In Supp. Section A.7 we provide a breakdown contrasting execution time for ResNet-50 (larger CG, 1.8min/arch mutation time) vs. EDSR (smaller with 1.5min/arch mutation time).\n\n### Q2 Modeling PSC using a more advanced GNN like Graph Transformer \nIt is possible to use a more advanced, potentially attention-based GNN and see performance improvements which is an exciting avenue for future work. In this paper, we establish a framework that we could build on top by improving its components, such as the PSC predictor, the search algorithm, and the database, which could result in speedup in the whole search process and better performing mutant architectures. \n\n### Q3 Mutation for a GNN Policy\nIt is interesting for future work to consider a GNN policy-based mutation approach that would model the sampling, aggregate nodes based on their importance, and better capture structural information. This could speed up the mutant-selection process and guide the search toward better candidate replacements that positively affect performance. \n\nReferences:\n\n[1] \"Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels\" - ICLR 2021.\n"}, {"review_id": "mcciXpUmYI", "reviewer": "Reviewer_A8eP", "summary": "This paper presents the AutoGO framework, which operates directly on the Computation Graph (CG) of a given DNN architecture. It splits the CG into segments and conducts a search process. Through extensive experiments, the paper shows that AutoGO effectively improves the performance of the top architectures in various public architecture benchmarks. Furthermore, AutoGO demonstrates its capability to automatically optimize different types of large CNN architectures and achieve enhanced results in various computer vision tasks.", "questions": "1. Does the node label contain channel information? The definition is mainly about the graph structure and it seems missing the channel information. And in that way, how would the custom framework adapt to the choice of width, depth, and kernel size?\n2. What if the Segment Database is based on some widely used architecture including Conv, MLP, and transformers rather than the NASBenchmark architecture? Would the generated architecture still perform better than the current Pareto front?\n3. The choice of the search space covers results mainly in small datasets such as CIFAR-10. How do we use these accuracies to train an accuracy estimator in other datasets or even for different tasks?", "limitations": "Please refer to the weakness part. \n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The whole framework from tokenization and mutation to estimation is reasonable and technically sound. \n2. It operates the complex problem of directly processing the computation graph and verify on several difficult tasks.", "weaknesses": "1. The verification for the ImageNet task is missing. \n2. The searched model is highly limited in the current segment database since it only contains the benchmark architectures which are not widely used in different tasks.\n3. The training of the accuracy estimator highly relies on the existing collected accuracy and model data pairs. And it would be hard to transfer with only limited accuracy numbers for other datasets and other tasks. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1 Verification on ImageNet\n\nWe indeed provide evaluation for ImageNet tasks by training ResNet-50/101 and VGG16-BN on ImageNet and then further fine-tune these architectures on Cityscapes (Semantic Segmentation) and MPII (Human Pose Estimation). We report the results in Table 3 and list our training/fine-tuning setup in Supplementary Section A.4.\n\n###  W2 Searched models are limited as the segment database only contains benchmark architectures\nOur segment database does not contain the benchmark architectures themselves, but rather the frequent subgraph segments extracted from these diverse benchmarks in a data-driven way. The segments range from 1-node primitive operations (e.g., conv, relu, pooling, add, concat, etc.), most of which are universally present in CNN architectures, up to more complex 15-node/16-edge subgraphs (e.g., the HiAML subgraph used in Figure 4) that vary greatly in terms of computations and hardware-friendliness. For instance, ResNet residual blocks consist of the 'Conv-BN-ReLU' sequence which is in our database, as is the Max Pool operation VGG use for downsampling. Our segments also generalize across different CV tasks, like EDSR [1], which do not use BatchNorm for Super Resolution and instead opt for simpler 'Conv-ReLU-Add' sequences which are also present in our database. \n\n### W3/Q3 The training of the accuracy estimator highly relies on the existing collected accuracy and model data pairs, which is hard to transfer\nIn this paper we do not attempt to train a predictor to estimate the exact task and/or dataset performance of a given architecture. Note how we use Spearman's Rank Correlation Coefficient (SRCC) in Table 1 to evaluate our PSC predictor, which only considers the relative rankings of predictor outputs compared to the ground truth. Rather, our PSC predictor is designed to focus on a how specific segment $s$ in an architecture contributes to the overall performance given its position relative to the rest of the architecture (represented by $P$ and $C$). We do this in order to estimate if replacing (mutating) $s$ with a new segment $s^*$ from our database will bring performance benefits. As such, when AutoGO is optimizing an architecture CG, the predictor acts as a 'proxy' where higher predictor outputs correspond to better architectures. In our experiments on multiple CV tasks and datasets, like ImageNet Classification, Semantic Segmentation on Cityscapes, Human Pose Estimation on MPII as well as Super Resolution on DIV2K/Set5/Set15/etc., and even Denoising using a proprietary in-house dataset, the mutated, hardware-friendly architectures found by AutoGO provide superior performance which validates our approach. \n\n### Q1 Does the node label contain channel information? How would the custom framework adapt to the choice of width, depth, and kernel size?\nYes, all CG nodes contain input/output height, width, channel (HWC) tensor size information, while nodes with learnable weights (e.g., Conv, Linear) contain weight tensor size (e.g., convolution kernel size) and a bias boolean as node features. \n\nTherefore, when we use AutoGO to optimize a given input architecture (e.g., ResNet, VGG, EDSR, etc.), we know the HWC information of every operation node that comprises said architecture. During mutation our resolution propagation MILP attempts to adapt replacement segments $s^*$ from our database to match the input/output HWC of the predecessor $P$ and successor $C$ of the input architecture. The MILP accomplishes this by tweaking the strides of convolution/pooling nodes in order to adjust HW as well input/output channels of convolution nodes in the replacement segment $s^*$. We do not adjust the kernel size of convolution operations. Note that in some cases the MILP may not find a solution, e.g., if $s$ performs downsampling, yet $s^*$ does not contain any nodes that can perform downsampling (conv or pooling ops) the proposed mutation {$P, s^*, C$} is deemed infeasible.\n\n###  Q2 What if the Segment Database is based on some widely used architecture including Conv, MLP, and transformers rather than the NASBenchmark architecture?\nCurrently, our database spans a wide range of subgraphs/segments that are used in various convolution-based computer vision models. Our framework could be extended to extract subgraphs from Transformer models which can enrich our database to further improve accuracy and hardware-friendliness. This is definitely a direction for future work given the rise of attention-based structures in computer vision architectures.\n\nReferences: \n\n[1] \"Enhanced Deep Residual Networks for Single Image Super-Resolution\" - CVPR'17.\n"}, {"review_id": "imKSEQe076", "reviewer": "Reviewer_AwFS", "summary": "This paper proposed a new NAS algorithm where a performance predictor is built for acceleration. In addition, the experiments are conducted for verification.\n============================\nThanks for the authors' rebuttal. Unfortunately, my concerns are still not addressed. For example, 1) the used data are not a benchmark, the reference also did not say it is a benchmark, while the authors believed it is a benchmark. I still believe the novelty of the work is very limited to the community, and cannot address the real concerns in the community.", "questions": "N/A", "limitations": "This paper ignores many more existing works on performance predictors, including the encoding of architectures in this topic. Compared to these existing works, the proposed algorithm in this paper has a very limit contribution.", "rating": 3, "confidence": 5, "soundness": 1, "presentation": 2, "contribution": 1, "strengths": "The search space is built on the segments of CG of DNNs.", "weaknesses": "Currently, \"performance predictor\" is more common than \"neural predictor,\" though they refer to the same thing.\n\nSome claims about neural predictors are not correct. For example, \"Neural predictors treat NAS benchmarks as datasets.\" In fact, the early works on this aspect did not use the NAS benchmarks as the dataset, and even these works were earlier than the NAS benchmarks. A baseline in this topic is [1], which is often compared with peer competitors.\n\n[1]  Sun et al., \"Surrogate-assisted evolutionary deep learning using an end-to-end random forest-based performance predictor,\" TEVC 2020.\n\nThe predictor is built on the subgraphs minded on NAS benchmarks. To this end, the constructed predictor cannot be generalized to other search spaces and can only be used for the same search space. As a result, the novelty of the work is limited.\n\nThe whole algorithm is very similar to the existing NAS algorithms, while the difference is that existing NAS algorithms use the search space composed of architecture units, while the proposed algorithm is based on the segments of CG of a particular architecture. While the motivation is not clear, why the use of segments of CG is more suitable?\n\nThe adopted optimization is indeed a multi-objective evolutionary algorithm, while it is called \"A Pareto front evolution strategy.\" In this case, the two objectives, i.e., accuracy and a chosen hardware-friendliness, are treated as conflicting objectives? If it is so, I would ask about the contribution of this work compared to the NAS algorithms falling into the multi-objective NAS algorithms, such as NSGA-NET.\n\nFor the example given: \"a Conv 3x3 node with incoming edges from Add and BatchNorm operations and an outgoing edge to a ReLU operation as \"conv2d3,in,add,batchnorm,out,relu\".\",  the information of kernel size and stride size have been removed. This involves the encoding of architecture, and there are multiple works in this aspect. Different architecture encodings have different impacts to the performance. Clearly, the one proposed in this paper lost information regarding the architecture.\n\nThe experiments on NAS-Benchmarks are not necessary enough because their search spaces are too simple. I suggest the authors check recent works on performance predictors.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "### W1 \"Some claims about neural predictors are not correct.\"\n\nEarlier works like [1] didn't use the term “NAS Benchmarks” as they were published prior to NAS-Bench-101 (which popularized the term). However, [1]'s Introduction says “The training data of the random forest are a set of data pairs, and each pair is composed of the CNN architecture and its performance.” This means the training data is still a benchmark set consisting of labeled architectures. Since 2020 benchmark has become common and usually refers to architectures labeled for performance. Our idea is to pretrain a predictor based on diverse enough families of labeled architectures (called benchmarks) so it generalizes well to other CNNs under generic CG representation.\n\n### W2 The predictor is built on the subgraphs mined on NAS benchmarks and cannot be generalized to other search spaces.\n\nThis is not true. The input to our PSC predictor are subgraphs of available CGs which provide a general architecture encoding. We can achieve generalization because the segments consist of primitive operations (nodes), e.g., Conv \n(torch.nn.Conv2d; tf.keras.layers.Conv2D), BN and ReLU, which are the smallest building blocks of CV models in general. Moreover, our segments are mined via BPE, which will first capture all possible single nodes (smallest granularity is one op) before considering any 2-node, 3-node,... subgraphs.  We train the predictor on a diverse range of NAS benchmarks (80% of 21k architectures) to achieve generalization to general form of CNNs.\n\nIn Tables 3-6, we showed that our predictor is generalizable to outside of the NAS Benchmark search spaces it is trained on. We use AutoGO with our PSC predictor to optimize architectures outside of NAS-Benchmarks like ResNets/VGG/EDSR/FSRCNN and even on other tasks. This is exactly in contrast to current predictors in the literature which use encodings to specific to their own cell/backbone design space and cannot generalize. \n\n### W3  Why the use of segments of CG is more suitable?\n\nFirst, existing NAS usually defines a search space and searches in that space, e.g., like most other works, [1] uses predefined macro skeletons and op sequences, and only considers a handful of blocks from classical networks like ResNet/DenseNet and pooling blocks and allocate them into a fixed macro skeleton. AutoGO aims to do NAS in a different way, it directly edits a given network's underlying CG (which unifies any network representation) in fine-to-coarse granularity to help ML engineers to fast mutate and deploy a famous network on devices. Our data-driven and algorithm-mined segments replace manual design choices and provide flexibility to mutate a network by single ops or by up to 15-node complex subgraphs (leading to more aggressive topology changes), e.g., Fig. 8 (Supp. Section A.8) shows how 8 classical EDSR residual blocks are replaced by 3 types of bigger blocks with operations on both parallel branches. These bigger blocks are generated using our algorithm-mined segment database and are very hard to be discovered manually for the task.\n\n### W4  the contribution compared to multi-objective NAS like NSGA-NET.\n\nMulti-objective NAS, which represents large literature, is not our contribution here. We just use a simple evolutionary algorithm to update the Pareto front under defined multiple objectives.  The contribution of AutoGO is a full framework that can directly mutate any input CNN (with our repo of ops and subgraphs discovered from data and without reinventing the search space) to yield a better one for the device (lower latency/GFLOPs and higher accuracy). Our results in Tables 3-6 show clear gains in this use case. \n\nWhile an early work NSGA-NET does not repeat phases (blocks), it still puts a lot of assumptions on search space design: \"for computationally tractability, we (NSGA-NET) constrain the search space such that each node in a phase carries the same sequence of operations, i.e. a 3 × 3 convolution followed by batch-normalization and ReLU.\"  This is incompatible with NB-201 that use a ReLU-Conv-BN ordering, or EDSR which argues against the use of BN for Super Resolution altogether. Using CG, AutoGO accommodates all of these cases. Another weakness the bit string encoding in NSGA-NET loses information from original graph when mutation and crossover are done on the bit strings. \n\n### W5 the encoding proposed in this paper lost information regarding the architecture.\n\nThe quoted sentence is not related to encoding at all. To clarify, the quoted sentence is only applicable to the segmentation process (a specific step when we convert the CG into a sequence before BPE segmentation). After segmentation, we then map the character-level segmentation back into the CG representation to partition them into subgraphs. In other words, our predictor is based on GNN trained on CGs directly, and AutoGO mutates directly on CGs (graphs) using mined segment database, which keeps all the kernel size, stride and input/output size and other information. Since this information is not lost we can do resolution propagation. It is a strength of this work that mutation is done on CGs directly (rather than on sequential encodings) without losing any information.\n\n### W6 The experiments on NAS-Benchmarks are not necessary enough because their search spaces are too simple.\n\nFirst, our experiments are not limited to NAS-Benchmarks. Tables 3-6 shows AutoGO can generalize and optimize a range of real-world CNN architectures (large or small) on diverse tasks/datasets. The goal of Table 2 is to show that AutoGO can even further optimize the “best” architectures in NAS each benchmark, which is something prior literature cannot achieve. Also, it shows that searching on manually designed search space is always not good enough, suggesting the necessity of a data-driven approach like AutoGO to directly edit the CG.  \n\nBased on these clarifications we hope the reviewer could reassess the contribution of the paper. "}]

Author rebuttal:
We would like to thank the reviewers for their constructive comments, for the suggested references, and for pointing out several typos, which we will fix. In addition to the individual responses, we are providing a PDF containing some new figures/tables.

We would like to clarify that the motivation of AutoGO is to provide an automated framework to help ML practitioners to optimize larger networks for deployment (with faster/lighter inference) on their target hardware (usually an edge device like cell phones or cameras instead of GPUs), such as FSRCNN on Super Resolution, and a U-Net on Image Denoising to optimize PSNR and latency/power for a mobile NPU. Most existing NAS is devoted to optimizing architectures by proposing a NAS search algorithm to explore the architectures or encodings of architectures in a manually defined search space, either pushing the accuracy to the limit or performing multi-objective search. However, none of the existing works will suit deployment and inference acceleration scenario above for several reasons:
1) When deploying an ML task in reality, ML practitioners seldom resort to NAS, because the manual redesign of a search space is the hardest to decide. This is especially challenging when one has multiple devices or multiple generations of devices, one would want to quickly migrate models across devices. Rather than redesigning everything including the search space from scratch, one will take an existing famous architecture already reported by the literature on that task and start to edit it to fit into the hardware while maintaining accuracy as much as possible. That is exactly the process AutoGO tries to automate, rather than searching for another large network that beats SOTA on a CV task. 
2) Given the large body of literature on NAS, the search algorithm (EA, RL, BO), the multi-objective search, and encoding of architectures, are already heavily studied--they are not the bottleneck. The bottleneck is how to come out with the search space for the task. Note that existing scientific research on NAS usually manually designs a search space that is good to boost scores and still friendly to GPUs but not necessarily friendly to other daily-used devices. AutoGO proposes a novel data science approach to this dilemma by mining segments from a diverse range of benchmarks featuring different kinds of topological features and ops and maintain a segment vocabulary. By directly operating on CG level (a fundamental representation of any network), AutoGO can directly edit any given input CNN's CG using this vocabulary (without distorting network representation), thus avoiding confining search to specific, manually designed cell/block structures or macro backbones or to any assumption.  The segment vocabulary contains fine-to-coarse subgraphs which can be constantly updated to supply to AutoGO.
3) We optimize on a range of NAS benchmarks to show that AutoGO can still enhance the best architectures in them, while exhaustive search cannot, because the search space design is not sufficient. We show AutoGO can generalize to enhance high-resolution networks ResNet EDSR VGG etc. in both accuracy and inference speed even on GPU. Finally, we demonstrate the already very lightweight manually designed proprietary FSRCNN and U-Net can still be optimized by AutoGO to achieve low-power/latency inference on cellphone. These results are all challenging to achieve.

Also, we clarify some writing in the paper:
### L91: "First, benchmarks only provide performance annotations for architectures inside a manually designed fixed search space." relevance to this work? (MAXz)

If we change an architecture in NB101 by tweaking ops or channels in a cell, it will result in an architecture outside the predefined NB101 search space, whose performance can't be assessed by a predictor trained on original NB101 encodings. In contrast, our predictor can as it operates in lower-level CG space.

###  What operations are used (MAXz)
We mutate an architecture using BPE-extracted segments, each composed of primitive operations like conv or relu. Segments range from all primitive operations (single nodes) to any 2-node sequences, ..., up to the largest segments in our database (Supp. Section A.1) with 15 nodes. 

### Line 225 “Retrain” Typo (MAXz)
This is a typo and is supposed to be “retain”. Mutation is guided by the PSC predictor, without requiring any retraining. 

### Our FSRCNN has 150x more FLOPS? (MAXz)
This is not the case. Our Proprietary FSRCNN-3,4 models in Tab. 5 are not comparable to e.g., FSRCNN-7 model in ECBSR paper. First, ours have 3 or 4 convolutional layers, while FSRCNN-7 has 7 layers (6 GFLOPs by Table 1 of the ECBSR paper) and uses a 9x9 Deconv for upsampling. But ours uses a 2x2 Deconv to make it friendly to cellphone hardware. Moreover, the FLOPs reported in Table 5 used an input image size of 64x640 which is what our power profiler allows. Also, there is a typo in Table 5 that FLOPs should be in units of 1e6, not 1e9. To clarify all of these, we provide a new Table 10 in the attached PDF with power metrics and FLOPs for input size 640x360 (which is used in ECBSR paper). At this size, our FSRCNN-3,4 base models have 2.67/3.74 GFLOPs, which is significantly less than the 6 GFLOPs of FSRCNN-7 in the ECBSR paper. Yet, the point shown by Table 5 is that AutoGO can still optimize such small models.

### FSRCNN, U-Net experiments use proprietary networks (MAXz)
AutoGO aims to assist ML engineers to auto-tune a known architecture on their target hardware (e.g., a cellphone) for faster inference. Our last results in 4.5 on FSRCNN, U-Net demonstrate this ability of AutoGO in reality, which complements our other results in 4.1-4.4 on public datasets/networks. We could only post relative changes at submission, but have been cleared to post power/lat metrics. The power values for the Table 6 U-Net are 724.59mW and 657.82mW for the original and AutoGO-optimized models, respectively.

Meta-review: This paper proposes AutoGO, a NAS framework that operates on the Computation Graph of a given architecture. The CG is partitioned into segments, i.e. it extracts subgraphs from existing benchmarks, to facilitate efficient architecture mutation. A "vocabulary" of segments is extracted from architectures using byte-pair-encoding. The paper empirically shows that AutoGO can improve the performance of the top architectures in common benchmarks. Furthermore, AutoGO demonstrates its capability to automatically optimize different types of large CNN architectures and achieve enhanced results in various computer vision tasks. The best replacement for a segment is searched with a variation of a multi-objective evolutionary algorithm (EA) using a GNN-based predictor.
The proposed model is innovative as it uses the architecture partitioning in an efficient way to allow for efficient EA. The provided experimental validation is extensive. Therefore, two of the reviewers provide a positive rating of the paper. At the same time, there is criticism of the significance of the approach, since it does not clearly improve over the SotA. Details on the pareto-optimality of the optimization have also been discussed, as well as the delineation form prior works on architecture segmentation. Still, I believe this paper proposes a very interesting new approach that might help to advance NAS and multi-objective NAS in the future.
Decision: Accept (poster)