Assessing the explainability of Graph Neural Networks in random graphs classification task

Abstract Graph Neural Networks (GNNs) have become the dominant deep learning model for learning on graph-structured data, enabling breakthroughs in fields ranging from bioinformatics to social network analysis. Yet, as any deep learning model they suffer from ‘black box’ syndrome. Their decisions making process remains largely unknown. In this work, we want to advance our understanding of GNN explainability. We evaluate the performance and stability of GNNExplainer, a widely used post-hoc interpretability method, on the simple task of random graph classification. Using three very different GNN architectures, Graph Convolutional Networks, Graph Attention Networks, and Graph Isomorphism Networks, we examine the explainability of models trained to distinguish between Erdős-Rényi and Barabási-Albert random graphs, as well as between dk-randomized variants of four real-world networks. Our results show that despite the models achieving perfect classification accuracy, feature importance values identified by GNNExplainer exhibit substantial variability across architectures, hyperparameters, and random seed values. Moreover, the extracted explanations often fail to align with theoretical expectations based on established graph properties, such as degree distributions and degree correlations. These findings indicate that explanations produced by GNNExplainer are highly model-, configuration-, and seed value-dependent, challenging its reliability for deriving general insights into GNN decision mechanisms. Our work highlights fundamental limitations in the current generation of GNN explanations using GNNExplainer and suggests the need for more stable, theoretically grounded approaches to explainability in graph-based learning.