Towards Robust Fidelity for Evaluating Explainability of Graph Neural Networks
Authors: Xu Zheng
Farhad Shirani
Tianchun Wang
Wei Cheng
Zhuomin Chen
Haifeng Chen
Hua Wei
Dongsheng Luo
Venue: ICLR 2024 poster (2024)
Keywords: Graph Neural Networks
Graph Explanation
XAI
Primary area: visualization or interpretation of learned representations

Abstract: Graph Neural Networks (GNNs) are neural models that leverage the dependency structure in graphical data via message passing among the graph nodes. GNNs have emerged as pivotal architectures in analyzing graph-structured data, and their expansive application in sensitive domains requires a comprehensive understanding of their decision-making processes --- necessitating a framework for GNN explainability. An explanation function for GNNs takes a pre-trained GNN along with a graph as input, to produce a `sufficient statistic' subgraph with respect to the graph label. A main challenge in studying GNN explainability is to provide fidelity measures that evaluate the performance of these explanation functions. This paper studies this foundational challenge, spotlighting the inherent limitations of prevailing fidelity metrics, including $Fid_+$, $Fid_-$, and $Fid_\Delta$. Specifically, a formal, information-theoretic definition of explainability is introduced and it is shown that existing metrics often fail to align with this definition across various statistical scenarios. The reason is due to potential distribution shifts when subgraphs are removed in computing these fidelity measures. Subsequently, a robust class of fidelity measures are introduced, and it is shown analytically that they are resilient to distribution shift issues and are applicable in a wide range of scenarios. Extensive empirical analysis on both synthetic and real datasets are provided to illustrate that the proposed metrics are more coherent with gold standard metrics.

Published as a conference paper at ICLR 2024
TOWARDS ROBUST FIDELITY FOR EVALUATING EX- PLAINABILITY OF GRAPH NEURAL NETWORKS
Xu Zheng", Farhad Shirani">, Tianchun Wang", Wei Cheng', Zhuomin Chen', Haifeng Chen', Hua Wei", Dongsheng Luo 163
"Scoool of Computing and Information Sciences, Florida International University, US
"College Information Sciences and Technology, The Pennsylvania State University, US NEC Laboratories America, US
*School of Computing and Augmented Intelligence, Arizona State University, US {xzhen019) 9, fsh rani, zchen051, dluo)efiu.ce ckw53566psst edu (weicheng, ha feng) (@nec-laaee com hua. wei
ABSTRACT
Graph Neural Networks (GNNs) are neural models that leverage the dependency structure in graphical data via message passing among the graph nodes. GNNs have emerged as pivotal architectures in analyzing graph-structured data, and their expansive application in sensitive domains requires comprehensive understand- ing of their decision-making processes - necessitating a framework for GNN explainability. An explanation function for GNNs takes pre-trained GNN along with a graph as input, to produce a 'sufficient statistic' subgraph with respect to the graph label. A main challenge in studying GNN explainability is provide fidelity measures that evaluate the performance of these explanation functions. This paper studies this foundational challenge, spotlighting the inherent limitations of prevailing fidelity metrics, including Fid,. Fid_, and Fida. Specifically, a definition of explainability is introduced and it is
formal, information-theoree shown that existing metrics often fail to align with this definition across various statistical scenarios. The reason is due to potential distribution shifts when sub- graphs removed in computing these fidelity measures. Subsequently, robust class of fidelity measures are introduced, and is shown analytically that they are resilient distribution shift issues and are applicable in wide range of scenarios. Extensive empirical analysis on both synthetic and real datasets are provided to illustrate that the proposed metrics are more coherent with gold standard metries. The source code is available at https://trustaiis-aala http://ruuaaiss-lllguuuubbiiiiii github.iofffidelit
INTRODUCTION
Graph Neural Networks (GNNs) have become a cornerstone for processing graph-stree graph-structured data, achieving impressive outcomes across various domains such as node classification and link predic-
tion (Kipf & Welling 2017 Hamilton et al. 2017 Veličković et al.] 2018 Scarselli et al. 2008). However, with their proliferation in sensitive sectors like healthcare and fraud detection, the demand for understanding their decision-making processes has grown significantly (Zhang et al., 2022a Wu et al. 2022 Li al. 2022). To address this challenge, explanation techniques have been proposed for GNNs, most commonly focusing on identifying a subgraph that dominates the model's prediction in post-hoc sense (Ying et al. 2019 Luo et al. 2020 Yuan al. 2021).
In the design and study of explainable GNNs, both model design and choice of evaluation metrics are important. While most efforts have primarily been made to develop new network architectures and
optimization objectives to achieve more accurate explanations (Ying et al. 2019 Luo et al. 2020
'hese authors contributed equally to this work.
Corresponding author

---

Published as a conference paper at ICLR 2024
Yuan et al.) 2021). in this paper, we underscore the critical importance of choosing the right evaluation metrics for the achieved explanations. In an ideal scenario, quantitative evaluation of an explanation subgraph can be achieved by comparing it with a gold standard ground truth explanation (Ying) et al. 2019). Yet, in real-world applications, such ground truth explanation subgraphs are rarity, often making direct comparisons impracticable. In lieu of this, surrogate fidelity metrics, namely Fid4, Fid_, and Fida, have been included to gauge the faithfulness of explanation subgraphs. At its core, the intuition driving such fidelity metrics is straightforward: if subgraph discriminative to the model, the prediction should change significantly when it is removed from the input. Otherwise, the prediction should be maintained. Hence, Fid+ is defined as the difference in accuracy (or predicted probability) between the original prediction and the new predictions of -on-explanation subgraph which is obtained by masking out the explanation subgraph (Pope et al. 2019, Bajaj et al. 202T), and Fid_ measures the difference between predictions of the original graph and explanation subgraph YYuan et al. 2022). As prevailing standards, these Fidelity metrics and their variants have been widely used in existing popular platforms, such as GraphFramEx [Amara et al. (2022),
GraphXAI (Agarwal et al. 2023). GNNX- BENX-BENCH (Kosan et al. 2023). 3 and DIG (Liu et al. 2021)
Although intuitively correct, we argue that the aforementioned Fidelity metrics come with significant backscck due to the impractical assumption that the to-be-explained model can make accurate predictions of the explanation subgraph (in Fid_.) or non-explanation subgraph (in Fid,). This does not hold in a wide range of real-world scenarios, because when edges are removed, the resultant subgraphs might be Out Of Distribution (OOD) (Fang et al., 2023c b). For example, in MUTAG dataset (Debnath et al. 1991), each graph is a molecule with nodes representing atoms and edges describing the chemical bonds. The functional group NO2 is considered the dominating subgraph that causes a molecule to be mutagenic. The explanation subgraph only consists of 2 edges, which much smaller than whole molecular graphs. Such disparities in properties introduce distribution shifts, putting the Fidelity metrics on shaky grounds, because of the violation of a key assumption in machine learning: the training and test data come from the same distribution (Hooker et al. 2019).
To build an evaluation foundation for eXplainable AI (XAI) in the graph domain, In this paper, we investigate robust fidelity measurements for evaluating the correctness of explanations. There are several non-trivial challenges associated with this problem. First, the to-be-explained GNN model is usually evaluated as a black-box model, which cannot be re-trained to ensure the generalization capacity (Hooker et al. 2019). Second, the evaluation method is required to be stable and ideally deterministic. As a result, complex parametric methods, such as adversarial perturbations (Hase et al.) 2021 Hsieh et al. 2021) , are not suitable as the results are affected by randomly initiated parameters.
We provide an information theoretic framework for GNN explainability. We define an explanation graph as subgraph of the input that satisfies two conditions: 1) the explanation graph is (almost) sufficient statistic of the input graph with respect to the output label, and 2) the size of the explanation graph is small compared to the input graph. Based on this, we provide two notions of explainability, namely, explainability of a classification task and explainability of a classifier for the task (Definitions 3. We quantify the relation between these two notions for low-error classifiers and classification tasks (Theorem l]. Computing the resulting information theoretic fidelity measure requires knowledge of the underlying graph statistics, which is not possible most real-world scenarios of interest. We propose a generalized class of surrogate fidelity measures that are robust to distribution shift issues in a wide range of scenarios (Proposition A.4. Our contributions are summarized as follows.
We pioneer spotlighting the inherent shortcomings of widely accepted evaluation methodologies in the explainable graph learning domain.
Grounded in solid theoretical underpinnings. we introduce novel evaluation metrics that are resilient to distribution shifts, enhancing their applicability in real-world contexts. This metric notably approximates evaluations conducted with ground truth explanations more closely.
Through rigorous empirical analyses on a diverse mix of synthetic and real datasets, we validate that our approach resonates well with gold standard benchmarks.
PRELIMINARIES
Random Graphs: We parameterize (random) labeled graph G' by tuple (V,,, A), where i) {11, U2, Un) } is the vertex set"] ii) E C V x is the edge set, iii) is the graph class label
Wee use node and vertex interchangeably.
2

---

Published as a conference paper at ICLR 2024
taking values from finite set of classes V, iv) X E Raxd is the feature matrix, where the i-th row of X, denoted by X; E !IId xd. is the d-dimensional feature vector associated with node 84 é E [n]. and v) A {0, 1 1 is the adjacency matrix. The graph parameters (Y, A, X) are generated according to the joint probability measure PY,AX Note that the adjaceney matrix determines the edge set &, where Aij
if (vi, vy) E E, and A.j denote the number of edges of G. Throughout this paper, we use lower-case letters, such as X, and a, represent realizations of the random objects G, Y, X and A, respectively. Given labeled graph G = (V. E,,;Y,, X, A), we denote the corresponding graph without label as G, and parameterize it by (V,E; X. A). The induced distribution of G is represented as P. and its support by G. Graph and Node Classification Tasks: In the classification tasks under consideration, we are given:
otherwise. We write |G| and |ε| interchangeably to
A set of labeled training data T = [(G,, Y.JI V E [[7]),, where (Gi, Y2) corresponds the i-th graph and its associated class label. The pairs (G,, i [[T]] are generated independently according to an identical joint distribution induced by Py.x.A-
A classification function (GNN model) f(.) trained to classify unlabeled input graph G into its class Y. It takes G input and outputs probability distribution Py on alphabet y. The reconstructed label Y is produced randomly based on Py.
In node classification tasks, each graph G2 denotes K Khhhp sub-graph centered around node uy with a GNN model f trained to predict the label for node U; based on the node representation of o; learned from G, whereas in graph classification tasks, G3 is random graph whose distribution is determined by the (general) joint distribution PY...z. with the GNN model f(-) trained to predict the label for graph G based on the learned representation of G. Formally we define classifier as follows.
Definition I (Classifier). For a classification task with underlying distribution Pv,X.A, a classier is function f : G - Ay. For given O, the classifier is called e-accurate if P(Y +Y) Se where Y produced according to probability distribution f(G).
2.1 INFORMATION THEORETIC MEASURES FOR QUANTIPYING EXPLAINABILITY
In this section, introduce two different but related notions of explainability, namely, explainability of a classification task, and explainability of a classifier for a given task. The interrelations between these two notions are quantified in the subsequent sections.
Given a classification task with underlying distribution Xy, an explanation function for the task is a mapping V : G + (Vezp, Eezp) which takes an unlabeled graph G = (V, E; X, A) as input and outputs subset of nodes Veap S V and subset of edges Eeep S Vezp Veap- Loosely speaking, good explanation (Vezp. Eexp) is subgraph which an (almost) sufficient statistic of G with respect Ri O, where we have defined
to the true label Y, i.e., I(;; w(aa))
Py. Glgexp S G)
(a) (geap) I(Y;GIL - =Puw
Σ Py.a Algeap S log Py (vlgerp C v.g
C
geep
In practice, a desirable explanation function is one whose output size is significantly smaller than the original input size, i.e., (G))) < (E(())). This is formalized below.
Definition 2 (Explainable Classification Task). Consider a classification task with underlying distribution PY.X.A. An explanation function for this task is a mapping vi - 2 x 2 For a given pair of parameters K. E [0,1] and E N, the task is called (s, -exeellaaiiaaale there exists an explanation function V G > (Verps Eeep) such that:
I(Y: IY: S K.
i1)
Eo Eo S..
A similar notion of explainability can be provided for given classifier as follows.
Definition 3 (Explainable Classifier). Consider a classification task with underlying distribution Py.x.A A and classier Ō Ay. For a given pair of parameters Ç E [0, and E N. the
2((Y G v can be alternatively written as (I(Y; S G)), where P, Pyae Py
3

---

Published as a conference paper at ICLR 2024
classifier f(-) is called (s, -xeexainiabe if there exists an explanation function (() such that
I(F:G SC.
ii) Ee(1p S
where Vi (G) (Veup. Eeep) and Y is generated according to the probability distribution f(G). The explanation function (-) is called an (s, () explanation for f(.).
3 FIDELITY MEASURES FOR EXPLAINABILITY
3.1 EXPLAINABLE TASKS VS EXPLIANABLE CLASSIFIERS
should be noted that the explainability of the classification task (Definition) 2 does not imply nor is it implied by the explainability of classifier for that task (Definition For instance, the trivial classifier whose output is independent of input explainable for any task, even if the task is not explainable itself. In this section, we characterize a quantitative relation between these two notions of explainability. To keep the analysis tractable, we introduce the following condition on (-()):
Condition 1: Vg.
S g = (3g (g)
(1)
Condition holds for the ground-truth explanation in many of the widely studied datasets in the explainability literature such as BA-2nn BA-2motifs, Tree-Cycles. Frie-Grid, and MUTAG datasets which are discussed Section 5 An important consequence of Condition is that (-) satisfies the condition, then 7(Y; (Z)) = I(;; G (G)). In the following, under the assumption of Condition 1, we show that the classifier has a low error probability, then its explainability implies the explainability of the underlying task. Conversely, we show that if the task is explainable, and its associated Bayes error rate is small, then any classifier for the task with an етrоr close to the Bayes error rate is explainable. The following provides the main result of this section.
Theorem (Sufficient Conditions for Equivalency of Task and Classitier Explainability). Con- sider a classification task with underlying distribution Py,X,A, A parameters Ç, K. E [0, 1}, and an integer s E N. Then,
1. If there exists classifier f()) this task which is e-accurate and (s, expllanabbe with the explanation function satisfying Condition 1, then, the task is (s, exxpllnnale, where
K' S + he(e) + e log (DV) - 1);
and (p(p) 2 -plogg- (1- p) log 1 p.p E [0, 1] denotes the binary entropy function. Particu- larly, K + 0 -
2. If the classification task is binary (Le. | = 2), is (s, -)x-epaaiiaall with an explanation function satisfying Condition 1, and has Bayes error rate equal to c", then any (c" + 8)-accurate classifier h(-)) is (s,1)=a expllainae,,,, where
r A hb(() +T, _ (2V26* + V
E _ 8 + Cmar (E",
2
8 (0,9c* eman ( (k),
and emaz (-) is defined Proposition I
Particularly, 1 0 as d, E-, x
The proof of Part 1) follows from the definition of explainability in Definitions 2 and B] and Fano's inequality. The proof of Part 2) uses the following intermediate result, which proves the existence of an explainable classifier for any explainable task, whose error is close to that of the Bayes classifier.
Proposition 1 (Existence of Accurate and Explainable Classifiers for Explainable Tasks), Con- sider a classification task with underlying distribution Py.x.A A. parameters K, E [o, 1), and an integer N. Assume that the task is (s, expplaaiiee with an exaplantion function satisfying Condition 1. Further assume that the classification task has a Bayes error rate equal to e". Then, there exists an e-accurate and (s, expplaiiiee classifier ((), such that
S Craz (c", R3),
(2)
4

---

Published as a conference paper at ICLR 2024
where we have defined
Emoa (z, v) 2 arg max((2ee) S ho(a) + + y}
2,y E [0,1]
1+ 1
CRF(2) A
1 (1 - z)
-(= 2 (1 -2 z)
2 E (0,1)
In particular, c - as C², -
The complete proof of Proposition is provided in Appendix A.1 and the proof of Theorem I provided in Appendix A.2
3.2
SURROGATE FIDELITY MEASURES FOR QUANTIFYING EXPLAINABILITY
Definitions 2 and D provide intuitive notions of explainability along with fidelity measures expressed
mutual information terms, however, in most practical applications it is not possible quantitatively compute and analyze them. To elaborate, let us consider the mutual information term in condition i) of Definition 3 Estimating the mutual information term, 1 (Y; G I (G)) is not practically feasible
in most applications since G has large alphabet size. To address this, prior works have considered alternative surrogate fidelity measures for evaluating the performance of explanation functions. At high level, an ideal surrogate measure Fid" V) + R must satisfy two properties: i) The surrogate fidelity value Fid V must be monotonic with the mutual information term T[ v()) given in Definition 3 so that a 'good' explanation function with respect to the surrogate fidelity measure is 'good' under Definition 3 and vice versa, and ii) there must exist an empirical estimate of Fid" (J, V with sufficiently fast convergence guarantees so that the surrogate measure can be estimated accurately using a reasonably large set of observations. These conditions formalized in the following two definitions.
Definition 4 (Surrogate Fidelity Measure). For classification task with underlying distribution Pv, a (surrogate) fidelity measure mapping Fid (J,V) + R22, which takes a puir consisting of a classification function I(.) and explanation function V-)) as impul, and outputs non-negative number. The fidelity measure is said to be well- well-behaved for a set of classifiers F and explanation functions S for all pairs of explanation functions V U22 E S and classifiers f F, we have:
I(; ()) S V.(G) = Fid(J, v2) S Fid(J, 11).
The condition in equation requires that better explanation functions in the sense of Definition must have higher fidelity when evaluated using the surrogate measure.
Definition 5 (Rate of Convergence Guarantee). Let Ti [[G,, Yj)li < Li),i N be a sequence of sets of independent and identically distributed observations for a given classificution problem. A fidelity measure Fid(-.-) is said be empirically estimated with rate of convergence 3 if there exits a sequence of functions Hn : Ta +> Fid,, 72 E such that for all > 0, we have:
P(FFidf,, 4) Fidn (J, VII E) On
for all classifiers f and explanation functions V.
3.2. THE OOD PROBLEM IN EVALUATING SURROGATE FIDELITY MEASURES
One class of surrogate fidelity measures has been considered in several recent works (e.g., (Pope)
ct al. 2019 Yuan et al. 2022) are the Fid4, Fid_, and FidA measures:
Fid4 e -
Fid_
Fida A Fid, Fid_, (4)
where P(-) is the distribution given by f(G), (+(-) is the distribution given by f(G, - V (T())))
p-(-) is the distribution given by (VV().)), G (V() is the subgraph with edge set E Eeep for
5

---

Published as a conference paper at ICLR 2024
V (G) (Vezp: Eeap), and T is a set of independent observations T= {(G,, i, .ITI.. As mentioned in Yuan et al. 2022), these fidelity measures can be empirically estimated by
IT Σ IT
Fid+
A
E P(u) - Pt (v)). T
1
Fid_ -
P(y)) (w)),, Fid Fid+ Fid_.
It should be noted that the rate of convergence of this empirical estimate is B = 1/2 (e.g., using the Berry- Esseen theorem (Billingsley 2017). The following proposition shows that these measures are well-behaved for class of deterministic classification tasks and completely explainable classifiers.
Proposition 2 (Well-Behal Behavednadedss of Fida on Deterministic Tasks). Consider deterministic classification task for which the induced distribution Pg has support G consisting of all graphs with n E N vertices, the graph edges are jointly independent, and E Zuxd, where Z is a finite set. Further assume that the graph label is Y [gexp E G) for fixed subgraph Gezp- that the task is deterministic. Let [(G) = (gezz C GG) be the O-correct classifier. Let S { [V [0, 1]} be a class of explanation.functiinn,, functions, where p(),(0) = Depz Meep E (]) = p and p(V = & Deap E g) = 1 p.p E [0, 1). The Fida fideiity measure is well-behaved for all explanation functions in S.
The proof is provided in Appendix A.3
Proposition] shoow that Fida is well-behaved in a specific set of scenarios, where the task is deterministic and the classifier is completely explainable. However, we argue that it is not well-behaved in a wide range of scenarios of interest which do not have these properties. This is due the OOD issue mentioned in the introduction. To elaborate, for a good classifier, which has low probability of error, the distribution ((G) must be close to Prie(-IG) on average, i.e., (f(ddv P. (-IG)) should be small, where drv denotes the total variation. As a result, P(Y) in equation 4 close (YIG) on average. However, this is not necessarily true for the p+(Y) and P (Y) terms. The reason is that the assumption (y x O only ensures that f(G) is close to Priz(- (7) for the rypical realizations of G. However, T ((() and (G) are not typical realizations. For instance, in many applications. it is very unlikely or impossible to observe the explanation graph in isolation, that is, to have T = (G). As a result, (G) and Py (G)). respectively, and Fid,,, Fid_ and FídA are not well-behaved. This is observed in our empirical analysis in Section 5 and the notion is analytically investigated in a toy-example in Appendix
pt (Y) and p (Y) are not good approximations for Pria(Y|G
3.2.2 A ROBUST CLASS OF SURROGATE FIDELITY MEASURES
Generally, in scenarios where To (G) and T - Vp (G) are not typical with respect to the distribution of G. the Fida measure may not be well-behaved. We address this by introducing a class of modified fidelity measures by modifying the definitions of Fid. and Fid_ in equation To this end, we define the stochastic graph sampling function E. : G + Ga with edge erasure probability a E [o. 1]. That is, (-) takes a graph G as input, and outputs a sampled graph G. whose vertex is the same as that of G, and its edges a and erased with probability 1 - a, independently of all other edges. We introduce the following generalized class of surrogate fidelity measures, and show that they are robust to OOD issues in wide range of scenarios:
sampled from G such that each edge is included with probability
Fiday, A B((PY)) Pon:- (Y)),
Fida,,- A AE(P(Y) -aar- (Y)),
(5)
Fida. A 2 Fidd.t - Fidoz.-
(6)
where a,, 02 E 10, P(.) is the distribution given by f(G), ponnt()) (.) is the distribution given by J(G - Fan (V))))). paz.-()) (.) is the distribution given by S(Fag G v(T)) + V(G)).
Note that if 01 and 0g2 = O. we recover the original fidelity measures, i.e., Fid,, + Fid4, Fida. On the other hand, if Q1 = 0 and 0g = 1, we have T - Ea, (T) Ea,(C (G) + (T) = G. Consequently, in this case there would be no OOD issue, however, the resulting fidelity measure is not informative since (ff v) = 0, for all classifiers and explanation functions V. Loosely speaking, if (yle(y))), y E E is 'smooth" as
Fido - Fid_, and Fi

---

Published as a conference paper at ICLR 2024
function of g, then OOD does not manifest and 01 1, 02 0 yields suitable fidelity measure (e.g., Proposition 2). On the other hand if (vlz) y E y is not smooth, then a1 < 1 and dg > would yield a suitable fidelity measure as this choice avoids the OOD problem. The generalized fidelity measures be empirically estimated by
T
Fidan e,.
1
Σ
Σ &CEer 18|=k2
Pe) - Pe)-E(Us)
| |A' Ecopl (a1)l
==1
T
Fiday,e--
1
Σ
Σ
Pe) - Peueuu (vi)
[T|
:=1 | |AEE
ECE, 1E|=/2
Fida Fidariet Fidaz,a,tt
where c <> O, Be N, a, c > 0 denotes the interval [e(a - c), E(a + <)}, the set A5(a), N, E [0, 1 is the set of e-typical binary sequences of length é with respect to the Bernoulli distribution with parameter a, i.c.. Aa(a) & {af 13 Ei=
1) al S e}. the distribution Pe(Bs (B:) is the probability of y under the distribution f(Ge), where Gg is the subgraph of G with edge set restricted to E, and T [G,, 22 E [[T is the set of observations, where &, is the edge set of Ge, i [7]. Using the Chernoff bound and standard information theoretic arguments, it can be shown that for fixed (11 02 and Olv [8 these empirical estimates converge their statistical counterparts with rate of convergence = 2 as [T| + oo for large input graph and explanation sizes (e.g., (Csiszár & Körner 2011)).
We show that F is well-behaved for a general class of tasks and classifiers, where the original Fidelity measure, Fid1,0,4 a is not well-behane Specifically, assume that there exists set of motifs Ty: E V, such that
1
if J, S and Vy ty Jy Eg. yy: & G. CG
P(Y = y
0
1 D
otherwise.
Furthermore, given E N and é [0, 1]. we assume that the graph distribution Pa and the trained classifier fs(-), satisfy the following conditions. The graph has n vertices. There exists a set & of input graphs, called an c-typical set, such that Po(0) 1 c, and
P(s(o) S
d 1.
where (*)) is the optimal Bayes classifier, i.e., (O) = y yf Jy S G. and f* arg max, Py otherwise The distance between the graph 9 and the set of graphs G is defined as d(G, 7) 2 ming' eg d d' g. and the distance between two graphs is defined as their number of edge differences. Proposition Behaedeehsssss of Fida, Fidelity Measure). In the classification scenario described above, Consider the class of explanation functions S, which consists of stochastic mappings :g + Geup where P(Gezp = J, = g) = for any & such that Bly Iy. E 9 and Geup = Φ. otherwise. Then,
Fidai. 2c - P(A)
k+1 111 -01--((A)--)))))) - 1 P(B') - )a)
1-c ((1 - + max (v)) +1
Fidaz,- <C P(A)(1 2 ){
12
k )
P(A)
Fidmi.m. 2 - PP(A) P(B')
1 1-c ((1 p pmax Pr()))+
) + P(A) (1 2
k+1
'The assumption in equation captures the infrequency of accurrence of atypical inputs in the training set, which incrcases chance of missclassifcation for those inputs and hence gives rise to OOD issues.
7

---

Published as a conference paper at ICLR 2024
2n 02 - 1- 2n., < 81 miny Byyl A is the event that Bly : By S G. and B' is the event that Σi=1 X; k, where X; are independent and identically distributed realizations of a Bernoulli variable with parameter 01. Particularly, as k, + oo and d,e 0 such that k onn) and 8 o( Fida, an. becomes monotonically increasing in p. Consequently, there exists a non-zero error threshold Eth > 0, such that Fida an, is well-behaved for all S Cth-
where c" is the Bayes error rate, a1 _ &
The proof is provided in Appendix A.4
4 RELATED WORK
Explainable GNNs. To interpret GNN models. previous works (Ying al., 2019 Luo al. 2020
Yuan et al. 2020; 2022; 2021; Lin et al. 2021 Wang & Shen [023] Miao et al. 2023 Fang et al. 2023c: Xie et a 2022 Ma et al.) 2022) tried different methods to offer interpretabiliity According to granularity, these explanation methods can generally be divided into two categories: i) instance-level
explanation (Ying et al. 2019; Zhang et al. 2022b] Xie et al. 2022). which offers explanations for every instance by recognizing important substructures; and ii) model-level explanation (Yuan et al. 2020; Wang Shen 2023 Azzolin et al. 2023), which is designed for providing global decision rules learned by target GNN models. Within these methodologies, these methods can be classified as
post-hoc explanations (Ying et al. 2019 Luo et al. 2020 Yuan et al.. 2021) and self-explainable
GNNs (Baldassarre & Azizpour 2019 Dai & Wang 2021 Miao et al. 2022). where the former uses an extra GNN model to elucidate the target GNN and the latter offers explanations while making
predictions. For comprehensive survey on this topic, please refer to (Yuan al., 2022).
Evaluation Metrics for Explainable GNNs. To comprehensively evaluate the explanations, both anecdotal evidence and quantitative measures, such as explanation accuracy, faithfulness, efficiency, completeness, consistency, are jointly adopted in the literature (Nauta et al. 2022). When ground- truth explanations are unavailable, fidelity measures and their variants are routinely adopted to evaluate the quality of explanations (Yuan et al. 2021). For example, DIG (Liu et al.) (021 and GraphFramEx (Amara et al., 2022) include both Fid, and Fid-; GraphXAI (Agarwal al. 2023)
adopts a variant that utilizes Kullback-Leeibh (KI.) divergence score to quantify the distance between predictions of the original graph and subgraph. to evaluate both factual and counterfactual explanations. However, the OOD problem of subgraph
(Kosan et al. (022)) uses Fidelity
explanations is overlooked in these platforms. Concurrently to this work, OAR evaluates post-hoc
explanation subgraphs via analyzing adversarial robustness (Fang et al. 2023a) GInX-Eval evaluates with a removing and fine-tuning strategy (Amara et al. 2023).
EXPERIMENTS
In this section, we empirically verify the effectiveness of the generalized class of surrogate fidelity measures. We also conduct extensive studies to verify theoretical claims. Four benchmark datasets with ground truth explanations are used for evaluation, with Cree-Cireles, and Tree-Grid (Ying et al. 2019) for the node classification task, and BA-2motifs (Luo al.) 2020) and MUTAG (Debnath et al. 1991 for graph classification. We consider both GCN and GIN architectures (Ying et al.) 2019 Xu let al. 2019) as the models be explained. Detailed experimental setups, full experimental results, and extra experiments are presented in the Appendix.
5.1 QUANTITATIVE EVALUATION BY COMPARING TO THE GOLD STANDARD
In adopted datasets, motifs are included which determine node labels or graph labels. Thus, the relationships between graph examples and data labels are well-defined by humans. The correctness of an explanation can be evaluated by comparing to the ground truth motif. Previous studies (Ying et al., 2019 Luo et al. 2020) usually model the evaluation as edge classification problem. Specifically, edges in the ground-truth explanation are treated as labels, and importance weights given by the explainability method viewed prediction scores. Then, AUC scores are considered the metric for correctness. In this section, we use a more tractable metric, edit distance (Gao et al., 2010) to compare achieved explanations with the ground- truth motifs a Gold Standard metric.
Consider an input graph Gj and let Grapp be the ground truuh explanation subgraph, i.c., the motif. We construct set of explanation functions, with varying qualities, to evaluate the well sell-behavedness
8

---

Published as a conference paper at ICLR 2024
Table I: Spearman correlation coefficient between metric and gold standard edit distance.
Dataset
Fid, 4
Fida..:
Fid
Fidas.
Fida
Fida: .... A
AUC
Tyce-Cycles
0.229
-0,990
-0.210
0.990
0.105
-0,990
-1.000
Tree-Grid
0.095
-1,000
0.457
1.000
-0.781
-1.000
-1.000
GCN
BA-2motifss
-0.924
-1.000
0.819
1.000
-0,990
-1.000
-1000
MUTAG
-0.190
-1.000
-0.276
1.000
-0.105
-1.000
-I 1,000
Tree-Cycles
0.200
-1,000
-0,229
1.000
-0,286
-1,00
-.000
Tree-Grid
1.000
1,000
-1.000
-0.993
1,000
1,000
-1.000
GIN
BA BA-2motif's
-0,838
-1.000
0.905
1.000
-1.000
-1.000
-1.000
MUTAG
-1.000
-1.000
0.886
1.000
-0.990
-1.000
-1.000
of the proposed fidelity measures. To elaborate, for a given B1, 82 E [0, 1], we construct an ex- planation function ,,,,,() (-) by random IID sampling of the explanation subgraph edges, and the non-explanation subgraph edges, with sampling rates 31 and 82, respectively. That is, to construct Ve,,% (G.), remove B1 ratio of edges from ground-truth explanation Gieop via random III) sampling, and randomly add 32 E [0, 1] ratio of edges from G, Gap Gr,zp by random IID sampling from the con-exlannttion subgraph. Clearly, the explanation function should receive better fidelity score for smaller (51, 82). We sweep 31 and 32 in the range [0, 0.1, 0.3. 0.5, 0.7, 0.9], and for each combination (B), 32). we randomly sample 10 candidate explanations. We adopt the proposed Fida,,+ Fidng.- F Fido where we have taken oj 1 02 0.1, as well as their counterparts to evaluate their qualities. For each combination, we calculate the average metric scores.
As analyzed in previous works (Yuan et al. 202T), fidelity measurements ignore the size of the explanation. Thus, redundant explanations are usually with high Fid, and low Fid_ scores. In the extreme case, with the whole input graph as the explanation, fidelity measures achieve the trivial optimal scores. This limitation is inherent and cannot not solved with the proposed metrics. To fairly compare the proposed metrics with the original ones, for each 82, given a fidelity measurement, we the Spearman correlation coefficient (Myers et al., 2013) between it and the gold standard edit distance to quantitatively evaluate the quality of the metric. Then, we report the average correlation scores Table I The number of sampling our measurements are 50.
We have the following observations in Table I First, Fidai,+ consistently yields correlation scores near 1.0 with the edit distance. It signifies robust inverse relationship between the two metrics. This is in agreement with the requirement in equation 3 In contrast, the original Fid, metric exhibits mixed results with half-positive and half-negative correlations. This inconsistency Fid,, underscores the potential superiority and consistency of our proposed Fid in aligning closely with the edit distance across various datasets. Moreover, the proposed Fidaz.- is strongly positively related to gold-standard edit distance compared to the original Fid.. we have similar observations in Fide and Fid Third, we observe that the AUC score of edge classification, which is used in previous papers, is perfectly aligned with the gold standard edit distance, which verifies the correctness of using AUC as the metric. Last, all fidelity measurements fail to evaluate the GIN classifier the Tree- Grid dataset. The potential reason is that GIN was designed for graph classification and its generalization performance on node classification is limited in Tree-Grid dataset.
CONCLUSION
In this paper, we have comprehensively explored the limitations intrinsic to prevalent evaluation methodologies in the realm of explainable graph learning, emphasizing the pitfalls of conventional fidelity metrics, notably their vulnerability to distribution shifts. By delving deep into the theoretical aspects, we have innovated novel set of evaluation metrics grounded in information theory, offering resilience to such shifts and promising enhanced authenticity and applicability in real-world scenarios. These proposed metrics have been rigorously validated across varied datasets, demonstrating their superior alignment with gold standard benchmarks. Our endeavor contributes to the establishment of a more robust and reliable machine-learning evaluation framework for graph learning.
ACKNOWLEDGMENTS
This project was partially supported by NSF grants IIS-2331908 and CCF-2241057. The views and conclusions contained this paper are those of the authors and should not be interpreted as representing any funding agencies.

---

Published as a conference paper at ICLR 2024
REFERENCES
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating explainability for graph neural networks. Scientific Data, 10(144), 2023. URL https:/wwww.natueecoomm cow.s//icccm/m//ec/eeccee
$41597-023-01974.
Kenza Amara, Zhitao Ying. Zitao Zhang, Zhichao Han, Yang Zhao, Yinan Shan, Ulrik Brandes, Sebastian Schemm, and Ce Zhang. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. In The First Learning on Graphs Conference, 2022. URL
Kenza Amara, Mennatallah El-Assady, and Rex Ying. GInx-eval: Towards in-distribution evaluation of graph neural network explanations. In XAI in Action: Past, Present, and Future Applications, 2023. URL http:s//oeeceoivwwwweeee/////o/p
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. Global explain- ability of gnns via logic combination of learned concepts. In Proceedings of the International Conference on Learning Representations (ICLR), 2023.
Mohit Bajaj. Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. Advances in Neural Information Processing Systems, 34:5644 5655, 2021.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional networks. arXiv preprint arXiv: 13686, 2019.
Patrick Billingsley, Probability and measure. John Wiley Sons, 2017.
Thomas M Cover. Elements of information theory. John Wiley Sons, 1999.
Imre Csiszár and János Körner. Information theory: coding theorems for discrete memoryless systems. Cambridge University Press, 2011.
Enyan Dai and Suhang Wang. Towards self- self-explainable graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 302-311, 2021.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Corwin Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2):786-797, 1991.
Luc Devroye, László Györfi, and Gábor Lugosi. A probabilistic theory of pattern recognition, volume 31. Springer Science & Business Media, 2013.
Junfeng Fang, Wei Liu, Yuan Gao, Zemin Liu, An Zhang, Xiang Wang, and Xiangnan He. Evalu- ating post-hoe explanations for graph neural networks via robustness analysis. Thirty-seventh Conference Neural Information Processing Systems, 2023a. URL http:://oooameriie.ee///uumm id=elD334PPhAg
Junfeng Fang, Wei Liu, An Zhang, Xiang Wang, Xiangnan He, Kun Wang, and Tat-Seng Chua. On regularization for explaining graph neural networks: An information theory perspective, 2023b. URL http:///ppaaawoowe...ee/////mm/d
Junfeng Fang, Xiang Wang, An Zhang, Zemin Liu. Xiangnan He, and Tat-Seng Chua. Cooperative explanations of graph neural networks. In Proceedings of the Sixteenth ACM International Conference on Web Search and Data Mining, pp. 616-624, 2023c.
Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance. Pattern Analysis and applications, 13:1131129, 2010.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
10

---

Published as a conference paper at ICLR 2024
Peter Hase, Harry Xie, and Mohit Bansal. The out-of-distribution problem in explainability and search methods for feature importance explanations. Advances in neural information processing systems, 1135600-366,,, 2021.
Sara Hooker, Dumitru Erhan, Pieter-Jan Kindermans, and Been Kim. A benchmark for interpretability methods in deep neural networks. Advances in neural information processing systems. 32, 2019.
Cheng- Yu Hsich, Chih- Kuan Yeh, Xuanqing Liu, Pradeep Kumar Ravikumar, Seungyeon Kim, Sanjiv Kumar, and Cho-Jui Hsieh. Evaluations and methods for explanation through robustness analysis. In International Conference on Learning Representations, 2021. URL hnttpsss//opennevveew.eell forum"dd=44XXpCCGGNN
Neil lethani, Adriel Saporta, and Rajesh Ranganath. Don't be fooled: label leakage in explanation methods and the importance of their quantitative evaluation. In International Conference Artificial Intelligence and Statistics, pp. 8925-8953. PMLR, 2023.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. URL https://openreview.nee/
Jorum'id-SJU4ayYY Ygl
Mert Kosan, Samidha Verma, Burouj Armgaan, Khushbu Pahwa, Ambuj Singh, Sourav Medya, and Sayan Ranu. Gnnx-bench: Unravelling the utility of perturbation-basee gnn explainers through in-depth benchmarking. arXiv preprint arXiv:2310.01791 2023.
Vladimir A Kovalevsky. The problem of character recognition from the point of view of mathematical statistics. Character Readers and Pattern Recognition, pp. 3-30, 1968.
Mark A Kramer. Nonlinear principal component analysis using autoassociative neural networks. AIChE journal, 37(2):233-22 243, 1991.
Yiqiao Li, Jianlong Zhou, Sunny Verma, and Fang Chen. A survey of explainable graph neural networks: Taxonomy and evaluation metrics. arXiv preprint arXiv:2207.125999 2022.
Wanyu Lin, Hao Lan, and Baochun Li. Generative causal explanations for graph neural networks. In International Conference Machine Learning, pp. 6666-6679. PMLR, 2021.
Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, et al. Dig: A turnkey library for diving into graph deep learning research. The Journal of Machine Learning Research, 22(1): 10881, 2021.
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: 13:19620-19631 2020.
Jing Ma, Ruocheng Guo, Saumitra Mishra, Aidong Zhang, and Jundong Li. Clear: Generative counterfactual explanations on graphs. Advances in Neural Information Processing Systems, 35: 25895-25907, 2022.
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic attention mechanism. International Conference on Machine Learning, pp. 15524-15543. PMLR, 2022.
Siqi Miao, Yunan Luo, Mia Liu, and Pan Li. Interpretable geometric deep learning via learnable randomness injection. Proceedings of the International Conference on Learning Representations (ICLR), 2023.
Jerome L Myers, Arnold D Well, and Robert F Lorch Jr. Research design and statistical analysis. Routledge, 2013.
Meike Nauta, Jan Trienes, Shreyasi Pathak, Elisa Nguyen, Michelle Peters, Yasmin Schmitt, Jörg Schlötterer, Maurice van Keulen, and Christin Seifert. From anecdotal evidence to quantitative evaluation methods: systematic review on evaluating explainable ai. ACM Computing Surveys, 2022.
11

---

Published as a conference paper at ICLR 2024
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10772-10781, 2019.
Luyu Qiu, Yi Yang, Caleb Chen Cao, Jing Liu, Yueyuan Zheng, Hilary Hei Ting Ngai, Janet Hsiao, and Lei Chen. Resisting out-of-distribution data problem in perturbation of xai. arXiv preprint 17Xiv:2177.14000. 2021.
Yuta Sakai and Ken-ichi Iwata. Sharp bounds on arimoto's conditional rényi entropies between two distinct orders. In 2017 IEEE International Symposium Information Theory (ISIT), pp. 2975-2979. IEEE, 2017.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008.
D Tebbe and S Dwyer. Uncertainty and the probability of error (corresp.). IEEE Transactions on Information theory, 14(3):516-518, 1968.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018. URL http:://wpouiiiiii...rrbommmt/tp
Xiaoqi Wang and Han-Wei Shen. Gnninterpreter: A probabilistic generative model-level expla- nation for graph neural networks. In Proceedings of the International Conference on Learning Representations (ICI.R) 2023.
Bingzhe Wu, Jintang Li, Junchi Yu. Yatao Bian, Hengtong Zhang, CHaochao Chen, Chengbin Hou, Guoji Fu. Liang Chen, Tingyang Xu, et al. A survey of trustworthy graph learning: Reliability, explainability, and privacy protection. arXiv preprint arXiv: 10014, 2022.
Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. agnk-igi graph explanations. Advances in Neural Information Processing Systems, 15:12027-1203 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neu-
ral networks? In International Conference on Learning Representations, 2019. URL https
//openteview.ne//fommmiici http:///ww....ooooooooi/ninr///o fid-ryGs6iA5Kmm
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer:
Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 430-438, 2020.
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-12253 PMLR, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2022.
He Zhang, Bang Wu, Xingliang Yuan, Shirui Pan, Hanghang Tong. and Jian Pei. Trustworthy graph neural networks: Aspects, methods and trends. arXiv preprint arXiv:2205.074 2022a.
Shichang Zhang, Yozen Liu, Neil Shah, and Yizhou Sun. Gstarx: Explaining graph neural networks with structure-awart cooperative games. Advances Neural Information Processing Systems, 35: 19810-199 199233,,,,, 2022b.
12

---

Published as a conference paper at ICLR 2024
A PROOFS
A.1 PROOF OF PROPOSITION 1
Proof. Let (.) be the explanation corresponding the (s, -)-xxliainaabi task, and let (()) & arg my Py (v))(v))) be the Bayes classifier. Define f(ī) as the deterministic classifier which outputs arg m Py (y)) (y) (g)) for given input g. By construction, f(-) is (s, expllainae since I(Y; ) = 0. It remains to show that equation holds, where is the accuracy of f(-) and c* the accuracy of f (-). To this end, note that by the assumption of explainability of the task, and using the fact that under Condition we have I(Y: G( I(:: -I it follows that:
(Y;GLuV I(Y:G) S K H(Y)V - HY|))) + K.
By Fano's inequality, we have:
H(|])) & ho(t") + log (1D) 1) (()) hn(e")
log (13) + k.
On the other hand, by reverse Fano's inequality (Tebbe & Dwyer 1968 have:
Kovalevsky
1968
Sakai &
Twata 2017).
H(Y 2 (1 11 1-c 1
1+
1+
c- (1 - <)
Consequently,
eRF(E) S ho((") + + log (1D) 1) + k.
This completes the proof.
A.2 PROOF OF THEOREM 1
Proof. Proof of I): From the assumption that f(-) is (s, --exxlaainable, we conclude that there exists an explanation (-()) satisfying conditions i) and ii) in Definition and Condition 1 in equation ] Then,
(1::0
2 (+
9
3 33 3 (+ (G)
(H
S + log (1)) - 1),
where (a) follows from the chain rule of mutual information, (b) follows from the assumption that (-) is an (8, C) explanation for f(-). (c) follows from the information theoretic identity that T(X;Y) & (XX) for all random variables X, Y. (d) follows from the fact that conditioning reduces entropy, and (e) follows from Fano's inequality (Cover 1999).
Proof of 2): Following the proof of Proposition] 1 define f(g) as the deterministic classifier which outputs arg max,ey Py Pr)v(a) (yl (g)) for given input g. We have:
P(h(G) + f (G) & P(h(G) * (G) + P(f(G) # ff)())
(8)
Define G, A (g] 2P ( < - 7), where 7 E [0, We have,
P(M(G) (G) P( E 9.) P(G & G,) # +1 9.).
(9)
13

---

Published as a conference paper at ICLR 2024
Furthermore, following Devroye al. 2013 Section 2.4), we have:
B(22 v (1 11) [([2Pr]((1))) - -1))
-2E..
Consequently, by the Markov inequality, we have:
P(1 - 111-12P ( 1 1 2
7E 00
?
So. E 2 7 [0, Using equation
we get:
+ P(h(G) # (G),, 9-),
(10)
On the other hand, using Devroye et al. 2013,
Theorem 2.2),
PY) = - Σ
Pe(o) Pelo)lly (1 (1(g) 2
1 (())+)))))))
1 2 22 Σ PaloPyyaaL
1 (
2
980,
2 E" + 2(1 7)
Σ 3E9,
where in the last inequality, have used the definition of 9y- Note that Eggs, pa
P(G & PL) + (G) & G2). Consequently,
P(N(G) * 2 c + 2(1 P(G & 9.) + ( gr)
xY) -
5
P(G P + (G) & 9,)
2(1-7)
2(1 1
Hence, from equation 10
we have:
2
8
P(h(G) # (G)
+
7
2(1 7
Similarly,
2
6-c"
P(f(G) & (() <
+
2(1 -7)
From equation g
we get:
P(N(T) + f()) < 4c + 8+c c-
2(1 77)
2(4e'vV2/e
Minimizing the right-hand-side over 7 E [0, 1). we get 7*
given that
ge- -0-
9Ea > Emaz (e", ,k) + 8. Hence,
P(h(T) # f(G)) - VZVETE (64c 166' + (2)
2 (--8ct + 8v2c VC + 12EVeTt
(64c - 16c +2))
2 ( (-AV22Ve + SE* E)
(8e" =E)² (8)
222 VE) ?
(2V2c" + VE)² _ T.
where we have defined g _ 8 6 6" Using the data processing inequality and Fano's inequality, get:
1 1 < I(h(G);; G[v (G) < hv(T) 7 log (2)
This proof is completed by noting that e < emaz (c", k).
14

---

Published as a conference paper at ICLR 2024
A.3 PROOF OF PROPOSITION 2
Proof. We need to show that the condition in equation is satisfied for any pair of explanations in S. We consider cases:
Case I: Deep S (T) for all 77 for which Geep S D. that is, whenever the motif Jeep is in G, then the explanation function (G) outputs the motif along with potentially other irrelevant edges and vertices. In this case. it is straightforward to verify that P(y) 1, Pt (y) - 1 1), and P- (v) = for all y E {0, 13. So, Fid+ = P(Y 1), Fid_ O, and Fid P(Y 1). Furthermore, I(V: L (G)) = 0.
Case 2: If the exists 9 such that Gezp S g but Deep & (g). then for any g such that goep E but Geup L V (T), we have P(1) = 1, P* (y) = 19eep n M (g) = o). and P- (y) = 0. Otherwise,
if Geep $ T we have y 0 and P(I) 1, p (1) = 1, and p- (y) = 1. So, Fid4 P(Y
1)-P(Y- 1, Deap (G) = Φ), Fid_ 0. and Fids P(Y 1) 11--)PP P(Y Mezp 1. NV = Φ)) Furthermore,
I GIo = 1
where we have used the fact that this is deterministic classification task. Note that since the graph edges are pairwise independent, we have:
H\ 11 (G)) Plgezp n [ = (Y)
P(geup n (T)) + 6) ( 1 (G) Jeap n (G) +))
The latter is an increasing function of P(genp n (g) Φ).
can be observed that Fid, in a decreasing and 7(Y: [ an increasing function of P(gezp
V/ (g) の). Consequently, the condition in equation 3 is satisfied. This completes the proof.
A.4 PROOF OF PROPOSITION 3
Proof. We have:
E" E(-c) SE,
where the left-hand-side follows from equation 7 since:
B(P(Y)) -()) = P(C))( (()))))
along with:
e' S P(G)P(Y = (())))+
= (1 PP- = (G])) = P MCC >
1
Furthermore,
E(pant S P(g)E(Pa P ( P(g9)
(a) P(A) E P (Y) E 9. + P(A))
1-e
(6)
P(A)
9,A, + -1 P(B') +e
(c) P(A)
IE ((Pait(Y)) E P(47) + +1 -1- +E
E
(4) P(A)
pmax Py (v)) + +1 -
) + -1 +e,
1
where A is the event that Bly g, C G. B is the event that the sampling operation removes more than k edges, and B' is the event that in n² consecutive realizations of Bernoulli variable with parameter an we get more than ones. In (a) we have used the fact that P(g, A) & P(A). In (b) we have used the fact that P(B 9) P(B'). In (c), have used P( & 1. In (d), we have used the
15

---

Published as a conference paper at ICLR 2024
assumption in equation 7 and the fact that the explanation function does not output the motif with probability (1 p). in which case it is not subtracted in the definition of pai,t, and it outputs the motif with probability in which case the motif is not present in G (P.(() since is 81- Additionally,
42
B(Po (Y)) P(A)(1 - 2 2nd
pp
where we have used the fact that if A occurs, and the explanation outputs the motif, which happens with probability p. then the optimal classifier f" outputs the correct label, and B' does not occur,
then fs()) agrees with f*()) with probability (x+T)) )d, and we have bounded P(B') 2 (1 2 2
by Hoeffding's 's inequality. Consequently,
Fidar+ 2 E P(A)
((1 P pmax m -1 1- 1 k )0)
-P(A)) P(B') -
12
1
Fidaz-- 5 P1A)(1 2In²
+
P P(A)
Fidanoa 2 -E P(A)) - - P(B')
((1 - + max Py (v))+
1 1-e
1- 1- k+1
)9) 1 + P(A)(L P(A)(L - 2 Rn?
''p.
k
02.4 Note that the lower-bound on Fiday .2, A is monotonically increasing in p. To prove that Fido .2.. well-behaved as k; n - Do and d, c + 0, it suffices to show that equation holds. Note that:
Pr. gleepp C
G v(G)) = = (a) (Bezp)
Σ v.
Py.alv.9laeay GG)log Py S P7 geep C G)
geap
= (o)(;)) + Po G
(11)
yEY
From the proposition statement, we have:
Pa(a)(o) P(yly By GG) (1- 93 C
(12)
P (G) (gy) = pP(] gy -, Vy
(13)
As result, from equations 11 we have:
(Y; G( - P(Bly G)((G;;)+
-
Σ P(W :gv gv S ()))))) PI.: CG)).
NEY
where we have used the fact that P(3ly By C G)- = Eyer P(ly'' 9y S GG,y = v). We note that G) HYY and I(Y; ; G 0 as + So, there exists an error threshold e such that for all S Gth and y E V, the term (1 (); pTY: Glg G is decreasing as a function of p. Since the lower-bound I(; ())))) is monotonically decreasing in p, conclude that equation holds and Fidajaaz is well-behaved.
Fidaraaz. A is monotonically increasing in p, and
B EXAMPLES AND ANALYSIS
An Analytical Example with Distribution Shift for the Fida Measure: In this example, provide an asymptotically deterministic classification scenario where for an errorless classifier f()). there exists explanation function V which is asymptotically optimal in the sense of Definition 3 but has a worse fidelity score under Fid, compared to classifier V which generates completely random outputs. We conclude that Fida is not bell-de for this scenario. To elaborate, let us
16

---

Published as a conference paper at ICLR 2024
consider classification scenario where G has N vertices, and it can be decomposed as the union of two subgraphs Go and Geap. Further assume that Go is Erdös Rembi with edge probability p E (0, 1) and has n E N vertices. The graph Geap is equal to Cn with probability 9 E (0, 1), and is equal an empty graph with probability
+ Un vi. We call the graph G atypical if it has less than than " edges. Note that the expected number of edges in Go is "(m=1) 2 p. and by the law of large numbers, as n + oc, the graph G has more than " edges with probability one. Let us assume that Y 1 i is typical and Cn S G, and Y = 0, otherwise. Let us consider the asymptotically optimal classifier S(G) which outputs Y = if C₁ S G and G is atypical, and outputs y O, otherwise. Consider the explanation function
q. where C, is the n-cycle V1 12
Cn Φ
if Cn CG Otherwise.
(G)
Clearly, we have I(Ý; G 1 L( - 0 as n 0o, and hence V(() is an (optimal) (n, exxpllnattn function as + cc. Note that, Fid+ (f. v1 + P(Y = 0). Fid (J. V + P(Y = 0), and Ffda 11 - 0 as - cc. On the other hand, let (2(G) be the explanation function which outputs a randomly and uniformly chosen subset of more than n²p edges from G. Then Fida(F, V2 P(Y 1) P(Y 0) 2q 1 which is greater than 0 if q 1/2. So, the trivial explanation 2 receives a higher score under Fida compared to the optimal explanation V,
C EVALUATION ALGORITHMS
In this section, provide the pseudo-code for computing the proposed Fida, and Fidaz.- in Alg. 1 and Alg. 2 respectively. Suppose that have set of input graphs, {G.) For each graph G the explanation subgraph to be evaluated is denoted by (G;)). The model to be explained is denoted by f()). We have two hyper-parameters, M and a in computing Fid M is the number of samples and or, introduced in equation 5 the ratio of edges sampled from explanation subgraph.
For Fidaz,,, we have another aeper-paraeeter a2 instead, which indicates the ratio of edges sampled from non-explanation subgraph.
Algorithm Computating Fiday.t
I: Input: A of input graphs and their subgraphs (G., ((G.)) a GNN model f(),, hyperparameters M and en.
2: Output: F Fiday.+ of (G.))
3: for each pair (G., (G.)) do m from to do 5: EV,((((,,) < sample aj edges from (T.).)
6: G.m G. Ea, (V.))
Compute the non-cxplanation subgraph
7: Fido,+(1, (1, f(Gi),, f(Grmm)
8: end for
9: Fidai+hi [1] <- 33 L Fidor [3
10:
end for
11: Fida + ++ IIT (id
12: Return Fidan.t.
D EXTENSION BEYOND GRAPHS
Some efforts have been conducted to address the distribution shift problem in evaluating general XAI methods (Hooker et al. 2019). Most of them focus designing more robust perturbation- based explanatory methods (Hase et al. 2021: Hsich et al.) 2021 Qiu et al.) 2021 Jethani et al. 2023). For example, ROAR retrains the model with a modified dataset to ensure the generalization of the classification model (Hooker et al. 2019). Robustness measurements include adversarial perturbations into metric (Hsieh et al. 2021b. However, these methods designed for grid data and it is non- trivial to adapt them to graphs. Moreover, these methods require access to the internal parameters of classification models and applicable black-box models.
17

---

Published as a conference paper at ICLR 2024
Algorithm 2 Computating Fidoz.-
1: Input:A set of input graphs and their subgraphs ((G,, ((G.)) GNN model f(), hyperparameters M and 02.
2: Output: Fidoz-- of ( (G.))
3: for each pair (Gi, (G.)) do
4: for m from to M do
5:
G. 6.+0 G.G. (G.)
# Compute the non-explanation subgraph
6:
Faz(G. t sample 02 edges from G;
Fidaz,- m] ((G.),. f(Eng (G.) (..)), end for
8:
9: Fidag.- [i] t- M Em= Fidag.- 17
10: end for
11:
Fidaz.- Ele 1idaz.-ii
12:
Return Fidoz.-.
In this study, we focus on the graph domain. The notion of explainability considered in this work is specific to sub-graph explanations. Recall that graph Geap is subgraph of if its vertices can be "aligned" with a subset of vertices in such that all edges between the two sets of vertices match. The subgraph explainability is key in the definition of mutual information I(Y; G L which is then used to define explainability in Definitions 2 and 3. As a basic foundation, unfortunately, the definition of mutual information is non-trivial be extended to general domains. However, the underlying ideas considered in this paper are general and may be applicable to non-graphical tasks, which is an interesting avenue for future research.
E DETAILED EXPERIMENTAL SETUP
We use a Linux machine with 8 NVIDIA A A100 GPUs as the hardware platform, each with 40GB of memory. The software environment is with CUDA 11.3, Python 3,7.16, and Pytorch 1.12.1.
E. DATASETS
We adopt two node classification datasets and two graph classification datasets with ground-truth motifs. Specifically, the Tree- Cyccle dataset includes an 8-depth balanced binary tree the base graph. 80 cycle motifs are then randomly attached to nodes from the base graph. (2) Tree-Grid created in similar way, except that the cycle motifs are replaced with 3-by-3 grids. (3) The BA-2motifs dataset consists of 1000 graphs. Half of them are obtained by attaching 'house' motif to 20-node Barabási-Albert random graph. Other graphs are with 5-node cycle divided into 2 classes based on the type of attached motifs. For these datasets, we use 10-dimensional all vector as node attributes (Ying et al.) 2019). We also use real-life dataset, MUTAG, for graph classification, which consists of 4,337 molecular graphs. These graphs are labeled based on their mutagenic effects (Ying et al. (2019). As discussed in (Luo al. 2020), chemical groups N H2 or NO₂ are used as ground truth motifs.
motifs. Graphs
E.2 CLASSIFICATION MODEL ARCHITECTURES
The GCN model architectures and hyperparameters of layers are the same the previous work (Luo et al. 2020). Specifically, for the node classification, two-stack GCN-Relu- ReeRRRelllthoonnn block followed by GCN-Relu block is used for embedding. following linear layer used for classifi- cation. For the graph classification, three-stack GCN-Rell CCNN-Relu-BatchNomm block is used for compute node embedding. Global max and mean pooling are used to read out the graph representations. A linear layer is then used for classification. Similarly, we create GIN models by replacing the GCN layer with setting in Pytorch. The models are trained with the Adam optimizer with initial learning rate of 1.0 x 10 3 For each dataset, we follow existing works (Luo et al. 2020 Ying et al. 2019) to split train/validation/test with 8: 1 for all datasets. Each model is trained for 1000 epochs.
Amear-Rells Relu-Linear Reeu GIN layer. All the variables are initialized with the default
18

---

Published as a conference paper at ICLR 2024
F EXTRA EXPERIMENTAL STUDIES
F.1 EFFECTS OF 01 AND ag.
As shown in our theoretical analysis, aj the rate removing edges from explanation subgraphs in Fidai.+ and 0g is the rate of retaining edges from non-explanation subgraphs in Fid To empirically verify the effects of these two parameters, we use the GCN model and vary these two hyper-parameters in the range [0.1, 0.3, 0.5, 0.7, 0.9]. Results of Spearman correlation scores shown in Figure 1 We observe that when on = 0.1 and 022 = 0.9, the proposed Fid and F strongly aligned with the gold standard edit distance. As on increases, the number of removing edges from explanation subgraphs increases, leading to more a severe distribution shifting problem. Thus, the Spearman correlation coefficient between Fider.+ and edit distance increases. Specifically, in the Tree-Circke dataset, the correlation even becomes positive when > 0.2. The similar phenomena can be observed in Fidaz.-. -. As a2 decreases, a smaller number of edges will be added from non-ext non-explanee ae-exlaanation subgraphs, which leads to the distribution shift problem. As result, the Fidog.- cannot be reliably aligned with the gold standard metric.
File.
Fil
FMl...
3.0
-00
472
00.92
(a) Tree-Circles
(b) Tree-Grid
(c) BA-2motifs
(d) MUTAG
Figure 1: Parameter studies on the effects of a1 and 02
F.2 CLASSIFICATION PERFORMANCE OF GNNS
We evaluate the accuracy performance of GNN models on training, validation, and test sets. The results are shown in Table 2 Both GCN and GIN achieve good performances in these datasets, with most test accuracy scores above 0.9. Following routinely adopted settings (Ying et al. 2019 safely assume that both models correctly the
Luo et al. 2020; Yuan et al. (02T), informative (onoiss in the input graphs to make predictions.
Table 2: Accuracy performance of GNN models.
Node Classification
Graph Classiication
Method
Accuracy
Cree-Cycles
Tree-Grid
BA-2motifs
MUTAG
Training
0.99
0.92
1.00
0.82
Validation
1.00
0.94
1.00
0.82
GCN
Test
0.99
0.94
0.99
0.81
Training
1.00
0.98
0.99
0.86
Validation
1.00
0.99
1.00
0.84
GIN
Test
0.99
0.97
1.00
0.82
F.3 DISTRIBUTION ANALYSIS
In Section 3.2.1 we argued that the previously studied Fida, Fid_ and Fid4 surrogate measures suffer from the OOD problem, since Fid_ and Fid__ rely accurate classifier outputs for inputs T and G V (G), respectively, and FidA depends both. In this section, we empirically verify the affremmenioned OOD problem. Specifically, we adopt an AutoEncoder (Kramer) 1991) to embed the adjacency matrix of (sub-)graph to 2-dimensional hidden representation. We choose the graph classification dataset. BA-2motifs, where all graphs have the same node size. The encoder network consists of two fully-connected layers, same that of the decoder network. Cross Entropy is used as the reconstruction error to train the Autoencoder model. The original graphs, the ground-truth explanation subgraphs, and the non-explanation subgraphs used for training.
19

---

Published as a conference paper at ICLR 2024
The visualization results of these three types of (sub-)graphh shown in Figure 2(a) We observe that both explanation subgraphs and non-explanation subgraphs have clear distribution shifts compared to the original graphs.
Derginal Grephrs
Original Grapha sampled Subgrapns
Kon Explamatton Sungrapte Explanation S48graphs
O Oiggnall Grophs Opem sampaaaamppp od Subgraphi
(a) Explanation & non-explanation (b) Down-sampled subgraphs in (c) Up-sampled subgraphs in subgraphs
Fidor.+ + for an O.L.
Fidaz.- for az 0.9.
Figure 2: Distribution analysis with visualization.
The proposed methods address the challenge by considering 'down/up-sampled subgraphs', Specifi- cally, in Fida,,+. given graph G and an explanation subgraph (G),, as shown Algorithm| we randomly remove o ratio of edges in (G) from G and compare the prediction with the original one. For simplicity, we denote this "down-sampled" subgraph. For 01 0.1. Figure 2(b) shows the visualization results of these down-sampledd subgraphs. We observe that these subgraphs are in-distributed. Similarly, in - sample 02 ratio of edges from the non-explanation subgraph and add them to the explanation subgraph. We denote this graph as an 'up-sampled' subgraph. The visualization results with a2 0.9 shown in Figure 2(c) which also verifies the in-distribution property.
To quantitatively evaluate the distribution shifting problem, we first normalize the representation vector and use KL-divergence to measure the distance between up/down-sane sampled subgraphs and the original graphs. The KL divergence between down-sampled subgraphs and original graphs with respect to a₁ is shown in Figure 3(a) When a₁ 1.0, the down-sampled subgraphs degenerate into non-explanation subgraphs, where the KI. divergence large. For small value of a1, the KI. divergence is small. In Figure ((b) we show the KL divergence between up- up-sampled subgraphs and original graphs with respect to a2. When d22 = 0.0, the up-sampled subgraphs become explanation evidenced by a large KL divergence value. On the other
subgraphs, which are out-of-distributed, hand, with large value of ag for example 0.9, we are able to largely alleviate the OOD problem.
0.75
Divengence
0.100
0.30
0.500
0.05
0.25
0.0
0.0
0.0
(a) Down-sampled subgraphs used in com- puting Fidan.t
(b) Up-sampled subgraphs used in comput- ing Fidaz.-.
Figure 3: KL divergence between down/up-sampled subgraphs and original graphs.
F.4 STABILITY ANALYSTS
In the proposed fidelity measurements, we sample M times to compute Fidm,t and Fid respectively. To verify the stability of our measurements. We change the value of M in the range
20

---

Published as a conference paper at ICLR 2024
(10, 100) and keep a11 0.1 and 02 0.9. For each value of M, evaluate the quality of ground- truth explanations 10 times and report the mean as well as the standard deviation in Fig. 4 Specifically, for the default setting, .M 50, also report the comparison of running time between methods and their counterparts Table 3
We have the following observations. First, M increases, the proposed metrics more stable. Second, our measurements are quite robust as the mean scores are stable with M ranging from 10 to 100. Thus, although our method slower than the original fidelity measurements, in practice, a small number of samples are enough to get precise estimations.
Table 3: Running time performance on GT explanation
Node Classification
Graph Classification
Model
Time(s)
Tree-Cireles
Tree-Grid
BA-2motifs
MUTAG
Ori.
1.06
3.77
2.98
56.91
GCN
Ours
13.34
64.44
48.97
302.38
Ori.
0.63
2.71
2.12
50.99
GIN
Ours
7.74
37.65
30.53
198.93
0.010
M
0.025
0.025
Mean Valtue
0.030
0.023
Masn
0.625
0.015
8.019
+ Mean
Mean
20
40
60
20
160
25
40
60
160
Sample Size (4)
Sample Size (M)
(a) Fida + on
(b) P Pidaz.- on Pree-Cireles
Mean 1 5D
-0.015
0.240
0.235
Meen Valuee
0.230
Mean
-0.025
0.25
0.220
0.155
40
69
80
100
60
80
100
Sample Size (M)
Sample Size
(c) Fida on Tree-Grid
(d) Fidaz.- on Tree-Grid
0.074
0.222
Moan
0.072
0.121
Maan Value
0.220
0.119
0.06
Maa
0.118
2.088
6.17
0.064
0.116
3.062
-- Mean 1 5D
0.115
60
30
60 Sample Size (M)
Sample Size (M)
(e) Fid on BA-2motifs
(f) Fid on BA-2motifs
0.038-
8.037
Moan Value
6.067
0.036
0.086
Mean
0.005
0.084
0.033
0.033
8.39
- Mean
0.822
- Mean 5D5
60
100
60
Sample Size (M)
Sample Size
(g) Fidn on MUTAG
(h) Fidoy,- on MUTAG
Figure 4: Parameter studies on M.
21

---

Published as a conference paper at ICLR 2024
F.5 QUALITATIVE EVALUATION
To qualitatively show the quality of different fidelity metrics, in this part, we visualize the fidelity scores with heat maps. We adopt the GCN model and follow the experimental setting in 5.1 Results are shown in Fig. 5 6 7 and 8 We can observe several phenomena. First, with the same 32. a candidate explanation generated by a small 31 indicates a smaller edit distance and better explanation quality. Thus, for Fid4, the values should decrease as a1 increases. However, as shown in Fig. ((a)
6(a) 7(a) and [(a) the original Fid, fails to keep the monotonicity. For example, when looking at the first column of Fig. (a) we observe that the Fid, scores first go up and then
go down with 31 increasing and achieves the highest score when there are 50% edges removed from the ground-truth explanations. The result shows that Fid,, fails to measure the correctness of
explanations. On the other hand, the new proposed Fidaz, is highly monotonic to gold standard edit distance. We have similar observations with Fid_ and Fida on all these datasets.
4.44
4.0
CM
40
00
AXT
KM
(a) Fid+
(b) Fid_
(c) Pida
AM
CO
(d) Fidayst
(6) Fida
(1) Fida .9.
Figure 5: Fidelity scores with GCN on Tree-Circles. The X-axis value, Bg is the ratio of added edges from the non-explanation subgraph to the candidate explanation. The Y-axis value, 31 is the ratio of edges removed from ground truth in the candidate explanation.
CCT
3-
(a) Fid+
(b) Fid_
(c) Fida
64
C4
30
30
45
33
0.4
KX
06
C8
0-
50
C3
C8
0C1
00
AM
57
C7
422
901
42
(d) Fiday
(c) Fidag.-
(1) Fiday,
Figure 6: Fidelity scores with GCN on Tree-Grid.
22

---

Published as a conference paper at ICLR 2024
F2
0.0
033
20
(a) Fid+
(b) Fid
(c) Fid
40
3-
(d) Fidai
(c) Fidaz.-
(f) Fida 09.
Figure 7: Fidelity scores with GCN on BA-2motifs.
32
221
440
121
121
AM
021
2M
(a) Fid+
(b) Fid-
(c) Fida
3
0 K2 40
42
3M
(d) Fidayst
(e) Fidaze-
(I) FidaragA
Figure 8: Fidelity scores with GCN on MUTAG.
F.6 CASE STUDIES
In this section, we adopt case studies show the effects of the OOD problem in original fidelity measurement and the robustness of the new proposed metrics. We use both graph classification datasets, BA-2motifs and MUTAG in this part. For each dataset, we choose a graph. We consider two candidate explanations: the gold standard one and an adversarial explanation. As shown in Table the first row is the gold standard explanation and the second row is an adversarial explanation with an edit distance of 10, which doesn't t contain the label information. The Fid, scores of these two explanations are close. Moreover, Fid_ and FidA mistakenly suggest that the adversarial explanation is better. These results further verify that the original fidelity metrics are fragile. On the other hand, the proposed fidelity metrics are more robust. All Fidm,.-, Fid,a.-, and F Fid,,, .0.. successfully give the correct measurements. We have similar conclusion in the case study of MUTAG in Table 5
23

---

Published as a conference paper at ICLR 2024
Table 4: case study on BA-2motif's dataset. The bold font indicates the better explanation subgraph suggested by fidelity measurements.
Explanation
Dis.
Fid+ 1
Fid_ 4
Fida
Pida
Fido,, Fiday .z.
0
-0.012
-0.036
0.024
0.169
0.002
0.167
-0.010
-0.052
0.042
0.009
0.103
-0.095
Table 5: A case study MUTAG dataset. The bold font indicates the better explanation subgraph suggested by fidelity measurements.
Explanation
Edit Dis.
Fid,
Fid 1
Fids
Fida
Fid
Fid .01.
0
0.619
0.627
-0.008
0.092
0.303
-0.211
10
0.697
-0.030
0.727
0.056
0.352
-0.296
F.7 ACCURACY BASED FIDELITY
As another variant. accuracv-basee Fidelity measurement is also used to evaluate the performance of explanations Yuan al. 2022). Let use {(G,, y/4 14)) denote set of T of graphs and their labels. f(-) is the GNN classifier to be explained. For the i-th graph G, (G,) denotes the explanation subgraph output by an explainer ((()) acting on G, The accuracy-ban fidelities are defined as follows.
Fidlec))
(arg max (G,) = =y) (arg maxf(G, (T())) = vi)
(14)
(ac(ac))
[arg max ((+)) -1)) 1arg max (ax)()(G.)) = -1)
T
Fidface) Fid(aar) (ace)
In a similar way, we formulate our accuracy-based Fidelity measurements, Fidlace) Piglace) and og
Fidlace) c. A. We adopt the same setting as Sec, F.5 and show the visualization results in Fig 10 12d We observe consistent improvements achieved by our methods over their counterparts, indicating their effectiveness in the iccuracy-based setting.
24

---

Published as a conference paper at ICLR 2024
323
200
50
541
(a) Fed(
(b) Fid
(c) Fid
64
30
45
25
42
(d) Fid
(c) Fid
(1) (acc) an .9.0.
Figure 9: Accuracy-based Fidelity results of GCN on Tree-Cireles.
3
8
0.6
423
AM
(a) Fid(ac))
(b) Fid(ace)
F Fideec)
64
30
0
PM
JM
(d) F
(c) Fidface)
(aec) (f)
Figure 10: Accuracy-based Fidelity results of GCN on Tree-Grid.
25

---

Published as a conference paper at ICLR 2024
0-4
623
(a) Fid(oc)
(b) Fid(ace)
(c) Fid
64
30
45
24
3- 3.0
42
(d) Fid
(c) Fid
(1) Fidlac))
Figure 11: Accuracy-based Fidelity results of GCN on BA-2motit
F
5
2.0
(a) Fid(ac)
(b) Fid(ace)
(c) Fiddec)
0-
(d) Fidface)
(c) Fidface)
(f) Figlac))
Figure 12: Accuracy- based Fidelity results of GCN on MUTAG.
26


Reviews:
[{"review_id": "wBSpW3xaJj", "reviewer": "Reviewer_dokf", "summary": "This paper analyzes the inherent limitations of prevailing fidelity metrics and proposes a robust class of fidelity measures.\nThe contributions are mainly about the relevant theoretical analysis", "questions": "- Can the proposed fidelity measures be applied to data beyond graphs? If so, why the paper restrict the scope to graphs?", "limitations": "", "rating": 3, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "- Sufficient theoretical discussions regarding prevailing fidelity metrics are introduced in the paper", "weaknesses": "- The paper is poorly structured. The theoretical analysis took up too much space, and many of the derivations can be moved into the appendix. In the meantime, the discussion for the motivation of Fidelity measures is too limited.  Experimental results are also too limited. \n- I hope the paper can better justify why the proposed fidelity metrics are ideal, and especially discuss their differences and relations with respect to the existing explainable GNN methods. Such discussions are lacking\n- It is not apparent that why technical theoretical results are special for graphs. Many definitions and discussions seem to relate to general machine-learning problems. Can they be applied to data beyond graphs? If so, why the paper restrict the scope to graphs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "sMiKOG0c3J", "reviewer": "Reviewer_gPjw", "summary": "The present work studies existing fidelity metrics to quantify performance of GNN explanation methods. Through a theoretical analysis, the authors find that existing fidelity metrics are not well-behaved for a wide set of scenarios without special properties due to the OOD nature of explanation subgraphs. To address this, the authors proposed modified fidelity metrics where explanation subgraphs are transformed to approximate the underlying data distribution and hence obtain more accurate approximations of predictions from trained GNN models, which, the authors argue, provide well-behaved proxy fidelity metrics.", "questions": "Could you elaborate on why proving that the proposed fidelity metrics are monotonically increasing in p means that they are monotonically increasing with the mutual information?", "limitations": "", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "-\tAddressing a fundamental aspect of GNN explainability, i.e., how well current metrics evaluate GNN explanation methods. This is a crucial topic.\n-\tTheoretical and empirical analysis to show that the widely accepted fidelity metrics are not well behaved for a wide range of scenarios without special properties. \n-\tInnovative proposal to transform sampled explanation subgraphs closer to the distribution of graphs in the training set for a well-behaved measure of fidelity.", "weaknesses": "The authors mention that current fidelity metrics are not well behaved because optimized models learn how to approximate the (graph) data distribution when making predictions and explanation subgraphs are rarely part of the dataset on their own, resulting in (potentially) poor estimates of predictions for explanation subgraphs. To address this, the authors design fidelity metrics which add/remove edges such that the explanation subgraphs approximate the training data distribution during evaluation of fidelity. I have three questions regarding this:\n1.  What are the authors’ thoughts on how the nature of explanations should be? I think intuition says that explanation subgraphs should indeed be OOD w.r.t. the data distribution, after all, we’re looking for *sub*graphs that stand out (can be predictive on their own). Do authors generally think that the field should be moving to finding IID explanation subgraphs (if this is possible)? \n2.  It appears that the OOD aspect is addressed in the proposed fidelity metrics. However, it seems to me that the sampling when computing fidelity metrics means that these metrics are not actually measuring fidelity of the actual explanation subgraph (but down/up-sampled versions of it). Why/how can we say that these fidelity metrics actually correspond to the explanation subgraphs themselves when these metrics measure fidelity *not* exactly for the explanation subgraphs? \n3. A different direction could be to accept that predictions for OOD subgraphs are not as accurate and compute fidelity metrics and compare explanations for subgraphs with the same sparsity level, as is done in https://proceedings.neurips.cc/paper/2021/file/2c8c3a57383c63caef6724343eb62257-Paper.pdf What are the authors’ thoughts on this?\n\nThe authors have done a great job at studying how fidelity metrics are not well behaved for a wide range of scenarios, which is a crucial question in GraphXAI. I, however, have some questions regarding their solution to the OOD issue of explanation subgraphs, specifically, my question 2. If this (and other concerns) are addressed, I am open to updating my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "LEZo8Zt0im", "reviewer": "Reviewer_oeQs", "summary": "This paper points out a crucial problem in evaluating the explainability of Graph Neural Networks (GNNs) that the subgraph is distributed differently from the training graphs. Recognizing the limitations of conventional fidelity metrics ($Fid_+$, $Fid_-$, and $Fid_\\Delta$) in capturing genuine model explainability due to the potential distribution shifts, the authors introduce an information-theoretic definition of explainability, carefully design and propose a straight forward evaluation methods by adopting sampling. They use 4 datasets and two tasks in the experimental part. They show that the proposed method is more consistent to ground truth ones.", "questions": "1. Why the proposed method fails with GIN on Tree-grid?\n2. How to select $alpha_1$ and $alpha_2$?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "1. The research problem is significant in the graph learning domain. They show that the existing evaluation method is heavily affected by distribution shifting problem, which is overlooked by existing methods. The proposed evaluation method has the potential to set new standards in the evaluation of GNN explainability.\n2. The paper provides strong theoretical analysis and empirical verification.\n3. The paper provides a simple and effective method with solid theoretical foundation.", "weaknesses": "I  have a minor concern that the proposed evaluation method is not deterministic and more time consuming comparing to the original fidelity measurement.\n\nMinor typos. \n\n1. In the introduction, \"nodes presenting atoms\" should likely be \"nodes representing atoms\".\n2. In the introduction, \"subgraph of the input which satisfies two conditions\" shoule be \"subgraph of the input that satisfies two conditions\"\n3. In Section 3, \"low error probability\" should be \"a low error probability\", \"with error close\"-> \"with an error close\", \" has Bayes error rate\" -> \" has a Bayes error rate\"", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}, {"review_id": "lQymYdgkcU", "reviewer": "Reviewer_aFFv", "summary": "The paper tackles the crucial challenge of evaluating the fidelity of explanations provided by Graph Neural Networks (GNNs). Given the increasing importance of GNNs in sensitive sectors, understanding their decision-making process is paramount. Traditionally, fidelity metrics like $Fid_+$, $Fid_-$, and $Fid_\\Delta$ have been utilized to measure the correctness of these explanations. The intuition behind these metrics is to assess the change in model predictions when certain subgraphs, deemed important for predictions, are masked out or removed. However, the authors spotlight potential issues with these metrics, chiefly the distribution shift when subgraphs are removed. An information-theoretic framework for GNN explainability is presented, highlighting the misalignment of prevalent surrogate fidelity metrics with their proposed fidelity measure. As a solution, a novel class of fidelity measures that are robust to distribution shifts is introduced. The paper validates these measures through empirical analysis on synthetic and real datasets, demonstrating that the new metrics align more closely with ground truth explanations.", "questions": "1. On Page 5, the authors claims that the convergence ratio of fidelity is 1/2. What does that mean in practice?  Does the proposed metric provide better convergence rate?\n\n2. The paper focus on graph classification problem. But in the experiment, there are two node classification datasets, how can this method be applied for node classification task?\n\n3. is OOD problem unique to graph? Or it also affects other domains, like images and natural languages.\n\n4. Are there computational complexities or scalability concerns with the new metrics, especially when dealing with large real-world graphs?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The paper effectively spotlights an overlooked issue in the field of explainable graph learning, bringing to the fore the inherent shortcomings of widely accepted evaluation methodologies. The introduction of robust evaluation metrics grounded in information theory provides a fresh perspective on the problem.\n\nQuality: The paper maintains high standards in its methodological approach. It's evident that thorough theorical analysis and experiments has been done.\n\nClarity: Overall, the paper is well organized that logically from identifying the problem, proposing a theoretical framework, and then introducing new evaluation metrics. It would be better if the authors can use a figure to clearly illusrate the differences between original fidelity and the proposed ones. \n\nSignificance: This research is timely and significant. Given the increasing number of papers on explainable GNNs. The routinely adopted metric is problematic and maybe misleading.  The paper's proposed fidelity metrics could play a important role in the literature.", "weaknesses": "1. The proposed metrics are not easy to understand until reading the algorithm in appendix. \n\n2. Only small scale datasets are adopted to evaluate the proposed metrics. \n\n3. It is unclear why we need to consider the rate of convergence in fidelity measurements.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)