DEGREE: Decomposition Based Explanation for Graph Neural Networks
Authors: Qizhang Feng
Ninghao Liu
Fan Yang
Ruixiang Tang
Mengnan Du
Xia Hu
Venue: ICLR 2022 Poster (2022)
Keywords: XAI
GNN

Abstract: Graph Neural Networks (GNNs) are gaining extensive attention for their application in graph data. However, the black-box nature of GNNs prevents users from understanding and trusting the models, thus hampering their applicability. Whereas explaining GNNs remains a challenge, most existing methods fall into approximation based and perturbation based approaches with suffer from faithfulness problems and unnatural artifacts respectively. To tackle these problems, we propose DEGREE (Decomposition based Explanation for GRaph nEural nEtworks) to provide a faithful explanation for GNN predictions. By decomposing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. Based on this, we further design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods. The efficiency of our algorithm can be further improved by utilizing GNN characteristics. Finally, we conduct quantitative and qualitative experiments on synthetic and real-world datasets to demonstrate the effectiveness of DEGREE on node classification and graph classification tasks.

Published as a conference paper at ICLR 2022
DEGREE: DECOMPOSITION BASED EXPLANATION FOR GRAPH NEURAL NETWORKS
Qizhang Feng', Ninghao Liu", Fan Yang', Ruixiang Tang', Mengnan Du', Xia Hu
'Department of Computer Science and Engineering. Texas A&M University
2 *Department of Computer Science, University of Georgia
3 Department of Computer Science, Rice University
{ {qf31, dumengnan) amu edu, ninghao. 1et..iiuuue liu@uga.edu (fy19,rt39, xia.huferice.ed
ABSTRACT
Graph Neural Networks (GNNs) are gaining extensive attention for their appli- cation in graph data. However, the black-box nature of GNNs prevents users from understanding and trusting the models, thus hampering their applicabil- ity. Whereas explaining GNNs remains a challenge, most existing methods fall into approximation based and perturbation based approaches with suffer from faithfulness problems and unnatural artifacts, respectively. To tackle these prob- lems, we propose DEGREE (Decomposition based Explanation for GRaph nEural nEtworks) to provide a faithful explanation for GNN predictions. By decompos- ing the information generation and aggregation mechanism of GNNs, DEGREE allows tracking the contributions of specific components of the input graph to the final prediction. Based this, further design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes that are overlooked by previous methods. The efficiency of our algorithm can be further improved by utilizing GNN characteristics. Finally, we conduct quantitative and qualitative experiments on synthetic and real-world datasets to demonstrate the effectiveness of DEGREF on node classification and graph classification tasks.
INTRODUCTION
Graph Neural Networks (GNNs) play an important role modeling data with complex relational information (Zhou et al. 2018), which is crucial in applications such as social networking (Fan et al.) 2019), advertising recommendation (Liu et al. 2019). drug generation (Liu et al., 22200), and agent interaction (Casas et al., 2019). However, GNN suffers from its black-box nature and lacks faithful explanation its predictions.
Recently, several approaches have been proposed to explain GNNs. Some of them leverage gra- dient or surrogate models to approximate the local model around the target instance (Huang et al.) 2020 Baldassarre & Azizpour 2019 Pope et al. 2019). Some other methods borrow the idea from perturbation based explanation (Ying et al. 2019 Luo et al.] 2020 Lucic et al.) (202T), under the assumption that removing the vital information from input would significantly reduce output con- fidence. However, approximation based methods do not guarantee the fidelity of the explanation obtained, Rudin (2019) states that a surrogate that mimics the original model possibly employs distinct features. On the other hand, perturbation based approaches may trigger the adversarial na- ture of deep models. [Caang et al.) (2018) reported this phenomenon where masking some parts of the input image introduces unnatural artifacts. Additionally, additive feature attribution methods (Vu) Thai 2020 Lundberg Leel (017) such as gradient based methods and GNNExplainer only pro- vide single heatmap or subgraph as explanation. The nodes in graph usually semantically individual and we need a fine-grained explanation to the relationships between them. For example, in organic chemistry, the same functional group combined with different structures can exhibit very different properties.
To solve the above problems, we propose DEGREE (Decomposition based Explanation for GRaph nEural nEtworks). which measures the contribution components in the input graph to the GNN prediction. Specifically, first summarize the intuition behind the Context Decomposition (CD)

---

Published as a conference paper at ICLR 2022
algorithm (Murdoch et al. 2018) and propose that the information flow in GNN's message prop- agation mechanism is decomposable. Then we design the decomposition schemes for the most commonly used layers and operations in GNNs, as to isolate the information flow from distinct node groups. Furthermore, we explore the subgraph-level explanation via an aggregation algorithm that utilizes DEGREE and the structural information of the input graph to construct series of sub- graph sets as the explanation. DEGREE guarantees explanation fidelity by directly analyzing GNN feed-forward propagation, instead of relying on input perturbation or the use of alternative models. DEGREE is non-additive and can therefore uncover non-linear relationships between nodes. We quantitatively and qualitatively evaluate the DEGREE on both synthetic and real-world datasets to validate the effectiveness of our method. The contributions of this work are summarized as follows:
We propose a new explanation method (DEGREE) for GNNs, from the perspective of decompo- sition. By elucidating the feed-forward propagation mechanism within GNN, DEGREE allows capturing the contribution of individual components of the input graph to the final prediction. We propose an aggregation algorithm that provides important subgraphs as explanation in order to mine the complex interactions between graph components. We combine the property of the message propagation mechanism to further reduce the computation.
We evaluate DEGREE on both synthetic and real-world datasets. The quantitative experiments show that our method could provide faithful explanations. The qualitative experiments indicate that our method may capture the interaction between graph components.
RELATED WORK
Despite the great success various applications. the black-box nature of deep models has long been criticized. Explainable Artificial Intelligence (XAI) tries to bridge the gap by understanding the internal mechanism of deep models (Du et al.) 2019). Mcanwhile, the need to tackle non-Er -ucllddid data, such as geometric information, social networks, has given rise to the development of GNNs. Similar to the tasks on image or text data, GNNs focus on node classification (Henaff et al. 2015
graph classification (Xu et al., 2018 Zhang et al. 2018), and link prediction (Zhang & Chen 2018
Cai & Jil 2020). Message passing mechanism allows the information to flow from one node to another along edges, and empowers GNNs with convolutional capabilities for graph data.
While the explainability in image and text domains is widely studied (Shrikumar et al. 2017 Sun- dararajan al. 2017 (Simonyan al., 2013), the explainability of GNN is on the rise. First, some recent work adapts the interpretation methods used for traditional CNNs to GNNs (Baldassarre & Azizpour 2019; Pope et al., 2019). They employ gradient values to investigate the contribution of node features to the final prediction. However, these methods ignore the topological informa- tion, which is a crucial property of graph data. Second, some methods trace the model prediction back to the input space in backpropagation manner layer by layer (Schwarzenberg et al. 2019 Schnake et al. 2020). Third, some methods define a perturbation- perturb node, edge, node features and identify the components that affect the prediction most. Specifically. GNNExplainer and PGExplainer (Ying et al. (2019) maximize the mutual information between perturbed input and original input graph to identify the important features. Causal Screen- ing (Wang et al.) (021) searches for the important subgraph by monitoring the mutual information from a cause-effect standpoint. CF-GNNEExpliiner (Lucic et al. (2021) proposes to generate counter- factual explanations by finding the minimal number of edges to be removed such that the prediction changes. In addition, XGNN (Yuan al. 2020) builds model-level explanation for GNNs by generating a prototype graph that can maximize the prediction. Moreover, due to the discrete and topological nature of graph data, XGNN defines graph generation as a reinforcement learning task instead of gradient ascent optimization.
interpretation whereby they
Many previous explanation methods for GNNs suffer from adversarial triggering issues, faithful- ness issues and additive assumptions. To this end, we propose decomposition based explanation for GNNs (DEGREE) to remedy these problems. DEGREE enables to track the contribution of the components from the input graph to the final prediction by decomposing a trained GNN. Thus, DEGREE guarantees the integrity of the input and eliminates the adversarial triggering issue of the perturbation-baut based approach. Since surrogate models used, DEGREE guarantees its faithful- ness. Mcanwhile, by integrating the decomposition to the normal layer, DEGREE does not have any additional training process.
2

---

Published as a conference paper at ICLR 2022
B
A
GCN
GCNs
Irput Graphh
Intermediate Graph
Final Groph
E
(4)
(6)
Node Feature
Target
Group
B
Target Portion
Bockground
Portion
Target Message
Bockground
Message
Figure 1: Illustration of the DEGREE for decomposing GCN. Node features latent embeddings contain targel portion (orange hemisphere) and an background portion (blue hemisphere). (a)-(c) show the workflow of the GCN, exhibiting only the messages aggregation for node A. (d) demon- strates message aggregation after decomposition. (e) demonstrates the decomposed message flow.
3 DEGREE: DECOMPOSITION BASED EXPLANATION FOR GNNS
this section, we introduce the details of the proposed explanation method. First, we introduce the notations and problem definition. Then, we discuss the general idea of decomposition based explanation. Finally, we develop concrete decomposition schemes for different GNNs layers.
3.1 PROBLEM DEFINITION
We first introduce the notations used in this work. Given graph G (V,E), where the set of nodes and & is the set of edges between nodes. The adjacency matrix of G is denoted as A E IR X.N The nodes are associated with features, and the feature matrix is denoted as X IR N where F is the feature dimension.
where N = | the number of nodes, so V {eI, U2..... uN P
In this work, we focus on explaining CNNN-baee classification models. Let f denote the target GNN model. f computes the likelihood of node or graph belonging to the target class, where G RIVl or f G + IR, for node or graph classification respectively.
The goal of explanation is to find the measuring the contribution of all possible subgraphs and find the ones with high contribution scores. However, there are two challenges to be addressed.
important subgraph in G given f()), which requires
(1) Given any subgraph of interest, how to estimate its contribution without breaking the input graph? (2) The number of all subgraphs in G usually very large, so how to choose candidate subgraphs for improving explanation efficiency? We tackle the first challenge in the following part of Sec 3ld solve the second one in Sec
3.2 DECOMPOSITION BASED EXPLANATION
In general, a prediction model f contains multiple layers L,, E {L....,
f(X) LT - .... L Li (X).
(I)
Let X(t) denotes the input to Lt, so X function composition. Here X[1] E NR. is the embedding matrix at 1-th layer, where F, is the latent dimension. The embedding vector of the i-th node 1-th layer is denoted as {1
(x((t)) and X[1] X. The symbol denotes
The core idea of decomposition based explanation is that, given a target node group (or subgraph) of interest, we estimate its contribution score to model prediction merely through feed-forward prop- agation. We call the information propagated from the target group larget portion, and the rest of information called background portion. does not necessarily mean it is important, while it only means score. In the following, we use y and to denote the target and background portion, respectively. Let (0, 1 where m means v belongs the target group and otherwise m; 0.
worth noting that, a node is in the target group interested in its importance
3

---

Published as a conference paper at ICLR 2022
Then, the decomposition is initialized from the layer of node features, where the target portion and
background portion of the input feature matrix are: X = diag( m and X = (I -I--iag((un d (x) respectively. In a neural network, information from different parts of input forward process into latent representations, which poses challenges for explanation. Suppose the target and background portion in [ are known from prior layer, we could explain the model if we can still distinguish the information flows of the two portions inside L. That is, at layer Lt, suppose its input can be decomposed as X [ X for explanation:
merged in the feed-
$ [t]. the following relations need hold
(1,
[( (t) B(X x²
(2)
x=(++]]
[+[++1]
X x[x
X 1),
(3)
where -.s-)) denotes the decomposed version of layer L. I(::.) and B(:,)) corresponds to the contribution of the target and the background portion to layer L, [t 1] and X 1] denotes the target and background portion of X[t + 1] as the imput to the next layer. The decomposition above goes from the input, through all intermediate layers, to the final prediction. If target node group or subgraph is important, then should contributes to most of the prediction, meaning that T(X X (T)) f(X).
3.3
INTUITIONS BEHIND DECOMPOSITION BASED EXPLANATION FOR GNN
The intuition behind decomposition based explanation could be summarized as two rules: (1) the target and background portion a higher layer mainly comes from the target and background portion at the lower layer respectively; (2) ideally there should be little interaction between the target portion and the background portion. Please note that the partition is not dimension-winn wise, meaning that each latent dimension may contain information from both target and background portions.
Figure briefly illustrates the working principle of GNNs: the model computes neural message for each node pair and aggregates message for them from their neighbors. A major step of decomposing GNNs is that: the target and background portion of node are aggregated from the target and background portion of its neighbours, respectively. This can be easily illustrated by the distributive nature of the GNN information aggregation mechanism:
X + AX(( A X
AX
AX
(4)
[=[++1] X=(++11]
Nevertheless, the above equation is only a conceptual illustration. A real GNN model could con- sist of various layers, such as graph convolution layers, fully connected layers, activation layers and pooling layers. Several challenges still need to be tackled to develop an effective explanation method. First, how to design the decomposition scheme for different types of layers? Second, how to efficiently find out the important nodes and subgraphs, by choosing the appropriate tar- get/background group given all possible node combinations?
3.4
DECOMPOSING GNN LAYERS
In this work, consider the decomposition scheme for two commonly used GNN architectures: GCN (Kipf & Welling 2016) and GAT (Veličković et al. 2017).
3.4.1
DECOMPOSING GCNs
The GCN architecture consists of graph convolution, fully connected layers, ReLU and maxpooling.
Graph Convolution Layer: The graph convolution operation pass messages between nodes:
x 1|+1 D - AD AD- X(( +WW++
(5)
where W and denote the trainable weights and bias. Here b is optional. À A denotes the adjacency matrix with self loop. The matrix D., Σ, A is the diagonal degree matrix of Á. The corresponding decomposition can be designed as follows:
4

---

Published as a conference paper at ICLR 2022
7(4 AD
X
AD
x
(6)
3
X + 1| 7|1 + b
[+++
B k
[[t]
+ B
where X it] and x is the target and background portion of [ respectively. The derivation of yit and B[t] is intuitive since graph convolution is linear operation. Motivated by (Singh et al., 2018), 7[t] and B[t] have to compete for their share of b as in Eq
7
|r R measures the
dimension-wist magnitude of [*[{] after the linear mapping (
is defined similarly).
Fully Connected Layer: fully connected layer prevalent in the model is shown below:
X + x b,
(8)
where & and b denote trainable weights and bias. Structure-wise, is very similar the GCN. The decomposition can be designed as:
X [1@
( +
[*++1]= X [t]
[ = x (1
(9)
X
+ +
X
X
X
ReLU Activation: For the activation operator ReLU, we use the telescoping sum decomposition
from Murdoch & Szlam (0017). We update the target term first and then update the background term by subtracting this from total activation:
(t + + 1] ReLU (t). x + = ReLU (x'(++ + xx11)
ReLU (x*
(10)
Maxpooling: We track the node indices selected by pooling in both target and background portion.
3.4.2 DECOMPOSING GATS
The graph attention layer in GAT is similar to Eq. but uses the attention coeflicients ai to aggregate the information (an alternative way to understand Eq. 5 that atj (D AD )s,)):
LeakyReLU (XX a
exp
04
(11)
EREMUUR exp
LeakyReLU
[X,(t)||X a
where || represents the concatenation operation. W and are parameters. X denotes the embed- ding of node i at layer L, NV denotes the neighbors of node i.
Therefore, graph attention layer can be seen as consisting of four smaller layers: linear mapping. concatenation, LeakyReLU activation, and softmax operation. Decomposing a linear mapping is as trivial as decomposing an FC layer. To decompose the concatenation operator:
X, [
[||+||]] X [X]]][]
(12)
For LeakyReLU, the idea of decomposition is the same as ReLU. For softmax operation, we split the coefficients proportionally the exponential value of the target and the background term of input:
exp (x ((l(
X + 1] softmar (Xlt))
exp
[x((t)
X
[t]]
+ exp (xx*(t))
(13)
exp (x*(1))
x + 1] softmar (X(t))
[x) + exp (xx(t))
exp
Here we employ the similar motivation that used to split bias term in Eq. and let [+]] and [t]] to compete for the original value. The detail of decomposing the attention coefficients can be found in Appendix B
5

---

Published as a conference paper at ICLR 2022
4 SUBGRAPH-LEVEL EXPLANATION VIA AGGLOMERATION
Through decomposition, we could compute the contribution score of any given node groups. How- ever, this is not enough for explaining GNNs. Our goal of explanation is to find the most important subgraph structure, but it is usually impossible to exhaustively compute and compare the scores of all possible subgraphs. In this section, we design an agglomeration algorithm to tackle the challenge.
4.1 CONTEXTUAL CONTRIBUTION SCORE
We first introduce contribution scores provided by decomposition. in many scenarios, we are more interested in the relative contribution of the target compared its contexts. Let V> C V be the target node group, and fD(.) (.) be the contribution score calculated from decomposition. The relative contribution y averaged over different contexts is calculated as:
scoring function be used in our algorithm. Different from the absolute
<(V)) e (N -P(TUC)-
(14)
where C is the context around V?, and NL (V7) contains the neighboring nodes of V> within L- hops. Here we use a random walk process RW() () to sample C. within the neighborhood around V The reason for sampling within the neighborhood based on the information aggregation, where node collects the information from its neighbors within certain hops constrained by the GNN depth.
4.2 SUBGRAPHS CONSTRUCTION VIA AGGLOMERATION
Our agglomeration algorithm initializes from individual nodes and terminates when the whole graph structure is included. Specifically, the interpretation process constructs a series of intermediate subgraph sets & {Si, ..., St}. where S {BI,... BM,) contains M4 subgraphs. At each step, the algorithm searches for the candidate node or node group that most significantly affects the contribution of subgraph Bm, m E fl.... M.) according to the ranking score r(u):
s(v) o (f o (B... r(v) A s(v) - E. [s(v']] s.t. v. (B,,),
(15)
where N (Bm) the set of neighbor nodes or node groups Bn. Here s(v) measures the influence of v to Bm, while r(v) further revises the value by considering the relative influence of e compared to other candidates v'. At the beginning q max, r(c'), and we set y 0.6 in experiments. The selected nodes are merged into subgraphs to form S/+1- Small subgraphs will be merged into larger ones, so we have M, S My. 2 j. The algorithm executes the above steps repeatedly and terminates until all nodes included (i.e., M, = 1), or a certain pre-defined step budget is used up. Further details of the algorithm can be found in Section of the Appendix.
our algorithm, B., = A node v is selected r(v) Z
5 EXPERIMENTS
5.1 EXPERIMENTAL DATASETS
Following the setting in previous work (Ying et al. 2019), we adopt both synthetic datasets and real-world datasets. The statistic all datasets are given in Sec A in the Appendix.
5.1.1 SYNTHETIC DATASETS
BA-Shapes. BA-Shapes is unitary graph based on 300-node Barabási-Albert (BA) graph (Barabási & Albert, 1999). 80 five-node motifs are randomly attached to the base graph. The motif is "house" structured network in which the points are divided into top-nodes, middle- nodes, or bottom-nodes. 10% of random edges are attached to perturb the graph.
BA-Community, BA-Community dataset is constructed by combining two BA-Shapes graphs To distinguish the nodes, the distribution of features of nodes in different communities differs. There eight node classes based on the structural roles and community membership.

---

Published as a conference paper at ICLR 2022
Tree-Cycles.
The Tree-Cycles dataset germinates from an eight-level balanced binary tree base graph. The motif is a six- six-node cycle. 80 motif's are randomly added to the nodes of the base graph. The nodes are classified into two classes, i... base-nodes and motif-nodes. Tree-Grids. is constructed in the same way as the Tree-Cycles dataset. The Tree-Grid dataset has the same hase graph while replacing the eycle motif with 3-by-3 grid motif.
5.1.2 REAL-WORLD DATASETS
MUTAG. It is a dataset with 4,337 molecule graphs. Every graph is labeled according to their mutagenic effect the bacterium. As discussed in (Debnath al., 1991), the molecule with chemical group NH2 or NO₂ and carbon rings are known to be mutagenic. Since non-mutagenic molecules have no explicit motifs, only mutagenic ones presented during the analysis.
Graph-8ST2. It is a dataset of 70,042 sentiment graphs, which are converted through Biaffine parser (Liu et al. 2021]. Every graph labeled according its sentiment, either positive or negative. The nodes denote words, and edges denote their relationships. The node features are initialized as the pre-trained BERT word embeddings (Devlin et al. 2019).
5.2
EXPERIMENTAL SETUP
5.2.1
EVALUATION METRICS
The interpretation problem is formalized as binary classification problem distinguishing between important and unimportant structures (nodes or edges, depending on the nature of ground truth). A good explanation should assign high scores to the important structures and low scores to unimportant ones. We consider the nodes within the motif to be important for the synthetic dataset and the rest to be unimportant. In the MUTAG dataset, the "N-H" and "N-O" edges important, and the rest are unimportant. We conduct quantitative experiments on the synthetic datasets and the MUTAG dataset, and qualitative experiments the MUTAG dataset and the Graph-SST2 dataset. We adopt the Area Under Curve (AÚC) to evaluate the performance quantitatively.
5.2.2 BASELINES METHODS AND IMPLEMENTATION DETAILS
Baselines Methods, We compare with four baselines methods: GRAD Ying et al. 2019) GAT (Veličoovc et al. 2017), GNNExplainer (Ying et al., 2019 and PGExxpaaine (Luo et al, 2020). (1) GRAD computes the gradients of GNN output with respect to the adjacency matrix or node features. (2) GAT averages the attention coefficients across all graph attention layers as edge importance. (3) GNNExplainer optimizes a soft mask of edges or node features by maximizing the mutual information. (4) PGExplainer learns an MLP (Multi-layer Perceptron) model to generate the mask using the reparameterization trick (Jang et al.) 2017).
Construction of Target Models. We use all synthetic datasets together with the MUTAG dataset for quantitative evaluation experiments. We train GCN and GAT model as the model to be explained for all datasets following the setup of previous work. Meanwhile, we construct DEGREE(GCN) and DEGREE(GAT) as the decomposed version for our method. We set the number of GNN layers to 3 for all datasets, except for the Tree-Grid dataset where it is 4. Since the 3-hop neighbors of some target nodes has only in-motif nodes (no negative samples). For the qualitative evaluation experiment, we use the MUTAG dataset and Graph-SST2 dataset. For all the model training, we use Adam optimizer. All the datasets are divided into crann/validation/test sets.
Explainer Setting. For all baseline methods, we keep the default hyper- parameters. For basclines (e.g., PGExplainer) who need training additional modules, we also split the data. We also split data for baselines requiring additional training (e.g. PGExplainer). We use all nodes in the motif for evaluation. For explainers that only provide node explanation, we average the score of its vertexes as edge explanation. The details of explainer settings can be found in Sec A in Appendix.
5.3 QUANTITATIVE EVALUATION
In this section, introduce experimental results on both synthetic datasets and the MUTAG dataset. For node classification, the computation graph only contains nodes within (-hop from the target node, where / is the number of model layer. The reason is that the nodes outside the computation

---

Published as a conference paper at ICLR 2022
Table 1: Quantitative Experiment Result.
Explanation AUC
Task
Node Classification
Graph Classificution
Dutasel
BA MA-Shapes
BA-Commuunty
Tree- Tree-Cyee Cycles
Tree-Grid
MUTAG
GRAD
0.882
0.750
0,905
0.612
0.787
GAT
0.815
0.739
0.824
0.667
0.763
GNNExplainer
0.832
0.750
0.862
0.842
0.742
PGEsplainer
0.963
0.894
0.960
0,907
0.836
DEGREEIGEN)
0,991 00.005
0.084=0.005
0.95820.004
0.925:0.040
0.875:50.028
DEGREE(GAT)
0.99010.008
0,012
0,91910.027
0.935.10.031
0.863.10.042
Time Efficiency(s)
GNNExplainer
0.65
0.78
0.69
0.72
0.43
PGExplainer
116.72(0.014)
35.71(0.024)
117.9600.99)
251.37(0.011)
503 503.52(0.012)
DEGREE(GON)
0.44
1.02
0.25
0.37
0.83
DEGREC(GAT)
1.98
2.44
0.96
1.03
0.79
Figure 2: The subgraph agglomeration results MUTAG dataset. The first shows correct prediction. The second and the third row report two typical examples of errors. Red is mutagenic, blue is non-mutagenic, gray is selected. The colored edges link the selected nodes. The process goes from left to right. The graph on the far left in each row displays the score for individual nodes.
graph will not influence the final prediction. ssowss the explanation AUC and time efficiency (the training time is shown outside the parentheses for PGExplainer). We have the following key findings. First, DEGREE achieves SOTA performances in most scenarios, showing its advantages in faithfulness over baseline methods. Second, the performance of DEGREE on GCN and GAT models can achieve similar high performance. This observation demonstrates the adaptability of our approach. Third, the improvement of AUC on BA-Community (79%) and MUTAG (75%) is more noticeable, where two datasets distinguish themselves from others is that their features are not constants. It thus shows that our explanation method could well handle node features as they propagate through the graph structure. In terms of efficiency, DEGREE is implemented by decomposing the built-in forward propagation function, there is training process. The time cost highly correlated to the complexity of the target model and the input size. We report further quantitative experiments in Appendix D
5.4 QUALITATIVE EVALUATION
In this section, we use Graph-SSTP and MUTAG datasets to visualize the explanation and demon- strate the effectiveness of our subgraph agglomeration algorithm in Sec
8

---

Published as a conference paper at ICLR 2022
"Maybe it's asking too much, but movie is truly going to inspire me, want little more than this."
'Though Ford and Neeson capably hold our interest, but it's just not a thrilling movie."
Figure 3: The subgraph agglomeration results on the Graph-SST2 dataset. The first row shows an incorrect prediction, the second row shows the correct one. Red is negative, blue is positive.
In the first example, we show three visualizations from the MUTAG dataset in Figure 2 The first row represents a correctly predicted instance. Our model successfully identifies the "NO2" motif as a moderately positive symbol for mutagenicity. The "H" or the carbon ring is considered a negative sign for mutagenicity. Once the "NO2" and the ring join, they become a strong positive symbol for mutagenicity. This phenomenon is consistent with the knowledge that the carbon rings and "NO2" groups tend to be mutagenic (Debnath al. 1991). We check instances with wrong predictions and show two representative examples. From the second row in Fig. 2 the GCN model precisely finds the "NH2" motif with the ring motif strong mutagenic symbol. But another wandering part without connection shows a strong non-mutagenic effect, ultimately leading to an incorrect prediction. The second row shows another typical failure pattern. The model catches the "NH2" and part of the carbon ring as mutagenic symbol, but the "CH3" on the bottom right shows strong non-mutagenic effect. The model erroneously learns negative interaction between them.
In the second example, we show two visualizations for the Graph-SST2 dataset in Figure 3 The sentence in the first row labeled negative, yet prediction is wrong. Our algorithm can explain the decision that the GNN model regards first half of the sentence ("Maybe it's asking too much"" as negative, the second half ("going to inspire me", "want little more than this") as positive. But the model can not tell the subjunctive tone behind the word "if", and consequently yields positive but incorrect prediction. The sentence the second row is negative, and the prediction correct. Our algorithm precisely identifies the positive part ("Though Ford and Neeson capably hold our interest") and the negative part ("but its just not a thrilling movie"). Moreover, reveals that the GCN model can correctly learn the transition relationship between these two components.
We observe that our method can detect non-linear interactions between subgraphs throughout the agglomeration process from above examples. It can help diagnose the incorrect predictions and enhance the credibility of the model. More visualizations and efficiency study are Appendix E
CONCLUSIONS
In this work, we present DEGREE which explains a GNN by decomposing its feedforward prop- agation process. After summarizing the fundamental rules for designing decomposition based ex- planation, we propose concrete decomposition schemes for those commonly used layers in GNNs. We also design an algorithm to provide subgraph-level explanation via agglomeration, which effi- ciently employs the topological information in graphs. Experimental results show that DEGREE outperforms baselines
of faithfulness and can capture meaningful structures in graph data.

---

Published as a conference paper at ICLR 2022
REFERENCES
Federico Baldassarre and Hossein Azizpour. Explainability techniques for graph convolutional net- works, 2019.
Albert-László Barabási and Réka Albert. Emergence of scaling in random networks. science, 286 (5439):509-512, 1999.
Lei Cai and Shuiwang Ji. A multi-scale approach for graph link prediction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 3308-3315, 2020.
Sergio Casas, Cole Gulino, Renjie Liao, and Raquel Urtasun. Spatially aaware graph neural networks for relational behavior forecasting from sensor data. arXiv preprint arXiv:1900.088 2019.
Chun-Hao Chang, Elliot Creager, Anna Goldenberg, and David Duvenaud. Explaining image clas- sifiers by counterfactual generation. arXiv preprint arXiv:
2018.
Asim Kumar Debnath, Rosa L Lopez de Compadre, Gargi Debnath, Alan J Shusterman, and Cor- win Hansch. Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro com- pounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34(2):886-777, 1991.
Jacob Devlin, Ming- Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding, 2019.
Mengnan Du, Ninghao Liu, and Xia Hu. Techniques for interpretable machine learning. Communi- cations of the ACM, 63(1):68-77 2019.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The World Wide Web Conference, pp. 417-426, 2019.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv preprint 156.0: 163, 2015.
Qiang Huang, Makoto Yamada, Yuan Tian, Dinesh Singh, Dawei Yin, and Chang. Graphlime: Local interpretable model explanations for graph neural networks. arXiv preprint arXiv:2001.06216. 2020.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax, 2017.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint 160.0020990 2016.
Jian Liang, Bing Bai, Yuren Cao, Kun Bai, and Fei Wang. Adversarial infidelity learning for model interpretation. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 286-296, 2020.
Cheng-Hao Liu, Maksym Korablyov. Stanislaw Jastrzebski, Pawet Wtodarczykk-Pruszyiss Yoshua Bengio, and Marwin HS Segler. Retrognn: Approximating retrosynthesis by graph neural net- works for de novo drug design. arXiv preprint arXiv:2011.13044 2020.
Meng Liu, Youzhi Luo, Limei Wang, Yaochen Xie, Hao Yuan, Shurui Gui, Haiyang Yu, Zhao Xu, Jingtun Zhang, Yi Liu, Keqiang Yan, Haoran Liu, Cong Fu, Bora Oztekin, Xuan Zhang, and Shuiwang Ji. DIG: A turnkey library for diving into graph deep learning research. arXiv preprint 1rXiv:2103.12600 2021.
Ninghao Liu, Qiaoyu Tan, Yuening Li, Hongxia Yang, Jingren Zhou, and Xia Hu. Is single vector enough? exploring node polysemy for network embedding. Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery Data Mining, pp. 932-940, 2019.
Ana Lucic, Maartje ter Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf- gnnexplainer: Counterfactual explanations for graph neural networks, 2021.
Scott Lundberg and Su-In Lee. unified approach to interpreting model predictions, 2017.
10

---

Published as a conference paper at ICLR 2022
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. arXiv preprint 1rX0::0111.04573, 2020.
W James Murdoch and Arthur Szlam. Automatic rule extraction from long short term memory networks. arXiv preprini arXiv: 170.002540 2017.
W James Murdoch, Peter J Liu, and Bin Yu. Beyond word importance: Contextual decomposition to extract interactions from Istms. arXiv preprint arXiv: 1xX.v:800.005533 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/CVF Conference on Computer Vision and Pattern Recognition, pp. 10772-10781, 2019.
Cynthia Rudin. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206-215, 2019.
Thomas Schnake, Oliver Eberle, Jonas Lederer, Shinichi Nakajima, Kristof T. Schütt, Klaus-Rober Müller, and Grégoire Montavon. Higher-order explanations of graph neural networks via relevant walks, 2020.
Robert Schwarzenberg, Mare Hübner, David Harbecke, Christoph Alt, and Leonhard Hennig, Lay- erwise relevance visualization in convolutional text graph classifiers, 2019.
Avanti Shrikumar, Peyton Greenside, and Anshul Kundaje. Learning important features through propagating activation differences. In International Conference on Machine Learning, pp. 3145- 3153. PMLR, 2017.
Karen Simonyan, Andrea Vedaldi, and Andrew Zisserman. Deep inside convolutional networks: Vi- sualising image classification models and saliency maps. arXiv preprint arXiv:1312.6034 2013.
Chandan Singh, W James Murdoch, and Bin Yu. Hierarchical interpretations for neural network predictions. arXiv preprint arXiv:1806.05337, 2018.
Mukund Sundararajan, Ankur Taly, and Qiqi Yan. Axiomatic attribution for deep networks. In International Conference on Machine Learning, pp. 3319-3328, PMLR, 2017.
Petar Veličkovié, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 2017.
Minh N Vu and My T Thai. Pem-explainer: Probabilistic graphical model explanations for graph neural networks. arXiv preprint arXiv:2010.05788, 2020.
Xiang Wang, Yingxin Wu, An Zhang, Xiangnan He, and Tat seng Chua. Causal screening to www.netfformmt
interpret graph neural networks, 2021. URL https: http:////pp/vvvieeeeeeeeee https::/ nzKv5vxZfge!
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful graph neural networks? arXiv preprint 1rXiv:1810.00826, 2018.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Gener- ating explanations graph neural networks. Advances neural information processing systems, 32:9240, 2019.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 430 438, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neural networks via subgraph explorations. arXiv preprint 55X:v:2102.05512. 2021.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. arXiv preprint arXiv: arXiv:1802.0000 0809, 2018.
11

---

Published as a conference paper at ICLR 2022
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 32, 2018.
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, Lifeng Wang, Changcheng Li, and Maosong Sun. Graph neural networks: A review of methods and applications. arXiv preprint 17X1::8812.08344, 2018.
12

---

Published as a conference paper at ICLR 2022
A DATASETS AND EXPERIMENTAL SETTING
In this section, we introduce the detail of the datasets as wall as the experimental setting. The code can be found at
4open. scí enceee/neeGeRRE
3128
Model setup: We adopt GCN model and GAT model architecture for corresponding experiments. We use GCN #in_channel,, #out_channer cchannll,,l....mammmme activation) denote GCN layer, and similar nota- tion for GAT layer and fully connected layer.
The structure of GCN model for node classification task following: GCN #feature,,,, 20, ReI.U) FC(,0, 20, ReLU) - FC(,0, #label, Softmaz)..
GCN (#feeture, 20, Re.U') GCN(#feature, 20, ReTUU
For graph classification task, we adopt Max-pooling layer before the FC layers: GCe(tfeeuur,, 20, RU) - GCN #feature 20, ReLU) GCN(#feature, 20, ReLU) Mazpooling FC(20, 20, ReLU) FC(20, #label, Softmar).
For GAT model architecture, we replace all GCN layers with GAT layer and keep the remaining setting unchanged. For experiments Tree-Grid dataset, adopt 4-layer GCN/GAT model by adding one more GCN/GAT layer with same setting before FC layers.
Dataset statistic: The statistics of synthetic datasets and real-world datasets reported in Table
Table 2: Statistics of the dataset
Dataset
# of nodes
# of edges
# of graphs
labels
features
BA-Shapes
700
4,110
4
Constant
BA-Coue DA-Community
1,400
8,920
Generated from Labels
Tree-Cycles
871
1,950
2
Constant
Tree-Grid
1,231
3,410
Constant
MUTAG 131,488
266,894
4,337
Node Class
Graph-SST2 714,325
1,288,566
70,042
BERT Word Embedding
Experimental setting: For all datasets, we use train/validation/test split of 80%/10%//00. For all synthetic datasets, the GCN model is trained for 1,000 epochs and the GAT model is trained for 200 epochs. For MUTAG dataset, the GCN and GAT model is trained epochs. For Graph-SST2 dataset, the GCN model is trained 10 epochs. We use Adam optimizer and set the learning rate to 0.005, the other parameters remain at their default values. We also report the accuracy metric reached on each dataset in Table
Table 3: Accuracy performance of GNN models
Dataset
BA-Shapes
BA-Community
Tree-Cycles
Tree-Grid
MUTAG
Graph-SST2
Task
Node Classification
Graph Classification
Model
GCN
GAT
GCN
GAT
GCN
GAT
GCN
GAT
GCN
GAT
GCN
Training
0.96 0.98
0.99 0.83
0.91 0.93
0.85 0.83
0.80 0.81
0.91
Validation
0.97 0.96
0.88 0.85
0.90 0.92
0.84
0.84
0.78
0.80
0.90
Testing
0.93 0.94
0.87 0.83
0.89 0.92
0.81 0.80
0.77 0.79
0.88
Hardware setting: We introduce the hardware that we use for the experiments.
CPU: AMD EPYC 7282 16-Core Processor.
GPU: GeForce RTX 3090 WVIDIA-MME 460.32.03 Driver Version: 460.32.03 CUDA Version: 11.2.
13

---

Published as a conference paper at ICLR 2022
B ATTENTION DECOMPOSITION
To calculate the attention coefficient, we need to first calculate the pre-normalized attention coeffi- cient between node and node as:
Oz = [eakg]RelLU(XXX00))XXXXX
And we use āi,j to denote a vector which consist of the pre-normalized attention coefficients be- tween node and its neighbors. Then we calculate the normalized attention coefficient node via Sof Softmax over its neighbors:
042 SoSSoommarree
We use Softmar(1 : I) to measure the dimension wise magnitude, and let them compete for the original value. The division between two vectors is element-wise.
C ALGORITHM
We conclude the computation steps of subgraph- explanation (Sec in Algorithm and
Algorithm 1: The algorithm subgraph agglomeration
Data: Graph 9 (V, E), Label y. Target model Hyperparameter q-
Result: Explanation tree T.
Score Metric Function: ø from Algorithm 3
Initialization: score queue ScoresQ) + Ø, explanation tree T + Ø.
for U E V do
I ScoresQ.add ([v}, priority o(f. {u))) end
while Scores( is not empty do Select Base Subgraph Set B = ScoresQ.oop(g) T.add(33)
ScoresQ <- Ø for Bn E B
Candidate Subgroup Set C = Get Candidate(G, B,.) with Algorithm for do CcdresQ.add(c priorit <(J,y,c) $lS.1, Bm))
end end
ScoresQ = [ScoresQ - E(Scores())
end
return T
Algorithm 2: The algorithm of candidate node selection
Data: Graph g (V, &), Subgraph B... Result: Candidate Subgraph Set
C+2
Neighbour nodes N < (Āle =< n, 2, E E,n n E Bm, 7 E V Bm) for E N do
| C.add(B,, U (v))
end
return C
14

---

Published as a conference paper at ICLR 2022
Algorithm 3: The algorithm of score computation e
Data: Graph G = -V, E), model f. No
Result: score V))
Sample a context set S by Random Walk within the L-hopp neighbor region of N..
Return: o(p", N)
SST E f()))
D EFFICIENCY STUDY
DEGREE is achieved by decomposing the feedforward process of the target model. Thus the ef- ficiency is highly dependent on the model structure. We report the statistic of time consuming on each dataset for GCN and GAT model in Table
We quantified the relationship between the size of the calculation graph and the time taken. The result is reported in Figure 4
Lacke
Figure 4: The quantitative studies of efficiency for different datasets and models. For the synthetic datasets, the horizontal coordinate represents the number of nodes in computation graph. For the MUTAG dataset, the horizontal coordinate represents the number of edges in computation graph.
Table 4: Efficiency performance.
Dataset
BA-Shapes
BA- ComCumtu
Tree-Cycles
Tree-Grid
MUTAG
Model
GCN
GAT
GCN
GAT
GCN
GAT
GCN GAT
GCN GAT
Avg. Time (s)
0.44
1.98
1.02 2.44
0.25
0.96
0.37 1.03
0.83 0.79
E QUALITATIVE EXPERIMENTS EXAMPLES
In this section, we report more qualitative evaluation results on the Graph-SST2 and the MUTAG datasets. The results are reported in Figure 5 and 6 We also investigate the time efficiency of our agglomeration algorithm in terms the relationship between q. the node number and the time spent.
We also investigate the time efficiency of our agglomeration algorithm in terms of the relationship between q, the node number and the time spent.
F ADDITIONAL EXPERIMENTS FOR REBUTTAL
F.1 QUANTITATIVE EVALUATION
In this section, we perform additional experiments comparing DEGREE with GNN-LRP Schnake et al. (2020) and SubgraphX Yuan et al. (2021). We use the MUTAG dataset and the Graph-SST2 dataset, as presented in Sec 5.1 The target model is the same as that introduced in See 3.2.2 Note that modify our method to search only for nodes that boost the score of the class of interest. We employ the Liang et al. (2020) as an evaluation metric. The ACC reflects the consistency of predictions based the whole graph and between interpreted subgraphs. Thus, ACC does not
15

---

Published as a conference paper at ICLR 2022
(a) Well, it probably won't have you swinging from the trees hooting it's praises, but it's definitely worth taking a look.
(b) Trouble every day is success some sense, it's hard to film so cold and dead.
Makes unusual pleasantly haunting debut behind the camera.
(d) Not everything in this ambitious comic escapade works, but Coppola, along with his sister, Sofia, is real filmmaker
Figure 5: The subgraph agglomeration results on the Graph-SST2 dataset with a GCN graph classi- fier. All instances all correctly predicted. Red is negative and blue is positive.
require ground truth label. We further define the sparsity as the ratio of the size the explanation subgraph to the original graph. At the same sparsity, the higher the ACC, the better the interpretation. Figure g shows the ACC of DEGREE, GNN-LRP and SubgraphX under various sparsity. We can find that DEGREE has competitive performance compared to GNN-LRP and SubgraphX. Besides, DEGREE has better time efficiency.
F.2 QUALITATIVE COMPARISON
In this section we make qualitative comparison between DEGREE and SubgraphX. We randomly select number of similar molecules and visualize the explanations generated by DEGREE and SubgraphX. We report them in the Figure We can find that none the subgraphs generated by SubgraphX include the 'N-H' 'N-O'. They only select the carbon ring as the important part. In contrast, DEGREE can precisely indicate that the mutagenicity caused by the 'N-H' or 'N-O'.
F.3 FORWARD-LOOKKING EXPERIMENT
In this section, we present simple prospective experiment from the early stages of this work. The dataset was generated by modifying the MUTAG dataset by selecting half of the graphs in the dataset and picking node at random in each graph, giving a special feature value of while giving the other nodes background white noise feature. Our task is to predict whether graph contains special nodes or not. train a 3-layer GCN which achieves 100% accuracy. We then use DEGREE to calculate the contribution score for each node. DEGREE is able to locate special nodes with 100% accuracy. Figure shows the visualisation.
16

---

Published as a conference paper at ICLR 2022
M M
M
Figure 6: The subgraph agglomeration results on MUTAG dataset with GCN graph classifier. All instances are incorrectly predicted. Red is mutagenic, blue is non-mutagenic, gray is not selected. The colored edges link the selected nodes.
17

---

Published as a conference paper at ICLR 2022
Ouration
0.
08
0.7
0.6
0.5
0.3
Num
100
Figure Relationship between the time efficiency(s), graph size and on the MUTAG dataset.
Graph-SST2
MUTAG
10
0.8
06
DEGREE
DEGREE
SubgraphX
SubgraphX
GNN LAP
GNN LRP
0.2
04
06
0.8
1.0
02
0.4
06
0.8
10
Sparsity
Sparsity
Figure 8: ACC of DEGREE, GNN-LRP and SubgraphX on MUTAG and Graph-SST2.
18

---

Published as a conference paper at ICLR 2022
Figure 9: Qualitative comparison of DEGREE and SubgraphX. The first row shows the interpreta- tion generated by SubgraphX. The second row is generated by DEGREE. The red color indicates mutagenicity.
0.034
8.006
Figure 10: Visualization of the heward-looking experiment. DEGREE can locate the special node
with 100% accuracy.
19


Reviews:
[{"review_id": "lIJLrT-HN15", "reviewer": "Reviewer_gPGV", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "\nThe main concern of this paper is the decomposition assumption.  Because of the nonlinearity property in neural networks, how to decompose to the target portion and the background portion for the input features/representations.  It likely has potential interactions between the target portion and the background portion. \n\nAs for the faithfulness issue, there exist a few decomposition-based explanations methods, e.g.,  Layer-wise Relevance Propagation (LRP) [1], Excitation BP [2], and GNN-LRP [3]. Most of their methods are proposed to employ score decomposition.\n\nThe subgraph-level interpretation search algorithm has been already explored by others [4]. It would be better if authors can compare with them.\n\n[1] Explainability techniques for graph convolutional networks\n\n[2] Explainability methods for graph convolutional neural networks\n\n[3] Higher-order explanations of graph neural networks via relevant walks\n\n[4] On Explainability of Graph Neural Networks via Subgraph Explorations\n\n\nIt is not easy to understand the description in the qualitative evaluation section, especially the description of Figures 2 and 3. \nMeanwhile, it would be better if authors can compare with other explanations methods in the qualitative evaluation section.\n", "summary_of_the_paper": "This paper proposes a decomposition-based explanations method for graph neural networks.  In detail, the authors design a subgraph level interpretation algorithm to reveal complex interactions between graph nodes, so as to achieve the faithful explanation for GNN predictions. They demonstrate the effectiveness of the proposed method on synthetic and real-world datasets. \n\n", "summary_of_the_review": "The main concern of this paper is the decomposition assumption.  Because of the nonlinearity property in neural networks, how to decompose to the target portion and the background portion for the input features/representations.  It likely has potential interactions between the target portion and the background portion. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "W9-E3Uzx_F", "reviewer": "Reviewer_XaeP", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths: \n- The problem studied is of importance and interesting. \n- The paper is generally well organized. \n- Quantitative experiments are done, which is a plus for subjective topics like XAI. \n\nWeaknesses: \n- Concepts are not defined or hard to follow. See details. \n- Qualitative experiments are hard to follow. See details. \n- Questions/unclear points regarding technical details. See details. \n- The decomposition method seems straightforward, especially the GCN decomposition (as it is largely linear). \n\nDetails. \n- Some technical concepts are not defined or hard to follow. \n    - Section 3.1. The goal of explanation is to find the most important subgraph in $\\mathcal{G}$ given $f(\\mathcal{G})$. The concept is vaguely defined. What is the concept of 'important'? Further, in the experiments, the task is actually to predict whether a node/edge is important or not. This seems to deviate from the definition. \n    - Section 4. 'We could compute the contribution score of any given node groups'. However, the notion of 'contribution score' is not defined previously. This makes this section hard to understand. \n- Qualitative experiments are hard to follow. \n    - Figure 2. What does it mean 'the process goes from left to right'?\n    - The authors claim that 'existing works suffer from adversarial triggering issues (perturbation) or inaccuracy (approximation)'. However, the claim is not supported, especially the perturbation-based drawback of unrealistic structures. I think this point can be better supported by showing examples that perturbation-based methods indeed generate such samples. At this point, I find it hard to evaluate the qualitative experiments. \n- Questions regarding technical details. \n    - Section 3.1, $f: \\mathcal{G}\\mapsto \\mathbb{R}^{|\\mathcal{V}|}$ or $\\mathbb{R}$. It seems that the formulation only works on binary classification or regression. Can this framework (respectively, DEGREE) be extended to the multi-class setting? \n    - Section 3.3 Intuition (2): ideally there should be little interaction between the target portion and the background portion. However, in graphs, this intuition can hardly be satisfied because nodes are connected to each other. How does the framework work when this intuition does not hold? Or can you provide evidence that this intuition somehow holds in real-world data? \n    - Equation 13, this equation is hard to understand. First, what does it mean $softmax(\\mathbf{X}[t])$? Second, what does it mean $\\exp(|\\mathbf{X}^\\gamma[t]|)$? Third, what does it mean to divide vectors with vectors (given that $\\mathbf{X}[t]$ is a vector)?\n\n- Minor issues. \n    - Please change the coloring of the figures such that they are visible when printed out. \n    - Section 4.2, how should we initialize $\\mathcal{E}$, $\\mathcal{S}_i$? How should we tune the parameters $I, q$? \n    - How is the definition of 'importance' in Graph-SST2? \n    - Section 5, last paragraph, 'detect non-linear interactions', what does it mean non-linear interactions? Does it mean language conjunctions such as 'if', 'but'? ", "summary_of_the_paper": "This paper proposes a decomposition-based explanation method for graph neural networks. The motivation of this paper is that existing works based on approximation and perturbation suffer from drawbacks. To address the issue of existing works, the authors directly decompose the influence of node groups in the forward pass. The decomposition rules are designed for GCN and GAT. Further, to efficiently select subgraph groups from all possible combinations, the authors propose a greedy approach to search for maximally influential node sets. Experiments on synthetic and real-world datasets verify the improvements over existing works. ", "summary_of_the_review": "In summary, this paper has its merits. The paper tackles an interesting problem. The proposed framework is generally sound. The paper is organized well in general. However, given its unclear points in experiments and technical details, I do not recommend acceptance at this point. \n\n====Post Response====\n\nMy doubts and suggested weaknesses are addressed partly. I am willing to suggest borderline accept. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "W5EUN7S4kRQ", "reviewer": "Reviewer_eChJ", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper focuses on the explanation of GNN performance, which is an interesting and critical problem. The paper proposes a reasonable method for the problem to decomposite the graph. The experiments are also comprehensive. However, there are still some points required to be clarified.\n\n1,  The new scoring function proposed in the paper uses a random walk process, so will the calculation process has a high time complexity and space complexity (storing sample graphs)?\n\n2, In q · maxv′ r(v′), what is the impact of the hyper-parameter q on the subgraph expansion?\n\n3, The AUC used in the experiments should be explained in detail. For me, I have to search previous works to understand how to use it in GNN explanation issue. It is not friendly to common readers.\n\n", "summary_of_the_paper": "The paper provides DEGREE, which decomposes the feedforward propagation mechanism of a GNN to understand it. They give realistic decomposition techniques for those typically used layers in GNNs after presenting the key guidelines for developing decomposition-based explanations. They also devise an approach for providing subgraph-level explanation via agglomeration, which makes effective use of graph topology. DEGREE surpasses baselines in terms of fidelity and can capture important structures in graph data, according to experimental results.", "summary_of_the_review": "The paper is easy to follow and has a reasonable method. Besides, the comprehensive experiments, especially the visualization of results, verify the effectiveness of the proposed method. I surely recommend acceptance after my above doubt is solved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "QuHUN2OJkI9", "reviewer": "Reviewer_81sK", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "Strengths:\nS1. The paper innovatively proposes a new explainable framework that decomposes the information into target and background portion. In contrast of previously used approximation-based, perturbation-based, additive feature attribution methods, the authors claim that the newly proposed method has the advantages of higher fidelity and node-level explainability.\nS2. Two popular GNN framework GCN and GAT are used as examples for decomposition operation, which demonstrates the methods compatibility to the current mainstream. A new subgraph construction algorithm is also proposed to tackle the problem arising during finding most important subgraphs, i.e., it’s impossible to enumerate all subgraphs.\nS3. The quantitative evaluation shows in two metrics: Explanation AUC and time efficiency. The proposed method significantly outperforms other benchmarked methods in at least one of the metrics (some benchmarked methods are only shown for Explanation AUC, not for time efficiency though), potentially making it a new choice under different use scenario. A qualitative evaluation was also included for a visual check of the result quality.\nS4. The paper is well organized and clearly written. Figures are provided with descriptive caption, including details needed for comprehension. Datasets includes both synthetic datasets and real-world datasets for diversity.\n\nWeaknesses: \nW1. The transition from absolute contribution scores to relative contribution score in Sec 4.1 is abrupt without detailed reasons. Why are relative scores preferred? Also, if they are preferred, why use absolute score in Sec 3? Providing answers to these two questions will make the logic flow more smoothly.\nW2. The exclusion of Graph-SST2 dataset from quantitative evaluation raises the question of whether the model has a poor performance on this dataset and hence has little generalization power. Providing the reasons for not including this dataset makes the benchmarking more supportive for the claimed superior model performance.\nW3. The limitation of the model was shown in the wrong prediction example in the qualitative evaluation but was not discussed in detail. What could have caused the wrong prediction and how to circumvent them?\nW4. Missing related work that should be discussed: On Explainability of Graph Neural Networks via Subgraph Explorations (ICML 2021)\n\nMinor comments:\n1. In Figure 2, I assume the shade of color means the value of the score, but it is probably a better idea to explicitly state it in the caption or have a legend in the figure.\n2. It would be preferred to include the statistics such as the number of graphs for synthetic datasets as well.\n\n\n", "summary_of_the_paper": "The paper aims at tackling the black-box nature problem of GNN by introducing a new type of explainable GNN framework called DEGREE (Decomposition based Explanation for GRaph nEural nEtworks). There are mainly two innovations. The first one lies in its ability to track contribution of components in the input graph. The second one is the algorithm for subgraph-level explanation via agglomeration. The model achieves a good compromise between performance and time efficiency.", "summary_of_the_review": "The paper innovatively proposes to decompose the information flow for explainability and provides a new algorithm to construct subgraphs to reveal more complex interactions. This novel way of explaining graph component contributions give insights into a new explainable GNN framework and is potentially inspiring for other works. The experiments also show its superior performance and time efficiency compared with other methods (although some related work is missing). Thus, I am slightly positive of this paper.\n\n====Post Response====\n\nAfter reading the author response, they have indeed addressed some of my concerns. However, after also reading through the other reviews and their respective replies, I am inclined to keep the score of \"marginally above the acceptance threshold\" because I am still more positive towards the work. I have additionally increased the novelty and significance from a 2 to a 3. Thank you for providing the reply, especially the details regarding my original concern about Graph-SST2. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a decomposition-based explanation method for graph neural networks. The motivation of this paper is that existing works based on approximation and perturbation suffer from various drawbacks. To address the challenges of existing works, the authors directly decompose the influence of node groups in the forward pass. The decomposition rules are designed for GCN and GAT. Further, to efficiently select subgraph groups from all possible combinations, the authors propose a greedy approach to search for maximally influential node sets. Experiments on synthetic and real-world datasets verify the improvements over existing works. During their initial responses, reviewers suggested that the authors experiment with more baselines and also clarify some of the technical details. The authors revised their manuscript to address several of these comments. So, I am tentatively assigning an accept to this paper.
Decision: Accept (Poster)