GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries

Graph Neural Networks (GNNs) can model complex relationships while posing significant interpretability challenges due to the unique and varying properties of graph structures, which hinder the adaptation of existing methods from other domains. To address interpretability challenges in GNNs, GNNBoundary was designed as a model-level explainability tool to provide insights into their overall behavior. This paper aims to thoroughly evaluate the reproducibility, robustness, and practical applicability of the findings presented in the original work by replicating and extending their experiments, highlighting both strengths and limitations while considering potential future improvements. Our results show that while the algorithm can reliably generate near-boundary graphs in certain settings, its performance is highly sensitive to hyperparameter choices and suffers from convergence issues. Furthermore, we find that the generated solutions lack diversity, often representing only a single region on the decision boundary, which limits their effectiveness in broader decision boundary analysis. All the code used throughout the research is publicly available on GitHub. Published in Transactions on Machine Learning Research (05/2025) Scope of reproducibility This study aims to thoroughly evaluate the reproducibility, robustness, and practical applicability of the findings presented in the original paper (Wang and Shen, 2024), by replicating and extending their experiments. The main ideas of their work are summarised in the following claims: 1. GNNBoundary can reliably identify pairs of adjacent classes within the embedding space generated by a GNN. 2. The GNNBoundary algorithm generates faithful near-boundary graphs and is applicable to any GNN using the message-passing framework, regardless of the scale of the dataset. 3. The generated near-boundary graphs are essential for analysing the model's decision-making process. Their analysis involves three key metrics: (a) Explaining the model's susceptibility to specific misclassifications through the boundary margin. (b) Calculating the boundary thickness to evaluate the model's robustness to perturbations, such as adversarial attacks. (c) Using the boundary complexity to assess how well the model represents the data. 4. The adaptive loss function proposed by the authors enables faster convergence of the GNNBoundary algorithm and lowers the risk of local minima compared to the standard cross-entropy loss. We can verify Claim 2, but Claims 1, and 4 are only partially verifiable. Claim 3 is unverifiable for us, and we find evidence that contradicts it. We perform additional experiments on the authors' work to highlight the method's strengths and weaknesses, and to reflect on potential improvements. Our contributions are as follows: • We show that GNNBoundary can consistently generate near-boundary graphs in certain settings but exhibits convergence issues and is highly dependent on the choice of hyperparameters. • We investigate the limitations of GNNBoundary and demonstrate that the solutions found by the algorithm lack diversity and only represent a small region of the decision boundary. • We apply GNNBoundary to a new architecture, showing that the method struggles with more complex models, but can still produce useful results.