DEGREE: DECOMPOSITION BASED EXPLANATION
Year: 2021

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.

heading: 1 INTRODUCTION
text: Graph Neural Networks (GNNs) play an important role in 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., 2020), and agent interaction (Casas et al., 2019). However, GNN suffers from its black-box nature and lacks a faithful explanation of its predictions.
Recently, several approaches have been proposed to explain GNNs. Some of them leverage gradient 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., 2021), under the assumption that removing the vital information from input would significantly reduce output confidence. However, approximation based methods do not guarantee the fidelity of the explanation obtained, as Rudin (2019) states that a surrogate that mimics the original model possibly employs distinct features. On the other hand, perturbation based approaches may trigger adversarial nature of the depth model. Chang 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 & Lee, 2017) such as gradient based methods and GNNExplainer only provide a single heatmap or subgraph as explanation. The nodes in graph are 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 of components in the input graph to the GNN prediction. Specifically, we first summarize the intuition behind the Context Decomposition (CD) algorithm (Murdoch et al., 2018) and propose that the information flow in GNN’s message propagation mechanism is decomposable. Then we design the decomposition schemes for the most commonly used layers and operations in GNNs, so 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 a series of subgraph 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 decomposition. 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 a series of 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.

heading: 2 RELATED WORK
text: Despite the great success in 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). Meanwhile, the need to tackle non-Euclidean 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 & Ji, 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; Sundararajan et al., 2017; Simonyan et 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 information, which is a crucial property of graph data. Second, some methods trace the model prediction back to the input space in a backpropagation manner layer by layer (Schwarzenberg et al., 2019; Schnake et al., 2020). Third, some methods define a perturbation-based interpretation whereby they perturb node, edge, or 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 Screening (Wang et al., 2021) searches for the important subgraph by monitoring the mutual information from a cause-effect standpoint. CF-GNNExplainer (Lucic et al., 2021) proposes to generate counterfactual explanations by finding the minimal number of edges to be removed such that the prediction changes. In addition, XGNN (Yuan et al., 2020) builds a 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.
Many previous explanation methods for GNNs suffer from adversarial triggering issues, faithfulness issues and additive assumptions. To this end, we propose a 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-based approach. Since no surrogate models are used, DEGREE guarantees its faithfulness. Meanwhile, by integrating the decomposition to the normal layer, DEGREE does not have any additional training process.

heading: 3 DEGREE: DECOMPOSITION BASED EXPLANATION FOR GNNS
text: In 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

heading: 3.1 PROBLEM DEFINITION
text: We first introduce the notations used in this work. Given a graph G = (V, E), where V is the set of nodes and E is the set of edges between nodes. The adjacency matrix of G is denoted as A ∈ RN×N , where N = |V| is the number of nodes, so V = {v1, v2, ..., vN}. The nodes are associated with features, and the feature matrix is denoted as X ∈ RN×F , where F is the feature dimension. In this work, we focus on explaining GNN-based classification models. Let f denote the target GNN model. f computes the likelihood of a node or graph belonging to the target class, where f : G 7→ R|V| or f : G 7→ R, for node or graph classification respectively. The goal of explanation is to find the most important subgraph in G given f(G), which requires measuring the contribution of all possible subgraphs and find the ones with high contribution scores. However, there are two challenges to be addressed. (1) Given any subgraph of interest, how to estimate its contribution without breaking up the input graph? (2) The number of all subgraphs in G is usually very large, so how to choose candidate subgraphs for improving explanation efficiency? We tackle the first challenge in the following part of Sec 3 and solve the second one in Sec 4.

heading: 3.2 DECOMPOSITION BASED EXPLANATION
text: In general, a prediction model f contains multiple layers Lt, t ∈ {1, . . . , T}: f(X) = LT ◦ LT−1 ◦ · · · ◦ L2 ◦ L1(X). (1)
Let X[t] denotes the input of Lt, so X[t + 1] = Lt(X[t]) and X[1] = X. The symbol ◦ denotes function composition. Here X[t] ∈ RN×Ft is the embedding matrix at t-th layer, where Ft is the latent dimension. The embedding vector of the i-th node at t-th layer is denoted as Xi[t].
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 propagation. We call the information propagated from the target group as target portion, and the rest of information is called background portion. In the following, we use γ and β to denote target portion and background portion, respectively. Let m ∈ RN and mn ∈ {0, 1}, where mn = 1 means vn belongs to the target group and otherwise mn = 0. 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)X and Xβ = (I−diag(m))X, respectively. In a neural network, different parts of input are entangled in the feedforward process into latent representations, which poses challenges for explanation. Suppose the target and background portion in X[t] are known from prior layer, we could explain the model if we can still distinguish the information flows of the two portions inside Lt. That is, at layer Lt, suppose its input can be decomposed as X[t] = Xγ [t]+Xβ [t], the following relations need to hold for explanation:
LDt (X γ [t],Xβ [t]) = Γ(Xγ [t],Xβ [t])︸ ︷︷ ︸ Xγ [t+1] , B(Xγ [t],Xβ [t])︸ ︷︷ ︸ Xβ [t+1]  (2) Lt(X[t]) = X[t+ 1] = X γ [t+ 1] + Xβ [t+ 1], (3)
where LDt (·, ·) denotes the decomposed version of layer Lt. Γ(·, ·) and B(·, ·) corresponds to the contribution of the target and the background portion to layer Lt. Xγ [t+ 1] and Xβ [t+ 1] denotes the target and background portion of X[t + 1] as the input to the next layer. The decomposition above goes from the input, through all intermediate layers, to the final prediction. If a target node group or subgraph is important, then it should contributes to most of the prediction, meaning that Γ(Xγ [T ],Xβ [T ]) ≈ f(X).

heading: 3.3 INTUITIONS BEHIND DECOMPOSITION BASED EXPLANATION FOR GNN
text: The intuition behind decomposition based explanation are summarized as two rules: (1) the target and background portion at 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. It is worth noting that the partition is not dimension-wise, meaning that each latent dimension may contain information from both target and background portions.
Figure 1 briefly illustrates the working principle of GNNs: the model computes neural message for each node pair and aggregates message for them from their neighbors. One more rule should be introduced to govern the decomposition of GNNs: the target and background portion of a node feature aggregates from the target and background portion of its neighbours, respectively. This can be easily illustrated by a decomposition of the concise aggregation mechanism of GNN:
X[t+ 1] = AX[t] = A ( Xγ [t] + Xβ [t] ) = AXγ [t]︸ ︷︷ ︸
Xγ [t+1] +AXβ [t]︸ ︷︷ ︸ Xβ [t+1] , (4)
where the intuition is that information aggregation is distributive in nature. To develop an effective explanation, several challenges should be tackled. First, how to design the decomposition scheme for different types of layers? Second, how to find a good target group given all possible combinations?

heading: 3.4 DECOMPOSING GNN LAYERS
text: In this work, we consider the decomposition scheme for two commonly used GNN architectures: GCN (Kipf & Welling, 2016) and GAT (Veličković et al., 2017).

heading: 3.4.1 DECOMPOSING GCNS
text: The GCN architecture consists of graph convolution layers, fully connected layers, and ReLU.
Graph Convolution Layer: The graph convolution operation pass messages between nodes:
X[t+ 1] = D̃− 1 2 ÃD̃− 1 2X[t]W + b, (5)
where W and b denote the trainable weights and bias. Here b is optional. Ã = A + I denotes the adjacency matrix with self loop. The matrix D̃i,i = ∑ j Ãi,j is the diagonal degree matrix of Ã. The corresponding decomposition can be designed as follows:
γ[t] = D̃− 1 2 ÃD̃− 1 2Xγ [t]W , β[t] = D̃− 1 2 ÃD̃− 1 2Xβ [t]W, (6) Xγ [t+ 1] = γ[t] + b · ∣∣γ[t]∣∣∣∣γ[t]∣∣+∣∣β[t]∣∣ , Xβ [t+ 1] = β[t] + b · ∣∣β[t]∣∣∣∣γ[t]∣∣+∣∣β[t]∣∣ , (7) where Xγ [t] and Xβ [t] is the target and background portion of X[t], respectively. The derivation of γ[t] and β[t] is intuitive since graph convolution is a linear operation. Motivated by (Singh et al., 2018), we let γ[t] and β[t] to compete for their share of b, as shown in Eq 7.
∣∣γ[t]∣∣ ∈ RFt+1 measures the dimension-wise magnitude of Xγ [t] after the linear mapping (
∣∣β[t]∣∣ is defined similarly). Fully Connected Layer: A fully connected layer prevalent in the model is shown below:
X[t+ 1] = X[t]Θ + b, (8)
where Θ and b denote trainable weights and bias. Structure-wise, it is very similar to the GCN. The decomposition can be designed as:
Xγ [t+1] = Xγ [t]Θ+b· ∣∣Xγ [t]Θ∣∣∣∣Xγ [t]Θ∣∣+∣∣Xβ [t]Θ∣∣ ,Xβ [t+1] = Xβ [t]Θ+b· ∣∣Xβ [t]Θ∣∣∣∣Xγ [t]Θ∣∣+∣∣Xβ [t]Θ∣∣ . (9) ReLU Activation: For the activation operator ReLU, we use the telescoping sum decomposition from Murdoch & Szlam (2017). We update the target term first and then update the background term by subtracting this from total activation:
Xγ [t+ 1] = ReLU ( Xγ [t] ) , Xβ [t+ 1] = ReLU ( Xγ [t] + Xβ [t] ) − ReLU ( Xγ [t] ) . (10)
Maxpooling: We track the node indices selected by pooling in both target and background portion.

heading: 3.4.2 DECOMPOSING GATS
text: The graph attention layer in GAT is similar to Eq. 5, but uses the attention coefficients αi,j to aggregate the information (an alternative way to understand Eq. 5 is that αi,j = (D̃− 1 2 ÃD̃− 1 2 )i,j):
αi,j =
exp ( LeakyReLU ([ Xi[t]W‖Xj [t]W ] a ))
∑ k∈Ni∪{i} exp ( LeakyReLU ([ Xi[t]W‖Xk[t]W ] a )) , (11)
where ‖ represents the concatenation operation. W and a are parameters. Xi[t] denotes the embedding of node i at layer Lt. Ni denotes the neighbors of node i. Therefore, a 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:
Xi[t]‖Xj [t] = Xγi [t]‖X γ j [t] + X β i [t]‖X β j [t]. (12)
For LeakyReLU, the idea of decomposition is the same as ReLU. For softmax operation, we split the coefficients proportionally to the exponential value of the target and the background term of input:
Xγ [t+ 1] = softmax ( X[t] ) ·
exp (∣∣Xγ [t]∣∣)
exp (∣∣Xγ [t]∣∣)+ exp(∣∣Xβ [t]∣∣) ,
Xβ [t+ 1] = softmax ( X[t] ) ·
exp (∣∣Xβ [t]∣∣)
exp (∣∣Xβ [t]∣∣)+ exp(∣∣Xγ [t]∣∣) .
(13)
Here we employ the similar motivation that used to split bias term in Eq. 7, and let ∣∣Xγ [t]∣∣ and∣∣Xβ [t]∣∣ to compete for the original value.

heading: 4 SUBGRAPH-LEVEL EXPLANATION VIA AGGLOMERATION
text: Through decomposition, we could compute the contribution score of any given node groups. However, 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.

heading: 4.1 CONTEXTUAL CONTRIBUTION SCORE
text: We first introduce a new scoring function to be used in our algorithm. Different from the absolute contribution scores provided by decomposition, in many scenarios, we are more interested in the relative contribution of the target compared to its contexts. Let Vγ ⊂ V be the target node group, and fD(·) be the contribution score calculated from decomposition. The relative contribution of Vγ averaged over different contexts is calculated as:
φ(Vγ) , EC∼RW(NL(Vγ)) [ fD(Vγ ∪ C)− fD(C) ] , (14)
where C is the context around Vγ , and NL (Vγ) contains the neighboring nodes of Vγ within Lhops. Here we use a random walk process RW () to sample C within the neighborhood around Vγ . The reason for sampling within the neighborhood is based on the information aggregation, where a node collects the information from its neighbors within certain hops constrained by the GNN depth.

heading: 4.2 SUBGRAPHS CONSTRUCTION VIA AGGLOMERATION
text: 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 E = {S1, ...,SI}, where Si = {B1, ...,BMi} contains Mi subgraphs. At each step, the algorithm searches for the candidate node or node group v that most significantly affects the contribution of subgraph Bm,m ∈ {1, ...,Mi} according to the ranking score r(v):
s(v) , φ ( {v} ∪ Bm ) − φ (Bm) , r(v) , ∣∣∣s(v)− Ev′ [s(v′)]∣∣∣ , s.t. v, v′ ∈ N (Bm), (15) whereN (Bm) is the set of neighbor nodes or node groups to Bm. Here s(v) measures the influence of v to Bm, while r(v) further revises the value by considering the relative influence of v compared to other candidates v′. At the beginning of our algorithm, Bm = ∅. A node v is selected if r(v) ≥ q ·maxv′ r(v′), and we set q = 0.6 in experiments. The selected nodes are merged into subgraphs to form Si+1. Small subgraphs will be merged into larger ones, so we have Mi ≤ Mj , i ≥ j. The algorithm executes the above steps repeatedly and terminates until all nodes are included (i.e., Mi = 1), or a certain pre-defined step budget is used up. Further details of the algorithm can be found in Section B of the Appendix.

heading: 5 EXPERIMENTS

heading: 5.1 EXPERIMENTAL DATASETS
text: Following the setting in previous work (Ying et al., 2019), we adopt both synthetic datasets and real-world datasets. The statistic of all datasets are given in Sec A in the Appendix.

heading: 5.1.1 SYNTHETIC DATASETS
text: • BA-Shapes. BA-Shapes is a unitary graph based on a 300-node Barabási-Albert (BA) graph (Barabási & Albert, 1999). 80 five-node motifs are randomly attached to the base graph. The motif is a ”house” structured network in which the points are divided into top-nodes, middlenodes, 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 are eight node classes based on the structural roles and community membership.
• Tree-Cycles. The Tree-Cycles dataset germinates from an eight-level balanced binary tree base graph. The motif is a six-node cycle. 80 motifs are randomly added to the nodes of the base graph. The nodes are classified into two classes, i.e., base-nodes and motif-nodes. • Tree-Grids. It is constructed in the same way as the Tree-Cycles dataset. The Tree-Grid dataset has the same base graph while replacing the cycle motif with a 3-by-3 grid motif.

heading: 5.1.2 REAL-WORLD DATASETS
text: • MUTAG. It is a dataset with 4,337 molecule graphs. Every graph is labeled according to their mutagenic effect on the bacterium. As discussed in (Debnath et al., 1991), the molecule with chemical group NH2 or NO2 and carbon rings are known to be mutagenic. Since non-mutagenic molecules have no explicit motifs, only mutagenic ones are presented during the analysis. • Graph-SST2. It is a dataset of 70,042 sentiment graphs, which are converted through Biaffine parser (Liu et al., 2021). Every graph is labeled according to 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).

heading: 5.2 EXPERIMENTAL SETUP

heading: 5.2.1 EVALUATION METRICS
text: The interpretation problem is formalized as a 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 are important, and the rest are unimportant. We conduct quantitative experiments on the synthetic datasets and the MUTAG dataset, and qualitative experiments on the MUTAG dataset and the Graph-SST2 dataset. We adopt the Area Under Curve (AUC) to evaluate the performance quantitatively.

heading: 5.2.2 BASELINES METHODS AND IMPLEMENTATION DETAILS
text: Baselines Methods. We compare with four baselines methods: GRAD (Ying et al., 2019), GAT (Veličković et al., 2017), GNNExplainer (Ying et al., 2019) and PGExplainer (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 a 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 train/validation/test sets.
Explainer Setting. For all baseline methods, we keep the default hyper-parameters. For baselines (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.

heading: 5.3 QUANTITATIVE EVALUATION
text: In this section, we introduce experimental results on both synthetic datasets and the MUTAG dataset. For node classification, the computation graph only contains nodes within l-hop from the target node, where l is the number of model layer. The reason is that the nodes outside the computation
graph will not influence the final prediction. Table 1 shows 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 (˜9%) and MUTAG (˜5%) is more noticeable, where the 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, so there is no training process. The time cost is highly correlated to the complexity of the target model and the input size. We report further quantitative experiments in Appendix C.

heading: 5.4 QUALITATIVE EVALUATION
text: In this section, we use Graph-SST2 and MUTAG datasets to visualize the explanation and demonstrate the effectiveness of our subgraph agglomeration algorithm in Sec 4.
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 et 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 out the ”NH2” motif with the ring motif as a 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 a mutagenic symbol, but the ”CH3” on the bottom right shows a strong non-mutagenic effect. The model erroneously learns a 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 is labeled negative, yet its 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 a little more than this”) as positive. But the model can not tell the subjunctive tone behind the word ”if”, and consequently yields a positive but incorrect prediction. The sentence in the second row is negative, and the prediction is 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, it 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 to diagnose the incorrect predictions and enhance the credibility of the model. More visualizations and efficiency study are in Appendix D.

heading: 6 CONCLUSIONS
text: In this work, we present DEGREE which explains a GNN by decomposing its feedforward propagation process. After summarizing the fundamental rules for designing decomposition based explanation, 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 efficiently employs the topological information in graphs. Experimental results show that DEGREE outperforms baselines in terms of faithfulness and can capture meaningful structures in graph data.

heading: A DATASETS AND EXPERIMENTAL SETTING
text: In this section, we introduce the detail of the datasets as wall as the experimental setting. The code can be found at https://anonymous.4open.science/r/DEGREE-3128.
Model setup: We adopt GCN model and GAT model architecture for corresponding experiments. We use GCN(#in channel,#out channel, activation) to denote a GCN layer, and similar notation for GAT layer and fully connected layer.
The structure of GCN model for node classification task is following: GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − FC(20, 20, ReLU)− FC(20,#label, Softmax). For graph classification task, we adopt a Max-pooling layer before the FC layers: GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − GCN(#feature, 20, ReLU) − Maxpooling − FC(20, 20, ReLU)− FC(20,#label, Softmax). For GAT model architecture, we replace all GCN layers with GAT layer and keep the remaining setting unchanged. For experiments on Tree-Grid dataset, we 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 are reported in Table 2.
Experimental setting: For all datasets, we use a train/validation/test split of 80%/10%/10%. 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 30 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 3.
Hardware setting: We introduce the hardware that we use for the experiments.
CPU: AMD EPYC 7282 16-Core Processor.
GPU: GeForce RTX 3090 NVIDIA-SMI: 460.32.03 Driver Version: 460.32.03 CUDA Version: 11.2.

heading: B ALGORITHM
text: We conclude the computation steps of subgraph-level explanation (Sec 4) in Algorithm 1, 2 and 3.
Algorithm 1: The algorithm of subgraph agglomeration Data: Graph G = (V, E), Label y, Target model f , Hyperparameter q. Result: Explanation tree T . Score Metric Function: φ from Algorithm 3. Initialization: score queue ScoresQ← ∅, explanation tree T ← ∅. for v ∈ V do
ScoresQ.add ( {v}, priority = φ(f, y, {v}) ) end while ScoresQ is not empty do
Select Base Subgraph Set B = ScoresQ.top(q) T.add(B) ScoresQ← ∅ for Bm ∈ B do
Candidate Subgroup Set C = Get Candidate(G, Bm) with Algorithm 2 for c ∈ C do
ScoresQ.add(c, priority = φ(f, y, c)− φ(f, y,Bm)) end
end ScoresQ = |ScoresQ− E(ScoresQ)|
end return T
Algorithm 2: The algorithm of candidate node set selection Data: Graph G = (V, E),Subgraph Bm. Result: Candidate Subgraph Set C. C ← ∅ Neighbour nodes N ← {n̄|e =< n, n̄ >, e ∈ E , n ∈ Bm, n̄ ∈ V \ Bm} for v ∈ N do C.add(Bm ∪ {v}) end return C
Algorithm 3: The algorithm of score computation φ Data: Graph G = (V, E), model f , NodeSet N Result: score φ(f, y,N ) Sample a context set S by Random Walk within the L-hop neighbor region of N . Return: φ(fD, y,N ) = 1|S| ∑ s∈S(f(N ∪ s)− f(s))

heading: C EFFICIENCY STUDY
text: DEGREE is achieved by decomposing the feedforward process of the target model. Thus the efficiency is highly dependent on the model structure. We report the statistic of time consuming on each dataset for GCN and GAT model in Table 4.
We quantified the relationship between the size of the calculation graph and the time taken. The result is reported in Figure 4

heading: D QUALITATIVE EXPERIMENTS EXAMPLES
text: 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 of 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.

heading: E ADDITIONAL EXPERIMENTS FOR REBUTTAL
text: E.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 Sec 5.2.2. Note that we modify our method to search only for nodes that boost the score of the class of interest. We employ the ACC Liang et al. (2020) as an evaluation metric. The ACC reflects the consistency of predictions based on the whole graph and between interpreted subgraphs. Thus, ACC does not require ground truth label. We further define the sparsity as the ratio of the size of the explanation subgraph to the original graph. At the same sparsity, the higher the ACC, the better the interpretation. Figure 8 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.
E.2 QUALITATIVE COMPARISON
In this section we make a qualitative comparison between DEGREE and SubgraphX. We randomly select a number of similar molecules and visualize the explanations generated by DEGREE and SubgraphX. We report them in the Figure 9. We can find that none of the subgraphs generated by SubgraphX include the ’N-H’ or ’N-O’. They only select the carbon ring as the important part. In contrast, DEGREE can precisely indicate that the mutagenicity is caused by the ’N-H’ or ’N-O’.
E.3 FORWARD-LOOKING EXPERIMENT
In this section, we present a 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 a node at random in each graph, giving it a special feature value of 1 while giving the other nodes a background white noise feature. Our task is to predict whether a graph contains special nodes or not. We 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 10 shows the visualisation.

Review summaries:
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.   

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.

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. 

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.