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.
abstractText: 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.
references.authors: Federico Baldassarre Hossein Azizpour
references.title: Explainability techniques for graph convolutional networks, 2019
references.authors: Albert-László Barabási Réka Albert
references.title: Emergence of scaling in random
references.venue: networks. science,
references.authors: Lei Cai Shuiwang Ji
references.title: A multi-scale approach for graph link prediction
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Sergio Casas Cole Gulino Renjie Liao Raquel Urtasun
references.title: Spatially-aware graph neural networks for relational behavior forecasting from sensor data
references.authors: Chun-Hao Chang Elliot Creager Anna Goldenberg David Duvenaud
references.title: Explaining image classifiers by counterfactual generation
references.venue: arXiv preprint arXiv:1807.08024,
references.authors: Asim Kumar Debnath Rosa L Lopez de Compadre Gargi Debnath Alan J Shusterman Corwin Hansch
references.title: Structure-activity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity
references.venue: Journal of medicinal chemistry,
references.authors: Jacob Devlin Ming-Wei Chang Kenton Lee Kristina Toutanova
references.title: Bert: Pre-training of deep bidirectional transformers for language understanding, 2019
references.authors: Mengnan Du Ninghao Liu Xia Hu
references.title: Techniques for interpretable machine learning
references.venue: Communications of the ACM,
references.authors: Wenqi Fan Yao Ma Qing Li Yuan He Eric Zhao Jiliang Tang Dawei Yin
references.title: Graph neural networks for social recommendation
references.venue: In The World Wide Web Conference,
references.authors: Mikael Henaff Joan Bruna Yann LeCun
references.title: Deep convolutional networks on graph-structured data
references.venue: arXiv preprint arXiv:1506.05163,
references.authors: Qiang Huang Makoto Yamada Yuan Tian Dinesh Singh Dawei Yin Yi Chang
references.title: Graphlime: Local interpretable model explanations for graph neural networks
references.venue: arXiv preprint arXiv:2001.06216,
references.authors: Eric Jang Shixiang Gu Ben Poole
references.title: Categorical reparameterization with gumbel-softmax, 2017
references.authors: Thomas N Kipf Max Welling
references.title: Semi-supervised classification with graph convolutional networks
references.venue: arXiv preprint arXiv:1609.02907,
references.authors: Jian Liang Bing Bai Yuren Cao Kun Bai Fei Wang
references.title: Adversarial infidelity learning for model interpretation
references.venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Cheng-Hao Liu Maksym Korablyov Stanisław Jastrzebski Paweł Włodarczyk-Pruszyński Yoshua Bengio Marwin HS Segler
references.title: Retrognn: Approximating retrosynthesis by graph neural networks for de novo drug design
references.authors: 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 Shuiwang Ji
references.title: DIG: A turnkey library for diving into graph deep learning research
references.venue: arXiv preprint arXiv:2103.12608,
references.authors: Ninghao Liu Qiaoyu Tan Yuening Li Hongxia Yang Jingren Zhou Xia Hu
references.title: Is a single vector enough? exploring node polysemy for network embedding
references.venue: In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Ana Lucic Maartje ter Hoeve Gabriele Tolomei Maarten de Rijke Fabrizio Silvestri
references.title: Cfgnnexplainer: Counterfactual explanations for graph neural networks, 2021
references.authors: Scott Lundberg Su-In Lee
references.title: A unified approach to interpreting model predictions, 2017
references.authors: Dongsheng Luo Wei Cheng Dongkuan Xu Wenchao Yu Bo Zong Haifeng Chen Xiang Zhang
references.title: Parameterized explainer for graph neural network
references.venue: arXiv preprint arXiv:2011.04573,
references.authors: W James Murdoch Arthur Szlam
references.title: Automatic rule extraction from long short term memory networks
references.venue: arXiv preprint arXiv:1702.02540,
references.authors: W James Murdoch Peter J Liu Bin Yu
references.title: Beyond word importance: Contextual decomposition to extract interactions from lstms
references.venue: arXiv preprint arXiv:1801.05453,
references.authors: Phillip E Pope Soheil Kolouri Mohammad Rostami Charles E Martin Heiko Hoffmann
references.title: Explainability methods for graph convolutional neural networks
references.venue: In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition,
references.authors: Cynthia Rudin
references.title: Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead
references.venue: Nature Machine Intelligence,
references.authors: Thomas Schnake Oliver Eberle Jonas Lederer Shinichi Nakajima Kristof T. Schütt Klaus-Robert Müller Grégoire Montavon
references.title: Higher-order explanations of graph neural networks via relevant walks, 2020
references.authors: Robert Schwarzenberg Marc Hübner David Harbecke Christoph Alt Leonhard Hennig
references.title: Layerwise relevance visualization in convolutional text graph classifiers, 2019
references.authors: Avanti Shrikumar Peyton Greenside Anshul Kundaje
references.title: Learning important features through propagating activation differences
references.venue: In International Conference on Machine Learning,
references.authors: Karen Simonyan Andrea Vedaldi Andrew Zisserman
references.title: Deep inside convolutional networks: Visualising image classification models and saliency maps
references.venue: arXiv preprint arXiv:1312.6034,
references.authors: Chandan Singh W James Murdoch Bin Yu
references.title: Hierarchical interpretations for neural network predictions
references.venue: arXiv preprint arXiv:1806.05337,
references.authors: Mukund Sundararajan Ankur Taly Qiqi Yan
references.title: Axiomatic attribution for deep networks
references.venue: In International Conference on Machine Learning,
references.authors: Minh N Vu My T Thai
references.title: Pgm-explainer: Probabilistic graphical model explanations for graph neural networks
references.venue: arXiv preprint arXiv:2010.05788,
references.authors: Xiang Wang Yingxin Wu An Zhang Xiangnan He Tat seng Chua
references.title: Causal screening to interpret graph neural networks, 2021
references.venue: URL https://openreview.net/forum?id= nzKv5vxZfge
references.authors: Keyulu Xu Weihua Hu Jure Leskovec Stefanie Jegelka
references.title: How powerful are graph neural networks
references.venue: arXiv preprint arXiv:1810.00826,
references.authors: Rex Ying Dylan Bourgeois Jiaxuan You Marinka Zitnik Jure Leskovec
references.title: Gnnexplainer: Generating explanations for graph neural networks
references.venue: Advances in neural information processing systems,
references.authors: Hao Yuan Jiliang Tang Xia Hu Shuiwang Ji
references.title: Xgnn: Towards model-level explanations of graph neural networks
references.venue: In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining,
references.authors: Hao Yuan Haiyang Yu Jie Wang Kang Li Shuiwang Ji
references.title: On explainability of graph neural networks via subgraph explorations
references.venue: arXiv preprint arXiv:2102.05152,
references.authors: Muhan Zhang Yixin Chen
references.title: Link prediction based on graph neural networks
references.venue: arXiv preprint arXiv:1802.09691,
references.authors: Muhan Zhang Zhicheng Cui Marion Neumann Yixin Chen
references.title: An end-to-end deep learning architecture for graph classification
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Jie Zhou Ganqu Cui Zhengyan Zhang Cheng Yang Zhiyuan Liu Lifeng Wang Changcheng Li Maosong Sun
references.title: Graph neural networks: A review of methods and applications
references.venue: arXiv preprint arXiv:1812.08434,
references.authors: Schnake
references.title: 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
references.venue: We employ the ACC Liang et al
sections.heading: 1 INTRODUCTION
sections.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.
sections.heading: 2 RELATED WORK
sections.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.
sections.heading: 3 DEGREE: DECOMPOSITION BASED EXPLANATION FOR GNNS
sections.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
sections.heading: 3.1 PROBLEM DEFINITION
sections.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.
sections.heading: 3.2 DECOMPOSITION BASED EXPLANATION
sections.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).
sections.heading: 3.3 INTUITIONS BEHIND DECOMPOSITION BASED EXPLANATION FOR GNN
sections.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?
sections.heading: 3.4 DECOMPOSING GNN LAYERS
sections.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).
sections.heading: 3.4.1 DECOMPOSING GCNS
sections.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.
sections.heading: 3.4.2 DECOMPOSING GATS
sections.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.
sections.heading: 4 SUBGRAPH-LEVEL EXPLANATION VIA AGGLOMERATION
sections.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.
sections.heading: 4.1 CONTEXTUAL CONTRIBUTION SCORE
sections.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.
sections.heading: 4.2 SUBGRAPHS CONSTRUCTION VIA AGGLOMERATION
sections.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.
sections.heading: 5 EXPERIMENTS
sections.heading: 5.1 EXPERIMENTAL DATASETS
sections.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.
sections.heading: 5.1.1 SYNTHETIC DATASETS
sections.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.
sections.heading: 5.1.2 REAL-WORLD DATASETS
sections.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).
sections.heading: 5.2 EXPERIMENTAL SETUP
sections.heading: 5.2.1 EVALUATION METRICS
sections.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.
sections.heading: 5.2.2 BASELINES METHODS AND IMPLEMENTATION DETAILS
sections.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.
sections.heading: 5.3 QUANTITATIVE EVALUATION
sections.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.
sections.heading: 5.4 QUALITATIVE EVALUATION
sections.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.
sections.heading: 6 CONCLUSIONS
sections.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.
sections.heading: A DATASETS AND EXPERIMENTAL SETTING
sections.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.
sections.heading: B ALGORITHM
sections.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))
sections.heading: C EFFICIENCY STUDY
sections.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
sections.heading: D QUALITATIVE EXPERIMENTS EXAMPLES
sections.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.
sections.heading: E ADDITIONAL EXPERIMENTS FOR REBUTTAL
sections.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.
title: DEGREE: DECOMPOSITION BASED EXPLANATION