Surrogate-Assisted Linear Genetic Programming for Evolving Graph Neural Networks for Node Classification

Abstract

Neural Architecture Search (NAS) aims to automate the design of neural network architectures, reducing reliance on manual engineering. Evolutionary approaches provide flexible search mechanisms but suffer from high computational cost due to expensive fitness evaluations. In this paper, we propose a Surrogate-Assisted Linear Genetic Programming (SA-LGP) framework for automated design of Graph Neural Network (GNN) architectures for node classification. Unlike conventional NAS methods based on fixed-length or graph-structured encodings, our approach employs variable-length linear genetic programs to construct architectures composed of diverse message-passing layers and regularization operators. To reduce computational cost, we introduce a pairwise surrogate model that predicts whether an offspring architecture is likely to outperform its parent using genotype-derived features and early training signals. The surrogate acts as a filter within the evolutionary loop, enabling full evaluation only for promising candidates. A two-stage evaluation protocol is used, consisting of a cheap early-training phase and a full-training phase for selected architectures. Experiments on benchmark graph datasets show that SA-LGP discovers compact and competitive GNN architectures while significantly reducing the number of expensive evaluations, demonstrating the effectiveness of surrogate-assisted evolutionary search.