Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels

Bin Xin Ru, Xingchen Wan, Xiaowen Dong, Michael A. OsborneICLR 2021 · OpenReview

Neural Architecture Search (NAS) has successfully automated the design of high-performing deep learning models, often surpassing human experts. However, most NAS algorithms operate as "black boxes": they might hand you a winning architecture, but they cannot tell you why it works or which specific components are responsible for its success.

Furthermore, many existing NAS methods struggle with the "graph-like" nature of modern search spaces, where models are represented as nodes and edges. Traditional Bayesian Optimization (BO) often relies on simplistic encodings that ignore topological structure. Newer Graph Neural Network (GNN) approaches attempt to solve this but require massive amounts of training data to become accurate—data that is prohibitively expensive to generate in NAS.

To address these challenges, researchers have introduced NAS-BOWL (Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman kernels). This novel approach navigates complex, graph-like search spaces efficiently and offers a rare "peek under the hood" by identifying specific structural motifs that drive performance.

The NAS-BOWL Methodology

NAS-BOWL achieves its efficiency and interpretability through three core components:

  1. GPWL Surrogate: The method uses a Gaussian Process (GP) as a surrogate model to predict the performance of unseen architectures. The "secret sauce" is the Weisfeiler-Lehman (WL) subtree kernel, which measures the similarity between two neural graphs by iteratively aggregating neighborhood information. This allows the model to "see" topological patterns without needing a massive training set.
  2. Interpretable Features: Because the WL kernel explicitly extracts structural features (subtrees or "motifs"), the authors can calculate the analytical derivative of the GP’s prediction with respect to these features. This reveals exactly how much a specific motif contributes to the final accuracy.
  3. Efficient Search: By identifying "good" motifs early, the algorithm can prune the search space, focusing only on candidate architectures that contain promising structural building blocks.
Weisfeiler-Lehman Kernel Feature Extraction

Key Insights: The "Aha!" of Motifs

One of the most significant contributions of NAS-BOWL is its ability to identify universal performance drivers.

  • Topology Matters: The WL kernel’s ability to capture hierarchical, topological structures makes it far more query-efficient than path-encoding or GNN-based methods. It requires 3x to 30x less data to achieve the same predictive accuracy as competitors.
  • Discovering Building Blocks: The paper identifies specific "motifs" that consistently drive performance. For example, separable convolutions and parallel connections directly from the input are frequently present in high-performing cells across different tasks. Conversely, it also identifies "worst" motifs that degrade performance.
Best and Worst Motifs Discovered
  • Transferable Wisdom: Motifs identified as "good" on a simple task (like CIFAR-10) remain "good" when transferred to more complex tasks (like ImageNet). This suggests that NAS-BOWL is uncovering fundamental architectural principles rather than just overfitting to one dataset.
  • Automated Tuning: Unlike GNNs, which require their own complex hyperparameter tuning, the GPWL surrogate can automatically learn its optimal parameters (like the depth of the WL iterations) by maximizing marginal likelihood.

Performance and Results

The researchers evaluated NAS-BOWL across several standard and custom benchmarks, including NAS-Bench-101, NAS-Bench-201, Flowers102, and the DARTS search space.

NAS-BOWL outperformed or matched all major baselines (including BANANAS and GCNBO) on the NAS-Bench datasets. In the open-domain DARTS search space, NAS-BOWL found an architecture with a 2.50% test error on CIFAR-10 in just 3 GPU days. For context, some competing methods take up to 150 GPU days to reach similar results. Furthermore, the method proved robust even when the objective function was "noisy," such as when validation accuracy fluctuated due to random initialization seeds.

Limitations and Future Work

While NAS-BOWL is highly efficient, the authors acknowledge a few areas for future growth:

  • Computational Scaling: Gaussian Processes typically scale cubically ($O(N^3)$) with the number of observations. While this isn't an issue for the typical query budgets in NAS (usually < 200), it could become a bottleneck for extremely long search runs.
  • Multi-Objective Search: The current work focuses primarily on accuracy. Future iterations could incorporate other constraints like latency, memory footprint, or energy consumption directly into the motif-importance calculations.
  • Theoretical Convergence: While empirically superior, a formal theoretical analysis of the convergence rates for BO with WL kernels in these specific discrete spaces remains an open research question.

Summary updated

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.
BibTeX
@inproceedings{ru2021interpretable,
  author = {Bin Xin Ru and Xingchen Wan and Xiaowen Dong and Michael A. Osborne},
  title = {{Interpretable Neural Architecture Search via Bayesian Optimisation with Weisfeiler-Lehman Kernels}},
  booktitle = {International Conference on Learning Representations},
  year = {2021},
  url = {https://openreview.net/forum?id=r4JW9qJx-M0},
}
Figure