Hard Masking for Explaining Graph Neural Networks
Authors: Thorben Funke
Megha Khosla
Avishek Anand
Venue:  (2021)
Keywords: Interpretability
Graph Neural Networks
Hard Masks

Abstract: Graph Neural Networks (GNNs) are a flexible and powerful family of models that build nodes' representations on irregular graph-structured data. This paper focuses on explaining or interpreting the rationale underlying a given prediction of already trained graph neural networks for the node classification task. Existing approaches for interpreting GNNs try to find subsets of important features and nodes by learning a continuous mask. Our objective is to find discrete masks that are arguably more interpretable while minimizing the expected deviation from the underlying model's prediction. We empirically show that our explanations are both more predictive and sparse. Additionally, we find that multiple diverse explanations are possible, which sufficiently explain a prediction. Finally, we analyze the explanations to find the effect of network homophily on the decision-making process of GNNs.

Under review as a conference paper at ICLR 2021
HARD MASKING FOR EXPLAINING GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph Neural Networks (GNNs) flexible and powerful family of models that build nodes' representations on irregular graph-structured data. This paper focuses on explaining or interpreting the rationale underlying a given prediction of already trained graph neural networks for the node classification task. Existing approaches for interpreting GNNs try to find subsets of important features and nodes by learning continuous mask. Our objective is to find discrete masks that are arguably more interpretable while minimizing the expected deviation from the underlying model's prediction. We empirically show that our explanations are both more predictive and sparse. Additionally, we find that multiple diverse explanations possible, which sufficiently explain prediction. Finally, we analyze the explanations to find the effect of network homophily on the decision- making process of GNNs.
INTRODUCTION
Graph Neural Networks (GNNs) are a flexible and powerful family of models that build representa- tions of nodes edges on irregular graph-structured data and have experienced significant attention in recent years. These methods are based on the so-called "neighborhood aggregation" scheme in which a node representation is learned by aggregation of features from their neighbors and have achieved state-of sfate-of-the-ar the--ar performance on node and graph classification tasks. Despite their pop- ularity, approaches investigating their interpretability have received limited attention. This paper focuses explaining or interpreting the rationale underlying given prediction of already trained graph neural networks.
There have been numerous approaches proposed in the literature for the general interpretability of machine learning models. The most popular approaches are feature attribution methods that intend to attribute importance to input features given input prediction either agnostic to the model parameter (Ribeiro et al. 2018, (016) or using model-specific attribution approaches (Xu et al, 2013 Binder et al. [2116] Sundararajan et al., 2017p. However, models learned over graph-structured data have some unique challenges. Specifically, predictions on graphs are induced by complex combination of nodes and paths of edges between them in addition the node features. Thus explanations for prediction should idcally be small subgraph of the input graph and small subset of node features that are most influential for the prediction (Ying al. 2019).
The only existing approach for GNN explainability proposes to learn a real-valued graph mask that selects the important subgraph of the GNNs computation graph to maximize the mutual informa- tion with the GNNs prediction Ying et al., 2019). We identify two crucial limitations of such an approach. Firstly, although mathematically tractable, a continuous mask does not ensure sparsity compared to a discrete mask desirable property for interpretability. Secondly, suitable notions of what constitutes an explanation in a GNN model and its evaluation are missing.
This paper proposes an alternate notion of interpretability for GNNs grounded in ideas from data compression in information theory. Specifically, we consider an explanation as a compressed form of the original feature matrix. The goodness of the explanation is measured by the expected de- viation from the prediction of the underlying model. We formalize this idea of interpreting GNN decisions as explicit optimization problem in rate-distortion framework. A subgraph of the node's computational graph and its set of features are relevant for a classification decision the expected classifier score remains nearly the same when randomizing the remaining features. This

---

Under review as a conference paper at ICLR 2021
Feature Mask
Computaion the rode mpnearring the paper
Gmppox
Tairing
Proditioo claa label "GNYY"
UMEE
mmnm
Node Mask
Eage
Example Explanation
hode2
learnt
prdictiinn "GNN"
heaturea Mordd in the ecampsl
"Neura"
Negtbboutted Nocis (Papers ssample:
GragkSuge di
(Ntswork
CCN
Figure 1: Computing hard masks for explaining the prediction of GNN.
formulation is arguably both a crisp, robust, and understandable notion of interpretability that is easy to evaluate. We propose a simple combinatorial procedure ZORRO that aims to find sparse subset of features and nodes in the computational graph while adhering user-specified level of fidelity. Our method aims to find multiple disjoint explanations (whenever possible) that guarantee an acceptable lower bound on fidelity to the model's decision.
Another key problem in post-hoc interpretability of GNNs is that of evaluating explanation methods. Current evaluation methods, such as those used by GNNEXPLAINER, are primarily anecdotal and lack principled metrics. Secondly, especially for worldworld datasets, there is ground truth for the explanation, making comparison difficult. We, on the other hand, posit that an explanation is faithful to the underlying model if it retains enough predictive power crisp and measurable quantity. To this extent, our optimization metric, fidelity, encodes an information-theorett interpretation of explanation if the explanation is highly predictive in expectation, then it is high qualitative explanation.
We conducted extensive experimentation three datasets and four diverse GNN approaches Graph Convolution Networks (Kipf & Welling 2017), Graph Attention Networks (Veličković et al.) 2018). GIN (Xu et al. 2019). and APPNP (Klicpera et al. 2019). Our main key findings are as follows.
1. We show that not one but multiple diverse explanations are possible that sufficiently explain a prediction. This multiplicity of explanations indicates the possible configurations that could be utilized by the model to arrive decision.
2. Unlike earlier mutual innfomaatioonnnooonnn preserving interpretability approaches, i.c. GNNEX- PLAINER (Ying et al.] 2019). we show that our explanations are both more predictive and sparse. We show that even with sparser explanations, our approach contains far more pre- dictive capacity than GNNEXPLAINER.
3. We then analyze the explanations across multiple GNN models to showcase differences between their learning behavior. We specifically show that GNN models rely heavily on homophily and that prediction errors are due inability to capture homophilic signals from their neighborhoods.
RELATED WORK
Representation learning approaches on graphs encode graph structure with without node fea- tures into low-dimensional vector representations, using deep learning and nonlinear dimensionality reduction techniques. These representations Khosla et al.) 2019 Funke et al. 2020) or semi-supervised manner by using neighborhood aggrega- tion strategies and task-hased objectives (Kipf & Welling 2017 Veličković al. 2018).
trained in an unsupervised (Perozzi et al.) 2014
2

---

Under review as a conference paper at ICLR 2021
This work focuses the post-hoc interpretability of decisions made by semi-supervised models based on graph convolution networks for node classification tasks. Inspired by the success con- volutional neural networks, graph convolution network (GCN) & Welling 2017) generalizes the convolution operation for irregular graph data. GCN and several of its variants follow neigh- borhood aggregation strategy where they compute node's representation by recursive aggregation and transformation of feature representations of its neighbors. For the node classification task, the final node representations then used predict unlabelled nodes' classes.
Interpretability in Machine Learning. Post-hoc approaches to model interpretability are popular- ized by feature attribution methods that aim to assign importance to imput features given a prediction either agnostic the model parameters (Ribeiro al.
2018 2016) using model specific attri-
bution approaches (Xu et al., 2015) Binder et al.
2016
Sundararajan et al. 2017). Instance-wise
feature selection (IFS) approaches (Chen et al.
Carter al. 2018 Yoon al., 2018). on the other hand, focuses on finding sufficient feature subset or explanation that leads to little or no degradation of the prediction accuracy when other features are masked. The advantage of this formulation is that the output explanation has precise meaning in terms of the predictive power of the chosen subset. Applying these works directly for graph models infeasible due the complex form of explanation, which should consider the complex association among nodes in addition to the input features.
2018
Interprefability in GNNs. Model agnostic approaches like ours to interpretability in GNNs include GNNEXPLAINER (Ying et al.) (019)) and XGNN((Yaa) et al. 2020). GNNEXPLAINER learns a real- valued graph mask and feature mask such that mutual information with GNN's predictions maximized. XGNN proposed reinforcement learning- based graph generation approach generate explanations for the predicted class for a graph. We instead focus on explaining node level decisions. As model introspective approach, Pope et al. (2019) extended the gradient-based saliency map methods to GCNs, which rely on propagating gradients/relevance from the output to the original model's input features. Other works (Kang et al., [209 [Idall et al.] (211)) focus on explaining unsupervised network representations, which is out of scope for the current work.
PROBLEM DEFINITION AND APPROACH
Naisy Channel N
((X)
4(Ys)
Ys
Encoder
Decoder
Fidelity
Reconstruction Loss
Figure 2: Our approach is based on the rate-distortion framework, which assumes two parties, the encoder and decoder. The encoder has the original (restricted) feature matrix X and sends it through a noisy channel to the decoder, which receives Ys. The goal is to determine, which parts of Ys have have the original values from X, such that the fidelity is high, i.e., the decoder predicts the same label as the encoder with a high probability.
3.1 BACKGROUND ON GNNS
Let G EV be a graph where each node associated with d dimensional input feature vector. Graph neural networks compute node representations by recursive aggregation and transformation of feature representations of its neighbors which are finally used for label prediction. Formally for
L-layer GNN, let ( denote the feature representation of node E V at layer é E L and N, denotes the set of its 1-hop neighbors. .x:()) corresponds to the input feature vector of n. The f-th layer of GNN can then be described as aggregation of node features from the previous layer followed by a transformation operation.
AGGREGATION
(faff-)) { (e-11) 1illjee 1JE
3

---

Under review as a conference paper at ICLR 2021
= "RANSFOOMMATION" (2!²)
(2)
Each GNN defines its aggregation function which is differentiable and usually a permutation invariant function. The transformation operation is usually a non-linear transformation employing ReLU non-linear activation. The final node's embedding an is then used to make the predictions
(n) argmaxo(zx
where a is a sigmoid or softmax function depending on whether the node belongs to multiple or a single class. and W is learnable weight matrix. The ith element of zn = corresponds to the (predicted) probability that node n is assigned to some class
3.2 PROBLEM FORMULATION
We interested in explaining the prediction of GNN (nn) for any node We note that for particular node, n the subgraph taking part in the computation of neighborhood aggregation opera- tion, see Eq. (T.. fully determines the information used by GNN to predict its class. In particular, for a L-layer GNN, this subgraph would be the graph induced on nodes in the L-hop neighborhood of We will call this subgraph as the computational graph of the query node. We would like to pint out that the term computational graph should not be confused with the computational graph of the neural network. Let (nn) S G denote the computational graph of the node n. Let X (n), or briefly X denotes the feature matrix restricted to the nodes of G(n). where each row corresponds to a d-ddimensional feature vector of the corresponding node in the computational graph.
We formulate the task of explaining the model prediction for node as finding a partition of the components of its computational graph into a subset, of relevant nodes and features, and its complement 8 of non-relevant components. In particular, the subset S should be such that fixing its value to the true values already determines the model output for almost all possible assignments to the non-relevant subset S The subset S is then returned we compute the expected value of fidelity in model's prediction for the noisy assignment to the non-relevant components.
explanation. To quantify relevance,
Let us denote with Ys the new perturbed feature matrix obtained by fixing the components of the S to their actual values and otherwise noisy entries. The values of components in S are then drawn from some noisy distribution, N. Let S = {Va, P& J be the explanation with selected nodes V, and selected features F.. Let S be the mask matrix such that each element St if and only if ith node (in G(n)) and jth feature are included in sets V,, and F, respectively and otherwise.
Ys X e S Z (1 S), Z N.
(4)
where @ denotes element-wise multiplication, and 1 a matrix of ones with the corresponding how the fixed elements are selected by F, and V,,
size. Definition. The fidelity of explanation S with respect to the graph neural network t and the noise distribution N is given by
F(S) EYsIZ~N [10(x)=0(Ys)]
(5)
By fixing the fidelity to a certain user-defined threshold, say we are then interested in all possible disjoint sets of explanations that would have the fidelity of least r. More precisely, our resulting set of explanations R is given as
R S1 V,F(S,) 2 and ns; (
CONNECTION TO THE RATE- DISSTORTIONN THEORY
Our problem formulation is inspired by rate-distortion theory (Sims 2016) which addresses the problem of determining the minimal information of a source signal that should be communicated over a leaky channel so that the source (input signal) can be approximately reconstructed at the receiver (output signal) without exceeding expected distortion D. In our problem, are in- terested in finding a small subset such that having knowledge only about the signal on and filling in the rest of the information randomly will almost surely preserve the class prediction if our
4

---

Under review as a conference paper at ICLR 2021
chosen subset contains the information that is relevant for the model's decision. Rather than mea- suring distortion or disagreement in the model's 's decisions, we instead measure fidelity or agreement among the model's decisions with the original and the distorted signal, respectively. Distortion can be computed using fidelity as DD = F. A schematic representation of our problem in terms of rate-distortion framework is shown in Figure 2
3.3 OUR APPROACH: ZORRO
We propose simple but effective greedy combinatorial approach, which we call ZORRO, to find the set of disjoint explanations with a desired level of fidelity. The pseudocode provided in Algo- rithm 1 Let for any node n, V, denote the vertices in its computational graph G(n) and F denote the complete set of features. We start with zero-sized explanations and select as first element
argmax F(V., (()) or argmax F)) vEV,
JEF
whichever yields the highest fidelity value. We iteratively add new features or nodes to the expla- nation such that the fidelity is maximized over all evaluated choices. Let V and F, respectively denote the set of possible candidate nodes and features that can be included in an explanation at any iteration. We save for each possible node u E V,, and feature E Fp the ordering RV, and RF, given by the fidelity values F((r), Fp)) and F(V,, {{}) respectively. To reduce the computational cost, we only evaluate each iteration the top K remaining nodes and features determined by Rv, and REg-
Once we found an explanation with the desired fidelity, we discard the chosen elements from the feature matrix X, i.e., we never consider them again as possible choices in computing the next explanation. We repeat the process by finding relevant selections completely disjoint from the ones already found. To ensure that disjoint elements of the feature matrix X are selected, we recursively call Algorithm 3 with either remaining (not yet selected in any explanation) set of nodes or features. Finally, return the set of explanations such that the fidelity of cannot be reached by using all the remaining components that are not in any explanation. For a detailed explanation of the algorithm details and the reasoning behind various design choices, refer to Appendix
Algorithm 3 GetExxplanations( Fp)
Algorithm ZORRO nn K)
1: S 0. V, Vg, F, = Fp. V, = 0. F, 0
I: V,, +- set vertices in ((n)
2: Rv, < list of E Vp sorted by F((v), F,)
2: F <- set of node features
3: Rr, +- list of E F, sorted by F(Vp.
3: return GetExplanat (ns K, Vn, F)
4: Add maximal element to V. or F. as in
5: while F(V., 2 do
6: V. = V.U argmax F((o)UVs, vEtOPx
Algorithm 2 FV,, F.)
7:
F. FFUU arginax F(V., ([U.U)) SEMPXE (F+)
1: for = O...., samples do
2: Set F.I. i.c. fix the selected values
8:
if if F.) ) S F(V,, then
and otherwise retrieve random values from the respective columns if ((((v,,,))) matches the original pre-
9:
Fr \fT F. P.
10:
else
3:
v. [w), V.
diction of the model then
SV.V..
4:
correct+
13: S = S SUGGeEEplaaaatiiieee
K, V2. F?) 14: S S= U Gettxpplaatioons
5:
return conrect
sumples
Pp)
15: return S
The pseudocode to compute fidelity is provided in Algorithm Specifically we generate the obfus- cated instance for a given explanation S {Va, F.). Ys by setting the feature values for selected node-set V, corresponding to selected features in F., to their true values. Figure [ visualizes how the fixed elements of the feature matrix are determined by choice of node mask V, and feature mask randomly choose value from the set of all possible values for
F, To set the irrelevant values, that particular feature in the dataset X. To approximate the expected value in Eq. (5), we generate a finite number of samples of Ys. We then compute fidelity as the fraction of samples for which the
5

---

Under review as a conference paper at ICLR 2021
dataset
dataset CiteSeer
dataset PubMed
200
150
#Nodes
model
125
100
GAT
GIN
75
APPNP
50
25
-n_
0
(10,0)(10020))
(10,0] (10.20]
Figure 3: The number of explanations found with ZORRO 0.85.
model's s decision matches its original decision. Our implementation of the proposed algorithm will be made public after publication.
CHOICE OF NOISY DISTRIBUTION N
One might argue that the irrelevant components can be set to rather than any specific noisy value. However, this might lead several side effects: in the case of datasets for which feature value of is not allowed or have some specific semantics or for models with some specific pooling strategy, for example, minpool. More specifically, the idea of irrelevant component not that is missing, but its value does not matter. Therefore to account for the irrelevancy of certain components given our explanation, we need to check for multiple noisy instantiations for the unselected components. Our choice of using the global distribution of features as the noisy distribution ensures that only plausible feature values are used. Next, our choice does not increase the bias towards specific values, which we would have by taking fixed values such as 0 or averages.
4 EXPERIMENTS
In our experiments, we tried to answer three primary research questions:
RQ 1. How often do multiple explanations exist for a given prediction? What are the sparsity- fidelity trade-offs for our approach?
RQ 2. How effective is ZORRO as compared to existing approaches in terms of fidelity and sparsity?
RQ Can we discover differences model behavior by post-hoc analysis of explanations?
To answer these research question, we use the datasets Cora, CiteSeer and PubMed from Yang et al. 2016).. We evaluate our approach on four different two-layer graph neural networks: graph convo- lutional network (GCN) (Kipf & Welling 2017), graph attention network (GAT) (Veličković al.) 2018). the approximation of personalized propagation of neural predictions (APPNP) (Klicpera al. 2019), and graph isomorphism network (GIN) (Xu et al. 2019). Table shows the statistics of the datasets and models. For more details of our experimental setup, we refer to Appendix
4.1 MULTIPLICITY AND SIZE OF EXPLANATIONS
Our first result is that multiple (disjoint) explanations indeed possible and frequent. Figure shows the number of nodes having multiple explanations. We observe that, without exception, all GNN models yield multiple disjoint explanations with 50% of the 300 nodes under study have 2 to 10 explanations. The disjoint explanations produced by our algorithm can be understood as disjoint piece of evidence that would lead the model to the same decision. We expect much larger number of overlapping explanations if the restrictive condition the objective here is to show that a decision can be reached in multiple ways, and each explanation practical realization of possible combination of nodes and features that constitutes decision. We are the first to establish the multiplicity of explanations for model predictions, unlike Ying et al. 2019) that outputs only explanation
disjointness is relaxed. However,
soft mask over features and edges.
In general, shorter or sparser explanations are more human interpretable and hence more desirable. We conducted experiments using two fidelity thresholds (7 0.85 and 0.98) and compared the

---

Under review as a conference paper at ICLR 2021
mozd - 6Ck ddiasse Cara
modd GCN dataset Cheseer
model GON (cadaset RubMed
1.0
correctly prodicted Fube
0.8
Truc
Explanation
0.6
0.4
0.2
0.0
85 Nodes
85
85 .90
98
98
85
Features
Nodes
Features
Nodes
Features
Figure 4: Comparison of ZORRO'S 's explanation size measured by the proportion of selected elements, Le., the number of selected nodes is divided by the number of nodes in the computational graph, and the number of selected features is divided by the number of features. For the results of all combinations, Figure
sizes of the first found explanation (see Figure 4 A key observation in this result is that ZORRO is still able to find sparse explanations for high fidelity requirements, i.e., at a 0.98, suggesting that only small number of nodes and features required for most of the predictions. Although there are differences between datasets, the choice of T has a limited influence on the explanations' size. Finally, interestingly find that mispredictions tend to require larger explanation size where explanation size is the fraction of nodes/features selected by ZORRO in comparison to the entire computation graph for the node.
4.2 COMPARISON WITH GNNEXPLAINER
We first note that unlike ZORRO explanation from GNNEXPLAINER is soft mask of importance scores E [0, 1] for node features and edges of the computational graph. In principle, one can choose the top-k features of GNNEXPLAINER with the highest importance values for comparing both the fidelity of both approaches. However, we choose the best settings of GNNEXPLAINER, i.c., the soft mask, to compare the fidelity distributions of both approaches (see Figure 5
As expected, the fidelity of explanations by ZORRO for all nodes is high [0.85, 0.95] or very high (0.95, 1]. However, GNNEXPLAINER exhibits low fidelity, i.c.S 0.70 for fairly large 40% of the nodes. The results show that our explanations are much likelier to preserve the model predictions than the soft explanations of GNNEXPLAIINRR
Table I: Average entropy of the retrieved feature masks
Cora GAT
CiteScer GAT GIN
PubMed GAT
method
GCN
GIN
APPNP
GCN
APPNP
GCN
GIN
APPNP
ZORRO = .98)
2.69
3.07
4.34
3.18
2.58
2.60
4.68
2.78
2.55
2.58
3.21
2.86
GNNEXPLAINER 7.27
7.27
7.27
7.27
8.21
8.21
8.21
8.21
6.21
6,21
6.21
6.21
But do the explanations from ZORRO have fidelity because they are less sparse than GNNEX- PLAINER? To systematically measure this, we computed the entropy of normalized probability dis- tributions over feature masks output by both approaches as measure of sparsity, see Table 1 Note that entropy is upper bounded by the log of the number of features (see Proposition D The high entropy for GNNEXPLAINER corresponds mask distribution closer uniform distribution, i.c., all features would have equal importance, In the case of ZORRO, the entropy is precisely equal to the log of the number of selected elements. The much lower entropy (as compared to GNNEXPLAINER) achieved by ZORRO shows that the hard masks are sparse.
Proposition 1. Let be the normalized distribution of explanation (feature) masks. Then H(p) S
(o) where M corresponds to complete set of features. In particular for ZORRO we have (()) = log (sleectiooonssze)) [Proof see Appendix B
We also visualize the output of the soft explanation a node that achieves a fidelity of 1, see Fig- ures and 11 We observe that the mask values distributed around given value explaining the

---

Under review as a conference paper at ICLR 2021
low entropy. In such cases, when all masks for all features take low values, small-sized explanation cannot be obtained as all components have similar importance. Effectively all features are kept in the input and no wonder that the highest value of fidelity is achieved. From the above two experi- ments, we conclude that ZORRO produces both sparse and high-fidelity explanations in comparison to GNNEXPLAINER.
300
GCN
GAT
GIN
APPNP
250
Method
Nethod Zomi BS zerte
Metrod
Nethod
Count
200
Panto .5
Parto d5 Earry
Zerr A5
150
Earo..0
Zarra
100
50
Low
Med.
High
V. High
Low
Med.
High
V. High
Low
Med.
High
V. High
Low
Med.
High
V.gigh
Figure 5: Comparison of fidelity, GNNEXPLAINER vs. ZORRO. Low: 0.7, Med.: (0.7,0.85). High: [0.85, 0.95) and V. High: 2 0.95
4.3 HOMOPHILY OF THE EXPLANATIONS
One of the motivations of post-hoc interpretability is to use explanations to derive insights into a model's inner workings. Towards this, we investigate the homophily of the selected nodes from our explanations since GNNs are known to exploit the homophily in the neighborhood to learn powerful function approximators. We define homophily of the node as the fraction of the number of its neighbors, which share the same label as the node itself. Intuitively, it should be easier to label node with the correct label if a larger fraction of nodes in its computational graph shares its label.
In what follows, we use homophily to refer to the homophily of node with respect to the selected nodes in its first found explanation. True/Predicted homophily refers to the case when true/predicted node labels are used. We investigate the joint distribution of true and predicted homophily exhibited by the studied node sample. The results are shown in Figure 6
We make the following observations.
Observation 1 Nodes depicting the orange regions on the extreme left side of the plots are nodes that exhibited low true homophily but high predicted homophily. The class labels for such nodes are correctly predicted. However, the corresponding nodes in the explanation were assigned the wrong labels (if they were assigned the same labels as that of the particular node in question, its predicted homophily would have been increased).
Observation 2 Several vertices corresponding to blue regions spread over the bottom of the plots have low predicted homophily. These nodes incorrectly predicted, and their label differs from those predicted for the nodes in their explanation set. The surprising fact is that even though some of them have high true homophily close 1, their predicted homophily is low. This also points the usefulness of our found explanation in which we conclude that nodes influencing the current node do not share its label.
We also note that for GIN and APPNP, we have some nodes with true homophily and predicted homophily close to 1 but are incorrectly predicted. This implies the node itself and the most influential nodes from its computational graph have been assigned the same label. We can conclude that the model based its decision on the right set of nodes but assigned the wrong class to the whole group.
Observation 3
4.4 RETRAINING BASED ON LOCAL MASKS
To evaluate our ZORRO independent from our proposed fidelity measure, we use our local method as a global feature selection method and study the induced performance drop. We retrieved the explanations for all training nodes of the GNN on Cora and selected the top k features, which were most often in the first explanation. Similarly, we retrieved all explanations with GNNExplainer and selected the top k features with the highest summed feature mask values. As Showss ZORRO outperforms GNNExplainer in all cases. Selecting the 100 most important features (with respect to ZORRO), has only a minor effect (A 0.01) on the test accuracy compared to the training on all 1433 features.
8

---

Under review as a conference paper at ICLR 2021
model GCN
model GAT
model GIN
model APPNP
2.0
Hemophit (redicted
0.8
0.6
0.4
22
1a
02 Homophily (True Labels)
Homophily (The Labek]
Homophily (Tre Label)
Homophlyy (Thu Labek]
Figure 6: Dataset PubMed. The joint distribution of the homophily with respect to the nodes selected in the ZORRO'S s explanation (r 0.85) with true and predicted labels. The orange contour lines correspond to the distributions for correctly predicted nodes, and the blue one corresponds to incorrectly predicted nodes.
Table 2: Test accuracy after, retraining GCN on Cora based on the top features. We repeated the retraining 20 times, report the mean and observed a variation of below .001 in all cases.
Method
k =
1
k: =
5
k
10
k
50
k
100
all
ZORRO (T = .85)
0.24
0.50
0.71
0.77
0.78
0.79
GNNEXPLAINER
0.15
0.21
0.35
0.54
0.66
0.79
4.5 EXPERIMENT ON SYNTIETICC DATASET
In GNNExplainer (Ying et al. 2019), the authors proposed to use synthetic datasets built from at- taching motifs, such as 'house grid, rings, to random Barabási-Albert (BA) graphs or regular trees. We evaluated our approach ZORRO on the synthetic dataset, which has features. The details of the experiment nations as well as the explanation of the random closest neighborhood baseline (in which we sample nodes randomly from the closest neighborhood). The task is to explain all the nodes from the house motif, and the ground truth are the five nodes from the corresponding house.
the synthetic dataset are stated in Appendix E and includes some node expla-
Table shows the performance of ZORRO with T .85 and T .98, GNNEXPLAINER and the random closest neighborhood heuristic. The heuristic outperforms all methods with respect to recall because it selects nodes only from the closest neighborhood. However, ZORRO achieves the highest precision and accuracy and outperforms GNNEXPLAINER.
Table 3: Average performance of the node (first) explanation on the synthetic dataset.
Method
# Nodes
Recall
Precision
Accuracy
Zorro (T .85)
2.48
0.35
0.94
0.90
Zorro (T .98)
5,42
0.50
0.90
0.90
GNNEXPLAINER
5.34
0.35
0.33
0.79
Random Closest Neighborhood
5.00
0.67
0.67
0.90
5 CONCLUSION
We propose ZORRO as a post-hoc explanation method for the decisions made by GNN models. Inspired by rate-distortion theory, we frame the problem of explaining GNN models as a feature and node selection problem so to minimize the expected deviation from the original decision. We proposed a simple combinatorial procedure ZORRO, which retrieves disjoint explanations consisting of binary masks for the features and relevant nodes while trying to optimize for fidelity. With our extensive experiments, we show multiple explanations are possible for given decision, unlike earlier approaches that provide soft mask. Furthermore, our explanations higher fidelity than existing approaches. Finally, our analysis of the homophily in the explanations highlighted differences in the models' behavior between correctly and wrongly predicted nodes.
sparser and achieve

---

Under review as a conference paper at ICLR 2021
REFERENCES
Alexander Binder, Grégoire Montavon, Sebastian Lapuschkin, Klaus-Robert Müllrr, and Wojciech Samek. Layer-wise relevance propagation for neural networks with local renormalization layers. In International Conference on Artificial Neural Networks. Springer, 2016.
Brandon Carter, Jonas Mueller, Siddhartha Jain, and David Gifford. What made you do this? un- derstanding black-box decisions with sufficient input subsets. arXiv preprint arXiv: 18 11.003805, 2018.
Jianbo Chen, Le Song, Martin Wainwright, and Michael Jordan. Learning to explain: An information-therreti perspective model interpretation. arXiv preprint arXiv:180200781, 2018.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometrie. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
Thorben Funke, Tian Guo, Alen Lancic, and Nino Antuloy-Fantlln. Low-dimensional sta- tistical manifold embedding of directed graphs. In International Conference on Learning Representations, 2020. /ttptttps.//eeeeiiiiie....
Maximilian Idahl, Megha Khosla, and Avishek Anand. Finding interpretable concept spaces in node embeddings using knowledge bases. In Machine Learning and Knowledge Discovery in Databases- International Workshops of ECML PKDD 2019, pp. 229-240. Springer, 2019. doi:
10.11077/978-3-000433322. 20.
Bo Kang, Jefrey Lijffijt, and Tijl De Bic. Explaine: An approach for explaining network embedding- based link predictions. arXiv preprint arXiv:1904. 194494994.,1694, 2019.
M. Khosla, V. Setty, and A. Anand. comparative study for unsupervised network representation learning. TKDE, 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations (ICLR), 2017.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. International Conference on Learning Representations (ICLR), 2019.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, et al. Explainability methods for graph convo- lutional neural networks. In Proc. of the Conference on Computer Vision and Pattern Recognition, pp. 10772-10781, 2019.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. why should i trust you?" cxplaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference knowledge discovery and data mining, pp. 1135-1144 2016.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Anchors: High- precision model-agnostic explanations. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Chris Sims. Rate-distortion theory and human perception. Cognition, 152:181-199 2016.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of the 34th International Conference Machine Leamiin-Voluuee 70, pp. 3319- 3328. JMLR. org, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, 2018. hatttps://operreviiee wttp:/wwwwww.weeeeeeeeeeeeeeeeee
accepted poster.
10

---

Under review as a conference paper at ICLR 2021
Kelvin Xu, Jimmy Ba. Ryan Kiros, Kyunghyun Cho, Aaron Courville, Ruslan Salakhudinov, Rich Zemel, and Yoshua Bengio. Show, attend and tell: Neural image caption generation with visual attention. In ICML, 2015.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations, 2019.
Zhilin Yang, William W. Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. 2016.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnn explainer: A tool for post-hoc explanation of graph neural networks. arXiv preprint arXiv:1903.03890 2019.
Jinsung Yoon, James Jordon, and Mihacla van der Schaar. Invase: Instance-wise variable selection using neural networks. 2018.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. KDD '20, pp. 430 438. Association for Computing Machinery, 2020.
APPENDIX
A ADDITIONAL DETAILS TO OUR ALGORITHM
In the design of our ZORRO algorithm, we have made several choices, which we explicitly want to explain in detail here. In general, we have make the following design choices: initialization of first element, iterative adding further elements, recursive design. Table contains the description
(which we repeat for completeness) all variables used within the Algorithms/ and
Table 4: Notation used in the algorithms
Variable
Description
n
Explained node
T
Threshold of fidelity
K
Number of nodes and features evaluate per iteration
V
Nodes in the computational graph of
G(n)
Computational graph of n Set of all possible features Set of possible nodes that can be included an explanation
F
VP
F
Set of possible features that can be included in an explanation Set of all explanations
S
V,
Set of remaining nodes Set of remaining features Selected nodes, i.c., nodes the current explanation
F,
V.
F.
Selected features, i.c., features in the current explanation Ordered list of the possible nodes
Rv,
RE
Ordered list of the possible features Fidelity, which takes a node set as first argument and a feature set as second argument
F(.))
V.
Best node candidate set found Best feature candidate set found Randomized feature matrix, where the features F, the nodes V, are kept fixed, see Eq. (4)
F,
Y(V,F.)
(())
GNN evaluated on à specific feature matrix, in Alg. only evaluated to retrieve the class label of node
X
Feature matrix of all nodes in G
Initialization of first element. A single explanation [V,, F,} consist selected nodes V, and selected features F.. The challenge select the first node and feature is the following: Selecting

---

Under review as a conference paper at ICLR 2021
only node only feature yields non-informative value, ie., F(fr).0) and F(O. {f}) for all v E Vn, and f E F' and some constant с E [0, 1]. The search for the optimal first pair would require Fl evaluations of the fidelity, which is in most cases too expensive. Therefore, we propose to use a different strategy, which also contains information for the following iterations. Instead of evaluating, which pair of feature and node yields the highest increase, we assess the nodes and features in a maximal setting of the other. To be more precise, we assume that, if we search for the best node, all (possible) features F' were unmasked:
argmax F() "EV,
(8)
Similarly for the features, we assume that all (possible) nodes are unmasked:
argmax SEF,
F(Vp: (f})
Whichever of the nodes or features yields the highest value is the first element of our explanation. Consequently, the next selected element is of different type than the first element, e.g., if we first choose a node, the next element is always that feature, which yields the highest fidelity based on that single node. We perform this initialization again for each explanation since for each explanation, the maximal sets of possible elements Vp and F are different.
Iterative search. The next part of our algorithm, which is the main contributor to the computational complexity, is the iterative search for additional nodes and features after the first element. A full search of all remaining nodes and features would require |V, + |Frl fidelity computations. To significantly reduce this amount, we limited ourselves to a fixed number K nodes and features, see Algorithm 3 To systematically select the K elements, we use the information retrieved in the initialization by Eq. (8) and (9). We order the remaining nodes V, and F5 by their values retrieved for Eq. (8) and (9) and only evaluate the top K. In Algorithmm]] we have denoted these orderings by Rv, and R.F and the retrieval of the top K remaining elements by tV, Rv, and top (Fr, Rr We also experimented with evaluating all remaining elements but observed no performance gain or inferior performance to the above heuristic. As a reason, we could identify that in some cases, the addition of single element (feature or node) could not increase the achieved fidelity. Using the ordering retrieved from the "maximal setting", we enforce that those elements are still selected, which contain valuable information with a higher likelihood. In addition, we experimented with refreshing the orderings Ry, and RF, after some iterations but observed similar issues as in the unrestricted search.
Recursive design. We explicitly designed our algorithm in a way such that we can retrieve multiple explanations, see 13 line 15 Algorithm 3 We recursively call the Algorithm twice, once with a disjoint sete the call in Tine T5 (only elements from the remaining set of nodes V, can be selected), and similarly in line 13 with disjoint feature set. Hence, the resulting explanation selects disjoint elements from the feature matrix since either the rows or columns are different from before. As greedy and fast stop criteria, used each further iteration, the maximal reachable fidelity of F(V, Fp).
Complexity analysis. The computational complexity of Algorithm 3 to retrieve an explanation Fv) with possible nodes Vp and possible features Fp is
O#tsapples x (IVpl + |Fp) + K(VV + (.)))(()).
where ((4) is the computational complexity for the forward pass of the GNN on the computational graph G(n). For the first explanation, we have
0 O#samples x ((V5) + |F] (07+*K[[6)) + +(
B PROOF OF PROPOSITION 1
Proof. We first compute the normalized feature mask distribution, p(f) for f E F (F is the complete set of features). In particular, denoting the mask value of ff by mask(f), we have
mask(f)
p() Erer mfsk(f)
12

---

Under review as a conference paper at ICLR 2021
Then (p)) E JEF ((ff)logll which achieves its maximum value for the uniform distribu- tion, i.c, p(f) = [FT. For ZORRO, let F, be the set of selected features. For each f E Fs. we then have p(f) 1 [F%] and O otherwise. The computed entropy is then equal to lo)() We want to point out that the proposition also follows for the case of node masks.
C EXPERIMENTAL SETUP
We focus on explaining the decisions of GNN models with respect the task of node classification. We fix the number of layers to two for all models and keep the rest of the model architectures and parameters as in the original paper. We train the models 200 epochs with ADAM optimizer and a learning rate of 0.01 and a weight decay of 0.0005. We use the model and GNNExplainer implementations of PyTorch Geometric Library (Fey & Lenssen 2019). For GNNExplainer, we use the default values of 100 epochs and learning rate of 0.01. For each dataset, we randomly selected 300 nodes and retrieved the explanations of GNNExplainer, and our method for the fidelity values {0.85, 0.98). )- We will publish the list of selected nodes together with the implementation. We used 100 samples to calculate the fidelity with Algorithm and and set K = 10 in our experiments.
Our implementation is based PyTorch Geometric 1.6 and Python 3.7. All methods were executed on a server with 128 GB RAM and Nvidia GTX 1080Ti.
Datasets. Three well-known citation network datasets Cora, CiteSeer and PubMed from Yang et al. (2016) where nodes represent documents and edges represent citation links. The class label is deseribed by similar word vector
index of category. Statistics for these datasets can be found in Table 1. We used the datasets, including their training and test split from the Py PyTorch Geometric Library, which corresponds to the data published by Yang al. (2066).
Table 5: Datasets and statisties. The test accuracy calculated on 1000 nodes.
Test Accuracy
Name
Classes
Features
[V]
[E]
GCN
GAT
GIN
APPNP
Cora 7
1433
2708
10556
0.794
0.791
0.679
0.799
CiteSeer
6
3703
3327
9104
0.675
0.673
0.480
0.663
PubMed
3
500
19717
88648
0.782
0.765
0.590
0.782
Models. As models we selected the well-known graph convolutional network (GCN) (Kipf & Welling 2017) and graph attention network (GAT) (Veličković et al. 2018) as well as the approxi-
mation of personalized propagation of neural predictions (APPNP) (Klicpera et al. 2019), and graph isomorphism network (GIN) (Xu et al.) 2019). APPNP utilizes a connection between PageRank and GCN, especially those with many layers, and extends GCNs based on the personalized PageRank. Xu et al. (2019) proposed GIN to match the representational power of the Weisfeiler-Lehnee graph isomorphism test by extending the expressiveness of the feature aggregation.
D ADDITIONAL EXPERIMENT RESULTS
This section contains additional visualizations:
Figure 7 shows the explanation size of Cora, CiteSeer, and PubMed for the models GCN, GIN, GAT, and APPNP.
Figure and Figure visualize the joint homophily distributions for the dataset Cora and CiteSeer.
Figure 10 shows the feature mask distribution of GNNEXPLAINER for single nodes with fidelity 1. Figure shows the feature mask distribution GNNEXPLAINER for all explained nodes.
To be transparent about the time of executing ZORRO, Figure 12 visualizes the runtime recorded during our experiments to retrieve the first explanation for ZORRO. For the runtime experiments, include the gradient approach used baseline in GNNEXPLAINER GRAD is gradient-based
13

---

Under review as a conference paper at ICLR 2021
Cor
mosel
1.0
Explanation Size
0.8
0.2
0.0
model GAT detanat Crea
model SAT detnset Cheeeet
model CAT detasel PubMed
1.0
Explanation Size
0.8
0.6
0.4
0.0
dataset
CiteSeer
Sataret PubMed
1.0
Explanation Size
0.4
0.2
0.0
datimee
model
PubMedd
1.0
correctlyy predicted Palse True
Explanation Size
0.8
0.6
0.0
t=.85 85 == 98 T= 85 == 98
== 885 == 98 == 85 r= 98 Nodes
t 85 == 98 T= 85 T .98 Nodes
Nodes
Features
Features
Features
Figure 7: Comparison on ZORRO'S explanation size measured by the proportion of selected ele- ments, i.e. the number of selected nodes is divided by the number of nodes in the computational graph and the number of selected features is divided by the number of features.
14

---

Under review as a conference paper at ICLR 2021
model GGN
model GAT
model GIN
model APPNP
2.0
a
0.6
20
0.4
Homophity
0.2
0.0
4
Homophily (The Labek)
Homophily ITre Label)
Homophly (Thu Labek]
Homophily (True Labels)
Figure 8: Dataset-Cora Joint distribution of the homophily with respect the selected subgraph (in the explanation of ZORRO (T .85) with true and predicted labels. The orange contour lines cor- respond the distributions for correctly predicted nodes and the blue one correspond incorrectly predicted nodes.
model m GCN
model GAT
model GIN
model m APPNP
2.0
Homeghiy (Predeted
0.4
2.2
9.0
0.8 Homophily (True Labels)
0.2
0.4
0.2 06 Homoshily (True Labels
1.
0.6 0.8 Homeshily (True Labels)
022
Homophily (Tre Labels
Figure 9: Dataset-CiteSeed Joint distribution of the homophily with respect to the selected sub- graph (in the explanation of ZORRO (r = .85)) with true and predicted labels. The orange contour lines correspond to the distributions for correctly predicted nodes and the blue one correspond to incorrectly predicted nodes.
method in which compute gradient of the GNN's loss function with respect the adjacency matrix and the associated node features (Ying et al. 2019) As stated in the computational complexity above, note that the runtimes do directly follow the graph size. To be precise, our approach is strictly local, i.e., it is independent of the input graph, however large it might be. The fastest average runtime we observed on PubMed, which has the highest number of nodes. Secondly, we indeed have tunable relationship between fidelity threshold and runtime.
Currently, our implementation follows the presented Algorithms 22 i.e., designed for explained single node. If multiple explanations V C V are requested, this initialization step can be performed for all requested nodes at the same time (for the first explanation). Then Vn, has to be replaced by UVV, E V} and in each step of the fidelity, the prediction agreement with respect V has to be checked and saved separately. Hence, the orderings Ry, and Ry, are computed for all nodes
Cora
CiteSeer
PubMed
15
100
Count
10
50
20
0.25
0.30
0.35
0.25
0.30
0.35
0.25
0.30
0.35
Features Mask Value
Features Mask Value
Features Mask Value
Distribution of GNNEXPLAINER" feature mask values corresponding explanations of a single node of GCN, where a fidelity of 1.0 is achieved. For the distribution of all nodes, models, and datasets, refer to Figure I1
Figure 10:
15

---

Under review as a conference paper at ICLR 2021
GCN
GAT
GIN
APPNP
10a
10a
10a
10a
Cora
10a
101
10
101
10a
10a
CiteSeer
10a
10a
10
10a
10a
10a
10
PubMed
103
10a
10a
10a
10a
10
10a
10a
0.75 Features Mask Value
0.25
0.50
0.75 Features Mask Value
0.25
0.50
0.25
0.50
0.75
0.25
0.50
0.75
Features Mask Value
Features Mask Value
Figure 11: Distribution of GNNEXPLAINER'S 's feature mask values corresponding to explanations of all explained nodes.
16

---

Under review as a conference paper at ICLR 2021
dataset Com model GCN
dataset Cera model GAT
dataset Core model in GIN
dataset Cora| model APPNP
ChNExplaieer
120
CNNExplainer GRAD
200
CNNEsplaieer GRAD
100
GRAD
GNNExplainer
20-
100
50
40
60-
400
40
200
20-
dataset CiteSeer| model GCN
datasel /eeeSerr| model CAT
dataset -CteSeer model CIN
dataset
CCieSSeer model APPNI
70
GNNExpaainer GRAI
GANExplainer
CNNExppainer
GNNEEppaiinr
60-
GRAD
.GRAD
GRAD
60
4000
50
2000
30
30
0000
20-
20-
10
10
1000
10-
dataset PubMeed model
dataset Mub model -GA
dataset- PubMed model
GIN
PubMed model
APPNP
GNNExplainer GRAD
GNNExolainer GRAD
GNNExplaieer CRAD
GNNExplainer
120
123
150-
100
GRAD
100
100
125
80-
80-
1.00
60-
02
0.7
0.7
0.7
Fidelit
Fidelit
Fidelity
Fidelit
Figure 12: Comparison of the runtime by model and dataset. The cirlce and the cross mark the av- erage fidelity and average time of GNNEXPLAINER and gradient baseline. The boxplots correspond to ZORRO and visualize the runtime for retrieving the first explanation, which has at least the given fidelity. For ZORRO, we recorded the time after the initilization, which can be pre-computed for all nodes simultaneously. Time is measured in seconds.
simultaneously. Limiting the maximum number of features or neighbors would additionally reduce the runtime because the outliers would be avoided.
E EXPERIMENTS ON SYNTHETIC DATASET
The synthetic dataset is generated by generating two communities consisting of house motifs at- tached to BA graphs. Each node has eight feature values drawn from (0, 1) and two features drawn from A (,) for nodes of the first community or (1, otherwise. In addition, fol- low the published implementation of GNNExplainer, the feature values are normalized within each community, and within each community, 0.01 % of the edges are randomly perturbed.
The eight labels are given by the following: for each community, the nodes of the BA graph form a class, the "basis' of the house forms a class, the 'upper' nodes form a class, and the rooftop is a class. The used model is a layee-layer GCN, which stacks each layer's latent representation and uses a linear layer to make the final prediction. The training set includes 80% of the nodes.
Since GNNEXPLAINER only returns soft edge mask, we sorted them and added both nodes from the highest-raniee ranked edges until at least five nodes were selected. In this way, we retrieved hard node masks, which are necessary to compare with the ground truth.
To highlight this task's insufficient design, we added as a very simple baseline, a random closest neighborhood heuristic, which randomly selects nodes from the nearest neighborhood. For example, a node has two direct neighbors and 15 nodes in the second neighborhood, we select the two immediate neighbors and sample another three randomly from the second neighborhood.
17

---

Under review as a conference paper at ICLR 2021
For the synthetic dataset, we know how many features not only randomly distributed but contain information about the community. Therefore, we selected the two features correlated with nodes' community membership ground truth and evaluated the methods' performance with respect to their feature selection. For GNNEXPLAINER, we selected from the calculated soft feature mask those two features with the highest value. In contrast, ZORRO directly select this number during inference. Table [ shows that GNNEXPLAINER fails to select the informative features and that ZORRO consistently selects the informative features. The configuration with lower threshold .85) shows that we only need one of the two informative features in most cases. However, to reach a higher threshold of r = .98, more features are required.
Table 7 shows how connected the retrieved explanation is. In other words, how close is the explana- tion to connected subgraph? We measure this by counting the number of connected components in the explanation with and without the explained node. As we can see, even though in GNNEX- PLAINER the number of connected components limited to four or three in the case with respec- tively without the explained nodes. This is the case since select the nodes based on edges, i.e., each connected component consists at least two nodes. The explanation tends to be way more disconnected than those of ZORRO.
Table 6: Performance of the feature masks on the synthetic dataset
Method
Features
Recall
Precision
Zorro (T = .85)
1.48
0.98
0.68
Zorro .98)
2.21
0.94
0.88
GNNEXPLAINER 2.00
0.08
0.08
Table Number of the connected components in the explanations of the synthetic dataset. Componentswithou is the number of connected components in the subgraph induced by the selected nodes. Components same, only with the explained node added the selected nodes.
Method
# Components,ath
# Components
Zorro .85)
mean std mean std
1.14
1.06
0.50
0.68
1.27
1.35
Zorro (T .98)
1.14
1.22
GNNEXPLAINER
mean
1.73
1.56
std
0.85
0.64
To exemplify the performance of our method, the Figure 14 and Figure 15 show some examples of found explanations for correctly respectively wrongly predicted nodes. We compare the expla- nation of ZORRO against the baseline GNNEXPLAINER. The first node in Figure 14 shows that ZORRO finds multiple explanations, which correspond the ground truth motif. In contrast, GN- NEXPLAINER ranks four nodes from the BA graph among the highest, which should not affect the prediction of the GCN. The illustrations in e) and d) show similar pattern. In addition, we see in c) the reason for low recall of ZORRO. Often only 2-3 nodes of the ground truth are sufficient to reach a high fidelity.
shows some explanations of wrongly predicted nodes. The first node 307 is not in the training set, and from ZORRO's 's explanation, we get some reasoning about the prediction. The GCN only needs the value from the node itself and two neighbors, which are (wrongly) predicted as the "basis" of the house. Hence, the node is predicted as the top wall, which would follow the following pattern: If from its first neighborhood and its second neighborhood each node is the basis, then the node is a top wall node. However, both neighbors, which are important for the prediction, were predicted false, and hence the resulting prediction is also wrong. This observation agrees with the observed "homophily of wrong predictions" of the real datasets. GNNEXPLAINES 's explanation of the same node is way larger and includes nodes from the house graph of the second community.
Figure 1
18

---

Under review as a conference paper at ICLR 2021
Figure 13:
Legend showing the symbols for the different classes of the synthetic dataset. Left and right the house graphs and both nodes (square and rotated square) represent the nodes in the BA graphs of the two communities.
The second example Figure [5 shows an example, where the explanations of ZORRO and GN- NEXPLAINER more similar. Both methods retrieve (mostly) members of the ground truth as an explanation for the false prediction.
19

---

Under review as a conference paper at ICLR 2021
(a) Node 1315: ZORRO
(h) Node 1315: GNNEXPLAINER
(c) Node 433: ZORRO
(d) Node 433: GNNEXPLAINER
Figure 14: Two nodes of the synthetic example explained by ZORRO and GNNEXPLAINER, which are correctly predicted. The first column shows the nodes with the ground truth labels. All nodes from the ground truth (house graph), well as all the nodes selected in the explanation colored as green (training set) and blue (test set). The second column shows the predicted classes and the explanation(s), where included in black all unselected nodes of the ground truth. All other colors correspond to each explanation, e.g., three disjoint explanations in a). The red circle highlights the node, which explained. The last column shows the computational graph of the explained node again with the ground truth labels.
20

---

Under review as a conference paper at ICLR 2021
(a) Node 307: ZORRO
(b) Node 307: GNNEXPLAINER
(c) Node 371: ZORRO
(d) Node 371: GNNEXPLAINER
Figure 15: Two nodes of the synthetic example explained by ZORRO and GNNEXPLAINER, which wrongly predicted. Style same Figure 14
21


Reviews:
[{"review_id": "nj1248dQWWG", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose ZORRO, a post-hoc explanation method for node classification with graph neural network architectures. ZORRO leverages rate-distortion theory to generate masks that select nodes in the target node neighbourhood and their most important features. \n\n* The problem is very relevant to the GNN community, and I am glad to see more works coming in on this topic.\n* The idea of relying on rate-distortion theory is interesting and original, and to the best of my knowledge this is the first time I see it used to tackle this research problem.\n* The paper is well structured and organised.\n* The original contribution is sufficient.\n* Related work is sufficiently well covered.\n\nNevertheless, the paper suffers from shortcomings:\n\nA) The paper claims that ZORRO can generate multiple, disjoint explanations, apparently all highly faithful. This seems to be at odds with the authors' claim to explain the behaviour of the model. In other words, if I were on the receiving side and I was given multiple _disjoint_ explanations, which one should I trust more? How can explanations shed a light on the  behaviour of models if they are disjoint? I see ZORRO is able to generate overlapping explanations as well (a property compatible for example with example-based technique in XAI literature such as counterfactual explanations), but I have mixed feelings on the effectiveness of disjoint explanations in practice.\n\nB) A drawback of this work is the complete absence of human-based evaluation. I acknowledge explainable AI literature is ripe with examples of accepted papers, but the authors seem to deliberately disregard this aspect (“We [.. ] are not interested if an explanation is congruent to human understanding\", Sec1). If humans are not important, then what is the reason you explain your predictions? If the goal is limiting to debugging a model, perhaps the narrative should be revisited. All in all, I believe users should be central in an XAI piece, and papers in this area should help the reader understand if the generated explanations meet users expectations - even in a ML conference such ICLR, even for a 8-page paper.\n\nC) The paper does not include any examples of the generated explanations. It is hard to figure out if the claimed fidelity brings meaningful results in practice, and the reader is left with this doubt. Aside from a full-fledged evaluation campaign (see A. above), some examples would really help make the case. \n\nD) Experiments do not include any evidence of whether ZORRO explanations work in practice. Besides, as I mentioned above, the author should probably clarify which audience they are targeting (i.e engineers debugging a model, end users trying to understand the reasons for a specific model outcome, etc.)\n\nE) I was expecting experiments to assess the impact of \\tau (the user-defined fidelity threshold). The authors experiment with .98 and .85 - and “the choice of \\tau has limited influence”, but I would have expected empirical evidence for such statements (i.e. experiments on a wider range of \\tau, to assess size and fidelity). If choosing a desired fidelity is not crucial, the paper should show so.\n\nF) There are not experiments on runtime complexity. The reader is left without evidence of how long it takes to generate an explanation for a target prediction.\n\nG) It is unclear if ZORRO achieves more faithful and also smaller explanations than GNNExplainer. Sec 4.2 suffers from clarity issues, as long as Figure 5.\n\nH) Some sections could be better clarified, to help the reader understand important aspects of the work: Example: In sec1, the “notations” paragraph would benefit from proofreading and re-wording. Sec 4.2 could also be refined.\n\nMinor:\n* Size matters for explanations, but smaller does not always mean better. For example, in medical decision support systems, some clinicians may prefer longer and more thorough explanations. Your milage may vary. \n* Figure 5 is poorly legible.\n* Some typos along the way (e.g. “denotes the binary column vector of selected nodes and Fs denote the binary row vector of selected nodes “ sec 1, “Effectively the complete input is presented as an input” in 4.2)\n\nQuestions for the authors:\n* Q1) How does ZORRO decide the size of each computational graph to work with (i.e. the size of the neighbourhood)?\n* Q1) It is not entirely clear to me how you ZORRO generates multiple explanations? I could not find how this is done in Algorithms 1-3. Could you please clarify?", "extra_scores": {}, "extra_text": {}}, {"review_id": "foRQOofAM41", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This work proposes to explain graph neural networks using hard masking techniques. Specifically, it tries to find the node mask $V_s$ and feature mask $F_s$ which can identify the most important information of the input such that the masked information can yield a high fidelity score. This work proposes a greedy method, ZORRO, to explore these hard masks, which can be used as the explanations of the prediction. Experimental results are interesting and promising.  \n\nStrengths:\n+ The task is very important. GNNs are very popular but they are mostly treated as black-boxes. Interpreting GNNs is still less studied.\n+ Compare with GNN-Explainer, this work focuses on using hard masks to explain GNN predictions. It is a reasonable choice since soft masks, which are used in GNN-Explainer, may introduce new semantic meaning or noise to the node representations since these representations are very sensitive.\n+ Experimental results are very interesting. First, there exist multiple explanations for the same input graph that they both lead to high fidelity scores. Second, the proposed method can obtain high fidelity scores than GNN-Explainer and more sparse explanations. In addition, this works studies several types of GNNs, such as GCN, GAT, GIN, APPNP.\n\nWeaknesses:\n- The connection between the proposed method and data compression is not convincing. From my understanding, it belongs to the masked-based interpretation methods, which is widely studied in other domains, such as image and NLP. Then I do not think it is something new from other fields--data compression in information theory.\n- In the proposed method, all nodes share the same feature mask $V_s$. Is it a proper choice? Is it possible that different nodes may have different important features? Then probably it is better to not share the $V_s$?\n- In the proposed method, the ordering information $R_V$ and $R_F$ are stored. It is computed in the beginning and keep fixed for later steps. However, in the later steps, the algorithm will update the $V_S$ and $F_s$, then why do we use the same ordering information? Top nodes, in the beginning, may not be top any more after some nodes/features selected?\n- The method itself is very straightforward, which is a simple greedy algorithm. Then I believe the technical contribution may not reach the bar of ICLR.   \n- The algorithm is not clearly explained. What’s the meaning of $V_r$, $F_r$, $R_{V_p}$, and $R_{F_p}$, etc.? How are they initialized?\n- For the comparisons with GNN-Explainer, we need to see some real examples—explanations for both correct predictions and incorrect predictions. It is not enough to just report numerical numbers.\n\n\nI am willing to adjust my score if my concerns are properly addressed.\n\n=====Update after rebuttal=====\n\nI have read the authors' rebuttal. However, my concerns are not well addressed. \n\n1. There are a lot mask based methods for interpretation in different domains [1] [2] [3] [4]. Existing methods [1][2][3] are providing post-doc explanations for a pretrained model. I still believe \"the connection between the proposed method and data compression is not convincing\". \n\n2. I still believe the novelty is limited. \n\nHence, I am keeping my score unchanged. \n\n[1] GNNExplainer: Generating Explanations for Graph Neural Networks, NIPS 2019\n\n[2] Real Time Image Saliency for Black Box Classifiers, NIPS 2017\n\n[3] Learning to Explain: An Information-Theoretic Perspective on Model Interpretation, ICML 2018\n\n[4] Rationalizing Neural Predictions, EMNLP 2016\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KaUa_fxo27w", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors address the problem of explaining the behaviour of graph neural networks (which operate on a computation graph based on their k-hop neighbourhood) such as a graph convolutional network (GCN). \n\nThe core idea is to identify, for each node v in the graph, the nodes and features of the graph most relevant to the behaviour of the GNN for node v. That is, the goal is to find a subgraph of the computation graph associated with a node v in the graph. Importantly, the authors propose to test whether the chosen subgraph is relevant (and the complement wrt the computation graph irrelevant) by adding random noise on the parts deemed irrelevant by their method. \n\nThe method is evaluated through a metric called fidelity, which is the agreement in label output between the behaviour of the original and masked GNN, in expectation over the noise distribution. \n\nWhile overall a well-written paper, a source of confusion is the authors tendency to conflate the computation graph and the graph to which the GNN is applied. The most important notion here is S, defined as a subset of the computational graph. When defining this, it is important to also define precisely this computation graph. What does it look like (abstractly, independent of the GNN instance used)? For instance, there is a nice compact way to unify most message-passing neural networks. (see e.g., https://pytorch-geometric.readthedocs.io/en/latest/notes/create_gnn.html) \nWhen you look at this definition, you see that there are several learnable functions (phi, etc.), the aggregation function, and finally the classification layer. Now, in your definition of a computation graph, what are the nodes? Are the applications of the learnable functions each a node? What about the aggregation (one node?). Again, I think for the reader to fully understand how your explanations S look like, this needs to be rigorously defined. My assumption here was that the computation graph groups computations such that nodes in the computation graph and nodes in the graph to which the GNN is applied coincide. Generally, I think you should spend more effort on section 3. The notation in the argmax statements in section 3.1 is also strange. For instance, S is defined as a pair. So it should be written as argmax F((V_p, {f})). Also, what is the p here? \n\nAnother worry I have is the efficiency of the approach. If your average number of features and nodes that exceed the fidelity threshold is K (the average size of S) and the graph has N nodes and F features, you need to evaluate the GNN KN+KF times to obtain an explanation for one node. For large graphs and/or graphs with numerous features, this can be expensive. And this is for the case when you compute the expectation with one Monte-Carlo sample from the noise distribution.\n\nThe most disappointing aspect of the paper, however, is the experimental evaluation. Sure it is interesting to assess the multiplicity and size of explanations. What would be more interesting, however, is to evaluate how faithful your explanations really are. And here is where I have a disagreement with your assumptions. You write “[...] that is completely faithful to the model i.e., the explanation achieves the fidelity value of 1.” But achieving a fidelity of 1 does not mean that your explanation is faithful. We could only know this if you removed the nodes and features and retrained the model with the same seeds/initialization. There is an intricate interplay between the nodes and features during training of a GNN. What you evaluate is how close to the original behaviour the GNN is when you remove certain nodes and features. But I would question whether this is a proper definition of faithfulness. \n\nMy suggestion would be to also run experiments where you retrain GNNs and check whether the behaviour is indeed such that removing the nodes and features your method deems unimportant leads to a minor change in behaviour. \n\nThe synthetic experiments of the GNNExplainer paper are not included. But it makes sense to me to define synthetic graph classes where the presence of certain features/nodes is known to cause the node label by construction. This way one can check whether those features are the ones identified by the XAI method. I would encourage the authors to also run these experiments and compare to the results from the GNN explainer. \n\nFinally, it is not entirely fair to compare other methods to yours through the notion of fidelity alone. Your method is defined to optimize for it. As I mentioned above, fidelity is one way to measure the quality of a reduced graph but not the only one. It is by no means the only one to measure “faithfulness,” as I have outlined above. For instance, it would also make sense to compare based on the measures introduced in the GNNExplainer paper. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides a simple approach to explaining GNN predictions for each node by greedily selecting nodes or features in each computation graph so as to increase the fidelity score. The fidelity score is based on comparing the original GNN output to what is obtained with noisy versions of the masked nodes/features. While simple, the approach seems somewhat inefficient (efficiency should be assessed/characterized). Also, several improvements to the evaluation expressed in the reviews/discussion (e.g., human evaluation, practical utility, comparison to gradient based methods) would make the submission somewhat stronger. 

Decision: Reject