[RE] GNNBoundary: Finding Boundaries and Going Beyond Them
Authors: Jan Henrik Bertrand
Lukas Bierling
Ina Klaric
Aron Wezenberg
Venue: Accepted by TMLR ()

Abstract: Graph classification models are becoming increasingly popular, while explainability methods face challenges due to the discrete nature of graphs and other factors. However, investigating model decision-making, such as through decision-boundary regions, helps prevent
misclassification and improve model robustness. This study aims to reproduce the findings of GNNBoundary: Towards Explaining Graph Neural Networks Through the Lens of Decision Boundaries (Wang & Shen, 2024). Their work supports 3 main claims: (1) their proposed algorithm can identify adjacent class pairs reliably, (2) their GNNBoundary can effectively and consistently generate near-boundary graphs outperforming the cross entropy baseline and (3) the generated near-boundary graphs can be used to accurately assess key properties of the decision boundary; margin, thickness, and complexity. We reproduce the experiments on the same datasets and extended them to two additional real-world datasets. Beyond that, we test different boundary probability ranges and their effect on decision boundary metrics, develop an additional baseline, and conduct hyperparameter tuning. We confirm the first claim regarding the adjacency discovery as well as the second claim that GNNBoundary outperforms the cross-entropy baseline under the limitation that it requires intensive hyperparameter tuning for convergence. The third claim is partially accepted as we observe a high variance between reported and obtained results, disproving the reliability and precision of the boundary statistics.
Code and instructions are available at: https://github.com/jhb300/re_gnnboundary.

Published in Transactions on Machine Learning Research (06/2025)
[RE] GNNBoundary: Finding Boundaries and Going Beyond Them
Jan Henrik Bertrand University of Amsterdam
Lukas Bierling" University of Amsleriam
lukas. Setoss.beerknn@@ssdddedl......
Ina Klaric University of Amsteriam
Tho.klaaricosstudent..u...
Aron Wezenberg
aron.wcczebbrrg. wwwpre/gg...eeeeereeeeeeuuuuuu..
University of Amsteriam
Reviewed on OpenReview: https: // openreview. net/ forum? id= XSgCOIMQDO
Abstract
Graph classification models becoming increasingly popular, while explainability methods face challenges due to the discrete nature of graphs and other factors. However, investigating model decision making, such as through decision- boundaryy regions, helps prevent misclas- sifications and improve model robustness. This study aims to reproduce the findings of GNNBoundary: Towards Exploining Graph Neural Networks Through the Lens of Decision Boundories (Wang & Shen (0244). Their work supports main claims: (1) their proposed algorithu can identify adjacent class pairs reliably, (2) their GNNBoundary can effectively and consistently generate near-boundary graphs outperforming the cross- cots-ey baseline, and (3) the generated near-boundary graphs can be used to accurately assess key prop- erties of the decision boundary; margin, thicknoss, and complexity. We reproduced the experiments on the same datasets and extended them to two additional real-world datasets. Beyond that, we test different boundary probability ranges and their effect on decision boundary metrics, develop an additional bascline, and perform hyperparameter tuning. We confirm the first claim regarding the adjacency discovery as well as the second claim that GNNBoundary outperforms the cross-entropy baseline under the limitation that it requires intensive hyperparameter tuning for convergence. The third claim is partially accepted as we observe a high variance between the reported and obtained results, proving the reli- ability and precision of the boundary statistics. Code and instructions are available at: rata:000/rrggnouuurrrr gunboundary
1 Introduction
Reproducibility is the backbone of scientific progress, ensuring that findings are robust, reliable, and gen- cralizable. In that, model explainability methods are often used by rescarchers to assess and improve the robustness of model. This study focuses on GNNBoundary by Wang & Shen a framework designed analyze decision boundaries in graph neural networks (GNN) [Scarselli et al., 2209),, more specifically in GNN-based classifiers. Understanding decision boundaries crucial for evaluating model robustness, as well identifying and understanding modes of failure. This is especially important for real-world applications in
Equal contribution.

---

Published in Transactions on Machine Learning Research (06/2025)
domains such as social networks, biology, and recommendation systems Fan et al, 2023 tivation behind this work lies in the originality of the approach: to the best of our knowledge, GNNBoundary represents the first method specifically aimed at investigating decision boundaries in GNNs, Furthermore, previous reproducibility efforts concerning its methodological predecessor, GNNInterpreter (Vasilcoiu et al. 2024), revealed that several key results could not be replicated. This underscores the importance of thor- oughly validating GNNBoundary's findings through dedicated reproducibility study.
The primary mo-
GNNs have shown remarkable performance in tasks that involve graph data, such as node classification, link prediction, and graph classification (Errica et al. 2020). Despite their widespread utilization, the complexity of these models often leads to challenges in understanding their decision-making. GNNBoundary, as a post hoc method, attempts to open this black-box by investigating decision boundaries with quantitative metrics and visualizing sear-boundary graphs for adjacent class pairs. In doing so, the method offers insight into how GNNs distinguish between classes and the robustness of the classification.
This reprodueibility study aims to verify the results and claims made in the original GNNBoundary paper by Wang & Shen (2024). Specifically, this study attempts to determine whether the GNNBoundary framework can be used to consistently and reliably generate near-bounden graphs and collect boundary metrics for the discovered adjacent class pairs. This involves reproducing the authors' experiments, verifying the correctness of the implementation, and evaluating the robustness of the findings across four datasets. Motif (Wang &
Shen 2023 ), Collab (Yanardag Vishwanathan (2015) Enzymes (Schomburg et al. (2004)) and IMDB
Yanardag & Vishwanathan (2015)).
Beyond reproducing the results from Wang & Shen 2024 using their instructions, our objective is to enhance the applicability of GNNBoundary to practitioners and rescarchers by providing additional guidance. Moreover, provide insights the generalizability and robustness of the method through additional experiments and analyses.
2 Reproducibility Considerations
To guide our efforts, the claims and contributions defined in this section will carry through the following sections. The main claims made by the authors are as follows:
Main Claims:
1. Their proposed algorithm for identifying adjacent class pairs can reliably identify the degree of adjacency of a class pair.
2. GNNBoundary can effectively and consistently generate near-boundary graphs with faster conver- gence and a higher success rate than the cross-cntropy bascline.
3. The generated hear-boundans graphs can be used to accurately assess key properties of the decision boundary: margin, thickness, and complexity.
Our main contributions beyond the reproduction of the results from Wang & Shen 22024 are:
Contributions:
Performing hyperparameter optimization to systematically analyze the impact of different configu- rations on convergence behavior, leading to faster and more stable model training.
2. Developing an additional baseline by using over 500 GNNInterpreter graphs (Wang & Shen 2023) per class in each dataset and connecting them via randomly assigned edges.
Extending experiments with two real-world datascts: posts from the forum site Roddit and a rela- tional graph dataset IMDB, with actors and actresses connected by co-appearances in movies.
4. Investigating the trade-off between boundary metric approximation quality and target class proba- bility ranges (e.g., [0.49. 0.51), [0.45, 0.55)), offering practical insights into the training requirements for near-boundary graph sampling.
2

---

Published in Transactions on Machine Learning Research (06/2025)
3 Background
3.1 Graph Neural networks
An increasing amount of graph structured data creates a need for a graph structure learning systems. Graph Neural Networks (GNNs) emerge from its predecessors in deep learning as models to operate on graph structures. Graphs have unique characteristics that differentiate them from other data types, such as a variable number of nodes and edges across graphs. This variability complicates the application of convolutions. Moreover, unlike images or lext, where individual data instances are typically independent, graphs exhibit inherent dependencies, nodes can be interconnected and therefore influence each other (Wul et al. 2020). GNNs are networks that aim to create representation vector of a node or a whole graph given the features of the node and the graph structure (Xu et al., 2019). The higher need for graph analysis and the emergence of various GNNs such as Graph Convolutional Networks (Kipf & Welling, 2017) and Graph Attention Networks (Veličković et al. 2018 create the need for explainability and interpretability in the
GNN domain.
3.2
Explainability of GNNs
In a review of explainability approaches to GNNs by Kakkad et al.] the explanation is described as either self- interpretability or post-hoc explainability methods. The former enables the model to justify its predictions during training and influence it, while the latter considers the training as black-box process that is be explained post-training. GNNBoundary is a post-hoc explainability method. It examines the decision boundaries of trained GNN by learning to generate graphs near the boundary. The final distinction in the review is between instance-level and model-level explainability. Instance-level explainability aims to explain predictions of a certain instance, while the model-level method aims to justify the high-level decision- making process of the whole model. GNNBoundrr considered model-level method as the generation of near-boundary graphs aims to explain global patterns the decision process of a GNN classifier. Tn literature previous to GNNBoundary, gencration-based methods do not yet explore the docision boundaries. However some methods explore the model-level behavior by generating graphs represenlative of class, such GNNInterpreter (Wang & Shen 2023 and XGNN (Yuan et al. 2020
3.3 Decision region and boundary
A classifier partitions the d-dimensional space Rd into C decision regions R1, R2, ... Re, such that for any E Re, the predicted class is argmarzffa() where k E [] (Krimi et al. 2019 The decision boundary between class and class 02 is defined as Beglle2 {G Jc, (G) Scg (G) (G), Vc' + c1,02), representing the set of graphs G where the classifier assigns equal probability to classes C1 and C22 while ranking them higher than all other classos. For the embodding space, Wang & Shen (GNNBoundary) define
B e le
( (H =n(n(H > on (H (H) )e, * #c,02)
(1)
where a is the Softmax activation function and mn are the last L / layers of the discriminator f that output the logits for graph embedding (() after layer I. In other words, the decision boundary represents the points in Rd where the classifier is "uncertain' about assigning a label between classes 0₁ and c2.
4 GNNBoundary
Wang & Shen (0024) propose an adjacency finding algorithm, an objective function to generate near- boundary graphs for adjacent class pairs and a dynamic regularization scheduler to avoid local minima.
Notation. A graph is represented as G = (V,8), where V = {ii, U,,..,, is the set of nodes and E C V x V is the set of edges. The total number of nodes is denoted by N, and the total number of odges denoted by M. The adjacency relationships between nodes are captured by the adjacency matrix A {0, 13 where an entry ay indicates the presence of an edge between node v and node By, while ai = 0 indicates the absence of edge. Node features are stored in the feature matrix Z NNxx where
3

---

Published in Transactions on Machine Learning Research (06/2025)
2, Id represents the feature vector of node v, and therefore the i-th row of Z Each class is associated with a decision region Re, which represents the set of points in the feature space that the classifier assigns to class c.
4.1 Adjacency Discovery
Running the boundary analysis for all class pairs would be computationally prohibitive. Hence, Wang & Shen propose an adjacency discovery method that calculates adjacency rates based on the dataset and all but the last layer of discriminator model f denoted as embedding function 7)r.-1- This comes with the advantage that the embedding space after the last hidden layer has linear decision boundaries. The algorithm samples graphs G.,, E R., and Gez E Ray, embeds them using 7/.-1 obtaining ((-")) and H (!--1) respectively. They then interpolate between H!!-1) and H the embedding space and use the remaining layer of the discriminator to determine if the interpolated embedding is part of any intermediate decision region other than Ra, or Rey. The final adjacency score is the share of the K sampled graph pairs that do not cross any decision region other than Re, or Roy.
4.2 Graph Generation
GNNBoundary Sampling. As discrete structures, graphs are not inherently differentiable. However, Wang & Shen propose a relaxation approach to mitigate this issue. The discrete graph structure is relaxed into a differentiable form allowing gradient-based optimization, using the reparameterization trick inspired by Jang et al.] (2017), Wang & Shen (023) and Luo et al. (2020). The boundary graphs are modeled as Gilbert random graphs (Gilbert, 1959, where the probability distribution of the graph P(G) is formulated as the product of node leature probabilities P(z:) and edge probabilities P(asy)- Edges are sampled from a Bernoulli distribution, while node features follow a Categorical distribution. To enable gradient-based learn- ing, the categorical variables are relaxed using the Concrete distribution (Maddison et al.) 2017). leading to a differentiable approximation. The concrete distribution is a contimuous version of the Categorical distri- bution with closed-form density, & ~ Concrete((E, -=) for the node features ūij ~ BBnaryy CanaarCCnncete((x Ta) for edges, where T3 and Ta are hyperparameters to control the approximation of Categorical distribution, Wiy E Ω and & E Z. Z and Z denole the set of all edge and node feature logits, respectively, represented matrices in practice. For sampling, the authors of GNNBoundary (Wang & Shen 2024) utilize the Gumbel- Softmax trick (Jang et al.] 2017), which ensures that both the edge variables and node feature variables remain disferentiable. This is achieved by computing edge variables ā.j and node feature variables & using the transformations ā. = Sigmoid ((wig + log e log(1 - e))/Ta) and , = Softmax((S: - log(- log r))/TT)) Furthermore, the graph distribution is learned by minimizing the expected loss function through Monte Carlo sampling and gradient descent, making the boundary graph generation process efficient for discrete graph structures, and as follows:
min L(G) A,
min Ea-P(n) [C(A, Z)] min B, [C(A, = min e.P
Σ C(A, ZZ K
1
(2)
n.Z
where A and Z denote the adjacency matrix and node feature matrix of the graph. We point out that this sampling framework builds on a strong independence assumption. Specifically, the probability distributions for the edges, nodes and node features are all independent of each other in this framework. While this assumption is needed to make the sampling computationally tractable, it yields a potentially inaccurate model of the graph sampling space. Future research could work on ways to mitigate this issue.
Boundary Criterion. To generate boundary graphs, the probability of a boundary graph belonging to both classes should be equal, i.e. GeIlez E Bailez with (J(G)), = of(()),, 0.5. As this is usually unattainable in practice, the authors propose relaxed class probability range that the boundary graphs are permitted to belong to. Thus, the stopping criterion for the optimization that determines whether a graph G is close enough to the boundary Be, Beille llez is defined as:
(G) = bpte
(3)
The authors suggest using Pmin = 0.45 and Pmaa = 0.55. Due to this relaxation, the term hoan-boundary graph' is more accurate than "boundary graph" and will be used in the following sections.
4

---

Published in Transactions on Machine Learning Research (06/2025)
Optimization. To generate near-bounarry graphs, the optimization objective must be designed to balance the trade-off between boundary classes while ensuring efficiency. A key limitation of using the cross-entropy loss as an objective function is its inability to fully satisfy the required constraints for near-boundary graph generation, as still may lead to the minimization one of the logit values of the boundary classes. This does not. serve the goal of producing near-boundary graphs that have features of both adjacent classes. An improved objective function is proposed that encourages posterior probabilities for boundary classes, p(ci) p(c2) 0.5, while minimizing unwanted class probabilities, V' & C2). Additionally, a squared penalty is introduced that penalizes logit values that differ from the target class probability vector. This optimization technique is essentially an "enhanced" cross-entropy that encourages higher probabilities for both adjacent classes and penalizes deviated logits. Formally,
min [(G) = min E (C
Bf(G)v p²(0)²-
af(GG, (1- (1)p" 1p (0000)ccmmx.ee.o0p0 (4) (E(0).0)
Σ
where f(G),, and (( are logits of the function f(G) of the two adjacent classes, (c(() is the detached version, or no gradient version, of the posterior probability p(c) = o((())) and a and B are constant hyperparameters.
Regularization. To encourage the interpretability of the generated graphs to be as succinct as possible, Wang & Shen impose a budget penalty limit the size of the explanation graph in terms of the number of nodes and edges. Concretely, they propose the use of L1 and L2 regularization:
Rbudget = Softplus ([)i) =B)²
with B being the expected maximum number of nodes in a boundary graph G. This regularization penalizes the model when the expected number of edges, computed from the relaxed adjacency matrix, exceeds a predefined budget. Given that certain patterns require certain graph sizes, a size penalty is a potential problem for convergence. Hence, the authors propose a dynamic scheduling method within the training procedure that adapts the budget penalty. To not hinder convergence, a smaller penalty is applied on graphs further away from the decision boundary and bigger penalty on graphs closer to the decision boundary. The budget penalty weight is defined as,
(t-1) H(())))) 1 MA 1) budget
budget budggee) }
2
w budget =
Sine
Sec
(6)
where budget is a hyperparameter for the initial weight, Sine is for weight increment, sdec is for weight decrement and Gt [G~P(C] for an optimization iteration The dynamic regularization can help convergence by permitting the budget penalty interfere with the main loss function.
(0)
4.3 Boundary Analysis
Margin. The boundary margin quantifies the minimum separation between decision regions in a graph classification model (Yang et al.) 2020). Unlike classical margin definitions, which are based on worst- case distances, Wang & Shen (2024) use class representative graphs (also denoted as Ge, in the following) generated using the GNNInterpreter framework (Wang Shen, (023). Given datasct D, a classification function f, and graph representations Go and le2 belonging to different decision regions, the boundary margin is defined as:
min @ (2) (Gey (oe)
[lor(Go,) - (G
(7)
where Go E RR, and Gorllez E B,, represent graph samples from class e₁ and its nearest. boundary region with class 02, respectively. The function (G) denotes the graph embedding function extracted from classifier f, mapping the input graphs into a learned fcature space. A larger margin implics better class soparation, contributing to model robustness, while a smaller margin suggests higher decision boundary instability, increasing the risk of misclassification YYngg et al. 2020
5

---

Published in Transactions on Machine Learning Research (06/2025)
Thickness. Boundary thickness is metric that quantifies the width of decision boundary. Given classification function f, the asymmetric boundary thickness @(S c, 02) is defined as the expected distance between pairs of graphs Go, and Garle sampled from a distribution P, weighted by the fraction of a continuous interpolation between these graphs where the posterior difference satisfies a margin condition. Formally, this expressed as:
0(, Geglle [|o(GG) @i (ea))
-o -o L/ (
(k(t)) (k((()))))
dt
(8)
where h(t) (1-t)- +t +t- defines an interpolation between the boundary graph embedding Or(G,, llea) and class graph embedding (n 7y is a threshold parameter that defines a margin condition for evaluating the boundary thickness, it is set at 0.75 to capture high uncertainty regions. Boundary thickness captures the average width of the decision boundary. If the decision boundary has a low width and thus separates the data well, the integral in eq. (8) will become small number. Hence, low boundary thickness corresponds to low graph density around the decision boundary and with that good separation of the data.
Complexity. The boundary complexity measure calculates the structural complexity of classifier's de- cision boundary by analyzing the distribution of adversarial examples in feature space. Using Principal Component Analysis (PCA), the spread of adversarial examples is captured through the eigenvalues À of their covariance matrix (Guan & Loew (2020)). A simpler decision boundary results in adversarial exam- plcs aligning along single eigenvector, whereas more complex boundary distributes them across multiple eigenvectors. This complexily is computed as the Shannon entropy of the normalized eigenvalues:
[|ll ((A))) log
(
--
A log All
d ||IlI )
N
T(f.c1,02)
/ log D.
(9)
Here, A= (A1, An) represents the eigenvalues of the covariance matrix of the adversarial set, and ||||| is the sum of all cigenvalues, ensuring normalized representation. The entropy function H (-) measures how evenly variance is distributed across eigenvectors, and D denotes the dimensionality of the feature space, normalizing the complexity measure to the range [0, 1]. A higher complexity indicates a more uneven decision boundary, implying greater sensitivity to perturbations and risk of over-fitting On the other hand, a lower complexity score suggests smoother boundary, which is more likely to generalize well unseen data.
5 Experimental Setup
In addition reproducing the results from Wang Shen (2024), in order confirm the validity and robust- ness of the described methods, we aim convey an empirically-driven intuition behind the GNNBoundary and to make it more accessible to practitioners and rescarchers. To reproduce the results, we utilized the authors' publicly available code repository]] However, several critical components were absent in the original implementation, as detailed in Appendix [ We implement the missing parts and make it public as linked in the abstract.
5.1 Adjacency Discovery
To verify claim I we run the algorithm for identifying adjacent class pairs proposed by Wang & Shen for all datasets. To further verify the resulting adjacency scores, we analyze the mcasurod success rates for near-boundary graph generation on the adjacent class pairs as well as on a selection of non-adjacent class pairs. High success rates would generally be expected on adjacent class pairs and low success rates would be expected on non-adjacent class pairs.
The authors' GitHub repository can be accessed at: http://hhbbb.ooo/ooollaaaaaaaaaa CaNaaaaallllla/NNauuuuuarraraa 2Th success denotes the proportion of 1,000 runs that successhully generated houndary graph within 500 iterations and within the target range of [0.45, 0.55).

---

Published in Transactions on Machine Learning Research (06/2025)
5.2 Datasets
The GNNBoundary method was originally evaluated on three datasets: Motif, Collab, and Enzymes, with the latter two being real-world graph datasets. The synthetic Motif dataset, introduced in Wang & Shen (2023), consists of graphs labeled with one of four predefined motifs: House, HouseX, Comp4, and Comp5. The Collab dataset comprises ego-networks of scientific collaboration, representing co-authorship networks in the fields of High Energy Physics (HF), Condensed Matter Physics (CM), and Astrophysics (Astro) Yanardag & Vishwanathan (2015). The Enzymes dataset Schomburg al. (2004) consists tertiary-structured proteins classified into one of six enzyme classes.
Given that only 3 datasets are used in Wang & Shen (2024), we further assess the method's performance in real-world settings, using two additional real-world datasets: IMDB and Reddit-Mulitclas. The IMDB dataset consists of 1,500 graphs, where nodes represent actors and actresses. An edge is formed bet two nodes if the corresponding individuals appeared in the same movie. Each graph is categorized into one of three genres: Comedy, Romance, or Sci-Fi. The Reddit datasct contains 232,965 posts collected from the social media platform Reddit. Each graph instance represents subreddit. communityy, where nodes correspond to posts, and edges indicate that user commented on both posts. The dataset includes five class labels corresponding to different subreddits: worldnews, videos (general video-sharing), Advice (humorous advice posts featuring animals), Auw (cute content), and Mildlginteresting. This dataset contains larger graphs compared to the other datasets (ef. table 5 to test the scalability of the method.
5.3 Hyperparameters
Wang & Shen report one set of hyperparameters for all datasets. Moreover, it is missing configurations for the dynamic regularization scheduler as well as the graph target size. Consoquently, we ran Bayesian Optimization Shahriari et al. (2015) to find the optimal hyperparameter configuration for each dataset. The search space consists of the sample size K, the target size, the target probabilities, the learning rate, the temperature, and the weight budget increase for the dynamic regularization schoduler and the weight budget decrease. Details on the scarch space are given in appendix H Moreover, we employed a simple custom loss for the hyperparameter tuning, being the average deviation of the class probabilities from the target 0.5:
1 Σ Nep
0.5| + pp(eg)) 0.5l
C(CP)
2
where Nep is the number of class pairs in adjacent class-pair set CP and o & o are class one and two of a class pair respectively. We chose this simple criterion instead of GNNBoundrriss dynamic boundary criterion to be independent of the tested method as well as for simplicity and thus casier interpretability.
5.4 Baselines
Wang & Shen propose a random baseline that generates boundary graphs using a graph from ei and a graph from 62 and combines them with a random edge.
Dataset-based Graph Sampling. In the absence of prior methods for analyzing the decision boundary of GNN-based classifiers, the authors proposed a simple baseline that samples a graph from the dataset for each class in the class pair and connects them with randomly assigned edge to obtain graph that is theoretically representative of both classes. Thus, it is expected to activate the classifier's probability distributions maximally for these two classes. Our reproduction of this baseline corroborates the authors' findings, demonstrating that this approach frequently fails to produce near-boundary graphs, as the randomly sampled graph structures often lack the properties needed to clicit near-boundary probability activations.
GNNNnterpreter- based Graph Sampling. To address the limitations of the random sampling base- line, we devisod a novel bascline leveraging GNNInterpreter (Wang & Shen 2023). Specifically, we generate clas-rrprrsenttatie graphs using GNNInterproter and connect them with a random edge. Since GNNInter- preter optimizes these graphs to maximize their respective class activations unlike dataset-sampled graphs,
7

---

Published in Transactions on Machine Learning Research (06/2025)
which may not lie in the decision region we hypothesize that combining two such graphs preserves and integrates class-specific features. Through GNN message passing, this aggregation is expected to enhance the activation of both classes more effectively than dataset-sampled graphs, as it reinforces decision-relevant features optimized for class activation. One limitation is that it introduces significant complexity due to the hyperparameter luming required for GNNnnterpreter (e.g. generating hundreds of graphs per class). These challenges render the GNNInterpreter--bsed bascline infeasible in settings where finding clas--representative graphs (e.g. using GNNInterpreter) is not needed anyways.
5.5 Boundary Embedding Discovery
The stochastic nature of GNNBounary's graph generation process raises the question how the distribu- tion of these generated graphs is structured embedding space (i.c., after applying the graph embedding function (G)). A robust generation process should produce embeddings that are broadly distributed yet concentrated around meaningful decision boundaries, ensuring that generated graphs effectively capture diverse but class-relevant featurcs. To challenge the boundary emboddings proposed by the authors, we implement method that randomly initializes an embedding and iteratively optimizes it toward a point in embedding space where the discriminator assigns a probability within the target range of [0.45, 0.55) for the corresponding class pairs. This approach allows us to probe the structure of the decision boundary and assess whether GNNBoundary embeddings naturally align with it or require extensive optimization. The primary goal is to analyze how the distribution of embeddings would appear if directly optimized in embedding space, particularly after visualizing its 2D representation using UMAP (Mclnnes et al. 2018) and PCA (Jolliffe, 2002). Formally, with yJr. being the last layer of discriminator function ʃ that assigns probability to a given embedding, let z be an embedding, which does not necessarily have to correspond to an actual valid graph. We seek a mear-boudarry embodding z" that satisfies zt = arg min, LCE (T), Cross-Entropy loss and y" is the target vector of shape C. Suppose, we want to find a boundary embedding for class i and j, then y = Vj = 0.5 and y = Yk: & i. The optimization is performed over an initially random embedding z cover most near-boundary regions in the embedding space. Note that this is only to find near-boundary points in the embedding space for the purpose of visualization and hence there is no need for z" to be the embedding of a valid graph.
where LCE is the
5.6 Boundary Statistics under Different Target Probability Ranges
The accuracy of boundary metric approximations depends on both the quantity and quality of near-boundary graphs. The quality refers to how close these graphs are to the boundary (defined as having probability of 0.5 for Ci and o2). To investigate this, we evaluate the boundary statistics (complexity, margin and thickness) for different target probability ranges. We analyze how these statistics deviate from the proposed larget range of [0.45, 0.55), providing insight into the consistency and reliability of the suggested range. If the statistics remain stable across small shifts in the target range, it suggests that [0.45, 0.55] is a reliable approximation of the actual docision boundary. In contrast, large variations in these statistics when adjusting the target range would indicate that our chosen range may poorly represent the true boundary, highlighting potential need for adjustment.
6 Results& & Discussion
To verify the stated claims and 3 extensions described in section report the results and discuss them in this section.
we reproduce all experiments from Wang Shen (2024) as well as the
6.1 Reproduction of Results
Before contributing additional insights on the optimized hyperparameters, new real-world datasets, the new bascline and the boundary statistics, we attempt to reproduce the results from Wang Shen (2024) as good as possible under their reported configurations (refer table in appendix H for an overview of the authors'
hyperparameters) Since some hyperparameters are not explicitly stated in Wang & Shen (2024) we infer
8

---

Published in Transactions on Machine Learning Research (06/2025)
the values and ranges from the demo notebooks provided in the authors' code base: initial weight budget 1, the weight increase as 1.15, the decrease as 0.95, and the target size as 30.
Boundary Graph Generation. When comparing our table | with table 1 in Wang & Shen (2024), we observe that we were mostly able to obtain very similar results when it comes to the ability of GNNBoundary to generate near-boundary graphs with both class-probabilities being close to 0.5. An exception of this are the first. four class-pairs of the Enzymes dataset which did not converge under the target probability range of Pmin 0.45 and Pmoz= 0.55. We hypothesize this discrepancy between our and the authors' results to be caused by subpar hyperparameter settings, slight differences in discriminator performance (cf. appendix E and figure 3 in Wang & Shen (2024)) and to some extend random variation. In terms of complexity, we mostly observe higher values, i.c. greater sensitivity to perturbations and overfitting, thus worse generalization to unseen graphs. As we reproduce their random baseline, we observe different values, but a similarly strong discrepancy between the class- hass-probabilitiee and the targeted 0.5 probability as well as high standard dcviations. Despite the small discrepancy regarding the Enzymes datasct, we can mostly confirm the results from Wang & Shen regarding the class-pair probabilities of GNNBoundary boundary graphs. We confirm the superiority of GNNBoundary over the random baseline without limitations.
Our proposed baseline, which leverages GNNunteppreter-bae random bascline suggested by Wang & Shen (024)). The resulting class probabilities for our baseline are reported in Table | Along with the challenging hyperparameter tuning required for GNNInterpreter, these results highlight the need for more effective baselines for generating boundayyy graphs.
graph sampling, did not outperform the
Finding Adjacent Class Pairs. We repro- duce the results for the Collab, Motif and En- zymes datasets using their provided code and ob- serve insignificant differences in adjacency scores (appendix B}. As layed out in section 5.1 we also analyze the correlation between the adjacency score and the corresponding GNNBoundary success rate to verify the author's ' proposed adjacency discovery algorithm. Figure[]depicts the measurements of the adjacency score and the GNNBoundary success rate for class pairs across datasets. Class pairs that were determined to be adjacent by |Wang & Shen are de- picted in blue, while a selection of non-adjacent class pairs is plotted in orange. The adjacency score used for fig. [ is the one we obtained from the author's adjacency discovery algorithm.
1,0
Adjacent
Non-adfaoitt
GNNBoundary Success Rate
Regression Line
0.8
0.4
0.0
0.2
0.4
0.8 0.8
1.0
Adjacency Score
Figure 1: Comparison of success rate to adjacency score for all adjacent class pairs obtained using their adjacency finding algorithm (Collab, Motif and En- zymes datasets). Success rates are measured under op- timized hyperparameters we obtained from HPO (cf. section 6.2 Adjacent means that the GNNBoundary author's ' reported these adjacent.
As expected, we can see clear correlation between the adjacency score and success rate, indicating that the obtained adjacency score is good proxy for ad- jacency. To further quantify these results, we cal- culate the Pearson correlation coefficient and deter- mine if the slope coefficient is statistically significant under a 95% confidence level. The Pearson correlation cocfficient is 0.6 and the v-vauue 0.0139. Hence, there is a clear positive correlation and the regression is statistically significant under set confidence level.
Given the clear positive correlation and statistical significance, we accept claim 1
Success Rate in Boundary Graph Generation. Under the authors' hyperparameter settings we cannot confirm the high reported success rates from Wang & Shen (2024) as well as we cannot confirm GNNBoundary consistently outperforming the cross-entropy baseline (cf. table 2 under their hyperparam- eter scttings. When using our hyperparameter scttings, we obtain success rates much closer the authors' ones and consistent superiority over cross-entropy for the Motif and Collab dataset (cf. table 3). For Enzymes we again struggle to confirm their results even with optimized hyperparameters.
9

---

Published in Transactions on Machine Learning Research (06/2025)
Table 1: Comparison of GNNBoundary and baseline near-boundary graph probabilities across datasets. We report the mean class probability among 500 boundary graphs and the corresponding standard deviation. No results were obtained for the Reddit dataset and convergence could not be reached for the "Romance-SciFFi"
class pair (view section 6.3 for more details). Probabilities closcr to 0.5 better.
GNNBounday
Random Baseline
Dataset
C1
Complexity
p(c1)
p(c2)
p(c1)
p(c2)
House
HouseX
0.02
0.51 0.03
0.49 + 0.03
0.72 0.26 0.06 0.15
Motif
House
Comp4
0.07
0.51 + 0.03
0.49 + 0.03
0.59 + 0.31 0.38 + 0.32
HouseX
Comp5
0.23
0.51 + 0.06
0.49 + 0.06
0.89 +: 0.26 0.00 1 0.02
HE
CM
0.31
0.48 + 0.02
0.48 + 0.02
0.31 + 0.44 0.00 + 0.00
Collab
HE
Astro
0.25
0.50 0.03
0.49 0.03
0.05 + 0.20 0.95 + 0.20
EC1
EC4
0.20
0.44 + 0.03
0.43 + 0.02
0.19 + 0.32 0.30 + 0.43
EC1
EC5
0.11
0.43 1 0.02
0.51 1 0.01
0.20 1 0.30 0.20 1 0.33
EC1
EC6
0.21
0.44 0.02
0.23 0.32 0.01 0.07
Enzymes
EC2
EC3
0.32
0.45 1 0.04
0.46 0.05
0.13 1 0.29
0.37 1 0.41
EC4
BC5
0.13
0.49 0.04
0.49 0.04
0.30 = 0.43
0.20 + 0.33
EC4
EC6
0.36
0.46 0.04 0.45 - 0.04
0.33 + 0.38
0.05 1 0.17
Comedy
Romance
0.03
0.46 + 0.01
0.46 + 0.01
0.30 + 0.14
0.11 + 0.20
IMDB
Comedy
Sci-Fi
0.27
0.50 + 0.03
0.50 0.03
0.30 + 0.13
0.62 0.16
Romance
Sci-Fi
To summarriee we confirm the ability of GNNBoundary to find faithful near-boundans graphs and its superiority over the random baseline. However we cannot confirm their high convergence rales. Under this limilation, we still consider cloim 2 to be volid.
Boundary Statistics Analysis. Based on the case study provided in section 5.3 of Wang & Shen (0224)
we implement the boundary margin, boundary thickness and boundary complexity metrics and reproduce the results for their three datasets and report them in appendix E We generally observe significantly higher values for the boundary thickness, which corresponds to a comparatively high probability density graphs on the boundary as opposed to the class regions. This can be interpreted as worse separability. For Motif, the margins are comparable for about half of the class combinations and significantly higher for the remaining half. Given that higher margins indicate better class-separability and with that better robustness, our results for Motif are even better than the ones reported by Wang & Shen, For Collab, we observe mostly lower margins, i.c. worse separability and robustness when compared to the authors results and for Enzymes we also observe mostly mixed results compared to the authors reports, where some are higher and other are lower without a clear tendency. In general, there are significant discrepancies between our results and the author's results, which makes us question the reliability and precision of the employod boundary statistics. Based on our observations, the boundary structure. Beyond that, hypothesize the worse separability exhibited by lower margin and higher thickness to be connected to a slightly worse classification performance compared to the authors (cf. the confusion matrix in appendix E to figure 3 in Wang & Shen (2024)). This is despite the fact that we used the authors' provided discriminator model checkpoints.
would rather see these statistics
approximate low-precision indicator of
In the light of these findings, we accept claim 5 only wnder the strong limitation that the boundary statistics cannot be considered reliable precise given their significont discrepancies under small changes of discriminator accuracy.
While we are mostly able confirm the results from Wang Shen (2024) on the Motif and Collab datascts, we face challenges in reproducing the results for the Enzymes dataset throughout all experiments. [aan & Shen also observe class pair probabilities closer to the edges of the [0.45, 0.55) range, lower success rates
10

---

Published in Transactions on Machine Learning Research (06/2025)
and higher boundary thickness for the Enzymes dataset in comparison to the other datasets. However, we cannot reach their results, not even under optimized hyperparameters (cf. table] 1 table 3 appendix F.. We hypothesize this to be connected to the high complexity of the dataset given the higher number of classes and worse classifier performance. This highlights the methods dependency on classifier performance and its limitations when it comes to more complex datasets. Our attempls to improve the performance for the Enzymes classifier or to use a different model architecture to enhance classifier performance did not succeed.
6.2 Hyperparameters
Among the hyperparameters that were reported by the authors tuned the target probability range, the learning rate and the temperature. As can be seen in table [ in appendix H. the discovered optimal configurations are highly dependent on the dataset and mostly deviate significantly from the author's reported configuration. This highlights the need for dataset specific reporting of hyperparamcters and offers an explanation for the large discrepancy (2024). Notably, the optimal values for temperature and learning rate can mostly be found at the boundaries of our tuning ranges designed around the values provided by the authors, which highlights that the optimal configurations are far from the values reported by Wang & Shen These results are expected given that different datasels come with different optimization landscapes that require appropriate hyperparamelers. For instance, an optimization landscape with a higher number of local minima usually requires a higher lcarning rate to enable global convergence.
convergence between our table 2 and table 2 in [Wann Shen
6.3 New Datasets
We find that GNNBoumdary works mostly well for IMDB, while it is not possible to run it in a reasonable amount of time for the Roddit dataset.
IMDB Dataset. We obtain fast and stable convergence for boundary graphs in class pairs 'Comedy- Romance" and "Comedy-SeiFi", while we could not achieve convergence for class pair 'Romanco-SciFi" The same goes for GNNInterpreter training: we obtain good results for classes "Comedy" and "SciFi', but not for 'Romance'. We observe that the boundary graphs for 'Romance-SeiFi" are very sparsely connected (ef. appendix F.1) and usually even contain several disconnected graphs. This is inherently problematic given that GNNs are based on message-passing and thus likely the reason for the described convergence issues.
Reddit Dataset. For training the boundary graph sampler, we increased the maximum number of nodes 3 to 550, which is slightly above the average graph size 508 nodes (cf. table 5 to make convergence more likely. However, such large graph has up to m(n-1) undirected edges, which for 550 nodes would be 2
from 25
up to 150.975 edges. Hence, the time and memory complexity of GNNBoundary is O(n²) w.r.t. to the number of nodes n, lcading to training times of around 330 minutes for a single boundary graph sampler on an Apple M3 chip. HPO and generating 500 boundary graphs to compute the boundary statistics was hence not possible under the resource roints of this work. Thus, we cannot report results for this dataset.
6.4 Random Baseline for Boundary Graph Class-Probabilities
Comparing lable 1 and lable q we cannot observe that the baseline based on dataset graphs has class probabilities closer to 0.5 than the one based on GNNInterpreter graphs: on average 35.7% for p(ci) and 23.1% for p(c2) when using datasct class graphs whereas the average probabilities for GNNInterpreter-bascd class graphs are 37.3% for p(c2) and 20.0% for p(c2). The variances of the class probabilities across the CNNInterpreter- and dataset-based baselines are also comparable. We also investigated using 2, 3 and 5 random edges but did not observe significant changes in the results and hence omit further details on this.
We used maximum number of nodes of 25 per graph the other datasets.
11

---

Published in Transactions on Machine Learning Research (06/2025)
6.5 Robustness of Boundary Detection
As described in section 5.5 we allempl to inspect the classifier embbeddng space by plotting the 2D UMAP and PCA of each adjacent class pair, the corresponding GNNBoundary near-boundary graphs and the near- boundary embeddings discovered by our cross-entropy based method described in section [_5] The visual results of our analysis can be found in appendix J In general, we found that GNNBoundary graphs form a larger structure throughout the embedding space, while our boundary embeddings are concentrated in one location (see herefore fig. [ and fig. [). This is due to the fact that our cross-entropy based method optimizes for probabilities under the use of a Softmax instead of the logits. Given that the logits are unbounded, our method always resorts to the same minimum for which the difference in magnitude of the logits enable the desired probability distribution. In contrast, GNNBoundary graph embeddings circumvent this limitation, spreading across a broader structure in latent space, demonstrating its robustness and ability to generate a diverse range of meaningful boundary graphs. Given that direct optimization in embedding space did not yield high variability, we emphasize the significant achievement of GNNBoundary in generating graphs that effectively traverse constrained regions without requiring direct optimization in embedding space,
We note that PCA is not beallty-preserving Hence, the fact. that the boundary graphs do not appear in- between the classes the plot does not necessarily correspond to the actual proximity in high-dimensionall latent space. Consequently, this empirical study might give an intuition for the distribution of embeddings in latent space, but it cannot be used to argue about the precise location of the found boundary graphs in that latent space.
6.6 Boundary Statistics under Different Target Probability Ranges
To validate the [0.45, 0.55] target range [Pmin Pmma), we analyzed boundary statistics (thickness, margin, complexity) across multiple ranges from [0.43, 0.57] to [0.495, 0.505] (appendix Kj. This assessment verifies whether the range proposed by Wann & Shen (024) reliably captures near-boundary graph properties.
Overall, the [0.45, range offers a reasonable trade-off for boundary graph generation. While some deviations-cspociinn
for narrower ranges like [0.495, 0.505]-are more pronounced due to the stochastic nature of graph sampling, most statistics remain consistent around this interval. For example, boundary thickness for House- Comp4 in Motif is stable, whereas Collab shows expected variations near the boundary. Notably, boundary margin deviations in the Enzymes dataset are less stable, likely because Enzymes is generally harder to optimize. As a result, the generated boundary graphs in Enzymes tend to be more dispersed embedding space, leading to fluctuating margin values across different larget ranges. Hence, this variation is not a drawback of the chosen target range but rather of the general instability of the boundary graph generation for the Enzymes datasct (sce table [ for success rates of graph generation for Enzymes). Despite these fluctuations, the [0.45, 0.55) range presents a solid compromise: it is wide enough to ensure a sufficient number of near-boundary graphs for analysis, while still preserving meaningful class distinctions. Therefore, we conclude that this range balances statistical robustness and practical feasibility in boundary graph generation.
7 Conclusion and Next Steps
GNNBoundary is a pioneering framework that enables finding near-boundary graphs in GNN classifiers that can be used to collect the boundary statisties margin, thickness and complexity for a quantilative assessment of a GNN classifiers robustness. It is the first work to offer explainability on the decision boundary of a GNN classifier. In this study, we reproduced the author's results and confirm the author's claims: (1) we observe similar results when using their adjacency discovery algorithm and report a high correlation between the obtained adjacency scores and near-boundary graph generation success rates. Further, (2) we find that GNNBoundary can consistently generate near-boundary graphs and is superior to the cross-entropy bascline. However, this was only possible after extensive hyperparameter optimization. Finally, (3) we observe high variations on the boundary statistics, which makes us question their reliability and precision. Nonetheless, they can still provide some orientation on the generalization capabilities of the classifier. As a result, we confirm only limited applicability of the boundary statistics. Throughout experiments, we observe performance issues with the Enzymes dataset and explain this with it's relatively high complexity and low classifier performance. To further assess GNNBoundary's general applicability, we test the method on two
12

---

Published in Transactions on Machine Learning Research (06/2025)
additional real-world datasets. In that, observe fair results for one dataset (IMDB) and results for the other (Reddit) due to deficient scalability with larger graphs. Moreover, we conduct an empirical analysis of GNN robustness in boundary detection and find it to be robust compared to a simple cross-entropy based baseline method for finding ncar-bounarry embeddings that we introduce. Finally, we perform a study on the stability of the boundary statistics under different target class probability ranges and confirm the [0.45, 0.55] range suggested by the authors.
In summary, can commend the effort of the GNNBoundary authors the interpretability of GNN classifiers is valuable and underexplored topie, but issues around the usability of their method, inchuding hurdles like the need for extensive hyperparameter optimization, confine future researchers case to build upon this idea.
Future research could work on a more realistic graph sampling framework that overcomes the strong indepen- dence assumption being made by the independence of the distributions for edges, nodes and node features. Attempts reduce the method's need for hyperparameter optimization or alternative approaches that are easier to apply could further contribute GNN classifier explainability. Despite our extensive hyperparam- eter optimization efforts, cannot confirm the author's consistently high convergence rates and observe significant discrepancies on the boundary statistics, highlighting the need for more robust methods.
Acknowledgments
The authors would like to express their sincere gratitude to the lecturers and staff of the course Fairness, A Accounlabillyy, Confidentialilyy and Transporency in AT at the University of Amsterdam for their insightful discussions and feedback. Additionally, we acknowledge Dr. Pascal Mettes (University of Amsterdam) for his guidance and explanations of topics covered this rescarch. Their insights and expertise contributed to our understanding and the development. of this work.
13

---

Published in Transactions on Machine Learning Research (06/2025)
References
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neural networks for graph classification. In International Conference on Learning Representations, 2020. URL
https://openrevier: http:///oppprroiiienoooooooouoar wow.ooornnnnddyyeoorrFF..
Fan Fan, Gang Wu, Yining Yang, Fu Liu, Yuli Qian, Qingmiao Yu, Hongqiang Ren, and Jinju Geng. A graph neural network model with a transparent decision-making process defines the applicability domain for environmental estrogen screening. Pawiroommntal Science 8 Technology, 57(46): 12236-1845, 2023.
Qizhang Feng, Ninghao Liu, Fan Yang, Ruixiang Tang, Mengnan Du, and Xia Hu. DEGREE: Decomposition based explanation for graph neural networks. In International Conference on Learning Representations, 2022. URL https://openrevier rett/forrmmdddeeeoobb33.....1
Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Zorro: Valid, sparse, and stable explanations in graph neural networks. IEEE Transactions on Knowledge and Data Engineering, 35(8): 8687 8698, 2022.
E. N. Gilbert. Random Graphs. The Annals of Mathematical Statistics, 30(4):1141 1144, 1959. doi: 1111114/amm/11777/0
URL
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 opplications (ICMLA), pp. 101-106. IEEE, 2020.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, and Yi Chang. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions Knowledge and Data Engineering. (5(7))6968-6977 2022.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In In- ternational Conference on Learning Representations, 2017. URL https:://pennreviev..o wtt.:ewwwwwweeeeeeeuuumue.... rkE3y85ee
I. T. Jolliffe. Principal Component Analysis. Springer, 2 edition, 2002. ISBN 978-0387954424. ISBN: 978-0387954424.
Jaykumar Kakkad, Jaspal Jannu, Kartik Sharma, Charn Aggarwal, and Sourav Medya. A survey on ex- plainability of graph neural networks. arXiv preprint arXiv:2306. 015809306.01988 2023.
Hamid Karimi, Tyler Derr, and Jiliang Tang. Characterizing the decision boundary of deep neural networks. arXiv preprint arXiv: 1912.991111 1460, 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL SJU4ayYgI
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Pa- rameterized explainer for graph neural network. Advances in newral information processing systems, 33: 19620-19631, 2020.
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: //openreview.co http://wwww...tettooooomtttttsaa
Leland Mclnnes, John Healy, Nathaniel Saul, and Lukas Großberger. Umap: Uniform manifold approxima- tion and projection. Journal of Open Source Software, 3(29):861, 2018. doi: 10.21105/joss.00866 URL
wtt.://////...///........ 00861
Tamara Percira, Erik Nascimento, Lucas Resck, Diego Mesquita, and Amauri Souza. Distill n'explain: explaining graph neural networks using simple surrogates. In International Conference on Artificial Intel- ligence and Statistics, pp. 6199 6214. PMLRR 2023.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 30(1):61-800 2009. doi: 10.1109/TNN. 2008.2005605.
Ida. Schomburg, Antje Chang, Christian Ebeling, Marion Gremse, Christian Heldt, Gregor Huhn, and Di- ctmar Schomburg. Brenda, the enzyme databasc: updates and major new developments. Nucleic Acids Research, 32(Database (ssue):D431-4455 2004.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P Adams, and Nando De Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the TEEE, 104(1):148-135 175, 2015.
Ana Vasilcoiu, THF Stessen, Thies Kersten, and Batu Helvacioglu. [re] guninterpreter: A probabilistic generative model-level explanation for graph neural networks. Transactions on Machine Learning Research.
Ana Vasilcoiu, T. H. F. Stessen, Thies Kersten, and Batu Helvacioglu. [re] guninterpreter: A probabilistic generative model-level explanation for graph neural networks. Trans. Mach. Learn. Res., 2024, 2024. URL
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio.
Graph allention networks. In International Conference on Learning Represenlations, 2018. URL https: //openreview.net wwtp:/ottttoodrrrreee.....
Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards multi-grained explain- ability for graph neural networks. Adcances in newral information processing systems, 34:18446-18458, 2021.
Xiaoqi Wang and Han Wei Shen. GNNInterpreter: A probabilistic generative model-level explanation for graph neural networks. In The Eleventh International Conference on Learning Representations, 2023. URL httpps://oeenrevier
met/fforunndddrrddhhhh444
Xiaoqi Wang and Han Wei Shen. Gunboundary: Towards explaining graph neural networks through the lens of decision boundaries. In The Twelfth International Conference on Learning Representations, 2024.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems, 32(1):4 24, 2020.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference on Learning Represenlations, 2019. URL htttp::/openreviee: du ryGs61A5Km
net/forum?id=
Pinar Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
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. Advances in Neural Information Processing Systems, 33:6223 6234, 2020.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 430 438, 2020.
15

---

Published in Transactions on Machine Learning Research (06/2025)
A Related work
The explainability methods of GNNs review by [akkad et al. as mentioned, defines two types of explain- ability approaches, post-hoc and self-interpretable approach. The main difference between these two approaches is where is the examination of the explanation laking place. In other words, post-hoc models examine the explainability of the model using only its imputs, outputs and at times the internal parameters of the model, while the self-interpretable methods design the explainabiliy--rchhtcee model, such as a subgraph extraction module, that provides insights into the decision-making process while it is still on going. Self interrrrrtee methods are inherently more complex to conduct, as they would require access to the architecture of model being examined. Even when building a model with the intention of self-interpreetablity,, the use of this method often sacrifices prediction accuracy for self self-interrretabblity
dircctly inside the
Post-hoc methods can be distinguished into white box methods, methods that require access to the model's parameters and embeddings (such as node weights of different layers), and black box methods, that do not require access to the embedding and the parameters and can, for example, train a surrogate model.
Such surrogate models, motivated by the complexity of the original models that might not be interpretable, try to approximate the relationship between input and output by simpler and interpretable functions of the surrogate model. A study by Huang et al. (2022), , attempting an explainability method under the name GraphLime uses local explanations that rely on the Hilbert-Schmidt Independence Criterion Lasso (HSIC Lasso) model, a kernel-based, nonlincar feature selection technique designed for interpretability. This allows the method to operate under the assumplion that the original node features in the graph are inherently interpretable. Given a node and its N-hop neighborhood, the HSIC Lasso method identifies a subset of node features that have the greatest influence on the model's prediction, which will then serve as the explanation for that prediction. On the other hand, the surrogate model can be a GNN as well, such as in the study by Pereira et al.] (2023), the DxptiinFxplain model creates simpler version of the original GNN model using knowledge distillation and then generates explanations by solving a basic convex optimization problem. It uses a lightweight surrogate model called Simplified Graph Convolution (SGC), which is a lincar model without any nonlinear activation functions and uses just one weight matrix across all layers. The SGC model is trained to mimic the original GNN by minimizing the KT.-divergence between their predictions. Once trained, explanations are obtained from the SGC model using a straightforward convex program.
The first white box method we investigate is the decomposition method, such as the DEGREE method by Feng et al.] (2022). It finds an explanation in the form of subgraph structures. First, it decomposes the message- gressage-passing feed-forward propagation mechanism of the GNN to find a contribution score of group of target nodes. Next, it uses an agglomeration algorithm that greedily finds the most influential subgraph as the explanation.
Further on, the important subgraphs used as explanations can be found by perturbing the input; these are known perturbation- methods. GNNFxplainer by |Ying et al. (2019) is one of the earliest methods developed for explaining GNN predictions. provides explanations by identifying subgraph and subset of node features that most strongly impact the model's output. To do this, it learns continuous masks over both the adjacency matrix and the node features, optimizing them to maximize the agreement between the model's prediction on the masked subgraph and the true class label using a cross-entropy loss.
Another approach, Zorro by Funke et al. (022). provides explanations by identifying the most important nodes and features that maximize Fidelity. Fidelity is calculated as the expected validity of the perturbed input, and Zorro uses a greody algorithm that selocts the node and fcature with the highest fidelity score at each step. Unlike other methods, Zorro applies a discrete mask to select a subgraph, without relying on backpropagation.
In contrast, ReFine by Wang et al. 2021 adopts two-stage strategy involving edge attribution (pre- training) and edge selection (finettuinn). During the pre-training phase, a GNN and an MLP are trained to estimate edge probabilities for the entire class by maximizing mutual information and applying a con- trastive loss between classes. In the fino-tuning phase, these edge probabilitics are used to sample edges and generate instanco-ppecific explanations by optimizing mutual information for that particular prediction. While decomposition and perturbation methods focus on analyzing and manipulating existing components
16

---

Published in Transactions on Machine Learning Research (06/2025)
of the imput graph or the model's computations to derive explanations, generation- based approaches take different path. Instead of selecting or masking parts of the input, these methods aim to directly generate new graph structures or features that are inherently interpretable. By framing explanation as a generative task, these methods provide more flexible and often more human-graspable insights, which highlights the need for generation-based methods of explainability. The method used as a baseline in both the initial GNNInterpreter paper and the reproduction paper of was the XGNN method by Yuan et al. (2020). This method offers model-level explanations by generating representative subgraph patterns that maximize the prediction confidence for specific class. The subgraph is constructed using reinforcement learning- beased graph generator, which is trained through policy gradient optimization. In this framework, the current graph represents the state, adding an edge corresponds to an action, and the reward is derived from the model's prediction score combined with predefined constraints. These rules are lypically grounded in domain knowledge, ensuring that the generated subgraphs are both meaningful and plausible. In contrast to the XGNN method comes the GNNnnterpreter (Wang & Shen, (023), a mothod developed by the authors of GNNBoundary. GNNInterpreter is method that aims at generating the explanation (interpreter) graphs for each class. The similarity between the explanation graph embedding and the mean embedding of all graphs act as optimization constraint, while the objective is to maximize the likelihood of obtaining the explanation graph. It doesn't require domain knowledge as opposed to XGNN and the study claims it outperforms XGNN, the state of the art model at the time, in generating explanation graphs aligned better with the dataset. Interestingly, the RE.GNNinterprrter study by Vasilcoiu et al. tried to replicate these results and failed, concluding it fact doesn't outperform XGNN.
This leads to the follow-up study to GNNInterpreter, which builds upon similar core concept. GNNBoundary by Wang & Shen (024) adopts generation-based approach to enhance interpretability, offering promising direction for explainable GNNs. It aims to build upon the original GNNInterpreter architecture, which previously faced reproducibility challenges. Given the method's potential importance an impact on the explainability of GNNs, it is essential to investigate into its reproducibility and reliability.
B Adjacency Finding
Adjacency rates reported in the original work differ slightly from the values obtained when reproducing adjacency tables, using the checkpoints provided and the seed noted in the open source code. As the differences are minimal, we decide upon accepting the adjacent pairs stated by the authors and proceed further with the research using them.
Figure 2: Adjacency matrices for each datasct. Small adjacency values indicate that no decision boundary between the two classes is present in the classifier. A threshold of 0.8 is applied to explore the adjacent class-pairs, while the class-pairs below this threshold are considered non-adjacent.
Motif
Collab
Enzymes
IMDB
1.0
Heonn
1.00
1.00
1.00
0.00
Feedyy
1.00
0.94
0.98
3.8
102
0.8
1.00
0.96
0.81
0.8
Xww.
1.00
1.00
0.03
1.00
0.8
366
003
230
100
0/1
0:72
0.6
0.8
0.94
1.00
0.65
0.96
1.00
0.78
Comp-4
1:00
0.03
100
0
1000
0.4
3.4
616
0.4
0.4
Camp-3
0.00
1.00
0.00
1.00
0.2
0.98
0.55
1.00
-32
000
077
213
070
000
103
0.2
0.61
0.778
1.00
-02
0.0
-.00
0.00
-0.0
meeryy
1/ster
C Success Rates of Boundary Graph Generation
The success rate measures the proportion of 1000 runs in which the boundary graph generation converged (generated a boundary graph in the target range of [0.45, 0.55)) within 500 itcrations. Given that the reported success rates were not achieved using the authors' implementation, HPO was used to find improved configurations. Given the discrepancy between the success rates using the author's hyperparameters and
17

---

Published in Transactions on Machine Learning Research (06/2025)
optimized ones with the reported results, consider their report of experimental setup insufficient for reproducing their work.
Table 2: Convergence success rates under the author's hyperparameters across class pairs comparing GNNBoundary to the baseline cross-entropy criterion for success rate and average convergence iteration. Higher success rate is better.
Success Rate
Avg. Convergence Iteration
Dataset
C1
C2
GNN-
Cross Entropy
GNN-
Cross
Boundary
Boundary
Entropy
House
House
0.072
0.055
125.24
273.40
Motif
House
Comp4
0.681
0.653
79.86
64.59
HouseX
Comp5
0.000
0.002
429.50
CM
0.793
0.998
118.00
65.30
Collab
HE
Astro
0.998
0.923
12.38
109.27
ECI
EC4
0.120
0.004
216.62
103.25
EC1
EC5
0.054
0.631
222.30
174.01
RC1
FC6
0.184
0.853
241.34
51.63
Enzymes
EC2
EC3
0.242
0.776
158.28
103.92
EC4
EC5
0.102
0.720
103.84
157.04
RC5
FCC
0.440
0.972
59.08
72.80
Table 3: Convergence success rates under optimized hyperparameters across class pairs comparing GNNBoundary to the baseline cross-entropy criterion for success rate and average convergence iteration. Higher success rate is better.
Success Rate
Avg. Convergence Iteration
Dataset
GNN-
Cross Entropy
GNN-
Cross
Boundary
Boundary
Entropy
House House
HouseX
0.527
0.055
201.65
273.40
Motif
Compl
0.950
0.653
41.45
64.59
HouseX
Comp5
0.010
0.002
343.23
429.50
HE
CM
1.000
0.998
77.75
65.30
Collab
HE
Astro
0.900
0.923
19.71
109.27
EC1
EC4
0.180
0.004
216.62
103.25
EC1
EC5
0.487
0.631
222.30
174.01
EC1
EC6
0.328
0.853
241.34
51.63
Enzymes
EC2
EC3
0.555
0.776
158.28
103.92
EC4
EC5
0.197
0.720
103.84
157.04
EC5
FC6
0.763
0.972
59.08
72.80
Comedy
Romance
0.750
0.0720
86.11
182.92
IMDB
Comedy
Sci-Fi
0.770
0.5080
228.52
243.43
Romance
Sci-Fii
No results were obtained for the Reddit datasct (cf. scction for more details) and convergence could not be reached for the "Romance-SciFi" class pair (ef. section 6.3
6.3
18

---

Published in Transactions on Machine Learning Research (06/2025)
D Baseline using GNNInterpreter
Given some ambiguities in Wang & Shen 2024 and the fact that GNNInterpreter graphs are used for the boundary statistics, we also compute the random baseline using GNNInterpreter graphs. It works the same way as the standard random baseline with the only difference being that it samples class-graphs from previously trained GNNInterpreter samplers instead of the labeled training datasets themselves.
Table 4: Baseline probabilities for datasets and class tuples sampling using GNNInterpreter class graphs connected using a random edge to obtain boundary graphs.
Dataset
Class Pairs
Novel Baseline p(22)
Cj
C2
p(c1)
House House
HouseX
0.3799 + 0.4140
0.0742 + 0.2260
Motif
Comp4
0.3171 0.3784
0.4397 + 0.4307
HouseX
Comp5
0.2394 0.3648
0.4669 + 0.4934
HE
CM
0.9607 + 0.0008
0.0000 + 0.0000
Collab
HE
Astro
0.9607 + 0.0008
0.0393 + 0.0008
EC1
EC4
0.0360 0.1575
0.0272 + 0.1551
EC1
EC5
0.0736 + 0.2442
0.0250 + 0.1501
EC1
EC6
0.4461 + 0.4790
0.0010 + 0.0160
Enzymes
EC2
EC3
0.0748 + 0.2462
0.6005 + 0.4589
EC4
EC5
0.3377 + 0.4299
0.5146 + 0.4564
EC5
EC6
0.2760 0.4256
0.0211 + 0.1212
19

---

Published in Transactions on Machine Learning Research (06/2025)
E Boundary Statistics
We run the boundary complexity, margin and thickness as well as a confusion matrix for all three datasets from Wang & Shen
(2024) and report on all of them except for the boundary complexity (which can be found in table in the following fig. These results are discussed in section 6.1
Boundary Thickness
Boundary Margin
Confusion Matrix
House
5.78
5.32
House
1.13
0.75
House
2622
27
194
0
2500
30
Decision Rogion
39.76
37.72
3.76
2898
44
Dicision
20
2
Comp-4
2.19
Comp-4
0.66
Comp-4
199
1
2732
0
1000
10
Comp-5
10.42
Comp-5
Comp-5
2800
Hous
heuse-
Comp-4 Camp-5
Mouse-X
Comp-4 Comp-5
House
HouseX Comp4
Camp-5
Dedision Boundary
Decision Roundary
Predicied
High Energy
10.34
7.38
Energy
2.98
2.60
3.0
High Everyy
2297
109
194
2000
Desision Region
Deciioo Region
2.5
Collab
Condarssed
55.74
30
Condersadd
220
Actual
Condensed
161
1.5
1000
20
1.0
8.13
10
1.78
0.5
223
1381
500
Astr
0.0
Energyy
Mather
Energy
Mataar
Erengy
Maller Predicted
Decision Boundary
Decision Boundary
4000
30
EG1
4046
2311
383
EG1
20:00
3:40
3.72
EG1
66
5
9
11
25
Doceaton Roggon
Rogian
133
3000
Deciston Region
EC2
5
65
8
8
7
863
83
Enzymes
2000
15
EC4
400
162
EC4
20:70
9:21
EG4
9
1
71
8
10
547
369
1000
3
6
0
172
EC8
3
77
EC1
802
EC3
ED4
EG6
EC2
EC4
ECS
ED6
EC1
EC3
EC4
EGB
Decision Boundary
Decision Boundary
Precicted
Figure 3: Boundary metric analyses and confusion matrices.
F
Datasets
Apart from the datasets we added, Wang Shen (0024) employ the Motif, Collab and Enzymes datasets described in the following. For better understanding of the employed datasets, we provide table 5
Table Dataset statistics.
Size refers the number of nodes in graph.
Statistic
Size (Nodes)
Mean Graph Size
Median Graph Size
Min
Max Graph Size
Std Graph Size
Graph Size
Motif
11,531
57.07
51.00
14
112
25.65
Collab
5,000
74.49
52.00
32
492
62.30
Enzymes
600
32.46
32.00
2
125
14.87
Reddit
4,999
508.51
374.00
22
3,648
452.57
IMDB
1,500
13.0
10.0
89
8.52
20

---

Published in Transactions on Machine Learning Research (06/2025)
F.1 Details the IMDB Dataset
Following the challenges generating boundary graphs for the 'Romanc-SciFi' class pair and GNNIn- terpreter graphs for the 'Romance' class, we provide examples of "Romance" 'Romance'-graphs and 'Romance-SeiF"- graphs to identify potential root causes.
(a)
(b)
(c)
(d)
(e)
Figure Examples of Homance-SciFy near-bouddary graphs.
(a) Near-boundary graph for Romance-Comedy.
(b) Near-boundary graph for Comedy-SciFi.
Figure 5: Comparison of near-boundary graphs for Romance-Comedy and Comedy-SciFi class pairs.
21

---

Published in Transactions on Machine Learning Research (06/2025)
G GCN Classifier
Table 6: Classifier accuracies, class-wise Fl-scores, and GNN architecture hyperparanntters for each datasel, using pre-trained checkpoints from the authors' work. For IMDB, the classifier was trained with architecture parameters informed by the datasct's graph properties.
Architecture Hidden Num
Dataset
Test Accuracy
Class
F1 Score
Channels Layers
House
0.923
House
0.984
Motif
0.961
6
3
Comp
0.946
Comp
0.994
High Energy
0.802
Collab
0.782
Condensed Matter
0.617
64
5
Astro
0.823
EC1
0.273
EC2
0.526
EC3
0.750
Enzymes
0.483
32
3
EC4
0.348
EC5
0.500
EC6
0.500
Comedy
0.156
IMDB
0.453
Romance
0.491
64
Sci-Fi
0.573
3 5
Reduce dimen- slons by half
layers
64
Sum Pool
Map to logits
channels
Input Graph
GCN Layers
Concat
Linear + ReLU
Lincar
Softmax
Mean Pool
Figure 6: Architecture overview of the GCN classifier. The model processes input graphs through multiple GCN layers with LeakyReLU and Dropout, performs global weighted pooling operations, and uses linear layers for the final classification.
22

---

Published in Transactions on Machine Learning Research (06/2025)
H Hyperparameter Optimization
The following table shows the scarch space employed for automatic hyperparameter optimization using Bayesian Optimization. We worked with 8 random starts, 200 luning ileralions and 3 runs per iteration. We found that the results within those runs were mostly consistent and we took the mean performance across those runs as the performance of the entire tuning iteration. Each run had 1000 training iterations. Hyperparameter optimization was done separately for each of the datasets.
Table 7: Search Space for Hyperparameters
Hyperparameter
Data Type
Range
Values
Prior Distribution
Target Size
Integer
[20, 60]
Uniform
Target Probabilitics
Categorical
('.44500.5*',
'0.4-0.6", '0.35-0.65")
Uniform
Learning Rate
Real
[0.01, 1]
Uniform
Temperature
Real
[0.05, 0.5]
Log-Uniform
Weight Budget inc.
Real
[1.05, 1.2]
Uniform
Weight Budget dec.
Real
[0.94, 0.99]
Uniform
Table 8: Hyperparameter optimization results. The search space includes the sample size K, the target size, the target probabilities, the learning rate, the temperature, the weight budget increase for the dynamic regularization scheduler and the weight budget decrease. HPO for the Reddit dataset was not possible under the given configurations due to the high graph size (cf. section 6.3
Hyperparameter
Collab
Motif
Enzymes
IMDB
Reddit
Authors
Iterations
1000
1000
1000
1000
1000
1000
Sample Size K
32
32
32
32
32
32
Init. Weight Budget
1
Target Size
60
50
46
60
Target Probabilities
[0.45, 0.55]
(0.4, 0.6)
(0.35, 0.65)
(0.4, 0.6)
[0.45, 0.55)
Learning Rate
0.01
1.0
0.02
0.9
1.0
Temperature
0.05
0.05
0.5
0.49
0.15
Weight, Budget Inc.
1.20
1.05
1.10
1.12
Weight, Budget Dec.
0.99
0.99
0.95
0.94
Custom Loss
0.038
0.118
0.170
0.10
Remarks on Implementation
We commend the authors for their efforts to ensure the reproducibility of their work by releasing their code, pre-trained model checkpoints, and providing detailed Readme instructions. In the spirit of transparency, we offer additional context on the implementation process and suggestions for improvement, with the hope of contributing to future learning opportunities in the field.
Reproducing the main results the study required a significant investment of both time and computational resources. While the provided notebooks served helpful examples, we encountered issues with hyper- parameter configurations they led to convergence problems and were incomplete. Since dedicated
23

---

Published in Transactions on Machine Learning Research (06/2025)
training script was included to replicate the results in the original paper, implemented our own training runs using the parameters specified in the paper inferred from the notebooks. As shown in table 2 this configuration often failed to generate sufficient near-boundary graphs, making the reproduction of the results significantly harder. To address this, we conducted hyperparameter optimization (HPO) to derive class-pairspeecfiic configurations that improved convergence. However, even with the optimized parameters, the success rates remained lower than the authors reported ones.
An implementation for the boundary complexity, thickness and margin was also not included in the code publicized by the authors.
The environment setup was facilitated by both an environment.yml and pyproject. file. The latter included Git. dependency from a common XAI library used by both the GNNInterpreter (Wang & Shen (003)) and GNNBoundary (Wang & Shen (2024) repositories. This common library contains several crucial components, but its inhoritance structure introduced implementation challenges. Specifically, overlapping versions of key components within the shared repository led to confusion. Notably, the absence of clear training script, the lack of well-defined boundary metric calculations, and the presence of multiple versions of graph sampling implementations required significant effort to understand and resolve the intended design.
Embedding Space Inspection
Class
120
House
Comp
Boundary Graphs
Our Boundary Embedd
80
PC-2
60
40
20
-30
-20
-10
0
10
20
PC-1
Figure 7: 2D PCA plot showing the first two principal components calculated from the classifier's embed- dings of all graphs in the Motif class-pair House- Plouse-Comp 4, the principal components of the corresponding GNNBounyyyy graph embeddings and our boundary embeddings.
"The gun-common-xal repository can found at: http::/dhhh...oooyylmmlaaaaaaaaa
24

---

Published in Transactions on Machine Learning Research (06/2025)
Class
House
15
Comp 4
Boundary Graphs
Boundary Embeddlings
UMAP-2
-5
-10
-10
-5
10
UMAP-1
Figure 8: 2D UMAP plot for showing the classifier embeddings for the datasct, the GNNBoundary embed- dings and boundary embeddings for the Motif class pair House Comp 4.
In fig. we embeddings are spread across larger area in a specific structure while the near-boundary embeddings are collapsed to the same location in the embedding space during optimization. This supports the findings that the GNNBoundary dynamic boundary criterion allows for a more robust optimization process than our cross-entropy based method. More details on our reasoning are provided in section
very similar phenomenon in fig. 7 The GNNBoundary near-boudaary graph
25

---

Published in Transactions on Machine Learning Research (06/2025)
K
Relationship Between Boundary Metrics and Target Ranges
Table Relationship between boundary thickness and target range
Datasel
Class
(0.43.0.57)
(0.44,0.56)
(0.45,0.55)
(0.47,0.53)
(0.48,0.52)
(0.49,0.51)
(0.495,0.505)
Motif
House
21.860
21.860
21.860
21.039
20.657
22.296
24.124
Comp-4
23.006
23.006
23.006
22.959
22.366
23.980
24.727
HonseX
94.832
94.108
92.528
89.067
87.809
95.975
95.114
Comp-5
49.071
48.010
46.773
46.545
46.309
48.020
49.969
House
36.431
36.431
36.431
34.303
35.824
35.774
37.607
HouseX
65.062
65.062
U62
64.079
62.873
68.698
64.628
Collab
High Energy
69.331
69.331
69.331
73.337
69.895
93.29
44.445
Astro
2047.92
2047.92
2047.92
1605.01
1741.06
2198.34
3204.41
High Energy
222.807
222.807
222.807
209.575
160.713
Condensed Matter
36.111
36.111
36. 36.111
75.734
22.746
Enzymes
RC4
205.928
206.793
210.382
220.714
219.387
230.614
229.475
FC5
286.960
282.358
292.259
308.021
300.307
363.206
298.949
207.833
209.161
204.6400
180.781
162.449
163.469
EC6
115.654
110.911
114.174
75.252
77.022
84.510
FCI
272.131
272.131
303.868
327.851
RC5
255.304
255.304
333.342
272.701
ECI
374.599
315.357
143.406
EC4
174.381
105.329
75.279
EC1
216.613
209.391
227. 606
151.933
EC6
100.109
77.762
74.587
48.068
EC2
91.520
96.992
86.903
77.186
81.010
113.270
98.641
EC3
1192.97
1192.71
1052.44
277.830
453.337
43.763
26

---

Published in Transactions on Machine Learning Research (06/2025)
Table 10: Percentage deviation from (0.45,0.55) target range for boundary thickness
Dataset
Class
(0.43,0.57) (0.44,0.56) (0.45,0.55) (0.47,0.63)
(0.48,0.52)
(0.49.0.51)
(0.495,0.505)
Motif
House
0.00%
-3.76%
-3.50%
1.99%
10.36%
Comp-4
0.00%
0.00%
0.00%
-0.20%
-2.78%
4.23%
7.48%
HouseX
2.49%
1.71%
0.00%
-3.74%
-5.10%
3.73%
2.79%
Comp-5
4.91%
2.64%
0.00%
-0.49%
-0.99%
2.67%
6.83%
House
0.00%
-5.59%
-1.67%
-1.80%
3.23%
HonseX
0.00%
0.00%
0.00%
-1.51%
-3.36%
5.59%
-0.67%
Collab
High Energy
0.00%
0.00%
0.00%
5.78%
0.81%
34.56%%
-35.99%
Astro
0.00%
0.00%
0.00%
-21.63%
-14.98%
7.35%
46.47%
High Energy
0.00%
0.00%
0.00%
-5.94%
-27.87%
Condensed Matter
0.00%
0.00%
0.00%
-28.74%
-37.01%
Enzymes
-2.12%
-1.71%
0.00%
4.91%
4.28%
9.62%
9.08%
EC5
-1.81%
-3.39%
0.00%
5.39%
2.75%
24.28%
2.29%
EC5
1.56%
2.21%
0.00%
-11.66%
-20.62%
-20.12%
EC6
1.30%
-2.86%
0.00%
-34.9%%
-32.54%
-25.98%
110.44%
-10.44%
0.00%
7.89%
EC5
-23.41%
-23.41%
0.00%
18%
EC1
161.22%
119.91%
0.00%
EC4
13165%
39.92%
0.00%
-1.3%
-8.00%
0.00%
-33.25%
EC6
34.22%
4.26%
0.00%
-35.55%
EC2
5.31%
11.61%
0.00%
-11.18%
-6.78%
30.34%
13.51%
EC3
13.30%
13.27%
0.00%
-73.61%
-56.95%
-93.58%
-95.84%
27

---

Published in Transactions on Machine Learning Research (06/2025)
Table 11: Relationship between boundary margin and target range
Dataset
Class
(0.43,0.57)
(0.44,0.56)
(0.45,0.56)
(0.47,0.53)
(0.48,0.62)
(0.49,0.51)
(0.495,0.505)
Motif
House
0.337
0.337
0.337
0.337
0.123
0.123
0.915
Comp-4
0.416
0.416
0.416
0.416
0.220
0.347
0.744
HouseX
0.492
0.755
0.755
0.755
0.909
3.046
3,046
Comp-5
1.626
3.797
3.797
3.797
4.480
4.480
7.069
House
1.236
1,236
1,236
1.503
1,430
1.430
1.922
HonseX
0.972
0.972
0.972
0.972
1.456
2.011
2.996
Collab
High Energy
3.023
3.023
3.023
2.398
3.333
3.318
4.097
Astro
2.796
2.796
2.796
2.689
2.979
12.058
9.505
High Energy
1.997
1.997
1.997
1.997
2.497
Condensed Matter
1.645
1.645
1.645
1.645
1.982
Euzymes
EC4
17.748
17.748
17.748
32.503
32.503
32.300
34.783
EC5
4.815
4.815
4.815
33.909
33.999
63.633
33.633
EC5
3.045
3.045
3.045
17.337
24.270
16.537
EC6
11.425
11.425
11.425
10.411
14.968
6.294
EC1
17.251
17.251
18.542
18.542
EC5
12.642
12.642
24:377
24.377
EC1
5,919
4.399
28 02.9
EC4
13.383
12.763
28.059
20.664
20.677
9.465
25.900
EC6
13.949
15.315
10.926
36.139
EC2
12.138
3.154
3.154
18.348
18.348
27.913
37.612
EC3
9.944
10.469
14.045
18.061
18.061
27.764
34.422
28

---

Published in Transactions on Machine Learning Research (06/2025)
Table 12: Percentage deviation from (0.45,0.55) target range for boundary margin
Dataset
Class
(0.43,0.57)
(0.44,0.56) (0.45.0.55)
(0.47,0.53)
(0.48,0.52)
(0.49,0.51)
(0.495,0.505)
Motif
House
0.00%
0.00%
0.00%
0.00%
-63.50%
-63.50%
171.51%
Comp-4
0.00%
0.00%
42.12%
-16.59%
HonseX
-3483%%
0.00%
0.00%
0.00%
20.40%
303.442
303.44%
Comp-5
-57.18%
0.00%
0.00%
0.00%
17.99%
17.99%
86. 86.17%
House
0.00%
0.00%
0.00%
21.60%
15.70%
15.70%
55.50%
HonseX
0.00%
0.00%
0.00%
0.00%
49.79%
106.89%
208.23%
Collab
High Energy
0.00%
0.00%
0.00%
-14.06%
10.23%
9.76%
35.53%
Astro
0.00%
0.00%
0.00%
-3.83%
6.55%
$31.26%
239.95%
High Energy
0.00%
0.00%
0.00%
25.04%
Condensed Matter
0.00%
0.00%
0.00%
0.00%
20.49%
Enzymes
EC4
0.00%
0.00%
0.00%
83.14%
83.14%
81.99%
95.98%
0.00%
0.00%
606.11%
606.11%
598.500 50%%
598.50%
EC5
0.00%
0.00%
0.00%
469.36%
697.04%
443.09%
EC6
0.00%
0.00%
0.00%
-8.8%%
31.01%
-44.91%
EC1
-6.96%
-6.96%
0.00%
0.00%
-88.1%%
-8..44%
0.00%
0.00%
EC1
-79.33%
-84.63%
0.00%
EC4
-52.00%
-54.51%
0.00%
118.32%
118.46%
0.00%
EC6
27. 67%
40.17%
0.00%
230.76%
EC2
284.84%
0.00%
0.00%
74%.
481.74%
785.00%
1092.52%
EC3
-29.20%
-25.46%
0.00%
28.59%
28.59%
97.68%
145.08%
29

---

Published in Transactions on Machine Learning Research (06/2025)
Table 13: Relationship between boundary complexity and target range
Dataset
Class
(0.43,0.57)
(0.44.0.56) (0.45,0.55) (0.47.0.53) (0.48,0.52)
(0.49,0.51)
(0.495,0.505)
Motif
House and Comud
0.072
0.072
0.072
0.064
0.002
0.054
0.000
HonxeX and Comp 5
0.182
0.135
0.114
0.080
0.087
0.058
0.068
House and HouseX
0.015
0.015
0.015
0.012
0.010
0.008
0.007
Collab
High Earrgy and Astm
0.253
0.253
0.253
0.229
0.217
0.240
0.253
High Energy and Condensed Matter
0.313
0.313
0.313
0.208
0.343
Enzymes
EC4 and EC5
0.138
0.168
0.186
0.187
0.189
0.182
0.247
ECS and ECG
0.349
0.326
0.335
0.403
0.413
0.374
BC1 and EC5
0.0455
0.0455
0.021
0.000
EC1 and EC4
0.199
0.122
0.189
EC1 and ECG
0.168
0.171
0.167
0.099
EC2 and EC3
0.306
0.289
0.296
0.313
0.318
0.396
0.000
30

---

Published in Transactions on Machine Learning Research (06/2025)
Table 14: Percentage deviation from (0.45,0.55) target range for boundary complexity
Dataset
Class
(0.43,0.57)
(0.44.0.56) (0.45,0.35) (0.47.0.53)
(0.48,0.52)
(0.49,0.51)
(0.495.0.505)
Motif
House and Comud
0.00%
0.00%
0.00%
-11.11%
-13.9%%
-11.11%
-16.67%
HouseX and Cump- House and HouseX
59 50.65%
18.42%
0.00%
-29.2%%
50.00%
49.12%
42.11%
0.00%
0.00%
0.00%
33.83%
46.67%
53.83%
Collah
High Energy and Astm
0.00%
0 0.00%
0.00%%
-9 -9.49%
-14.23%
-5.14%
0.00%
High Energy and Condensed Matter
0.00%
0 0..00%
0.00%
-4.79%
9.58%
Enzymes
BC1 and
-16.57%
1.200%
12.63%
13.80%
9.84%
48.80%
BCS and
4.18%
-2.00%
20.30%
23.28%
11.6498
EC1 and
116.67%
116.67%
0.00%
-100.00%
BC1 and EC4
3.29%
-35.45%
0.003E
BC1 and EC6
0.00%
2/40%
0.0036
-10.72%
BC2 and EC3
3,38%
-2.30%
0.00%
5.74%
17.57%
101.35%
-100.00%
31


Reviews:
[{"review_id": "Hd5Nrih1nD", "reviewer": "Reviewer_KrTr", "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: the paper includes extensive experiments, containing both the original findings in previous studies and additional results. \n\nWeaknesses: \n* New conclusions from this paper is somewhat inadequate, limiting the originality and significance of the paper. \n\n* For the inconsistent conclusions, the paper does not provide much theoretical explanations nor intuitions/insights. \n\n* All the datasets used in the paper are of small scales. The conclusions may not apply to large-scale datasets and complex GNNs, thus more experiments are required. As admitted in the experimental part of the paper, the method is hard to run even on some moderate size graphs, which makes me concern about the scalability and effectiveness of the method at large scale.", "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 reproduce the findings of *GNNBoundary: Towards Explaining Graph Neural Networks Through the Lens of Decision\nBoundaries (Wang & Shen, 2024)*, with additional hyper-parameter searching in the experiments. They further develop an additional baseline using GNNInterpreter graphs, investigate two real-world datasets, and explore the trade-off between boundary metric approximation quality and target class probability ranges.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Experiments: The scalability and effectiveness of the method should be validated on larger datasets. Otherwise, the results are less convincing, and the authors should provide complexity analysis and admit this limitation. This is critical to changing my recommendation.\n\n* Writing: A large part of the main contexts is the repetition of previous paper without introducing additional information. This leads to redundancy and makes the contribution of the paper vague. Improving writing would strengthen the work.\n\n* Theory and new conclusions: The paper has no theoretical results and very limited insights, which is crucial to strengthening the work. The authors are also strongly encouraged to include more novel results in additional to validating or reproducing known results.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "JKVCshBXJ7", "reviewer": "Reviewer_mQYL", "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\n1. the paper is written in a clear and accessible manner, where the goals and contributions of the paper are clearly stated. \n2. the authors provided a comprehensive reproducibility analysis, and thoroughly conducted additional experiments with a new baseline and extra datasets \n3. the topic of GNNs, explainability and reproducibility are relevant both to the broader ML community and to the readership of this journal. \n4. The materials presented here are, to the best of my knowledge, grounded and technically sound. \n\nWeaknesses: \n\nI state the weaknesses that I perceive below, with corresponding requested changes in the \"Requested Changes\" section. \n\n1. it is not immediately clear to the reader from the paper of WHY GNNBoundary is chosen to be reproduced, out of all the potentially relevant literature. In other words, what makes GNNBoundary stand out and interesting/important to reproduce? This is important to aid the reader in understanding the context of this paper. \n\n2. it is desirable that the paper be as self-contained as possible. The authors did a good job setting up the notation and framework of GNNBoundary, and I find the background for GNNBoundary and Decision regions satisfactory. However, there is not sufficient background information on GNNs for a general ML audience to follow. For example, in equation (1) notations like H and sigma are directly introduced, with the assumption that the readers know GNNs very well already.", "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 conducts a reproducibility analysis of the GNNBoundary paper by Wang and Shen. The authors the 3 main claims of Wang and Shen, conducted experiments on the same datasets used by Wang and Shen (and additional datasets), as well as provide additional guidance via a novel baseline and hyperparameter tuning. They discover that while two of the three main claims in Wang and Shen are reproduced, the third main claim is only partially verified due to high variation of results.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The requested changes below corresponds to weakness 1 and 2 above. \n\n1. Give a paragraph/subsection that A. gives a more comprehensive literature review that positions GNNBoundary within the literature of explainability or GNNs B. give a brief explanation on why GNNBoundary is meaningful/important/interesting to replicate, as opposed to other competitors.   \n\n2. Add a section/paragraph (in the supplement/appendix if space is a constraint) that gives a brief outline/notation setup for the types of GNNs that are relevant to this paper.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eEwH2p6VXw", "reviewer": "Reviewer_mFFx", "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- Reproduction is an important avenue of research, especially where groundbreaking work is considered, which \"GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries\" does appear to exhibit.\n- Further detailed evaluations are provided, which deepen the investigations into GNNBoundary.\n- The clear structure following the main three claims being investigated.\n\n# Weaknesses:\n- This work is generally poorly written:\n  - This work does not cover related work. Special consideration should be given to the work since the publication of GNNBoundary (also considering about 1 year prior due to submission and recency).\n  - This work is not self-contained. There are multiple mentions of variables that are not explained in this work. Specifics follow in the requested changes.\n  - There are multiple grammar, spelling, and typo mistakes throughout this work, which, in some cases, lead to poor comprehensibility.\n  - Some parts of this work seem to be in poor order or lack well-structured motivation.\n  - There are multiple points in this work where terms, statements, and descriptions are used that are not clearly defined. More details in the requested changes.\n  - Some references refer to arXiv where proceedings-publications are available. More details in the requested changes.\n- There is at least one instance of poor scientific practice. Namely, the p-value of some hypothesis is stated before the authors specify a confidence value, followed by the authors specifying a confidence of 98%--a very unusual chosen confidence. Finally, the author chose to state the acceptance of a claim without specifying that they reject the negation of the claim--which the hypothesis test actually evaluated.", "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 work reevaluates and reproduces a previous ICLR publication, \"GNNBoundary: Towards Explaining Graph Neural Networks through the Lens of Decision Boundaries.\" In addition, it further evaluates the previously proposed method on two additional datasets, IMDB and Reddit, where Reddit is not computable in all experiments. Lastly, the authors include some additional disparate evaluations. The authors confirm, for the most part, the claims made in the original work.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please include a detailed related work section, paying special care to any work published since 2023. If this cannot fit into the main body of this work, include it as an appendix. Feel free to refer to the related work of the original work where appropriate. (acceptance)\n- \"Section 3.3 Decision region and boundary\" does not fully cover the background of this work. namely, \\mathcal B^{(l)}_{c_1||c_2} is not explained. What is this quantity, and what is it used for in this work? Please make sure that no reader needs to refer back to the original work of GNNBoundary. (acceptance)\n- \"Section 4 Notation paragraph\" The first sentence is malformed: \"A graph, ....\" This sentence is missing multiple parts like a verb. (strengthens work)\n- \"Section 4 Notation paragraph\" Clarify the relationship of Z and z_i, namely, that z_i is likely the i-th row of Z. Alternatively use Z_{i, \\cdot} (strengthens work)\n- \"Section 4.1\" is also not self-contained. namely, what are \\mathcal R_{c_1} and \\mathcal R_{c_2}. (acceptance)\n- \"Section 4.2\", \"efficient for discrete graph structures, and follows:\" You probably intended \"efficient for discrete graph structures, as follows:\" (strengthens work)\n- Throughout this work, you use an incorrect command for the indicator function. Consider, for instance, equation 3. Instead of an indicator, you are using a symbol that resembles \\mathbb I. (strengthens work)\n- \"Equation (4),\" you did not define p^* (acceptance)\n- \"Equation (5),\" without further context, it is not clear what ||Sigmoid(\\Omega)||_1 is. Also, as part of this regularization paragraph, you should refer to the original motivation from GNNInterpreter. (acceptance)\n- \"Equation (8),\" you never specify what \\gamma is or how it is chosen. (acceptance)\n- \"Section 5,\" \"We implement the missing parts and make it public as linked in the abstract.\" As of now, there is no link (nor a blank link replacement for anonymity) in the abstract. What did you intend here? (strengthens work)\n- \"Section 5.4,\" This is more of a question although you could include some more motivation or explanation here: Why do you expect graphs generated from GNNInterpreter to function better, or even differently, than random graphs from the classes when combined via a random edge? (strengthens work)\n- \"Section 5.5\" \"target range for the corresponding class pair classes.\" I do not know what you are trying to say here. In addition, this subsection apparently lacks motivation. While it becomes somewhat clearer what you are attempting after reading section 6.5, it is unclear to me what you are trying to evaluate here. This also complicates the conclusions drawn from section 6.5 and figure 2. (strengthens work)\n- \"Section 5.6\" \"To investigate this, we evaluate the boundary statistics (complexity, margin, and thickness) for different target probability ranges and analyze the patterns.\" This is a very ambiguous statement, and Appendix J (intended to include this evaluation) does not include any text evaluating tables 9-11. I would strongly suggest (acceptance)\n- \"Section 6.1\" Here, you exhibit poor scientific practice. You should first specify the intended confidence, which is likely 95%, then specify the p-value of your evaluation, and then conclude that you reject the negation of claim 1, thus accepting claim 1. (acceptance)\n- \"Section 6.1\" I am having trouble understanding Figure 1. What does a point in this figure represent? How are the success rates computed? (acceptance)\n- \"Table 1\" Please include your proposed GNNInterpreter baseline in Table 1. Also, the chosen precision in Table 1 is higher than necessary. 1e-2 should be sufficient here, giving you more space for the first request. (strengthens work)\n- \"Figure 2\" What are the principal components computed upon? Also, the labels on the x and y-axis should read principal component 1 and principal component 2. Depending on your answer, this might be an unfair evaluation and necessitate additional evaluations using principal components computed on other sets. (acceptance)\n- Fix your references. For instance, GNNInterpreter was published at ICLR 2023, and the paper on GAT was published at ICLR 2018, ... . Your references contain 10/23 publications only listed as arXiv, most of which are likely published in some proceedings and should be cited as such.", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This is a reproducibility study. The authors took some effort into hyperparameter tuning and evaluating new datasets, providing some new insights on which datasets the reproduced method still works on. Hence, although borderline, I would recommend acceptance, following most of the reviewers' recommendations.
Decision: Accept (poster)