Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking
Authors: Michael Sejr Schlichtkrull
Nicola De Cao
Ivan Titov
Venue: ICLR 2021 Spotlight (2021)
Keywords: Graph neural networks
interpretability
sparse stochastic gates
semantic role labeling
question answering

Abstract: Graph neural networks (GNNs) have become a popular approach to integrating structural inductive biases into NLP models. However, there has been little work on interpreting them, and specifically on understanding which parts of the graphs (e.g. syntactic trees or co-reference structures) contribute to a prediction. In this work, we introduce a post-hoc method for interpreting the predictions of GNNs which identifies unnecessary edges. Given a trained GNN model, we learn a simple classifier that, for every edge in every layer, predicts if that edge can be dropped. We demonstrate that such a classifier can be trained in a fully differentiable fashion, employing stochastic gates and encouraging sparsity through the expected $L_0$ norm. We use our technique as an attribution method to analyze GNN models for two tasks -- question answering and semantic role labeling -- providing insights into the information flow in these models. We show that we can drop a large proportion of edges without deteriorating the performance of the model, while we can analyse the remaining edges for interpreting model predictions.

Published as a conference paper at ICLR 2021
INTERPRETING GRAPH NEURAL NETWORKS FOR NLP WITH DIFFERENTIABLE EDGE MASKING
Michael Sejr Schlichtkrull 1,, Nicola De Cao 12, Ivan Titov' 1.2
University of Amsterdam, UUniversity of Edinburgh m. S schhichtkrul11 Suwaaaallllalaaae nl, www.deeaaa.va..cmm nl, ititoveinf.ed uk
ABSTRACT
Graph neural networks (GNNs) have become popular approach to integrating structural inductive biases into NLP models. However, there has been little work interpreting them, and specifically understanding which parts of the graphs (e.g. syntactic trees or co-reference structures) contribute to a prediction. In this work, introduce post-hoc method for interpreting the predictions of GNNs which identifies unnecessary edges. Given a trained GNN model, we learn a simple classifier that, for every edge in every layer, predicts if that edge be dropped. We demonstrate that such a classifier can be trained a fully differ- entiable fashion, employing stochastic gates and encouraging sparsity through the expected Lo norm. We use our technique as an attribution method to analyse GNN models for two tasks question answering and semantic role labelling provid- ing insights into the information flow in these models. We show that we can drop large proportion of edges without deteriorating the performance of the model, while we can analyse the remaining edges for interpreting model predictions.
INTRODUCTION
Graph Neural Networks (GNNs) have in recent years been shown to provide scalable and highly performant means of incorporating linguistic information and other structural biases into NLP mod- els. They have been applied to various kinds of representations (c.g., syntactic and semantic graphs, co-reference structures, knowledge bases linked to text, database schemas) and shown effective on a range of tasks, including relation extraction (Zhang et al., [0188] /Zhu et al. 2019: Sun et al.) 2019a Guo et al. 2019). question answering (Sorokin & Gurevych| 2018]SSun [Sun et al. [0188 De Cao et al. 2019), syntactic and semantic parsing tasks (Marcheggiani & Titoy] 2017 Bogin al.) 2019 et al. 2019), summarisation (Fernandes et al. 2019), machine translation (Bastings et al. 2017) and abusive language detection social networks (Mishra et al. 2019).
While GNNs often yield strong performance, such models are complex, and it can be difficult to understand the 'reasoning' behind their predictions. For NLP practitioners, is highly desirable to know which linguistic information given model encodes and how that encoding happens (Jumelet) H 2018 Giulianelli al., 2018 Goldberg 2019). The difficulty interpreting GNNs represents a barrier to such analysis. Furthermore, this opaqueness decreases user trust, impedes the discovery of harmful biases, and complicates error analysis (Kim 2015 Ribeiro et al. 2016b) Sun et al.] 2019b Holstein al.) 2019). The latter is a particular issue for GNNs, where seemingly small implementation differences can make or break models (Zaheer et al. 2017 Xu et al 2019). this work, focus post-hoc analysis of GNNs. We interested especially in developing method for understanding how the GNN uses the input graph. As such, we seek to identify which edges in the graph the GNN relies on, and at which layer they are used. We formulate some desiderata for an interpretation method, seeking a technique that is:
1. able identify relevant paths in the input graph, as paths of presenting GNN reasoning patterns to users;
of the most natural ways
2. sufficiently tractable to be applicable to modern GNN-based NLP models;
3. as faithful (Jacovi & Goldberg 2020) as possible, providing insights into how the model truly arrives the prediction.

---

Published as a conference paper at ICLR 2021
Original model
Gated model
(8)
(8)
hng
(E)
Figure I: GRAPHMASK uses vertex hidden states and messages at layer & (left) as input to classi- fier g that predicts mask 2(f) We use this to mask the messages of the kth layer and re- co-coputte the forward pass with modified node states (right). The classifier g is trained to mask as many hidden states possible without changing the output of the gated model.
simple way to perform interpretation use erasure search (Li et al. 2016 Feng et al. 2018), an approach wherein attribution happens by searching for maximal subset of features that can be entirely removed without affecting model predictions. The removal guarantees that all information about the discarded features is ignored by the model. This contrasts with approaches which use heuristics to define feature importance, for example attention-based methods (Serrano & Smith pook-propagation techniques (Bach et al. 2013 (Sundararajan al., They do not guarantee that the model ignores low-scoring features, attracting criticism in recent years (Nie al. 2018 Sixt al. 2019 Jain & Wallace 2019). The trust in erasure search is reflected in the literature through other methods motivated as approximations of erasure (Bachrens) al., 2010: Simonyan et al. 2014), or through new attribution techniques evaluated using erasure search as ground truth (Serrano & Smith 2019 Jain & Wallace 2019).
2019
Jain & Wallace (219))
2017
Applied to GNNs, erasure search would involve searching for the largest subgraph which can be completely discarded. Besides faithfulness considerations and conceptual simplicity, discrete attri- butions would also simplify the comparison of relevance between paths; this contrasts with contin- uous attribution to edges, where it is not straightforward to extract and visualise important paths. Furthermore, in contrast to techniques based on artificial gradients (Pope et al.] [019 Xie Lu, 2019 Sccharzzebbrrg al., (2019), erasure search would provide implementation invariance (Sun-) dararajan et al. 2017). ). This important in NLP, as models commonly use highly parametrised decoders top of GNNs (e.g., Koggel.ooell-Keee Kedziorsk et al. (2019))
While arguably satisfying criteria (1) and (3) in our desiderata, erasure search unfortumately fails on tractability. In practical scenarios, it is infeasible, and even approximations, which remove fea- ture at a time ZZintgraf et al. 2017) and underestimate their contribution due to saturation (Shrikumar et al. 2017), remain prohibitively expensive.
Our GRAPHMASK aims at meeting the above desiderata by achieving the same benefits as erasure search scalable manner. That is, our method makes easily interpretable hard choices on whether to retain or discard edges such that discarded edges have no relevance to model predictions, while remaining tractable and model-agnostic (Ribeiro et al. 2016a). GRAPIMMSSK can be understood as a differentiable form of subset erasure, where, instead of finding an optimal subset to erase for every given example, we learn an erasure function which predicts for every edge (u, v) at every layer whether that connection should be retained. Given an example graph G, our method returns for each
layer & subgraph g(()) such that we can faithfully claim that no edges outside ((*) influence the predictions of the model. To enable gradient- optimization for our erasure function, we rely on sparse stochastic gates (Louizos al. 2018 Bastings al., 2019).
In erasure search, optimisation happens individually for each example. This can result in a form of overfitting where even non-superfluous edges are aggressively pruned because a similar prediction could be made using alternative smaller subgraph; we refer to this problem as hindsight bias. Because our interpretation method relies on a parametrised erasure function rather than an individual per-edge choice, we address this issue by amortising parameter learning over a training dataset through a process similar to the readout bottleneck introduced in Schulz et al. (2020). In other words, the decision to drop or keep edge is made based the information available in the network (i.c., representation of the graph nodes) without having access to the final prediction (or to the gold standard). As we demonstrate in Section 4 this strategy avoids hindsight bias.
2

---

Published as a conference paper at ICLR 2021
Contributions Our contributions are follows:
We present a novel interpretation method for GNNs, applicable potentially to any end-to-
end neural model which has GNN as component D
We demonstrate using artificial data the shortcomings of the closest existing method, and show how our method addresses those shortcomings and improves faithfulness.
We use GRAPHMASK to analyse GNN models for two NLP tasks: semantic role label- ing (Marcheggiani & Titov 2017) and multi-hop question answering (De Cao al. 2019)
RELATED WORK
Several recent papers have focused on developing interpretability techniques for GNNs. The closest to ours is GNNExplainer (Ying et al.) 2019). wherein a soft erasure function for edges is learned individually for each example. Unlike our method (and erasure search), GNNExplainer cannot as such guarantee that gated edges do not affect predictions. Furthermore, as we show in our exper- iments (Section 4) separate optimisation for each example results in hindsight bias and compro- mises faithfulness. Pope et al. (2019); Xie & Lu (2019) explore gradient- methods, including gradient heatmaps, Grad-CAM and Excitation Backpropagation. Similarly, [Schwarzenberg et al.) et al. (2020) apply Layerwise Relevance Propaga- tion (Bach et al. 2001)) to the GNN setting. These methods represent an alternative to GRAPIMASKK. but as we have noted their faithfulness is questionable (Nie et al., 2018 Sixt et al. 2 Jain & Wal- lace 2019), and the lack of implementation invariance (Sundararajan et al. al.] 201 is problematic (see Appendix Hj. Furthermore, significant engineering is still required to develop these techniques for certain GNNs, e.g. networks with attention as the aggregation function (Veličković et al.) 2018).
2019); |Baldassarre & Azizpour
Another popular approach is to treat attention or gate scores measure of importance (Serrano & Smith 2019). However, even leaving questionable faithfulness (Jain& & Wallace, (209)) aside, many GNNS use neither gates nor attention. For those that do (Marcheggiani & Titov 20177; Veličkovid ct al. 2018 Neil et al. 2018:] Xie & Grossman 2018), such scores are, as we demonstrate in Sec- tion not necessarily informative, as gates can function to scale rather than filter messages.
Outside of graph-specific methods, one line of research involves decomposing the output into a part attributed to a specific subset of features and a part attributed the remaining features (Shapley 1953 Murdoch et al. 2019 Singh et al., 2019 Jin et al. 20200). For GNNs, the computational cost for realistic use cases (e.g. the thousands of edges per example in Cao et al. (019)) is prohibitive.
LIME (Ribeiro et al.) 2016b) like us relies on a trained erasure model, but interprets local models in place of global models. Local models cannot trivially identify useful paths or long-distance dependent pairs of edges, and as also pointed out in Ying et al. (2019) LIME cannot be easily applied for large general graphs. Similarly, it is unclear how to apply integrated gradients (Sundararajan ct al. 2017) to retrieve relevant paths, especially for deep GNNs operating in large graphs.
Masking messages in GRAPHMASK can be equivalently thought of as adding a certain type of noise to these messages. Therefore, GRAPIIMASK can be categorised as belonging to the recently introduced class of perturbation- based methods (Guan et al., 2019: Taghanaki et al., 2019 Schulz et al. 2020) which equate feature importance with sensitivity of the prediction to the perturbations of that feature. The closest to our model is Schulz et al.] (002)), wherein the authors like us apply secondary, trained model predict the relevancy of feature in a given layer. Unlike us, this trained model has 'look-ahead" i.c. access to layers above the studied layer, making their model vulnerable to hindsight bias. Their approach uses soft gates on individual hidden state dimension to interpolate between hidden states, Gaussian noise in order to detect important features for CNNs on an image processing task, and makes independent Gaussian assumptions on the features to derive their objective. We adapted their method to GNNs and used it as a baseline in our experiments.
In our very recent work (De Cao et al., 2020) we have introduced a similar differentiable masking approach to post-hoc analysis for transformers. We used sparse stochastic gates and Lo regular- isation to determine which input tokens can be dropped, conditioning on various hidden layers. Concurrently to this paper. Luo et al. (2020) have also developed interpretability technique for GNNs relying on differentiable edge masking. Their approach uses a mutual information objective like GNNExplainer, along with local binary concrete classifiers as in GRAPHMASK.
Source code available at httttsss:////t htttttp:://ggttuuccoo//////eeeee www...c.....ccc..ccctcc hawponshhhhi/Gaaaaaaaaaaa /GraphMaa'
3

---

Published as a conference paper at ICLR 2021
3 METHOD
3.1 GRAPH NEURAL NETWORKS
A Graph Neural Network a layered architecture which takes an input graph 9 = (V,E) (i.c., nodes and edges) to produce a prediction. At every layer k. GNN computes a node representation ha for each node u E V based on representations of nodes from the previous layer. At the bottom layer, vertices are assigned an initial embedding h& e.g. GloVE embeddings, or the hidden states of an LSTM. For layers > O, GNN can be defined through a message function M and an aggregation function A such that for the 1c-th layer:
(2) where Tu.e indicates the relation type between nodes u and and ((v) the set of neighbour nodes of v. Typical implementations of GNNs rely on either mean-, sum- or max- max-pooling for aggregation.
M (n!- ( (k-1) Tu,e) m a,e
(k)
h
( (mmle u e u N(v)))
3.2 GRAPHMASK
Our goal is to detect which edges (u, u) at layer i can be ignored without affecting model predic- tions. We refer to these edges and the corresponding messages mu,e as superfluous. GNNs can be highly sensitive to changes the graph structure. A GNN trained on graphs where all vertices e have degree d(v) >> for some integer n. may become unstable if applied to graph where some vertices have degree d(r) < n.. Hence, dropping edges without affecting predictions can difficult. Nev- ertheless, many edges in that graph may be superfluous for all purposes other than normalization. Therefore, it is not enough to search for edges which can be dropped instead, we search for edges which, through binary choice 20,0
((k)
(0, 1}, can be replaced with a learned baseline b(();
(k) (R) m u.o ua m.. + ((+) (1- 2 uuv
(k)
(3)
Conceptually, the search for a subset that generates the same prediction can be understood as a form of subset erasure (Li et al.) 2016; Feng et al. 2018). Unfortunately, erasure breaks with the principles we proposed in Section Ji two important ways. First, since it involves searching over all the possible candidates that could be dropped, it is not tractable. Second, since the search happens individually for each example, there is a danger of hindsight bias. That is, the search algorithm finds minimal set of features that could produce the given prediction, but which not faithful to how the model originally behaved (as confirmed in our experiments. Section 4 To overcome those issues,
(k) compute 2 through simple function, learned once for every task across data points:
(1) (k) = 9x (h 1 m,,))
(4)
where x denotes the parametens of g, which is implemented as a single-layer neural network (see Appendix A for the architecture).
Instead of selecting gate values 24.0 individually for each prediction, the parameters π are trained on multiple datapoints, and used explain predictions for examples unseen in the training phase. Moreover, each 2(k) is computed relying only on information also available to the original model when computing the corresponding GNN message (i.e. states of nodes at layer k, ha and ( As such, the explainer is not provided with a look-ahead These two aspects, by design, work to prevent hindsight bias. We refer this strategy amortisation. The alternative to amortisation is to choose the parameters æ independently for each gate, without any parameter sharing across gates. In that case, optimisation would be performed directly on the analysed (i.e. test) examples. We refer to this strategy as the non-amortized version of Graph F] We will show in Section [ that this version of GRAPHMASK, unlike the amortized approach, is susceptible hindsight bias.
"The readout function in Schulz et al. (2020) violates this constraint.
It would be wasteful to use neural network g- (
(k) (k)) in the non- amortizr case and train it on
single example. Instead, we directly optimize the parameters of our stochastic relaxation, Hard Concrete, discussed in 3.3
4

---

Published as a conference paper at ICLR 2021
L.D
0.0
0.85
0.52
0.36
0.28
0.0
0.O
0.49
0,28
-0007-
(a) Erasure search
(b) Integrated Gradients
(c) Information Bottleneck
0.0
0.0
0.0
0.0
0.0
0.0
0.0
0.
0.0
0.0
1.0
1.0
(d) GNNExplainer
(e) Ours (non-amortized)
(f) Ours (amortized)
Figure 2: Toy example: model predicts whether there more black edges (-+ than blue edges. (-+). Erasure search, GNNExplainer, and non-amortized GRAPHMASK overfit by retaining only single black edge (top left). Integrated gradients and the information bottleneck approach give unsatisfying results as all edges have attribution. Only amortized GRAPIMASK correctly assigns attribution and only to black and blue edges.
After g is trained, to analyse data point with GRAPHMASK, we first execute the original model over that data point to obtain h.. Ao and mu.0. We then compute gates for every edge at every layer, and execute a sparsified version the model shown in Figure ! For the first layer, the messages For subsequent layers, we aggregate the masked messages using Equation 2 to obtain vertex embeddings k,( which we then use obtain the next set of masked messages. Note that the only learned parameters of GRAPHMASK are the parameters и of the erasure function and the learned baseline vectors b((2, ,8(*) - the parameters of the original model kept constant. As long as the prediction relying the sparsified graph is the same as when using the original one, we can interpret masked messages as superfluous.
of the original model are gated according to Equation
3.3 PARAMETER ESTIMATION
Given GNN of L layers, graph G, and input embeddings X' (e.g., initial node vectors additional inputs), our task is identify set Gs ( ,..., GG()) of informative sub-graphs such that g( C G Vk L. We search for graph with the minimal number of edges while maintaining f(Gs, X) xe f(G,X) (x)///ww We can cast this, quite naturally, in the language of constrained optimization and employ method that enables gradient descent such as Lagrangian relaxation. In general, however, it is not possible guarantee equality between f(g X) and fGs, X') since is a smooth function, and as therefore a minimal change in its input cannot produce the exact same output. As such, we introduce a divergence D+[ XG) X)] measure how much the two outputs differ, and ii) tolerance level | R>0 within which differences are regarded as acceptable. The choice of D. depends on the structure of the output of the original model. practical way to minimize the number of non-zeros predicted by is minimizing the To 'norm' (i.e., the total number of edges that are not masked). Hence, formally, we deñiee our objective over dataset D as
max min X b
Σ
[R (2(4 + +X(D,(F(0
B)
(5)
G.VDD
1=1 (u,))E
With f(Gs. X¹) we denote forward pass where for each layer the graph may vary, where for X() the graph the layers.
5

---

Published as a conference paper at ICLR 2021
Method
Prec.
Recall
F1
Edge Type
k
k
Erasure search*
100.0
16.7
28.6
Integrated Gradients
88.3
93.5
90.8
MATCH (8.1%)
9.4%
11.1%
8.9%
Information Bottleneck
55.3
51.5
52.6
DOC-BASER (13.2%6)
5.9%
17.7%
10.7%
GNNExplainer
100.0
16.8
28.7
COREF (4.25)
4.4%
0%
0%
Ours (non- amortized)
96.7
26.2
41.2
COMPLEMENT (73.55))
31.9%
0%
0%
Ours (amortized)
98.8
100.0
99.4
Total (100%)
51.6%
28.8%
19.6%
Table 1: Comparison using the faithfulness gold
Table 2: Retained edges for De Cao et al. (2019)
standard on the toy task. *as in Li et al. (2016).
question answering GNN by layer (l)) and type.
where 1 is the indicator function and X E R20 denotes the Lagrange multiplier.
Unfortunately, our objective is not differentiable. We cannot use gradient- based optimization since i) Lo is discontinuous and has zero derivatives almost everywhere, and ii) outputting a binary value needs a discontinuous activation, e.g. the step function. A solution is to address the objective in expectation and employ either score function estimation i.e. REINFORCE (Williams) 1992). biased straighttthrough estimators (Maddison et al. 2017 Jang et al. (017). or sparse relaxation (Louizos) et al. 2018 Bastings et al. 2019). We choose the latter since it exhibits low variance compared to REINFORCE and is an unbiased estimator. We use the Hard Concrete distribution, a mixed discrete- continuous distribution to exact zeroes. At the same time, it also admits continuous outcomes in the unit interval, for which an unbiased and low variance gradient can be computed via the reparameterization trick (Kingma & Welling 2014). We refer to Louizos et al. (2018) for details. Attribution scores correspond to the expectation of sampling non-zero masks, since any non-zero value can leak information. In our experiments, GRAPHMASK converges to a distribution where scores in expectation assume near- binary values.
the closed interval [0, 1]. This distribution assigns non-zero probability
SYNTHETIC EXPERIMENT
We first apply GRAPIMASK in setup where clearly defined ground-truth attribution is known. As opposed to the real-world tasks we address in Sections 5 and 6, this allows for evaluation with respect to faithfulness. The task is defined as follows: a star graph G with single centroid vertex No. leaf vertices v1.-.., Un, and edges (11, (o), (Vn, vo) is given such that every edge (u, v) is assigned one of several colours Cu.e E C. Then, given query (ar, y) whether the number of edges assigned x is greater than the number of edges assigned We generate examples randomly with 6 to 12 leaves, and apply a simple one-layer R-GCN (Schlichtkrull et al.) 2018) (see Appendix D for details). The trained model perfectly classifies every example. We know precisely which edges are useful for a given example- those which match the two colours being counted in that example. The GNN must count all instances of both to compute the maximum, and no other edges should affect the prediction. We define gold standard for faithfulness on this basis: For y, all edges of type x and y should be retained, and all others should be discarded.
x C, the task is to predict
In Table I we compare GR GRAPHMM ARRSHM to four baselines: erasure search (Li et al. 2016). integrated gradients (Sundararajan et 2017), an information bottleneck approach (Schulz et al. 2020), and GNNExplainer (Ying et al. 2019). Neither integrated gradients nor the information bottleneck ap- proach were designed for graphs, and as such we adapt them for this setting (see Appendices Ir and for details). Since GNNExplainer and Information Bottleneck do not make hard predictions, we define for both any gate o, where o; for some threshold as open, and closed otherwise. For integrated gradients we normalize attributions to the interval |-1:1] take the absolute value, and apply a threshold We select E (0.1...., 0.9) to maximize F1 score on validation data.
Only the amortized version of our method approximately replicates the gold standard. In fact, era- sure search, GNNExplainer, and non-amortized GRAPIIMASK recall only a fraction of the non- superfluous edges. Visually inspecting the scores assigned by various methods (Figure 2 we that erasure search, GNNExplainer, and the non-amortized version of our method all exploit their training regime reach the same fow-penalty solution with perfect model performance, but which is not faithful to the original model behaviour, Since the task is to predict whether x > y, the model achieves perfect score with only edge of type x retained. Conversely, for any S y, the model

---

Published as a conference paper at ICLR 2021
Answer rode
Jonny Associates
0.8
V
N
% paths
Japan
2
1996
0.6
0
0.4
5
10
5 10
Phi
Japan
Query nodo
token distance
token distance
Figure 3: Subgraph of retained edges (21% of the original) for the query "abe Phi".
Figure 4: Percentage of paths used in pre-
dictions as a function of the distance between the predicate and the predicted role for the LSTM+GNN model (on the left) and the GNN only model (on the right).
+ is COMPLEMENT, and + is MATCH where edge labels indicate in which layer GRAPHMASK retains such edge.
+ is DOC--OCCBBETE
achieves a perfect score with all edges dropped. Amortization prevents this type of overfitting to the objective. For integrated gradients, inspecting predictions shows that the scalar attribution scores vary greatly across examples with different numbers of edges. Hence, a single t cannot be defined to always distinguish between useful and superfluous edges, even on this simple task.
QUESTION ANSWERING
We now apply GRAPHMASK (amortized) analyze predictions for a real model. Due to the com- plexity, no human gold standard for attribution can be constructed in this setting (Jacovi & Goldberg 2020 We choose the GNNNbased model for multi-hop QA presented in De Cao et al. (2019). eval- uated on WikiHop (Welbl et al. 2018). The task is, given a query sentence and set of context documents, to find the entity within the context which best answers the query. Nodes in the GNN graph correspond to mentions of entities within the query and context, and four types of edges be- tween those are introduced: string match (MATCH), document-leve co-occurrence coreference resolution (COREF), and, finally, the absence of any other edge (COMPLEMENT).
The model consists a two-layer BiLSTM reading the query, and three layers of R- GCN (Schlichtkrull et al., 2018) with shared parameters. Node representations at the bottom layer are obtained by concatenating the query representation to embeddings for the mention question. Here, we focus on their GloVe-based model. Finally, the mention representations are combined into entity representations through max-pooling.
GRAPHMASK replicates the performance of the original model with performance change of -0.4% accuracy. 27% of edges are retained, with the majority occurring in the bottom layer (see Ta- ble D. To ensure that the choice of superfluous edges is not just a consequence of the random seed, i.. to verify the stability of our method, we compute Fleiss' Kappa scores between each individual (k)
measurement of z0,0 across 5 different seeds. We find high agreement with x 0.65. Dropping just a random 25% of these retained edges greatly harms performance (see Appendix J].
For comparison, if do not amortize to provide resilience against hindsight bias, the retained edges are different, with 0.4% of retained edges in the bottom and 91.0% in the top layer. Similarly, GNNExplainer and Integrated Gradients assign the bottom layer, respectively, only 4.3% and 11.3% of their total attribution score. In contrast, dropping the bottom layer on all examples yields much larger accuracy drop (-26%) than any other layer (e.g., -7% for the top one). This suggests that these techniques do not produce faithful attributions. We provide more details in Appendix K
In Table 2 we investigate which edge types are used across the three layers of the model. De Cao et as.ss (219)) ablation test suggested that COREF edges provide marginal benefit to the model: our analysis does not entirely agree. Investigating further, we see that only 2.3% of the retained COREF edges overlap with MATCH edges (compared to 32.4% for the entire dataset). In other words, the system relies on COREF edges only in harder cases not handled by the surface MATCH heuristic. The role COMPLEMENT edges play is interesting well: this class represents the majority of non- superfluous edges in the bottom layer, but always superfluous in subsequent layers. The model relies on initial propagation-stey across these edges, perhaps for an initial pooling of context.
7

---

Published as a conference paper at ICLR 2021
SBJ 185
OPRD in
rebound
in
energy
prices
which
helped
18
expected O
do
the
same
C-A1
predicate
Figure 5: Example analysis on SRL from the GNN+LSTM model (superfluous ares excluded).
De Cao et al. s (2019) model concatenates a representation of the query to every node in the graph before running GNN. As such, one might expect edges connecting mentions of the query entity to the rest of the graph to be superfluous. This, however, not the case at least one such edge is retained in 92.7% of all cases, and in 84.1% of cases in the bottom layer. We hypothesize that the model relies on GNN to see whether other mentions share a surface form or co-occur with mentions of the query entity, and, if not, how they otherwise connect to those. To investigate this, we measure the percentage of retained edges at each layer that occur on paths originating from query entities.
We find that the proportion of edges that occur on paths from mentions of the query increases drastically by layer, from 11.8% at layer O, to 42.7% at layer I, and culminating in 73.8% in the top layer. A mention corresponding to the predicted answer is for 99.7% of examples the target of some retained edge. However, the chance that the predicted entity is connected to the query (72.1%) is near-identical to that of the average candidate entity (69.2%). As such, the GNN is responsible not only for propagating evidence to the predicted answer through the graph, but also for propagating evidence to alternate candidates. The majority of paths take one of two forms - a COMPLEMENT COMPLEMENT edge
edge followed by either a MATCH or DOC-BASED edge (22%), followed by two MATCH or DOC-BASED edges (52%). MATCH and ROC-BASED edges in the bottom layer tend to represent one-hop paths rather than being the first edge longer path.
Relations used by De Cao et al. (2019) are sym- metric (c.g., coreference works in both di- rections). A distinct feature of the subgraphs retained by GRAPHMASK is that pairs of edge and its inverse are both judged to be either superfluous non-superfluous (individually in each layer). In Figure 3 this can be seen for the DOC-BASED edges in layer 2 between Japan and Johnny & AAssociates. Indeed, 49%, 98% and 79% of retained edges in, respectively, lay- ers 0, 1 and 2 have their inverses also retained. In other words, 'undirected" message exchange between mentions, resulting in enriched men- tion representations, appears crucial.
Retained edges
Type
Length
GNN-only
LSTM+GNN
1
2
(3705)
0.01
0.99
0.01
0.99
2
0.07
0.74
0.19
0.10
0.90
>> (10004)
0.74
0.22
0.04
0.79
0.21
1
0.02
0.98
0.01
0.99
2 (2006)
0.30
0.25
0.45
0.89
0.11
(32811
0.56
0.32
0.12
0.73
0.27
Table 3: Percentages of paths with either 0, 1, or 2 edges retained, split by path length and predicate type, for the two models. For the LSTM+GNN model, at most one edge can be included per path as only single GNN layer is employed.
SEMANTIC ROLE LABELING
We now turn to the GNN-based SRL system of Marcheggiani & Titov (2017). The task here is to identify arguments of given predicate and assign them to semantic roles; the labels below the sentence in Figure Their GNN relies on automatically predicted syntactic dependency trees, allowing for information flow in both directions between syntactic dependents and their heads. We investigate both their best-performing model, which includes a BiLSTM and one layer of a GNN, and their GNN-only [ For LSTM+GNN, the masked model has a minuscule performance change of -0.62% F, and retains only 4% of messages. The GNN-only model has a similarly small performance change of -0.99% F, and retains 16% of messages. We again compute Fleiss' Kappa scores between AAAK with 5 different seeds, finding substantial agreement of respectively k 0.79 and k 0.74 for the full and GNN-only models.
In Marcheggiani & Titov 2017). the hest GNN-only model used three layers of GNN; with our reimple- mentation, two-layer GNN performed better. Our reimplementation performed on par with the original.
8

---

Published as a conference paper at ICLR 2021
The GNN, in this case, employs scalar, sigmoidal gates on every message. A naive method for inter- pretability could be to inspect their values. However, gates do not necessarily reflect the importance of individual messages; rather, they may provide scaling as a component in the model. On develop- ment data, the mean gate takes the value 0.16, with a standard deviation of 0.07. We evaluate the model with every message where the corresponding gate value is more than one a below the mean dropped, and find that performance decreases by 16.1% F1 score even though only 42% of edges are removed. Thus, we see that these gates act as scaling rather than reflecting the contribution of each edge to the prediction (see also Appendix D for soft gate values for the example in Figure (5). This matches the intuition from Jain & Wallace 2019) that gates do not necessarily indicate attribution.
We first investigate which dependency types the GNN relies on. We summarise our finding in Fig- ure [8] in Appendix [ The behaviour differs strongly for nominal and verbal predicates NMOD dominates for nominals, whereas SBJ and OBJ play the largest roles for verbal predicates. This is unsurprising, because these edges often directly connect the predicate to the predicted roles. Even where this is not the case see rebound in the example in Figure 5 these edges connect predic- tions to tokens close to the predicate, easily reachable via the LSTM. Interestingly, several frequent relations (occurring in > 10% of examples) ORD, CV, CONJ, HYPH, SUFFIX, and POSTHON. For the LSTM-GNN model, we find that 88% of retained edges point to predicted roles (e.g. rebound), and the remaining 12% mostly point to arguments of other predicates in the same sentence (e.g. which) 6
entirely superfluous these include P, NAME, CO-
Marcheggiani & Titov|s is (2017) original findings suggest that the GNN is especially useful for pre- dicting roles far removed from the predicate, where the LSTM struggles to propagate information. This could be accomplished by using paths in the graph; either relying on the entire path, or par- tially relying on the last several edges in the path. We plot in Figure I the percentage of paths from predicate to a predicted argument, such that a subpath (i.e. at least one edge) ending in the predicted argument was retained. For the LSTM+GNN model, we find that the reliance on paths decreases as the distance to the predicate increases, but only for nominal predicates. For the GNN-only model, we see the opposite: reliance on paths increases as the distance to the predicate increases. We inves- tigate in Table 3 the proportion of edges retained on paths of varying length between the predicate and predicted roles. Practically all direct connections between the predicate and the roles are kept this is unsurprising, as those edges are the most immediate indication of their syntactic relation- ships. Longer paths often useful in both models, although a lower rate for nominal predicates in the LSTM+GNN model. Our findings are consistent with the literature, where dependency paths connecting predicate and argument represent strong features for SRL (Johansson & Nugues 2008 Roth & Lapata 2016).
CONCLUSION
We introduced GRAPHMASK, a post-hoe interpretation method applicable to any GNN model. By learning end-to-end differentiable hard gates for every message and amortising over the training data, GRAPHMASK is faithful to the studied model, scalable to modern GNN models, and capable of identifying both how edges and paths influence predictions. We applied our method to analyse the predictions of two NLP models from the literature - an SRL model, and a QA model. GRAPH- MASK uncovers which edge types these models rely on, and how they employ paths when making predictions. While these findings may be interesting per se, they also illustrate the types of anal- ysis enabled by GRAPHMASK. Here we have focused on applications to NLP, where there is strong demand for interpretability techniques applicable to graph-based models injecting linguistic and structural priors- we leave the application of our method to other domains for future work.
7.1 ACKNOWLEDGEMEN
The authors want to thank Benedek Rozemberezki, Elena Voita, Wilker Aziz, and Dieuwke Hupkes for helpful discussions. This project is supported by the Dutch Organization for Scientific Research (NWO) VIDI 639.022.518, SAP Innovation Center Network, and ERC Starting Grant BroadSem (678254).
'Note though that the GNN model of Marcheggiani & Titov (007)) 'knows' which predicate it needs to focus on, as its position marked in the STL input.

---

Published as a conference paper at ICLR 2021
REFERENCES
Sebastian Bach, Alexander Binder, Grégoire Montavon, Frederick Klauschen, Roburt Müller, and Wojeiech Samek. On pixel-wise explanations for non-linear classifier decisions by layer-wise relevance propagation. PloS one, 10(7)=e01301 30140, 2015.
David Bachrens, Timon Schroeter, Stefan Harmeling, Motoaki Kawanabe, Katja Hansen, and Klaus- Robert Müller. How to explain individual classification decisions. Journal of Machine Learning Research, 11(Jum):1803- 1831, 2010.
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works. arXiv preprint arXiv: 13686, 2019.
Jasmijn Bastings, Ivan Titov, Wilker Aziz, Diego Marcheggiani, and Khalil Sima'a an. Graph convo- lutional encoders for syntax-aware neural machine translation. In Proceedings the 2017 Confer- ence on Empirical Methods in Natural Language Processing, pp. 1957-1967, Copenhagen, Den- mark, September 2017. Association for Computational Linguistics. doi: 10. 10117-200/
BRLLhtts:// www a I web. org/ http://o.w...oor///tttooooooooo.
Jasmijn Bastings, Wilker Aziz, and Ivan Titov. Interpretable neural predictions with differentiable binary variables. In Proceedings of the 57th Annual Meeting of the Association for Compu- tational Linguistics, pp. 2963-2977, Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10. 10.18653/v1//19-111 1284. URL httph:tts////
P1 P19-1284]
Ben Bogin, Jonathan Berant, and Matt Gardner. Representing schema structure with graph neural networks for text-to-SQI. parsing. In Proceedings the 57th Annual Meeting of the Associ- ation for Computational Linguistics, pp. 4560 Florence, Italy, July 2019. Association for Computational Linguistics. doi: 10.18653/11/119-1444 1448. https:::: www. aclweb. org/
anthology/PP9 1448
Nicola De Cao, Wilker Aziz, and Ivan Titov. Question answering by reasoning across doc- uments with graph convolutional networks. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 2306-2317, Minneapolis, Minnesota, June 2019, Association for Computational Linguistics. doi: 10. 10.18653/1//119-1224.. URL https: / www. www.acl.eb..orr/attio...o
Nicola De Cao, Michael Schlichtkrull, Wilker Aziz, and Ivan Titov. How do decisions emerge across layers in neural models? interpretation with differentiable masking. arXiv preprint arXiv:2004. 14992, 2020.
Shi Feng, Eric Wallace, Alvin Grissom II, Mohit lyyer, Pedro Rodriguez, and Jordan Boyd- Graber. Pathologies of neural models make interpretations difficult. Proceedings of the 2018 Conference Empirical Methods in Natural Language Processing, pp. 3719-3728, Brussels, Belgium, Sctober-Novemble 2018. Association for Computational Linguistics. doi: 10.18653/v1/D18-1444 URL (tttttttp::// / www. ac web wrg. htt.bborrggarttholgg////////// 10--111111111 1407
Patrick Fernandes. Miltiadis Allamanis, and Mare Brockschmidt. Structured neural summariza- tion. In International Conference on Learning Representations (ICLR), 2019. URL https:
7/openreview. www.:/ttt/ttodddeeomomoo HerssoRqm
Mario Giulianelli, Jack Harding, Florian Mohnert, Dieuwke Hupkes, and Willem Zuidema. Under the hood: Using diagnostic classifiers investigate and improve how language models track agreement information. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 240-248. Brussels, Belgium, November 2018. Association for Computational Linguistics. doi: 10.18653/v URLhttps::/wwrr
ac web. breb.org/antien www.rrrrg.nnngggggoooooooo
5426
Yoav Goldberg. Assessing bert's syntactic abilities. arXiv preprint arXiv:1901.0m 2019.
Chaoyu Guan, Xiting Wang, Quanshi Zhang, Runjin Chen, Di He, and Xing Xie. Towards deep and unified understanding of deep neural models in nlp. In International Conference on Machine Learning, pp. 2454-2463 2019.
10

---

Published as a conference paper at ICLR 2021
Zhijiang Guo, Yan Zhang, and Wei Lu. Attention guided graph convolutional networks for relation extraction. In Proceedings of the 57th Anmual Meeting of the Association for Computational Linguistics, pp. 241-251, Florence, Italy, July 2019. Association for Computational Linguisties. doi: 10.18653/v1/P19- 1024. URL Stltttts:: www. ac web. haagg//anhoooooo httphholggyp1g9gg- 1-244
Jan Hajie, Massimiliano Ciaramita, Richard Johansson, Daisuke Kawahara, Maria Antônia Martí, Lluís Mårquez, Adam Meyers, Joakim Nivre, Sebastian Padó, Jan Stěpánek, Pavel Strañák, Mihai Surdeanu, Nianwen Xue, and Yi Zhang. The CoNLL-2009 shared task: Syntactic and semantic dependencies in multiple languages. In Proceedings of the Thirteenth Conference on Computa- tional Natural Language Learning (CoNLL 2009); Shared Task, pp. 1-18, Boulder, Colorado, June 2009. Association for Computational Linguisties. URL https: www. ac awwweb.orr org/ anthology/WW09-110
Kenneth Holstein, Jennifer Wortman Vaughan, Hal Daumé III, Miro Dudik, and Hanna Wallach. Improving fairness in machine learning systems: What do industry practitioners need? In Pro- ceedings of the 2019 CHI Conference on Human Factors in Computing Systems, pp. 1-16, 2019.
Alon Jacovi and Yoav Goldberg. Towards Faithfully Interpretable NL. Systems: How should we define and evaluate faithfulness? Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 2020.
Sarthak Jain and Byron C. Wallace. Attention is not Explanation. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pp. 3543-3556, Minneapolis, Minnesota, June 2019, Association for Computational Linguisties,, doi: 10.18653/v1/N1--111 URL https: www. acl web wwtg//nnhoooyy/A1--11333
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with Gumbel-Softmax. International Conference on Learning Representations., 2017.
Tao Ji, Yuanbin Wu, and Man Lan. Graph- based dependency parsing with graph neural networks. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguisties, pp. 2475-2485, 2019.
Xisen Jin, Junyi Du, Zhongyu Wei, Xiangyang Xue, and Xiang Ren. Towards Hierarchical Impor- tance Attribution: Explaining Compositional Semantics for Neural Sequence Models. Interna- fional Conference on Learning Representations, 2020.
Richard Johansson and Pierre Nugues. Dependency- semantic role labeling of propbank. In Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing, pp. 69-78, 2008
Jaap Jumelet and Dieuwke Hupkes. Do language models understand anything? on the ability of LSTMs to understand negative polarity items. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 222-231, Brussels, Bel- gium, November 2018. Association for Computational Linguistics. doi: 10. 11663///1/W1---1
URL httph::t//////t
acl acl wtt. wwtp:///nnnooooyyl/----------
Been Kim. Interactive and interpretable machine learning models for human machine collabora- fion. PhD thesis, Massachusetts Institute of Technology, 2015.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. International Conference on Learning Representations, 2015.
Diederik P Kingma and Max Welling, Auto-encoding variational bayes. Proceedings of the 2nd International Conference on Learning Representations (ICLR), 2014.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. International Conference Learning Representations (ICLR), 2017.

---

Published as a conference paper at ICLR 2021
Rik
Dhanush Bekal, Yi Luan, Mirella Lapata, and Hannaneh Hajishirzi. Text Generation from Knowledge Graphs with Graph Transformers. In Proceedings of the 2019 Con- ference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume (Long and Short Pupers), pp. 2284-2293, Minneapolis, Min- nesota, June 2019. Association for Computational Linguistics. doi: 10.18653/v1/N19- 1238. URL
https: www wwwwwb.wwwbb... orgg http://www.....or/aaaaaoooooo/ga
1238
Jiwei Li, Will Monroe, and Dan Jurafsky. Understanding neural networks through representation erasure. arXiv preprint arXiv: /61iv.1/1..0 261..02220 2016.
Christos Louizos, Max Welling, and Diederik P. Kingma. Learning sparse neural networks through 4y regularization. In International Conference Learning Representations, 2018. http:::::
//openreview.nee
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 Pro- cessing Systems, 33, 2020.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous relaxation of discrete random variables. International Conference on Learning Representations (ICLR), 2017.
Diego Marcheggiani and Ivan Titov. Encoding sentences with graph convolutional networks for semantic role labeling. In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pp. 1507-1516, Copenhagen, Denmark, September 2017. Association for Computational Linguistics. URL https::///// http://wwwwww..b...co http://..o.oooaooooooooo/////1//
Pushkar Mishra, Marco Del Tredici, Helen Yannakoudakis, and Ekaterina Shutova. Abusive lan-
guage detection with graph convolutional networks. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies. Volume I (Long and Short Papers), pp. 2145-2150, 2019.
W. James Murdoch, Peter J Liu, and Bin Yu. Beyond word importance: Contextual decomposition to extract interactions from Istms. International Conference on Learning Representations (ICLR), 2019.
Daniel Neil, Joss Briody, Alix Lacoste, Aaron Sim, Paidi Creed, and Amir Saffari. Interpretable graph convolutional neural networks for inference on noisy knowledge graphs. Machine Learning for Health (ML4HI) Workshop at NeurIPS, 2018
Weili Nie, Yang Zhang, and Ankit Patel. A theoretical explanation for perplexing behaviors of backpropagation-basee visualizations. arXiv preprint arXiv: /00.0009,, 2018
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E Martin, and Heiko Hoffmann. Ex- plainability methods for graph convolutional neural networks. In Proceedings of the IEEE Con- ference on Computer Vision and Pattern Recognition, pp. 10772-10781, 2019.
Danilo Jimenez Rezende, Shakir Mohamed, and Daan Wierstra. Stochastic backpropagation and approximate inference in deep generative models. International Conference on Machine Learning (ICML), 2014.
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. Model-agnostic interpretability of ma- chine learning. arXiv preprint
201
Marco Tulio Ribeiro, Sameer Singh, and Carlos Guestrin. whhy should i trust you?" explaining the predictions of any classifier. In Proceedings of the 22nd ACM SIGKDD international conference 2016b.
on knowledge discovery and data mining, pp.
Michael Roth and Mirella Lapata. Neural semantic role labeling with dependency path embed- dings. In Proceedings of the 54th Annual Meeting of the Association for Computational Lin- guistics (Volume 1: Long Papers), pp. 1202, Berlin, Germany, August 2016. Association for Computational Linguistics. doi: 10.18653/v 11P16-111., URL https: /wwww. aclweb.
lorg/ www.anthhoooyyoo1111111 ogy/p16-1113
12

---

Published as a conference paper at ICLR 2021
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In European Semantic Web Conference, pp. 593-5593-770 Springer, 2018.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T Schütt, Klaus-Robert Müller, and Grégoire Montavon. Xai for graphs: Explaining graph neural network predictions by identifying relevant walks. arXiv preprint arXiv:2006.00 03589, 2020.
Karl Schulz, Leon Sixt, Federico Tombari, and Tim Landgraf. Restricting the flow: Information bottlenecks for attribution. In International Conference on Learning Representations, 2020. URL
net Eorum? id- 111--xxwhhrYYB
Robert Schwarzenberg, Mare Hübner, David Harbecke, Christoph Alt, and Leonhard Hennig. Lay- erwise relevance visualization in convolutional text graph classifiers. Proceedings of the Thirteenth Workshop Graph-Based Methods for Natural Language Processing (TexGraphss- 13). pp. 58-62, Hong Kong, November 2019, Association for Computational Linguistics. doi: 5308
10.18653/v 1/D
BtLhttpss:///
acwweb. org/ wwegg//thhloogyyygog
Sofia Serrano and Noah A. Smith. Is attention interpretable? In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp. 2931 2931-2951, Florence, Italy, July 2019. Association for Computational Linguisties. doi: 10. 186518////v1/ 1282. URL https:
7 acwwbb. org/ wnthhoooyoooo----oooo1 1282
Lloyd S Shapley. value for n-person games. Contributions to the Theory of Games, 2(28):307- 317, 1953.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In Proceedings of the 34th International Conference on Ma- chine Learning-Volee 70, pp. 3145-3153. JMLR. org, 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Visualising image classification models and saliency maps. Workshop at International Conference on Learning Representations, 2014.
Chandan Singh, W James Murdoch, and Bin Yu. Hierarchical interpretations for neural network predictions. International Conference on Learning Representations (ICLR), 2019.
Leon Sixt, Maximilian Granz, and Tim Landgraf. When explanations lie: Why modified bp attribu- tion fails. arXiv preprini arXiv: 19120999,, 2019.
Daniil Sorokin and Iryna Gurevych. Modeling semantics with gated graph neural networks for knowledge base question answering. In Proceedings of the 27th International Conference Computational Linguistics, pp. 3306-3317, 2018.
Pascal Sturmfels, Scott Lundberg, and Su-In Lec. Visualizing the impact of feature attribution baselines. Distill, 5(1):e22, 2020.
Changzhi Sun, Yeyun Gong, Yuanbin Wu, Ming Gong, Daxin Jiang, Man Lan, Shiliang Sun, and Nan Duan. Joint type inference on entities and relations via graph convolutional networks. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pp- 1361-1370, Florence, Italy, July 2019a. Association for Computational Linguistics. doi: 10. 18653/v 1/P19-1131)
htRhhttps: www. http::/wwwwwwwww..boooo wwwp:oogggganaoe http://b.cc./.aacooooool/-------
Haitian Sun, Bhuwan Dhingra, Manzil Zaheer, Kathryn Mazaitis, Ruslan Salakhutdinov, and William Cohen. Open domain question answering using early fusion of knowledge bases and text. In Proceedings of the 2018 Conference Empirical Methods in Natural Language Pro- cessing, pp. 4231-4242 2018.
Tony Sun, Andrew Gaut, Shirlyn Tang, Yuxin Huang, Mai ElSherief, Jieyu Zhao, Diba Mirza, Eliz- abeth Belding, Kai-Wei Chang, and William Yang Wang. Mitigating gender bias in natural lan- guage processing: Literature review. In Proceedings of the 57th Annual Meeting of the Associa- fion for Computational Linguistics. pp. 1630-1640, Florence, Italy, July 2019b. Association for Computational Linguistics. doi: 10. 10.18653/v1/P19. 1159. htthttps: www. aclweb. org/ mnthologyy/P99-139
13

---

Published as a conference paper at ICLR 2021
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 3319- 3328. JMLR. org, 2017.
Saeid Asgari Taghanaki, Mohammad Havaei, Tess Berthier, Francis Dutil, Lisa Di Jorio, Ghassan Hamarneh, and Yoshua Bengio. Infomask: Masked variational latent representation to localize chest disease. In International Conference on Medical Image Computing and Computer-Assisted Intervention, pp. 739-747. Springer, 2019.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop: Divide the gradient by running average of its recent magnitude. COURSERA: Neural networks for machine learning, 4(2):66- 31, 2012.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. International Conference on Learning Representations, accepted as poster.
2018.
Johannes Welbl, Pontus Stenetorp, and Sebastian Riedel. Constructing datasets for multi-hop read- ing comprehension across documents. Transactions of the Association for Computational Lin- guistics, 6:287-302, 2018.
Ronald J Williams.
Simple statistical gradient-follownng algorithms for connectionist reinforcement learning. Machine learning, 8(3-4)222--55 1992.
Shangsheng Xie and Mingming Lu. Interpreting and understanding graph convolutional neural network using gradient-based attribution method. arXiv preprint arXiv:1903.03760 2019.
Tian Xie and Jeffrey C Grossman. Crystal graph convolutional neural networks for an accurate and interpretable prediction of material properties. Physical review letters, 120(14): 14:34111),,,,, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? International Conference on Learning Representations (ICLR), 2019.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating explanations for graph neural networks. In Advances in Neural Information Process- ing Systems, pp. 9240-9251, 2019.
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Russ R Salakhutdinov, and Alexander Smola. Deep sets. In Advances in neural information processing systems, pp. 3391- 3401, 2017.
Yuhao Zhang, Peng Qi, and Christopher D. Manning. Graph convolution over pruned dependency trees improves relation extraction. In Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, pp. 2205-2215, Brussels, Belgium, October-November 2018. Association for Computational Linguistics. doi: 10.18653/11/D18. 1244. URL http:s/p::///ee
wolweb..c. wot.oogg/aaaaooo antho ogy DD18 1244
Hao Zhu, Yankai Lin, Zhiyuan Liu, Jie Fu, Tat-Seng Chua, and Maosong Sun. Graph neural net-
works with generated parameters for relation extraction. In Proceedings the ing of the Association for Computational Linguistics, pp. 1331-1339, 2019.
the 57th Annual Meet-
Luisa M Zintgraf, Taco S. Cohen, Tameem Adel, and Max Welling. Visualizing deep neural network decisions: Prediction difference analysis. International Conference on Learning Representations (ICLR), 2017.
14

---

Published as a conference paper at ICLR 2021
A ERASURE FUNCTION ARCHITECTURE
We compute the parameters स for the function erasure function In defined in Equation 6 through
simple multilayer perceptron. We first derive representation (k) of edge at layer lc simply through concatenation:
Ju.e
(k)
[ (k) (R)) m....
(6)
We then compute the scalar location parameters Tu.o for the hard concrete distribution based on (R). qu.
Tu. W (t ReL (R) (
where LN represents Layer Normalization.
In addition to the formulation of GNN which we define in Equations 1 and tions employ a faster- - but less expressive - formulation, where aggregation is done through matrix multiplication between the vertex embeddings matrix (7)) and a (normalized, relation-specific) adjacency matrix A, (Kipf & Welling 2017 Schlichtkrull et al. 2018 De Cao et al. 2019
some implementa-
H (k) (t-10--1
(8)
Applying the computation of ga.0 from Equation 6 within that scheme would be prohibitively ex- (k)
pensive, as qu,e would need to be computed for every possible combination of and rather than just those actually connected by edges. The complexity would as such rise to O(V2) rather than O(V+ + F), which for large graphs can be problematic. To apply our method in such cases, also develop a faster alternative computation of yuu, based on a bilinear product. this case rather than enumerating all possible messages, rely purely the source and target vertex embeddings h and l² Taking inspiration from R-GCN (Schlichtkrull et al. 2018), we compute an alternative matrix-form (*) as:
3 (R) ( (1) (e H())))
where (((h) unique to the relation r. We sample relation-specific matrix-form gates 2,4,, and apply these using an alternate but equivalent version of Equation 3 to derive representation matrix (k) for the vertices in the masked model:
E(2,00 A,) (w() + ((J - A,)
(10)
where J/ represents the all-one matrix. In our experiments, we rely on the adjacency-list formulation for SRI in Section 6 and the adjacency-matre formulation for QA Section
B THE HARD CONCRETE DISTRIBUTION
The Hard Conerete distribution assigns density to continuous outcomes in the open interval (0, 1) and non-zero mass to exactly 0 and exactly 1. A particularly appealing property of this distribution that sampling can be done via a differentiable reparameterization (Rezende et al.) 2014 Kingma & Welling 2014). In this way, the Lo loss in Equation becomes an expectation:
Σ [R (2.0)
Pa P.
* o]
(11)
(M,D)EE
A=1
(u,e)EE
for which the gradient can be estimated via Monte Carlo sampling without the need for REINFORCE and without introducing biases.
The distribution bution obtained applying an affine transformation to the Binary Concrete distribution Maadiisnn et al. 2017 Jang et al. 2017) and rectifying its samples in the interval [0, 1] (see 6) A Binary Concrete is defined over the open interval (0, 1) (pe in Figure [a) and it is parameterised by loca- tion parameter 7 E R and temperature parameter E R The location acts logit and controls
A stretched and rectified Binary Concrete (also known as Hard Concrete) distri-
15

---

Published as a conference paper at ICLR 2021
Prly D0y
Pcly
0.8
0.6
-02
0.0
02
344
0.6
0.8
1.0
1.2
0.0
12 -02
0.0
022
0.4
0.6
D8
1.5
(a)
(b)
Figure 6: Binary Concrete distributions: (a) a Concrete pe and its stretched version psc; (b) a rectified and stretched (Hard) Concrete PHC-
the probability mass skewing the distribution towards 0 in case of negative location and towards in case of positive location. The temperature parameter controls the concentration of the distribution. The Binary Concrete is then stretched with affine transformation extending its support (I, with S 0 and r 2 1 (psc in Figure 6ap. Finally, we obtain a Hard Concrete distribution rectifying samples in the interval [0, 1]. This corresponds collapsing the probability mass over the interval (1, 0J to O, and the mass over the interval [1, r) to (pис in Figure 6b). This induces a distribution over the close interval [0, 1] with non-zero mass at 0 and 1. Samples are obtained according
((log u - log(1 u) + +7) /T) min (1, max (0, ( r) + r))
(12)
where ar is the Sigmoid function (xx) (1+ and u 4(0, 1). We point to the Appendix B of Louizos et al. (2018) for more information about the density of the resulting distribution and its cumulative density function.
In our experiments, we found a constant temperature = 1/3 to work well. Message specific location parameters 7u.0 are computed as specified in the previous section. We found practical to shift the initial location using bias = 2, e.g. rather than directly using Tw in Equation 12 (k)
(k)
we substitute Yu.v + c. This places the model an initial state where gates are open, which essential for learning.
C TRAINING DETAILS
When training GRAPHMASK, we found it helpful to employ a regime wherein gates are progres- sively added layers, starting from the top. For a model with K layers, we begin by adding gates only for layer k, and train the parameters for these gates for iterations. We then add gates for the next layer k 1, train sets of gates for another 5 iterations, and continue downwards this manner. Optimising for sparsity under the performance constraint using the development set, we found the method to perform best with 8 for SRL, while the optimal setting for QA was
We found it necessary to use separate optimizers and learning for the Lagrangian À parameter and for the parameters of GRAPHMASK. Thus, we employ Adam (Kingma Ba 2015) with initial learning rate 1e 4 for GRAPHMASK, and RMSProp (Tieleman & Hinton 2012) with learning rate le for A. For the tolerance parameter B, we found 3 = 0.03 to perform well for all tasks.
We carried out all experiments which it analyses, training- and run-time depends on the complexity of that model. At training time, GRAPHMASK requires single forward pass to compute gate values, followed by a backward pass through the sparsified model. Thus, every iteration requires at most twice the computation time of equivalent iteration using the investigated model.
single Titan X-GPU. As GRAPIMASKK executes the model
16

---

Published as a conference paper at ICLR 2021
D DATASETS
SRL We used English CoNLL-2009 shared task dataset (Hajič et al. 2009). This dataset contains 179.014 training predicates, 6390 validation predicates, and 10498 test predicates. The dataset can be accessed at at/tttps:///fff wwf..uni........c.mmm...mmmm.m.. wwwp//oonn00o---010
QA For question answering, we used the WikiHop dataset (Welbl et al. 2018), and the prepro- cessing script from De Cao al. (2019). See Table for details. The dataset be accessed at cs ucl ac.ukk/
Min
Max
Avg.
Med.
# candidates
2
9
19.8
14
documents
3
63
13.7
11
# tokens/doc.
4
2,046
100.4
91
Table 4: WIKIHOP dataset statistics from Welbl et al.
2018): number candidates and documents
per sample and document length. Table taken from De Cao al. (2019).
E SYNTHETIC TASK MODEL
For the synthetic task discussed in Section employ model consisting of one-layer R- GCN (Schlichtkrull et al., 2018). Vertex embeddings are initialized with the concatenation a one-hot-encoding of x and one-hot-encoding of y. These are fed into initial MLP with one hidden layer to construct zeroth-layer vertex embeddings (.))) For every leaf, messages are then computed as:
(1) ReLU(W Co,, (0 be...) m,,0
(13)
Aggregation of messages is implemented as sum-pooling, and predictions are made from an MLP with one hidden layer computed from the embedding Wog of the centroid. We use dimensionality of 50 for R-GCN states, and dimensionality of 100 for the MLP hidden states. The model is trained with Adam (Kingma & Ba 2015), with initial learning rate of 1e-
F INTEGRATED GRADIENTS FOR GRAPHS
To apply integrated gradients assign attributions edges, we take the simplistic approach of defining a scalar variable sk "u, by which the message from to v at layer k is multiplied, and interpolate between st
and ak 0. We then compute the relative attribution of a using 0 as a baseline; that is, we assume that the problem can be modelled as interpolating between edges being "fully present" and "fully absent" through "partially present" states. We note that it is nontrivial to extend this approach to multi-layer GNNs, since "partially present" edges in upper layers affect gradient flow and thus attribution to lower layers during interpolation. For this reason, information that has to travel through many edges - e.g., long-distance paths is systematically underestimated in terms of importance. For the synthetic task where we rely on a single-layer GNN, we do not encounter this problem as no long- min-tiit connections are possible: for real-world problems, this may not be the case (see e.g. our findings for QA in Appendix K). Furthermore, as we have noted in Section 3.2 the zero-vector may not be an appropriate baseline for general GNNs as it changes the degree statistics
the graph. This could harm the performance of integrated gradients (Sturmfels et al. 2020); however, as we have constructed our synthetic task such that the number of leaves and thus the degree of the centroid changes, a GNN which achieves perfect score for this task must be robust with respect to changing degree statistics. To make binary predictions, we normalise attributions to the interval [-1; 1], take the absolute value, and again apply a threshold t {0.1,.., 0.9) determine useful and superfluous edges.
17

---

input to Published as a conference paper at ICLR 2021
G INFORMATION BOTTLENECK FOR GRAPHS
A related attribution technique to ours is the information bottleneck approach proposed by [Scuuzz eet al. al.j (2020). Their technique involves computing individual soft sigmoidal gates Çni for each di- mension 2 of the hidden state h of CNN to attribute importance. Instead of learned baseline, gated vectors are replaced with samples from a Gaussian distribution. The mean and variance for this Gaussian are computed over all examples in the training dataset. To promote sparsity, the KL divergence between the dataset distribution and the distribution obtained by interpolating between that distribution and the observed value through the gate is used regularisation.
In Section El we also include results for an adaptation of [Schulz et al. (2020) to the problem of attributing importance messages in graph neural network. To apply the information bottleneck approach for our setting, we do the following. First, instead of individual gates Emi for each dimen- sion of the message m, we use single gate Em. We use their Readout Bottleneck approach, which can be seen as a parallel to our amortisation strategy. We predict logits for each gate by conditioning on the source and target embeddings, as well as on the message itself, similar to how we compute parameters for GR GRAPHASK (see Appendix AA). This contrasts with the original approach of using 1x1 col-ooovosusions over the depth dimension conditioning on "downstream" messages the GNN could cause hindsight bias. Training is done with the KL-divergence based loss introduced in Schulz et al. (2020). Finally, we compute the mean and variance the Gaussian noise used as a baseline (and for the loss) in their approach using all messages in the same layer over the entire training dataset. We found using the entire training data to collect statistics to work better than collecting statistics individually per example.
H IMPLEMENTATION INVARIANCE FOR GNNS
MLP
GNN
Rebtld 4
Ral.igg)
x
t
MUP
LRP with f
tj = 3/2, = 1/2
ReLUgy
Intiad State
CNN Lagar
viet-ej Reiltte'
ReLUO))
LRP with
x' 1/2
MBP werdon
LRP with g
x" 2/3
LRP with g
2, t!!
Figure 7: Attributions for two functionally equivalent networks. We give graph
GNN (on the left) where x is the edge from the top-right node to the central right node. The GNN update rule is simply aggregation with a sum over the neighbour nodes and no activation function. After one GNN layer we apply a MLP (on the right) which is implemented with for two functionally equivalent networks [(4,, lg) and g(1,, 12) (exactly the same in the counterexample provided in Figure 7 in Sundararajan et al. 2017). Since LRP is not implementation invariant, it will produce two different attributions for the node (i.c., t' and f"), and as a consequence of the propagation rule (Schwarzenberg et al. 2019), the attribution to z will also be affected (i.c., x' and x").
18

---

Published as a conference paper at ICLR 2021
1 SRL DISTRIBUTION OVER EDGE TYPES FOR RETAINED EDGES
NM00 (4))
NMGO (5)
NM00 (-)
NMDO (2)
ADV
ADV
VC (6-)
VC (6)
TMP (-3
TMP (5)
DEP (-3]
DEP (3)
IM (c)
IM [c)
(3)
HM00 (-5
HM00
SUB [c)
SUB
OPRO (4)
OPRD
OPRD [x)]
0PRD
PRO (>)
PAD
TITLE
TITLE
MNR
20
30
40
30
60
70
80
00
70 80
Type of all retained edges
odges of retaiind
Figure 8: Distribution over edge types for retained edges (left) and probability of keeping each edge type (right); in both cases split by nominal (N) and verbal (V) predicates; edge types dependency function including computation directionality: flow from the head, (->) or flow to the head (<-). Excludes edges that occur less than 10 % cases, and edges judged superfluous in more than 99 % cases.
J GRADUALLY DROPPING RETAINED EDGES
Retained edges
Acc.
Retained edges
F1
Retained edges
F1
100% (Orig. model)
59.0
100% (Orig. model)
87.1
100% (Orig, model)
83.8
27% (GRAPHMASK)
58.6
4% (GRAPHMASK)
86.6
16% (GRAPHMASK)
83.1
20.25%
55.2
3%
83.1
12%
74.4
13.5%
52.8
2%
74.3
8%
66.1
6.25%
47.7
1%
68.9
4%
58.9
0%
45.2
0%
63.8
0%
56.5
(a) Question Answering
(b) SRL: LSTM+GNN
(c) SRL: GNN-Only
Table 5: Performance of the three real-world models using the original input graphs, using the subgraphs retained after masking with GRAPHMASK, and using only randomly selected 0/25/50/75/100% the edges retained after masking with GRAPHMASK. Dropping the edges marked superfluous by our technique does not impact performance; dropping the remaining edges, even if only a randomly selected 25% of them, significantly hurts the model.
K BASELINE PERFORMANCE ON QUESTION ANSWERING
Although we cannot directly measure and compare the faithfulness of different techniques on real tasks through human pathologies in the attributions provided by both GNNExplorer and Integrated Gradients. An impor- tant clue the level of attribution assigned by each technique to the individual layers of the GNN. In Figure 9 plot for each layer of the Question Answering model the mean percentage of edges assigned specific attribution levels by each technique.
human-produces produced gold standard (Jacovi & Goldberg 2020). we can identify clear
GNNExplainer and Integrated Gradients both assign low levels of attribution the first two layers, relying primarily on the top layer. However, as we see in Table 6 dropping the bottom layer yields much larger performance decrease (-26%) than dropping the top layer (-7%). This is at odds with the predicted attributions. For GNNExplainer, manual inspection reveals this to be a product of hindsight bias. Very specific configurations of top-layer edges adjacent to the predicted answer
19

---

Published as a conference paper at ICLR 2021
Mcan percentage scored above
15
15
10
10
10
5
0
0.2 0.4
0.6 0.8
0.2 0.4 0.6 0.8
0.2 0.4 0.6 0.8
Autribution level
Attribution level
Attribution level
Layer 0
Layer
(c) Layer
Figure 9: Mean percentage of messages assigned attribution scores above certain level in the QA model of Section [5] separated by layer. We report scores for GNNExplainer Integrated Gradients and GRAPHMASK
(in most cases, retaining only edges where the predicted answer is the target) generates the same predictions as the original model. This mirrors common pathology of erasure search QA for textual data, where the answer span and nothing else is selected as an explanation (Feng et al. 2018
For Integrated Gradients, the low scoring of the bottom layer is result of long-distance information (e.g. information from edges and vertices far from the predicted answer, which must travel through half-open pseudo-gates in the other layers reach the predicted answer) being systematically under- estimated as we discuss in Appendix This prevents meaningful comparisons of attribution scores between layers.
Layers discarded
Accuracy
Model
k = 1
Full model
59.0
GNNExplainer
4.3
11.9
83.8
-laeer
33.1
Integrated Gradients
11.3
33.0
55.7
-layer
41.6
GRAPIMASK
51.6
28.8
19.6
layer
52.0
Table Mean percentage the total attribution score allocated to each layer for the question answering model, according GNNExplainer, Integrated Gra- dients, and GRAPHIMASK.
Table 6: Performance of the question an- swering model with all edges each in- dividual GNN layer dropped.
Another approach is to compare the proportion of the total attribution score that different techniques assign each layer; ideally, this should reflect the importance of that layer. Table we compute the mean percentage of the total score assigned to messages in each layer. As in Figure 9 we see GNNExplainer and Integrated Gradients assign low levels of attribution the bottom layer, at odds with the empirical performance loss from excluding that layer. This again indicates that the baselines are unlikely to faithful.
20

---

Published as a conference paper at ICLR 2021
L
SRL EXAMPLE WITH SOFT GATES
price repport
comsumer
0
samee
10000133 0.1
0.00
C-AI
expested
predicute
price
prosucer
0
0
0187618
up
0
push
helped
rehound
A1
Figure 10: The example analysis from Figure using the analysis heuristic where edges with soft gate values more than one standard deviation below the mean discarded. Directions are combined into one arc.
21


Reviews:
[{"review_id": "nw8J3rgjTdh", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "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": "Summary\nThis paper proposes an interpretation method for graph neural networks (GNNs) by learning parameterized, differentiable edge masks. The proposed method uses a single-layer NN classifier to predict  whether an edge can be dropped. It further uses L0 norm to encourage sparsity and amortizes parameter learning over a training dataset to avoid the hindsight bias. The method is experimented on a toy dataset (to demonstrate its faithfulness) and two real NLP tasks (multi-hop question answering and semantic role labeling). There are some interesting discussions based on the edge pruning results of these 2 tasks.\n\nStrengths\n- The paper proposes a novel interpretation method for GNNs. The method is technically interesting and well-motivated.\n- The discussions for the QA and SRL models are thorough and interesting and provide useful insights. For example, the analysis shows that GNN-only models rely more on the paths for arguments farther away from the predicates, compared to LSTM-GNN models.\n- The paper is well-written overall.\n\nWeaknesses\n- Some technical details are omitted. For example, “amortization” is only briefly mentioned in the last part of the introduction with a citation to Shultz et al., (2020). But this seems an important component of the model (shown in Section 4, Figure 2 and Table 1). It would be helpful to add more explanations/definitions so that the paper is more self-contained.\n- The analysis and discussions for the QA and SRL tasks are very interesting. But they seem to be lacking actionable and generalizable conclusions.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "jTbeMppdA1N", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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 of the paper set out to design a method for explaining the behaviour of graph neural networks. Here the focus is on GNNs used in the context of natural language processing. \n\nThe authors argue that the following three properties of a method are desirable:\n\n(1) The method should identify relevant paths across layers as paths are natural ways to present GNN reasoning patterns;\n(2) Be tractable, that is, allow the computation of paths in an efficient manner;\n(3) Be faithful.\n\nThe authors discuss existing post-hoc XAI approaches and the ways in which they do not meet at least one of the above desiderata.\n\n(A friendly comment here: perhaps it would be better to tone down the language just a little bit. I’m not sure I’m convinced that paths are the most natural way to present GNN reasoning patterns, for instance. They are one possible way. Also, what is and isn’t faithful is still not really rigorously defined in the literature and your definition could be made a bit more specific.)\n\nAt this point, it would also make sense to define/make more explicit what you mean by “edge” and “paths” which you want to remove/retain to explain the behaviour of the GNN. Do you mean edge as in “edge between the input graph’s nodes in the computation graph induced by the GNN for one node”? Or do you mean “edge between neurons in the computation graph …”. Making this more concrete allows the user to follow your claims and reasoning better. \n\nThe proposed method belongs to the class of perturbation-based methods. It is very similar to prior work [1] and the authors should focus a bit more on similarities and differences in comparison to [1]. It seems the major difference is in the gating mechanism which is soft in [1] and in the application domain (image CNNs vs. GNNs). The lack of detailed discussion of [1] is especially problematic in the context of what the authors refer to as amortization. This seems to be crucial and makes a significant difference empirically yet is not discussed beyond a brief mention that this was introduced in [1]. The impression I currently have is that the paper is an application of [1] to GNNs. \n\nOne weakness of the proposed approach compared to prior work on explaining GNNs seems to be that it can only mask edges and not features. Is my understanding correct?\n\nThe experiments are well-designed and executed as far as I can tell. I am a proponent of the synthetic data experiments of the GNNExplainer and was happy to see them. It is interesting how well the integrated gradient method works compared to the GNNExplainer. I also like the NLP applications of GNNs and the corresponding experiments. Here, however, I would have wished to see a comparison again with integrated gradients and GNNExplainer. Is there a reason for not making such a comparison?\n\nOverall I think this is a well-written and executed paper. The main problem is that it is very similar to prior work and doesn’t make enough of an effort to carve out the differences and similarities. The missing discussion of amortization is especially problematic, as it seems to be the decisive factor in the proposed method's performance. \n\n[1] Karl Schulz, Leon Sixt, Federico Tombari, and Tim Landgraf. Restricting the flow: Information bottlenecks for attribution. In International Conference on Learning Representations, 2020.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "inK6Tvu11R1", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Summary\nThis paper presents a new interpreting algorithm for understanding graph neural network (GNN) models for natural language processing (NLP) tasks. The main idea is to remove redundant edges for each layer of GNN after training the model. To find the redundant edges, the authors suggest minimizing the difference between the output of GNN with the original graph and inputs and the output of GNN with sub-graphs that remove some edges. The loss function forms the L0 norm with the Lagrange multiplier. The algorithm also learns baseline edge information that can replace the values of target edges. Experiment with synthetic datasets shows that suggested algorithms can find the important edges for the task rather than others that find only part of the important edges. Experiments on question answering and semantic role labeling with the real dataset, the suggested algorithm shows the percentage of retained edges and evidence that support the usefulness of the GNN algorithm for the task rather than LSTM.\n\nThe main strength of this paper is suggesting a sound and straightforward learning algorithm identify important edges for the task from the trained GNN model. Even the idea is simple; it can make people understand the GNN models better. I like to read the synthetic experiment section since it makes me admit to why the suggested algorithm much better than other algorithms. I also like to see the usefulness of the algorithm for the real NLP dataset.\n\nWhat concerns me most is the lack of explanation about the amortized. The authors mentioned it in the Introduction section with Schulz et al. 2020 paper. But it is hard to imagine the amortized and non-amortized algorithms in the experiment sections. Following the result in Figure 2, amortization is a key factor in identifying the important edges. Could the authors explain it more about this on the suggested algorithm?\n\n\n\nOverall, I admit that the suggested algorithm is a sound method to increase the interpretability of GNN models. But I have some questions that I want to listen to the author’s responses.\n\n\nQuestions\n- How much drop the performance after masking? I know that the goal of masking is interpretability, not performance. But I am curious about it since if there are few drops, then we can identify informative sub-graphs by masking.\n- Can we increase the percentage of masking nodes? Does it govern by the $\\lambda$?\n- Can we use the suggested algorithm for other NLP tasks that use GNN models such as [1, 2, 3]?\n\nTypos\nWe investigate in Tables 3 and 3 on page 8\n\nReference\n[1] https://www.aclweb.org/anthology/P18-1026/\n[2] https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16329\n[3] https://www.aclweb.org/anthology/P18-1149/ ", "extra_scores": {}, "extra_text": {}}, {"review_id": "1xiqsCKqcPV", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "*Summary of the paper*: This paper introduces a post-hoc method -- GraphMask, to interpret the prediction of GNNs. For each edge in the GNNs, the authors introduce a learnable hard gate which indicates whether this edge could be erased or not. The gates can be trained together with the model in a fully differentiable way. By analyzing the GNN models' behavior on two tasks -- question answering and semantic role labeling, the authors find that a large proportion of edges could be dropped without deteriorating the performance of the model. At the same time, the remaining edges could be used for interpreting model predictions.\n\n*Strength of the paper*:  \n1. The idea to erase edges in GNNs is intuitive and straightforward, but how to do it properly is the problem. This paper introduces a simple yet viable method to deal with it. This kind of technique is potentially useful to analyze other models' behavior.\n\n2. The experiments are well designed including both qualitative analysis, quantitative results, and reasonable ablation to show the effectiveness of their method. The thorough analysis conducted by the authors also contains useful insights of the model's behavior which is consistent with the literature.\n\n3. The authors have done a thorough literature review and clearly state where does this paper stands.\n\n*Comments*:\n\n1. I really like the synthetic experiment designed in the paper which distinguishes the explanation proposed in the paper from others to be faithful. However, from my point of view, the task introduced here is too simple to say that such kind of faithfulness could be generalized to the real setting. I am curious if you further drop a small proportion of the remaining edges, how would it affect the performance?\n\n2. Those model-dependent post-hoc explanations are interesting, I am curious how those explanations (remaining edges) would change if you have different encoders like BERT/Roberta. Could we treat it as a way to measure how much structural information is capture by the encoder? Also, other than the post-hoc explanation, do you have any idea of how we can further use such kinds of explanations to build a better/robust/faithful model?\n\n*Reason for score*: Overall, I vote for accepting this paper. I like the idea of differentiable masking and the way the authors use to build faithful explanations for GNNs. The experimental results and analysis provide new insights to this area. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a method for  interpretable  graph neural networks.
The idea is intuitively well motivated: after training the model, discard spurious edges that are not critical to making predictions in the graph, and only retain salient edges.
Experiments on synthetic and real datasets show that the proposed method is effective at dropping only the edges that are not useful for the task at hand;  while leading to  only small performance degradation.  The paper is well-written. Overall, the paper brings together prior ideas in a useful way, and is well-executed.
Decision: Accept (Spotlight)