On Discprecncies between Perturbation Evaluations of
Graph Neural Network Attributions

GNNExplainer(Ying et al. 2019). In this paper, the model learns a feature mask proportional to the importance of the features. The importance of the input features is evaluated based on model’s sensitivity w.r.t its presence and absence. Therefore GNNexplainer gives more weight to the features which affects models behavior. For backpropagating the gradients in mutual information maximization equation, reparameterization trick was leveraged.

PGExplainer (Luo et al. 2020). In this method, the objective is again to maximize the mutual information $MI(\cdot,\cdot)$ between the GNN’s prediction when $G$ and $G_{s}$ are the input to the model. In this equation $H\left(\cdot\right)$ stands for entropy. This can be seen as a minimization problem since the term $H(Y)$ in the equation 1 is fixed, and as a result, the objective turns into minimizing the conditional entropy $H(Y_{s}|G=G_{s})$. Two relaxation assumptions have been used for this model: i) $G_{s}$ is a gilbert graph with independently selected edges from $G$, and ii) probabilities of an edge $(e_{ij})$ from the original graph existing in the explanatory graph $P(e_{ij})$ is approximated with Bernoulli distribution $e_{ij}\sim Bern\theta_{i,j}$. Also, reparameterization trick (Jang, Gu, and Poole 2016) is leveraged to optimize the objective function with gradient-based methods. Finally, binary concrete distribution was utilized to approximate the sampling process from the Bernoulli distribution and forming $\hat{G}_{s}\approx G_{s}$. Considering several subsets and classes, Monte Carlo is used to aproximately oprimize the objective function with $K$ as the total number of sampled graph, and $C$ as the number of labels, and $\hat{G}_{s}^{(k)}$ as the k-th sampled graph:

GradCAM (Pope et al. 2019). Let the output of $j^{th}$ layer be $\hat{X}^{j+1}$ and the gradient be $g_{j}\in R^{N\times C_{j}}$ where, $C_{j}$ is the number of neurons in the $j^{th}$ layer. GradCAM proposes to compute feature weights signifying the importance of the feature $\alpha_{k}$ as: $\alpha_{k}=\sum_{i\in C_{j}}\hat{X}^{j+1}_{ki}\ast O_{j}$ where, $O_{j}=\sum_{i=0}^{N-1}g_{j}(i)$ and $i$ denotes the neurons. Inspired from GradCAM and Dive into graphs (DiG)(Liu et al. 2021), we rank the edges $e_{l,m}$ in the input graph $G$ by applying a normalization of the gradients throughout the network and adding the activation function to that. Here $l$ and $m$ denote $l^{th}$ and $m^{th}$ node. The rank of $e_{lm}$ is denoted by $\beta_{l}m$ and can be mathematically formulated as: $\beta_{lm}=\frac{\alpha_{l}+\alpha_{m}}{2}$.

SubgraphX (Yuan et al. 2021). This method uses the concept in game theory to gain different graph structures as players. To explore the important subgraph, Monte Carlo Search Tree has been used. In this search tree, root is the input graph, and each of other nodes corresponds to a connected subgraph. To reduce the search space MCTS is leveraged by selecting a path from a root to a leaf node with highest reward. $\displaystyle G^{*}=\operatorname*{argmax}_{\left|\displaystyle G_{s}^{i}\right|\leq N_{min}}Score(f(.),\displaystyle G,\displaystyle G_{s}^{i})$ is a scoring function for evaluating the importance of a subgraph $G_{s}^{i}$ with the upper bound $N_{min}$ for its size given the trained GNNs $f(.)$ and the original input graph $G$. After several iterations of search, the subgraph with the highest score from the leaves is identified as the explanation. For both MCTS and selection of explanation, Shapley value (Kuhn and Tucker 1953; Lundberg and Lee 2017) from the cooperative game theory was use as the score function. Set of the players is defined as $P=\left\{G_{s}^{i},v_{k},...,v_{r}\right\}$ where the subgraph $G_{s}^{i}$ is one player with $k$ nodes and $r(r\leq m-k)$ is the number of its L-hop neighboring nodes. To have an even more efficient computing, Monte Carlo sampling is applied to calculate Shapley values with considering a $S_{i}=P\setminus\left\{G_{s}^{i}\right\}$ as a coalition set of nodes. Finally, the approximation of Shapley values $\phi(G_{s}^{i})$ with $T$ total number of sampling steps and $f(.)$ as the trained GNN network, can be written as: $\phi(G_{s}^{i})=\frac{1}{T}\sum_{t=1}^{T(f(S_{i}\cup{{G_{s}^{i}}})-f(S_{i}))}$

Earlier, we mentioned using the unperturbed test set for evaluation of RoMie and RoLie. The motivation behind using the original, unperturbed test set is two-fold. Firstly, to ensure a fair comparison of network accuracy across various levels of sparsity, it’s essential to maintain consistency in the test set used across all sparsity conditions. Comparison of accuracies loses its reliability when the test sets differ in each evaluation due to varying perturbations. As a result, the impact of adding or removing important edges into the subgraph in accuracy plots will not be readily trackable (Figure 2). Secondly, based on our observations in Figure 19 (b) and (c), some specific structural patterns (cycle or house for BA2Motif) might form during perturbation in graph datasets. These patterns could potentially introduce a classification bias. The intention behind attribution methods is to support the network to make classification decisions based on the existing features of nodes and edges within a subgraph. The patterns, however, might serve as favorable but dishonest cues for the network to correctly classify without genuinely considering those features. To avoid these patterns in the test set, we once again recommend sticking to the original test set.

How about Out-of-distribution (OOD) effects? The distribution mismatch refers to the situation when train and test sets come from different distributions. Usually, training data used to develop the model does not entirely represent the real-world data (test set) it will eventually encounter. An example would be urban training areas for autonomous driving while the vehicle is going to be tested in off-the-road regions with challenges outside of the distribution of urban areas. In the context of interpretability, however, the methods are expected to accurately identify important features within the input data that cover the challenges to contribute to the network’s classification. while there might be an apparent mismatch between the perturbed training set and the unperturbed test set, it can be deduced that ODD will not occur as long as the network shows generalization. Thus, in this study, we only focus on analyzing attribution methods when they show generalizability. By doing so, we circumvent the above-mentioned problems related to a perturbed test set and also have taken into account the OOD effect.

The impact of node elimination when nodes do not possess features, and therefore have no predictive information, can be observed in Figure 3. We show the difference between RoMie applied on REDDIT-BINARY and BA3Motifs datasets with the absence or presence of isolated nodes. No significant disparity was observed. Hence, in datasets with non-existent node features, the elimination of isolated nodes has negligible influence on the retraining process. It is not the case for datasets with node features, however. As demonstrated in Figure 4 and Figure 5, when applying RoMie to MUTAG and ENZYME, the isolated nodes exhibit discriminative capabilities. Including these isolated nodes during retraining leads to a relatively high network accuracy at low sparsity, $65\%$, and $85\%$, respectively. This suggests that despite keeping only a few of the most important edges, the presence of isolated nodes reinforces the network. Conversely, when these isolated nodes are eliminated, the accuracy drops to $17\%$ for MUTAG and $65\%$ for ENZYME, showing artificially high network accuracy.

Based on this observation, we propose to eliminate any isolated nodes that arise after the attribution-finding process: Firstly, in the context of chemical and biological real-world datasets, a subgraph is meaningful upon the interconnectivity of all its consisting nodes. An isolated, non-bonding atom in a molecule or enzyme is not sensible. Secondly, the primary objective of our analysis centers on discovering the importance of edges. A node turns isolated because all its edges are already moved, therefore the edge removal process implies the removal of related isolated nodes emerging during this process as well.

All attributions provide probability edge weighting. Therefore, the attribution is the subset of the graph selected based on the edge weights. However, SubgraphX does not provide probability weights for edges. Therefore we generated the binary edge mask for each percentage in our KAR and ROAR experiments. E.g., for the x%, we search for a x% size subgraph. We perform retraining by applying edge removing/keeping using probability importance weightings provided by the attributions, albeit as mentioned before, for SubgraphX, we directly compute the subgraph. In general, we have implemented our experiments based on seven percentages of 0, 10, 30, 50, 70, 90, and 100 defined by the number of removing/keeping edges. During random experiments, each one is performed three times with a separate set of random probability weights with different seeds.

Earlier we mentioned it is insufficient to base the attribution evaluation solely on one retraining strategy and parallel evaluation of Most and Least important edges is crucial. Four scenarios come into play when looking at methods’ performance across different sparsities:

i) When there is a sharp rise in low levels of sparsity for RoMie, the behavior of RoLie is a pivotal factor: a) if RoLie also displays a sharp rise at the beginning, the overall method seems to behave unpredictably, lacking a discernible pattern. We could see this in GradCAM in Figure 19. Accuracy in the RoMie curve quickly rises to the original accuracy. However, as the method ignores some discriminative edges, during RoLie experiments, some discriminative edges keep the accuracy high, and thus GradCAM is undesirable from this perspective. From the visual explanations in Figure 19 (b) and (c), we can relate it to the fact that GradCam ignores either cycle or house structure in RoMie, and therefore will be present in the least important edges with discrimination power for the network. On the other hand, b) if RoLie exhibits a smooth rise, it suggests the method’s ability for generalization. PGExplainer and SubgraphX both show this behavior in the two retraining settings. With a look at the visual examples, we can see that PGExplainer captures the whole part of both cycle and house structures, giving us a piece of strong evidence that GCN potentially focuses on these features during its retraining. SubgraphX returns the most but not the entire part of the house pattern, which has a high overlapping part with the cycle one. Hence, removing them could disrupt network training. Therefore, it does not show a bad performance in the ROAR experiment.

ii) In cases where the early sparsity ascent for RoMie lacks sharpness, likewise, RoLie’s characteristics further determine the method’s behavior: a) if RoLie remains sharp in such a context, it signals an inability to generalize. In Figure 19 we see that GNNExplainer nearly performs on par with the random setting in both retraining evaluations, and its visualized outputs demonstrate a lack of confidence behind both cycle and house patterns. However, b) in case of a smooth RoLie accompanied by a method that appears random implies a lack of consistency. The method does not pick the most important edges at low sparsities, yet it does not leave them behind in the least important list. This is a case where the model is not very smart in identifying attributions. For BA2Motif dataset, non of the methods exhibited this behavior. For such examples please look at supplementary.

Thus, the takeaway here is that the merit of an attribution method is not merely determined by the success of one retraining strategy; RoMie and RoLie must be analyzed jointly for a well-rounded and sound judgment.

A central point of concern in the evaluation of attributions could revolve around whether the behavior of methods remains consistent when applied to different datasets and network architectures, or if their effectiveness in terms of generalizability varies from one setting to another. In Figure 19, we employed the GCN and evaluated the outcomes of retraining. Shifting our focus to Figure 8, we aim to trace the results of the four methods on the same dataset (BA2Motif), but this time employing the GIN architecture. This as a comparison point allows us to monitor the influence of a different network on the outcomes.

Previously for GCN, we observed PGExplainer can precisely identify circle-house motif pair in low sparsity. This implied the edges related to the motif would not appear among the least important edges. That is why a smooth RoLie was observed. For the GIN (shown in Supplementary), PGExplainer overlooks either Cycle or house motif. This will let some edges related to the motifs remain in the subgraph when retraining on the least importants. Therefore, it will lead to undesirable high accuracy at low sparsity for RoLie.

Unlike PGExplainer, GradCAM captures the whole Cycle-house pair in the new GIN setting. In Figure 19 (b) and (c) we noted GradCAM was unable to capture house motifs in contrast to Figure 8 (b) and (c) where we see the pair is discernable for the method. Overall, results for GradCam look fairly consistent in both architectures. This is also the case for GNNExplainer and SubgraphX. GNNExplainer continues to exhibit similar behavior close to random as before. We only observe an increase in accuracy for it once the sparsity level reaches 50%. What sets this method different in the context of GIN is that it shows a wide range of variability, making it less robust in the GIN setting. For subgraphX in RoLie plot, we observe a peculiar behavior. There is a sudden jump in the curve. This behavior can be justified by the fact that SubgraphX results do not necessarily overlap if we increase the search space (e.g., from 30% to 50%). All in all, results in Figure 7 prove the inconsistency of methods when employed across different networks.

From Binary to Trinary Classification: Binary datasets like BA2Motifs have a notable limitation. Achieving high accuracy is feasible by focusing on a single discriminative motif and disregarding the features of the other motif. To address this, we introduce BA3Motifs, an extended multi-class variant of BA2Motifs, where the triangle motif replaces the house motif to create a third class. Figure 8 shows experiments to evaluate attribution method’s data dependency using this dataset. In contrast to BA2Motifs, retaining PGExplainer features has no positive impact on network retraining, showing a performance similar to random settings. Retraining the least important features also does not reduce the performance. This is because PGExplainer fails to capture either cycle, house, or triangle motifs, as can be seen in the sample visualization. This evidence indicates that methods such as PGExplainer might exhibit inconsistent behavior in BA2Motifs and BA3Motifs, implying that the method’s performance is contingent on the dataset.

So far, our observations have highlighted the dependence of attribution methods on both the dataset and the network. The next question that arises is whether, in a specific setting, we can make a general recommendation for a method. Our attempts in this study were not directed at creating a benchmark; rather, our aim was to introduce a framework for fair evaluation. However, as we employed the RoMie and RoLie approaches across various settings, evident trends could be seen: PGExplainer shows to be a method that has the most variable performance among different settings, while GradCAM is relatively more stable. GNNExplainer was the method that performed similarly to the random setting in most experiences. SubgraphX shows the disadvantage of non-overlapping subgraphs as sparsity was increasing. For instance, in sample visualization as in Figure 1 for the BA2Motif, the selected nodes in sparsity level of $30\%$ were not necessarily appearing also in $70\%$. This can be associated with the fact that subgraphX has a different search span each time it looked for attributes. This lesd to huge jumps both in RoMie and RoLie plots. Therefore we recommend using subgraphX for datasets of small graph size where the search space can be limited. In addition to the trend, a key observation can be drawn from both the RoMie and RoLie plots: at a specific sparsity, a method can demonstrate superior performance compared to another one, while underperforming the same method at a different sparsity level. Keeping this in mind, it becomes essential to initially determine the desired sparsity level and then proceed to method comparison. What holds particularly important here is the alignment of the sparsity level of $x\%$ in RoMie with the sparsity level of $(100-x)\%$ in RoLie, as these two subsets Combined represent the complete original graph sample $G_{o}$. Thus, for one method to be considered more reliable than another, it must exhibit higher accuracy in RoMie and lower accuracy in the complementary sparsity within RoLie. When coupled with the visualization of attributions, these insights provide us with a robust basis for comparison.

Initially, for each dataset a three-layer GIN and GCN were trained; all three layers have an identical number of neurons though their number might vary from 20 to 300 depending on the dataset and network. BA-2Motifs was trained for 100 epochs with batch size 64 for GCN and 32 for GIN, BA-3Motifs for 100 epochs with batch size 64, REDDIT-BINARY, IMDB-BINARY, ENZYME, and MTAG for 500 epochs and early stopping of 100 with batch size 64, though for MUTAG batch size was 32. Adam optimizer with a learning rate of 0.001 was employed. We applied the same configuration during retraining strategies i.e. RoLie and RoLie.

We used two Nvidia GPUs ”Quadro P6000” and ”GeForce GTX 1080 Ti” on an ”AMD Ryzen 7 1080X Eight-Core Processor” CPU, Python version 3.10.4, Pytorch 1.12, Torch-geometric 1.7.2 and Dive-Into-Graphs (DIG) 0.1.2 packages.

Alongside random setting, four attributions were used to provide probability edge weighting. For both GNNExplainer and PGExplainer, we applied Adam optimizer with different learning rates of 0.01 and 0.003, and a range number of epochs from 300 to 500 and 10 to 100 were considered to depend on the dataset respectively. For PGExplainer, we have selected a two-layer fully connected network to provide edge weights. For SubgraphX, the configuration is 10 iterations with 14 expansions to extend the child nodes of the tree search. Despite other attributions, SubgraphX does not provide probability weights for edges, therefore we introduced a trick instead in which we have separately generated the binary edge mask for each percentage in our RoMie and RoLie experiments.

BA-2Motifs: A synthetic binary graph classification dataset that each graph possesses either a five-node cycle or house motif [(ref2)] and we expect the attribution to find these patterns. BA-3Motifs: For further examination of our experiments on multi-class datasets, we prepared an extended version of BA-2Motifs where we propose a set of newly generated 500 graphs. We produced the third class by replacing the triangle motif with the house one in the second class. REDDIT-BINARY: A real social networking dataset, each graph belongs to either answer-question or discussion-based threads [(ref1)]. We expect that explainer methods should mostly provide focal-like and sub-group patterns for these two classes respectively.

IMDB-BINARY: It is a real social networking dataset representing movie collaboration between actors/actresses [(ref3)]. Each actor/actress is represented by a node and there is an edge between them if they appeared in the same movie. Each graph is labeled as either action or romance genre, though action has a higher priority.

MUTAG: A real biological binary classification dataset determining whether a given chemical compound has a mutagenic effect on a bacterium or not [(ref4)]. Nodes and edges are representing atoms and bonds between them respectively.

ENZYME: It contains enzyme graphs from the BRENDA enzyme database which is a dataset of protein tertiary structures [(ref5)]. The main goal is to classify each enzyme into one of the 6 EC top-level classes.