An approach using BRKGA for optimizing graph neural network architectures

Abstract Graph Neural Networks (GNNs) have become essential for learning from graph-structured data, achieving strong results across node classification, link prediction, and graph-level tasks. However, identifying effective GNN architectures remains difficult due to the heterogeneous and high-dimensional nature of their search spaces, which combine discrete architectural operators with continuous hyperparameters. This paper introduces BRKGA-GNN, a Neural Architecture Search framework that leverages the Biased Random-Key Genetic Algorithm (BRKGA) to efficiently explore mixed discrete–continuous GNN design spaces. The novelty of our approach lies in three components: (i) a continuous random-keys encoding scheme, (ii) a parameterized decoder capable of translating random-key vectors into heterogeneous GNN topologies, and (iii) a rich and modular search space integrating aggregators, propagation mechanisms, normalization layers, activation functions, and pooling operators. BRKGA provides a principled and computationally efficient mechanism for navigating large architectural spaces, enabling smooth exploration through a continuous genotype while preserving structural validity through deterministic decoding. Experiments conducted on three benchmark citation networks (Cora, Citeseer, PubMed) demonstrate that BRKGA-GNN achieves competitive or superior performance compared to representative NAS baselines, including evolutionary, reinforcement-learning, and weight-sharing methods, while maintaining low variance and stable convergence behavior. The results indicate that BRKGA-GNN constitutes a robust and scalable framework for automated GNN design, highlighting the effectiveness of combining random-keys encoding with a structured decoder for exploring complex architectural search spaces.