Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 5: Marginally below acceptance threshold
review_content: ---------- After feedback ---------- 

First 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.

> 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. 

Even 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.

> 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) ...

In 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:

motif a) g(1) = 10, g(2) = 10 ... g(10) = 10, g(11) = -10, .... g(20) = -10 : AG = 0

motif b) g(1) = 1, g(2) = 1 ... g(10) = 1, g(11) = 1, .... g(20) = 1 : AG = 20

In 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.

---------- Before feedback ---------- 

The 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. 

Overall, 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.

The 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.

Interpretation 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.

Although 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. 

The 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.

Another 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.
review_title: Reasonable approach, but a bit weak technical impact

final_score: rating: 7: Good paper, accept
review_content: 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. 

Even 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.  

Minor comments:
•	By 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.

•	I 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). 

•	Structure: 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.

•	From 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. 

review_title: Innovative usage of WL Graph Kernel

final_score: rating: 7: Good paper, accept
review_content: # Summary of the paper

The 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.


Overall, 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.


# Merits


- The paper is clearly written and the approach is well motivated

- 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

- 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.



# Concerns

- 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?

- 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.

- 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.


# Post Rebuttal:

 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.
review_title: review

final_score: rating: 9: Top 15% of accepted papers, strong accept
review_content: Summary
========
This 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. 

Pros
====
* The proposed idea is novel and natural, given the graph natures of network architecture.
* The notes on the interpretability is very interesting and differ the work from other methods.
* Extensive empirical studies and ablation studies.
* Extensive detail for reproducibility.
* The paper is very well written.

Minor comments
===============
I think this is a really nice work and I only have some minor comments:

* 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.

* 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.

Reason for score
==============
I 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.

Post rebuttal comments
=========================
I 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.
review_title: Recommendation to strong accept

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)