GraphPNAS: Learning Distribution of Good Neural Architectures via Deep Graph Generative Models
Authors: Muchen Li
Jeffrey Yunfan Liu
Leonid Sigal
Renjie Liao
Venue: Submitted to ICLR 2023 (2023)
Keywords: Neural Architecture Search
Deep Generative Models of Graphs
Graph Neural Networks

Abstract: Neural architectures can be naturally viewed as computational graphs. Motivated by this perspective, we, in this paper, study neural architecture search (NAS) through the lens of learning random graph models. In contrast to existing NAS methods which largely focus on searching for a single best architecture, i.e, point estimation, we propose GraphPNAS a deep graph generative model that learns a distribution of well-performing architectures. Relying on graph neural networks (GNNs), our GraphPNAS can better capture topologies of good neural architectures and relations between operators therein. Moreover, our graph generator leads to a learnable probabilistic search method that is more flexible and efficient than the commonly used RNN generator and random search methods. Finally, we learn our generator via an efficient reinforcement learning formulation for NAS. To assess the effectiveness of our GraphPNAS, we conduct extensive experiments on three search spaces, including the challenging RandWire on TinyImageNet, ENAS on CIFAR10, and NAS-Bench-101. The complexity of RandWire is significantly larger than other search spaces in the literature. We show that our proposed graph generator consistently outperforms RNN-based one and achieves better or comparable performances than state-of-the-art NAS methods. 

LEARNING DISTRIBUTIONS OF GOOD NEURAL ARCHITECTURES VIA DEEP GRAPH GENERATIVE MODELS
GRAPHPNAS:
Anonymous authors Paper under double-bling review
ABSTRACT
Neural architectures can be naturally viewed as computational graphs. Motivated by this perspective, we, in this paper, study neural architecture search (NAS) through the lens of learning random graph models. In contrast to existing NAS methods which largely focus on searching for a single best architecture, i.e., point estimation, we propose Graph a deep graph generative model that learns a distribution of well-performing architectures. Relying on graph neural networks (GNNs), GraphPNAS can better capture topologies of good neural architec- tures and relations between operators therein. Moreover, our graph generator leads learnable probabilistic search method that is more flexible and efficient than the commonly used RNN generator and random search methods, Finally, we learn our generator via an efficient reinforcement learning formulation for NAS. To assess the effectiveness of our GraphPNAS, we conduct extensive experiments on three search spaces, including the challenging RandWire on Tiny- ImageNet. 101. The complexity of RandWire is signif-
ENAS on CIFARIO, 10, and icantly larger than other search spaces in the literature. We show that our proposed graph generator consistently outperforms RNN based one and achieves better comparable performances than state-of-the-an NAS methods.
INTRODUCTION
In recent years, we have witnessed a rapidly growing list of successful neural architectures that underpin deep learning, e.g., VGG, LeNet, ResNets (He et al., 2016), Transformers (Dosovitskiy et al., 2020). Designing these architectures requires researchers to go through time-consuming trial and errors. Neural architecture search (NAS) (Zoph & Le, 2016; Elsken et al., 2018b) has emerged as an increasingly popular research area which aims to automatically find state-of-the-art neural architectures without human-in-theeloopy
NAS methods typically have two components: search module and an evaluation module. The search module is expressed by a machine learning model, such as a deep neural network, designed operate in a high dimensional search space. The search space, of all admissible architectures, is often designed by hand in advance. The evaluation module takes an architecture as input and outputs the reward, e.g., performance of this architecture trained and then evaluated with metric. The learning process of NAS methods typically iterates between the following two steps. 1) The search module produces candidate architectures and sends them the evaluation module; 2) The evaluation module evaluates these architectures to get the reward and sends the reward back to the search module. Ideally, based on the feedback from the evaluation module, the search module should learn to produce better and better architectures. Unsurprisingly, this learning paradigm of NAS methods fits well to reinforcement learning (RI.).
Most NAS methods (Liu et al., 2018b; White et al., 2020; Cai et al., 2019) only return single best architecture (i.e., a point estimate) after the learning process. This point estimate could be very biased as it typically underexplores the search space. Further, a given search space may contain mul- tiple (equally) good architectures, a feature that point estimate cannot capture. Even worse, since the learning problem of NAS is essentially a discrete optimization where multiple local minima ist, many local search style NAS methods (Ottelander et al., 2020) tend to get stuck in local minima. From the Bayesian perspective, modelling the distribution of architectures is inherently better than

---

point estimation, e.g., leading to the ability to form ensemble methods that work better in practice. Moreover, modelling the distribution of architectures naturally caters to probabilistic search methods which are better suited for avoiding local optima, e.g., simulated annealing. Finally, modeling the distribution of architectures allows to capture complex structural dependencies between operations that characterize good architectures capable of more efficient learning and generalization.
Motivated by the above observations and the fact that neural architectures can be naturally viewed as attributed graphs, we propose a probabilistic graph generator which models the distribution over good architectures using graph neural networks (GNNs). Our generator excels at generating topolo- gies with complicated structural dependencies between operations. From the Bayesian inference perspective, our generator returns a distribution over good architectures, rather than single point estimate, allowing to capture the multi-modal nature of the posterior distribution of good architec- tures and to effectively average or ensemble architecture (sample) estimates. Different from the Bayesian deep learning (Neal, 2012; Blundell et al., 2015; Gal Ghahramani, 2016) that mod- els distributions of weights/hidden units, model distributions of neural architectures. Lastly, our probabilistic generator is less prone to the issue of local minima, since multiple random architectures generated at each step during learning. In summary, our key contributions are as below.
We propose GNN-based graph generator for neural architectures which empowers learn- able probabilistic search method. To the best of our knowledge, we are the first to explore learning deep graph generative models as generators in NAS.
We explore a significantly larger search space (e.g., graphs with 32 operators) than the literature (e.g., garphs with up to 12 operators) and propose to evaluate architectures under low-data regime, which altogether boost effectiveness and efficiency of our NAS system.
Extensive experiments on three different search spaces show that our method consistently outperforms RNN-bassd generators and is slightly better or comparable to the state-of-the- art NAS methods. Also, it can generalize well across different NAS system setups.
2 RELATED WORKS
Neural Architecture Search. The main challenges in NAS are 1) the hardness of discrete optimiza- tion. 2) the high cost for evaluating neural networks, and 3) the lack of principles in the search space design. First, to tackle the discrete optimization, evolution strategies (FS) (Elsken et al., 2019; Real al., 2019a), reinforcement learning (RL) (Baker et al., 2017; Zhong et al., 2018; Pham al., 2018; Liu et al., 2018a), Bayesian optimization (Bergstra et al., 2013; White et al., 2019) and continuous relaxations (Liu et al., 2018b) have been explored in the literature. We follow the RL path as it is principled, flexible in injecting prior knowledge, achieves the state-of of-the-art art performances (Tan & Le, 2019), and can be naturally applied to our graph generator. Second, the evaluation requires train- ing individual neural architectures which is notoriously time consuming(Zoph & Le, 2016). Pham et al. (2018); Liu et al. (2018)) propose a weight-sharing supernet to reduce the training time. Baker et al. (2018) use a machine learning model to predict the performance of fully-trained architectures conditioned on carly-stage performances. Brock et al. (2018); Zhang et al. (2018) directly predict weights from the search architectures via hypernetworks. Since our graph generator do not relies on specific choice of evaluation method, we choose to experiment on both oracle training(training from seratch) and supernet settings for completeness. Third, the search space of NAS largely determines the optimization landscape and bounds the best-possible performance. It is obvious that the larger the search space is, the better the best-possible performance and the higher the search cost would likely be. Besides this trade-off, few principles are known about designing the search space. Previ- ous work (Pham al., 2018: Liu et al., 2018b; Ying et al., 2019; Li et al.. 2020) mostly focuses on cell-based search space. A cell is defined as a small (e.g.. up to 8 operators) computational graph where nodes (i.e., operators like 3x3 convolution) are connected following some topology. Once the search is done, one often stacks up multiple cells with the same topology but different weights to build the final neural network. Other works (Tan et al., 2019; Cai et al., 2019; Tan & Le, 2019) typically fix the topology, e.g., a sequential backbone, and search for layer-wise configurations (e.g.. operator types like 3x3 vs. 5x5 convolution and number of filters). In our method, to demonstrate our graph generator's ability in exploring large topology search space, we first explore on chal- lenging large cell space (32 operators), after which we experiment on ENAS Macro (Pham et al., 2018 8) and NAS- MAS--Bncchmark-100 101 et al., 2019) for more comparison with previous methods.
2

---

Neural Architecture Graph for NAS. Recently, line of NAS research works propose to view neural architectures as graphs and encode them using graph neural networks (GNNs). In (Zhang et al., 2020; Luo et al., 2018), graph auto-encoders used to map neural architectures to and back from a continuous space for gradient- optimization. Shi et al. (2020) use bayesian optimization (BO), where GNNs used to get embedding from neural architectures. Despite the extensive use of GNNs as encoders, few works focus on building graph generative models for NAS. Closely related to our work, Xic et al. (2019) explore different topologies of the similar cell space using non- learnable random graph models. You et al. (2020) subsequently investigate the relationship between topologies and performances. Following this, Ru al. (2020) propose a hierarchical search space modeled by random graph generators and optimize hyper- pppammparaeeters using BO. They are different from our work as we learn the graph generator to automatically explore the cell space.
Deep Graph Generative Models. Graph generative models date back to the Erdōs-Rény model (Erdös & Rényi, 1959), of which the probability of generating individual edges the same. Other well-known graph generative models include the stochastic block model (Holland et al., 1983), the small-world model (Watts & Strogatz, 1998), and the preferential attachment model (Barabási & Albert, 1999). Recently, deep graph generative models instead parameterize the probability of gen- erating edges and nodes using deep neural networks in, e.g., the auto- regressive fashion (Li et al., 2018; You et al., 2018; Liao al., 2019) or variational autoencoder fashion (Kipf & Welling, 2016; Grover et al., 2018; Liu et al., 2019). These models are highly flexible and can model complicated distributions of real-world graphs, e.g., molecules (Jin et al., 2018), road networks (Chu al., 2019), and program structures (Brockschmidt et al., 2018). Our graph generator builds on top of the state- of-the-art deep graph generative model in (Liao et al., 2019) with several important distinctions. First, instead of only generating nodes and edges, we also generate node attributes (e.g., operator types in neural architectures). Second, since good neural architectures are actually latent, our learn- ing objective maximizes the expected reward (e.g., validation accuracies) rather than the simple log likelihood, thus being more challenging.
METHODS
The architecture of any feedforward neural network can be naturally represented as a directed acyclic graph (DAG), a.k.a., computational graph. There exist two equivalent ways define the compu- tational graph. First, we denote operations (e.g.. convolutions) as nodes and denote operands (e.g., tensors) as edges which indicate how the computation flows. Second, we denote operands as nodes and denote operators as edges. We adopt the first view. In particular, a neural network G with N operations is defined as a tuple (A, X) where A E (0, 1) is an N x N adjacent matrix with Aij 1 indicates that the output of the j-th operator is used as the input of the i-th operator. For operator with multiple inputs, inputs are combined together (e.g., using sum or average opera- tor) before sending into the operator. X is a N-size attribute vector encoding operation types. For any operation i, its operation type X, can only choose from pre-defined list with length D, e.g., 1 x 1,3 3 or 5 x 5 convolutions. Note that for any valid feedforward architecture, G can not have loops. One sufficient condition to satisfy the requirement is to constrain A to be a lower triangu- lar matrix with zero diagonal (i.e., excluding self-loops). This formalism creates a search space of (N1)/2 possible architectures, which is huge even for moderately large number of operators N and number of operation types D. The goal of NAS is to find an architecture or a set of archi- tectures within this search space that would perform well. For practical consideration, we search for cell graphs (e.g.. N = 32) and then replicate this cell several times to build a deep neural architec- ture. We also experiment on the ENAS Macro search space where G defines entire network. More details for the corresponding search spaces can be found in Section 4.
3.1 NEURAL ARCHITECTURE SEARCH SYSTEM
Before delving into details, we first give an overview of our NAS system, which consists of two parts: a generator and evaluator. The system diagram is shown in Fig. 1. At each step, the probabilistic graph generator samples a set of cell graphs, which are further translated to neural architectures by replicating the cell graph multiple times and stacking them up. Then the evaluator evaluates these architectures, obtains rewards, and sends architecture-rewant pairs to the replay buffer. The replay buffer is then used to improve the generator, effectively forming reinforcement learning loop.
3

---

Probabilistic Graph Generator
Samples from
Stem
Generator's Distribution
Stage
Down Sample
(X Alca)
(X A
Stage 2
Reinforce
Samples g
Down Sample
Evaluator
Replay Buffer G. R())
R())
Oracle Supernet Benchmark
Stage
Classifier
(0) DAG from step
(1)Aupeent with New & edges
(2) Encode Node & (3) GNN Message (4) Edge & Node
Edge
Passing
Sampling
(b)
Figure 1: Figure (a) is the pipeline of our NAS system. The core part is GNN-based graph generator from which we sample graph representations of neural network G. The corresponding model for each G is then sent to evaluator for evaluation. The evaluation result is first stored in replay buffer and then used for learning the graph generator through Reinforcement Learning. Figure(b) shows one generation step in the proposed probabilistic graph generator.
3.1.1 PROBABILISTIC GENERATORS FOR NEURAL ARCHITECTURES
Now we introduce our probabilistic graph generator which is based on a state-of-the-art deep auto- regressive graph generative model in (Liao al., 2019).
Auto- Regresegee Generation. Specifically, we decompose the distribution of a cell graph along with attributes (operation types) an auto-regressive fashion,
((A = 11 AA-1 X.) X..
(1)
where A,,: and X; denote the i-th row the adjacency matrix A and the i-th operation type respec- tively. To ensure the generated graphs are DAGs, constrain A to be lower triangular by adding binary mask, i.e., the i-th node can only be reached from the first i nodes. We omit the masks in the equations for better readability. We further model the conditional distributions as follows,
K
PP (A,, Xi-1. X
A X1)
II OR.0.
(2)
k=1
18iKi
P PX, N. A1. X1) Categorical (B1, ,3))
(3)
0n .....,a
OKK Softmax Σ Lijje MLP ( - -15))
(4)
3 BD Softmax (MLP
(5)
014.5
0K3 Sigmoid (MLP, - h:
(6)
where the distributions of the operation type and edges are categorical and K-mixture of Bernoulli respectively. D again the number of operation types. MLP,. MLP,, and MLP, different instances of two-layer MLPs with ReLU activations. Here hş is the representation of i-th node
4

---

returned by GNN which has been executed S steps of message passing at each generation step. This auto-regressive construction breaks down the nice property of permutation invariance for graph generation. However, we do not find it an issue in practice, partly due to the fact that the graph isomorphism becomes less likely to happen while considering both topology and operation types.
Message Passing GNNs. Each generation step n S N in auto-regressive generation above relies on representations of nodes up to and including n itself (see Eq. (4)-(6).. To obtain these node representations {ha), we exploit message passing GNNs (Gilmer et al., 2017) with attention mechanism similar to (Liao et al., 2019). In particular, the s-th message passing step involves executing the following equations successively.
m = f((h hr,, 1ú)l)
(7)
d Sigmoid - h2))
(9)
h;- = [hq. u,]
(8)
h GRU EjEN(O) miym (10)
where (i) the set of node along with its neighboring nodes. miy is the message sent from node i to j at the s-th message passing step. The connectivity for the propagation in GNN is given by A1s-1,13-1 with the last node (for which A.. has not been generated yet) being fully connected. Note that message passing step is different from the generation step and we run multiple message passing steps per generation step in order to capture the structural dependency among nodes and edges. The f and g are two-layer MLPs. Since graphs are DAGs in our case rather than undirected ones as in (Liao et al., 2019), we add 1iy in Eq. (7), a one-hot vector for indicating the direction of the edge. We initialize the node representations hς (for < n) as the corresponding one-hot encoded operation type vectors; 12 is initialized to special one-hot vector. Here is an additional feature vector that helps distinguish i-th node from others. We found using one-hot-encoded incoming neighbors of i-th node and a positional encoding of the node index work well in practice. We encourage readers to reference Fig. for detailed visualization of graph generation process.
Sampling. To sample from generator, we first draw architectures following the standard ancestral sampling where each step involves drawing random samples from a categorical distribution and mixture of Bernoulli distribution. At each step. this sampling process adds new operator with a certain operation type and wire to previously sampled operators.
3.1.2 EVALUATOR
Our design of generator and NAS pipeline do not rely on specific choice of evaluator. Motivated by (Mnih et al., 2013), we use replay buffer for storing the evaluated architectures. In our paper, based specific datasets, explore three types of evaluators, namely, oracle evaluator, supernet evaluator and benchmark evaluator, which are briefly introduced as follows.
Given sample from the generator, oracle evaluator trains the corresponding network from scratch and tests it to get the validation performances. To reduce computation over- head, common approach is to use early stopping (training with fewer epochs) as in (Tan et al., 2019; Tan & Le, 2019). In our experiment, we instead use a low-data evaluator similar to few-shot learning where we keep the same number of classes but use fewer samples per class to train.
Oracle evaluator.
SuperNet evaluator. Aiming at further reducing the amount of compute, this evaluator uses a weight-sharing strategy where each graph is a sub-graph of the supernet. We followed the single- path supernet setup used in (Pham et al., 2018) to compare with previous methods.
Benchmark evaluator. NAS benchmarks, e.g., (Ying et al., 2019), provide accurate evaluation for architectures within the search space, which can be seen as oracle evaluators with full training budgets on larget datasets.
3.2 LEARNING METHOD
Since we are dealing with discrete latent variables, i.e., good architectures in our case, we train NAS system using REINFORCE (Williams, 1992) algorithm with the control variate (a.k.a. bascline) to reduce the variance. In particular, the gradient of the loss or negative expected reward L w.r.t. the generator parameters Φ is,
Olog P(g) R(9) as
V ((()) E
(11)
5

---

where the reward R is standardized R(g) = (R(g) /)/o. Here the baseline C' is the average reward of architectures in the replay buffer and a is standard deviation of rewards in the replay buffer. The expectation in Eq. (11) is approximated by the Monte Carlo estimation. However, the score function (i.e., the gradient of log likelihood w.r.t. parameters) in the above equation may numerically differ lot for different architectures. For example, if negative sample, i.e., an architecture with a reward lower than the baseline, has a low probability P(G), it would highly likely to have an extremely large absolute score function value, thus leading to a negative reward with an extremely large magnitude. Therefore, in order to balance positive and negative rewards, we propose to use the reweighted log likelihood follows,
log P()) (( log(1 - P(G)) + RRg)> log(P(9))
(12)
where 3 is a hyperparameter that controls the weighting between negative and positive rewards. P(g) is the original probability given by our generator.
Exploration vs. Exploitation Similar to many RL approaches, our NAS system faces the explo- ration vs. exploitation dilemma. We found that our NAS system may quickly collapse (i.e., overly exploit) to a few good architectures due to the powerful graph generative model, thus losing the diversity and reducing to point estimate. Inspired by the epsilon greedy algorithm (Sutton & Barto, 2018) used in multi-armed bandit problems, we design a random explorer to encourage more explo- ration in the early stage. Specifically, at each search step, our generator samples from either itself or a prior graph distribution like the Watts-Stroger e is gradually annealed to 0 so that the generator gradually has more exploitation over exploration. Whats more, we design our replay buffer to keep a small portion of candidates. As training goes on, bad samples will be gradually be replaced by good samples for training our generators, which encourage the model to exploit more.
model with a probability e. As the search goes on,
4 EXPERIMENTS
In this section, we extensively investigate our NAS system on three different search spaces to verify its effectiveness. First, we adopt the challenging RandWire search space (Xie et al., 2019) which significantly larger than common ones. To the best of our knowledge, we are the first to explore learning NAS systems in this space. Then we search on the ENAS Macro (Pham et al., 2018) and NAS-Bench-1014 1Ying et al., 2019) search spaces to further compare with previous literature. For all experiments, we set the number of mixture Bernoulli K to be 10, the number of message passing steps 5 to 7, hidden sizes of node representation h and message my, to 128. For RNN-based baselines, we follow the design in (Zoph et al., 2018) if not other specified.
4.1 RANDWIRE SEARCH SPACE ON MANY-IMAGENE
WandWire Search Space. Originally proposed in (Xie et al., 2019), a randomly wired neural net- work is ResNet-like four-stage network with the cell graph G defines the connectivity of N con- volution layers within each stage. At the end of each stage, the resolution is downsampled by 3x3 convolution with stride 2 whereas the number of channels is doubled. While following the RandWire small regime in (Xic et al., 2019), we share the cell graph G among last three stages for simplifica- tion. To keep the number of parameters roughly the same, we fix the node type to be separable xx3 convolution. The number of nodes N within the cell graph G is set to 32 excluding the input and output nodes. This yields a search space of 2.1 10149 valid adjacency matrices, which is extremely large and renders the neural architecture search challenging. More details of the RandWire search space can be found in the Appendix E.I
Tiny-ImageNet w. Oracle Evaluator.
To enable search on the RandWire space, we exploit the oracle evaluator on the Imag-Ima dataset (Chrabaszez et al., 2017). To save computation, we employ a low-data oracle evaluator where we sample 1/10 of Imageemt training set for training and use the rest for validation at each search step. Similar to the few-shot learning, we keep the number of classes unchanged but reduce the number of samples per class. After the search, we retrain our found architectures on the full training set and evaluate it on the original validation set. Specifically, for each model, the oracle evaluator trains for 300 epochs and uses the average validation accuracy of the last epochs as the reward. Our total search budget is around 16 GPU days, which approximately amounts to 320 model evaluations, e.g., 40 search steps and 8 samples evaluated per step. For random search baselines, we choose Réndi (ER) and Patts-Strooatt (WS) models. Specifically, we first randomly draw hyperparameters from certain ranges, i.e., 0.1 S

---

Cost (GPU Days)
Low Data (Scarch)
Full Data (Final)
Methods
Val Avg Acc
Std
Val Avg Ace
Std
ER-TopK
15.2
23.12
0.34
61.76
0.04
WS-TopK
15.6
22.39
0.91
62.24
0.34
ER-BEST
15.2
20.07
1.62
62.10
0.25
WS-BEST
15.6
18.68
1.41
62.16
0.92
RNN (Zoph et al., 2018)
17.2
18.46
0.99
61.73
0.77
Ours
16.7
20.32
1.12
62.57
0.40
Table 1: Comparisons on Tiny-ImageNet. The top and bottom blocks include random search and learning-to-seane methods respectively. ER-TopK and WS-TopK refers to top (K=4) architectures found by all WS and ER models during search. ER-BEST and WS-BEST refer to the best ER and WS models found during search, i.c., 5=.75) and ER(x=0.1). Here Avg and Std of accuracies are computed based on 4 architectures sampled from generators.
p S 0.5 for ER and 0.2) S (k. p) S (6, 0.8) for WS, and then sample & from individual models. We set the reweight coefficient /3 to 0.05. For the random explorer, we choose WS model with the same hyperparameter range as a prior distribution and set = 0.6 in the beginning and decay by factor of 0.2 every 10 search steps. We also find that gradually shrinking replay buffer size to keep 30% to 10% of top-performing architectures helps stabilize the training of the generator. At the search time, we reject samples that already appear in the replay buffer to avoid duplications. We apply the same setting to the RNN generator for a fair comparison.
Results. As shown in Table 1, compare our NAS system with other random search methods and Icarning-to-see to-scarch methods. We can see that our method outperforms the RNN-based generator and other random search methods in terms of average validation accuracy the full dataset. Our generator also has a lower variance compared to the RNN-based one. Moreover, we observed that RNN based generator sometimes degenerates that it frequently sample densely-conneeted graphs. This is probably due to the fact that RNN based generator does not effectively utilize the topology information. We can see that high search reward (i.e., a low-data validation accuracy) do not necessarily lead to better performances in full data training. which indicates bias of the oracle evaluator within the low-data regime. Random search methods are prone to be biased they select architectures solely based on the search reward. Nevertheless, our generator is less affected by the bias and able to learn distribution of good architectures that perform well on full data training.
We also show results of the best archi- tectures found within 4 samples in Ta- ble 2. Here, ER-top-1 and WS-top-1 refers to the best model found from cor- responding random scarch. FC refers to the fully-connecte three times longer to train compared to our model. It is clear that the best model found by our method outper- forms those discovered by other meth- ods by considerable margin. More- over, we scale up the best models (de- noted as large) by adding more chan- nels and one more computation stage (more details are in Appendix F. 1). We can see that our searched architectures perform favorably against manually designed architectures like ResNet (He et al., 2016) and ResNeXt (Xie et al., 2017).
Model
Param (M)
Topl Top5 Ace
Resnet18
11.68
59.7110.09
80.32_0.10
Resnet50
25.56
63.4210.30
82. 82.6120.15
Resnext50
27.56
63.62
82. $2.73=0.00
FC
3,49
60.82+0.24
82.29
graph, which takes
ER- ER-Top1
3.23
61.82+0.00
82.30
RS-Topl
3.22
62.55+0.15
82 64
RNN
3.32
62.29
82, 02.16
Ours
3.27
63.23 10.18
83.06
WS-Topl Large
19.38
63.84
82. 20.16
RNN Large
19.78
63.6910.28
82.74
Ours Large
19.18
64.45
83.23
Table 2: Comparisons of best searched architectures (av-
eraged over 3 runs per architecture) on Tiny ImageNet.
4.2 ENAS MACRO SEARCH SPACE ON CIFAR10
ENAS Macro Search Space, originally proposed by Pham al. (2018), is search space which focuses on the entire network. G here defines the entire network with N = 12 nodes. The operation type (D=6)' per node is also searchable. g is guaranteed to contain length- 11 path, i.e., Vi 1, A = 1. The goal is to search off diagonal entries, i.e., skip connections. This gives search space of 1.6 x 1029 valid networks in total.
1 1, x convolution, 1 5 5 separable convolution, max pooling, avg pooling
7

---

Scarch Cost
Params (M)
Best Error Rate
Top Samples
Methods
(days)
Avg
Std
Net Transform (Cai et al., 2018)
T0
19.7
5.7
NAS (Zoph & Le, 2016)
22400
7.1
4.47
PNAS (Liu al., 2018a)
225
3.41
Lemonade (Elsken et al., 2018a)
56
3.4
3.6
EPNAS-Macro (Perez-Rua et al., 2018)
1.2
38.8
4.01
RNN (Pham et al., 2018)
0.9
19.64
4.18
4.47
0.282
RNN Large
0.9
36.92
4.00
4.16
0.089
Ours Ours Large
0.5
20.47
3.73
3.93
0.098
37.71
3.55
3.62
0.050
Table 3: Comparisons on CIFARIO dataset. The bottom and top blocks include NAS methods with ENAS Macro and other search spaces respectively. *; re-implementation. -: inapplicable.
Method
Avg Error
#Queries
0.8
Local Search
GCN Pred
6.331
150
BANANAS
Valilalion Error of (Best
6.6
RNN
Evolution
6.109
150
Ours (RL)
Ours
5,930 =0.14
150
Random Search
6,413 10.422
300
6.2
Local Search
5.879
300
BANANAS
5.906 :102296
300
8.0
RNN (RL)
6.028++0.228
300
Ours (RL)
5.807:40.077
300
0
50
100
150
200
250
300
Num Architectures Evalualed
Performances (average 10 runs) of best architectures vs. the number of architecture evaluations (search step).
Figure 2:
Table 4: Best model performances on NAS-
Bench-101. indicates numbers are taken from (White et al., 2019) Table
SuperNet Evaluator. For ENAS Macro search space, we experiment on CIFARIO (Krizhevsky al., 2009) dataset. For our generator, we use the ER model with p = 0.4 as our explorer, where decays from 1 to 0 in the first 100 search steps. For RNN based generator, we follow the setup in (Pham et al., 2018). We also adopt the weight-sharing mechanism (Pham et al., 2018) to obtain SuperNet evaluator that efficiently evaluates model's performance. We use a budget of 300 search steps with around 100 architectures evaluated per step for all methods. After the search, we use a short- training of 100 epochs to evaluate the performances of 8 sampled architectures, after which top-4 performing ones are chosen for a 600-epoch full training. The best validation error rate among these architectures is reported. For simplicity and fair comparison, do not use additional tricks (e.g., adding entropy regularizer) in (Pham et al., 2018). More details are provided Appendix F.
In Table 3, compare the error rates and variances for different NAS methods. Note that this vari- ance reflects the uncertainty of the distribution of architectures as it is computed based on sampled architectures. It is clear that our GraphPNAS achieves both lower error rates and lower variances compared to RNN based generator and is on par with the state-of-the-art NAS methods on other search spaces. We also see that the best architecture performance of our generator outperforms RNN based generator by significant margin. This verifies that our GraphPNAS is able to learn distribution well-performing neural architectures. Given that we only sample architectures, performances could be further improved with more computational budgets.
4.3 NAS BENCHMARKS
NAS-Bench-100 (Ying et al., 2019) is a tabulate benchmark containing 423K cell graphs, each of which a DAG with up to 7 nodes and edges including input and output nodes. We compare the performances of our GraphPNAS to open-source implementations of random search methods, local search methods, and BANANAS (White et al., 2019). The latter two are the best algorithms found by White et al. (2020) on NAS-Bench-101 For GCN prediction and evolution methods, use the score reported in (White et al., 2020). We give each NAS method the same budget of 300 queries and plot the curve of lowest test emorr As shown in Fig. 2, our GraphPNAS is able to quickly find well perfoorrn architectures. We also report the avg error rate 10 runs in Table 4. Our GraphPNAS again outperforms RNN
function of the number of evaluated architectures.
8

---

Ours
RNN Generator
Olustering Coeffiient
1022
014
25
45
Average Path length
Figure 3: Visualization of architecutre explore sapce of GraphPNAS vs RNN. Each point in the figure denotes a model evaluation. Colors of each node denotes its validation accuracy returned by the low-data Oracle evaluator.
based generator by significant margin and beats strong baselines like local search methods and BANANAS. Notably, our GraphPNAS has a much lower variance than other methods, thus being more stable across multiple runs.
NAS-Bench-201 (Dong & Yang, 2020) is defined on a smaller search space where up to 4 nodes and 6 edges are allowed. Experimental results can be found in Appendix A.
DISCUSSION & CONCLUSION
Qualitative Comparisons between RNN and GraphPNAS. In (You et al., 2020), the clustering coefficient and the average path length have been used to investigate distributions graphs. Here we adopt the same metrics to visualize architectures (graphs) sampled by RNN based and our generators in RandWire experiments. Points in Fig. refer to architectures sampled from both generators in the last 15 search steps where random explorers disabled. The validation performances color-coded. We can see that our GraphPNAS samples a set of graphs that have better validation accuracies while the ones of RNN generator have large variances in performances. Moreover, the graphs in our case concentrate to those with smaller clustering coefficients, thus less likely being densely-connected. On the contrary, RNN generator tends to sample graphs that are more likely to be densely-connected. While RNN has been widely used for NAS, we show in our experiments that our graph generator consistently outperforms RNN over three search spaces on two different datasets. This is likely due to the fact that our graph generator better leverages graph topologies, thus being more expressive learning the distribution of graphs.
Bias in Evaluator. In our experiments, we use SuperNet evaluator, low-data, and full-data Oracle evaluator to efficiently evaluate the model. From the computational efficiency perspective, one would prefer the SuperNet evaluator. However, it tends to give high rewards to those architectures used for training SuperNet. Although the low-data evaluator is more efficient than the full-data one, its reward is biased discussed in Section 4.1. This bias is caused by the discrepancy between the data distributions in low-data and full-data regimes. We also tried to follow (Tan et al., 2019) to use early stopping to reduce the time cost of the full-data evaluator. However, found that it assigns higher rewards to those shallow networks which converge much faster in the early stage of training. We show detailed results in Appendix E.4.
Search Space Design. The design of search space largely affects the performances of NAS methods. Our GraphPNAS successfully learns good architectures on the challenging RandWire search space. However, the search space is still limited as the cell graph across different stages is shared. A promising direction is learn to generate graphs in hierarchical fashion. For example, one can first generate macro graph and then generate individual cell graphs (each cell is node in the macro graph) conditioned on the macro graph. This will significantly enrich the search space by including the macro graph and untying cell graphs.
Conclusion. In this paper, we propose a GNN-based graph generator for NAS, called GraphP- NAS. Our graph generator naturally captures topologies and dependencies of operations of well- performing neural architectures. It can be learned efficiently through reinforcement learning. We extensively study its performances spaces. Experimental results show that our GraphPNAS consistently outperforms RNN-based gen- erator all datasets. Future works include exploring ensemble methods based on GraphPNAS and hierarchical graph generation on even larger search spaces.
the challenging RandWire as well as two widely used search

---

REFERENCES
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network archi- tectures using reinforcement learning. In International Conference on Learning Representations ICLR, 2017.
Bowen Baker, Otkrist Gupta, Ramesh Raskar, and Nikhil Naik. Accelerating neural architecture search using performance prediction. In International Conference on Learning Representations ICLR, 2018.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286 (5439), 1999.
Gabriel Bender, Hanxiao Liu, Bo Chen, Grace Chu, Shuyang Cheng, Pieter-Jan Kindermans, and Quoc V Le. Can weight sharing outperform random architecture search? an investigation with tunas. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 14323-14332, 2020.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(2), 2012.
James Bergstra, Daniel Yamins, and David D. Cox. Making science of model search: Hyperpa- rameter optimization in hundreds of dimensions for vision architectures. In Proceedings of the International Conference Machine Learning, ICML, 2013.
Charles Blundell, Julien Cornebise, Koray Kavukcuoglu, and Daan Wierstra. Weight uncertainty in 2015.
neural networks. arXiv preprint
Andrew Brock, Theodore Lim, James M. Ritchie, and Nick Weston. SMASH: one-shot model archi- tecture search through hypernetworks. International Conference on Learning Representations
ICLR, 2018.
Mare Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXiv preprint arXiv: 1880508490) 2018.
Han Cai, Jiacheng Yang, Weinan Zhang, Song Han, and Yong Yu. Path-level network transformation for efficient architecture search. In International Conference on Machine Learning, pp. 678-687 PMLR, 2018.
Han Cai, Ligeng Zhu, and Song Han. Proxylessnas: Direct neural architecture search target task and hardware. In International Conference on Learning Representations ICLR. OpenReview.net, 2019.
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 Confer- ence on Computer Vision, pp. 1294-1303, 2019.
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arXiv:1707.088 2017.
Hang Chu, Daiqing Li, David Acuna, Amlan Kar, Maria Shugrina, Xinkai Wei, Ming- Yu Liu, An- tonio Torralba, and Sanja Fidler. Neural turtle graphics for modeling city road layouts. In Pro- ceedings of the IEEE International Conference Computer Vision, pp. 4522 4530, 2019.
Xiangxiang Chu, Xiaoxing Wang, Bo Zhang, Shun Lu, Xiaolin Wei, and Junchi Yan. Darts-; ro- bustly stepping out of performance collapse without indicators. arXiv preprint rxXi:2200900007, 2020.
Xuanyi Dong and Yi Yang. Network pruning via transformable architecture search. Advances in Neural Information Processing Systems, 32, 2019a.
Xuanyi Dong and Yi Yang. One-shot neural architecture search via self-evaluated template network. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 3681-3699 2019b.
10

---

Xuanyi Dong and Yi Yang. Searching for robust neural architecture in four gpu hours. In Proceed- ings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1761-1770, 2019c.
Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. arXiv preprint SoXiv:2001.003266, 2020.
Xuanyi Dong. Lu Liu, Katarzyna Musial, and Bogdan Gabrys. Nats-bench: Benchmarking nas algorithms for architecture topology and size. IEEE transactions on pattern analysis and machine intelligence, 2021.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words: Transformers for image recognition scale. arXiv preprint arXiv:2010. 19929, 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient oulti-objective neural architecture search via lamarckian evolution. arXiv preprint arXiv:1804. 09081, 2018a.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey, arXiv preprint arXiv: 05377, 2018b.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient multi-objectiive neural architecture search via lamarckian evolution. In International Conference on Learning Representations ICLR, 2019.
Paul Erdös and Alfréd Rényi. On random graphs Publicationes Mathematicae Debrecen, 6, 1959.
Stefan Falkner, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter opti- mization scale. In International Conference on Machine Learning, pp. 1437-1446. PMLR, 2018.
Yarin Gal and Zoubin Ghahramani. Dropout as bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint 174001170..01212, 2017.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs.
arXiv preprint arXiv: Xiv:1803.1045 2018
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2), 1983.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. arXiv preprint (EXi::/8022.4334,, 2018.
Thomas N Kipf and Max Welling.
Variational graph auto-encoders. arXiv preprint
1rXiv:1611.07300 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. In Uncertainty in artificial intelligence, pp. 367-377. PMLR, 2020.
Wei Li, Shaogang Gong, and Xiatian Zhu. Neural graph embedding for neural architecture search. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 4707-4714, 2020.
11

---

Yujia Li, Oriol Vinyals, Chris Dyer. Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint 2xXiv:8803.033244 2018.
Renjie Liao, Yujia Li, Yang Song. Shenlong Wang, Will Hamilton, David K Duvenaud, Raquel Urtasun, and Richard Zemel. Efficient graph generation with graph recurrent attention networks. In Advances Neural Information Processing Systems, pp. 4255-4266 2019.
Chenxi Liu, Barret Zoph, Maxim Neumann, Jonathon Shlens, Wei Hua, Li-Jia Li, Li Fei-Fei, Alan Yuille, Jonathan Huang, and Kevin Murphy. Progressive neural architecture search. In Proceed- ings of the European Conference on Computer Vision (ECCV), pp. 19-34, 2018a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv preprint arXiv: (tte::88060000555 2018b.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows. In Advances in Neural Information Processing Systems, pp. (3578-13588 2019.
Shun Lu, Yu Hu, Longxing Yang, Zihao Sun, Jilin Mei, Zeng Yiming, and Xiaowei Li. Du-darts: Decreasing the uncertainty of differentiable architecture search. In BMVC, 2021.
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, pp. 419-427, 2019.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. Advances in neural information processing systems, 31, 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wier- stra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 2013.
Radford M Neal. Bayesian learning for neural networks, volume 118. Springer Science & Business Media, 2012.
T Den Ottelander, Arkadiy Dushatskiy, Marco Virgolin, and Peter AN Bosman. Local search is a remarkably strong baseline for neural architecture search. arXiv preprint arXiv:2004.0890 089996 2020.
Tuan-Manuel Perez- Rua,, Moez Baccouche, and Stéphane Pateux. Efficient progressive neural archi- tecture search. In BMVC, 2018.
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint 1822:/800..0266, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. In AAAI Conference on Artificial Intelligence, 2019a.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. In Proceedings of the aaai conference on artificial intelligence, volume 33, pp. 4780-4789, 2019b.
Robin Ru, Pedro Esperanca, and Fabio Maria Carlucci. Neural architecture generator optimization. Advances in Neural Information Processing Systems, 33:1 12057 2020.
Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Bridging the gap between sample-based and one-shot neural architecture search with bonas. Advances in Neural Information Processing Systems, 13:1888--119, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Mingxing Tan and Quoc Le. Efficientnet: Rethinking model scaling for convolutional neural net- works. In International conference on machine learning, pp. 6105-6114 14. PMLR, 2019.
12

---

Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoe V Le. Mnasnet: Platform-aware neural architecture search for mobile. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 2820-2828. 2019.
Alvin Wan, Xiaoliang Dai, Peizhao Zhang, Zijian He, Yuandong Tian, Saining Xie, Bichen Wu, Matthew Yu, Tao Xu, Kan Chen, et al. Fbnetv2: Differentiable neural architecture search for spatial and channel dimensions. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12965-12974, 2020.
Duncan J Watts and Steven H Strogatz. Collective dynamics of 'small-world" networks. Nature, 393(6684), 1998.
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. arXiv preprint arXiv:I910.111 198.99900.188.,,, 2019.
Colin White, Sam Nolen, and Yash Savani. Local search state of the art for neural architecture search benchmarks. arXiv preprint arXiv:2005.02966 2020.
Ronald J Williams. Simple statistical gradient-folowingg algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229-25 256, 1992.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual trans- formations for deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 1492-1500, 2017.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neu- ral networks for image recognition. Proceedings of the IEEE International Conference on Computer Vision, pp. 2284-1293, 2019.
Yuhui Xu, Lingxi Xie, Xiaopeng Zhang, Xin Chen, Guo-Jun Qi, Qi Tian, and Hongkai Xiong. (PC)- [darts]: Partial channel connections for memory-efficient architecture search. In International Conference Learning Representations, 2020. URL https: wwwp//pveee.eeeeeeeeeeeeeeeeeeee forum?
1d=BJ1S634tPr.
Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas- bench-101: Towards reproducible neural architecture search. In International Conference on Machine Learning, pp. 7105-7114, 2019.
Jiaxuan You, Rex Ying, Xiang Ren, William L. Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint 1rXiv:1802.08773 2018.
Jiaxuan You, Jure Leskovee, Kaiming He, and Saining Xie. Graph structure of neural networks.
arXiv preprint arXiv:2007.06559 2020.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. arXiv preprint arXiv:1810.05749, 2018.
Miao Zhang, Huiqi Li, Shirui Pan, Xiaojun Chang, Zongyuan Ge, and Steven Su. Differentiable neural architecture search equivalent space with exploration enhancement. Advances Neural 2020.
Information Processing Systems,
Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu. Practical block-wise neural net- work architecture generation. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2018.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning, arXiv preprint 1:X1v.1611.01578, 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoc V Le. Learning transferable architectures for scalable image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 8697-8710, 2018
13

---

A EXPERIMENTS ON THE NAS-BENCH- 201 SEARCH SPACE
Here we compare our method on NAS-Bench- Sei--Bnnchh20000 ((Donng & Yang. 2020) with random search (RAN- DOM) Bergstra & Bengio (2012), random search with parameter sharing (RSPS) Li & Talwalkar (2020), REA Real et al. (2019b), REINFORCE Williams (1992), ENAS Pham et al. (2018), first order DARTS (DARTS 1st) Liu et al. (2018b), second order DARTS (DARTS 2nd), GDAS Dong & Yang (2019c), SETN Dong Yang (2019b), TAS Dong & Yang (2019a), FBNet-V2 V2 Wan et al.
(2020), TuNAS Bender al. (2020), BOHB Falkner et al. (2018).
CIFAR-II 10
CIFAR 100
ImageNet- 12-100
Methods
validation
test
validation
test
validation
test
Weight Sharing
NAS:
RSPS
87.60+-0.61
91.05-+0.66
68.27+0.72
0..26-00.9
39.73+0.34
40.69-F0.36
DARTS (1st)
49.27=13.44
59.8447.84
61.08=4.37
61.26:14.43
38.07
37.88+2.91
DARTS (2nd)
58.78=13.44
65.38-7.88
59.48=5.13
60.49:4.95
37.56:1.110
36.79-1.559
GDAS
89.68=10.22
93.23-10.58
68.35=2.71
68.1722.50
39.55+0.00
39.40:1.000
SETN
90.00+00.97
92.72++0.73
69.19+1.42
69.36+1.722
39.77++0.3
39.51+0.33
ENAS
90.20++0.00
93.06++0.00
7..21
70.67+0.62
40.78+00.00
41.44
Multi-trial NAS:
REA
91.25+00.1
94.02+00.3
0..2
72.23+0.84
45.71
45.77+
REINFORCE
91.12:10.25
93.90::..26
71.80=0.94
7..86=0.89
45.37
45.6410.78
RANDOM
91.0710.226
93.86110.23
71.46=0.97
71.55
45.03
45.28:10.97
BOHB
91.17+0.27
93.944-0.28
72.04+0.93
72.00-0.86
45.55+0.79
45.70++0886
Ours
91.47:00.55
94.2811..17
7..47=0.84
0..34-0.81
45.00
45.40:10.97
Table 5: Searched best architecture performance on IAS-Bench-201. We run our methods 10 times to obtain mean and standard deviation.
To fairly compare with scores reported in (Dong et al., 2021), we fix a search budget of 20000s on CIFARÍO and CIFAR100, and 30000s on ImangeNet-16-111 which is approximately 150, 80, and 40 oracle evaluations (with sample evaluated per step) on CIFARIO, CIFAR 100, and ImageNet- 16-120 respectively. Specifically for MAS-Bench-200) we use random explorer in the first 10 steps and keep the top 15 architectures in the replay buffer. We found that model outperforms pre- vious methods on CIFARIO and CIFAR 100 datasets and is on par with state-of-the-ar methods on ImageNet- 16-120 dataset. On ImageNet-16-1 16-120, after extend the number of search budget from 40 to 60 steps, we significantly boost the performance to 45.57(+0.57) and 45.79(+0.4) on validation and test sets respectively. This indicates that the search process of our model hasn't 't converged due to the limited search steps. This suggests that a reasonable number of search steps is needed for our model to reach its full potential.
B COMPARISON WITH NAGO
Following Xie et al. (2019)'s work on random graph models, Ru et al. (2020) propose to learn parameters of random graph models using bayesian optimization. We compare with the randwire search space (refers to as RANG) in (Ru et al., 2020). Since the original search space in (Xie al., 2019) do not reuse cell graphs for different stages, we train conditionally independent graph generators for different stages respectively. That is 3 conditionally independent generators for conv3, c,nv,, and conv, stage in Table 9. We perform a search on the CIFAR10 dataset, where each model is evaluated for 100 epochs. We restrict the search budget to 600 oracle evaluations. We align with settings in (Ru et al., 2020) for retraining and report sampled architecture's 's test accuracy and standard deviation in the Table 6. We can that method learns distribution of graphs that outperforms previous methods.
C EXPERIMENTS ON THE DARTS SEARCH SPACE
DARTS is small eell-graph-ber based search space (Liu et al., 2018b). It is defined on DAG with up to 6 nodes and possible operators. Each node can have no more than two inputs. Like NAS- Bench-201, node operations defined the edge where nodes represent fuse operation between
14

---

Methods RANG-D RANG-BOHE RANG-MOBO
Reference Xie et al. (2019)
Avg. Test Accuracy (%)
Std.
94.1
0.16
Ru et al. (2020)
94.0
0.26
Ru al. (2020)
94.3
0.13
Ours
94.6
0.18
Table 6: Comparison of the searched results on CIFARIO. Mean test accuracy and the standard deviation calculated over samples from the searched generator. We align the search space design and retraining setting for a fair comparison.
incoming edges. Desipte the fact that NAS performances on CIFARIO with DARTS already saturated, we experiment it to compare with previous NAS methods. To be consistent with DARTS, we split CIFARIO into subsets containing 40000 training and 10000 validation samples and train architectures using SGD for 50 epochs with initial learning rate of 0.025 (annealed to via cosine decay), momentum of 0.9, weight decay of 0.0003, as well as auxiliary towers, drop path, and cutout. We allow budget of 96 oracle evaluations, or roughly 72 hours 4 NVIDIA TITAN Xp GPUs. We follow the DARTS final evaluation pipeline and perform SGD for 600 epochs with an initial learning rate 0.025 annealed by cosine decay, momentum 0.9, and weight decay 0.0003. We also perform data augmentation (cropping/horizonte flipping) and adapt auxiliary towers, drop path, and cutout.
Architecture ENAS NSGA-NET DARTS
Reference
Test Error (%)
Params (M)
Search Cost (GPU hr.)
Pham et al. (2018)
2.89
4.6
11
Lu al. (2019)
2.75
3.3
Liu et al. (2018b)
2.76
3.3
96
PDARTS
Chen al. (2019)
2.50
3.4
RF-DARTS
Zhang et al. (2020)
3.65
4.3
PCDARTS
Xu et al. (2020)
2.57
3.4
DARTS-
Chu et al. (2020)
2.58
3.5
DUDARTS
Lu et al. (2021)
2.38
3.7
0.4
BANANAS
White et al. (2019)
2.64
283
Ours
2.77
3.4
288
Table 7: Comparison results on CIFARIO with DARTS search space.
From Table 7, we can see that our method is on par with the state-of-art methods. The computation cost majorly due the fact that oracle evaluation used, where future works using performance predictor or SuperNet-based evaluator could be exploited to reduce the computation. Due to limits on available computation, we reuse the best hyperparameters found in NAS-bench-101, We expect further hyperparameter tuning would further boost the performance. We also provide search results on CIFAR100. Due to time constraints, we only compare with a few open-source NAS methods. For fair comparison, reuse the final training hyperparameters from Chen et al. (2019).
Architecture DARTS
Test Error (%)
Params (M)
Search Cost (GPU hr.)
19.24
3.3
96
PDARTS (trained CIFAR-1007
15.92
3.6
0.3
PDARTS (trained on CIFAR-10)*
16.55
3.4
0.3
Random Sampling
17.57
3.3
Random Search
16.70
3.4
288
Ours
15.89
3.4
288
Table Comparison of results CIFAR100 with DARTS search space.
D MORE DETAILS ON GRAPH GENERATOR
To more clearly illustrate the sampling process of our generator, we detailed probabilistic sampling process of generator in Fig. 4.
15

---

Node Label
Node
Neighbor Encoding
Feature
3. Positional Encoding
3
Edge
Edge direction
(0) DAG from Last step
(1)Augment with New node & edges
(2) Encode Node & Edge Feature
(3) GNN Message
(4) Edge & Node
Passing
Sampling
Figure 4: Detailed steps of auto-regressive generation with our graph generator.
E MORE DETAILS ON THE RANDWIRE EXPERIMENTS
E. DETAILS OF RANDWIRE IRE SEARCH SPACE
Here provided more details the RandWire search space shown in Table and Fig. 5.
Base
Large
Stage
Output
Cell
Channels
Cell
Channels
conv1
convexa
32
convaxa
48
conV2
56x56
convaна
64
convaxa
96
conV3
x8
G
64
G
192
G
288
сопV4
14x14
g
128
G
384
conv5
7x7
256
g
586
classifier
1x1
1x convix1. 1280-d
global average pool, 200-d fe, softmax
Table 9: Randwire search space with base and large settings. Base is the default setting for search while Large refers the architecture of scaled up models in Table 2. conv denote ReLU- SepConv-BN triplet.. , The input size is 224 pixels. The change of the output size implies stride of 2 (omitted in table) in the convolutions that placed at the end of each block. G is the shared cell graph that has 32 node.
E.2 DETAILS FOR RANDWIRE EXPERIMENTS
For experiment on Tiny-Imagenee we resize image to 224 224 as showed in Table 9. We apply the basic data augmentation horizontal random flip and random cropping with padding size 4. We provide detailed hyper-parameter for oracle evaluator training and learning for GraphPNAS in Table 10
E.3 VISUALIZATION OF ARCHITECTURES FROM OUR GENERATOR
Here visualize the top candidate architectures in Fig.
E.4
BIAS FOR EARLY STOPPING
As discussed in Section 5, using early stopping will lead to local minimal where the generator learns generate shallow cell structure. We quantify this phenomenon in table 11, where that
16

---

Stam Conv
Stage
Down Scale
Stage
Down Scale
Stage
Classifier
Figure 5: Visualization of WandWire search base space used in this paper. Different from (Xie al.,
2019), G here is shared across three stages.
Oracle Evaluator
Graph Controller
batch size optimizer
256
graph batch size
16
SGD
generator optimizer
Adam
learning rate learning rate deacy
0.1
generator Learning rate
le44
consine Ir decay
generator learning rate decay
none
weight decay
le-4
generator weight decay
0.
grad clip training epochs
generator gradient clip replay buffer fitting epochs
1.0
300
2000
Table 10: Hyperparameter setting for oracle evaluator and training our graph generator.
with early stopping training, the generator will generate more shallow architectures with shorter path from input to output. The corresponding average final validation accuracy also dropped by large margin compared the low data evaluator counter part.
evaluator early stopping
Final Val Acc
Average Path
Longest Path
61.86
2.595
6.525
low data regime
62.57
3.046
8.75
Table 11: In the table, we show ablation on the choice of oracle evaluator with our graph generator. The average Path and Longest path are computed as the average path length and longest path length from input to output over samples from the corresponding generator.
F MORE DETAILS ON ENAS MACRO EXPERIMENTS
For ENAS Macro search space, we use a pytorch-based open source implementation" and follow the detailed parameters provided in (Pham et al., 2018) for RNN generator. Specifically, we follow (Pham et al., 2018) to train the SuperNet and update the generator in an iterative style. At cach search step, two sets of samples Guain and Goval sampled from the generator. Guain is used to learn the SuperNet's weights by pack-propagating the training loss. The updated SuperNet used for evaluating Geval, which is then used for updating the generator.
For our generator, we evaluate 100 architectures per step and update our generator every epochs of SuperNet training. Instead of evaluating evaluated per step and evaluate on the full test set. We found this stables the training of our generator while keeping evaluation costs the same. In the replay buffer, the top 20% of architectures is kept.
single batch, reduce the number of models
For training SuperNet and RNN generator, we follow the same hyper-parameter setting in (Pham al., 2018) except the learning rate decay policy is changed cosine learning rate decay. For
17

---

ER
61.88
61.82
61.76
WS
62.24
62.55
62.13
62.29
62.04
RNN
60.86
Ours
63.23
62.73
63.06
Figure 6: Visualization of Top architectures sampled by each method. We observe that around 50% of samples from RNN generators are densely connected graphs or even fully connected graphs.
18

---

1319
Ours Best: 3.55
Enas Best: 4.00
Figure 7: The best architecture found by GraphPNAS and RNN generator (Pham al., 2018). Correspond to scores report in table 3. To get this architecture, we pre-evaluate 8 samples for both methods and select top-perfore op-performing architecture.
training generator we use the same hyrrparraeteer as in Table 10 with graph batch size changed to 32. For retraining the found the best architecture, we use a budget of 600 epoch training with a learning rate of 0.1, batch size 256, and weight decay 2c-4. We also apply cutout with probability of 0.4 to all the models when retraining the model.
F.1 VISUALIZATION OF BEST ARCHITECTURE FOUND
Here we visualize the best architecture found by GraphPNAS and RNN generator for Enas Macro search space in Fig. 7.
G MORE DETAILS ON NAS-BENCH-IN 101
For sampling on NAS-Bench- 101 (Ying et al., 2019), we first sample a 7-node DAG, then we remove any node that is not connected to the input or the output node. We reject samples that have more than 9 edges or don't 't have a path from input to output.
To train our generator on Nas- Hus--Bnnch-1le 101, we use Erdós Erdos-Rényí with p 0.25, is the beginning and decreased to 0 after 30 search steps. For the replay buffer, we keep the top 30 architectures. Our model is updated every 10 model evaluations, where we train 70 epochs on the replay buffer at each update time. The learning rate is set le-3 for with batch size of 2 on Nas-bench- 101. per
in
19


Reviews:
[{"review_id": "bBZ1om23I7Y", "reviewer": "Reviewer_kb9c", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposed to use GNN as the architecture controller in reinforcement learning based NAS.", "summary_of_the_review": "An interesting paper that first proposed using GNN as architecture controller, but need to be benchmarked with more recent methods and on more datasets.", "strength_and_weaknesses": "Strength:\n1. Some novelty as the first paper to propose using GNN-based generative modeling for generating architectures in NAS.\n2. Improved results compared to an RNN-based generator and several baselines that are quite old though.\n\nWeakness:\n1. I feel the cited papers and compared baselines are quite out-of-date. Cited works are mostly before 2020. While I am not well literatured in NAS, I do know there were multiple NAS methods proposed in 2021/2022. Maybe most of them are differentiable NAS methods but some comparisons should be made.\n2. Can evaluation be performed on the larger ImageNet and the newer NAS-bench-201 datasets? I feel results on the smaller and older datasets, without many more recent baselines, are less convincing.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FXs1n9qlImd", "reviewer": "Reviewer_DyTs", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper proposes a GNN-based neural architecture method that can model the distribution of well-performing architectures. With a reinforcement learning formulation, the paper claims that the learned GNN-generator is more flexible and efficient than existing work.", "summary_of_the_review": "Please refer to above.", "strength_and_weaknesses": "### Strengths\n1. The paper proposes a GNN-based graph generator for NAS, which is an interesting exploration.\n2. The paper applies the method to extensive experiments and shows state-of-the-art results on multiple benchmarks.\n3. The paper also introduces a larger search space and proves the efficiency of the method against the existing work.\n\n\n### Weaknesses\n1. More discussions of how the neural architecture is encoded in a GNN model would be appreciated. For example, figure 4 in the appendix should be in the main paper and illustrated.\n2. The evaluation of the method is applied to smaller datasets (Tiny-Imagenet, which is not common in the previous work. It would be more interesting to see how the method performs on large-scale real applications.\n3. It would be interesting to see different constraints for the NAS method, such as latency constraints of the neural architecture.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "81mlr2DW08T", "reviewer": "Reviewer_QTZh", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes a probabilistic graph generator that models the distribution over good architectures using GNNs. This converts the neural architectures to a learnable computational graph. Extensive experiments indicate the effectiveness and efficiency of the proposed method. This paper is generally well-written, and the idea is interesting. ", "summary_of_the_review": "This paper is generally well-written, and the idea is novel. I'd like to increase the score if the authors can resolve the above concerns.", "strength_and_weaknesses": "Strength:\n1. The idea of considering the NAS as GNN is interesting.\n2. The paper is well-organized and easy to follow. \n\n\nWeaknesses:\n1. The experiment does not show the efficiency of the method. Would you consider adding computational complexity analysis or time consumption?\n2. I don't quite understand why this method is less effective than other methods when the number of architectures evaluation is small. It suddenly got better as the number increased （Figure 2). Can you explain?\n3. In addition, the authors do not conduct experiments on the most common DARTS space, making it hard to conduct comparisons with most existing SOTA NAS methods. I understand that the DARTS space is an old benchmark and not easy to get significant improvement, while I am still interested in the performance of the proposed method in this space.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "-vN_qQoXYA", "reviewer": "Reviewer_8CC8", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper propose a NAS algorithm named GraphPNAS, which uses a graph generator instead of classical RNN generator to sample architectures from the space. RL algorithm is used to update the generator. Experiments on several different search space show the effectiveness of the method.", "summary_of_the_review": "This paper propose a NAS algorithm named GraphPNAS, which uses a graph generator instead of classical RNN generator to sample architectures from the space. However, the contributions are limited on model design. Furthermore, extend explanations and experiments are needed to support the method.", "strength_and_weaknesses": "Pros:\n1.\tThe paper is clear written and easy to follow.\n2.\tThe Figure3 show the architecture space model by the proposed generator is better than classical RNN controller.\n3.\tThe authors use several different search spaces on different datasets to demonstrate model effectiveness.\n\nCons:\n1.\tThe literature review is not sufficient. There are lots of papers use graph generators for NAS[1~3]. So this point is not new. The authors should explain how their model is more brilliant than these methods.\n2.\tThe graph generator model designs are borrowed from previous works. There are few contributions in this part.\n3.\tMore NAS baselines should be compared in the experiment part. The authors should also show why the architecture space model by the proposed graph generator is better than previous works.\n\n\n[1]Zhang, Miao, et al. \"Differentiable neural architecture search in equivalent space with exploration enhancement.\" Advances in Neural Information Processing Systems 33 (2020): 13341-13351.\n[2]Shi, Han, et al. \"Bridging the gap between sample-based and one-shot neural architecture search with bonas.\" Advances in Neural Information Processing Systems 33 (2020): 1808-1819.\n[3]Ru, Robin, Pedro Esperanca, and Fabio Maria Carlucci. \"Neural architecture generator optimization.\" Advances in Neural Information Processing Systems 33 (2020): 12057-12069.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject