[RE] GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries
Authors: Tyme Chatupanyachotikul
Leonard Horns
Matei Nastase
Venue: Accepted by TMLR ()

Abstract: 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)
[RE] GNNBoundary: Towards Explaining Graph Neural Net- works through the Lens of Decision Boundaries
Matei Nastase
mater..nastasee@sttuuue.. uno.
Tyme Chatupanyachotikul
tyme. Symeecchhttpooggccoooooleutetete uva...
Leonard Horns
Reviewed on OpenReview: https: opwpr:/veeee..eeee.me net/ forum? id= 2L,LTHOdZW
Abstract
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 inter- pretability challenges GNNs, GNNBoundary was designed as a model-level explainability, tool provide insights into their overall behavior. This paper aims to thoroughly evaluate the reproducibility, robustnesss 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 per- formance 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 deci- sion boundary analysis. All the code used throughout the research is publicly available GitHub
1 Introduction
Rapid advancements Artificial Intelligence (AI) have led to its unprecedented integration across diverse domains, profoundly impacting companies, organizations, governments, and individuals (Rashid and Kausik 2024). However, the widespread adoption of Al-driven algorithms raises pressing concerns regarding their reliability, accountability, and ethical implications. Consoquently, research efforts have shifted focus from merely improving performance to developing tools that ensure AI systems are transparent, robust, and aligned with ethical standards (Bibi 2024).
Graph Neural Networks (GNNs) exemplify this challenge, offering an unparalleled ability to model complex relationships in graph data, but posing significant interpretability hurdles due to the unique and varying properties of graph data (Wang and Shen 2023), which prevent the adaption of most existing methods from other domains Yuan al. 2022).. These challenges are particularly concerning given GNNs deployment in applications where trustworthiness is critical (Wu et al. 2022a such molecular biology (Zhang et al, 2021), fraud detection (Cheng et al. 2022). and recommendation systems (wu et al. 2022b). Despite their growing prominence, rescarch on GNN explainability remains limited and mainly covers instance- level methods (Wang and Shen, 2023). Building on their prior work: GNNInterpreter (Wang and Shen 2023), GouNBaurd Towards Explaining Graph Neural Networks Through the Lens of Decision Boundaries (Wang and Shen 2024) further addresses this gap by proposing a model-level explainability method aimed at demystifying G.N decision-making through the generation and analysis of graphs near the decision boundaries of trained model.

---

Published in Transactions on Machine Learning Research (05/2025)
2 Scope of reproducibility
This study aims to thoroughly evaluate the reproducibility, robustness, and practical applicability of the find- ings presented in the original paper (Wang and Shen 2024h, 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 messago-passing framework, regardless of the scale of the dataset.
3. The generated near-boundary graphs are essential for analysing the model's drcision-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 evaluate the model's robustness to perturbations, such 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 verify Claim but Claims 1 and are only partially verifiable. Claim is unverifiable for us, and find evidence that contradicts it. We perform additional experiments the authors' work to highlight the method's s strengths and weaknessos, and to reflect on potential improvements. Our contributions are follows:
We show that GNNBoundary can consistently generate near-boundary graphs in certain settings but exhibits convergence issues and is highly dependent the choice of hyperparameters.
We investigate the limitations of GNNBoundary and demonstrate that the solutions found by the algorithm lack diversity and only represent 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.
3 Prerequisites
2024) is a novel modcl-level explainability tool that provides insights into the overall behavior of GNNs. Unlike prior instance-level explainability methods (Luo et al.) 2020 Ying et al.] 2019 Vu and Thai 2020). which focus on individual predictions, this tool analyses broader decision- making patterns across entire dataset. To develop the necessary background knowledge, first review some key concepts in graph theory, graph neural networks, and the closely related GNNInterpreter algorithm (Wang and Shen 2023)
GNNBoundary Wang and Shen
3.1 General theory and notations
For consistency, use the same mathematical notations as in the original papers. We represent graph G (V,&) as set of N nodes, V, and set of M edges, & C V x V. The node pairs in & may be ordered or unordered, distinguishing directed and undirected graphs. In memory, the graph is usually represented by a binary adjacency matrix A E {0, 1] NxN where ar = 1 only if there is an edge from node v; to and 0 otherwise.
GNNs (Scarselli al. 2009) leverage message- saassggg-assing mechanisms for learning node representations. A
GNN with T. layers consists of embedding function & (first K layers) and scoring function n (last I- K
2

---

Published in Transactions on Machine Learning Research (05/2025)
layers before softmax). We denote their sub-functions up to layer I as di and n, with the hidden node representations given by H (r( E NxD") where (() is the number of dimensions of the embedding.
At each layer, the network partitions the embedding space into C' decision regions (R. I [1, CT), where R. = =R. represents the decision region for class e in the input space. The classifier assigns class é to the graph if é = arg maxe fe(G), or in other words, G E R!! The decision boundary between two classes Be llea is defined as the region in the embedding space where the probability of a graph being assigned to either class Ci or class eg is exactly 0.5.
3.2 GNNInterpreter
A previous approach for model-level explainability in GNNs is the GNNInterpreter (Wang and Shen 2023 Similar to the GNNBoundary algorithm, GNNInterpreter employs Monte Carlo strategy to learn the parameters of distribution over the input space, enabling the sampling of graphs that maximise the model's confidence in its prediction for given class While the underlying methodology is the same for both algorithms, the learning objective is very different, requiring different criteria to facilitate convergence. GNNInterpreter utilises an additional objective to ensure that the generated data belongs to the true data distribution. This cannot be applied to GNNBoundary as datapoints belonging to two classes at once should not be part of the data distribution in typical classification problems.
4 Methodology
To reproduce the experiments, we make use of the official implementation published by the authors. Their repository provides access to an implementation of GNNBoundrr, datasets, environment details, and model checkpoints. We identify and resolve some discrepancics between the paper and the implementation, along with minor bug fixes, and expand the codebase by implementing the missing margin, thickness, and com- plexity metrics, as well our additional experiments. Our updated version is available in this repository!
4.1 GNNBoundary Algorithm
Identifying Adjacent Classes We identify adjacent classes (sharing decision boundary) using the adjacency score proposed by Waang and Shen (2024), which measures the probability that graphs sampled from the respective classes form an adjacent pair. Two classes are considered adjacent if their score exceeds a set threshold, indicating that most of the straight paths between the decision regions of the two classes do not cross any other class in the embedding space.
Generating boundary graphs To generate graphs near a decision boundary, we learn a distribution over which graphs best represent this boundary, assuming independence between both the edges (Gilbert random graph, Gilbert (1959) ) and node features (Wang and Shen 2024). Following their method, we optimise this minimise their novel objective function and applying a continuous relaxation (Maddison al.] 2017) to the edges and node features to enable gradient flow. This objective function is a modified version of the cross-entropy loss with target probabilities of 0.5 for both boundary classes, where the logits of the boundary classes are never minimised during training. We approximate the integral over our distribution through Monte Carlo integration. Additionally, we add both L1 and L2 regularisation on the parameters of the edge distribution, as well as a budget penalty on the number of edges following Wang and Shen (2023). Their method dynamically increases the weight for this budget penalty when the main convergence criterion is met, but the expected number of edges in the learnt distribution exceeds predefined threshold, preventing convergence. Conversely, it iteratively reduces the weight if the criterion is no longer satisfied. We consider the algorithm converged, if the expected class probabilities for both boundary classes are within the range [0.45, 0.55).
distribution by using Stochastic Gradient Descent (SGD)
3

---

Published in Transactions on Machine Learning Research (05/2025)
4.1.1 Boundary Analysis
Wang and Shen (2024) propose that a set of sampled boundary graphs for a class pair (21,02) can used to analyse the properties of the decision boundary by approximating Beillez- Following Wang and Shen (2024).
we implement three quantitative measures for this analysis.
The boundary margin measures the minimum distance between classifier's intermedi- ate representation and the decision boundary, providing insight into the model's generalisation and stability to input perturbations (Elsayed ct al. 2018). The asymmetric margin boundary equation formulated by Yang et al. (2020) is:
Boundary margin
(f.
[ (Ga (Ge,
min
(1)
obtain the boundary margin by selecting (G) to be the output embedding produced by the graph pooling layer, which aligns with standard practices for interpreting deep neural networks (Bajaj et al. 2021 J. To obtain the boundary margin, we calculate the minimum distance over all pairings of dataset graphs belonging to class c and a set of sampled boundary graphs.
As done by Wang and Shen (0224)
Boundary thickness Boundary thickness measures the expected distance between a level of predicted class probability in class' decision region and a corresponding boundary. Yang et al. (2020) show that thicker boundaries enhance robustness, while thinner ones lead to overfitting. The equation for asymmetric boundary thickness is:
+ (1,7, Co (Ga)) (Gaillez)) f.¹ 1 11200tchht)) dt
(2)
where P is a distribution over pairs of points (Go Ge, llez for E [0, 1], and 7 0.75 as done by Wang and Shen 2024 We approximate the integral term in the equation through discretisation: El=o 1)>0(((h())) -aae)))))n__naaaa (((((()))) where At is 0.02, and 50.
P.
We M(1) (1-1) -)- (Ga, + (Gellez)
Boundary complexity Complexity is a measure of the model's generalisability, where a high decision boundary complexity might indicate overfitting (Guan and Loew 2020 The generated boundary graphs approximate the decision boundary and can be used to mcasure boundary complexity by:
T(f. = H (A/1IAI)) (A(/Il)))((\ /og D (-
1-ECan (1s/ (1/112111)) /log D
where denotes the cigenvalues the covariance matrix of boundary graphs Gazll<z E Bealles Follow- ing Wang and Shen (2024). we work with the sample covariance of the last hidden layer representations, m (Gel))2), as this complexity measure applies only linearly separable boundaries.
4.2 Datasets
We evaluate the GNNBoundary algorithm on all three datasets used in the original work: Motif, Collab, and Enzymes, as well as one additional dataset. For each dataset, we reserve 10% of the samples for model evaluation. It is worth mentioning that dataset sizes reported here (Table are slightly higher than those in Wang and Shen (2024), likely due to updates since the original study.
The Molif datasel is synthetic dataset with classes: House, House-X, Complete-4, and Complete-5, which indicate a specific pattern that appears in each graph within this class. The Collab dataset is a real-world dataset containing graphs representing collaboration networks of researchers from three related physics fields: High Energy, Condensed Matter, and Astro. Noteably, more than half of the samples belong to the High
4

---

Published in Transactions on Machine Learning Research (05/2025)
Dataset
Nodes
Edges
Classes
Examples
Node feature
Motif
57.07
77.08
11,531
Categorical
Collab
74.49
2457.78
5,000
None
Enzymes
32.63
62.14
600
Categorical
Reddit
429.63
497.75
2
2,000
Noue
Table 1: Dataset statistics. For the number of nodes and edges, we report the mean across all examples.
Energy class. Lastly, the Enzymes dataset is another real-world dataset consisting of protein structures that can be divided into different classes.
To expand our investigation for Claim 2 we also apply GNNBoundary to the Reddit-Binary dataset (Red- dit). It consists of graphs representing the user interactions in Anestion-Answer Despite having only two classes, its significantly larger graph size (see Table I presents a unique challenge, allowing us to assess GNNBoundary 's effectiveness on larger graphs without the added complexity of multiple decision regions.
Discussion threads.
4.3 GNN Architectures
All original experiments follow the same architecture, consisting initial graph convolutional layers (Kipf and Welling 2017), pooling layer that applies sum and mean-pooling, fully connected layer with a ReLU activation, and a final linear classifier. The model sizes chosen to optimise performance, with specific configurations for each dataset: 3 graph-convolutionaal layers (embedding size of 6) for the Motif dataset, 5 layers (embedding size of 64) for Collab, and 3 layers (embedding size of 32) for Enzymes. For the additional Boeditt-iinary dataset, we also use 5 graph convolutional layers with an embedding size of 64. In our ovaluations, we analyse results from both the provided chockpoints and models we train ourselves (see Appendix B for training details). Finally, we lest GNNBoundary on a Graph Atlention Network (GAT) (Veličković et al. 2018) architecture by replacing the graph convolutional layers with graph attention layers, while keeping the number of layers and embedding size the same.
4.4 Hyperparameters
We base hyperparameters on those reported in the original paper. However, not all were documented, we also refer to their published demo notebooks. Notably, some hyperparameters differ between the paper and the demo, suggesting potential variations in the original experiments. For our additional investigations, we manually tune GNNBoundary's hyperparameters to ensure convergence, such as accommodating for the larger graph size in the Reddit dataset. However, we refrain from doing a full hyperparameter search because, between convergence rate and resulting class probabilities, the concrete objective for the search unclear. Additionally, robustly approximating their performance would require large number of runs per parameter combination, which is infeasible with limited resources. A full list of hyperparameters for both the original and additional experiments is provided in Appendix B
4.5 Experimental setup and code
A key difference between our approach and the original method is that we sample directly from the dataset when needed, whereas the authors frequently made use of GNNInterpreter to produce graph samples. We choose this approach to ensure the validity of the claims is independent of the sampling source (Wang and Shen 2024 and to evaluate GNNBound as a standalone method.
For each model, we establish the pairs of adjacent classes using the previously mentioned method from Section 4.1 We set the same threshold of 0.8 adjacency for every experiment. To
Adjacency between classes
5

---

Published in Transactions on Machine Learning Research (05/2025)
mitigate stochasticity and fluctuations of borderline scores inherent to the method, repeat the experiment 10 times and report mean adjacency scores for robustnesss
Boundary graphs To verify the capability of successfully learning a boundary graph distribution, we test the algorithm on all adjacent class pains of each respective dataset. For each pair, we run the algorithm 1,000 times, for a maximum of 500 iterations each. For every successful run (see Section 4.1 we sample 500 graphs from the learnt distribution and compute the mean and standard deviation over their predicted class probabilities. We report the convergence rate, as well as both the statistics for the best run, and their average across runs. For every pair of classes (c1 02), we select as the best run, the sampler that minimizes:
Σ (E(oL)a))
mean(p(e)) 0.5| + std(p(c))
(4)
Baseline The methodology for generating baseline boundary graphs was obtained from Wang and Shen (2024), which involves connecting random edge between randomly sampled pair of graphs: G1 E Rey: G2 E Rey. The rationale behind this idea is that the boundary graph should contain discriminative features for both of the adjacent classes. We sample 500 graphs per class pair for the evaluation of GNNBoundary.
Boundary analysis To generate the necessary boundary graphs, we sample from the graph distribution of the best converged GNN BoNddayy run. Since these evaluation metrics are influenced by the quality of the generated graphs, we only use graphs for which the predicted probabilities of the adjacent class pair lie within the range [0.45, 0.55). We use the same 500 sampled boundary graphs to calculate each metric.
4.6 Computational requirements
Our experiments have modest hardware requirements, as both the models and datasets are of moderate size. All experiments can be reproduced using an Intel Core 17-10870H processor (8 cores, 16 threads, 2.2 GHz base, 5.0 GHz boost). However, to accelerate computationally intensive tasks (such as training 1,000 samplers per class pair) we utilized an NVIDIA A100 GPU. The total computation time for our experiments was approximately 30 hours. During this period, we estimate energy consumption of 4.22 kWh, resulting in 1.87 kg of CO2 emissions, roughly equivalent to driving for km.
5 Results
5.1 Results reproducing original paper
Dataset
Original Paper
Provided Checkpoints
Retrained
Motif
0.99
0.95
1.00
Collab
0.74
0.85
0.78
Enzymes
0.52
0.73
0.53
Table 2: Model test set accuracies on each datasct. Columns show accuracies reported in the original paper, the accuracies of the official models' checkpoints, and our own retrained checkpoints.
Model training Analysing Table observe significant discrepancies between the reported model accu- racies and the provided checkpoints, making the exact reproduction of the authors' results challenging due to the nature of the GNNBoundary algorithm. These differences in accuracy may stem from unreported factors such as initialisation methods or random seed choices that lead to more favorable test. splits, particularly for the small-sized Enzymes dataset. Notably, training the models from scratch with the given hyperparameters yiclds accuracies more aligned with the original results. However, since our primary objective is replicate the authors' analysis, we mainly focus on the results obtained using the provided checkpoints in the following sections, while additional findings from trained models are detailed in Appendix

---

Published in Transactions on Machine Learning Research (05/2025)
EC1
1.00
0.07
0.71
0.66
1.00
0.82
house
1.00
1.00
0.01
1.00
0.88
EC1
1.00
0:57
0.58
0.79
0.73
0.60
EC2
0.07
1.00
0.67
0.82
0.47
0.82
house
1.30
1.00
0.02
1.00
6C3
0.58
0.82
1.00
0
0.72
0.70
EC3
0.71
0.92
1.00
0.74
0 78
0.79
1.00
CM
0.88
1.00
0.55
0.79
0.47
0.20
1.00
0.49
EC4
0.08
Ecb
0.73
0.49
0.72
0.70
1.00
0.78
EC5
1:00
0.61
0.78
0.81
1.00
0.95
comp_5
0.01
1.00
0.00
1.00
Advc
0.99
11.65
1.010
EC0
0.80
0.82
0.70
0.49
0.70
1.00
EC6
0.82
0.79
0.79
0.38
0:95
1.00
camp_4
1amp_5
E04
EC1
EC2
EC3
EC6
(a) Motif
(b) Collab
(c) Enzymes (reproduced)
(d) Enzymes (original)
Figure 1: Adjacency scores for cach model trained on the respective datasets.
Following the authors' approach, we first compute the adjacency scores for all classes across datasets and consider adjacent only the pairs that surpass the threshold of 0.8 as presented in Figure [ We successfully reproduce the same pairs of adjacent classes for Motif and Collab, but not for Enzymes. Although adjacent classes should generally share some features in the input space, their representation in the embedding space may vary significantly depending on the initialisation of the model and the local minimum to which it converges. For this reason, obtaining different pairs does not invalidate the correctness of the algorithm. On the other hand, we could not find any correlation between the adjacency scores and the performance of the GNNBoundary algorithm. Moreover, the presence of two outlier pairs: FC2 & EC3 and Condensed Matter & Astro (sce Table 3 makes Claim only partially verifiable.
Dataset
Class Pair
Complexity
GNNBoundary
Baseline
C1
C2
Orig.
Repr.
p(c)) / p((2)
p(c:) p(e2)
Motif
House House
House
6.55e-8
0,200
0.489
(0.039) / 0.511 (0.039)
0.054 (0.926) 0.166 (0.182)
Comp4
6.55e-8
0,122
0.504 (0.002) / 0.496 (0.002)
0.291 (0.699) 0.295 (0.306)
HouseX
Comp5
2.57e-7
0.163
0.490 (0.046) / 0.510 (0.046)
0.745 (0.018) 0.339 (0.096)
Collab
IIE
CM
0.0463
0.276
0.485
(0.015) 0.464 (0.025)
0.847 (0.131) 0.310 (0.295)
IIE
Astro
0.0246
0.174
0.495
(0.017) / 0.478 (0.018)
0.363 (0.629) 0.460 (0.466)
CM
Astro
0.031
0.492 (0.047) / 0.503 (0.048)
0.057 (0.281) 0.208 (0.436)
Enzymes
EC1
EC6
0.1492
0.218
0.457 (0.080) / 0.465 (0.074)
0.135 (0.274) 0.135 (0.274)
EC2
EC3
0.2325
/ 0.480 (0.040) / 0.481 (0.040)
0.118 (0.201) 0.230 (0.317)
BC2
EC6
0.012
0.176 (0.354) 0.298 (0.384)
Reddit
Q&:A
Discuss
0.182
0.462 (0.076) / 0.538 (0.076)
0.807 (0.193) 0.237 (0.237)
Table 3: GNNBounary results per dataset and class pair. For complexity, we report the original and our reproduced values. We report mean and standard deviation over sampled graphs for the class probabilities and use samples from the best converging run for GNNBoundary. All shown class pairs are adjacent, aside from (CM, Astro).
Generating Boundary Graphs For the datasets Motif and Collab, we are mostly able to produce the results of Wang and Shen (2024). Except for the class pair House-X Comp-5 the convergence rates of GNNBoundary are very high (see Table 4 and the best. runs for each respective class pair consistently gencrate graphs with boundary class probabilitics close to 0.5 (sce Table 3). The generated graphs also consistently outperform our baseline, which performs similarly to the results reported by Waan and Shen (2024) These results directly support Claim
For the Enzymes datasct, the convergence rates of GNNBoundary are drastically lower, and we are not able to achieve convergence at all for the class pair EC2, EC3 (see Table 4 Furthermore, the generated boundary graphs for the best runs seem to resemble the boundary less accurately (see Table 3 although they still outperform the bascline. In contrast, Wang and Shen (2024) were able to achieve high convergence rates for all 6 adjacent class pairs that they identified for their model. We likely observe different results because we have not been able to find good GNNBoundary hyperparameters for this dataset. Nonetheless, our results
7

---

Published in Transactions on Machine Learning Research (05/2025)
Dataset
Class Pair
Convergence
Run Means
Run Std. Devs.
C1
C2
Orig.
Repr.
p((x) / p(ez)
p(c,) / p(ez)
Motif
House
HouseX
0.86
0.940
0.512 (0.042) / 0.487 (0.012)
0.156 (0.062) / 0.158 (0.063)
House
Compd
1.00
0.833
0.516
(0.031) / 0.483 (0.031)
0.051 (0.024) / 0.051 (0.024)
HouseX
Comp5
0.76
0.096
0.503 (0.041) / 0.497 (0.041)
0.110 (0.046) / 0.110 (0.046)
Collab
HE
CM
1.00
0.999
0.486 (0.027) / 0.475 (0.028)
0.102 (0.036) / 0.105 (0.036)
HE
Astro
1.00
0.988
0,481 (0.027) / 0.492 (0.029)
0.072 (0.024) / 0.085 (0.028)
CM
Astro
0.982
0.499 (0.040) / 0.493 (0.039)
0.152 (0.051) / 0.150 (0.051)
Enzymes
EC1
EC6
0.75
0.002
0.460 (0.005) / 0.464 (0.001)
0.090 (0.014) / 0.077 (0.006)
EC2
EC3
0.74
0.000
EC2
EC6
0.062
0.470 (0.028) 0.485 (0.030)
0.094 (0.060) / 0.084 (0.057)
Reddit
Q&A
Discuss
0.222
0.480 (0.041) 0.520 (0.041) 0.167 (0.031) 0.167 (0.031)
Table 4: GNNBoundary results per dataset and class pair. For convergence, we report the original and our reproduced values. In Table 3 we only report the mean and standard deviation (std) of sampled graphs for the best run. Here, we look at the behaviour of these statistics across all converging runs. The columns Run Means and Run Std. Devs. display the mean and standard deviation of graph samples per run in the format. 'mean (std): All shown class pairs are adjacent, aside from (CM, Astro).
show that the algorithm can struggle with more complex datasets and is sensitive to the hyperparameter configuration.
Convergence is also highly dependent on both the dataset and the class pair. For example, the convergence rate of the class pair House-X & Comp-5 is drastically lower than for the other pairs in this dataset (sce Table 4 although the adjacency scores are equally good (sce Figure 1 Additionally, these average class probabilitiee are produced by the best converging runs for each class. We can see from Table that the mean class probability for sampled boundary graphs varies significantly across multiple runs, indicating that for several runs the generated boundary graphs are biased towards one class. The average standard deviation (Table 4 is also a lot higher than in our best runs, producing more graphs that do not closely represent the boundary.
Boundary Analysis In this section, Claim 3 is further investigated. The different boundary metrics are calculated and shown in Appendix D The numbers vary from the original paper, however, this is expected as we suspect the provided model checkpoints to be different from the model checkpoints used originally by Wang and Shen 2024).
Furthermore, Wang and Shen b024g claim that the boundary margin is a measurement of the robustness of boundaries to input perturbations, which is related to the risk of misclassification (Claim Ba); and have shown that the relative size of the boundary margin of adjacent classes can be used to evaluate the relative likelihood of misclassification. However, are unable to replicate this finding, as we cannot find any correlation between the boundary margin and the misclassification rate. Further analysis of this can be found in Appendix A
For boundary complexity, Wang and Shen 2024] claim that this metric can be used to analyse the complexity of the decision making rule. As our datasets have very different characteristics, and we use varyingly powerful models, we would expect the learnt decision boundarics to be very different. The authors anticipated that the decision boundary complexity of the Enzyme's model should be the most complex, as the classification of real-world datasets with multiple classes should be more challenging than synthetic datasets with fewer classes, which is supported by their numbers. However, in our experiments the values for the boundary complexity lie within a similar range for all three datasets, and there is no visible correlation (see Table 3 Therefore, we are unable to accept Claim Ce.
These results make us question the suitability of GNNBoundary samples for the computation of these metrics, which is why we refrain from further discussion of boundary thickness here. Instead, we investigate how well samples represent the decision boundary in Section 5.2
8

---

Published in Transactions on Machine Learning Research (05/2025)
5.2
Results beyond original paper
150
-5
125
0.0
0
-8
7.5
5.0
-12
0.0
-10
255
Emundeyy
-15
-35
-50
-25
-20
-15
-10
-5
-35
-30
-25
-20
-15
-10
-5
10
20
30
(a) PCA for adjacent class pairs of Motif.
80
50
50
40
20
-50
-90
-100
-150
-90
-250
120
140
-400
-300
-200
-100
(b) PCA for adjacent class pairs of Collab.
40
100
-20
40
-00
100
120
-200
-250
-200
-150
-100
-50
(c) PCA for adjacent class pairs of Enzymes.
Figure 2: Principle Component Analysis (PCA) of the Graph embedding space for the original datasets. We plot the Graph embeddings (G) of dataset graphs and generated boundary graphs G projected onto the first two principal components for all adjacent class pairs. For the generated boundary graphs, we sample 50 graphs from 10 different converged runs and highlight the result from the best run.
Qualitative analysis of the generated graphs In this section, we conduct further investigations to understand why we were unable to reproduce Claim A reason could be that the graph samples have a low variance, preventing them from adequately capturing the full landscape of the boundary between the two classes. To verify this, we project the graph embeddings of adjacent class pairs and their corresponding boundary graph embeddings onto the first two principal components using Singular Value Decomposition (SVD) to visually assess their diversity. For cach adjacent class pair, we randomly select 10 different con- verging runs (including the best one), and sample 50 graphs from each of the samplers.
As shown in Figure 2 each boundary graph distribution from the best sampler converges to single region, with graphs being generated only from its immediate vicinity. Although these graphs seem to lic at the boundary between the two classes, which supports Claim 2 they only represent a small region of it. This is particularly evident in Figure [2a] where the simplicity of the Motif dataset and the lower dimensionality of the model's 's embeddings show the scparation between classes and the boundary. This introduces a significant bias the computation of the suggested boundary metrics (margin, thickness, and complexity), and explains why the values obtained were inaccurate. Furthermore, we have observed that the variation in generated
9

---

Published in Transactions on Machine Learning Research (05/2025)
graphs are minimal, and all runs produce similar graphs. Utilizing all the graphs from the different samplers does still not yield an accurate representation of the boundary, potentially highlighting the limitation of this method.
To further support this point, we examine the distribution of the graph distribution parameters. The distribution has two types of parameters: O2g and Pit. fig represents the probability of sampling an edge between nodes i and j, while pik denotes the probability of sampling the discrete feature & for node i.
The parameter distributions of the learnt graph distributions are shown in Appendix F] We observe that the edge and node feature probabilities are highly skewed toward 0 or 1 for all class pairs across all datasets. This indicates that iteratively sampling from this distribution will consistently produce similar graphs, which can be verified by visualizing the samples (see Appendix G). The evidence presented demonstrates that conducting a comprehensive analysis of the entire boundary using a single GNNBoundary sampler is infeasible, as the method fails to capture the full diversity of the boundary. Therefore, we refute Claim 3
Dataset
Class Pair
Convergence
GNNBoundary
Baseline
C1
C2
p(e)) p(e2)
p(c)) / p((2)
Motif
House
HouseX
0.016
0.441 (0.127) 0.556 (0.126)
0.081 (0.200) / 0.852 (0.306)
HouseX
Comp5
0.529
0.486 (0.015) / 0.496 (0.014)
7.02e-5 (5.51e-1) / 1.000 (0.000)
HouseX
Comp4
0.080 (0.242) / 0.920 (0.242)
Comp4
Comp5
0.026 (0.120) / 0.022 (0.139)
Table 5: GNNBoundary results and convergence rates for the adjacent class pairs of the GAT model trained on Motif. For class probabilities, we report the mean and standard deviation over sampled graphs using samples from the best converging run for GNNBoundary. All values are rounded to three decimal places. Additionally, the development of the mean and standard deviation across runs can be found in Appendix E
Our previous experiments have demonstrated that the GNNBoundary algo- rithm can successfully generate graphs near the boundary between two classes, as Claim P asserts. However, we have relied solely on the GCN architecture so far, which raises concerns about the generalisability of the method. To address this, we apply the GNNBoundary to GAT, model with comparable performance benchnnarks (Dwivedi et al. 2022). but a distinct message-pasingg mechanism.
Achieving convergence for GNNBoundary on the GAT network proves more challenging than on GCNs due to persistent exploding gradients, which underscore the increased complexity of a GAT's latent space. To miligate this, we modily some of the hyperparameters (see Appendix BB, stabilizing the learning curves across experiments. For the class pairs where GNNBoundary converges, we achieve samplers of comparable quality (see Table 5) to those trained on the GCN architecture, supporting the claim that the method can be extended to other graph networks.
However, despite these adjustments, the convergence rates of the algorithm remain low, and for half of the class pairs, GNNBoudnary fails to converge even after extensive hyperparameter tuning. This highlights the challenges that arise when applying GNNBoundary to more complex message-passing schemes and empha- sizes the need for a deeper inderstanding of the method's optimisation process, which could be explored in future work.
Additionally, interesting phenomenon emerged when tracking the class probability progression (see Figure 3 for the pairs House & House-X X and House & Comp-5 that share common class (House), but have very different convergence rates of 2.1% and 49.2% respectively. We attribute this to the latent space structure, where House, House-X, and Comp-5 might form a triplet structure rather than two distinct adjacent pairs. This leads to a conflict for our objective: increasing House-X's probability inadvertently raises Comp-5's, preventing convergence. Such scenarios will be even more prevalent in datasets with more classes, which raises concerns about the scalability of the method in this regard, and explains our difficulties in reproducing the results of Wang and Shen (2024) for the Enzymes dataset.
10

---

Published in Transactions on Machine Learning Research (05/2025)
1.0
house
1.00
1.00
0.51
1.00
House House X Comp-6 "Ww
0.8
0.8
house
1.00
1.00
0.8
House
0.6
ww
House-X
comp_44
0.51
1.00
1.00
0.96
0.4
Comp-5
0.4
0.2
0.2
comp_5 5
1.00
0.45
0.96
1.00
0.0
0.0
house
house_x
comp
comp
200
300
400
500
50
100
150
(a) Adjacency scores
(b) House & HouseX
(c) House & Comp5
Figure 3: Adjacency scores and development of class probabilities during training for the GAT Motif. The class probabilities are shown for both adjacent pairs, namely House & HouseX, and House & Comp5,
Reddit-Binary To assess the scalability of GNNBoundary in terms the graph size, we introduce the Reddit-Binary dataset. Its samples contain significantly more nodes compared the datasets used by Waan and Shen (2024) (see Table D which drastically increases the complexity of the learnt graph distribution. Moreover, select binary classification problem evaluate the algorithm's performance on more complex data without encountering the complications discussed in the previous section.
In this new setting, we conduct additional hyperparameter tuning, which yield moderate results. While the convergence rate (see Table 4 is higher than that observed for the Enzymes dataset, it remains significantly lower than for the more successful datasets. The boundary complexity values (see Table 3) are consistent with those obscrved for other datasots. In contrast, the mean class probabilities per run are slightly worse, accompanied by a higher standard deviation. This outcome is anticipated, given the relatively lower number of convergent
and the higher variance inherent to sampling from larger graph distribution. These re- sults support the idea that the increased scale of the dataset does not hinder the ability of the GNNBoundary to converge, which aligns with Claim However, as shown in our experiments, scaling up the dataset does introduce several challenges, indicating that additional training strategies may still be needed to address these issues.
6 Discussion
Based on our results, we can only partially accopt the claims made by the authors. Their GNNBoundary algorithm drastically outperforms a naive approach, such as the proposed baseline, and can consistently generate boundary graphs, when the algorithm converges to good solution. However, there are several weaknesses.
Consistent convergence is difficult achieve, as the algorithm is highly sensitive to hyperparameter changes and tends to diverge in some settings, however for the solutions that converged, we were able to generate boundary graphs for all class pairs except for the Enzymes dataset. Furthermore, the true expected class probabilities of most solutions do not satisfy the specified stopping criterion, as convergence is determined based on the Monte-Carlo approximation and is therefore subject. to the variance of the sampled graphs. These difficultics seem to increase for growing number of number of classes or larger graphs, but with enough resources, is still possible to find these solutions. We therefore accept Claim 2 but the effectiveness for wider range of models remains to be investigated in future work.
When the algorithm does find a good solution, it fails to approximate significant region of the decision boundary, but instead, the learnt distribution only represents a single region on the boundary. This sig- nificantly reduces its value for analysing the decision boundary with the metrics proposed in Claim D and explains why in our experiments, the boundary complexity does not seem to be correlated with the different models. This is likely, due to lack of expressive power in the boundary graph distribution caused by the independence assumption edges and node features. Based these findings, we reject Claim 3
11

---

Published in Transactions on Machine Learning Research (05/2025)
Future research should focus on improving the stability and reliability of training by addressing hyperparam- eter sensitivity and exploring alternative graph distributions that better capture the full decision boundary. Strengthening convergence consistency would not only improve the algorithm's 's applicability but also enable a more reliable verification of Claim facilitating a fairer comparison between their novel criterion and standard cross-entropy loss.
6.1 What was easy
The architecture of the GNNBoundary is thoroughly explained in the paper, along with most of the essential thcoretical concepts needed to understand the algorithm. Each experiment is outlined adequately, with the set-up and the objectives clearly stated in the paper, which makes it easy to follow and assess the claims. Additionally, an official implementation of the algorithm is publicly available through a GitHub repository provided by the authors. The repository also includes model chockpoints as well as demo notebooks that allow for partial reproduction of the experiments, offering a solid foundation for our efforts of replicating this study. The pseudocode for both finding adjacent class pairs and the GNNBoundary was also provided in the paper, which made verifying the given implementation more accessible.
6.2 What was difficult
Finding good hyperparameterss for GNNBoundary posed particularly challenging, which made it hard to evaluate the effectiveness of their algorithm. Furthermore, we encountered several inconsistencies between the code and the paper. There appeared to be bugs in the novel optimisation criterion, the stopping criterion, and the Monte Carlo approximation used in the GNNBoundary algorithm. Additionally, graph samples were processed differently by the model al test-time, leading to unpredictable shift in the learnt distribution, and although this was not mentioned in their paper, only the graph edges were sampled from this distribution, while the node features were al always assigned the most probable value. Lastly, all datasets were slightly larger than the numbers indicated in their paper, but this did not appear to affect the results a significant way.
6.3 Communication with original authors
We reached out to the original authors for further clarification regarding their paper and the associated code in an effort to resolve the discrepancies and ambiguities previously discussed. However, we did not receive a response.
Acknowledgments
We thank the FACT-AI team at the University of Amsterdam for their support during this project, and Paul Koole for his collaboration in the carly stages. We are particularly grateful to Madhura Pawar for providing guidance and critical feedback.
References
Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam,, and Yong Zhang, Robust counterfactual explanations on graph neural networks. CoRR, abs/2107.04086, 2021. URL https: wwtxxii.rrg/bbb///// 04086
Palwasha Bibi. Establishing transparency and accountability in ai: Ethical standards for data governance and automated systems. 2024.
Dawei Cheng, Xiaoyang Wang, Ying Zhang, and Liqing Zhang Graph neural network for fraud detection via spatial-temporal attention. IEEE Transactions on Knowledge and Data Engineering, 34(8))3800-3814 2022. doi: 1..1109/KKDE.000.00000
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2022. URL http:///tww...r///////////////0/
12

---

Published in Transactions on Machine Learning Research (05/2025)
Gamaleldin F. Elsayed, Dilip Krishnan, Hossein Mobahi, Kevin Regan, and Samy Bengio. Large margin deep networks for classification, 2018. URL https://arxiv.. wwwpxivvorggaaan aaaaabbs18000 1803. 05598
Edgar Gilbert. Random graphs. The Annals of Mathemalical Statisties, 30 30(4):1141-1144 1959.
Shuyue Guan and Murray Loew. Analysis of generalizability of deep neural networks based on the complexity of decision boundary. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 101 106, 2020. doi:
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017. URL fttt:p:://opnnreviee form/orumm
SJU4ayYg1
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Pa- rameterized explainer for graph neural network, 2020. URL httpps//arraiw.org//b//// wtwgg////////....////// 04573
Chris J. Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. In International Conference on Learning Representations, 2017. URL https:
Adib Bin Rashid and MD Ashfakul Karim Kausik. Ai revolutionizing industries worldwide: A comprehensive overview of its diverse applications. Hybrid Advances, 7:100277, 2024. ISSN 2773-207X. doi: https://
2oi.org/10.10111 hybadd 2024.100277. URL httpp://ww..cieenndrrree...cddde
$2778207X24001386
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. TEFF Transactions on Neural Networks, 20(1):61-88) 2009. doi: 10.1109/TNN, 2008.2005605.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks, 2018. URL htttpss//arrii.oog//aa//1/1---..
Minh N. Vu and My T. Thai. Pgm-explainer: Probabilistic graphical model explanations for graph neural networks, 2020. URL attp:://arriv..rr//ab//000..... 05788
Xiaoqi Wang and Han Wei Shen. GNNInterpreter: A probabilistic generative model-level explanation for graph neural networks. In The Eleventh International Conference Learning Representations, 2023. URL https::/ nett:/orrummdd-rrgehhhtttt
Xiaoqi Wang and Han Wei Shen. GNNBoundary: Towards explaining graph neural networks through the lens of decision boundaries. In The Twelfth International Conference on Learning Representations, 2024.
URL http:p::///operevveeeeeeeteeee www.:/eefooumte. wiw.mmidddiwiiixxi..m
Bingzhe Wu, Jintang Li, Junchi Yu, Yalao Bian, Henglong Zhang, CHaochao Chen, Chengbin Hou, Guoji Fu, Liang Chen, Tingyang Xu, Yu Rong, Xiaolin Zheng, Junzhou Huang, Ran He, Baoyuan Wu, GUangyu Sun, Peng Cui, Zibin Zheng, Zhe Liu, and Poilin Zhao. A survey of trustworthy graph learning: Reliability, explainability, and privacy protection, 2022a. URL https://arx::: wwazewiwwwrr/ee. wttp://babb///..1000000
Shiwen Wu, Fci Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph neural networks in recommender systems: A survey. ACM Compul. Surv., 55(5), December 2022b. ISSN 03660-3300. doi: 10.1145/3535100 URL 1145/35351011
https://doi.org
Yaoqing Yang, Rajiv Khanna, Yaodong Yu, Amir Gholami, Kurt Keutzer, Joseph E. Gonzalez, Kannan Ramchandran, and Michael W. Mahoncy. Boundary thickness and robustness in learning models. CoRR, abs/2007.05088 2020. URL https::/ arxiv. http://wwwv..ooo/////////a/ httg/abs/2007.000
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovee. Gnnexplainer: Generating explanations for graph neural networks, 2019. URL stttps://ardd..rg/aaaa/////aae/s
13

---

Published in Transactions on Machine Learning Research (05/2025)
Hao Yuan, Haiyang Yu, Sharui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, 2022. URL httpps:://axxvv.ooo org/ absp/012.222..... 15445
Xiao-Meng Zhang, Li Liang, Lin Liu, and Ming-Jing Tang. Graph neural networks and their current applica-
tions in bioinformatics. Frontiers in Genetics, 12, 2021. ISSN 1664-8021, doi: 10.3389 2fg.:/fffeeee......ee. URL http::::/wwww..ooottt jtw.rrronnrerrssioooooorrrraaaaa /eaaaaac//rrrtiicee///.....0. /ww.:////eee...//////////3 fggne..gee.... 2021.690044
A
Evaluating boundary margin and misclassification rate
We further evaluate the boundary margin of the adjacent classes and the misclassification rate, to see whether lower boundary margin results in a lower misclassification rate. We present the results in Table
Correct Relative Misclassification Prediction from Boundary Margin
Dataset
Class
Adjacent Class
Boundary Margin
Misclassification
HouseX
0.48
House
Compá
Motif
House
0.57
HonseX
Comp5
0.93
Condensed Matter
3.21
High Energy
Astro
3.78
194
High Energy
2.91
161
Collab
Condensed Matter
Astro
3.61
28
High Energy
4.41
223
Condensed Matter
5.09
21
EC1
12.17
Enzymes
EC6
BC2
31.03
Table 6: Comparison of boundary margin and misclassification for adjacent classes. Final column indicates whether the boundary margin between two adjacent accurately predicts the relative misclasification rate.
From the results, there does not seem to a correlation between boundary margin and misclassification rate. For every dataset except Collab, the misclassification rate is higher for adjacent classes with larger boundary margins, and out of the pairs of adjacent classes, the boundary margin correctly predicts the relative misclassification rate of 2 pairs.
B Hyperparameters
B.1
Training GNN
Category
Parameter
GCN
GAT
Motif
Collab
Enzymes
Reddit
Motif
Optimization
Optimizer
SGD)
SGD)
SGD)
SGD
SGD
0.001
0.001
0.0001
0.004
0.001
Num epoch
128
1024
4096
100
128
Table 7: Hyperparameters used to train GNN for each dataset across different architecture. After training for the set number of epochs, the best model is chosen as the model with the highest validation accuracy.
B.2 GNNBoundary
The equations associated with the hyperparameters are shown for additional clarity.
Objective function
14

---

Published in Transactions on Machine Learning Research (05/2025)
L(G)= = E B.n(G)w D' (MG))=
Σ a (G)) (1 -"(l)) p0
(5)
(E(().2) Here the predicted probability for a Graph and class is given as p (bG) softmax(1((G))
(e(e)
Near-Boundary Criterion
(G) ((ac)) (G)
(6)
Regularization
Roudget
Softplus (Il [[ssimmi -B)²
(7)
Dynamic Regularization Scheduler
(v(G()) I(-v(Gt0))(aa)) budget 2 2
budges }}
W budget
(t)
(t-1) w budget
inn
Sec
(8)
Category
Parameter
GCN
GAT
Description
Original Datasets
Biuary Reddit Dataset
Motif Dataset
Criterion
See Eq.
See Eq.
W.
25
25
25
Criterion weight
Regularisation
1.1
1.I regularien larisation weight
L2
1
L2 regularisation weight
10
100
30
Anticipated max odges 7
Buttipi
Controls sharpness Solpplus transition
Optimisation
Optimiser
SGD
SGD
SGD
0.01
Learning rate of optimiser
Puina: Pmax.
00.45, 0.55
[0.45, 0.55]
[0.45, 0.55]
Relaxed near boundary criterion
6
Bmax
60
400
60
Max edges for convergence
"uddet
Initial budget penalty weight
1.15
1.15
1.15
Budget penalty incremeut
0.98
0.98
0.98
Budget penalty decrement
Kyc
32
32
32
Monte Carlo sample count
Graph distribution
Naaax
25
150
50
Max number of nodes
0.15
0.15
Conerete distribution temperature
Table 8: Hyperparameters used for GNNBoundary across different datasets. The regularisation parameters, optimisation settings, and graph distribution constraints are listed for GCN and GAT models. The original datasct consists of Motif, Collab, and Enzymes.
15

---

Published in Transactions on Machine Learning Research (05/2025)
C Results from our own trained model
We applied the GNNBoundary algorithm to our independently trained GNN model using the same datasets as the original study to assess its effectiveness beyond the provided checkpoints. As shown in Table [ GNNBBuudary successfully generates improved boundary graphs compared to the basclinc. However, for the Collab and Euzymes datasets, the generated boundary graphs deviate from the target class probability of 0.5.
Consistent with reproduced results using the original checkpoint, the standard deviation of class prob- abilities in the converged runs remains high, and GNNBoundary exhibits a low convergence rate for the Enzymes dataset (see Table
EC1
1.00
0.70
0.66
0.76
0.80
0.70
house
1.00
0.00
0.00
1.00
1.00
0.93
1.00
EC2
0.70
1.00
0.66
0.67
0.77
0.76
0.00
1.00
1.00
1.00
EC3
0.66
0.66
1.00
0.20
0.58
0.59
1.00
0.64
EC4
0.76
0.67
0.20
1.00
0.69
0.61
comp_4
0.00
1.00
1.00
0.00
ECS
0.80
0.77
0.58
0.69
1.00
0.80
1.00
0.64
1.00
comp_5
1.00
1.00
0.00
1.00
EC8
0.70
0.76
0.59
0.61
0.80
1.00
house_x
comp_4
comp_5
HE
CM
Astro
EC1
EC4
EC5
EC6
(a) Motif
(b) Collab
(c)
Enzymes
Figure 4: Adjacency scores for our retrained models Motif, Collab, and Enzymes.
Dataset
Class Pair
Complexity
GNNBoundary
Baseline
C1
C2
p(c1) / p(c2)
p(c)) / p(c2)
Motif
House
Comp5
0.194
0.521 (0.053) / 0.479 (0.053)
0.022(0.107)
0.977 (0.107)
HouseX
Comp4
0.341
0.502 (0.045) / 0.496 (0.044)
0.041(0.167)
0.959 (0.167)
HouseX
Comp5
0.509
0.505 (0.045) / 0.486 (0.043)
0.945(0.207)
0.055 (0.207)
Collab
HE
CM
0.217
0.448 (0.027) / 0.498 (0.029)
0.845 (0.234) / 0,138 (0.231)
HE
Astro
0.135
0.464 (0.017) / 0.459 (0.017)
0.384 (0.427) / 0.603 (0.439
Enzymes
EC1
EC5
0.262
0.480 (0.101) / 0.394 (0.106)
0.219 (0.362) / 0.333 (0.362)
FC5
FC6
2.87e-14
0.422 (0.096) / 0.457 (0.084)
0.356 (0.417) / 0.221 (0.350)
Table 9: GNNBoundry results per dataset and class pair from our trained model. For class probabilities, report the mean and standard deviation sampled graphs using samples from the best converging for GNNBomnary, All values are rounded to three decimal places.
16

---

Published in Transactions on Machine Learning Research (05/2025)
Dataset
Class Pair
Convergence
Run Means
Run Std. Devs.
C2
p(c1) p(ez)
p(c1) p(c2)
Motif
House
Comp5
0.884
0.511 (0.042) 0.489 (0.042)
0.162 (0.054) 0.162 (0.054)
HouseX
Comp4
0.410
0.501 (0.038) 0.495 (0.038)
0.116 (0.066) 0.119 (0.066)
HouseX
Comp5
0.607
0.482 (0.042) 0.487 (0.041)
0.167 (0.060) 0.145 (0.064)
Collab
HE
CM
0.973
0.459 (0.014) 0.460
(0.016)
0.062 (0.009) 0.077 (0.014)
HE
Astro
0.004
0.455 (0.006) 0.455 (0.004)
0.023 (0.004) 0.020 (0.003)
Enzymee
EC1
EC5
0.092
0.472 (0.050) 0.452 (0.053)
0.190 (0.054) 0.202 (0.054)
EC5
EC6
0.040
0.380 (0.026) 0.533 (0.036)
0.206 (0.026) 0.210 (0.026)
Table 10: GNNBoundary results per dataset and class pair from our own trained model. The Convergence column represents the reproduced value. The columns Run Means and Run Std. Dees. display the mean and standard deviation of graph samples per run the format 'mean (std); All values are rounded three decimal places.
D Boundary evaluation metrics
Boundary Margin
Boundary Thickness
Confusion Matrix
house
0.41
2.17
house
20.25
29.25
house
2622
194
Motif
house_x
0.60
0.86
house_x
15.34
12.14
house_x
12
2898
0
44
1.37
comp
26.95
199
27.32
comp_5
comp
comp
2800
house
house_x
comp_4 comp_5
house
house_x comp_4
comp_5
house
house_x comp_4 comp_5
HE
3.50
3.64
HE
7.75
8.51
HE
2297
109
194
Collab
CM
2.77
5.13
CM
10.63
12.48
CM
161
586
28
HE
CM
Astro
HE
CM
Astro
HE
CM
Astro
EC1
65
3
5
9
7
11
EC1
14.79
EC1
194.01
65
8
8
Enzymes
EC2
25,
EC2
115.90
71
8
3
5
6
0
80
6
EC6
20.87
12.95
EC6
122.22
90.68
EC6
4
8
3
2
6
77
EC1
EC2
EC6
EC1
EC2
EC6
EC1
EC2
EC3
EC4
EC5
EC6
Figure Boundary analysis results for the three original datasets. We compute boundary margin and thickness for adjacent class pairs well the confusion matrices for the corresponding models.
17

---

Published in Transactions on Machine Learning Research (05/2025)
E
Results of GNNBoundary on GAT model
Dataset
Class Pair
Complexity
Run Means
Run Std. Devs.
C1
p(c)) / p(c2)
p(c)) / p(c2)
Motif
House
HouseX
0.050
0.506 (0.072) 0.483 (0.073)
0.294 (0.150) 0.295 (0.151)
XouseX
Compā
0.021
0.491 (0.077) / 0.507 (0.077) -
0.272 (0.132) 0.273 (0.132)
HouseX
Comp4
0
Comp4
Compō
Table 11: GNNBoundary results per dataset and class pair from trained GAT model. The columns
Run Means and Run Std. Dees. display the mean and standard deviation of graph samples per run in the format mmean (std). All values are rounded to three decimal places.
F
Graph distribution parameter analysis
Here, we show the parameter distributions of the graph distributions learnt by GNNBoundary. Figure f is the parameter distribution for the Motif dataset, Figure for the Collab dataset, and for the Enzymes dataset.
Heargam (weghes) dads
Hisoggan Theta (Edge Weight))
<4
Hallogaa (Fasture Diighhtal (0.2
ttitogmmn Thets (Edge Velght)
Poblbbiy
Pobabityy
Figure 6: Histogram of graph distribution parameters learnt for the Collab Dataset for all adjacent class pairs.
18

---

Published in Transactions on Machine Learning Research (05/2025)
Hasogram |Featuue weights] class pair (1.3)
Histogram p1 (Feature weights) claes pair (1,3)
Histogram of p2 (Feeture 2 weights) cless pair (1.5(
Hislogram of p3 l'eeatur 3 weights) class pair [1,3]
Histogram of p4 (f (Fieature weighes) clace pair (1.3)
Histogram Thets (Edge Weihtts)
25.9
25.
23
19:0
10.0
Deesfy
Dendfyy
Dendy
Dendy
10.0
130
5.0
0.4
90
0.2
2.4 Probatilty
20
20
1.0
00
02
0.8 Probac
6.4 Probabilly
0.8
0.4 Protability
Probabilty
Protabrity
Histogram of p0 (" /eeturre weights] cless pair (0.2)
Histogram of
Histogram of p2 (Feature 2 weights) clese per (0.2)
Histogram of p3 (F /'eature 3 weights) clese pair (0.2)
Histagram of pf (F (Feature 4 weeignes) clees pair (0.2)
Histogram of Thete (Edgg Weights)
pT (Festure 1 weights) dles pair (0.2)
200
14
12.5
200
12
150
13.5
Denefy
Dentiyy
Densiyy
Denuty
100
2.5
255
022
2.4
12
Probanilly
Pobsabity
Pistablily
Protosilly
Probatily
Pistabilty
Histogram weights] clos's pair (0.1)
Histogram p1 (Feelure weighra)
Histogram of p2 (Feeture 2 weighte) pair (0.1)
Histogram of p8 (Feeture weights)
Histogram p4 weights) class pair (0.1)
Histogram Thita (E:gg Weights)
pair (D.1)
pair
25
250
14
15.6
200
12
12.5
100
Danial
12
Denstr
13
30
130
80
08
0.2
022
30
0.2
00
12
50
3. Protebility
6.3
1.0
0.5 Proboc
08
10
6.4 0.6
8.3
02
044 Pictabiity
Probuciiity
Probabiity
Probabilly
Figure 7: Histogram of graph distribution parameters learnt for the Motif Dataset for all adjacent class pairs.
19

---

Published in Transactions on Machine Learning Research (05/2025)
Hitggan Thate Edde Viegins)
caess per $0.0
class (0.8)
cless par (8.0)
20
Protuci
Mistogram p0 theature weighta)
Haatggumm of a1 (Phasture welgho))
Histogrmm of 02 (Tuature weights
14
Potubilyy
Figure 8: Histogram of graph distribution parameters learnt for the Enzymes Dataset for all adjacent class pairs.
20

---

Published in Transactions on Machine Learning Research (05/2025)
G GNNBoundary samples
In this section, we visualise the boundary graphs generated by GNNBoundary alongside the graphs obtained from the dataset. We sample 5 graphs using GNNBoundary for each adjacent class pair in the Motif, Collab and Enzymes dstasets(see Figure Dh.
Motif
House
House - HouseX
Housex
House
Compé
Comp4
Comp5
Collab
High Enargy
High Energy Condense Mater
Condense Matiw
High Energy
High Energy Astro
Asto
Enzymes
E01
EC1 E08
E08
5G2
EC2 508
E06
Figure 9: Samples generated by GNNBoundary for each adjacent class pair, alongside the graphs sampled from the datasct, in Motif, Collab, and Enzymes.
21


Reviews:
[{"review_id": "MqGz5927ls", "reviewer": "Reviewer_K7rc", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well structured. I particularly appreciate paragraph 2, where the authors provide a schematic summary of the claims tested, which is not present in the original paper.\n- The authors don't limit their work to just reproducing the original experiments; they also allegedly (I didn't verify this myself) extended the original code, they provide further experiments on one more dataset and one more model, and they give further insights on the original results.\n\nWeaknesses:\n- The description of the original method is sometimes a bit short, forcing the reader to look at the original paper too.\n- In some parts of the paper, it is not fully clear what is a new contribution and what is not. For example, in paragraph 4.1 the authors frequently use the pronoun \"we\", where it seems they are describing the original method. \n- It would have been nice to add more datasets and models.\n- See in the section below some other limitations.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors present a reproducibility study of \"GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries\", which introduced a model-level explainability method for GNNs.\nThey reproduce the original experiments, pointing out some reproducibility concerns, and introduce further analyses and tests to verify the original claims.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. More important concerns:\n    - The baseline used in the original paper is admittedly quite naive, isn't there a way to improve it?\n    - The authors decided to sample graphs directly from the dataset instead of using GNNInterpreter (paragraph 4.5). They say to do so to verify that the method is independent from the sampling source, but I could not find this claim in the original paper, nor it is reported in paragraph 2. To what extent does this choice explain the difference in results?\n    - Is there a reason why it was not possible to report a standard deviation for the boundary complexity in Table 3?\n    - In the paragraph \"Boundary analysis\", it is claimed that there is no correlation between the boundary margin and the misclassification rate. Can the authors quantify this correlation?\n    - In the same paragraph, the authors say that the claim that boundary thickness is a measure of robustness to adversarial perturbations would need to be explored in a future work. In my opinion, having two reproducibility studies for the same method is a bit hard to justify, and it would have been interesting to see this point explored further.\n    - In paragraph 5.2, the authors show that what GNNBoundary finds is a small portion of the real boundary. Does this result change between runs?\n\n\n2. Some concerns that I have on the original paper that were not analysed in this review:\n    - Is there a meaningful difference between the boundary margin and the boundary thickness? They both measure a distance between a class and a boundary, I am left wondering if they are redundant.\n    - The original paper takes the definition of boundary complexity from a paper by Guan and Loew (2020), who argue that this metric doesn't take into account if a boundary shows more complex local structures, e.g. zigzags. It would have been interesting to criticise and analyse the effects of this simplification.\n\n3. Minor mistakes or typos:\n    - The notation used for GNN is a bit confusing, where $l$ seems to indicate both the number of GNN embedding functions, but also a specific layer\n    - $D^{(l)}$ has not been defined\n    - In paragraph 3.1, $G\\in\\mathcal{R}^{(L)}_{c}$ should be $G\\in\\mathcal{R}^{(L)}_{\\hat c}$\n    - In equation (2), the $dt$ is missing from the integral. Also, the distribution $P$ has not been introduced.\n    - When introducing the metric \"boundary thickness\", the authors describe it as \"the expected distance traveled along line segments\n between classes across a decision boundary\". I don't agree with this description because the formula computes an expected value between class $c_1$ and the boundary $c_1 || c_2$, not between $c_1$ and $c_2$.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Dnj6yRM7YO", "reviewer": "Reviewer_3mPi", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Weaknesses: \nThe paper frequently attributes differences in results to hyperparameter choices but does not provide a systematic sensitivity analysis to confirm this. Additionally, it does not test how random seeds, weight initialization, or stochastic optimization methods influence results. Running multiple trials with fixed vs. varying seeds would help separate systematic errors from random variations. Another limitation is that the datasets used are likely updated versions of those in the original study, which could affect reproducibility. Even small changes in dataset composition may alter adjacency relationships and decision boundaries, making it unclear whether discrepancies arise from methodological differences or dataset updates.  \n\nStrengths:\nThe paper systematically evaluates the original claims by replicating and extending experiments. Testing on an additional dataset, Reddit-Binary, allows for an assessment of scalability, while applying GNNBoundary to a different architecture (GAT) provides insights into its generalizability.\nThe study also includes robustness checks on convergence and decision boundary metrics, improving the evaluation of GNNBoundary’s reliability. By identifying key limitations the paper provides a balanced analysis and offers directions for improvement.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper evaluates the GNNBoundary algorithm, a model-level explainability tool designed to interpret Graph Neural Networks (GNNs) through decision boundary analysis. The authors attempt to replicate and extend the experiments of the original paper to assess reproducibility, robustness, and practical applicability.\nThey focuses and try to verify the following claims on the original paper: \n1)GNNBoundary identifies adjacent class pairs within the GNN embedding space. (Partially verified)\n2)It generates near-boundary graphs applicable across different GNN models and datasets. (Verified with caveats)\n3)These graphs allow for effective decision boundary analysis using boundary margin, thickness, and complexity metrics. (Not verified, with evidence contradicting the claim)\n4)An adaptive loss function improves convergence and reduces local minima. (Partially verified)\nThey also extend the original paper by testing the model on an additional dataset (Reddit dataset) and on an additional architecture (Graph Attention Networks GAT) and by investigating the limitations of the proposed method.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "A proper study, such as a grid search or an ablation study, would quantify the exact impact of hyperparameters on reproducibility. The paper attributes performance differences to hyperparameter choices but does not systematically analyze their influence. A structured sensitivity analysis would help determine which parameters have the most significant effect on convergence and accuracy. Additionally, the datasets used in this study appear to be updated versions of those in the original paper. The authors mention that dataset sizes are slightly higher than those reported in Wang and Shen (2024), likely due to updates. This discrepancy can affect the reproducibility of results, as even minor variations in dataset composition could lead to different adjacency relationships and decision boundaries. Since reproducibility studies aim to assess whether results can be replicated under the same conditions, it is important to clarify the potential impact of dataset updates. Running experiments on older versions of the datasets, if available, or quantifying the effect of dataset changes on the results would strengthen the claims about reproducibility. \nBoth of these aspects could strengthen the assumptions and narrative of the paper. A sensitivity analysis of hyperparameters would provide a more precise evaluation of their role in shaping the results, reinforcing the reliability of the conclusions. Similarly, addressing dataset version differences would enhance the clarity of the reproducibility discussion, ensuring that variations in results are correctly attributed.", "broader_impact_concerns": "There are no concerns regarding the ethical implications of this work that would require adding or modifying a Broader Impact Statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "4Y1huG4JBY", "reviewer": "Reviewer_B3Up", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The analysis and experiments are well-structured and systematically aligned with the claims presented in the original study, ensuring clarity and coherence.\n- The work introduces a new dataset and model, extending evaluation beyond what was originally tested\n- The experiments and analyses are conducted with a good level of detail, providing both numerical and visual insights that contribute to a deeper understanding of the method’s behavior.\n- Discrepancies between the original experiments and the corresponding code are identified and thoroughly examined, with a comprehensive discussion provided in both the main paper and the appendix.\n- The submission provides well-founded and compelling evidence to support its statements, offering insights that are valuable to the research community.\n\nWeakness:\n- The performance of the Reddit-Binary dataset should be analyzed in greater detail, with a thorough motivation of the results and a clear explanation of the potential underlying factors influencing them, other than the graph-size increment.\n- Extending the findings with only a single additional dataset and model may lack robustness, as broader validation across multiple datasets and architectures would provide stronger support for the conclusions.\n- GNNBoundary is highly sensitive to hyperparameters, making stable convergence difficult. While the study documents this, a clearer quantification of search effort (e.g., computational cost) would improve clarity.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper analyzes and evaluates the GNNBoundary method, which provides model-level explanations for Graph Neural Networks (GNNs). The authors assess the reproducibility of experiments, the method's robustness, and its applicability to different contexts, identifying both its strengths and limitations.\nTo achieve this, the authors conduct a series of experiments—some replicating those in the original study and others introducing variations—to both validate certain claims made by the original authors and challenge others. These experiments focus on reproducing the original results, testing the model on a new dataset, evaluating its performance with a different GNN architecture, and conducting a qualitative analysis of the generated graphs concerning the decision boundary.\nThe findings from these experiments and analyses provide the motivation and scope for this study. Specifically, the reproducibility studies are structured to verify the claims made in the original paper regarding:\n- The identification of adjacent class pairs,\n- The generation of near-boundary graphs and the method's applicability to any GNN,\n- The evaluation metrics used, including boundary margin, thickness, and complexity,\n- The proposed loss function’s faster convergence and reduced risk of local minima.\n\nThe code is publicly available. Additional results are presented in the Appendix.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- How challenging was the hyperparameter tuning process? The paper frequently emphasizes the high sensitivity of the procedure to hyperparameter choices. Explicitly quantify this challenge in terms of the number of parameters to be tuned and the associated computational cost. While the list of hyperparameters is provided, specifying the extent of the search required to determine optimal values—such as computational time or resources needed —would help clarify the effort involved.\n- In Appendix, Section G, consider adding images of the graphs corresponding to the classes from which the generated graphs originate. Without them, the explanation lacks clarity.\n- Style and Grammatical Errors: \n    - Sec. 4.2: \"We evaluate the GNNBoudnary\" → Typo: \"GNNBoundary\"\n    - Sec. 4.1.1: \"...might indicate overfitting Guan and Loew (2020)\" and Sec. 3.1: \"GNNs Scarselli et al. (2009).\" → Consider placing citations within parentheses for correctness and readability.", "broader_impact_concerns": "No significant ethical concerns arise from this work. The authors have demonstrated awareness of sustainability aspects by transparently reporting the energy cost of their research. Additionally, no potential negative impacts related to bias, security, or misuse of the proposed technology have been identified.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper had three reviews, which were positive in terms of validity and completeness of the claims. There is a consensus that the paper is written well, and most sections are interesting, including the novel experiments and studies. Two reviewers (B3Up, 3mPi) were concerned by the lack of a systematic investigation of hyper-parameters. However, as the authors clarify, this is much harder when considering explainability, and both reviewers were satisfied by the answer. All further comments by reviewer K7rc were addressed. The methodological part is difficult to read without having read the original paper, but this is expected for a reproducibility study.

The authors are invited to double check and proofread everything, as there are minor typos (e.g., "Recommendation systems Wu et al. (2022b)" has the citation formatted wrongly, "explainability methods(Luo et al. (2020) [...])" has a missing space, etc.).
Decision: Accept (poster)