Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels
Authors: Binxin Ru
Xingchen Wan
Xiaowen Dong
Michael Osborne
Venue: ICLR 2021 Poster (2021)

Abstract: Current neural architecture search (NAS) strategies focus only on finding a single, good, architecture. They offer little insight into why a specific network is performing well, or how we should modify the architecture if we want further improvements. We propose a Bayesian optimisation (BO) approach for NAS that combines the Weisfeiler-Lehman graph kernel with a Gaussian process surrogate. Our method not only optimises the architecture in a highly data-efficient manner, but also affords interpretability by discovering useful network features and their corresponding impact on the network performance. Moreover, our method is capable of capturing the topological structures of the architectures and is scalable to large graphs, thus making the high-dimensional and graph-like search spaces amenable to BO. We demonstrate empirically that our surrogate model is capable of identifying useful motifs which can guide the generation of new architectures. We finally show that our method outperforms existing NAS approaches to achieve the state of the art on both closed- and open-domain search spaces.

Published as a conference paper at ICLR 2021
INTERPRETABLE NEURAL ARCHITECTURE SEARCH VIA BAYESIAN OPTIMISATION WITH WEISFEILER- LEHMAN KERNELS
Binxin Ru", Xingehen Wan', Xiaowen Dong, Michael A. Osborne Machine Learning Research Group University of Oxford, UK (robin, xwan, xdong, mosb) @robots. ac.
ABSTRACT
Current neural architecture search (NAS) strategies focus only on finding a sin- gle, good, architecture. They offer little insight into why a specific network is performing well, or how we should modify the architecture if we want further improvements. We propose a Bayesian optimisation (BO) approach for NAS that combines the Weistciler-Lehman graph kernel with a Gaussian process surrogate. Our method optimises the architecture in highly data-efficient manner: it is capable of capturing the topological structures of the architectures and scalable to large graphs, thus making the digediimensionl and graph-like search spaces amenable to BO. More importantly, our method affords interpretability by dis- covering useful network features and their corresponding impact on the network performance. Indeed, we demonstrate empirically that our surroaate model is capa- ble of identifying useful motifs which can guide the generation of new architectures. We finally show that our method outperforms existing NAS approaches to achieve the state of the art on both closed- and open-domain search spaces.
INTRODUCTION
Neural architecture search (NAS) aims automate the design of good neural network architectures for a given task and dataset. Although different NAS strategies have led to state-of-the-an oftt---rttt-tttt neural
architectures, outperforming human experts' design on a variety of tasks (Real et al. [017) 7 Zoph and
2017 Cai et al. 2018 Liu et al. 2018a by Luo et al. 2018 Pham et al. 2018 8 Real et al.) 2018)
Zoph et al. 2018a Xie et al. 2018). these strategies behave in a black- fashion, which returns little design insight except for the final architecture for deployment. In this paper, we introduce
the idea of interpretable NAS, extending the learning scope from simply the optimal architecture to interpretable features. These features can help explain the performance of networks searched and guide future architecture design. We make the first attempt at interpretable NAS by proposing new NAS method, NAS-BOWL; our method combines a Gaussian process (GP) surrogate with the Deisfeiler-Lehmarl (WL) subtree graph kernel (we term this surrogate GPWL) and applies it within the Bayesian Optimisation (BO) framework to efficiently query the search space. During search, we harness the interpretable architecture features extracted by the WL kernel and learn their corresponding effects on the network performance based on the surrogate gradient information.
Besides offering new perspective interpratability, our method also improves over the existing BO-based NAS approaches. To accommodate the popular cell-based search spaces, which are non-
continuous and graph-like (Zoph et al. 2018a: Ying et al. 2019 Dong and Yangl 2020). current approaches either rely on encoding schemes (Ying et al.] 2019 White et al., 2019) ) or manually designed similarity metrics (Kandasamy al. 2018). both of which are not scalable to large architectures and ignore the important topological structure of architectures. Another line of work employs graph neural networks (GNNs) construct the BO surrogate (Ma et al.) 2019 Zhhng et al.) 2019 Shi et al. 2019); however, the GNN design introduces additional hyperparameter tuning, and the training of the GNN also requires large amount of architecture data, which is particularly
thub. com "qqual contribution. Codes available http:////ggghh........o////e////

---

Published as a conference paper at ICLR 2021
expensive to obtain in NAS. Our method, instead, uses the WL graph kernel to naturally handle the graph-like search spaces and capture the topological structure of architectures. Mcanwhile, our surrogate preserves the merits of GPs in data-efficiency, uncertainty computation and automated hyperparameter treatment. In summary, our main contributions are as follows:
We introduce GP-based BO strategy for NAS, NAS-BOWL, which is highly query-efficient and amenable to the graph-like NAS search spaces. Our proposed surrogate model combines GP with the WL graph kernel (GPWL) to exploit the implicit topological structure of architectures. It is scalable to large architecture cells (e.g. 32 nodes) and can achieve better prediction performance than competing methods.
We propose the idea of interpretable NAS based on the graph features extracted by the WL. kernel and their corresponding surrogate derivatives. We show that interpretability helps in explaining the performance of the searched neural architectures. As a singular example concrete application, we propose simple yet effective motif- transfer learning baseline to warm-start search new image tasks.
We demonstrate that surrogate model achieves superior performance with much fewer ob- servations in search spaces of different sizes, and that our strategy both achieves state-of-the-art performances both BAS-Bench datasets and open-domain experiments while being much more efficient than comparable methods.
2 PRELIMINARIES
Graph Representation of Neural Networks Architectures in popular NAS search spaces can be represented acyclic directed graph (Elsken et al., 2018 Zoph al., (018b) Ying al.) 2019] Dong and Yang. 2020 Xie et al., 2019), where each graph node represents an operation unit or layer (e.g. conv3x3 on relu Ying et al. (2019)) and each edge defines the information flow from one layer to another. With this representation, NAS can be formulated as an optimisation problem to find the directed graph and its corresponding node operations (i.e. the directed attributed graph G) that give the best architecture validation performance yG)): G arg maxç v(G).
Bayesian Optimisation and Gaussian Processes To solve the above optimisation, we adopt BO, which query-efficient technique for optimising a black-box, expensive-to-evallate ob- jective (Brochu et al.) 2010). BO uses statistical surrogate to model the objective and builds an acquisition function based on the surrogate. The next query location is recommended by optimising the acquisition function which balances the exploitation and exploration. We use GP as the surrogate model in this work, as it can achieve competitive modelling performance with small amount of query data (Williams and Rasmussen, 2006) and give analytic predictive posterior mean ((G,\D,-1) and variance k(Gr, D. on the heretofore unseen graph Ge given
observations: ((G(DD,)) = k(G,, G K-1 1K--11a--1 and k:GG, (D,)) = k(G,, G²) k(G,, G k (G G.) where G = (G....., G.-13 and Via-1 = [y1 Vi...... .........---111 11-1 are the t observed graphs and objective function values, respectively, and ) is the (i, element of Gram matrix induced on the (i, training samples by k( the graph kernel function. We use Expected Improvement (Mockus et al. 1978) in this work though our approach compatible with alternative choices.
D.-1 = (G14-1,y14-1) [Ka--1y AGG Gý)
Graph Kernels Graph kernels are kernel functions defined over graphs to compute their level of similarity. generic graph kernel may be represented by the function k(-;)) over pair of graphs G and G' (Kriege et al. 2020):
k(G, (CCG)))(((GGG(C)C) ((G))
(2.1)
where Φ6-) is some feature representation of the graph extracted by the graph kernel and (-, )) denotes inner product in the associated reproducing kernel Hilbert space (RKHS) (Nikolentzos et al.. 2019; Kriege et al. 2020). For more detailed reviews on graph kernels, the readers are referred to Nikolentzos et al. (2019). Ghosh al. (2018) and Kriege et al. (2020).
2

---

labels into Published as a conference paper at ICLR 2021
Algorithm 1 NAS-BOW Algorithm. Optional steps of the exemplary use of motif- based warm starting (Sec 3.2) are marked in gray italics.
Initialisation
I: Imput: Maximum BO iterations T, BO batch size b, acquisition function a(-), initial ob- served data on the target task Du. Optional: past-task query data pass and surrogate Spast
Step 1
08722
2: Output: The best architecture G
Arch
Arch
Initialise the GPWL surrogate S with Do do
UB22
Step
for 1,..., ,
34
5:
Pruming based on the past-task motifs then
3
6:
Compute the motif importance scores (equation 3.4 with Span/S on Daaa/D,
7:
while Get
do
Arch
8:
Generate batch of candidate archi- tectures and reject those which contain none of the top 25% good motif's (simi- lar procedure as Fig. a))
Step 4
hro features
features
(..lArch
Pr.dArch Al
B..(Arch
B..(ArhhA)
h=0 features
h=1 features
9:
end while
① Input
@
Convirt
O++
10:
else
MasPael Jell
11:
Generate B candidate architectures G
end if
Figure 1: Illustration of one WL iteration. Given two architecture cells initialisation, WL kemnl first collects the neighbourhood labels of each node (Step 1) and compress the collected h 1 features (Step 2). Each node is then relabelled with = features (Step 3) and the two graphs are compared based on the histogram on both h = and h features (Step 4). This WL iteration will be repeated until h H.
13:
{G = arg maxGes. or (G-1))
14:
Evaluate their validation accuracy (ve,i)
15:
D: + 1 1 U )= (in))im)
16:
Update the surrogate 8 with D,
17:
end for
18: Return the best architecture seen far G7
3 PROPOSED METHOD
We begin by presenting our proposed algorithm, NAS-BOWL in Algorithm [ where there are few key design features, namely the design of the GP surrogate suitable for architecture search (we term the surrogate GPWL) and the method to generate candidate architectures each BO iteration. We will discuss the first one in Section 3.1, For architecture generation, we either generate the new candidates via random sampling the adjacency matrices, or use a mutation algorithm similar those used in number of previous works (Kandasamy et al.) 2018 Ma et al.) 2019 White et al.) 2019 Shi et al., 2019): each iteration, we generate the architectures by mutating number of queried architectures that perform the best. Generating candidate architectures in this way enables us to exploit the prior information on the best architectures observed so far to explore the large search space more efficiently. We report NAS-BOW with both strategies in our experiments. Finally, to give a demonstration of the new possibilities opened by our work, we give an exemplary practical use of intepretable motifs for transfer learning in Algorithm I which is elaborated in Sec 3.2
3.1 SURROGATE AND GRAPH KERNEL DESIGN
To enable the GP work effectively on the graph-like architecture search space, selecting a suitable kernel function is arguably the most important design decision. We propose to use the Weisfeiler- Lehman (WL.) graph kernel (Shervashidze et al. (011) enable the direct definition of GP surrogate the graph-like search space. The WL kernel compares two directed graphs based on both local and global structures. It starts by comparing the node labels of both graphs via a base kernel Anase (Φo (G), Φ (o"))) where (G( denotes the histogram of features at level h = (i.e. node features) the graph. where h is both the index of WL iterations and the depth of the subtree features extracted. For the WL kernel with h > 0, shown in Fig. [ it then proceeds collect features by aggregating neighbourhood labels, and compare the two graphs with khase (6) (G), Φ (G") based the subtree structures of depth (Shervashidze al. 2011 Höppner and Jahnke 2020
3

---

Published as a conference paper at ICLR 2021
The procedure then repeats until the highest iteration level h = H specified and the resulting WL kernel is given by:
H
k (G, = Σ ( ox))
(3.1)
h=
In the above equation, Abase is base kernel (such as dot product) over the vector feature embedding. As h increases, the WL kernel captures higher-order features which correspond to increasingly larger neighbourhoods and features at each h concatenated to form the the final feature vector (Ø(G) = (o G).... HH (G))). The readers are referred to App. for more detailed algorithmic descriptions of the WI kernel.
We argue that WI. desirable for three reasons. First, in contrast to many ad hoc approaches, WI. established with proven successes on labelled and directed graphs, by which networks are represented. Second, the WL representaatin of graphs is expressive, copoloyy-preserving
yet interpretable: MMoris et al. (2019) show that WL is as powerful as standard GNNs in terms of discrimination power. However, GNNs requires relatively large amount of training data and thus is more data-inefficient (we validate this in Sec. 55. Also, the features extracted by GNNs are harder to interpret compared to those by WL. Note that the WL kernel by itself only measures the similarity between graphs and does not aim to select useful substructures explicitly. is our novel deployment of the WL. procedure (App. A) for the NAS application that leads to the extraction of interpretable features while comparing different architectures. We further make smart use of these network features to help explain the architecture performance in Sec 3.2] Finally, WL is efficient and scalable: denoting {n, m as the number of nodes and edges respectively, computing the Gram matrix on N training graphs may scale O(NHm + N2 Hn) (Shervashidze et al. 201 As we show in App. E.3 in typical cell-based spaces H S 3 suffices, suggesting that the kernel computation cost is likely eclipsed by the ((N3) scaling of GP we incur nonetheless. This is to be contrasted to approaches such as path encoding in White et al. (2019), which scales exponentially with n without truncation, and the edit distance kernel Jin al. (2019), whose exact solution is NP-complete (Zeng et al. 2009).
With the above-mentioned merits, the incorporation of the WL kernel permits the usage of GP-based BO on various NAS search spaces. This enables the practitioners to harness the rich literature of GP-based BO methods on hyperparameter optimisation and redeploy them on NAS problems. Most prominently, the use of GP surrogate frees us from hand- picking the WL hyperparameter H as we can automatically learn the optimal values by maximising the Bayesian marginal likelihood. As we will justify in Sec. 5 and App. E.3 this process is extremely effective. This renders further major advantage of our method as it has no inherent hyperparameters that require manual taning. This reaffirms with our belief that a practical NAS method itself should require minimum tuning. it is almost impossible to run traditional hyperparameter search given the vast resources required. Other enhancements, such as improving the expessiiveeess of the surrogate by combining multiple types of kernels, are briefly investigated in App- C We find the amount of performance gain depends on the NAS search space and a WL kernel alone suffices for common cell-based spaces.
3.2 INTERPRETABLE NAS
The unique advantage of the WL kernel is that it extracts interpretable features, i.e. network motifs from the original graphs This in combination with our GP surrogate enables us to predict the effect of the extracted features on the architecture performance directly by examining the derivatives of the GP predictive mean w.r.t. the features. Derivatives as tools to interpret MI. models have been used previously (Engelbrecht et al. 1995 Koh and Liang [017 Ribeiro et al. 2016) but, given the GP, we can compute these derivatives analytically. Following the notations in Sec. 2 the derivative with respect to のi (G.), the j-th element of (GG,) (the feature vector of a graph G2) is Gaussian with an expected value:
Oy E EptviG.R 1) La (G.) d
Op D(D(C.), (G.)
P1--1)
K K
(3.2)
where 1 = (dG))).... () is the feature matrix stacked from the feature vectors of the
previous observations. Intuitively, since each (G,) denotes the count of a WL feature in G., its derivative naturally encodes the direction and sensitivity of the objective (in this case the predicted
validation accuracy) about that feature. Computationally. since the costly term, K is already computed in the posterior mean, the derívatives can be obtained at minimal additional cost.
4

---

Published as a conference paper at ICLR 2021
Best motils
Werst motifs
Besl moliís
Worsi motifs
cone cone
nor CarV
ner cony 3rd
output
Dvg pool
200 pool 3xd
max pool
(a) Best and worst motif's identified on N201 (CIFAR- 10) dataset using 300 training samples (left) and on DARTS search space after 3 GPU days of scarch by HAS-BOWL (right). For DARTS space, the motif boxed in pink is featured in all optimal calls found by various NAS methods in Fig 3
cifar10-valid
citar100
ImageNet16-
DARTS Search Space
30
all
good
15
all
good
10
all
good
60
all
good
had
bad
bad
20
0
0
0.90
0.7
Val Acc
0.8
0.9
0.4
Val Acc
0.6
0.8
0.0
0.2 0.4
Val Acc
Val Acc
(b) Validation accuracy distributions of the validation architectures on different tasks of N201 (left 3) and DARTS (right). all denotes the entire validation set, while good/bad denote the distributions of the architectures with at least 1 best/worst motif, respectively; dashed lines denote the distribution medians. Note that in all cases, the good subset includes the population max and in N201, the patterns solely trained the CIFAR-10 task also transfer well to CIFAR- 10AAR-100/mmaeNee16.
Figure 2: Motif discovery on N201 (CIFAR- 10) and DARTS spaces.
By evaluating the aforementioned derivative at some graph G, we obtain the local sensitivities of the objective function around (GG). To achieve global attribution of network performance w.r.t interpretable features which we are ultimately interested in, we take inspirations from the principled averaging approach featured in many gradient- based attribution methods (Sundararajan et al. 2017, Ancona et al., (0177), by computing and integrating over the aforementioned derivatives at all training samples to obtain the averaged gradient (AG). AG of the j-th feature @ is given by:
0p
- JaniCID a (G)
AG( = EG
p( (G))dg((G)
(3.3)
(G)
Fortunately, in WL kernel, (-) E Z22 and thus p((2() (.)) is discrete, the expectation integral reduces to a weighted summation over the "prior" distribution p(d (-))v. To approximate p( (-)), we count the number of occurrences of each feature & (G₂) in all the training graphs (Gi,... G where & (.) is present and assign weights according to its frequency of occurrence. Formally, denoting G as the subset of the training graphs where for each of its element Φ² > O, we have
E1e,, Wn (1b5) [C.] where Wr, (x,)
By
18
1
AG(O))
Σ (n))()), m2'=1
(3.4)
|9l Σn= Wr (Ø,)
9
where 5(.,)) :) is the Kronecker delta function and the cardinality of a set. Finally, we additionally incorporate the uncertainty of the derivative estimation by also normalising AG with the square root of the empirical variance (EV) to penalise high- nigh-variance (hence less trustworthy as a whole) gradient
estimates closer to O. EV may be straightforwardly computed:
EV (V( = VG (G)
0p
]
= Ee [ (o) )" (Res Op
1)
(3.5)
The resultant derivatives w.r.t. interpretable features AG(d')/ /BV(0)) allow us to directly identify the most influential motifs on network performance. By considering the presence or absence of such motifs, we may explain the competitiveness of an architecture or the lack of it, provided the surrogate is accurate which we show is the case in Sec. 5 More importantly, beyond passive explaining, we can also actively use these features as building blocks to facilitate manual construction of promising networks, or as priors to prune the massive NAS search space, which we believe would be of interest to both human designers and NAS practitioners. To validate this, we train our GPWL on architectures drawn from various search spaces, rank all the features based on their computed derivatives and show the motifs with most positive and negative derivatives (hence the most and least desirable features]
For reproduciabilltty, we include detailed procedures and selection criteria in App. D.1
5

---

Published as a conference paper at ICLR 2021
dil conv 3x33
imput max pool_ 3x3
sep cop_conv_ar 3x3
sep_conv _ocv__S5v
add
dl_coo__555 5x5
output
avg avo_ 3x3
Figure 3: Best cells discovered by (left to right) DARTS, ENAS, LaNet, BOGCN and NAS-BOWL (ours) in the DARTS search space. Note the dominance of separable convolutions (especially 3x3) in operation nodes (i.e. nodes excluding input, output and add) and the presence of highlighted structures encompassing the boxed motif in Fig. in all cells.
We present the extracted network motifs the CIFAR-10 task of NAS-Bench-201 (N201) (Dong and Yang 2020) and DARTS search space in Fig. aa). The motifs extracted on other N201 image and NAS-Bench- 101 (N101) (Ying al. 2019) are shown in App. D.2. The results reveal some interesting insights on network performance: for example, almost every good motif in N201 contains conv_ x and all-but-one good motif's in the DARTS results contain at least one separable _onv_3x3. In fact, this preference over (separable) convolutions is almost universally observed in many popular NAS methods (Liu et al. 2018a| [hi al.) 2019) Wang et al.,
tasks
Pham et al. (0188) and ours: besides skip links, the operations in their best cells are dominated
by separable convolutions (Fig. 3. Moving from node operation label to higher-order topological features, in both search spaces, our GPWL consistently finds series of high-performing motifs that entail the parallel connection from input to multiple convs often of different filter sizes this corresponds to the grouped convolution unit critical to the success of, e.g. ResNeXt (Xie et al.) 2017). A specific example is the boxed motif in Fig. 2 a), which combines parallel convs with skip link. This motif other highly similar ones consistently present in the optimal cells found by many NAS methods including ours (as shown in Fig. 3 despite the disparity in their search strategies. This suggests a correlation between these motifs and good architecture performance. Another observation is that majority of the important motifs for both search spaces in Fig. aa involve the input. From this and our previous remarks on the consensus amongst NAS methods in favouring certain operations and connections, we hypothesise that at least for cell-based search space, the network performance might be determined more by the connections in the vicinity to the inputs (on which the optimal cells produced by different NAS methods are surprisingly consistent) than other parts of the network (on which they differ). This phenomenon is partly observed in Shu et al. (219),, where the authors found that NAS algorithms tend to favour architecture cells with most intermediate nodes having direct connection with the input nodes. The verification of this hypothesis is beyond the scope of this paper, but this shows the potential of our GPWL in discovering novel yet interpretable network features, with potential implications for both NAS and manual network design.
Going beyond the qualitative arguments above, we now quantitatively validate the informativeness of the motifs discovered. After identifying the motifs, in N201, we randomly draw another 1,000 validation architectures unseen by the surrogate. Given the motifs identified in Fig. 2a)), an architecture is labelled either "good" (2 1 good motif), "bad" (2 1 bad motif) or neither. Note if an architecture contains both good and bad motifs, is both "good" and "bad". As demonstrated in Fig. b). we indeed find that the presence of important motifs is predictive of network performance. A similar conclusion holds for DARTS space. However, due to the extreme cost in sampling the open-domain space, we make two modifications our strategy. Firstly, the training samples are taken from BO run, instead of randomly sampled. Secondly, we reuse the training samples for Fig. (bb) instead of sampling and evaluating the hold-out sets. The key takeaway here that motifs are effective in identifying promising and unpromising candidates, and thus can be used to aid NAS agents to partition the vast combinatorial search space, which often considered a key challenge of NAS, and to focus the most promising sub-regions. More importantly, the motifs are also transferable: while the patterns in Fig. 2 a) are solely trained on the CIFAR-1Ó, they generalise well to CIFAAR-100ImmgeNeete 6 tasks this is unsurprising,
one key motivation of cell-based search space is exactly to improve transferability of the learnt structure across related tasks (Zoph et al.) 2018a). Given that motifs are the building blocks of the cells, we expect them transfer well, too.
With this, we propose a simple transfer learning baseline could be practically useful for NAS. Specifically, we can exploit the motifs identified on one task to warm-start the search on a related new task. With reference to Algorithm [ under the transfer learning setup, we use a GPWL surrogate trained on the query data of past related task Spest as well as the surrogate the new target task S to compute the AG of motifs present in queried architectures
singular demonstration of how motifs

---

Published as a conference paper at ICLR 2021
(equation 3.4) and identify the most positively influential motifs similar to Fig. 2 aa) (Line 3). We then use these motifs to generate a set of candidate architectures Gr for optimising the acquisition function at every BO iteration on the new task; Specifically, we only accept a candidate if it contains at least one of the top 25% good motifs (i.e. pruning rule). Finally, with more query data obtained on the target task, we will dynamically update the surrogate S and the motif scores mitigate the risk of discarding motif's purely based on the past task data. Through this, we force the BO agent to select from a smaller subset of architectures deemed more promising from a previous task, thereby "warm starting" the new task. We briefly validate this proposal in the N201 experiments of Sec.
RELATED WORK
In terms of NAS strategies, there have been several recent attempts in using BO (Kadaaaayy et al. 2018, Ying et al., 2019 Ma et al.] 2019 [Shi et al.] 2019; White et al. 2019). To overcome the limitations of conventional BO for discrete and graph-like NAS search spaces, Kandasamy et al. (2018) use optimal transport to design similarity measure among neural architectures while Ying ct al. (019) and White et al. (2019) suggest encoding schemes to characterise neural architectures with discrete and categorical variables. Yet, these methods are either computationally inefficient or not scalable to large architectures/cells (Shi et al.) 2019; White et al.] 2019). Alternatively, several works use graph neural networks (GNNs) as the surrogate model (Ma al. 2019 Zhang et al.] 2019 Shi et al. (2019) to capture the graph structure of neural networks. However, the design of the GNN introduces many additional hyperparameters to be tuned and GNN requires relatively large number of training data to achieve decent prediction performance as shown in Sec. 5 Another related work (Ramachandram et al. 2018) apply GP-based BO with diffusion kernels to design multimodal fusion networks; however, it assigns each possible architecture as node in an undirected super-gran graph and the need for construction of and computation on such super-graphs graphs limits the method to relatively small search spaces. In terms of interpretability, [Shu et al. (2019) study the connection pattern of network cells found by popular NAS methods and find a shared tendency for choosing wide and shallow cells which enjoy faster convergence. You al. (2020), by representing neural networks as relational graphs, observe that the network performance depends on the clustering coefficient and average path length of its graph representation. [Radosavovic et al. (2020) propose a series of manual design principles derived from extensive empirical comparison to refine a ResNer-based search space. Nevertheless, all these works do not offer NAS strategy, and purely rely on human experts derive insights on NAS architectures from extensive empirical studies. In contrast, our method learns the interpretable feature information without human inputs while searching for the optimal architecture.
5 EXPERIMENTS
Surrogate Regression Performance We examine the regression performance of GPWL on several NAS datasets: NAS-Bench-100 101 (N101) on CIFAR-10 (Ying et al., CIFAR-100 and ImageNet16. As both datasets only contain CIFAR-sizA images and relatively small architecture celle" to further demonstrate the scalability of our proposed methods to much larger architectures, we also construct a dataset with 547 architectures sampled from the randomly wired graph generator described in Xie et al. (2119;; each architecture cell has 32 operation nodes and all the architectures are trained on the Flowers (2 dataset (Nilsback and Zisserman, 2008) Similar to Ying et al.] ) Dong and Yang (2020); Shi et al. (2019). we use Spearman's 's rank correlation between predicted validation accuracy and the true validation accuracy the performance metric, as what matters for comparing architectures is their relative performance ranking.
al.,20199, 2 and N201 on CIFAR- 10,
We compare the regression performance against various competitive baselines, including NASBOT (Kandasamy et al. 2018). GPs with path encodings (P (Pache) (White et al.) 2019). GNN (Shi 2019) which uses a combination of graph convolutional network and a final Bayesian linear regression layer as the surrogate, and COMBO (Oh et al. 2019 which use GP with a diffusion kernel on a graph representation of the combinatorial search spaces. We report the results in Fig. 4 our GPWL surrogate clearly outperforms all competing methods on all the NAS datasets with much
II N101 and N201, each cell is a graph of and nodes, respectively.
We choose COMBO as methodologically it is very close to the most related work (Ramachandram et al. 2018 whose implementation is publicly available.
7

---

Published as a conference paper at ICLR 2021
60
0.9
67--3
Bonc Corrre
GPAA
6.
Enchdn RASSOT
039
223
230 cxrples
230 A6
30
Mymber Nymber of ng Saiples
(a) N201(C-10)
(b) N201(C-100)
(c) (I01((m)
(d) N101
(c) Flowers
Figure 4: Mean Spearman correlation achieved by various surrogates across 20 trials on different datasets. Error bars denote +1 standard error. The red dashed lines are there to help with visual comparison between the performance of GPWL and other baselines.
7.0
10.0
6.8
92
Aecracy Text Fr
Besan Telk
55.0
$3.5
13.0
30
75
u0
325
02
160
125
Numizer Aechinactamm Exaluded
Homber Anchtiecturee Evelanee
number of Archiledturea Evelusted
(a) N101
(b) N201(C-10)
(c) N201(C-100)
(d) (ImageN))
2.0
10.5
73.5
55.0
6.0
15.5
6.6
23.5
9.4
0.2
23.0
6.0
53.5
27.0
53.0
300 125 Nuritera Eechinettonn Eantlated
25
23
50
75
300
323
23
30
100
123
25
300
125
(c) N101
( N201(C-10)
gg) (201(C-100)
(h) (20
NASBOWLM
BANANASF
BANANASM
regulanizod__vvlllo ovolution
tpe
smacbo
NASBOWLr
genbo
random search
Figure 5: Median test error on NAS NAS-Bench datasets with deterministic (top row) and noisy (bottom row) observations from 20 trials. Shades denote 1 standard error and black dotted lines are ground- truth optima. Note the seemingly large regret N201 (ImageNet) is due to that there are only out of 15.6K architectures with test error in the interval of [52.69 (optimum), 53.25).
less training data: specifically, GPWL requires least 3 times less data than GNN and Patoen and 10 times less than COMBO on N201 datasets. It is also able to achieve high rank correlation on datasets with larger search spaces such as N101 and Flowers 102 while requiring 20 times less data than GNN on Flowers 102 and 30 times less data on N101. Moreover, in BO, uncertainty estimates are as important as the prediction accuracy; we show that GPWL produces sound uncertainty estimates in App. E.I Finally, in addition to these surrogates previously used in NAS, we also demonstrate that our surrogate compares favourably against other popular graph kernels, as discussed App. F.2
Architecture Search on NAS- Datasets We benchmark our proposed method, NAS-BOWL.
against a range of existing methods, including random search, TPE (Bergstra et al. 2011).
Reinforce-
ment Learning (x: 1) (Zoph and Le 2016), BO with SMAC (smacbo) (Hutter et al."
2011). regularised
evolution RRaal et al.] 2019) and BO with GNN surrogate (genbo) (Sii et al. we also include BANANAS (White et al., 2019) which claims the state-of- both NAS-Bench datasets, validation errors of different random seeds are provided, thereby creating noisy objective functions. We perform experiments using the deterministic setup described White et al.] (2019), where the validation errors over multiple seeds are averaged to eliminate stochasticity. and also report results with noisy objective functions. We show the test results both setups in Fig. aland the validation results in App. F.3 In these figures, we use NASBOWL. and NASBOWLE to denote NAS-BOWL with architectures generated from mutating good observed candidates and from random sampling, respectively. Similarly,
2019) On N101, performance. In
SAAAAANNAS///AAAAAA represent the BANANAS with mutation/random sampling (White et al. 2019). On CIFAR- 100/ImageNet tasks of N201, we also include NASBOWLm (TL) which is NASBOWLm with additional knowledge motifs transferred from a previous run on the CIFAR-10 10 task of N201 to prune the candidate architectures as described
in Sec. 3.2 The readers are referred to App. F2 for detailed setups.
8

---

Published as a conference paper at ICLR 2021
Table I: Performances CIFAR- 10. GPU days do not include the evaluation cost of the final architecture; NAS-BOWL results from 4 random seeds on a single NVIDIA GeForce RTX 2080 Ti.
Algorithm
Avg. Error
Errer
#Params(M)
GPU Days
GP-NAS at
2020
3.79
3.9
DARTS
2018a
2.7620.08
3.3
ENAS
Pham et ml
2018
2.89
4.6
6
ASHA Li and alaak
2019
3. 3.03 2.330.05 13
2.85
2.2
9
Randon WS
2019
2.85 2.55..00
2.71
4.3
10
BANANAS WWhife ot el
2019
2.64
2.57
12
BOGCN (Sl
2.61
3.5
93*
LaNet
Wang el
2019
2.53 2.00
3.2
150
NAS-BOWL
16611o.oo
2.50
3.7
1: expanded search space from DARTS. *: estimatedd by us. not reported.
It is evident that NAS-BOWL outperforms all baselines on all NAS- tasks in achieving both lowest validation and test errors. The experiments with noisy observations further show that even in more realistic setup with noisy objective function observations, well as it inherits the robustness against noise from the GP. The preliminary experiments on transfer learning also show that motifs contain extremely useful prior knowledge that may be transferred to warm-start a related task: notice that even the architectures at the very start without any search in realistic setting, searching directly on
still performs very
already perform well this is partieularly appealing. large-scale datasets like ImageNet from scratch is extremely expensive. While further experimental validation on wider range of search spaces or tasks of varying degrees of similarity are required to fully verify the effectiveness of this particular method, we feel as an exemplary use of motifs, the promising preliminary results here already demonstrates the usefulness. Finally, we perform ablation studies in App. F3
Open-domain Search We finally test NAS-BOWL the open-domain search space from DARTS (Liu et al. 2018a). We allow a maximum budget of 150 queries, and we follow the DARTS setup (See App. for details): during the search phase, instead of training the final 20-cell architectures, we train a small 8-cell architectures for 50 epochs. Whereas this results in significant computational savings, it also leads to the degraded rank correlation of performance during search and evaluation stages. This leads to a more challenging setup than most other sample-based methods which train for longer epochs and/or search on the final 20-cell architectures directly. Beyond this, also search single cell structure and use it for the two cell types (normal and reduction) defined in DARTS search space. We also use default maximum number of 4 operation blocks to fit the training on a single GPU: this is contrasted to, e.g. ENAS and LaNet that allow for up to 5 and 7 blocks, respectively.
We compare NAS-BOW with other methods in Table D and the best cell found by NAS-BOWL is already shown in Fig. in Sec. 3.2 To ensure fairness of comparison, we only include previous methods with comparable search spaces and training techniques, and exclude methods that train much longer and/or use additional tricks (Liang et al., 2019 Cai et al. 2019). It is evident that NAS- BOWL finds very promising architectures despite operating GaU-days, NAS-BOWL. is of comparable computing cost to the one-shot methods but performs on par with better than methods that consume orders of magnitude more resources, such as LaNet which is 50x more costly. Furthermore, it is worth noting that, if desired, NAS-BOWL. may benefit from any higher computing budgets by relaxing the aforementioned restrictions (c.g. train longer on larger architectures during search). Finally, while we use a single GPU, deployed to run on parallel computing resources to further reduce wall-clock time.
more restricted setup. Consuming 3
can be casily
6 CONCLUSION
In this paper, we propose a novel BO-based NAS strategy, NAS-BOWL, which uses a GP surrogate with the WL graph kernel. We show that our method performs competitively on both closed- and open-domain experiments with high sample efficiency. More importantly, our method represents first step towards interpretable NAS, where we propose to learn interpretable network features to help explain the architectures found as well as guide the search on new tasks. The potential for further work is ample: we may extend the afforded interpretability in discovering more use-cases such as on multi-objective settings and broader search spaces. Moreover, while the current work deals primarily with practical NAS, we feel a thorough thcoretical analysis, on e.g., convergence guarantee, would also be beneficial both for this work and the broader NAS community in general.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Esteban Real, Sherry Moore, Andrew Selle, Saurabh Saxena, Yutaka Leon Suematsu, Jie Tan, Quoc V Le, and Alexey Kurakin, Large-scale evolution of image classifiers, International Conference Machine Learning (ICML), pages 2902-2911, 2017.
Barret Zoph and Quoc Le. Neural architecture search with reinforcement learning. In International Conference Learning Representations (ICLR), 2017.
Han Cai, Tianyao Chen, Weinan Zhang, Yong Yu, and Jun Wang. Efficient architecture search by network transformation. In AAAI Conference on Artificial Intelligence, 2018.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. Darts: Differentiable architecture search. arXiv
preprint arXiv: 09055, 2018a.
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. European Conference Computer Vision (ECCV), pages 19-34, 2018b.
Renqian Luo, Fei Tian, Tao Qin, Enhong Chen, and Tie- Yan Liu. Neural architecture optimization. In Advances in Neural Information Processing Systems (NIPS), pages 7816-7827, 2018.
Hieu Pham, Melody Guan, Barret Zoph, Quoe Le, and Jeff Dean. Efficient neural architecture search via parameter sharing. In International Conference on Machine Learning (ICML), pages 4092-4101, 2018.
Esteban Real, Alok Aggarwal, Yanping Huang, and Quoc V Le. Regularized evolution for image classifier architecture search. arXiv: /802,01548, 2018.
Barret Zoph, Vijay Vasudevan, Jonathon Shlens, and Quoe V Le. Learning transferable architectures for scalable image recognition. In Computer Vision and Pattern Recognition (CVPR), pages 8697-87 10, 2018a.
Sirui Xie, Hchui Zheng, Chunxiao Liu, and Liang Lin. Snas: stochastic neural architecture search. arXiv preprint arviv: /8/2.099/ 2018.
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 (ICML), pages 7105-7114, 2019.
Xuanyi Dong and Yi Yang. Nas-bench-201 Extending the scope of reproducible neural architecture search. arXiv preprint arXiv:200J.00326 2020.
Colin White, Willie Neiswanger, and Yash Savani. Bananas: Bayesian optimization with neural architectures for neural architecture search. arXiv preprint arXiv: 11858, 2019.
Kirthevasan Kandasamy, Willie Neiswanger, Jeff Schneider, Barnabas Poczos, and Eric P Xing. Neural architecture search with Bayesian optimisation and optimal transport. In Advances in Neural Information Processing Systems (NIPS), pages 2016-2025, 2018.
Lizheng Ma, Jiaxu Cui, and Bo Yang. Deep neural architecture search with deep graph Bayesian optimization. In Web Intelligence (WI), pages 500-507. JEEE/WIC/ACM, 2019.
Chris Zhang, Mengye Ren, and Raquel Urtasun. Graph hypernetworks for neural architecture search. In International Conference on Learning Representations, 2019. URL https:://pperreviee
net fort/forum? iitorrmmiid-ee www
Han Shi, Renjie Pi, Hang Xu, Zhenguo Li, James Kwok, and Tong Zhang. Multi-objective neural architecture search via predictive network performance optimization, 2019.
Thomas Elsken, Jan Hendrik Metzen, and Frank Hutter. Neural architecture search: A survey. arXiv: 1808 05377, 2018.
10

---

Published as a conference paper at ICLR 2021
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, pages 8697-8710, 2018b.
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, pages 1 1284-122 1293, 2019.
Eric Brochu, Vlad M Cora, and Nando De Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hicrarchical reinforcement learning. arXiv preprint arXiv: 1012::00 2010.
Christopher KI Williams and Carl Edward Rasmussen. Gaussian processes for muchine learning, volume 2. MIT press Cambridge, MA, 2006.
Jonas Mockus, Vytautas Tiesis, and Antanas Zilinskas. The application of bayesian methods for seeking the extremum. Towards global optimization, 2(117-129):2, 1978.
Nils M Kriege, Fredrik D Johansson, and Christopher Morris. A survey on graph kernels. Applied Network Science, 5(1):1-42, 2020.
Giannis Nikolentzos, Giannis Siglidis, and Michalis Vazirgiannis. Graph kernels: A survey, arXiv preprint arXiv: /22/8, 2019.
Swarnendu Ghosh, Nibaran Das, Teresa Gonçalves, Paulo Quaresma, and Mahantapas Kundu. The journey of graph kernels through two decades. Computer Science Review, 27:88-111, 2018.
Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mchlhorn, and Karsten M Borgwardt. Weisfeiler-lchman graph kernels. Journal of Machine Learning Research, 12(77):
4539-25611 2011.
Frank Höppner and Maximilian Jahnke. Enriched weisfeiler-lhhman kernel for improved graph clustering of source code. In International Symposium on Intelligent Data Analysis, pages 248- 260. Springer, 2020.
Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe Weisfeiler and leman go neural: Higher-order graph neural networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pages 4602-4609, 2019.
Haifeng Jin, Qingquan Song. and Xia Hu. Auto-keras: An efficient neural architecture search system. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1946-1956, 2019.
Zhiping Zeng, Anthony KH Tung, Jianyong Wang, Jianhua Feng, and Lizhu Zhou. Comparing stars: On approximating graph edit distance. Proceedings of the VLDB Endowment, 2(1):25 -36, 2009.
Andries Petrus Engelbrecht, Ian Clocte, and Jacek M Zurada. Determining the significance of input parameters using sensitivity analysis. In International Workshop on Artificial Neural Networks, pages 382-388. Springer, 1995.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions. In Proceedings of the 34th International Conference on Machine Learning-Vool Volume 70, pages 1894.1894. JMLR. org, 2017.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. wwhy should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference on knowledge discovery and data mining, pages 1135-1144, 2016.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. arXiv preprint arXiv: /703.01363 2017.
Marco Ancona, Enea Ceolini, Cengiz Öztireli, and Markus Gross. Towards better understanding of gradient- based attribution methods for deep neural networks. arXiv preprint 2017.
11

---

Published as a conference paper at ICLR 2021
Linnan Wang, Saining Xie, Teng Li, Rodrigo Fonseca, and Yuandong Tian. Sample-efficient neural architecture search by learning action space. arXiv preprint arXiv:1906.06832. 2019.
Saining Xie, Ross Girshick, Piotr Dollár, Zhuowen Tu, and Kaiming He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492-1500, 2017.
Yao Shu, Wei Wang, and Shaofeng Cai. Understanding architectures learnt by cell-based neural architecture search. In International Conference on Learning Representations, 2019.
Dhanesh Ramachandram, Michal Lisicki, Timothy J Shields, Mohamed R Amer, and Graham W Taylor. Bayesian optimization graph-structured search spaces: Optimizing deep multimodal fusson architectures. Neurocomputing, 298:80-89, 2018.
Jiaxuan You, J. Leskovec, Kaiming He, and Saining Xie. Graph structure of neural networks. International Conference Machine Learning, 0bs/2000.065553 2020.
Iija Radosavovic, Raj Prateek Kosaraju, Ross Girshick, Kaiming He, and Piotr Dollár. Designing network design spaces. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 14428-14434 2020.
Maria-Eles Brria- Nilsback and Andrew Zisserman. Automated flower classification over a large number of classes. In 2008 Sixth Indian Conference on Computer Vision, Graphics and Image Processing, pages 722-729. IEEE, 2008
Changyong Oh, Jakub Tomczak, Efstratios Gavves, and Max Welling. Combinatorial bayesian optimization using the graph cartesian product. In Advances in Neural Information Processing Systems, pages 29 1910-2920, 2019.
James S Bergstra, Rémi Bardenet, Yoshua Bengio, and Balázs Kégl. Algorithms for hyper-parameter optimization. In Advances in Neural Information Processing Systems (NIPS), pages 2546-2554, 2011.
Barret Zoph and Quoc V Le. Neural architecture search with reinforcement learning. arXiv preprint arX1v:161..0158, 2016.
Frank Hutter, Holger H Hoos, and Kevin Leyton-Brown. Sequential model-based optimization for general algorithm configuration. In International conference learning and intelligent optimization, pages 507-523. Springer, 2011.
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, pages 4780-4789, 2019.
Hanwen Liang, Shifeng Zhang, Jiacheng Sun, Xingqiu He, Weiran Huang, Kechen Zhuang, and Zhenguo Li. Darts+: Improved differentiable architecture search with early stopping. arXiv preprint (ttv::/99000000
2019.
Han Cai, Ligeng Zhu, and Song Han. ProxylessNAS: Direct neural architecture search on target task and hardware. In International Conference on Learning Representations (ICLR), 2019.
Zhihang Li, Teng Xi, Jiankang Deng, Gang Zhang, Shengzhao Wen, and Ran He. Gp-nas: Gaussian process based neural architecture search. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1933-11942, 2020.
Liam Li and Ameet Talwalkar. Random search and reproducibility for neural architecture search. arXiv:1902.079 2019.
Nino Shervashidze, SVN Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten Borgwardt. Efficient graphlet kernels for large graph comparison. In Artificial Intelligence and Statistics, pages 488-495, 2009.
Risi Kondor and Horace Pan. The multiscale laplacian graph kernel. In Advances in Neural Information Processing Systemx, pages 2990-2998. 2016.
12

---

Published as a conference paper at ICLR 2021
Nathan de Lara and Edouard Pineau. A simple baseline algorithm for graph classification. arXiv preprint
2018.
Hisashi Kashima, Koji Tsuda, and Akihiro Inokuchi. Marginalized kernels between labeled graphs. In Proceedings of the 20th international conference on machine learning (ICML-03), pages 321-328,
2003.
Boris Weisfeiler and Andrei A Lehman. A reduction of a graph to canonical form and an algebra arising during this reduction. Naucchno-Technichessee Informatsia, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv:18100008826, 2018.
Thomas Gärtner, Peter Flach, and Stefan Wrobel. On graph kernels: Hardness results and efficient alternatives. In Learning theory and kernel machines, pages 129-143. Springer, 2003.
Karsten M Borgwardt and Hans-Peter Kriegel. Shortest-patt patt kernels on graphs. In Fifth IEEE International Conference on Data Mining (CCMM'0), pages 8-pp. IEEE, 2005.
Chih-Long Lin. Hardness of approximating graph transformation problem. In International Sympo- sium Algorithms and Computation, pages 14- Springer, 1994.
Carl Edward Rasmussen. Gaussian processes in machine learning. In Summer School Machine Learning, pages 63-71. Springer, 2003.
Mehmet Gönen and Ethem Alpaydin. Multiple kernel learning algorithms. Journal of machine learning research, 12(64):2211-22 12268,, 2011.
Corinna Cortes, Mehryar Mohri, and Afshin Rostamizadeh. Algorithms for learning kernels based on centered alignment. The Journal of Machine Learning Research, 13(1):795-83) 8288 2012.
Hanxiao Liu, Karen Simonyan, and Yiming Yang. DARTS: Differentiable architecture search. In International Conference on Learning Representations (ICLR), 2019.
Nils M Kriege, Pierre-Louis Giscard, and Richard Wilson. On valid optimal assignment kernels and applications to graph classification. In Advances Neural Information Processing Systems, pages 1623-1631, 2016.
Ahsan Alvi, Binxin Ru, Jan-Peter Calliess, Stephen Roberts, and Michael Osbome. Asynchronous batch bayesian optimisation with improved local penalisation. International Conference on Machine Learning, pages 253 262, 2019.
James Bergstra and Yoshua Bengio. Random search for hyper-parameter optimization. Journal of machine learning research, 13(Feb):281-305, 2012.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process opti- mization in the bandit setting: No regret and experimental design. arXiv preprint arXiv:0912.399. 2009.
13

---

Published as a conference paper at ICLR 2021
A
ALGORITHMS
Description of the WL. kernel Complementary to Fig- 1 in the main tex, in this section we include
a formal, algorithmic description of the WI. procedure Algorithm 2
Algorithm 2 Weisfeiler-Lehman subtree kernel computation between two graphs Shervashidze et al.
(0011)
Input: Graphs {G,, G23. Maximum WL iterations !!
2: Output: The kemel function value between the graphs k
3: Initialise the feature vectors (o(G,) &f ((G2)) with the respective counts of original node labels
i.e. the h = 0 WL features. (E.g. o'(G) is the count of i-th node label of graph G1)
4: for h 1, ................................ H do
5: Assign multiset-label (w) to each node v in G consisting of the multiset (4~-1/m E (v), where 1 is the node label of node of the h - 1-th WL. iteration; N(v) are the neighbour nodes of node
6: Sort each elements in M, (v) in ascending order and concatenate them into string (n
7:
Add - (v) as prefix to (v).
8:
Compress each string 8% (v) using hash function f so that ((sx())) = f(s((w)) iff (n( =
Sp, (w) for two nodes {u, w).
9: Set (v( == (s ( (v))Ve E G.
10: Concatenate the (bG1), (G2) with the respective counts of the new labels
11: end for
12: Compute inner product between the feature vectors in RKHS k (b(G1),
B DETAILED REASONS FOR USING THE WL KERNEL
We argue that WL kernel a desirable choice for the NAS application for the following reasons.
1. WL kernel is able to compare labeled and directed graphs of different sizes. As discussed architectures in almost all popular NAS search spaces (Ying et al. al./22199 Dong and Yang. 2020; Zoph et al.) 2018b Xie et al. 2019) can be represented directed graphs with node/edge attributes. Thus, WL kernel can be directly applied on them. On the other hand, many graph kernels incompatible with directed graphs (Kondor and Pan, 2016; de Lara and Pineau] (2088). Converting architectures into undirected graphs can result in loss of valuable information such as the direction of data flow in the architecture (we show this in Section 5).
in Section [
either do not handle node labels (Shervashidze al. 2009),
2. WL kernel is expressive yet highly interpretable. WL kernel is able capture substructures that go from local to global scale with increasing h values. Such multi-scale comparison is similar to that enabled by a Multiscale Laplacian Kernel (Kondor and Pan 2016) and desirable for architecture comparison. This is in contrast to graph kernels such as Kashima et al. (2003): [Shervashizee et al. (2009), which only focus on local substructures, or those based on graph spectra Lara and Pineau (2018), which only look at global connectivities. Furthermore, the WI. kernel is derived directly from the Weisfeiler-Lehme as powerful GNN in distinguishing non-isomorphic graphs (Morris al. [2019) [uu et al. 2018). However, the higher-order graph features extracted by GNNs are hard to interpret by humans. On the other hand, the subtree features learnt by WL kernel (e.g. the h 0 and h 1 features in Figure ??) are easily interpretable.
graph isomorphism test (Weisfeiler and Lchman 1968), which is shown to be
WL kernel is relatively efficient and scalable. Other expressive graph kernels are often pro- hibitive to compute: for example, defining {n, m) to be the number of nodes and edges in a graph, random walk (Gärtner al. 2003). shortest path (Borgwardt and Kriegel| 2005) and graphlet kernels
(Shervashidze et al. 2009) incur a complexity of O(n²). O(n") and On (n respectively where A is the maximum graphlet size. Another approach based on computing the architecture edit-distance (Jin et al. 2019) is also expensive: its exact solution is NP-complete (Zeng et al. 2009) and is provably difficult to approximate (Lin 1994). On the other hand, the WL kernel only entails a complexity of O(H)) (White et al. 2019), which without truncation scales exponentially with
'Consequently, naively computing the Gram matrix consisting of pairwise kernel between all pairs in N graphs is of O(N2 Hm), but this he further improved to O(N 22 Hn). See Morris al. (2019)
14

---

Published as a conference paper at ICLR 2021
C COMBINING DIFFERENT KERNELS
In general, the sum or product of valid kernels gives another valid kernel, as such, combining different kernels to yield a better-performing kernel is commonly used in GP and Multiple Kernel Learning (MKL) literature [Rasmussen] 2003] Gönen and Alpaydin 2011). In this section, we conduct a preliminary discussion on its usefulness to GPWL. As singular example, we consider the additive kernel that is linear combination of the WL kernel and the MLP kernel:
kadd (G1; G2) alww G2) (KM.L(Gi, G2) s.t. 3 1, a, 82
(C.1)
where 8 are the kernel weights. We choose WL. and MLP because we expect them to extract diverse information: whereas WL processes the graph node information directly, MLP consider the spectrum of the graph Laplacian matrix, which often reflect the global properties such as the topology and the graph connectivity. We expect the more diverse features captured by the constituent kernels will lead to more effective additive kernel. While it is possible to determine the weights in more principled way such as jointly optimising them in the GP mor-innii likelihood, in this example we simply set = 0.7 and 3 = 0.3. We then perform regression on
101 and Flower102 datasets following the setup as in Sec. [ We repeat each experiment 20 times and report the mean and standard deviation in Table 2 and show the uncertainty estimate of additive kernel in Fig. 6. In both search spaces the additive kernel outperforms the constituent kernels but the gain over the WL kernel is marginal. Interestingly, while MLP performs poorly on its own, it can be seen that the complementary spectral information extracted by it can be helpful when used alongside our WL kernel. Generally, we hypothesise that as the search space increases in complexity (e.g.. larger graphs, more edge connections permitted, etc), we expect that the benefits from combining different kernels to increase and we defer more comprehensive discussion on this future work. As starting point, one concrete proposal would be applying a MKL method such as ALIGNF (Cortes et al. 2012 our context directly.
Table 2: Regression performance (i.t.o rank correlation) of additive kernels
Kernel
N101
Flower- 102
WL + MLP
0.871
0.81310.018
WL
0.862:20.03 0.458
0.80410.0088
MLP!
0.492:10.12
Taken directly from Table
-1.0
Vallesstion Prodiction
-1.0
-15
-2.
-2.
-25
25
-3.0
-30
-2
-1
-3
-2
Validition Target
Validation Target
(a) N101
(b) Flower102
Figure 6: Predictive vs ground-truth validation error of GPWL with additive kernel on N101 and Flower- 102 in log-log scale. Error bar denotes +1 SD from the GP posterior predictive distribution.
D FURTHER DETAILS ON INTERPRETABILITY
D.1 SELECTION PROCEDURE FOR MOTIF DISCOVERY
NAS-Bench datasets In the closed-domain NAS-Bench datasets (including both NAS- bench-101 and NAS-Bench-2 we randomly sample 300 architectures from their respective search space, fit the GPWL surrogate, and compute the derivatives of all the features that appeared in the training
15

---

on the Published as a conference paper at ICLR 2021
Best mobils
Worst mobils
po0d
20-
condiid
Vall Auz
(a) Best and worst motifs identified on the N101 dataset (left), and the validation accuracy distributions in the validation architectures (right).
Best mobils
Workt mobils
clfe110 calld
difa/100
ImageNelle-1Z
good
good
25
Bec
bed
crea 203
paod 141
0.5
Vol
(b) Best and worst motif's identified on CIFAR-100 task of N201 dataset (left). and validation accuracy distributions transferred on CIFAR-10, CIFAR-I00 and ImageNet (right 3).
Bedt mabis
Worst mobile
offr10 valic
cfar100
ImageNett6 120
5o0d
good
15-
bad
bod
20
30
coea pool
Vell Aer
Val Acc
(c) Best and worst motif's identified on the ImageNet task N201 dataset (left), and the validation accuracy distributions transferred on CIFAR-10, CIFAR-100 and ImageNet (right 3).
Figure 7: Motif discovery on N101 and CIFAR-100 and ImageNet tasks of N201. Note that since N101 is trained on CIFAR-10 only, it is not possible to show the results transferred on another task. All symbols and legends have the same meaning as in Fig. 2 in the main text.
set. As a regularity constraint, we then filter the motifs to only retain those that appear for more than 10 times to ensure the estimates of the derivatives by the GPWL surrogate are accurate enough and are not swayed by noises/outliers. We finally rank the features by the numerical values of the derivatives, and present the top and bottom quantiles of the features as "best motifs" and "worst motifs" respectively in Fig. 2 in the main text and Fig. 7in in Sec. D22
DARTS Search Space In the open-domain search space, it is impossible to sample efficiently since each sample drawn requires us evaluate the architecture in full, which is computationally prohibitive. Instead, we simply reuse the GPWL surrogate trained in one run of open-domain experiments described in Sec. 5 which contains 120 architecture Sechtecturer-validattio validation accuracy pair evaluated over 3 GPU days. Due to the smaller number of available samples, here we only require each feature to appear at least twice as a prerequisite, and we sclect the top and bottom 15% of the features to be presented in the graphs. All other treatments are identical to the descriptions above.
D.2 MOTIF DISCOVERY ON N101 AND OTHER TASKS OF N201
Supplementary Fig. in main text, here we outline the motifs discovered by GPWL also on the N101 search space and on the other tasks (CIFAR-100, ImageNet16) of N201 in Fig, 7 We follow the identical setup as described in both the main text and Sec. D.1 In all cases, the motifs are highly effective in separating the architecture pool, and it is also noteworthy that the motifs found in the other N201 tasks are highly consistent with those shown in Fig. 2 in the main text with only minor
'The architecture here refers to the small architecture evaluated during search stage, instead of the final architecture during evaluation stage. Refer Sec. andd App.
16

---

Published as a conference paper at ICLR 2021
(a) Top motifs
searched CIFAR- (b) Optimal (C-10) (c) Optimal (C-100) (d) Optimal (ImageNet)
10 only
Figure 8: Computed motifs and ground-truth optimal cells for all 3 tasks of N201. Note that optimal CIFAR-10 cell contains motifs I and 3, optimal CIFAR-100 cell contains motif and optimal ImageNet16 cell contains motif 2.
0.
Valcatto Prctetoon
-3.5
0.2
-3.50
-2.
5.75
-2.1
2.3
-1.00
-30
-1.5
-10
-1.
Valcetion Target
Valdetion Target
Valcatoon Target
Yalldadon
16 Mutttonn Target
(a) N101
(b) N201(C-10)
(c) N201(C-100) (d) (201(Im)))Net)
(c) F00wer
Figure 9: Predicted vs ground-truth validation error of GPWL in various NAS-Bench tasks in log-log scale. Error bar denotes 1 SD from the GP posterior predictive distribution.
differences, further supporting claim that the GPWL is capable of identifying transferable features without unduly overfitting to a particular task.
To give further concrete evidence the working and advantage of the proposed method in N201, in Fig 8 we show the top-4 motifs in terms of the derivatives computed from one experiment on CIFAR-10 only, according to Sec and the ground-truth best architectures in each of the three tasks included. In this case, while the optimal cells for the different tasks are similar (but not identical) and reflective of high-level transferability of the cells, transferring the optimal cell in one task directly another will be sub-optimal. However, using our method as described in Algorithm by transferring the motifs in Fig(S(a) a)a on CIFAR-100 and ImageNet tasks, we reduce the search space and resultantly search time drastically (as any cell to be evaluated now needs to contain one of the motifs in Fig. ((a)) yet do not preemptively rule out the optimal cell (as all optimal cells contain "good" motifs). As such, our method strikes a balance between performance and efficiency.
E FURTHER REGRESSION RESULTS
E. PREDICTIVE MEAN + STANDARD DEVIATION OF GPWL SURROGATE ON NAS DATASETS
In this section, we show the GPWL predictions on the various NAS datasets when trained with 50 samples each. It can be shown that not only a satisfactory predictive mean produced by GPWL in terms of the rank correlation and the agreement with the ground truth, there is also sound uncertainty estimates, as we can see that most cases the ground truths are within the error bar representing one standard deviation of the GP predictive distributions. For the training of GPWL, we always transform the validation errors (the targets of the regression) into log-scale, normalise the data and transform back at prediction, empirically we find this leads to better uncertainty estimates.
E.2 COMPARISON WITH OTHER GRAPH KERNELS
We further compare the performance of WL kernel against other popular graph kernels such as (fast) Random Walk (RW) (Kashima et al. 2003 Gärtner et al., 2003)). Shortest- Patte (SP) (Borgward! and Kriegel 2005), Multiscale Laplacian (MLP) (Kondor and Pan 2016) kernels when combined
17

---

Published as a conference paper at ICLR 2021
Corr. and -iogimmggrall......... libel hooc)
Histooram of selected GPAL
Com. 2nd legimarghal (kellhood)
Halcooram of sawctec GPAL
0000
0.92
Progartyy
0.35
0.00
11 Urooo 1arm WL conttoro
P. 1TCTAPPTTTT 11 621X.000
11 Plmmsimam WL Berabant
11 W. AeSOO
(a) N101
(b) Flowers102
Figure 10: Spearman correlation on train/validation sets and the negative log-marginal likelihood of GP against H (the maximum WL iteration) and the histograms of selected by GPWL over 20 trials on (a) N101 and (b) Flowers102.
with GPs. These competing graph kernels are chosen because they represent distinct graph kernel classes and are suitable for NAS search space with small or no modifications. In each NAS dataset, randomly sample 50 architecture data to train the GP surrogate and another 400 architectures as the validation set to evaluate the rank correlation between the predicted and the ground-truth validation accuracy.
We repeat each trial 20 times, and report the mean and standard error of all the kernel choices on all NAS datasets in T We also include the worst-case complexity of the kernel computation between a pair of graphs the table. The results in this section justify our reasoning in App. B combined with the interpretability benefits we discussed, WL consistently outperforms other kernels across search spaces while retaining modest computational costs. RW often comes a close competitor, but its computational complexity is worse and does not always converge. MLP, which requires us to convert directed graphs to undirected graphs, performs poorly, thereby validating that directional information is highly important.
Table Regression performance (i.t.o Spearman's 's rank correlation) of different graph kernels.
Kernel
Complexity
N101
CIFARIO
CIFAR100
ImageNet16
Flower- 102
WL
((Hm)
0.862=#0.03
0.812=0.06
0.823=0.03
0.796=0.04
0.804=0.018
RW
O
0.801=0.04
0.809=0.04
0.782=0.06
0.795=0.03
0.759++0.04
SP
O
0.80110.05
0.792.10.06
0.76110.06
0.762-0.08
0.694110.08
MLP
O(Lng)
0.458
0.51910.14 0.412=0.15
0.538=0.07
0.49211012
1: L the number neighbours, hyperparameter of MLP kernel.
E.3 VALUE OF H (MAXIMUM NUMBER OF WL ITERATIONS)
As discussed, the Weisfeiler-Lehmee kernel is singly parameterised by H, the maximum number of WL iterations. The expressive power of the kernel generally increases with H, as the kernel is capable of covering increasingly global features, but at the same time we might overfit into the training set, posing a classical problem of pariance-bias trade-off. In this work, by combining WL with GP, we optimise H against the negative log- marginal likelihood of the GP. In this section, on different data-sets we show that this approach satisfactorily balances fata-fitting with model complexity.
To verify, on both N101 and 00 data-sets we described, we train GPWL surrogates on 50 random training samples. On N101, we draw another 400 testing samples and on Flowers 102, we use the rest of the data-set as the validation set. We use the Spearman correlation between prediction and the ground truths of the validation set as the performance metric. We summarise our result in Fig. 10 in both data-sets, we observe a large jump in performance from H = 0 to 1 (measured by the improvements in both validation and training Spearman correlation), and slight dip in validation correlation from = 2 to 3, suggesting an increasing amount of overfitting if we increase further. In both cases, the automatic selection described above succeeded in finding the "sweet spot" of H = or 2, demonstrating the effectiveness of the approach.
F CLOSED-DOMAIN EXPERIMENTAL DETAILS
All experiments were conducted 36-core 2.3GHz Intel Xeon processor with 512 GB RAM.
18

---

Published as a conference paper at ICLR 2021
F.1 DATASETS
We experiment on the following datasets:
NAS-Bench-101 (Ying al. 2019): The search space is an acyclic directed graph with 7 nodes and a maximum of 9 edges. Besides the input node and output node, the remaining 5 operation nodes can choose one of the three possible operations: convl x1-bn-re u and maxpool 3. The dataset contains all 423,624 unique neural architectures in the search space. Each architecture is trained for 108 epochs and evaluated on CIFARIO image data. The evaluation is repeated over 3 random initialisation seeds. We can access the final training/validation/ees accuracy, the number of parameters as well as training time of each architecture from the dataset. The dataset and its API can be downloaded from https://
(env3x3-bn-ree
ceesearch/naasbencce
NAS-Bench-201 (Dong and Yang 2020): The search space is an acyclic directed graph with 4 nodes and edges. Each edge corrssonds to an operation selected from the set of 5 possible options: convi x conv3 x3, avgpool3xX 3x3,, skip-connect and zeroize. This search space is applicable to almost all up-to-date NAS algorithms. Note although the search space of
is more general, it's smaller than that of NAS-Bench-1011 The dataset contains all 15,625 unique neural architectures in the search space. Each architecture trained for 200 epochs and evaluated on 3 image datasets: CIFARIO 10, CIFAR 100, ImageNet 1-20.. The evaluation is repeated over 3 random initialisation seeds. We can access the training accuracy/loss, validation accuracy/loss after every training epoch, the final test accuracy/loss, number of parameters as well as FLOPs from the dataset. The dataset and its API can be downloaded from http::: /itt://///ttuuu.bo thub. com X- -Beh/B 201
Flowers102: We generate this dataset based on the random graph generators proposed in Xic et al. (0199) The search space is an acyclic directed graph with 32 nodes and varying number of edges. All the nodes can take one of the three possible options: input, output, relu-conv3x3-1
Thus, the graph can have multiple inputs and outputs. This search space is very different from those of NAS-Bench-101 and HAS-Bench-201 and is used to test the scalability of our surrogate model for a large-scale search space (i.L. number of numbers in the graph). The wtaes//wwiinn/oonettiiii in the graph is created by one of the three classic random graph models: Erdos-Reny (ER). Barabasi-Albert (BA) and Watt-Strogatz (WS). Different random graph models result in graphs of different topological structures and connectivity patterns and are defined by one or two hyperparameters. We investigate total of 69 different sets of hyperparameters: 8 values for the hyperparameter of ER model, 6 values for the hyperparameter of BA model and 55 different value combinations for the two hyperparameters of WS model. For each hyperparameter set, we generate 8 different architectures using the random graph model and train each architecture for 250 epochs before evaluating on Flowers 102 dataset. The training set-ups follow Liu et al. 2019). This results in our dataset of 552 randomly wired neural architectures.
F.2 EXPERIMENTAL SETUP
NAS-BOWL We use batch size B = (i.c., at each BO iteration, architectures yielding top 5 acquisition function values are selected to be evaluated in parallel). When mutation algorithm described in Sec. 3.2 is used, we use a pool size of 200, and half of which generated from mutating the top-10 T0 best performing architectures already queried and the other half is generated from random sampling to encourage more explorations in NAS-Bench-101 In NAS-Bench-201, accounting for the much smaller search space and consequently the lesser need to exploration, we simply generate all architectures from mutation. For experiments with random acquisition, we also use P = 200 throughout, and we also study the effect of varying P later in this section. We use WL with optimal assignment the feature vectors of two graphs G1 and G2 (GG)) and oi (b(G2) respectively, the OA inner product in the WI. case is given by the histogram intersection (Gb()), (G2)) = Σ; min (G1), (G2). where x²(.) (-) is the j-th element of the vector. On 20S- which features a much smaller search space which we find a simple dot product of the feature vectors df (, (CTT)T(((C ((G2) to perform empirically better. We always use 10 random samples to initialise NAS-BOWL.
(OA) (Kriege et al., 2016) for all datasets apart from NAS- Bench-201. Denoting
19

---

Published as a conference paper at ICLR 2021
On 101 dataset, we always apply pruning (which is available in the NAS-Bench- 101 API) to remove the invalid nodes and edges from the graphs. On architectures are defined over DARTS-like, edge-labelled search space, we first convert the edge- labelled graphs to node-labelled graphs as a pre-processing step. It is worth noting that it is possible to use WI kernel defined over edge-labelled graphs directly (e.g the WL.-edge kernel proposed by Shervashidze et al. (201T)) although in this paper we find the WL kernels over node-labelled graphs to perform empirically better.
dataset, since the
On the transfer learning setup of N201, we first run a standard optimisation task on the CIFAR- 10 task (we term this the base tusk) but we allow for up to an expanded budget of 250 architecture evaluations to build up the confidence of GPWI. derivative estimates. We then extract the "good motifs" identified by GPWL (i.c. those features with derivatives in the top quantile). For the subsequent CIFAR- 100/ImageNet16 optimisations (we term this the transferred tasks). On the transferred tasks, with everything else unmodified from standard runs (e.g. budget, pool size, batch size, acquisition function choice, etc), we additionally enforce the pruning rule such that only candidates in the pool with at least 1 match to the previously identified "good motifs" are allowed for evaluations and the rest are removed. The key difference is that under standard runs, the pool of size B is generated once per BO iteration via random sampling/mutation procedure is executed for many times as required until we have a pool of B architectures where each meets the pruning criteria.
algorithm since all candidates are accepted; here, this
We use the code made public by the authors (White et al. 2019) com/naszill a/ bananas), and use the default settings contained in the code with the exception of the number of architectures queried at each BO iteration (i.e. BO batch size): the default is 10. but conform to our test settings we use instead. While we do not change the default pool size of P = 200 at each BO iteration, instead of filling the pool entirely from mutation of the best architectures, we only mutate 100 architectures from top-10 10 best architectures and generate the other 100 randomly to enable a fair comparison with our method. It is worth noting that neither changes led to a significant deterioration the performance of BANANAS: under the deterministic validation error setup, the results we report are largely consistent with the results reported in White et al, (2019); under the stochastic validation eπror setup, our BANANAS results actually slightly outperform results in the original paper. It is finally worth noting that the public implementation of BANANAS on NAS-Bench-200 was not released by the authors.
BANANAS
(nttps://githug
GCNBO for NAS We implemented the GNN surrogate in See. 5.1 by ourselves following the description in the most recent work (Shi et al. 2019), which uses graph convolution neural network in combination with a Bayesian linear regression layer to predict architecture performance in its BO-based NAS To ensure fair comparison with our NAS-BOWI, we then define normal Expected Improvement (EI) acquisition function based on the predictive distribution by the GNN surrogate to obtain another BO-based NAS baseline in Sec. 5.2, GCNBO. Similar all the other baselines including our NASBOWLI and BANANASI, we use random sampling to generate candidate architectures for acquisition function optimisation. However, different from NAS-BOWL and BANANAS, GCNBO uses batch size B = 1, i.e. at each BO iteration, NAS-BOWL and BANANAS select new architectures evaluate next but GCNBO select new architecture to evaluate next. This setup should favour GCNBO if we measure the optimisation performance against the number of architecture evaluations which is the metric used in Figs. and because at each BO iteration, GCNBO selects the next architecture G2 based on the most up-to-date information ar (G whereas BOS-BOWW and BANANAS only select one architecture Gr,1 in such fully informed way but select the other four architectures {Gr,) with outdated information. Specifically, in the sequential case (B- = 1), Gr,2 is selected only after we have evaluated Gr,1, Ga is selected by maximising ( (Gr,1, Vt. 1t): the same procedure applies for Gt,3, Gr,4 and G1,5- However, in the batch case (B- 5) where Gt, for 2 < 5 need to be selected before G is evaluated, (Gr, 18 are all decided based on ar (G) like Gt,1. For more detailed discussion
on sequential (B- 1) and batch (B> > 1) BO, the readers are referred to Alvi et al. (2019)
Other Baselines For all the other baselines: random search (Bergstra and Bengio 2012). TPE (Bergstra et al. 2011). Reinforcement Learning Zooph and Le 2016), BO with SMAC (Htttr
Shi al. 2019) did not publicly release their code.
20

---

Published as a conference paper at ICLR 2021
64
565
9.0
33.
RC
28.5
6.0
23.0
28.5
25.0
4.0
545
56
27.5
55.
25.5
53.5
20 75
100
227
20.0
22
100
125
13.0
300
125
Normerro dechiaatioss tassated
Hamber dethiiemmeee Evalaane
Ho dechirecturee Exaliated
Mamber RectRacturee unttd
(a) N101
(b) N201(C-10)
(c) N201(C-
(d) (ImageNee)))
6.4
22.5
022
0
600
8:50
23.5
53.5
23.0
9.2
55.0
5.00
2:75
27.5
8.50
52
25.5
50
Norterr of Acciiolaano Eealuded
25
100 225
Mumber decriiacttune Comtucted
35
160 125 dechRoctures Evelured
75
25
ArchRecttins
25
1EC. 125
(c) N101
(f) (201(C-10)
(g) N201(C-100)
(h) N201 (Imageen))
NASRCWLM
BANANASr
BANANASm
regularized_ eevolutinn
tpa
smacbo
NASBOWLr
NASBOWLm(TL)
genba
rendom_ search
Figure 11: Median validation error on NAS-Bench datasets with deterministic (top row) and noisy (bottom row) observations from 20 trials. Shades denote 1 standard error.
et al. 2011), regularised evolution (Real et al. 2019), we follow the implementation available //ttts::/ggttii thub. com/ aut om /naa catrss_eehhhaaaaa rks for NAS MAS--Bnnh--10 (Ying et al.) 2211)). We modify them to be applicable on
(Dong and Yang 2020). Note that like GCNBO,
all these methods are sequential B = 1, and thus should enjoy the same advantage mentioned above when measured against the number of architectures evaluated.
F.3 ADDITIONAL NAS-BENCH BENCH RESULTS
Validation Errors Against Number of Evaluations We show the validation errors against number of evaluations using both stochastic and deterministic validation errors of NAS-Bench datasets in Fig. It is worth noting that regardless of whether the validation errors are stochastic or not, the test errors are always averaged to deterministic values for fair comparison. It is obvious that NAS-BOWL still outperforms the other methods under this metric in achieving lower test error or enjoying faster convergence, or having both under most cireumstances. This corresponds well with the results on the test error in Fig. 5 and double-confirms the superior performance of our proposed NAS-BOWL in searching optimal architectures.
Effect of Varying Pool Size As discussed in the main text, NAS-BOWL introduces no inherent hyperparameters that require manual tuning as it relies on non-parametric surrogate. Nonetheless, besides the surrogate, the choice on how to generate the candidate architectures requires us to specify number of parameters such as the pool size (P, the number of candidate architectures to generate at each BO iteration) and batch size B. In our main experiments, we have set P = 200 and = throughout; in this section, we consider the effect of varying P to investigate whether the performance of NAS- BOWL is sensitive to this parameter.
We keep B- = but adjust P E (50, 100, 200, 400), and keep all other settings to be consistent with the other experiments using the deterministic validation errors on NAS-Bench- 101 (N101) (i.c. averaging the validation error seeds to remove stochasticity), and we report our results in Fig. 12 where the median result is computed from 20 experiment repeats. It can be shown that while the convergence speed varies slightly between the different P choices, for all choices of P apart from 50 which performs slightly worse, NAS-BOWL converges similar validation and test errors at the end of 150 architecture evaluations - this suggests that the performance of NAS-BOWL is rather robust to the value of P and that our recommendation of P 200 does perform well both in terms of both the final solution returned and the convergence speed.
A Ablation Studies In this section we perform ablation studies on the both N101 and N201 (with deterministic validation errors). We repeat each experiment 20 times, and
performance on
21

---

This Published as a conference paper at ICLR 2021
6.0
6.6
R00 Teed Eent
6.4
3.8
Pw400
P.400
3.7
5.6
-4
5.8
Kumber of Archttecturss Doatusted
Nimber Archeteturess Evaluated
(a) Validation Error
(b) Test Error
Figure 12: Effect of varying P on NAS-BOWL in N101.
we present the median and standard error in terms of both validation and test performances in Fig. (N101 (a)(b) and N201 (c)d)). We now explain each legend as follow:
1. mutate: Full NAS-BOWL. with the mutation described in Sec. 3.2 (identical to NASBOWLm in
Figs. 11 and :):
rand: NAS-BOWL with random candidate generation. This is identical to NASBOWL: Figs.
11 [aand 5
3. UCB: NAS-BOWL with random candidate generation, but with the acquisition function changed from Expected Improvement (EI) to Upper Confidence Bound (UCB))Srinivas |Srnivas et al. (2009) a'acq = J 3, where μu, are the predictive mean and standard deviation of the GPWL surrogate, respectively and fn, a coefficient that changes as a function of n, the number of BO iterations.
We select 3 at initialisation (3y) to 3, but decay it according to 8n = /uy 2 log(2(n + 1)) as suggested by Srinivas et al. 2009). where n is the number of BO iterations.
VH: NAS-BOWL with random candidate generation, but instead of leaving the value of h (number of WL iterations) to be automatically determined by the optimisation of the GP log marginal likelihood, we h the counts of each type of original node operation features (e.g. conv3x3-bn-rell essentially reduces the WL kernel to a Vertex Histogram (VH) kernel.
i.e. no WL iteration takes place and the only features we use are
0.0
6.5
5.9
23.5
23.5
3.8
UC3
0.4
23.0
20.0
9.7
Aveeage Bea
20.5
5.6
5.5
27.0
27.0
5.8
25.5
25.5
Arthitectumee
200
of Arthttcctume
200
Mumber Architutu its Evelubol
Number Archt es Evolucted
(a) Val. Error N101
(b) Test Error N101
(c) Val. Error on N201
(d) Test Error on N201
Figure 13: Ablation studies of NAS-BOWL
We find that topological information and using an appropriate are highly crucial: in both N101 and N201, VH significantly underperforms the other variants, although the extent of underperformance is smaller in N201 likely due to its smaller search space. This suggests that how the nodes are connected, which are extracted as higher-order WL features, are very important, and the multi-scale feature extraction in the WL kernel is crucial to the success of NAS-BOWI BOWL. On the other hand, the choice of the acquisition function seems not matter much as there little difference between UCB and runs in both N101 and N201. Finally, using mutation algorithm leads to a significant improvement in the performance of NAS-BOWL, as we have already seen in the main text.
G OPEN-DOMAIN EXPERIMENTAL DETAILS
All experiments were conducted on a machine with an Intel Xeon- W processor with 64 GB RAM and single NVIDIA GeForce RTX 2080 Ti GPU with 11 GB VRAM.
22

---

Published as a conference paper at ICLR 2021
G.1 SEARCH SPACE
in the popular NAS- Net search space, and we limit the maximum number of operation nodes to be 4 (in addition to 2 input nodes and 1 imput node in each cell), and the possible node operations are
Our search space is identical that of DARTS (Luu et al. 20)
and 5 x 5 separable convolutions (sep-conv-3x3 and sep- sep-come conv- x), 3 x 3 and 5 x 5 dilated convolutions (dil feil-conv-3x3 and dil -il-conv-5x5), 3 x max pooling and average pooling (max-pool 1 x33 and a avg-pool- 1033poo03333) identity skip connection tskip-connen
and zeroise (none).To enable the application of the GPWL surrogate without modification, we use the ENAS- style node-attributed DAG representation of the cells (this representation can be easily converted to the DARTS- edge-attributed DAG without any loss of information). We show the best cell identified by NAS- HAS-BOWL in the DARTS search space in both edge- and node-attributed DAG representations in Fig.
14 as an example.
c [k:2)
3xd
EEAL meu
appc
KILEIR 363
cop.conv.t 313
up cone
up aar
conv Ixd
[
direer
[_
coppecomect
sop_cowv_3d
(a) attributti DAG
(b) Node DAG
Equivalent representations of the best cell identified by in the DARTS search space. Our method uses the node-attributed version during search, and this cell is used for both the normal and reduction cells.
Figure 14:
G.2 EXPERIMENTAL SETUP
We mostly follow the setup and the code base /https://github. DARTS (Liu et al., 2018a), and detail the setup in full below:
http:thbb..comuaaat////rrrrre from
Architecture Search During the architecture search, we use half of the CIFAR-10 training data and leave the other half as the validation set. We use stack the search cell 8 times to produced small network, and use batch size of 64 and initial number of channels of 16. As discussed, we only search one cell, and use this for both normal and reduction cells (in DARTS the two cells are searched separately). We use SGD optimiser with momentum of 0.9, weight decay of x 10-4 and an initial learning rate of 0.025 which is cosine annealed to zero over 50 epochs. As known by previous works (Liu et al.) 20). the validation performance on CIFAR- is very volatile, and to ameliorate this we feed the average of the validation accuracy of the final 5 epochs the observed accuracy to the GPWL surrogate. We use the identical setup for GPWL surrogate as the NAS- MAS-Bench experiments and we the standard mutation algorithm described to generate the candidates every BO iteration.
Architecture Evaluation After the search budget (set to 150 architectures) is exhausted, we evaluate the neural network stacked from the best architecture found, based on the validation accuracy during the search stage. During evaluation, we construct a larger network of 20 cells and is trained for 600 epochs with batch size 96 and initial number of channels of 36. Additional enhancements that are almost universally used in previous works, such as path dropout of probability 0.2, cutout, and auxiliary towers with weight 0.4 are also applied in this stage (these techniques are all identical to those used in Liu et al. (a)). Any other enhancements not used in DARTS such as mixup, Autmmugment and test-time data augmentation are not applied. The optimiser setting is identical to that during architecture search, with the exception that the cosine annealing is over the full 600 epochs instead of 50 during search. During this stage, set for training. and report best accuracy encountered during evaluation on the validation set in Table i We finally train the final architecture for 4 random repeats CIFAR-10 dataset.
the entire CIFAR-10 10 training
23


Reviews:
[{"review_id": "qIPld8SjM3", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a new neural architecture search algorithm combining Bayesian optimization with the expressive and popular Weisfeiler-Lehman (WL) Graph Kernel. One advantage of using WL is the interpretable results that stem from the nature of how the kernel is computed, namely a propagation scheme through the graph. Combined the derivative of Eq. 3.2, one can extract subgraphs that are directly responsible for increased performance. In a variety of experiments, the authors show not only increased performance of detected architectures but also find subgraphs that are found by other algorithms as well. \n\nEven though my expertise does not lie in the field of NAS, I find this work quite appealing. It is an innovative application for graph kernels, which suffer from scalability which in this setting is less of a problem. I find the aspects of novelty, interpretability, and quantitative results convincing enough to recommend acceptance. Furthermore, the work is largely well structured and written, and the figures are legible and relevant. W.r.t whether the comparison to other SOTA NAS algorithms is of good quality and fair, I think the input from reviewers with a NAS background would be valuable.  \n\nMinor comments:\n•\tBy itself a graph kernel is a similarity measure and does not perform any subgraph selection. It happens that due to the WL propagation scheme, the WL graph kernel consists of interpretable features while computing the similarity. I would clarify this a little more in 3.1. Since this is, in my opinion, the most innovative part of the manuscript, I would even consider bringing Figure 5 from the appendix into the main paper (maybe in a condensed form). To get some space for this you could shorten some descriptions of experiment parameters and comparison methods to the appendix. Also, I think Figure 5 is not 100% complete. To make it even easier to parse, I would put boxes around the subgraphs in the $h=1 features$ box and annotate them with their respective index. E.g. the upper graph with 4 outgoing edges should be annotated with 5 and so on. This also makes it a little clearer how WL leads to larger networks in each round of propagation.\n\n•\tI would be interested in some statistics about the chosen h parameter (do you mostly find small subnetworks to lead to high performance?) and how it is being optimized (due to its discrete nature). \n\n•\tStructure: I would move 3.2 into a subsection under the experiments. In general, the manuscript reads a little squished as you have a lot of references to the appendix. It is not easy to remedy this as you don’t want the work you did go unnoticed but maybe you can leave some references out and submit a longer version of this work to a journal where you don’t suffer the space constraints of a conference paper.\n\n•\tFrom Table 1 it seems like the Avg. error gains are not significant as they overlap (in terms of standard deviations) for example with the DARTS results which is not bad as you still save one day of training. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "o0sW7RES5W3", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "---------- After feedback ---------- \n\nFirst of all, I greatly appreciate the authors patient response to me during the feedback period. The discussion was really fruitful. Unfortunately, I still have a concern about interpretability of the proposed method, which is a central topic in the paper.\n\n> First, we find it a bit strange when the reviewer says “it is difficult to find importance/meaning of comparing motifs is unclear”, we clearly show our method does find importance in NAS-Bench-101, all 3 tasks of NAS-Bench-201 and DARTS search space (Fig 1 and 7) -- if we can't find importance/distinguish different motifs, none of the results we've shown would've been possible. \n\nEven when a method works empirically, if a rationale behind the procedure is not clarified, a paper would not be scientifically convincing. Thus, I still do not think my claim is strange.\n\n> Second, the example the reviewer gives is not a case when averaged gradient fails. On the contrary, it is exactly an example of when averaged gradient works. A motif with high and diverse local gradient magnitudes but average to near-0 is not important for the purpose of interpretability, as it doesn’t consistently explain the network performance by itself (just based on such motifs, one cannot conclusively deduce the impact on performance of an arbitrary, unseen architecture in general) ...\n\nIn the last response, the authors explained the interpretability issue through combination of motifs, but it did not resolve my concern. To simplify the discussion, consider a bit extreme case in which only one motif is employed in a network simultaneously, and assume WL parameter h = 0. Let g(c) = d \\mu / d \\phi^j |_\\phi^j=c. Then, consider a hypothetical case as follows:\n\nmotif a) g(1) = 10, g(2) = 10 ... g(10) = 10, g(11) = -10, .... g(20) = -10 : AG = 0\n\nmotif b) g(1) = 1, g(2) = 1 ... g(10) = 1, g(11) = 1, .... g(20) = 1 : AG = 20\n\nIn this example, b) has a larger AG, but a) can have larger importance in practice, and now, since only one kind of motif is employed simultaneously, the explanation of the authors cannot be applied. For the exploration purpose, I do not find any rationale to consider that b) is more important than a). I know that these are extreme examples and may depend on an application scenario, but my point is that these examples reveal difficulty of interpretation of AG. The authors introduce AG at Section3.2 as an importance measure without carefully discussing how it can be interpreted in the context of the WL based exploration (just referring other papers without discussing details in a sense of the above averaging). The explanation through marginalization also does not get rid of this question. Since the interpretability is a main theme of the paper, providing a better interpretability of AG would be desired.\n\n---------- Before feedback ---------- \n\nThe paper proposes to use Weisfeiler-Lehman (WL) kernels for neural architecture search. WL kernel can incorporate the topological structure of the network, and the authors combines WL kernels with Bayesian optimization (BO) to optimize the validation performance of the network. Further, the authors also claim that WL kernels provide a useful interpretation about good / bad network structures by using the derivative of Gaussian process (GP), which can also be used for 'pruning' architectures. The performance is shown for several benchmark datasets. \n\nOverall, the idea would be reasonable, and the approach would be useful. However, I'd have to say that the technical novelty and depth would be somewhat weak because the standard WL kernel is directly used without any significant modification, and a gradient-based importance evaluation is also a known technique (and its interpretation in this context is a bit difficult). Further, in my understanding, the paper should have provided more general discussions, not only to show data-specific observations. Detailed comments are as follows.\n\nThe proposal of the paper is not fully clear for me because the strategies are described for each one of datasets, separately. I couldn't find general procedures for the architecture search, from the main text of the paper. In practice, of-course, tuning on each dataset would be required, but showing specific tunings for well-known benchmark datasets is not attractive. A strategy applicable to wide range of tasks would be required for a methodology paper.\n\nInterpretation of the gradient-based motif identification is difficult for me. Even when a motif has a large positive or negative gradient value, it only implies 'local' importance around the given architecture. To derive general insight, more careful treatment would be required. The authors provide the motif discovery procedure in D.1, but it should be shown in main text because interpretability is one of main theme of this paper. In Section D.1, the authors described an approach taking average of all possible values, but the average is also difficult to interpret importance because it compresses the entire space, and as the author admitted, the computation would be often intractable in practical settings.\n\nAlthough the authors claim that good/bad motif identification is useful for 'pruning', no detailed general pruning procedure is shown in the main text. Providing a general algorithm would be required. What does 'prune' mean in this context? If a motif is regarded as 'bad' once, it is discarded forever, or can revive somewhere? As I mentioned above, gradient information is only local information. Even when a motif is 'bad', simply discarding it completely would be risky. Even when the 'average' gradient is used, the problem would not be mitigated, because even if the average gradient suggests a motif is useless, it may help to improve accuracy locally. For me, the rationale behind the exploration strategy with the pruning in the paper is quite unclear. \n\nThe authors claim that the identified motif is trasferable. However, evidence of this claim is not fully clear. It seems empirical suggestions only from a few (similar) datasets. When is transferring effective, how do you know it holds when, and can it harm in some case? I think that a general discussion is missing in the paper.\n\nAnother difficulty of the gradient-based importance evaluation is that the lack of uncertainty evaluation. The gradient (3.2) is the expected value of the predictive distribution of GP. Therefore, the variance is not considered. For example, if GP does not have any observations, the expected gradient would be 0 (when prior is f(x) = 0 with the unit variance for any x, which is a standard setting), but variance of gradient would be large, meaning that a motif is still has a potential to become important. Again, discarding a motif by the expected gradient without considering uncertainty is seemingly risky, though the paper lacks this kind of discussion on uncertainty, though the uncertainty evaluation is a central issue on in the context of BO.", "extra_scores": {}, "extra_text": {}}, {"review_id": "kFybPZZR_iy", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 9, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n========\nThis work proposed a BO based NAS method using Weisfeiler-Lehman kernel. The idea is novel and natural considering the neural network architectures as acyclic directed graphs. I am a bit surprised to see no one tried it before in the NAS field and it is great to know that using WL kernel leads to competitive NAS performance comparing to other NAS methods and at the same time improves interpretability. \n\nPros\n====\n* The proposed idea is novel and natural, given the graph natures of network architecture.\n* The notes on the interpretability is very interesting and differ the work from other methods.\n* Extensive empirical studies and ablation studies.\n* Extensive detail for reproducibility.\n* The paper is very well written.\n\nMinor comments\n===============\nI think this is a really nice work and I only have some minor comments:\n\n* There is another line of work using BO for NAS: Ru, Binxin, Pedro Esperanca, and Fabio Carlucci. \"Neural Architecture Generator Optimization.\" arXiv preprint arXiv:2004.01395 (2020). Would be nice to know how does the proposed method compared to it.\n\n* The appendix C mentioned about using MKL to combine WL and MLP kernels. But in the end the author used 0.7 and 0.3 as the weights for them. I am wondering whether some simple MKL algorithm such as ALIGNF  can improve the performance here. You can find more detail in this paper: Cortes C, Mohri M, Rostamizadeh A. Algorithms for learning kernels based on centered alignment[J]. The Journal of Machine Learning Research, 2012, 13(1): 795-828.\n\nReason for score\n==============\nI liked this work a lot, it bridged NAS and BO through the usage of graph kernels (WL kernel). As a result, NAS becomes more sample efficient, which is empirically verified by extensive study in this work. The author did a very good job on the empirical evaluations, they are thorough, solid and contains many ablation studies to understand their methods.\n\nPost rebuttal comments\n=========================\nI thank the authors for their responses. I encourage the authors to continue the line of work on replacing the random sampling of NAGO. Given NAS-BOWL surrogate, one can do Thompson Sampling instead of random sampling. On the MKL side, the same weights for all the kernels might be the cause of worse performance. I would also encourage the authors to verify that. Nevertheless, those are minor comments and I still think this is an important work to bridge BO and NAS. I will keep my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "0XIFsKAFG_L", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "# Summary of the paper\n\nThe paper presents a new Bayesian optimization strategy based on Weisfeiler-Lehman Kernels for neural architecture search. The proposed method is more sample efficient than other state-of-the-art Bayesian optimization (BO) methods and allows to identify repeating motifs in well performing architectures.\n\n\nOverall, I really enjoyed reading the paper and I am somewhat surprised that nobody has tried this before. The usage of the Weisfeiler-Lehman kernel is well motivated and enables users to obtain a better intuition which parts of an architecture lead to a good performance. Also, the proposed BO method outperforms other state-of-the-art BO methods across a range of competitive benchmarks. However a few points need to be clarified, and it would be great if the authors could address them in the rebuttal.\n\n\n# Merits\n\n\n- The paper is clearly written and the approach is well motivated\n\n- The proposed method achieves  strong results compared to other Bayesian optimization strategies based on Gaussian process surrogate models. Also, the paper presents a thorough empirical evaluation to other state-of-the-art BO method on well established benchmarks\n\n- As far as I know, this is the first Bayesian optimization for NAS that provides interpretable features to explain which motifs of neural networks architectures work well.\n\n\n\n# Concerns\n\n- Looking at Figure 12 in the appendix, it seems that the proposed method GPWL gets its main boost from the mutation strategy used  to  optimize the acquisition function. This makes me wonder whether the model is actually better than, for example BANANAS, or whether the gain in performance is mostly due to the mutation strategy? How well would BANANAS works with this mutation strategy?\n\n- Could you also add the plots in Figure 3 with the regret on the y-axis (as in the original papers)? This would show how far away from the optimum an optimizer actually is. This is somewhat hidden with ranking plots, where an optimizer might have found an architecture with a negligible performance difference to the global optimum but has a lower rank.\n\n- Why does start GPWL at a higher rank than the other baselines in Figure 3? And why does it stop earlier? Also the dashed red horizontal line is not explained in the caption.\n\n\n# Post Rebuttal:\n\n I thank the authors for taking the time to address my concerns. The paper is well written and the proposed approached is promising. I therefor recommend acceptance.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Most reviewers found the method proposed to be technically sound, well-motivated and particularly interesting due to the interpretability of its results. Indeed, the extraction of interpretable motifs from NAS is a valuable contribution. One of the reviewers was particularly concerned by the lack of guarantees of the proposed method and a perceived failure mode of averaged gradients. We thank both the reviewer and the authors for the detailed discussion on these points. Ultimately, the benefits of the method proposed and the magnitude of the contributions in the paper outweigh these concerns.
Decision: Accept (Poster)