GraphPNAS: Learning Probabilistic Graph Generators for Neural Architecture Search
Authors: Muchen Li
Jeffrey Yunfan Liu
Leonid Sigal
Renjie Liao
Venue: Accepted by TMLR ()

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 graph generative 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 four search spaces, including the challenging RandWire on TinyImageNet, ENAS on CIFAR10, and NAS-Bench-101/201. 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.

Published in Transactions on Machine Learning Research (11/2023)
GraphPNAS: Learning Probabilistic Graph Generators for Neural Architecture Search
Muchen Li University of British Columbia Vector Institute for Al
muchenk@cs.ubc..
Jeffrey Liu
jeffrey. yunfan. liu Bwwaterroooo
University of Waterloo
Leonid Sigal
Isigal@cs. ubc.
University of British Columbia
Vector Institute for Al
Canada CIFAR AI Chair
NSERC CRC Chair
Renjie Liao
rjliao@ece.ubc.c ubc.ca
Universily of British Columbia Vector Institute for Al Canada CIFAR AT Chair
Reviewed on OpenReview: https: openreviee. net/ forum? id= 7ca8
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 existing NAS methods which largely focus searching for single best architecture, i.e., point estimation, we propose GraphPNAS, deep graph generative model that learns 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 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 Tiny-ImageNet, ENAS CIFAR10, and NAS- Rench-101/201. 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. We open source our code here: https: http://ggccuub.../S---aaaaee com/DSL--Lab/rrappee
1 Introduction
In recent. years, we have witnessed 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 through time-consuming trial and errors. Neural architecturo 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-the-loop.
NAS methods typically have two components: search module and an evaluation module. The scarch module is expressed by 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

---

Published in Transactions on Machine Learning Research (11/2023)
advance. The evaluation module takes an architecture as imput and outputs the reward, e.g., performance of this architecture trained and then evaluated with a metric. The learning process of NAS methods typically iterates between the following two steps. 1) The search module produces candidate architectures and sends them to 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 (RL).
Most NAS methods (Liu et al., 2018b; White et al., 2020; Cai et al., 2019) only return a single best archi- tecture (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 multiple (equally) good architectures, a feature that a point estimate cannot capture. Even worse, since the learning problem of NAS is essentially a discrete optimization where multiple local minima exist, many local search style NAS methods (Ottclander et al., 2020) tend to get stuck in local minima. From the Bayesian perspective, mod- elling 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 architec- tures 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 topologies with com-- plicated structural dependencies between operations. From the Bayesian inference perspective, our generator returns a distribution over good architectures, rather than a single point estimate, allowing to capture the multi-modal nature of the posterior distribution of good architectures and to effectivcly average or ensemble architecture (sample) estimales. Different. from the Bayesian deep learning (Neal, 2012; Blundell et al., 2015; Gal & Ghahramani, 2016) that models distributions of weights /hidden units, we model distributions of neu- ral architectures. Lastly, our probabilistic generator is less prone to the issue of local minima, since multiple random architectures are generated at each step during learning. In summary, our key contributions are below.
We propose a GNN-based graph generator for neural architectures which empowers a learnable probabilistic scarch 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 out- performs RNN-based 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 optimization,
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 (ES) (Elsken et al., 2019; Real et al., 2019), reinforcement learning (RL) (Baker et al., 2017; Zhong et al., 2018; Pham et al., 2018b; Liu et al., 2018a), Bayesian optimization (Bergstra et al., 2013; White el 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-the-art performances (Tan Le, 2019), and can be naturally applied to our graph generator. Second, the evaluation requires training individual neural architectures which is notorionsly time consuming(Zoph & Le, 2016). Pham et al. (2018b); Liu et al. (2018b) propose a weight-sharing supernet
2

---

Published in Transactions on Machine Learning Research (11/2023)
to reduce the training time. Baker et al. (2018) use machine learning model to predict the performance of fully-trained architectures conditioned on early-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 scratch) and supernel 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. Previous work (Pham et al., 2018b; Liu et al., 201 8b; 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 soquential backbone, and search for laycr-wise configurations (e.g., operator lypes like 3x3 vs. 5x5 convolution and nunber of filters). In our method, to demonstrate our graph generator's ability in exploring large topology search space, we first explore a challenging large cell space (32 operators), after which we experiment on ENAS Macro (Pham et al., 2018b) and feenchmrrk-101///
et al., 2019) for more comparison with previous methods.
Neural Architecture as Graph for NAS. Recently, a 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., 2018a), graph auto-encoders are used to map neural architectures to and back from a contimuous space for gradient-based optimization. Shi et al. (2020) use bayesian optimization (BO), where GNNs are used to get embedding from neural architectures. Despite the extensive use of GNNs as encoders, few works focus building graph generative models for NAS. Closely related to our work, Xie 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 et al. (2020) propose a hierarchical search space modeled by random graph generators and optimize syper-parametter 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 ErdsRónyi model (Erdös & Rényi, 1959), of which the probability of generating individual edges is 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 generating edges and nodes using deep neural networks in, e.g., the auto-regressive fashion (Li et al., 2018; You el al., 2018; Liao el 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 et 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 learning objective maximizes the expected reward (e.g., validation accuracies) rather than the simple log likelihood, thus being more challenging.
Graph Generative models for Neural Architectural Search Closely related to our work, there is line of research that learns to generate graph architecture for neural architecture sn the prior paradigm, graph generative networks largely relied upon Variational Auto Encoders (VAEs). NAO(Luo et al., 2018b) employed an ASTM-based VAE, synchronized with performance prediction for gradient-based based architectural optimization. In contrast, Arch2Vec (Yan et al., 2020) was designed to translate the graph representation of neural architecture into an implicit vector using GraphVAE, aiming for its optimization through Bayesian Optimization. AG-Ne((Lukasiik et al., 2022), a more recent advent, originated a generative network from the VAF decoder, allied with surrogate model to expedite efficient learning. To extract sample from AG-Net, initial random sample is obtained from the architoctural representation space, after which decoder is utilized to translate the sample into graph represenlation. Our methodology differs significantly, utilizing an rete-regressive graph generator, wherein the generation of the graph mirrors a Markov decision process.
3

---

Published in Transactions on Machine Learning Research (11/2023)
Probabilistic Graph Generator
Samples from Generator's Distribution
Stem Conv
2
Stage
1
Down Sample
ARAA)
(x ((t4a))
Stage 2
Reinforce
Samples g
Down Sample
Evaluator
Replay Buffer G, R())
RG)
Oracle Supernet Benchmark
Stage
Classifier
(a)
(0) DAG from Last step
Augment with New node edges
(2) Encode Node
(3) GNN Message (4) Edge Node
Edge Feature
Passing
Sampling
(b)
Figure Figure (a) is the pipeline of our NAS system. The core part a GNN-based graph generator from which we sample graph representations of neural network G. The corresponding model for each G then sent to the evaluator for evaluation. The evaluation result is first stored in replay buffer and then used for learning the graph generator through Reinforcement Bearning.Figureee shows one generation step in the proposed probabilistic graph generator.
3 Methods
The architecture any feedforward neural network can naturally represented as directed acyelic graph (DAG), a.k.a., compulational graph. There exist two equivalent ways define the computational graph. First, we denote operations (e.g., convolutions) nodes and denote operands (e.g., tensors) as edges which indicate how the computation flows. Second, denote operands nodes and denote operators as edges. We adopt the first view. In particular, a neural network G with N operations is defined as tuple () where A E [0, is an N x N adjacent matrix with A;j = 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 operator) before sending into the operator. vector encoding operation types. For any operation its operation type X; can only choose from a pre- defined list with length D, e.g., 1 1, architecture, can not have loops. One sufficient condition to satisfy the requirement is to constrain A to be lower triangular matrix with zero diagonal (í.e., excluding self-loops). This formalism creates search space of NNN-1N possible architectures, which is huge even for modcrately large number of operators N and number of operation lypes D. The goal of NAS to find an architecture or a set of archilect 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 build deep neural architecture. 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.
a N-size attribute
or 5 convolutions. Note that for any valid feedforward
4

---

Published in Transactions on Machine Learning Research (11/2023)
3.1 Neural Architecture Search System
Before delving into details, we first give overview of our NAS system, which consists of two parts: generator and an evaluator. The system diagram is shown in Fig. 1. At each step, the probabilistic graph gencrator 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-reward pairs to the replay buffer. The replay buffer then used improve the generator, effectively forming reinforcement learning loop.
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 aulo-regressive graph generative model in (Liao et al., 2019).
Auto-Regres Regreseege Generation. Specifically, we decompose the distribution of a cell graph along with attributes (operation types) in an auto-regressive fashion,
P(A,X) = II P ()P PX XI.
(1)
where A and X, denote the i-th of the adjacency matrix A and the i-th operation type respectively. To ensure the generated graphs are DAGs, we constrain A to be lower triangular by adding binary mask, i.e., the i-th node can only be reached from the first i i-1 nodes. We omit the masks in the equations for better readability. We further model the conditional distributions as follows,
K
P (Ai, [Ai;:Ai-1,s X AI., X1) = Σ
O&k
II OR
(2)
k=1
ISj<i
P X,11
A1. X1) Categorical (31, ,BD)
(3)
a 0K Softmax Σ Eisjes
MLP a (h n1)))
(4)
B PD = Softmax (MPP((h))
(5)
01iii 0K.. Sigmoid (MLP h2))
(6)
where the distributions of the operation type and edges categorical and K-mixture of Bernoulli respec- tively. D is again the number of operation types. MLP., MLPp, and MLP, different instances of two-layer MLPs with ReLU activations. Here he is the representation of i-th node returned by GNN which has been executed S steps of message passing at each generation step. This auto-regressive construc- tion breaks down the nice property of permutation invariance for graph generation. However, we do not find as 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 I N in auto-regressive generation above relies representations of nodes up to and including n itself (see Eq. (4) (6)). To obtain these node representations { we exploit message passing GNNs (Gilmer et al., 2017) with an 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/ h3. 18y) hn = [12, us]
(7)
d Sigmoid h2))
(9)
(8)
ho+1 GRU(K, E mi)m
(10)
where (iii is the set of node i along with its neighboring nodes. my 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 A 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 ʃ and g two-layer ML.Ps.
5

---

Published in Transactions on Machine Learning Research (11/2023)
Since graphs are DAGs in our case rather than undirected ones as in (Liao et al., 2019), we add 1, in Eq (7), one-hot vector for indicating the direction of the edge. We initialize the node representations hg (for < n) as the corresponding one-hot encoded operation type vectors; h2 is initialized to a special one-hot vector. Here u, is an additional feature vector that helps distinguish i-th node from others. We found using one-hol-encoded incoming neighbors of i-th node and positional encoding of the node index work well practice. We encourage readers to reference Fig. 4 for a detailed visualization of graph generation process.
Sampling. To sample from generator, first draw architectures following the standard ancestral sampling where each step involves drawing random samples from categorical distribution and a mixture of Bernoulli distribution. At cach step, this sampling process adds new operator with a certain operation type and wire it to previously sampled operators.
3.1.2 Evaluator
Our design of generator and NAS pipeline do not rely on a specific choice of evaluator. Motivated by (Mnih et al., 2013), we use a replay buffer for storing the evaluated architectures. In our paper, based on specific datasets, we explore three lypes of evaluators, namely, oracle evaluator, supernet evaluator and benchmark evaluator, which are briefly introduced as follows.
Oracle evaluator. Given sample from the generator, an oracle evaluator trains the corresponding network from scratch and tests it to get the validation performances. To reduce computation overhead, a 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.
SuperNet evaluator. Aiming at further reducing the amount of compute, this evaluator uses 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., 2018b) to compare with previous methods.
Benchmark evaluator. NAS benchmarks, e.g., (Ying et al., 2019), provide accurate evaluation for archi- tectures within the search space, which can be seen as oracle evaluators with full training budgets on target datasets.
3.2 Learning Method
Since we are dealing with discrete latent variables, i.e., good architectures in our case, we train our 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,
VL(o) = EE(g) [- Olgg P(9) R(G)
(11)
Os
where the reward R is standardized R(g) (R(G) C)/o. Here the baseline C is the average reward of architectures in the replay bufler and a is standard deviation of rewards in the replay buffer. The expectation in Eqq (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 a lot for differont architectures. For example, if a negative sample, i.e., an architecture with a reward lower than the baseline, has a low probability P(G), would highly likely to have an extremely large absolute score function value, thus leading negative reward with an extremely large magnitude. Therefore, in order to balance positive and negative rewards, propose to use the reweighted log likelihood as follows,
log P(g) = =1 R(G) log(1 - P(G)) + R(g)>0 (Pg())())
(12)
where 3 is a hyperparameter that controls the weighting between negative and positive rewards. IP(G) is the original probability given by our generator.
Exploration vs. Exploitation Similar to many RL approaches, our NAS system faces the exploration vs. exploitation dilemma. We found that our NAS system may quickly collapse (ie., overly exploit) to few
6

---

Published in Transactions on Machine Learning Research (11/2023)
Cost (GPU Days)
Low Data (Search)
Full Data (Final)
Methods
Val Avg Acc
Std
Val Avg Acc
Std
ER- TRRTTop
15.2
28.12
0.34
61.76
0.04
WS-Toph. ER-BEST
15.6
22.39
0.91
62.24
0.34
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 Tmng-ImageNNe. The top and bottom blocks include random search and learning- to-search 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.e., W5(k=4,p=0.55) and ER(r=0.1). Here Avg and Std of accuracies are computed based on 4 architectures sampled from generators.
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 random explorer to encourage more exploration in the early stage. Specifically, at each search step, our generator samples from either itself or a prior graph distribution like the WattsStrogatz model with a probability e. As the search goes on, is gradually annealed to 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.
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 is 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., 2018b) and NAS-Bench-101 101(ing et al., 2019) scarch 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 S to 7, hidden sizes of node representation hy and message mi 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 Tiny-Ima
RandWire Search Space. Originally proposed in (Xie et al., 2019), a randomly wired neural network is a ResNet-like four-slage network with the cell graph g defines the connectivity of N convolution 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 (Xie et al., 2019), we share the cell graph G' among last three stages for simplification. To keep the number of parameters roughly the same, we fix the node type to be separable 3x3 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 x 10 valid adjacency matrices, which is extremely large and renders the neural architecture search challenging. More details of the WandWire search space can be found in the Appendix C.1.
Nmageem w. Oracle Evaluator. To enable search on the RandWire space, we exploit the oracle evaluator the Tiny-ImageNet dataset (Chrabaszez et al., 2017). To save computation, data oracle evaluator where we sample 1/10 of Tiny-ImageNet training set for training and use the rest for validation at cach scarch 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 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 ErdsRénni (ER)
employ low-
7

---

Published in Transactions on Machine Learning Research (11/2023)
Model
Param (M)
Top1
Top5 Acc
Resnet118
11.68
59.7
80.3240.10
Resnet50
25.56
63.42.00.0
82.6140.15
Resnext50
27.56
63.62+0.07
82.73.0.08
FC
3.49
60.82.0.24
82.29400.9
ER-Topl
3.23
61.82
82.30+0.11
RS-Topl
3.22
62.55
82.64
RNN
3.32
62.29
82. 16.0.4
Ours
3.27
43.28
83.06
WS-Topl Large
19.38
63.84
82.61
RNN Large
19.78
63.6940.2s
82.7440.21
Ours Large
19.18
64.45.1..2
83.23
Table 2: Comparisons of best-searched architectures (averaged over 3 runs per architecture) on Tiny Ima- geNet.
and WattsStrogatz (WS) models. Specifically, we first randomly draw hyperparameters from certain ranges, t.e., 0.1 < 0.5 for ER and (2, 0.2) S (k,p) S (6, 0.8) for WS, and then sample G from individual models. We set the reweight cocfficient A 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 it by a 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 fair comparison.
Results. As shown in Table 1, compare our NAS system with other random search methods and learning- to-search methods. We can see that our method outperforms the RNN-based generator and other random search methods in terms of average validation accuracy on the full dataset. Our generator also has a lower variance compared to the RNN-based onc. Morcover, we observed that RNN-based generator sometimes degenerates so that frequently samples densely-connected graphs. This is probably due to the fact that RNN based generator does not effectively utilize the topology information. We can see that a high search reward (f.c., low-data validation accuracy) does not necessarily lead to better performances in full data training, which indicates a bias of the oracle evaluator within the low-data regime. Random search meth are prone to be biased as they select architectures solely based on the search reward. This suggests that if a model is selected purely based on the proxy measurement, there may be bias when using proxy measurements such as low-data compared to Full data. Instead, learning a probabilistic distribution with the proxy and then sampling from this distribution may offer a more robust search method than deterministic selection with a proxy.
We also show results of the best architectures found within 4 samples in Table 2. Here, ER-top-1 and WS- top-1 refer to the best model found from the corresponding random search. FC refers to the fully-connected graph, which takes three times longer to train compared to our model. It is clear that the best model found by our method outperforms those discovered by other methods by a considerable margin. Moreover, we scale up the best models (denoted as large) by adding more channels and one more computation stage (more details are Appendix C.1). We can see that our searched architectures perform favorably against manually designed architectures like ResNet (He al., 2016) and ResNeXt (Xic al., 2017).
4.2 ENAS Macro Search Space on CIFAR10
ENAS Macro Search Space, originally proposed by Pham et al. (2018b), is a 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 also searchable. G is guaranteed to contain a length-11 path, i.e., Vi > 1, A = 1. The goal is scarch off-diagonal entrics, i.e., skip connections. This gives scarch space of 1.6 x 1029 valid networks in total.
11 5 convolution, x 1, 5xx separable convolution, max pooling, avg pooling
8

---

Published in Transactions on Machine Learning Research (11/2023)
Search Cost
Params (M)
Best Error Rate
Top Samples
Methods
(days)
Avg
Std
Net Transform (Cai et al., 2018)
10
19.7
5.7
NAS (Zoph Le, 2016)
22400
7.1
4.47
PNAS (Liu et al., 2018a)
225
3.2
3.41
T Lemonade (Elsken al., 2018a)
3.4
3.6
EPNAS-Macro (Perez- Rua al., 2018)
1.2
38.8
4.01
RNN* (Pham al., 2018b)
19.64
4.18
4.47
0.282
RNN Large
0.9
36.92
4.00
4.16
0.089
Ours
20.47
3.73
3.93
0.098
Ours Large
0.5
37.71
3.55
3.62
0.050
Table 3: Comparisons on CIFAR1O dataset. The bottom and top blocks inchude NAS methods with ENAS Macro and other search spaces respectively. *: our re-implementation. inapplicable.
Method
Avg Error
# #Queries
GCN Pred
6.331
150
Random
6.8
Local Search
Evolution
6.109
150
Validation Error Best BestAAchh Arch)
BANANAS
Ours
5.930 100.143
150
8.6
RNN (RL)
NAO"
6.51
192
(RL)
8.4
AG-NET
5.82
192
Arch2Veef
5.95
400
Random Search
6.413 1:04422
300
Local Search
5.879
300
BANANAS
5.906 20.296
300
RNN (RL)
6.028 228
300
0
50
100
150
200
250
300
Ours (RL)
20.072
300
Architacturas Evaluated
Figure Performances (average over 10 runs) of best architectures vs. the number of architecture evaluations (search step).
Table 4: Best model performances on NAS- Bench-101. indicates mumbers are taken from (White et al., 2019; Luo et al., 2018b; Yan et al., 2020; Lukasik et al., 2022)
SuperNet Evaluator. For ENAS Macro search space, we experiment on CIFAR10 (Krizhovsky et al., 2009) dataset. For our generator, we use the ER model with p = 0.4 as our explorer, where decays from to in the first 100 search steps. For RNN based generator, we follow the setup in (Pham et al., 2018b). We also adopt the weight-sharing mechanism in (Pham et al., 2018b) 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 4 architectures is reported. For simplicity and a fair comparison, we do not use additional tricks (e.g., adding entropy regularizer) in (Pham el al., 2018b). More details are provided in Appendix D.
In Table 3, compare the error rates and variances for different NAS methods. Note that this variance 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 a significant margin. This verifies that our GraphPNAS is able to learn a distribution of well-performing neural archi- toctures. Given that we only sample architoctures, the performances could be further improved with more computational budgets.
4.3 NAS Benchmarks
NAS-Bench-101 (Ying et al., 2019) is a tabulate benchmark containing 423K cell graphs, each of which is DAG with up to nodes and edges including input and output nodes.
9

---

Published in Transactions on Machine Learning Research (11/2023)
CIFAR R- 10
CHFAR-TOO
ImageNett. 16--------66-122-- 16-
Methods
Generator
Val
Test
Val
Test
Val
Test
Optinuen
91.61
94.37
73.49
73.51
46.72
47.31
Weight Sharing NAS:
GDAS (Dong & Yang, 2019)
89.68
98.223_o.s8
28.35
68.1722.50
30.55
39.40g0000
ENAS (Pham et al., 2018a]
90.20
93.76
70.21
70.67 20
40. 40.78 2800000
41.44.0000
SGNAS (Iuung & Chu, 2021)
90. 90.18
93.53=0.12
20.28
70.31
44.65+2.32
44.98
DeNet (Chen et nl., 2021)
91.55.0000 oo
94.36 00000
73.4920.00
73.51 20.00
46.37 00
46.3420.00
Multi-trial NAS
RANDOM (Doug & Yang, 2020)
91.07 2:025
93. 93.86_n.22
71. 71.46g0.07
71.56g0.97
45.03g0.91
45.28
RANDOM
BOII (Falkner et al., 2018)
+0.27
93 83.94_0..8
22.04
72.00
45. 45.55
45.70
IlyperBand
REINFORCE (Ying sl., 2019)
91.12
93. 2..00....
71.80
71.8620.50
25.37
15.6 15.61.0078
LSTM
GANAS [Changiz Rezaci et al., 2021)
94.34_o.os
73.2880017
46.80
Graph GAN
Areh2VEC (Yan al., 2020)
91.41
94.18=0.24
73.35
20.37
46.34 is
46.27 #:033
Graph VAE
AG-Net (Lukasik et al,, 2022)
91.55
94.241-..9
73.2:0..4
73.12#0.40
-66331 -66.31
46.20
Graph VAE Decoder
GraphPNAS
91.50+0..0
94.34_0.04
73.41
46. 20.27
46.50_....
Anto-regressiv GRAN
Table 5: Scarched best architecture performance on NAS-Bench-201. We run our methods 10 times to obtain mean and standard deviation.
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-Bencb-101. For GCN prediction and evolution methods, we 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 error as a function of the number of evaluated architectures.
As shown in Fig. 2, our GraphPNAS is able to quickly find well-performing architectures. We also report the avg error rate over 10 runs in Table 4. Our GraphPNAS again outperforms RNN based generator by a 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- 20S-Bench-201 (Dong & Yang, 2020) is defined on a smaller search space where up to 4 nodes and 6 edges are allowed. Here we compare our method on NAS-Bench-201 (Dong & Yang, 2020) with random search (RANDOM) Bergstra & Bengio (2012), ENAS Pham et al. (2018b), GDAS Dong & Yang (2019), BOHB Falkner et al. (2018). Closely related to methods, we compare with 3 more NAS methods with graph genrator: Arch2VecYan et al. (2020), AG-Net Lukasik et al. (2022), GANNAS Changiz Rezaci et al. (2021). Here Arch2VEC, AG-Net and our methods are fixed to 100 queries, while GANNAS is reported to use 400 qureis. Note that Arch2VEEC is coupled with a surrogate model for preselecting arch before queries. Our model can also potentially benefit from such setting. As shown in table 5, our method is either on- par-with or have outperformed previous graph generator based model on all three splits of NAS-Bench-200 201, However, it's worth noting that the NAS-Bench-201 is less challenging in the size of search space. Gradient based methods like DrNAS Chen et al. (2021) can well explore the entire search space given limited compute budget and find near optimal solution. In table 5, DrNAS is able to find the optimal model with validation accuracy of 73.49 on cifar100 validation set while our method find a sub-optimal model with 73.41(-0.08) accuracy.
We also experiment with the effect of budget on ImageNett16--10 split. We start with a baseline of 45.00 and 45.39 accuracy on validation and test set over 40 queries. By extending the budget with 20 more queries, we observe significantly improvement of performance to 45.57 (+0.57) and 45.79 (+0.4) on validation and test sets respectively. Extending it to 100 queries gives us the state-of-the-art result showed in table 5. This indicates that our model can not well explore the search space and converge with limited search steps. This is probably due to the fact that the auto-regressive model requires enough samples in the replay buffer to be able to train well, so a reasonable number of search steps is neoded for our model to reach its full potential.
5 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 of graphs. Here we adopt
10

---

Published in Transactions on Machine Learning Research (11/2023)
Ours
RNN Generator
Val
Clustering Coefficient
0.3
02
02
0.16
0.
0.1
0.14
2.5
35
25
35
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.
the same metrics to visualize architectures (graphs) sampled by RNN based and our generators in RandWire experiments. Points in Fig. 3 refer to architectures sampled from both generators in the last 15 search steps where random explorers 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 coefficintss, 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 two different datasets. This likely due to the fact that our graph generator better leverages graph topologies, thus being more expressive in learning the distribution of graphs.
disabled. The validation performances
color-coded. We can see that
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 Sete Although the low-data evaluator is more efficient than the full-data one, its reward biased as discussed in Section 4.1. This bias 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 carly stopping to reduce the time cost of the full- data evaluator. However, we 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 C.4.
Search Space Design. The design of search space largely affects the performances of NAS mothods. Our GraphPNAS successfully learns good architectures on the challenging RandWire search space. However, the search space still limited as the cell graph across different stages is shared. promising direction is learn generate graphs in hierarchical fashion. For example, one can first generate a macro graph and then generate individual cell graphs (cach cell is a 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.
Limitation to Scale up. Our method, as with all multi-trial generator-based NAS methods, does face a notable limitation: scaling up with an Oracle Evaluator proves challenging. One can resort to proxy evaluators, employing strategies such as weight-sharing, early-stopping, zero-cost-proxy, etc. However, these search results could be hcavily influenced by the bias of the evaluator. On the upside, the dccoupling of the architecture generator from the evaluator (unlike pruning- based DrNAS and weight-sharing methods like ENAS) implies that any improvement in evaluation can consistently result in superior NAS methods across all search spaces
Conclusion. In this paper, we propose a GNN-based graph generator for NAS, called GraphPNAS. Our graph generator naturally captures topologies and dependencies of operations of well-performing neural archi- tectures. It can be learned efficiently through reinforcement learning. We extensively study its performances on the challenging RandWire as well as two widely used search spaces. Experimental results show that our GraphPNAS consistently outperforms the RNN-based generator all datasets. Future works include
11

---

Published in Transactions on Machine Learning Research (11/2023)
exploring ensemble methods based our GraphPNAS and hicrarchical graph generation even larger search spaces.
Acknowledgments
This work was funded, part, by the Vector Institute for AI, Canada CIFAR Chair, NSERC CRC, NSERC DG and Discovery Accelerator Grants, and Oracle Cloud credits. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through the Digital Research Alliance of Canada alliance. can ca, and companies sponsoring the Vector Institute www. vectorinstitute wasstitute.a//ttattaeeeeee ai/#partners, Advanced Research Computing at the University of British Columbia, and the Oracle for Research program. Additional hardware support was provided by John R. Evans Leaders Fund CFI grant and Compute Canada under the Resource Allocation Competition award. We would like to thank Raquel Urtasun, Wenyuan Zeng, Yuwen Xiong, Ethan Fetaya, and Thomas Kipf for supporting the exploration along this research direction before this work.
References
Bowen Baker, Otkrist Gupta, Nikhil Naik, and Ramesh Raskar. Designing neural network architectures 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 Learning Representations ICLR, 2018.
Alsert-Táss1ó Barabási and Réka Albert. Emergence of scaling in random networks. Science, 286(5439). 1999.
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: Hyperparameter opti- mization in hundreds of dimensions for vision architectures. In Proceedings of the International Conference on Machine Learning, TCML, 2013.
Charles Blundell, Julien Cornebise, Koray Kavukeuoglu, and Daan Wierstra. Weight uncertainty in neural networks. arXiv preprint Xrxiv:5505. 05424, 2015.
Andrew Brock, Theodore Lim, James M. Ritchie, and Nick Weston. SMASH: one-shot model architecture search through hypernetworks. In International Conference on Learning Representations ICLR, 2018.
Mare Brockschmidt, Miltiadis Allamanis, Alexander L Gaunt, and Oleksandr Polozov. Generative code modeling with graphs. arXiv preprint ar 18511800.000 08490, 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 on target task and hardware. In International Conference Learning Representations ICLR. OpenReview.nec, 2019.
Scyed Saced Changiz Rezaci, Fred X. Han, Di Niu, Mohammad Salamch, Keith Mills, Shuo Lian, Wei Lu, and Shangling Jui. Generative adversarial neural architecture search. pp. 2227 2234, 2021. doi: 10.24963//jcca..222 2001//00.2333. URL nttps://doi. org/10 100 http://iccaaa.221////1 Main Track.
Xiangning Chen, Ruochen Wang, Minhao Cheng, Xiaocheng Tang, and Cho-Jui Hsieh. Dr(nas): Dirichlet neural architecture search. In International Conference on Learning Representations, 2021. URL https:
//openreview.net wet.:/orummidd-PP/aaaeeeee
Patryk Chrabaszez, Ilya Loshchilov, and Frank Hutter. downsampled variant of imagenet as an alternative to the cifar datasets. arXiv preprint arxiv: 14f::107.000 707.007778811111 08819, 2017.
12

---

Published in Transactions on Machine Learning Research (11/2023)
Hang Chu, Daiqing Li, David Acuna, Amlan Kar, Maria Shugrina, Xinkai Wei, Ming- Yu Liu, Antonio Torralba, and Sanja Fidler. Neural turtle graphics for modeling city road layouts. In Proceedings of the IEEE International Conference on Computer Vision, pp. 4522 4530, 2019.
Xuanyi Dong and Yi Yang. Searching for a robust neural architecture four gpu hours. In Proceedings of the CREE/CVP Conference on Computer Vision and Paltern Recogrillion, pp. 1761 1770, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-201: Exlending the scope of reproducible neural architecture search. arXiv preprint arXtt:2001.00300 2020.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Un- terthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, et al. An image is worth 16x16 words:
Transformers for image recognition at scale. arXiv preprint arXiv:2010. 11929, 2020.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient multi-objective neural architecture search vía lamarckian evolution. arXiv preprint 1rXi::1804.000 2018a.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. anXiv preprint arXi::1808. 05377, 2018b.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Efficient multi-objoctive neural architecture search via lamarckian evolution. In International Conference on Learving Representations ICLR, 2019.
Paul Erdös and Alfréd Rényi. On random graphs Publicationes Mathematicae Debrecen, 6, 1959.
Stefan Falkmer, Aaron Klein, and Frank Hutter. Bohb: Robust and efficient hyperparameter optimization at scale. In International Conference on Machine Learning, pp. 1437-1446. PMLR, 2018.
Yarin Gal and Zoubin Ghahramani, Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pp. 1050-1059, 2016.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint vrXii:1704.0122 2017.
Aditya Grover, Aaron Zweig, and Stefano Ermon. Graphite: Iterative generative modeling of graphs. anXiv preprint ar Xiv:18800. 10459, 2018.
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition.
Proceedings of the IEEE conference on computer vision and paltern recognilion, pp. 770 778, 2016.
Paul W Holland, Kathryn Blackmond Laskey, and Samuel Leinhardt. Stochastic blockmodels: First steps. Social Networks, 5(2), 1983.
Sian-Yau Huang and Wa Chu. Searching by generating: Flexible and efficient one-shot nas with architec- ture generator. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 983 992, 2021.
Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. arXiv preprint wrXiw:182.044366 2018.
Thomas N Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint 1Xi::6611.07300 2016.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
Wei Li, Shaogang Gong, and Xiatian Zhu. Neural graph embedding for neural architecture search. Proceedings of the AAAI Conference on Artificial Intellgence, volume 34, pp. 4707 4714, 2020.
Yujia Li, Oriol Vinyals, Chris Dyer, Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. Xio preprint arxio: 1833. 003.03324, 2018.
13

---

Published in Transactions on Machine Learning Research (11/2023)
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 in Newral Information Processing Systems, pp. 4255 4265, 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 Proceedings of the Euro- pean Conference on Computer Vision (ECCV), pp. 19-34, 2018a.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architocture search. ar preprint arXiv:1806.0000 2018b.
Jenny Liu, Aviral Kumar, Jimmy Ba, Jamie Kiros, and Kevin Swersky. Graph normalizing flows In Advances in Neural Information Processing Systems, pp. 13578-1233 13588, 2019.
Jovita Lukasik, Steffen Jung, and Margret Keuper. Learning where to look generative nas is surprisingly efficient. In European Conference on Computer Vision, pp. 257-273. Springer, 2022.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. Advances in neural information processing systems, 31, 2018a.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural archilecture optimization. Advances in nearal information processing systems, 31, 2018b.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Toannis Antonoglou, Daan Wierstra, and Martin Riedmiller. Playing atari with deep reinforcement learning. arXiv preprint arXiv:1312.5602 2013.
Radford M Neal. Bayesion 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 remarkably strong bascline for neural architecture scarch. Xi preprint arXiv:2044.080 2020.
Juan-Manuel Perez-Rua, Rua, Moez Baccouche, and Stéphane Pateux. Efficient progressive neural architecture search. In BMVC, 2018
Hieu Pham, Melody Guan, Barret Zoph, Quoc Le, and Jeff Dean. Efficient neural architecture search via parameters sharing. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Reseorch, pp. 4095-4104. PMLR, 10-15 Jul 2018a. URL https: httpss://troceeeeeeeteeee p/ppee/ed/o/c///sss///oe .mw.. wwl...pres//vee htth///00///haaaaae pham/8a......1 html.
Hieu Pham, Melody Y Guan, Barret Zoph, Quoe V Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. arXiv preprint Xrxiv:1822. 002668.8, 2018b.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V. Le. Regularized evolution for image classifier architecture search. In AAAI Conference on Artificial Intelligence, 2019.
Robin Ru, Pedro Esperanca, and Fabio Maria Carlucci. Neural architecture generator optimization. Advances in Neural Information Processing Systems, 13:12057-12069, 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 scarch with bonas. Aduances in Newral Information Processing Systems, 33:1808 1819, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International conference on machine learning, pp. 6105-6114. PMLR, 2019.
Mingxing Tan, Bo Chen, Ruoming Pang, Vijay Vasudevan, Mark Sandler, Andrew Howard, and Quoc 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.
14

---

Published in Transactions on Machine Learning Research (11/2023)
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 19X0::190.111 11858, 2019.
Colin White, Sam Nolen, and Yash Savani. Local search is state the art for neural architecture search benchmarks. arXiv preprint SSt:::0005002660 2020.
Ronald J Williams. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8(3-4):229 256, 1992.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transforma- tions for deep neural networks. In Proceedings of the IEEE conference computer vision and pattern recognilion, pp. 1500, 2017.
Saining Xie, Alexander Kirillov, Ross Girshick, and Kaiming He. Exploring randomly wired neural networks for image recognition. In Proceedings of the IEEE International Conference on Computer Vision, pp. 1284-1293, 2019.
Shen Yan, Yu Zheng, Wei Ao, Xiao Zeng, and Mi Zhang. Does unsupervised architecture representation learning help neural architecture search? Advances in neural information processing systems, 33:12486 12498, 2020.
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. ar preprint 3rXiv:1802.08773 2018.
Jiaxuan You, Jure Leskovee, Kaiming He, and Saining Xie. Graph structure of neural networks. arXiv preprint arXtt:2007.06559 2020.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. arXiv preprint arXte:1810.057449 2018
Miao Zhang, Huiqi Li, Shirui Pan, Xiaojun Chang, Zongyuan Ge, and Steven Su. Differentiable neural architecture search in equivalent space with exploration enhancement. Advances in Neural Information Processing Systems, 33:13341 13351,, 2020.
Zhao Zhong, Junjie Yan, Wei Wu, Jing Shao, and Cheng-Lin Liu. Practical block-wise neural network architecture generation. In IEEE Conference on Computer Vision and Pattern Recognition, CVPR, 2018.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. arXiv preprint arXiv:161.00157, 2016.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe Le. Learning transferable architectures for scal- able image recognition. In Proceedings of the IEEE conference on compuler vision and pallern vecognition, pp. 8697-8710, 2018.
15

---

Published in Transactions on Machine Learning Research (11/2023)
A More details on Graph Generator
To more clearly illustrate the sampling process of our generator, we detailed probabilistic sampling process of our generator in Fig. 4.
1. Node Label
1
Node
Neighbor Encoding
Feature
3. Positional Encoding
2
Edge Feature
1. Edge direction
2
6
5
5
(0) DAG from Last step
(1)Augment with New node & edges
(2) Encode Node & Edge Feature
(3) GNN Message Passing
(4) Edge & Node Sampling
Figure 4: Detailed steps of auto-regressive generation with our graph generator.
B
Comparison with NAGO
Following Xie et al. (2019)'s work on random graph models, Ru et al. (2020) propose learn parameters of random graph models using bayesian optimization. We compare with the randwire search space (refers RANG) in (Ru et al., 2020). Since the original search space in (Xie et 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, conv4, and convs stage in Table 7. We perform search on the CIFARI0 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 test accuracy and standard deviation in the Table We can see that our method learns distribution of
Methods RANG-D
Reference
Avg. Test Accuracy (%)
Std.
Xie et al. (2019)
94.1
0.16
RANG-BOHB RANG-MOBO
Ru al. (2020)
94.0
0.26
Ru al. (2020)
94.3
0.13
Ours
94.6
0.18
Table 6: Comparison of the scarched results on CIFAR10. are calculated over 8 samples from the searched generator. We align the search space design and retraining setting for fair comparison.
Mean accuracy and the standard deviation
graphs that outperforms previous methods.
C More details on the Randwire experiments
C.1 Details of RandWire search space
Here provided more details the RandWire search space shown in Table and Fig. 5.
16

---

Published in Transactions on Machine Learning Research (11/2023)
Base
Large
Stage
Output
Cell
Channels
Cell
Channels
conv1
112x112
convax
32
convaxa
48
conV2
56x56
convax3
64
convaxa
96
conV3
g
64
192
288
conv4
14x14
g
128
384
conv5
7x7
G
256
586
1x convix1: 1280-d
classifier
global average pool, 200-d fe, softmax
Table 7: Randwire search space with base and large settings. Base is the default setting for search while Large refers to the architecture of scaled up models in Table 2. conv denote ReLU-SepConv-Bi triplet The imput size is 224x224 pixels. The change of the output size implies a stride of 2 (omitted in table) in the convolutions that are placed at the end of each block. G the shared cell graph that has = 32 node.
Stem Conv
Stage 1
Down Scale
Stage 2
Down Scale
Stage 3
Classifler
Figure 5: Visualization of RandWire search base space used this paper. Different from (Xie et al., 2019),
G here is shared across three stages.
17

---

Published in Transactions on Machine Learning Research (11/2023)
C.2 Details for RandWire experiments
For experiment on Tiny-Imagenet, resize image to 224 224 showed in Table 7. We apply the basic
data augmentaaiin of horizontal random flip and random cropping with padding size 4. We provide detailed
hyper-paramcter for oracle evaluator training and learning for GraphPNAS in Table 8
Oracle Evaluator
Graph Controller
batch size optimizer
256
graph batch size
16
SGD
generator optimizer
Adam
learning rate
0.1
generator Learning rate
1o4
learning rate deacy
consine Ir decay
generator learning rate decay
none
weight decay
le-4
generator weight decay generator gradient clip replay buffer fitting epochs
0.
grad clip training epochs
0.
1.0
300
2000
Table 8: Hyperparameter setting for oracle evaluator and training graph generator.
C.3 Visualization of architectures from our generator
Here we visualize the top candidate architectures in Fig. 6
C.4 Bias for early stopping
As discussed in Section 5, using early stopping will lead to local minimal where the generator learns to generate shallow cell structure. We quantify this phenomenon in table 9, where we can see that 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 a large margin compared the low data evaluator counter part.
evaluator early stopping
Final Val Acc
Average Path
Longest Path
61.86
2.595
6.125
low data regime
62.57
3.046
8.75
Table 9: In the table, we show ablation on the choice of oracle evaluator with our graph generator. The average Path and Longest path computed the average path length and longest path length from input to output over 8 samples from the corresponding generator.
More details on ENAS Macro experiments
For ENAS Macro search space, we use a pytorch- artorch-based based open source implementation' and follow the detailed parameters provided in (Pham et al., 2018b) for RNN generator. Specifically, we follow (Pham et al., 2018b) to train the SuperNet and update the generator in an iterative style. At each search step, two sets of samples Gerain and Geval are sampled from the generator. Girain is used to learn the SuperNet's weights by back-propagating the training loss. The updated SuperNet is 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 5 epochs of SuperNet training. Instead of evaluating on a single batch, we reduce the number of models 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. the replay buffer, the top 20% of architectures kept.
18

---

Published in Transactions on Machine Learning Research (11/2023)
ER
61.88
61.82
61.76
WS
62.2 24
62.55
62.13
62.29
62.04
RNN
60.86
Ours
63.23
62.73
63.06
Figure 6: Visualization of Top 3 architectures sampled by each method. We observe that around 50% of samples from RNN generators are densely connected graphs or even fully connected graphs.
19

---

Published in Transactions on Machine Learning Research (11/2023)
2
mend 2
2
Ours Best: 3.55
Enas Best: 4.00
Figure 7: The best architecture found by GraphPNAS and RNN generator (Pham et al., 2018b). Correspond to scores report in table 3. To get this architecture, pre-evaluate 8 samples for both methods and select top-performing architecture.
For training SuperNet and RNN generator, we follow the same hyper-parameter setting in (Pham et al., 2018b) except the learning rate decay policy is changed to cosine lcarning rate decay. For training our generator we use the same hyperparameter as in Table 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 a cutout with probability of 0.4 to all the models when retraining the model.
D.1 Visualization of best architecture found
Here visualize the best architecture found by GraphPNAS and RNN generator for Enas Macro search space in Fig. 7.
E More details on NAS Benchmark
For sampling on NAS-Bench-101 (Ying et al., 2019), we first sample a 7-node DAG, then we remove any node that not connected to the input or the output node. We reject samples that have more than 9 edges or don't have a path from input to output.
To train our generator on Tas-Bench- 101, we use ErdsRényi with p 0.25, e is set in the beginning and decreased to 0 after 30 search steps.
20

---

Published in Transactions on Machine Learning Research (11/2023)
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 to 1e-3 for with batch size of 2 on Nas- aas-bench-101 101.
21


Reviews:
[{"review_id": "LdcF6zJfpz", "reviewer": "Reviewer_LA45", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "[Strength]:\n\n1. This paper is very well-organized and easy to follow. Different aspects of the proposed methods are explained clearly.\n2. Using auto-regressive models as the graph (architecture) generator is an interesting and novel idea in the context of NAS, and constitutes a key differentiating factor from the highly-relevant baseline NAGO.\n\n[Weakness]:\n\n1. [Major] Missing relevant baselines or references. There exist more recent prior works that are relevant to the proposed methods. But they seem to be missing in the paper.\n    1. Recent GNN-generator-based NAS methods: For example, arch2vec [1] trains a simple Graph VAE and uses the encoder for NAS task, trained via Reinforcement Learning.\n    2. SOTA results on 201 and 101 benchmarks: The baselines included in 201 and 101 experiments are outdated (4-5 years old). There are more recent methods that achieve better results. For example, DrNAS [2] as a weight-sharing NAS, and arch2vec [1] as a multitrial NAS. They should be included to get a better sense of the effectiveness of the proposed method.\n2. [Major] Search Cost & Lack of experiments at scale. The proposed method, when paired with an oracle evaluator, is too expensive for practical usage. As a result, the paper does not bench its method on experiments at scale (e.g. ImageNet-1K which is a standard experiment in NAS papers in recent years). One solution, as the author mentioned, is to use a supernet evaluator. However, this will lead to the same restriction on the search space design as all one-shot NAS (of which the most recent methods achieve stronger performance compared with the proposed method), thereby eliminating the flexibility of search space generation in the proposed method.\n\n\n[1] Yan et al. Does Unsupervised Architecture Representation Learning Help Neural Architecture Search? NeurIPS 2020 \\\n[2] Chen et al. DrNAS: Dirichlet Neural Architecture Search. ICLR 2021", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "[Summary]\n\nThis paper studies Graph-Generator-based methods for NAS.\nSince NAS search spaces can be viewed as DAG, the paper proposes to train an auto-regressive graph generator to generate graphs as architectures.\nThe generated architectures are subsequently trained from scratch (or in a Supernet) to obtain their scores.\nDue to the non-differentiable nature of the pipeline, the author adopts REINFORCE algorithm to train the generator.\nExperimental results are conducted primarily on Three search spaces: RandWire (Tiny-ImageNet), NAS-Bench-201 (CIFAR-10/100, Tiny-ImageNet), and NAS-Bench-101 (CIFAR-10), the proposed method discovers better architecture compared with selected baselines (more on this in the weakness section).", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Include proper SOTA weight-sharing and GNN-based methods as baselines on the benchmark spaces. The works referred to in the weakness section only represent the reviewer’s somewhat not-up-to-date knowledge of the field, so there are likely more recent works that should be included as well.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "3mWefjGznh", "reviewer": "Reviewer_cqZC", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strength**\n\n1. The  paper is well organized and easy to follow.\n2. The authors propose a unique approach to NAS by using a graph generative model to learn a distribution of high-performing architectures, which deviates from traditional NAS methods that focus on finding a single optimal architecture.\n3. The proposed method is evaluated across three different search spaces, ranging from small cell-based search spaces to large topology search spaces, demonstrating its effectiveness.\n\n**Weakness**\n\n1. The paper compares the proposed method with a broad range of models, but most of these models seem to be outdated, having been proposed before 2021.\n2. The paper lacks some crucial implementation details. For instance, how to determine the node index in Section 3.1.1 is not clearly explained.\n3. The paper lacks a comprehensive ablation study. Specifically, it does not provide a detailed analysis of how different hyperparameters impact the performance of the proposed method.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces GraphPNAS, a deep graph generative model to learn a distribution of high-performing architectures for Neural Architecture Search (NAS). The model leverages graph neural networks (GNNs) to capture the topologies of good neural architectures and the relationships between their operators. The whole model is trained by REINFORCE algorithm. Numerical results demonstrate that GraphPNAS consistently outperforms RNN-based generators and achieves comparable or better performance than state-of-the-art NAS methods.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "## Proposed Changes:\n\n1. The concept of modeling the distribution of model architectures and using graphs to embed model architectures is not new [1]. The authors should clarify the unique aspects and advantages of their proposed method more explicitly.\n2. The choice of baseline models for comparison varies across different benchmarks. For instance, in the 'RandWire Search Space on Tiny-ImageNet' section, only traditional methods and RNN-based methods are used for comparison. The authors should provide a rationale for their choice of baseline models.\n3. In Table 1, there is no clear correlation between results in low data and results in full data. The authors claim that the proposed method is less affected by such bias. This point could be elaborated further for clarity.\n\n[1]. 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\n", "broader_impact_concerns": "N/A\n", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zBg4Vw70Rv", "reviewer": "Reviewer_836L", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros.\n1. The problem is very important. \n2. Combining GNN with NAS is kind of interesting. \n\nCons. \n1. The main baseline (backbone) RNN in Table 1 is from 2018, which makes the model comparison less meaningful. \n2. The related work part is quite out-of-date. It cites only two 2021's works, no newer work. \n3. The module very related to graphs is classic message passing, which makes the extension to graph generative model kind of trivial. \n4. The novelty is kind of incremental. Authors combine message passing with a well-known learning method.\n5. Author do not mention potential limitations. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the problem of neural architecture search and propose a graph neural network-based model GraphPNAS. Experiments show that the proposed graph generator achieves better or comparable performances than state-of-the-arts. \n", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add more up-to-date and strong baselines in the top venues for comparison. \n2. Add more recent related works for discussion. \n3. Go deeper and improve the method. Add something new about graph structure.\n4. Include limitations. \n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The initial reviews suggested that while the work had several strengths it also seemed to have missed surveying and comparing against some of the recent neural architecture search (NAS) literature. 

The authors provided detailed rebuttals and included: A) a survey of recent work, B) new experimental results with said work, and C) an improved discussion of the relationships and limitations of their work. 

These improvements were key and two of the three reviewers recommend acceptance. One also noted that "the overall novelty and potential of the proposed method remain evident." However, the third while recognizing that the literature was better surveyed also remarks: 1) the lack of large-scale experiments; 2) an incomplete analysis of the NAS-Bench-201 results (Table 4). 

The former (1) was discussed by the authors in their rebuttal. The authors also address the question in the updated version of their manuscript (Section 5, paragraph "Limitation to Scale up"). I find this to be sufficient given TMLR's criteria. 

The latter (2) remains, however. In particular, the authors in Table 4 did not add the DrNAS [1] baseline nor the optimal upper-bound results provided in that paper. Without these baselines, the authors' conclusion is that "our methods is [sic] either on-par-with or have outperformed previous graph generator based model on all three splits of NAS-Bench-201." However, [1] reports that DrNAS finds near-optimal solutions on this NAS-Bench-201 benchmark thereby questioning the authors' analysis.

Adding DrNAS would be nice, but is perhaps not necessary. However, either adding the upper bound (given your exact methodology) or at least discussing these results in the context that this benchmark might be "solved" would, I find, provide a more accurate analysis. I also imagine other parts/sentences in the paper might have to be updated to take this discussion into account.

Overall, this is a good paper and I recommend that it is accepted with minor revisions (discussed above). 

Congratulations! I look forward to working toward a camera-ready version of this work with its authors.


[1] Chen, X., Wang, R., Cheng, M., Tang, X., & Hsieh, C.-J. DrNAS: Dirichlet Neural Architecture Search. ICLR 2021.
Decision: Accept (poster)