# Do Not Train It: A Linear Neural Architecture Search of Graph Neural Networks

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 65 references that are in the map.
- First posted on arXiv 23 May 2023.

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

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Neural Architecture Search with Reinforcement Learning](https://mlsanity.com/paper/1611.01578/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Image-based Recommendations on Styles and Substitutes](https://mlsanity.com/paper/1506.04757/) (2015)
- [FBNet: Hardware-Aware Efficient ConvNet Design via Differentiable Neural Architecture Search](https://mlsanity.com/paper/1812.03443/) (2018)
- [Single Path One-Shot Neural Architecture Search with Uniform Sampling](https://mlsanity.com/paper/1904.00420/) (2019)
- [Implicit Bias of Gradient Descent on Linear Convolutional Networks](https://mlsanity.com/paper/1806.00468/) (2018)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Understanding and Robustifying Differentiable Architecture Search](https://mlsanity.com/paper/1909.09656/) (2019)
- [Neural Architecture Search on ImageNet in Four GPU Hours: A Theoretically Inspired Perspective](https://mlsanity.com/paper/2102.11535/) (2021)
- [Neural Architecture Optimization](https://mlsanity.com/paper/1808.07233/) (2018)
- [Genetic CNN](https://mlsanity.com/paper/1703.01513/) (2017)
- [Hyper-Parameter Optimization: A Review of Algorithms and Applications](https://mlsanity.com/paper/2003.05689/) (2020)
- [DARTS+: Improved Differentiable Architecture Search with Early Stopping](https://mlsanity.com/paper/1909.06035/) (2019)
- [Stabilizing Differentiable Architecture Search via Perturbation-based Regularization](https://mlsanity.com/paper/2002.05283/) (2020)
- [Auto-GNN: Neural Architecture Search of Graph Neural Networks](https://mlsanity.com/paper/1909.03184/) (2019)
- [GeniePath: Graph Neural Networks with Adaptive Receptive Paths](https://mlsanity.com/paper/1802.00910/) (2018)
- [A survey of sparse representation: algorithms and applications](https://mlsanity.com/paper/1602.07017/) (2016)
- [Weight-Sharing Neural Architecture Search: A Battle to Shrink the Optimization Gap](https://mlsanity.com/paper/2008.01475/) (2020)

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

- [ADGym: Design Choices for Deep Anomaly Detection](https://mlsanity.com/paper/2309.15376/) (2023)
- [No Need to Train Your RDB Foundation Model](https://mlsanity.com/paper/2602.13697/) (2026)
- [ClimateLLM: Efficient Weather Forecasting via Frequency-Aware Large Language Models](https://mlsanity.com/paper/2502.11059/) (2025)
- [GSTAM: Efficient Graph Distillation with Structural Attention-Matching](https://mlsanity.com/paper/2408.16871/) (2024)
- [Explainable Graph Neural Architecture Search via Monte-Carlo Tree Search (Full version)](https://mlsanity.com/paper/2308.15734/) (2023)

## Abstract (arXiv)

Neural architecture search (NAS) for Graph neural networks (GNNs), called NAS-GNNs, has achieved significant performance over manually designed GNN architectures. However, these methods inherit issues from the conventional NAS methods, such as high computational cost and optimization difficulty. More importantly, previous NAS methods have ignored the uniqueness of GNNs, where GNNs possess expressive power without training. With the randomly-initialized weights, we can then seek the optimal architecture parameters via the sparse coding objective and derive a novel NAS-GNNs method, namely neural architecture coding (NAC). Consequently, our NAC holds a no-update scheme on GNNs and can efficiently compute in linear time. Empirical evaluations on multiple GNN benchmark datasets demonstrate that our approach leads to state-of-the-art performance, which is up to 200× faster and 18.8% more accurate than the strong baselines.