Analyzing the Properties of Graph Neural Networks with Evolutionary Algorithms

Graph Neural Networks (GNNs) have achieved remarkable success in graph structure learning, but recent research reveals their vulnerability to carefully designed perturbations. To address this, ProGNN, a GNN model based on graph properties, was proposed to clean perturbed graphs by jointly learning robust GNNs and structural graphs. However, ProGNN’s performance is affected by the quality and distribution of input graph data, making it sensitive to specific types or distributions and underperforming with diverse data. This work introduces EProGNN, a novel GNN model incorporating an evolutionary algorithm, which jointly processes perturbed graph properties and introduces an evolutionary approach during graph structure updates. EProGNN generates diverse graph representations (individuals) through mutation functions and evaluates their quality using a fitness function, retaining high-scoring individuals for optimization and eliminating low-scoring ones. EProGNN overcomes overfitting, effectively handles perturbed graphs, and learns better graph embeddings, offering a novel method for graph structure optimization. Experiments on benchmark datasets and baselines demonstrate EProGNN’s effectiveness and the advantages of evolutionary algorithms in graph optimization. Experiments on benchmark datasets and baselines demonstrate EProGNN’s effectiveness and the advantages of evolutionary algorithms in graph optimization. For example, on the Cora dataset, EProGNN achieved a 1.48% higher accuracy than ProGNN at a 25% perturbation rate and demonstrated greater robustness against targeted attacks.