# Explainable Graph Neural Architecture Search via Monte-Carlo Tree Search (Full version)

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 27 of its 46 references that are in the map.
- First posted on arXiv 30 Aug 2023.

## Builds on (most cited first, 27 of 27)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Learning to Simulate Complex Physics with Graph Networks](https://mlsanity.com/paper/2002.09405/) (2020)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [From Anecdotal Evidence to Quantitative Evaluation Methods: A Systematic Review on Evaluating Explainable AI](https://mlsanity.com/paper/2201.08164/) (2022)
- [Random Search and Reproducibility for Neural Architecture Search](https://mlsanity.com/paper/1902.07638/) (2019)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [AutoML-Zero: Evolving Machine Learning Algorithms From Scratch](https://mlsanity.com/paper/2003.03384/) (2020)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Auto-GNN: Neural Architecture Search of Graph Neural Networks](https://mlsanity.com/paper/1909.03184/) (2019)
- [Simplifying Architecture Search for Graph Neural Network](https://mlsanity.com/paper/2008.11652/) (2020)
- [NAS-Bench-Graph: Benchmarking Graph Neural Architecture Search](https://mlsanity.com/paper/2206.09166/) (2022)
- [Beyond Real-world Benchmark Datasets: An Empirical Study of Node Classification with GNNs](https://mlsanity.com/paper/2206.09144/) (2022)
- [Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs](https://mlsanity.com/paper/2302.12357/) (2023)
- [AutoGraph: Automated Graph Neural Network](https://mlsanity.com/paper/2011.11288/) (2020)
- [A Survey on Fairness for Machine Learning on Graphs](https://mlsanity.com/paper/2205.05396/) (2022)
- [Neural Architecture Search using Deep Neural Networks and Monte Carlo Tree Search](https://mlsanity.com/paper/1805.07440/) (2018)
- [FOX-NAS: Fast, On-device and Explainable Neural Architecture Search](https://mlsanity.com/paper/2108.08189/) (2021)
- [Learning Interpretable Models Through Multi-Objective Neural Architecture Search](https://mlsanity.com/paper/2112.08645/) (2021)
- [Do Not Train It: A Linear Neural Architecture Search of Graph Neural Networks](https://mlsanity.com/paper/2305.14065/) (2023)
- [A Simple and Scalable Graph Neural Network for Large Directed Graphs](https://mlsanity.com/paper/2306.08274/) (2023)

## Abstract (arXiv)

The number of graph neural network (GNN) architectures has increased rapidly due to the growing adoption of graph analysis. Although we use GNNs in wide application scenarios, it is a laborious task to design/select optimal GNN architectures in diverse graphs. To reduce human efforts, graph neural architecture search (Graph NAS) has been used to search for a sub-optimal GNN architecture that combines existing components. However, existing Graph NAS methods lack explainability to understand the reasons why the model architecture is selected because they use complex search space and neural models to select architecture. Therefore, we propose an explainable Graph NAS method, called ExGNAS, which consists of (i) a simple search space that can adapt to various graphs and (ii) a search algorithm with Monte-Carlo tree that makes the decision process explainable. The combination of our search space and algorithm achieves finding accurate GNN models and the important functions within the search space. We comprehensively evaluate ExGNAS compared with four state-of-the-art Graph NAS methods in twelve graphs. Our experimental results show that ExGNAS achieves high average accuracy and efficiency; improving accuracy up to 26.1% and reducing run time up to 88%. Furthermore, we show the effectiveness of explainability by questionnaire-based user study and architecture analysis.