Faithful Interpretation for Graph Neural Networks
Authors: Lijie Hu
Tianhao Huang
Lu Yu
Wanyu Lin
Tianhang Zheng
Di Wang
Venue: Accepted by TMLR ()

Abstract: Currently, attention mechanisms have garnered increasing attention in Graph Neural Networks (GNNs), such as Graph Attention Networks (GATs) and Graph Transformers (GTs). This is due to not only the commendable boost in performance they offer but also their capacity to provide a more lucid rationale for model behaviors, which are often viewed as inscrutable. However, Attention-based GNNs have demonstrated instability in interpretability when subjected to various sources of perturbations during both training and testing phases, including factors like additional edges or nodes. In this paper, we propose a solution to this problem by introducing a novel notion called Faithful Graph Attention-based Interpretation (FGAI). In particular, FGAI has four crucial properties in terms of stability and sensitivity to interpretation and the final output distribution. Built upon this notion, we propose an efficient methodology for obtaining FGAI, which can be viewed as an ad hoc modification to the canonical Attention-based GNNs. To validate our proposed solution, we introduce two novel metrics tailored for graph interpretation assessment. Experimental results demonstrate that FGAI exhibits superior stability and preserves the interpretability of attention under various forms of perturbations and randomness, which makes FGAI a more faithful and reliable explanation tool.

Published in Transactions on Machine Learning Research (05/2025)
Faithful Interpretation for Graph Neural Networks
Lijic Hu"
kijie./nu@kkust.cdoe edu..
Provable Responsible Al and Data Analytics (PRADA) Lab King Abdullah University of Science and Technology
Tianhao H
tianhao alez. saae.ttunn@@@mma. com
Provable Responsible AI and Data Analytics (PRADA) Lab Nankai University
Lu Yu Ant Group
lu. w..yykkkoust.e edu. sa
Wanyu Lin
wanglinn@comppoolgee edu.hk
Deportment of Computing Hong Kong Polytechreic Universily
Tianhang Zheng
sthaheng@eju.edu.co
The State Key Laboratory of Blockchain and Data Security Zhefiang University
Di Wang!
di www.n@nkaaussse.ee edu. 8a
Provable Responsible Al and Data Analytics (PRADA) Lob King Abdullah University of Science and Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id= Y8EspzaksH
Abstract
Currently, attention mechanisms have garnered increasing attention in Graph Neural Networks (GNNs), such Graph Attention Networks (GATs) and Graph Transformers (GTs). This is due to not only the commendable boost in performance they offer but also their capacity to provide more lucid rationale for model behaviors, which are often viewed as inscrutable. However, Attention-base based GNNSs have demonstrated instability in interpretability when subjected to various sources of perturbations during both training and testing phases, including factors like additional edges or nodes. In this paper, we propose a solution to this problem by introduingg a novel notion called Faithful Graph Attention-basee Interpretation (FGAI). In particular, FGAI has four crucial properties in terms of stability and sensitivity to interpretation and the final output distribution. Built upon this notion, we propose efficient hothodolggy for obtaining FGAI, which can be viewed the canonical Attention-based GNNs. To validate our proposed solution, we introduce two novel metrics tailored for graph interpretation assessment. Experimental results demonstrate that FGAI exhibits superior stability and preserves the interpretability of attention under various forms of perturbations and randomness, which makes FGAT a more faithful and reliable explanation tool.
ad hoc modification to
1 Introduction
Graph Neural Networks (GNNs) have experienced rapid proliferation, finding versatile applications across a spectrum of domains such as communication networks (Jiang 2022), medical diagnosis (Ahmedt-Aristizaaal
"Equal contribution. Part of the work done when Tianhao Huang research intern PRADA Lab.
Cooresponning author.

---

Published in Transactions on Machine Learning Research (05/2025)
et al. 2021). and bioinformatics Yi et al. 20221. As the adoption of deep neural networks continues to expand within these diverse fields, the significance of interpreting deep models to improve decision-making and establish trust in their results has grown commensurately. In this context, attention-based GNNs, such as Graph Attention Network (GAT) (Veličković et al. 2018) and Graph Transformer (GT) (Dwivedi & Bresson 2021h; ; have arisen as a prominently utilized approach for model interpretation, which offers the promise of deciphering complex relationships within graph-structured data using attention vectors, providing valublle insights into the decision-making processes of deep models.
5
0
o
D
Attack
Vanilla
Vanilla
5
Atback
3
3
FGAI
PGAI
Figure 1: Stability of interpretation and prediction in binary node classification task. Interpretation and predictions within the binary node classification can be susceptible to perturbations.
However, the maturation GNNs has revealed a critical concern that the increasing prevalence of adversarial attacks targeting graph-structured data. Dai et al. (2018) Zügner al. (2018 2020 has also exposed potential vulnerabilities in Attention- GNNs. This necessitates a meticulous examination of Attention- GNNs' robustness and reliability of interpretation in real-world applications. As illustrated in Figure our investigations have uncovered that even slight perturbations, such the addition of edges to node and the introduction of new node, can significantly change the predictions and interpretations of GAT. Notably, these perturbations lead to shifts in top indices of the attention vector, resulting in significant alterations to the prediction for node 7. Recent studics (Li et al., 2024 2025) have also shown that even minor perturbations to graph structure can significantly alter the explanation outcomes of Explainable Graph Neural Networks (XGNNs), posing serious risks in safety-critical applications such as drug discovery. This vulncrability challenges the fundamental principle that slight perturbations should not drastically alter attention distributions, unstable explanations undermine trust in model interpretability. This inherent instability fundamentally undermines Attention- GNNs' capacity to serve as a truly faithful tool for model explanation.
Instability has been a recognized problem in interpretation methods within deep learning. An unstable interpretation is susceptible to noise data, hindering users from comprehending the underlying logic of model predictions. Furthermore, instability reduces the reliability of interpretation as a diagnostic tool, where even slight input perturbations can drastically alter interpretation outcomes (Ghorbani et al. 2019 Dombrowski et al. 2019 Yeh et al. 2019). For safety- and security-critical applications like drug discovery, slight perturbations may have disastrous effects on the results. For example, Wang et al. (0233 roduces DrugExplorer to provide domain experts with interpretable visual explanations for GNN-basee drug repurposing predictions. Hence, stability is increasingly recognized as a crucial factor for faithful model interpretations. This prompts our question: Con we augment. the faithfulness of attention layers by enhancing their stability while preserving the key characteristics of intermediate representation explanation and prediction?
2

---

Published in Transactions on Machine Learning Research (05/2025)
To advance the cause of faithful graph interpretation within the graph attention-based framework, we introduce a rigorous definition of Faithful Graph Attention-based Interpretation (FGAT) that operates at node classification. Attention vectors in the graph attention-basee networks provide visual representations of the importance weights assigned to neighboring nodes. Thus, intuitively, FGAI should possess the following four properties for any input: (1) Significant overlap between the top-k indices of the allention layer of FGAT and the vanilla attention to inherit interpretability from the original Attention-based GNNss (2) Inherent. stability, making the attention vector robust randomness and perturbations during training and testing. (3) Close prediction distribution to that of vanilla irrention-basede GNNs to maintain Attention-basse GNNs' outstanding performance. (4) Stable output distribution, which is robust to randomness and perturbations during training and testing. Based on these four criteria, we can formally define the FGAL as a substitute for at altention-based graph interpretation.
Our contributions can be summarized as follows: (1) In-depth analysis of stability in graph attention-based networks interpretation and prediction. Our work explores and explains the stability issuc of the attention layer in Attention-based GNNs caused by different factors.
(2) A Definition for FGAI. We propose a rigorous mathematical definition of FGAL. This definition is for node classification, and it is also formal framework for faithful interpretation in Attention-based GNNs. (3) An Efficient algorithm for FGAI. To effectively address the stability issue identified and aligned with our proposed definition of FGAI, we introduce novel method for deriving FGAI. Specifically, we present a minimax stochastic optimization problem designed to optimize an objective function comprising four key terms, each corresponding to one of the four essential properties (4) Novel evaluation metrics. We design two innovative evaluation metries for rigorously evaluating the attention-based graph interpretation techniques. The comprehensive experiments showcase the superior performance of our approach in enhancing the faithfulness of Attention-based GNN variants, indicating that FGAI is more reliable and faithful explanatory tool. Due to the space limit, we provide additional experimental settings and results in the appendix.
outlined in our definition.
2 Related Work
Robustness in Graph Neural Networks. There has been some research investigating the robustness of graph-based deep learning models. Verma & Zhang (2019) first derived generalization bounds for GNNs and explored stability bounds on semi-supervisod graph learning. Zügner & Günnemann (2019) and Bojchevski & Günnemann (2019) independently developed effective methods for certilying the robustness of GNNs, and they also separately introduced novel robust training algorithms for GNNs. However, to the best of our knowledge, there has been limited research conducted on the robustness of GAT. [Body et al. (2021) indeed pointed out that their proposed GATv2 has advantage over the vanilla GAT in terms of robustness. Nevertheless, their approach sacrifices the interpretability that is present in the original attention. GSAT (Miao et al.) 2022) leverages stochastic attention and information bottleneck to achieve interpretable and generalizable graph learning, surpassing both post-hoc methods and existing interpretable models without sacrificing predictive performance. However, it does not address the issue of how to maintain the robustness of explanations under graph perturbations.
Faithfulness in Explainable Methods. Faithfulness is an essential property that explanation models should satisfy, which refers to the explanation should accurately reflect the true reasoning process of the model
(Wiegreffe & Pinter 2019 Herman
2017 Jacovi & Goldberg 2020 Lyu et al. 2022 Hu et al. 2024a cl..
Faithfulness is also related to other principles like sensitivity, implementation invariance, input invariance, and completeness (Yeh et al. 2019). Completeness means that an explanation should comprehensively cover all relevant factors for prediction (Sundararajan et al.) 2017). The other three terms are all related to the stability when facing different kinds of perturbations. The explanation should change if heavily perturbing the important features that influence the prediction (Adebayo et al. 2018). but stable to small perturbations
(Hu el. al. 2023b a Gou el al. 2023 Lai et al. 2023). Thus, stability is an important. factor in explanation faithfulness. Some preliminary work has been proposed to obtain stable interpretations. For example, Yeh| ct al. (2019) theoretically analyzed the stability of post-hoe interpretation and proposed to use smoothing to improve interpretation stability. YYn et al. (2022) designed an iterative gradient descent algorithm to get counterfactual interpretation, which shows desirable stability. Chen et al. (024)) theoretically analyze the
3

---

Published in Transactions on Machine Learning Research (05/2025)
limitations of attention-based interpretable GNNs via subgraph multilinaar extension, and propose GMT to bridge the approximation gap, achieving superior interpretability and generalizability While some prior work has proposed techniques to attain stable interpretations, these approaches have primarily focused on post-hoc interpretation and text data, making them less directly applicable to the complexities of graph data. In this conlext, our work bridges these research areas by addressing the stability problem in graph interpretation, providing a rigorous definition of Faithful Graph Attention-based Interpretation (FGAT), proposing efficient methods aligned with this definition, and introducing novel evaluation metrics tailored to the unique demands of graph interpretation, thereby advancing the faithfulness and robustness of graph-based deep learning models.
Attention-based Graph Neural Networks. Graph Neural Networks (GNNs) [Scarselli et al., 2008 Gori
ct al., 2005) have garnered significant attention in recent years deep learning approach in the fields of graph data mining and machine learning. Prior studies have put forth variely of GNN variants featuring diverse approaches to aggregating neighborhood information and employing graph-level pooling methods, such as GraphSAGE (Hamilton et al. 2017), Graph Convolutional Network (GCN, (Kipf & Welling/ 20166). Graph Attention Network, (GAT, (Veličković et al.) 2018 ). Graph Isomorphism Network, (GIN, (Xu et al., 2018)), and others. Among them, GAT (Veličković et al., 2018) introduced an attention mechanism during the node aggregation process, enabling the network to learn the importance weights between different nodes automatically. This capability allows GAT to better handle heterogeneity and importance differences among nodes, making it one of the state-of-the-art graph neural networks and exhibiting strong interpretability. Wang et al. (2019) introduced an innovative heterogeneous graph neural network that leverages hierarchical attention to achieve an optimal fusion of neighbors and multiple meta-paths in a structured manner. [Boddy et al. 2021 revealed that vanilla GAT computes limited attention that the ranking of the calculated attention scores remains unconditioned and proposed a GATv2 with a modified order of operations that demonstrates superior performance compared to GAT, exhibiting enhanced robustness to noise as well.
3 Toward Faithful Graph Attention-based Interpretation
3.1 Graph Attention Networks
Before clarifying the definition of the model with stable interpretability, we first introduce the attention layer in Attention-based GNNs. Note that our approach can be directly applied to any graph attention-based network. Here, we follow the notations in Veličković et al. (2018) for typical GAT. We have input nodes with features h = hi,.h,,,.,,,
h2 E TR² where N is the number of nodes and F is the dimension of
features. The input node features are fed into the GAT layer and then produce a new set of node features 1 = (M4 .y.,,,,............... ,, 14 E FR.. Then, the allention coefficients are calculated by a self-attention mechanism on the nodes: a = RF x RF -
Gi = a(Wh,, (WW,W)))
where We E E x R is weight matrix after a shared linear transformation applied to each node. And eij indicates the importance of node j's features to node i. In practice, softmax function is used to normalize the coelficients across all neighbors of each node. Specifically, for node i we have E RIMI with each entry wsy being
exp (eir)
Why softmax, EvENe exp (esk)*
(2)
where M₁ is the neighbor set of node i. Subsequently, Wi are employed to calculate a linear combination of the corresponding features, serving as the final output features for cach nodc. We consider the node classification task. The final output distribution for each node is
yi = a Σ Wig Why).
(3)
JEN;
where a is a non-linear activation function.
4

---

Published in Transactions on Machine Learning Research (05/2025)
3.2 Faithful Graph Interpretation
Motivation: As we discussed in the rotrouctt section, for Attention-based GNNs, both the interprelability of the attention vector and the performance of the classifier are unstable to slight perturbations on the graph structure, invalidating it as a faithful explanation tool. Thus, we aim to find a variant of the attention vector that is stable while preserving the key characteristics of intermediate representation explanation and prediction in vanilla, attention. We call such variant "stable attention". Before diving into our rigorous definition of "stable attention", we first need to intuitively think about what properties it should have. The first one is keeping similar interpretability we can easily see that the rank of its entries can reflect the importance of its neighboring nodes. Thus, "stable attention" should also have almost the same order for each entry as in the vanilla one. However, keeping the rank for all entries is too stringent, motivated by the fact that the interpretability and the prediction always rely on the most important entries. Here, we can relax the requirement to keep the top-k indices almost unchanged.
the vanilla attention. In the vanilla. attention vector for a node,
In facl, such a property is not enough as it could also be unstable. Modeling such instability is challenging as the perturbation could be caused by multiple resources, which is significantly different from adversarial robustness. Our key observation is that wherever a perturbation comes from, it will subsequently change the attention vector. Thus, if the interpretability of "stable attention", i.e., the top-k indices, is resilient to noise, we can naturally think it is robust. to those different perturbations.
However, this is still insufficient. The main reason is that keeping interpretability does not indicate keeping the prediction performance. This is because keeping interpretability can only guarantee the rank of indices unchanged, but cannot ensure the magnitude of these entries, which determine the prediction, unchanged. For example, suppose the vanilla attention vector is (0.5, 0.3, 0.2), then the above "stable attention" might be (0.9, 0.051, 0.049), which is siguificantly different from the original one. Based on these, we should also enforce the prediction performance, i.e., the output distribution, to be almost the same as the vanilla one. Morcover, its output distribution should also be robust to perturbations shown in Figure in Appendix.
Based on our above discussion, our lakeaway is that "stable atlention" should make its top-k indices and output distribution almost the same as vanilla attention while also being robust to perturbations. In the following, will translate the previous intuitions into rigorous mathematical definitions. Specifically, we call the above "stable attention" as Faithful Graph Attention-based Interpretation (FGAI). We first give the definition of top-k overlaps to measure the interpretability stability.
Definition 3.1 (Top-k overlaps). For vector & E Rd, we define the set of top-k component Tx(+) as follow,
(z) = i [d] and fl(z; 2 xz: E [d] S k}}.
And for two vectors x, x', the top-k overlap function (x,, is defined by the overlapping ratio between the top-k components of two vectors i.c., Va(x,x') = - (T) (x))).
Moreover, from equation | and equation 2 we can see the vanilla attention vector w; for node depends on input hs, thus we can think of as a function of hú denoted as w(he). Similarly, the out distribution yi is a function of an attention vector w and the input node h4, denoted as y(h, w). Based on the above notation, can formally define a (nodc-level) FGAI as follows.
Definition 3.2 ((Node-level) FGAI). We call map / is a (D, a,,, B, k1, 12) Faithuul Graph Attention- based Interpretation mechanism for the vanilla attention mechanism w if it satisfies for any node i with feature h;,
(Similarity of Interpretability) Vn, (w)h)), w(ha)) 2 B1 for some 12 81 2 0.
(Stability of Interpretability) (w.,), ö6 (h4) + p) 2 82 for some 1 82 2 0 and all ||el| s R,,
where ||. is norm and R, 2 0.
(Closeness of Prediction) D(y(h, ú) y(4, w)) S a1 for some a1 2 0, where D is some loss or divergence, yhh, i) o (Ejes, (h:)) Wh₂).
*It. notable that the dimensions of x. xt the above definition could be different.
5

---

Published in Transactions on Machine Learning Research (05/2025)
(Stability of Prediction) ( w), u(,, ii + +6) I 02 for all ||ō|| I R2, where D is some loss divergence, and y(h, i + +6) = a ( (wh(h: + 6), Why), R₂ 2 0,
where a = minfa1, 02), 8 = max and = min R1, R2}. Moreover, for any input node with feature h, we call (h) as a (D, k, Faithfll Graph Attention- based Interpretation for this node,
Note that in the previous defimition, there are several parameters. There are two properties similarity and stability for prediction and interpretability, respectively.
The first two conditions are the similarity and stability of the interpretability. We ensure v has similar interpretability with the vanilla attention mechanism. There are two paramcters, kn and 31. hn could be considered prior knowledge, i.e,, we believe the top-ki indices of allention will play the most important role in making the prediction, or their corresponding y features almost determine its prediction. B1 measures how much interpretability does w inherit from vanilla attention. When 81 = 1, then this means the top-k- order of the entries in w is the same as it is in vanilla attention. Thus, 31 should close to 1. The term stability involves two parameters, RS and 82, which correspond to the robust region and the level of stability, respectively. Ideally, if i satisfies this condition with Ri = oo and 3n = 1, then w will be extremely stable w.r.t any randomness or perturbations. Thus, in practice, we wish R₁ to be as large as possible and 32 to be close enough to 1.
The last two conditions are the similarity and stability of prediction based attention. In the third condition, measures the closeness between the prediction distribution based on w and the prediction distribution based on vanilla allention. When 0₃ = O, then ve = w. Therefore, we hope 01 to be as small as possible. It is also notable that D is the loss to measure the closeness of two distributions, which could also be some divergence. Similarly, the term stability involves two parameters, R2 and a2, which correspond to the robust region and the level of stability, respectively. Ideally, if to satisfies this condition with R₂ 3o and ag = O, then i will be extremely stable w.r.t any randomness perturbations. Thus, in practice, we wish Rs to be as large as possible and 02 to be sufficiently small.
Thus, based on these discussions, we can see Definition 3.2 is consistent with our above intuition on graph faithful attention, and it is reasonable and well-defined.
More discussions on top-k conditions. In fact, the inclusion of a top-k condition within the graph interpretation framework serves as a dual-puuposee mechanism that significantly motivates our research efforts. Firstly, this condition plays a pivotal role in retaining the most salient characteristies of node information. By focusing on the top-k elements, we ensure that the most critical aspects of the graph structure and relevance are preserved, allowing for more focused and interpretable process. This selective retention of key features is particularly valuable in complex and large-scale graph data, where identifying the most influential nodes can lead to more meaningful insights and informed decision-making.
Secondly, the top-k condition acts as a potent sparsity accelerator for graph computation. By narrowing down the attention scope to the most relevant nodes, we effectively roduce the computational burden associated with graph processing. In our extensive experiments, we empirically demonstrate that the compulational cost incurred by our approach is well-contained, requiring no more than 150% of the GPU memory utilized by the vanilla GAT and GT. This efficiency gain not only ensures the scalability of our approach but also underscores its practical viability for real-world applications. In essence, our research is driven by the dual aspiration of enhancing the interpretability and computational efficiency of graph-based deep learning models. By integrating the top-k condition, we strike a balance between retaining essential information and optimizing computational resources, thereby empowering graph interpretation with greater fidclity and scalability.
Here we need note that FGAT is different from adversarial robustness. See Appendix B for details.
6

---

Published in Transactions on Machine Learning Research (05/2025)
4 Finding FGAI
In the last section, we presented rigorous definition of faithful node-level graph interpretation. To find such FGAI, we propose formulate minimax optimization problem that involves the four losses associated with the four conditions in Definition 3.2
Based on Definition 3.2 we can see that a natural way to find a + is to minimize the prediction closeness with the vanilla attention while also satisfying other three conditions:
min E, (Dy(h, 1),, v(h, w))]
s.t. EA max Via Vis (w(h), u(h) p)] 2 $2.
l
EA [v, (whhh,, w(h)) N 31,
EA max D(y(h, T). uhh, + 6)) S 02
However, the main challenge is that the top-k overlap function is non-differential, which makes the optimization problem hard to train. Thus, we seek to design a surrogate loss Cx(-) for V-)(-), which can be used in training. The details are in the Appendix
Final objective function and algorithm. By transforming each constraint to a regularization, we can finally get the following objective function. Details are in the Appendix A
min E, [D(((, ú), s(h, w)) + AI (w, ū) + d2 max D(y(h, 1), y(h, i 8)) As max Lkg (1., v p)], 1
l|lll
where (-) is defined in p The second term top-k is substituted by surrogate loss, which is differentiable and practical to compute via backpropagation. This term guarantees the explainable information of the attention. The third term D min-max optimization controlled by hyperparameter A2 in order to find the maximum tolerant perturbation to the attention layer, which affects the final prediction. The final term Laz is also min-max optimization to find the maximum tolerant perturbation to the intrinsic explanation of the attention layer. In other words, we derive robust region using this min-max strategy.
To solve the above minimax optimization problem, we propose Algorithm 1 See Appendix
A for more details.
5 Experiments
5.1
Experimental Setup
Datasets.
In this study, we employ several datasets encompassing small to large-scale graphs to conduct an exhaustive comparison of our approach with the baseline methods. For the node classification task, we (McAuley al.) 2015). Coauthor CS and Coauthor Physics (Shchur
utilize Amazon CS and Amazon Photo
et al. 2018), ogbn-arXiv (Wang et al.
2020 Mikolov al. 2013). For the link prediction lask, we adopt.
Cora,
Citeseer and Pubmed (Sen et al.
2008). Finally, for the graph classification task, we make use of the
D&D Debnath et al. 1991), MUTAG Dobson & Doig 2003) and Politifact (Dou et al. 2021) dataset. We
present the statistics of the selected datasets in Table and these datasets in Appendix C
We also provide a detailed description of
Baselines. We employ three attention-based models, namely Graph Attention Network (GAT) Veličković ct al. 2018), GATv2 (Brody et al., (021), and Graph Transformer (GT) (Dwivedi & Bresson 2021 as basc models for three downstream lasks, namely node classification, graph classification and link prediction lask. Due to space constraints, the results of the link prediction task are presented in Appendix [D] Following the work of /Zheng al. (2021), we compare our method with vanilla. methods and two general defense techniques: layer normalization (LN) and adversarial training (AT). We refer readers to Appendix G for implementation details.
7

---

Published in Transactions on Machine Learning Research (05/2025)
Post-hoc Self-cxplained. Here, need to clarify the distinction between our approach and post-hoc learning frameworks such as PGExplainer (Luo et al. 20200) SubgraphX (Yuan et al. 2021). RC-Explainer (Wang et al.) 2022), etc. As shown in the research by Kosan et al. (2023), these explainers often exhibit significant instability when facing perturbations. Our method, on the contrary, has a distinct advantage in this regard. In other words, our approach specifically designed to address this issue.
Evaluation Metrics. For assessing the model's performance, we utilize the Fl-score as a primary metric. To comprehensively assess the stability of the model when encountering various forms of perturbations and randomness, well its ability to maintain the interpretability of attention, present graph-basee based Jensen-Shannon Divergence (g-JSD) and Total Variation Distance (g-TVD) metrics for mcasuring model stability. Furthermore, we design two additional novel metrics, namely, F and stopee to fully evaluate the interpretability of the graph attention- based neural networks.
i) Graph-based Total Variation Distance. g-TVD is a metric employed to quantify the dissimilarity between two probability distributions. It defined mathematically as
N
g- TVD 1)
Σ 1ys V..
2
where y and ÿ represent the outputs of the model before and after perturbation of the graph, respectively. Note that compared to the original TVD, here rescale it by dividing [N], where |N] is the number of nodes in the graph.
ii) Graph-based Jensen-Shannon Divergence. g-JSD is a metric used to quantify the similarity or dissimilarity between two probability distributions. is defined as follows,
g g-JSD(w, w) (K (KL(w]) + (L()))))
E|
where w and w represent the attention vectors of the model before and after perturbation of the graph, w [ww + w), and KT is Kullback-Leibler Divergence which can be defined as K KT(wlllu = wy log( ms my Note that compared to the original JSD, here we rescale it by dividing [EI, where |E] is the number of edges in the graph.
fii) F-slope. Building upon the foundation laid by Yuan et al. (2022 propose F+ stope and F stope to better evaluate the interpretability of different Attention- based GNNs. In detail, let T represent the set of nodes correctly classified by the model. Then, we rank the importance of edges based on the allention values assigned to each edge by the trained model. higher attention value indicates greater importance, while a lower value suggests lesser importance for the respective edge on the graph. Next, we utilize M,* as a mask for important edges and M, as a mask for unimportant edges, where r represents the proportion of deleted edges in the graph. In this way, (r) for positive perturbation and (r)) for negative perturbation be computed
T
F+ (r)
-- Mr = yy))
=
T
F (r) =
MF = vK))
T
From the above definitions we can see Ft and Fuce are functions of r, our metrics Ft and slope is the slop of these metrics respectively. For example, caleulate F+ Pstope (it similar for Falope) practically, we take different values of r ranging from to 0.5 with step 0.1, obtaining different values of F for each r. Then we fit a linear regression to these values and get the slope, which will be stope Clearly, F+ Fstope is a positive indicator, with higher values indicating that the model is sensitive important features. Ón the other hand, Tope is negative indicator, showing the model's insensitivity less important features.
8

---

Published in Transactions on Machine Learning Research (05/2025)
Table 1: Results of g-JSD and g-TVD of applying different methods various base models before and after perturbation. f mcans higher value under this metric indicates better results, and means the opposite. The best performance is bolded. The same symbols are used in the following tables by default. (2 Due to the substantial computational cost of calculating Laplacian positional encoding (214GiB), GT is unable to run on the ogbn-arXiv dataset.)
Model Method
Amazon-Pliee Photo
Amazon-CS
Coauthor-CS
Coauthor- Phyyics
ogbu-arXiv
g-JSDI
g-TVD.
g-JSD
g-TVD
g-JSD
g-TVD
g.JSD
g-TVD
g-JSD
g-TVD
Vanilla
6.67=199E-7
7.41=22
3.03-135:7
21.4115.8
2.2910.5E6
5.07
581118E7
1.7710.1
427E-8
36.97
LN
1.4-7
0.0611011
6.98-0.11.8
0.03:10.0
5.10:0.1E-7
0.03:10.0
L1610.1E-
0.10.0.11
4.57E-
0.09
GAT
AT
1.40-0.8--7
0.78-006
6.8740-2E-8
0.34-0.1
1.34+188F-6
1,58+122
8.1444.2F77
1.16+06
3.89F-8
1.13
FCAI
1.3810.0
0.46:20.1
0.28-0.18:
0.6820.1
5.1710.02
1.2410000
1.00000E-7
0.1810.0
3.89E-8
3.28
Vanilla
8.77=5.TE-7
1.63:199
1.00-066-7
16.8213
1.16:0225-
5.07+155
3.0520.6B77
1.7020.5
5.80E-8
3.92
LN
2.56
2.58.15.7
0.05_
0.07.10.1
5.1110:EE-7
0.03
1.110000-7
0.01.00.0
2.381-7
0.01
GATv2
143-0000-7
0.12=0.1
6.9420.08-8
0.23=0.1
6.71=111-77
0.79=10
L.3220.5-77
0.5520.5
1.92-8
2.09
FGAI
1.3710.0E-7
0.28:10:0
7.00-0.11:
0.47
5.3250008-7
0.84110.0
1.19100E
0.2010.0
3.96E-8
1.08
Vanilla
2.23-0.2E-7
0.45=0.3
0.5--
3.50=0.4
8.787
12.84-5.4
L1310,1E7
3.0140.8
OOM
OOM
GT
LN
1.0-0.1E-7
1.47=0.3
3.00-1.7R-7
4.17=3.1
2.377
0.17++0.1
1.67
0.09+0.1
OOM
OOM
3E--
3.39=2.5
9.12-366-7
0.32=0.2
7.73=0.1E-7
0.21#0.1
6.16=1/E-8
0.05
0OM
OOM
FCAT
1.61 +0.0077
0.06++0.0
6,70+0.2E-N
0.28+00.1
1.97+1.26-7
0.30++.1
8.91+0.1F-8
0.08+0.1
0OM
OOM
Table 2: Results of micro-averaged Fl scores of applying different methods various base models before and after perturbation.
Model
Mothod
Amasson-Phol
Ammzzon-CS
Cosuthor-CS
Coauthor- Physics
ogbnt-axXiv
F11
F1
Vanilla
0.800600.07
0.2363=0.02
0.7734=0.06
0.3655=0.07
0:900==0.00
0.6342:0.01
0.9481+0.00
0.7312#0.01
0.6813
0.0720
GAT
EN
0.1129-0.01 0.4385.00002
0,051000.008
0. 0.000000.08
0,726810.01
0. 0.724810.01
0.896710.01
0.888510.02
0,0729
0.0733
AT
0.05
0.822910.05 05
0.7584-0000
0.736110.00
0.9069-0.00
0.98110.100
0.918910.00
0.789110.09
0.6830
0.6742
PGAT
0.8665+000
0.8687+0001
0
0.8247
0.885++0.00
0,8905
0.9493--000 00.00
0.9485-0.00
0.0760
0.8760
Vanillo 0.800700.02
0.3655+0.16
0.7435-0.03
0.3750+0.12
0:000++0.00
0
0.900700000
0.7231+0.02
0.6127
0.5623
EN
0,4111
0.000000000
0.6173
0.515411008
0.7429:0.01
0.740610.01
0.754810002
0.752110.02
0.0718
0.0718
GATv2
AT
0.8835+0.01
0.8761+0002
0.740 00.06
0.7419+0.06
0.9044-0000
0.8513+0.11
0.949++0.01
0.8602+0.11
0.6385
0.5844
FGAI
0.8100=0.02
0.8852=0001
0.7778=0.00
0.7744=0.00
0.000:00000
0.8978=0.00
0.948G=50000
0.9474:0000
0.6152
0.6122
Vanilla 0.8501=0.03
0.812020.00
0.8611
0.8300.0.01
0.901210.01
0.870810.01
0.938810.01
0.921810.0L
00M
0OM
GT
LN
0.5017-0.10
0. 0..028.00000 0.000
0.5192-0.112
0.527010.12
0.861210.02
0. 0.865710.00 02
0.760210.15
0.7597.10.15
00M
COM
AT
0.1188-0.11
0.6360+0.07
0.374-0000
0.3744-0.00
0.6103+0.18
0.6108+00.17
0.8831+0.14
0.8830+0.14
00M
COM
FGAI
0.861210000
0.879710:01
0.877810:00
0.872510:00
0.916020:00
0.9090-0.00
0.941910:02
0.9380_0:02
00M
0OM
5.2 Stability Evaluation
We first conduct a comprehensive assessment of the stability against perturbations in interpretabilityy and the output performance of FGAI in comparison to other baseline methods. In this setting, we primarily utilize g-JSD to mcasure attention vector stability (stability of interpretability) and gVT to evaluate the stability of output distributions (stability of prediction). To assess the stability of node interpretation, we initiate the testing process by randomly selecting a small number of specific nodes within the graph and introducing perturbations by adding edges and neighboring nodes to these selected nodes. We then calculate the g-JSD of the attention vectors of these two cases. Similarly, we can also evaluate the g- TVD of the two output distributions.
The results are presented in Table and Table 2 We can observe that FGAI achieves the best Fl score on almost all base models and datasets, both before and after perturbations. This indicates the stability of its performance. Moreover, FGAI exhibits smaller g-IDD values compared to the vanilla model, signifying enhanced attention stability, while a similar trend is observed in the g- TVD metrics, demonstrating the stability of predictions. These findings collectively emphasize the effectiveness of FGAI in bolstering both attention and prediction stability, thereby positioning it as a reliable and robust approach for graph interpretation. However, while LN and AT exhibit lower g-JSD and TVD values than FGAI on some datasets, their F1 scores are very low. This suggests that they do not guarantce the stability of the performance of the base model.
9

---

Published in Transactions on Machine Learning Research (05/2025)
GAT
GATv2
GT
0.0
2,40
203
651
033
Fae
6.0
3.4
Figure Results on Amazon-Photo dataset under positive and negative perturbations for LN, AT, and FGAI to GAT, GATv2, and GT, both the clean graph (the upper figure) and the graph attacked by an injection attack (the lower figure).
5.3 Interpretability Evaluation
We calculate the proportion (dependent variable, i.e., Fite and Free the figure) nodes that the model originally predicts correctly and still predicts correctly after removing edges based on attention weights according to the specified proportion (independent, variable, ie.,, in the figure). Figure 2 presents experimental results regarding positive and negative perturbations. Duc to space limitations, more results can be found in Appendix E (Figure 5 6 7 and Table 8). On the clean graph, all methods across all models exhibit interpretability: the proportion of nodes predicted correctly in the face of negative perturbation decreases much less than when facing positive perturbation. However, on the graph after an slight injection attack, we can observe that vanilla GAT and GATv2 show a positive slope whon facing negative perturbation, indicating a complete loss of interpretability in the presence of perturbations. The same siluation occurs with GT+LN and GT+AT, and since LN and AT already exhibit significant decrease in prediction accuracy, they are not faithful interpretations.
Only FGAT, across all base models, demonstrates interpretability on both clean and attacked graphs: its performance decreases slowly when facing negative perturbation and rapidly when facing positive perturbation. This indicates that even on perturbed graphs, FGAI can ensure stable attention distributions from the base model, providing a faithful explanation. Due to space constraints, additional analyses on the experimental results can be found Appendix E
5.4 Visualization Results
We showcase the attention values of selected subset of nodes and edges from the graph data before and after perturbation, as depicted in Figure 3 (2) We highlight the top-k most important neighboring nodes and edges connected to specific node before and after perturbation, presented in Figure Due to space limitations, some of the visualization results are presented in Appendix (Figure g). In Figure we obscrve that the attention values of GAT significantly decrease after perturbation, compromising the topological importance structure of the graph and thus losing their interpretability for the graph. In contrast, FGAI maintains relatively consistent attention values before and after perturbation, demonstrating its superior performance resisting perturbations while preserving interpretable stability. Likewise, Figure 3 reinforces our model's stability in retaining the most crucial characteristics of neighboring node information, reinforcing the faithfulness of our approach.
Our visualization results come two forms: (1)
10

---

Published in Transactions on Machine Learning Research (05/2025)
Figure (a) Left Four Column: Visualizations of the attention results for GAT and FGAT, showcasing subset of nodes and edges from the graph data before and after perturbation. The color of the edges corresponds to their respeclive magnilude of values. (b) Right Four Column: Visualizations of the attention results for GAT and FGAI before and after perturbation. The red color connects the nodes that appeared in top-k nodes.
5.5 Ablation Study and Computation Cost
We also conducted experiments on the ablation study in Table 9 as well as time and storage complexities comparison in Table I0 see Appendix H and [ details. These findings reinforce the central roles played by the top-k loss and TVD loss in improving the faithfulness of the model. For computational cost, we observe that, compared to these methods, FGAI is more efficient approach. Our method incurs relatively minimal additional overhead compared to the vanilla model, offering efficient and cost-saving solution for the graph defense community.
6 Conclusions
While some studies (Shin et al. 2024) argue that attention mochanisms inherently provide interprotability, others (Fan al. 2021: Panagiotaki al. 2023 highlight their limitations, such as instability or misalignment with model behavior. This debate remains unresolved, especially in GNNs, where graph structure adds complexity. Our work does not aim to settle this broader question but instead focuses practical goal: if attention is used for explanations in Attention-based GNNs (as commonly done), how can we improve its faithfulness? In this study, we investigated the faithfulness issues Attention-based GNNs and proposed a rigorous definition for FGAI. FGAI is characterized by four key properties emphasizing stability and sensitivily, making it a more reliable tool for graph interprelation. To assess our approach rigorously, we introduced two novel evaluation metrics for graph interpretations. Results show that FGAI excels in preserving interprotability while enhancing stability, outperforming other methods under perturbations and adaptive allacks.
Acknowledgments
Di Wang and Lijie Hu are supported in part by the funding BAS/1/1669-01-01, URF/1/4663-01-01, RE1/1/5232-01-01, REI/1/5332-01-011 and URF/115508-01-01 from KAUST, and funding from KAUST Center of Excellence for Generative AI, under award number 5940. Wanyu Lin is supported in part by Hong Kong (HK) Research Grant Council (RGC) General Research Fund under Grant PolyU 15208222, NSFC Young Scientist Fund under Grant PolyU A0040473.
References
Julius Adebayo, Justin Gilmer, Michael Muelly, Ian Goodfellow, Moritz Hardt, and Been Kim. Sanity checks for saliency maps. Advances in neural information processing systems, 31, 2018.
11

---

Published in Transactions on Machine Learning Research (05/2025)
David Ahmedt-Aristizabal, Mohammad Ali Armin, Simon Denman, Clinton Fookes, and Lars Petersson. Graph-based deep learning for medical diagnosis and analysis: past, present and future. Sensors, 21(14): 4758, 2021.
Aleksandar Bojchevski and Stephan Günnemann. Certifiable robustness to graph perturbations. Advances in Neural Information Processing Systems, 32, 2019.
Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? ai preprint arXiv:2105.14491, 2021.
Yongqiang Chen, Yatao Bian, Bo Han, and James Chong. How interpretable are interpretable graph neural networks?, 2024. URL https: batps://arxiv httg//bs/2406..
Hanjun Dai, Hui Li, Tian Tian, Xin Huang, Lin Wang, Jun Zhu, and Le Song. Adversarial attack on graph structured data. In International conference on machine learning, pp.
PMLR, 2018.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Struct utructure-yttivity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):786-799 1991.
Paul D Dobson and Andrew J Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 330(4):771 78,, 2003.
Ann-Kathrin Dombrowski, Maximilian Alber, Christopher J. Anders, Marcel Ackermann, Robert Müller, and Pan Kessel. Explanations can be manipulated and geometry blame. In Advances in Neural Information Processing Systems 32: Anmual Conference Newral Information Processing Systems 2019, NewrIPS 2019, December 8- 8-14, 2019, Vancouser, BC, Canada, pp. 13567-13578, 2019.
Yingtong Dou, Kai Shu, Congying Xia, Philip S. Yu, and Lichao Sun. User preference-awaee fake news detection. In Proceedings of the 44th International ACM SIGIR Conference Research and Development in Information Retrieval, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. genoralization of transformer networks to graphs, 2021.
Negin Entezari, Saba A Al-Sayouri, Amirali Darvishzadeh, and Evangelos E Papalexakis. All you need is low (rank) defending against adversarial attacks on graphs. In Proceedings of the 13th International Conference on Web Search and Dala Mining, pp. 169 177, 2020.
Yucai Fan, Yuhang Yao, and Carlee Joe- Wong. Gen-se: Attention as explainability for node classification in dynamic graphs, 2021. URL httts://arxiv..ott htrgg//s/2211....mm 055988
Amirata Ghorbani, Abubakar Abid, and James Y. Zou. Interpretation of neural networks is fragile. In The Thirly- Third AAAT Conference on Artificial Intelligence, AAAT 2019, The Thirty-Firsl Innovative Applications of Artificial Intelligence Conference, LAAI 2019, The Ninth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2019, Honobuku, Hawaii, USA, January 27 February 1, 2019, pp. 3681-3688. AAAI Press, 2019.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. A new model for learning in graph domains. In Proceedings. 2005 IEEE International Joint Conference on Neural Networks, 2005., volume 2, pp. 729 7344 IEEE, 2005.
Xiaochuan Gou, Lijie Hu, Di Wang, and Xiangliang Zhang. A fundamental model with stable interpretabilitt for traffic forecasting. In Proceedings of the 1st ACM SIGSPATIAL International Workshop on Geo- Ceo-Privacy and Dala Utilily for Smart Societies, pp. 10 13, 2023.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
Bernease Herman. The promise and peril of human evaluation for model interpretability. arXiv preprint TrXXix1711.07// 2017.
12

---

Published in Transactions on Machine Learning Research (05/2025)
Lijie Hu, Yixin Liu, Ninghao Liu, Mengdi Huai, Lichao Sun, and Di Wang. Improving faithfulness for vision transformers. arXiv preprint or arXin:3311 1. 17983, 2023a.
Lijie Hu, Yixin Liu, Ninghao Liu, Mengdi Huai, Lichao Sun, and Di Wang. Seat: stable and explainable attention. In Proceedings of the AAAT Conference on Artificial Intellignce, volume 37(11), pp. 12907-12915 5, 2023b.
Lijie Hu, Tianhao Huang, Huanyi Xie, Chenyang Ren, Zhengyu Hu, Lu Yu, and Di Wang. Semi-supervisod concept bottleneck models. arXiv preprint arXiv:2406. 18992, 2024a.
Lijic Hu, Liang Liu, Shu Yang, Xin Chen, Hongru Xiao, Mengdi Li, Pan Zhou, Muhammad Asif Ali, and Di Wang. hopfieldian view-based interpretation for chain-of-thought reasoning. ar preprinl ar XrXiv:246.. 1.6...2200 12255, 2024b.
Lijie Hu, Chenyang Ren, Zhengyu Hu, Cheng-Long Wang, and Di Wang. Editable concept bottleneck models. arviv preprint (05 2024c.
Alon Jacovi and Yoav Goldberg. Towards faithfully interpretable ulp systems: How should we define and evaluate faithfulness? In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistios, pp. 4198-4205, 2020.
Weiwei Jiang. Graph- based deep learning for communication networks: A survey, Computer Communicatiins,, 54, 2022.
Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & dala mining, pp. 66-74, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint Xiv: 109. 02907, 2016.
Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Medya, and Sayan Ranu. Gnnx-bench: Unravelling the utility of perturbation-baso gnn explainers through in-depth benchmarking. arXio preprint 0rXiw:2310.0172 1et.2310..19/4 2023.
Songning Lai, Lijic Hu, Junxiao Wang, Laure Berti-Equille and Di Wang. Faithful vision-language interpreta- tion via concept bottleneck models. In The Twelfth International Conference on Learning Representations, 2023.
Jiate Li, Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Graph neural network explanations are fragile, 2024. URL battps://arxise owwooog////./.oo //ab////40.... 031933
Jiate Li, Meng Pang, Yun Dong, Jinyuan Jia, and Binghui Wang. Provably robust explainable graph neural networks against graph perturbation attacks, 2025. URL
04224.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33: 19620-19631, 2020.
Qing Lyu, Marianna Apidianaki, and Chris Callison-Burch. Towards faithful model explanation in nlp: A survey. arXiv preprint brXiv:2209.11326, 2022.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. In International Conference on Learning Representations, 2018.
Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image- recom- Baeza-Yates, mendations on styles and substitutes. In Ricardo Bacza- Yates, Mounia Lalmas, Alistair Moffat, and Berthier A. Ribeiro-Neto (eds.), Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, Santiago, Chile, August 9-13, 2015, pp. 43 52. ACM, 2015.
13

---

Published in Transactions on Machine Learning Research (05/2025)
Siqi Miao, Miaoyuan Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism, 2022. URL. https://arxi:: org/abs/220) 2201 12987
Tomas Mikolov, 1lya Sutskever, Kai Chen, Greg Corrado, and Jeffrey Dean. Distributed representations of words and phrases and their compositionality, 2013.
Efimia Panagiotaki, Daniele De Martini, and Lars Kunze. Semantic interpretation and validation of graph attention-based explanations for gnn models, 2023. URL http:///axxiv..ogabbbb///sa/ 04220
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions neural networks, 20(1):61-S0)) 80, 2008.
Prithviraj Sen, Galilco Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93 93, 2008.
Oleksandr Shchur, Maximilian Mumme, Alcksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. Relational Representation Learning Workshop, NeurIPS 2018, 2018.
Yong-Min Shin, Siqing Li, Xin Cao, and Won- Yong Shin. Faithful and accurate self-attention attribution for message passing neural networks via the computation tree viewpoint, 2024. URL https://arxiv.org/ abs/2406.04611
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International conference on machine learning, pp. 3319 3328. PMLR, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liô, and Yoshua Bengio.
Graph attention networks. International Conference on Learning Representations, 2018. URL https
//openreview. wttp://oommidddr......
Saurabh Verma and Zhi-Ti Zhang. Stability and generalization of graph convolutional neural networks. Tn Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1539-1548, 2019.
Kuansan Wang, Zhihong Shen, Chiyuan Huang, Chieh-Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-45))) 1118966-13,.11 2020.
Qianwen Wang, Kexin Huang, Payal Chandak, Marinka Zitnik, and Nils Gehlenborg. Extending the nested model for user-centric xai: A design study on gun- based drug repurposing. IEEE Transactions on Visualization and Computer Graphics, 29(1):1266 1276, 2023. doi: 22211//TTCC..22..33222
Xiang Wang, Yingxin Wu, An Zhang, Fuli Feng, Xiangnan He, and Tat-Seng Chua. Reinforced causal explainer for graph neural networks. IEEE Transactions on Pattern Analysis and Machine Intelligence, 45 (2):2297 2309, 2022.
Xiao Wang, Houye Ji, Chuan Shi, Bai Wang, Yanfang Ye, Peng Cui, and Philip Yu. Hetcrogencous graph allention network. In The world wide web conference, pp. 2022 2032, 2019.
Sarah Wiegreffe and Yuval Pinter. Attention is not not explanation. In Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the Ith International Joint Conference on Natural Language Processing (EMNLP-JJCNPP) pp. 11 20, 2019.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? Xiv preprint aixiv 1x0::1810.0000 310.00826, 2018.
Chih-Kuan Yeh, Cheng Yu Hsieh, Arun Sai Suggala, David Inouye, and Pradeep Ravikumar. On the fin)fiiclity and sensitivity of explanations. In Advonces in Neural Information Processing Systems 32: Arnual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancouver, BC, Canada, pp. 10965-1010 10965-10976, 2019.
14

---

Published in Transactions on Machine Learning Research (05/2025)
Hai-Cheng Yi, Zhu-Hong You, De-Shuang Huang, and Chee Keong Kwoh. Graph representation learning in bioinformatics: trends, methods and applications. Briefings in Bioinformalics, 23(1)bbbab344, 2022.
Fan Yin, Zhouxing Shi, Cho-Jui Hsieh, and Kai-Wei Chang. On the sensitivity and stability of model interpretations in ulp. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2631 -241, 2022.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. In International conference on machine learning, pp- 12241-12252. PMLR, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: Laxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5))5782255 01757727779,, 2022.
Xiang Zhang and Marinka Zitnik. Gunguard: Defending graph neural networks against adversarial attacks. Advances in neurol information processing systems, 33:9263 -275, 2020.
Qinkai Zheng, Xu Zou, Yuxiao Dong, Yukuo Cen, Da Yin, Jiarong Xu, Yang Yang, and Jie Tang. Graph robustness benchmark: Benchmarking the adversarial robustness of graph machine learning, 2021.
Daniel Zügner and Stephan Günnemann. Certifiable robustness and robust training for graph convolutional networks. In Proceedings of the 25th ACM STGKDD International Conference on Knowledge Discovery & Data Mining, pp. 246 256, 2019.
Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pp. 2847-2856, 2018
Daniel Zügner, Oliver Borchert, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on graph neural networks: Perturbations and their patterns. ACM Transactions on Knowledge Discovery from Data (TKDD), 14(5):1-31, 2020.
A Optimization
In the definition section, we presented a rigorous definition of faithful node-level graph interpretation. To find such an FGAL, we propose to formulate a min-max optimization problem that involves the four conditions in Definition 3.2 Specifically, the formulated optimization problem takes the third condition (closeness of prediction) as the objective and subjects optimization problem according to the definition. Specifically, we first have
the other three conditions. Thus, we can get rough
min E, D(y(h, w), y(h, w)). 40
(4)
Equation 44 is the basic optimization goal. That is, we want to get a vector that has a similar output prediction with vanilla GAT for all input nodes h. If there is no further constraint, then we can see the minimizer of (4) is just the vanilla GAT w. We then consider constraints for this objective function:
vh. s.t. max D(y( w), y(h, vt + 8)) S a, |
(5)
Vs, (ıi(h), wh)) 2 B,
(6)
max Vk, (h), (h) + p) 2 S
(7)
Equation (5) is the constraint of stability, Equation (6) corresponds to the condition of similarity of explanation, and Equation 7 links to the stability of explanation. Combining equations (4) and using regularization to deal with constraints, we can get the following objective function.
min En[ (D((h,, ()) yh,, w)) + (n Vi, (w)()), (hh)) i
A2 max D(y(h, v s + 6)) a) A max (3 Vk, (((h),)(())) + p))], |
(8)
R
15

---

Published in Transactions on Machine Learning Research (05/2025)
Similarity of Interpretation
Sort Value
Closeness of Prediction
0.23
0.37
TTop
0.54
Stubility of Prediction
Stability of Interpretation
GAT
Sort Value
Sort Value
0.04
7
0.02
Attack
0.05
1
0.12
0.37
TTpaa
3
0.22
0.54
4
0.36
Top
FGAI
EGAL
6
0.55
Figure The illustration of our definition.
where A > 0, A2 > 0 and A > 0 are hyperparameters.
From now on, we convert the problem of finding a vector that satisfies the four conditions in Definition 3.2 to min-max stochastic optimization problem, where the overall objective is based on the closeness of prodiction condition with constraints on stability and lop-k overlap.
Next, we consider how to solve the above min-max optimization problem. In general, gradient descent-based methods to get the solution of outer minimization and use PSGD (Projected Stochastic Gradient Descent) to solve the inner maximization. However, the main difficulty is that the top-k overlap function Vi, (ii(h), wh)) and V&, (wh), whh) + p) is mon-differentiabll, which impede us from using gradient descent. Thus, we need to consider a surrogate loss of V+.(.). Below, we provide details.
use the stochastic
Projected gradient descent to find the perturbation 8. Motivated by Madry et al. (2018), we can interpret the perturbation as the attack to w via maximizing 5. Then, 5 can be updated by the following procedure in the p-th iteration.
1
6p 8-1 7p |Bp
Σ
VD(y(h,w),v(t v(h, +66-1))
hEB,
67 arg min ||5 5p MMls
where "ip is a parameter of step size for PGD, Bp a batch and [Bp is the batch size. Using this method, we can derive the optimal 8* in the t-th iteration outer minimization for the inner optimization. Specifically, find the maximum tolerant of perturbation w.r.l to in the 1-th iteration of outer SGD.
Top-k overlap surrogate loss. Now, seck to design surrogate loss Cx(-) for - --((-) which can be used in training. We takes the ( for VVa(w, w) as example. To achieve this goal, one possible naive surrogate objective might be some distance (such as f--nrrm) between ú and w, e.g., L(w) = || - w-ll. Such a surrogate objective seems like it could ensure the top-k overlap when we obtain the optimal or near-optimal solution (i.e., w = arg min L(w) and w E arg min -V,, (w0, w)). However, it lacks consideration of the top-k information, which makes it a loose surrogate loss. Since we only need to ensure high top-k indices overlaps between and w, one improved method minimizing the distance between t and w constrained on the top-k entries only instead of the whole vectors, i.c., ||wse -gst ll1, where Wgt &gg I is the vector and à constrained on the indices set Sk respectively and St the top-k indices set of w. Since there are two top-k indices sets, one is for w, and the other one is for w, we need to use both of them to involve the top-k indices formation for both vectors. Thus, based
above idea, our surrogate be written follows,
16

---

Published in Transactions on Machine Learning Research (05/2025)
Algorithm FGAA
Input: Graph (h1 .,,,...,h ,,.,,,,,,,, hy), attention weight w. Initialize faithful attention layer Wp.
for t= 1,..... do Initialize do. po-
5: for p 1.2. P do
6: Update 6 using PGD.
5p 6p- + 7/p Σ VD uh-1 + 6p-1))-
8:
67 = arg min | 6/1l
|66|5
end for
10:
for 1,2, Q do
11:
Update p using PGD.
12:
Pq P Tq Σ VLxx (1) W2-1 Pg-1)-
13:
P = arg min || Pyll-
14:
end for
15: Update w using Stochastic Gradient Descent.
Wi = 14-1 - T/t Diy(hh w))
\1 LL, (W, 11-1) A2 VDD Uy 1x 1); v(h, u2-1 6z)) - ds VL (wx-1, ū + p&2)
16: end for
17: Return: "" =TT.
L (w, 1)
2k (1lwst 6e + 110gg Wst I11).
(9)
Note that besides the 4-norm, we can use other norms. However, in practice, we find 4-norm achieves the best performance. Thus, throughout the paper, only use 4--orm.
Projected gradient descent to find the perturbation p. Similarly, surrogate loss of Lx(-) to get the optimal p² in the t-th iteration of outer SGD.
use the PGD and the
1
Pq P + Ty
V V (w, w + pq-1);
B
Pg = arg min |p - Pyll:
where Ty is a parameter of step size for PGD, Bg is batch and [B,l is the batch size.
Final objective function and algorithm. Basod on the above discussion, we can derive the following overall objective function
min E. D(y(h, (), uh,, w)) AI (w, w) i
+ X max Dly(h, (), yh, w + 5)) + As max Lk, (w,, 2i + p)], |
(10)
where [x(-) is defined in Based on the previous idea, we propose Algorithm to solve 110
So far, we propose an efficient algorithm to solve this objective function, which meets the FGAI definition. The first term D minimizes the output difference of vanilla GAT and FGAI make it more stable. The second term top-k is substituted by surrogate loss which is differentiable and practical to compute via
17

---

Published in Transactions on Machine Learning Research (05/2025)
backpropagation. This term guarantees the explainable information of the attention. The third term D is min-max optimization controlled by hyperparameter X2 in order to find the maximum tolerant perturbation to the attention layer, which affects the final prediction. The final term C22 is also a min-max optimization to find the maximum tolerant perturbation to the intrinsic explanation of the attention layer. In other words, we derive a robust region using this min-max strategy. Thus, we get the final version 110 to solve our problem. Details of the algorithm are presented Algorithm
B Differences with adversarial robustness
While both FGAI and adversarial robustness consider perturbations or noises on graph data. There are many critical differences: (1) In adversarial robustness, the goal is only to make the prediction unchanged under perturbation on the imput (the property of stability of prediction), while in FGAI we should additionally keep the prediction close to the vanilla onc. (2) Not only the prediction, we should also make the interpretability stable and close to the vanilla altention. Due lo these additional conditions, our method for achieving FGAI is totally different from the methods in adversarial robustness, such as certified robustness or adversarial training. See Section 4 for details. (3) The way of modeling robustness in FGAI is also totally different from adversarial robustness. In adversarial robustness, it usually models the robustness to perturbation on input data. However, FGAT, due to the requirement on interpretability, i.e., the top-k indices of the vector, we cannot adopt the same idea. Firstly, directly requiring the top-k indices robust to perturbation on the input will make the optinization procedure challenging (which is minimax optimization problem) as the top-k indices function is non-iifeernntiabl,, and calculating the gradient of the attention is costly. Secondly, rather than perturbation on input data, as we mentioned, the perturbation could come from multi-resouroes, such as a combined perturbation of edges and additional nodes. Thus, from this perspective, our stability of interpretability is more suitable for "stable attention".
Table 3: Statistics of the datasets used for the node classification task.
Amazon-Photo
Amazon-CS
Coauthor-CS Coauthor-Physic ogbn-arXiv
#N Nooes
7,650
13,752
18,333
34,493
169.343
#Edges
119,043
245,778
81,894
247.962
1,166,243
# Node Features
745
76T
6,805
8,415
128
# Classses
8
10
15
5
40
Training Nodes
765
1,375
1,833
3,449
90,941
Validation Nodes
765
1,375
1,833
3,449
29,799
# Test Nodes
6,120
11,002
14,667
27,595
48,603
C Additional Information for the Dataset
We demonstrate our dataset statistics in Table Table and Table 5 Amazon CS and Amazon Photo are divisions within the Amazon co-purchase network originally introduced in McAuley et al. (2015), where nodes represent products, edges signily common pairing of two products in customer purchases, and node features are based on ofg-of-words encoded product reviews, with class labels determined by the product category. Coauthor CS and Coauthor Physies (Shchur et al., 2018 refers to co-suthorship networks derived from the KDD Cup where individual authors are depicted as nodes, and an edge connects them if they have collaborated on a rescarch paper. Node features encompass paper keywords associated with each author's publications, and labels are indicative of the primary areas of study in which each author is most active. The ogbn-arXiv dataset (Wang et al., 2020 Mikolov et al., 2013) represents the citation network between all Computer Science arXiv papers indexed by MAG. Each node is an arXiv paper, and each directed edge indicates that one paper cites another. The Cora datasct (Sen et al. 2008) collection contains 2,708 scholarly papers categorized into seven research domains, while the PubMed corpus comprises 19,717 diabetes-related publications from the PubMed database grouped into three thematic categories. The CiteSeer dataset includes 3,312 academic documents organized into six subject classifications. In structural biology, the D&D dataset (Debnath et al. 1991) features 1,178 high-resolution protein structures from the Protein Data Bank's non-redundant subset, where amino acid residues form nodes connected by edges when their spatial distance
18

---

Published in Transactions on Machine Learning Research (05/2025)
Table 4: Statistics of the datasets used for graph classification task.
D&D
MUTAG
Politifact
#Graphs
1,178
188
314
(f Classses
2
2
#.Avg. Nodes
284.32
17.93
130.74
#Avg. Edges
715.66
19.79
129.75
# Training Graphs
706
112
188
# Validation Graphs
118
31
# #Test Graphs
351
Table 5: Statistics of the datasets used for the link prediction task.
Cora
Pubmed
Citeseer
# Nodes
2,708
19,717
3,327
# Edgges
9,502
79,784
8,194
#oode Features
1,433
300
3,703
# Training Links
4,488
37,676
3,870
# Validation Links
526
4,432
454
#Test Links
1,054
8,864
910
is below 6A. For chemoinformatics applications, MUTAG (Dosson & Doig 2003
provides a repository of
nitroaromatic compounds annotated for mutagenicity assessment in Salmonella typhimurium. Regarding social media analysis, the Politifact [Dou et al.) 2021) dataset captures Twitter propagation networks of news storics labeled as factual or decoptive based on professional fact-checking evaluations.
Additional Results on Stability Evaluation
Table The results g-JS, g- TVD, and classification accuracy before and after perturbation when applying different methods to various base models in the graph classification task.
Model
Method
Citeseor
8-1SD]
gTTV)
ROC-AUC-
Attacked?
8-JSD
8-TVD
ROC-AUC
attacked
g-1SD
g-TVD
ROC-AUC
attacked
GAT
Vanilla
PGAI
2.58E-08
6.38E-07
1.22
0.7338
0.7327
0,6849
0.6258
2.06E-05
2.508-06
0.26
0.35
0.7945
0.7544
0/848
2.38E-06
2.77:-06
1.30
0.9000
0.8967
0.8833
0.8667
GATv2
Vanila
S0TE-U1
1.42
I.7028
ILA8S7
2.12E-00
1.50
0.7071
(16144
2.31E:06
1.00
0,8533
0.8U83
6.00K-08
0.7682
1.32F-05
0.20
0.7945
2.34K-D4
0.8800
In Table S and Table 7 we present a comparison of the performance of our method and the base model on the graph classification and link prediction task. As shown, our method significantly enhances the stability of the attention layer, resulting in the base model demonstrating robust stability when faced with small perturbations.
E
Additional Results on Interpretability Evaluation
Here, we present the results of the interpretability evaluation on all datasets. Similar to before, we showcase the results in the face of positive and negative perturbations when applying LN, AT, and FGAI to GAT, GATv2, and GT, both on the clean graph (the upper figure) and the graph attacked by an injection attack (the lower figure) on various datasets. We calculate the proportion (dependent variable, i.e., Ft and Fo. in the figure) of nodes that the model originally predicts correctly and still predicts correctly after removing important or unimportant edges based on attention weights (i.e., positive perturbation or negative perturbation) according to the specified proportion (independent variable, i.e., r in the figure).
From the results shown in Figure 5 and 7 supplemented by Table g we can more comprchensively examine the interpretability of the models after applying different methods different models and draw the following conclusions:
19

---

Published in Transactions on Machine Learning Research (05/2025)
Table The results of g-JSD, g- g-T,,, and the ROC-AUC score before and after perturbation when applying different methods to various base models in the link prediction task.
Model
Pubmed
Citeseer
g-1SD]
(-TVD
ROC-AUC"
Attacked!
g-ISD
B-TVD
ROC-AUI
attacked
g-J81)
g-TVD
ROC-ATIC
attacked
GAT
Vanilla
PGAI
1.79E-05
2:237-05
0.0065
0.0074
0.8502
0,8362
0.8107
0.7855
3.86E-06
4.055-066
0.0008
0.0363
0.8268
0.8288
0.8153
0.7203
3.17E-05
4.601-055
0.0080
0.0308
0.8424
0.8368
0.7873
0.7115
GATV2
PGAT
Vanilla
1.80E-05
1.41700
0.0027
0.0016
0.8741
0.8678
0,8589
0.8520
3.81E-06
3.877-006
0.0004
0.0306
0.8414
0,8377
0.8345
0.828
3.17E-05
4.577-05
0.0099
0.0201
0.8300
0.7870
0.7635
GAT
GATv2
GT
6.9
1.45
13
45
0.4
6.9
680
0.53
2..00
0.50
Figure 5: Additional results of interpretability evaluation on Amazon-CS.
Whether it is GAT, GATv2, or GT, they all exhibit some interpretability on clean graphs. When facing negative perturbation, GT performs the best-its performance decreases the least with an increase in perturbation rate r, maintaining Fie above 0.95 across different datasets. GAT and GATv2, on the other hand, show a more pronounced decrcase, indicating weaker insensitivity to unimportant edges. When facing positive perturbation, the F+ of GAT and GATv2 sharply declines with the perturbation rate r, surpassing GT, demonstrating sensitivity to important edges (edges with larger attention values).
On clean graph, the performance of different methods (LN, AT, and FGAT) is similar. Morcover, the performance of FGAI is almost identical to the vanilla model, confirming that FGAI ensures similarity of interpretability and closeness of prediction with the vanilla model.
On the attacked graph, the interpretability of all vanilla Attention-based GNNs is compromised, with abnormal phenomena such as positive slopes (improved performance as edges decrease). LN and AT also fail to maintain the interpretability of the base model. Only FGAI still ensures the stability of interpretability and stability of prediction. Moreover, at this point, the Pope of FGAI is consistently greater than that of the base model across all datasets, while stope is consistently smaller than the base model, demonstrating outstanding interpretability.
F Additional Visualization
Here, we present additional visualization results in Figure g
G Implementation Details
Regarding the architecture of the vanilla model, for the ogbn-arxiv dataset, we configure GAT, GATv2 and GT with three layers and 8 attention heads. The hidden layer dimension is set to 128. On other datasets,
20

---

Published in Transactions on Machine Learning Research (05/2025)
GAT
GATv2
GT
119
0..0
100
633
00.00
1..00
615
Figure 6: Additional results of interpretability evaluation on Coauthor- CS.
GAT
GATv2
GT
149
149
1.0
685
699
3
075
80
170
039
Figure 7: Additional results of interpretability evaluation Coauthor-Physice
we use one layer and an 8-dimensional hidden layer with 8 attention heads for GAT and GATv2 and an 128-dimensional hidden layer with 8 attention heads for GT. A consistent feature dropout rate and an attention dropout rate of 0.6 are applied to all datasets. We use Adam the optimizer. The learning rate is fixed at 0.01, and an L22 regularization is set to 0.0005. During the training of FGAI, maintained the same parameters as the vanilla model. For the Coauthor-CS and Coauthor-Physics datasets, we set X1, X and À to 1, 1, and 1, respectively, with K values of 100,000 and 200,000, respectively. For the Amazon-CS and Amazon-Phote datasets, \1 A2. and A3 were set to 0.8, 1, and 1, and K was set to 100,000. On the ogbn-arXiv dataset, we used Å1 A2, and A values of 1, 10, and 5, respectively, with K set to 600,000. Note that for the hyperparameter K, can observe significant differences in its values across different datasets. The reason is that according to the definition of FGAI in Definition 3.2 we need to find appropriate K value to ensure that the FGAI attention vector retain the most critical features of the vanilla attention vector while relaxing its constraints on less important features. This preserves the interprotability of attention under different forms of perturbations and randomness. Therefore, we set. K to approximately 50% of the number of edges in the dataset (the total length of the attention vector). In Figure 9 we show the line chart of different components the loss of FGAI on various datascts as the epoch increases. can be seen that the stability of explanation loss corresponding to Xg and the similarity of explanation loss corresponding Xa remain at relatively low value.
21

---

Published in Transactions on Machine Learning Research (05/2025)
Table 8: The results of our proposed metrics, Poop and stoppe for evaluating the interpretability of different methods applied to different models across all datasets. Note that Esiope and stope are generally negative values; the numbers in the table are displayed absolute values. Values that were originally positive are marked with underline.
Before Attack
After Attack
Model
Method
Amazan-Plood
Amazon-C:8
Counthor-CS
Coonthor-PPyeiic
Amazonn Anaston-hhota
Amuzon-CC
Comnthor-CS
Comnthor- Physics
F-
F+ 1
F-
F+
F-
F+
F-
F+
F-
F+
F-
F+
F-
F+
F-
F+
Vanilla
0.3848
1.2821
0.1617
104477
0.4301
1,3124
1.1857
0,0001
0.7312
0.1406
0.0967
0,8045
GAT
AT
0.2276
0.3504
0.9613
1.0870
0.338
0.1375
0.7050
1,0409
0.4008
0.0050
1.3766
1.2403
0.0963
0.7821
0.7000
0.3881
0.3385
0.6481
1.1285
0.3431
0.2518
0.6001
0.8607
0.4108
0.6371
1.1650
1.3644
0.1196
0.1811
0,77U8
0.7991
EGAT
0.2540
1:2185
0.1162
1/315
0.4222
1,1406
0.0006
0.7917
0.7076
1,1548
0.1007
0.0350
0.404
1,2851
0.0871
0.7972
Vanilla
0.3000
1.4200
0.5120
1,4822
0.4782
1,5120
0.1831
0.8579
0.07ST
0.9399
0.8016
0.5533
0.0:63
0.8871
0.1193
0.0299
G
LN
0.2270
0.2724
1 1500
0.4726
1.4244
0.4589
1.3192
1.4350
0.0234
0.3873
0.5388
1.2757
1.3382
0.0033
0.3106
1.3302
0. 0.4022
0.3432
1.433
0.5190
0.2272
0.9825
FGAT
0.4206
14705
0.334
1,5288
0/402
1,3758
0.2020
1.1040
0.338
1,8440
0.2005
1.1505
0.3975
1.3801
0.2869
03332
Vauilla
0.0266
0.3630
0.0283
0.5655
0.103
0.2761
0.2064
0.1533
0.1052
GT
0.0848
0.5385
0.5764
0.0720
0.0007
0.2236
0.1136
0.1500
0.5894
0.0161
0.0007
AT
0.1438
0.5783
0.0000
0.0000
0.1516
0.7966
0.7108
1.1688
0.1898
0.4963
0.0000
0.0012
0.1967
0.7733
0.6952
1.1257
EGAT
0.0866
0 0.4064
0.0270
0.5288
0.0688
0.3331
0.0382
0.1828
0.0354
0. 0.0027
0,0244
0.0 030325
0.0571
0.2640
0.0579
0.1815
Coauthor- CS
Coauthor- Physics
Amazon -C
Amazon-Photo
Figure 8: (a) Left Four Column: Additional visualizations of the attention results for both the vanilla model (GAT) and FGAI on Coauthor-CS and Coauthor-Physics dataset, showcasing subset of nodes and edges from the graph data before and after perturbation. We have selected a representative portion of the graph for display due to the substantial size of the dataset. The color of the edges corresponds to their respective magnitude of values. (b) Right Four Columm: Additional visualizations of the attention results for both the vanilla model (GAT) and FGAI on two datasets, showcasing top-k important neighboring nodes and edges from specific node before and after perturbation. The red color connects the nodes both appeared in top-k nodes before and after perturbation.
For the perturbation method, we first randomly generate nodes and connect them with random edges, and then employ the Projected Gradient Descent algorithm to create features for these new nodes, maximizing the perturbation for the graph. In our experiments, we set n=200 e=20, and the perturbation level on features to be 0.1. Additionally, we utilize Total Variation Distance loss as the loss term D in Algorithm I and select the f--orm as the perturbation radius norm.
For all experimental data, we conduct five runs using different random soods and reported both the average results and standard deviations.
H Ablation Study
We conduct ablation experiments on the loss function to demonstrate that each component the loss plays an
indispensable role bolstering the efficacy of FGAL As illustrated in Algorithm [ we systematically remove one or several components of the loss function by setting the corresponding X; values to 0. Subsequently, we evaluate the performance of FGAT with the remaining components. From the results presented in Table g
22

---

Published in Transactions on Machine Learning Research (05/2025)
Table 9: Ablation study of the proposed method. We evaluate the effectiveness of three loss functions in
objective function Amazon-Photo datasct.
Ablation Setting
Metrics
Model
C,
L
Ls
g-JSDI
g-TVD!
FIt
F11 1
/
1.30SE 7
0.4576
0.8665
0.8637
4
1. 13396E--7
0.1587
0.8698
0.8662
1.3689E-7
0.7937
0.8222
0.8180
GAT
1.3719E.7
0.4676
0.8616
0.8590
/
1.3700E-7
0.7991
0.8273
0.5225
1.3880E-7
0,5028
0.8616
0.8587
1.3717E-7
0.8529
0.8209
0.8144
1.3708H-7
0.2804
0.8160
0.8252
1.3710E-7
0.3086
0.8111
0.8216
1.3680E-7
0.5471
0.8029
0.8183
GATv2
1.3711E-7
0,3390
0.8119
0.8081
1.3882--7
0.5735
0.7493
0.7539
1.374E-7
0,2941
0.8091
0.8206
1.3700E-7
0,5415
0.75-19
0.7672
V
1.0210E-6
0.4295
0.8482
0.8319
2.8307E-5
0.5964
0.7377
0.7059
1.0275--6
1.0221
0.8351
0.5090
GT
1.0533E-6
0.3598
0.7779
0.7595
1.0281E-6
0.9455
0.8312
0.8087
2.9748E-5
0.7176
0.8110
0.5096
1.0275K-66
1.0120
0.8279
0.8044
Table 10: Time overhead and GPU memory usage for various methods on different datasets, all values are estimated, conducted on an NVIDIA V100 device with 200 epochs. O0M (Out of Memory) indicates exceoding the GPU memory limit, rendering the program unable to run.
Amazon-Phann Photo
Coauthor- Physics
ogbn-arXiv
Method
Time
GPU
Time
CPU
Time
GPU
GAT
30s
1000MrB
Imin
4000MBB
2min
4000MGB
GAT+LN
30s
1100MiB
Imin
4000MBB
2min
4400MBB
GT
50s
1200MrB
10min
6000MiB
15min
12500MiB
GAT+FGAT
60s
1300MiB
10min
6000M1B
20min
16000MiB
Pro-GNN
10min
6000MBB
10min
S000MBB
OOM
GNN-SVD
20min
6000MBB
20min
8000MBB
OOM
GNNGuard
25min
1000M1B
25min
1000MBB
OOM
it is evident. that removing the adversarial loss component significantly degrades the F1 score performance of FGAL However, there is slight improvement in the g-JSD) metric. On the other hand, omitting the top-k loss component leads to a slight increase in the F1 score, surpassing even the performance with all components on GAT (when removing L1). Nevertheless, there is a substantial drop in performance on g-JSD and g-TVD metrics. This indicates that during the training process, FGAT strikes a balance among the various components of the loss function, enabling the full method to achieve the best overall performance across all metrics. This observation underscores the high degree of joint effectiveness among the four terms within our objective function, collectively contributing the enhancement of model prediction and explanation faithfulness. These findings reinforce the central roles played by the top-k loss and TVD loss in improving the faithfulness of the model.
Computation Cost Comparison
The usage of time and space also crucial metric for evaluating the excellence of a method, as it is related to the practical deployment and application in real-world scenarios. We test the time overhead and
23

---

Published in Transactions on Machine Learning Research (05/2025)
Epeets
Commortion LoB
120000
7009
6009
0000
80000
3000
1000
GATv2 Amazon-Phooke
GAT Amazon-Photo
idai Cempanants Over Spedua
Lesa Comporent Over Spects
Senvert Lig sugaraao watonn
GATv2 on ogbn- Arxiv
GAT on ogbn- Arxiv
Figure The illustration showing the training loss decreasing with increasing epochs for the GATv2 and GAT model applying FGAI the Amazon-Photo and ogbn-Arxiv dataset.
GPU memory usage of some popular graph defense methods, namely Pro-GNN Jin et al. (222)), GNN-SVD Entezari et al. (2020) and GNNGuard Zhang & Zitnik (2020). The results are presented in Table IO We observe that, compared these methods, FGAI is more efficient approach. To our knowledge, a primary reason for this discrepancy is that defense methods like GNN-SVD and GNNGuard require calculations the dense form of the adjacency matrix of the graph. Consequently, this significantly limits their applicability on large-scale datasets. On arb dataset (169,343 nodes, 1,166,243 edges), all these methods exceed the GPU memory limit (32GiB). In contrast, our method incurs relatively minimal additional overhead compared to the vanilla model, offering an efficient and cost-saving solution for the graph defense community.
J Limitations
This paper focuses solely on faithful interpretation for attention-based GNNs, such as GT or GAT. In the future, we aim to extend this work to all GNN variants, such as GCN, GraphSAGE, etc., to help drive research efforts across the entire community in the direction of GNN interpretability.
24


Reviews:
[{"review_id": "sEHmrOtt0u", "reviewer": "Reviewer_9L2K", "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\n(+) This work addresses an important issue: the instability of attention-based GNNs, particularly under perturbations, which is critical for faithful model interpretation.\n\n(+) The proposed framework, FGAI, introduces a novel and well-defined formulation for stable and robust graph attention-based interpretation.\n\n(+) The authors design new evaluation metrics (g-JSD and g-TVD) specifically tailored to assess the stability and interpretability of graph-based models, enhancing the clarity of their results.\n\n(+) Extensive experiments on diverse datasets demonstrate the effectiveness of FGAI in improving stability and interpretability compared to baseline methods.\n\n**Weaknesses:**\n\n(-) The proposed approach is limited to attention-based GNNs and does not generalize to other types of GNN architectures, such as GCN or GraphSAGE;\n\n(-) The interpretability of the attention-based GNNs may not be fully grounded;\n\n(-) The relation between interpretable GNNs is unclear;\n\n(-) The experiments are mostly conducted on citation networks, while it's unclear how the method generalizes under adversarial perturbations, and more complicated benchmarks;", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 investigates the challenge of faithful interpretation for attention-based Graph Neural Networks (GNNs) like GAT and Graph Transformers under perturbations. The authors argue that conventional attention mechanisms in GNNs lack stability in interpretability and prediction when exposed to perturbations, such as added edges or nodes. Then, they propose a new framework called Faithful Graph Attention-based Interpretation (FGAI), which ensures stability and robustness while preserving the interpretability of attention mechanisms. The method is formulated as a minimax optimization problem, balancing interpretability and prediction closeness to the original model. They introduce new evaluation metrics tailored for graph interpretation and conduct extensive experiments across multiple datasets, demonstrating that FGAI significantly enhances stability and interpretability under various perturbations.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Discussion with respect to the interpretability study:\n- In fact, the interpretability of the attention-based GNNs may not be fully grounded[1];\n- The relation between interpretable GNNs such as [2,3] is unclear;\n- In fact, the rationale of the proposed metrics is heuristic and not clear, which is built upon the assumption that the perturbation won't change the importance of the neighbors. However, if the neighbors are already perturbed, it is natural to alter the attention distributions;\n\n2. The proposed approach is limited to attention-based GNNs and does not generalize to other types of GNN architectures, such as GCN or GraphSAGE:\n- An important category of attention-based GNNs, i.e., graph transformers, is neglected in experiments and analysis;\n- It would be beneficial to discuss the limitations and how the proposed framework can be generalized to more broader GNN architectures.\n\n3. The experiments are mostly conducted on citation networks, while it's unclear how the method generalizes under adversarial perturbations[4,5] and more complicated benchmarks such as link prediction, graph classification and heterophilous graphs.\n\n**References**\n\n[1] Understanding Attention and Generalization in Graph Neural Networks, NeurIPS'19.\n\n[2] Interpretable and Generalizable Graph Learning via Stochastic Attention Mechanism, ICML'22.\n\n[3] How Interpretable Are Interpretable Graph Neural Networks? ICML'24.\n\n[4] Adversarial Attacks on Graph Neural Networks via Meta Learning, ICLR'19.\n\n[5] Understanding and Improving Graph Injection Attack by Promoting Unnoticeability, ICLR'22.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "Un6OJMys4q", "reviewer": "Reviewer_2B51", "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. This paper targets the interpretation of attention-based GNNs, which is a meaningful topic not only for GNNs, but may also have an impact on the research of other attention-based models.\n\n2. The experiments are conducted from different perspectives, including different performance metrics, visualization results, and computational costs. \n\n3. Various datasets are included to validated the proposed method.\n\n\nWeaknesses:\n1. The performance reported in Table 1 is limited.\n\n2. The baselines are limited and old. In terms of attention-based GNNs, can graph transformers be also included for experiments?\n\n3. The targeted problem, although meaningful, seems to have limited practical influence in the field.", "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": "Targeting the problem that existing attention based GNNs will exhibit instability in interpretability due to the perturbations in training and testing stage, this paper proposes a novel notion named Faithful Graph Attention-based Interpretation (FGAI), which has four essential required properties in terms of stability and sensitivity to interpretation and final output. With this notion, the authors also proposes a strategy to obtain FGAI, which is basically a strategy to modify the traditional attention-based GNNs. Two novel metrics are also proposed to validate the proposed method.\n\nThe proposed strategy is experimented on various public datasets.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I would recommend including more analysis on the newly proposed attention-based GNNs.\n\nBesides, it would be better to discuss the practical influence of the proposed method.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dbO9rdsyOX", "reviewer": "Reviewer_ezoE", "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 introduces Faithful Graph Attention-based Interpretation (FGAI) with four well-defined properties addressing stability and sensitivity in both interpretation and output.\n2. The authors proposes new evaluation metrics (g-JSD, g-TVD, F-slopes) and tests across multiple datasets and model variants.\n\nWeaknesses:\n1. The proposed method involves multiple hyperparameters that need careful tuning for different datasets.\n2. While better than some baselines, the method still faces memory constraints on very large graphs.\n3. The paper could benefit from more theoretical analysis of why the proposed method works better than alternatives.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper addresses the instability of attention mechanisms in Graph Neural Networks when faced with perturbations like additional edges or nodes, despite their strong performance and interpretability benefits. To solve this, the authors introduce Faithful Graph Attention-based Interpretation (FGAI), which has four key properties relating to stability and sensitivity of both interpretation and output distribution. FGAI can be implemented as a simple modification to existing attention-based GNNs, and its effectiveness is evaluated using two newly proposed metrics for graph interpretation assessment. Experimental results show that FGAI provides more stable and reliable interpretations under various perturbations compared to traditional attention mechanisms.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Please refer to the weaknesses section.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work investigates the challenge of faithful interpretation for attention-based Graph Neural Networks (GNNs) like GAT and Graph Transformers under perturbations. The authors argue that conventional attention mechanisms in GNNs lack stability in interpretability and prediction when exposed to perturbations, such as added edges or nodes. Then, they propose a new framework called Faithful Graph Attention-based Interpretation (FGAI), which ensures stability and robustness while preserving the interpretability of attention mechanisms. The method is formulated as a minimax optimization problem, balancing interpretability and prediction closeness to the original model. They introduce new evaluation metrics tailored for graph interpretation and conduct extensive experiments across multiple datasets, demonstrating that FGAI significantly enhances stability and interpretability under various perturbations.

For the strengths, this work addresses an important issue: the instability of attention-based GNNs, particularly under perturbations, which is critical for faithful model interpretation. The proposed framework, FGAI, introduces a novel and well-defined formulation for stable and robust graph attention-based interpretation. The authors design new evaluation metrics (g-JSD and g-TVD) specifically tailored to assess the stability and interpretability of graph-based models, enhancing the clarity of their results. Extensive experiments on diverse datasets demonstrate the effectiveness of FGAI in improving stability and interpretability compared to baseline methods. The authors address reviewers' concerns well in their rebuttal. Thus, I would like to recommend accept as is.
Decision: Accept (poster)