# Global optimization of graph acquisition functions for neural architecture search

arXiv: https://arxiv.org/abs/2505.23640 · HTML: https://mlsanity.com/paper/2505.23640/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 39 of its 56 references that are in the map.
- First posted on arXiv 29 May 2025.

## Builds on (most cited first, 30 of 39)

- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Regularized Evolution for Image Classifier Architecture Search](https://mlsanity.com/paper/1802.01548/) (2018)
- [A Tutorial on Bayesian Optimization](https://mlsanity.com/paper/1807.02811/) (2018)
- [Progressive Neural Architecture Search](https://mlsanity.com/paper/1712.00559/) (2017)
- [FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.03443/) (2018)
- [NAS-Bench-201: Extending the Scope of Reproducible Neural Architecture Search](https://mlsanity.com/paper/2001.00326/) (2020)
- [NAS-Bench-101: Towards Reproducible Neural Architecture Search](https://mlsanity.com/paper/1902.09635/) (2019)
- [Scalable Bayesian Optimization Using Deep Neural Networks](https://mlsanity.com/paper/1502.05700/) (2015)
- [A Comprehensive Survey of Neural Architecture Search: Challenges and Solutions](https://mlsanity.com/paper/2006.02903/) (2020)
- [Neural Architecture Search with Bayesian Optimisation and Optimal Transport](https://mlsanity.com/paper/1802.07191/) (2018)
- [BANANAS: Bayesian Optimization with Neural Architectures for Neural Architecture Search](https://mlsanity.com/paper/1910.11858/) (2019)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [GPflow: A Gaussian process library using TensorFlow](https://mlsanity.com/paper/1610.08733/) (2016)
- [Neural Architecture Search: Insights from 1000 Papers](https://mlsanity.com/paper/2301.08727/) (2023)
- [Neural Predictor for Neural Architecture Search](https://mlsanity.com/paper/1912.00848/) (2019)
- [Strong mixed-integer programming formulations for trained neural networks](https://mlsanity.com/paper/1811.08359/) (2018)
- [Graph Kernels: State-of-the-Art and Future Challenges](https://mlsanity.com/paper/2011.03854/) (2020)
- [GraKeL: A Graph Kernel Library in Python](https://mlsanity.com/paper/1806.02193/) (2018)
- [On Valid Optimal Assignment Kernels and Applications to Graph Classification](https://mlsanity.com/paper/1606.01141/) (2016)
- [Graph Kernels: A Survey](https://mlsanity.com/paper/1904.12218/) (2019)
- [Partition-based formulations for mixed-integer optimization of trained ReLU neural networks](https://mlsanity.com/paper/2102.04373/) (2021)
- [When Deep Learning Meets Polyhedral Theory: A Survey](https://mlsanity.com/paper/2305.00241/) (2023)
- [A Study on Encodings for Neural Architecture Search](https://mlsanity.com/paper/2007.04965/) (2020)
- [Optimization of Tree Ensembles](https://mlsanity.com/paper/1705.10883/) (2017)
- [Exploring the Loss Landscape in Neural Architecture Search](https://mlsanity.com/paper/2005.02960/) (2020)
- [DPNAS: Neural Architecture Search for Deep Learning with Differential Privacy](https://mlsanity.com/paper/2110.08557/) (2021)
- [Maximizing information from chemical engineering data sets: Applications to machine learning](https://mlsanity.com/paper/2201.10035/) (2022)
- [Mixed-Integer Convex Nonlinear Optimization with Gradient-Boosted Trees Embedded](https://mlsanity.com/paper/1803.00952/) (2018)
- [Global Optimization of Gaussian processes](https://mlsanity.com/paper/2005.10902/) (2020)

## Built on by (most cited first, 2 of 2)

- [The Catechol Benchmark: Time-series Solvent Selection Data for Few-shot Machine Learning](https://mlsanity.com/paper/2506.07619/) (2025)
- [Global Optimization on Graph-Structured Data via Gaussian Processes with Spectral Representations](https://mlsanity.com/paper/2511.07734/) (2025)

## Abstract (arXiv)

Graph Bayesian optimization (BO) has shown potential as a powerful and data-efficient tool for neural architecture search (NAS). Most existing graph BO works focus on developing graph surrogates models, i.e., metrics of networks and/or different kernels to quantify the similarity between networks. However, the acquisition optimization, as a discrete optimization task over graph structures, is not well studied due to the complexity of formulating the graph search space and acquisition functions. This paper presents explicit optimization formulations for graph input space including properties such as reachability and shortest paths, which are used later to formulate graph kernels and the acquisition function. We theoretically prove that the proposed encoding is an equivalent representation of the graph space and provide restrictions for the NAS domain with either node or edge labels. Numerical results over several NAS benchmarks show that our method efficiently finds the optimal architecture for most cases, highlighting its efficacy.