STExplainer: Global Explainability of GNNs via Frequent SubTree Mining

We would like to express our concern regarding the validity of this review, as the weaknesses raised by the reviewer appear to primarily stem from misunderstandings. To clarify these points, we provide an explanation of our design in response to each of the mentioned weaknesses.

W1: There is a misunderstanding here. After selecting the Top-M subtrees, our method exclusively works with these M subtrees, eliminating the need to access all graph instances repeatedly. The information about whether two subtrees are in the same data instance is obtained during the initial access to the data instances. Therefore, there is no redundant access to all graph instances, showcasing the efficiency of our design. This highlights that the method's complexity is not amplified, reinforcing the effectiveness of our approach in utilizing subtrees instead of subgraphs or data instances.

W2: We would like to clarify a potential misunderstanding. $L$ is NOT a hyperparameter of our approach but represents the number of GNN layers, as mentioned in our paper. That is, when dealing with a pretrained $L$-layer GNN, we need to consider $L$-hop subtrees, where $L$ is fixed and is the same as the number of layers in the GNN in question. Altering $L$ can impact the performance of the original GNN in question. Therefore, changing $L$ wouldn't lead to a fair experiment for evaluating our explainer's performance.

W3: The main goal of our paper is to provide understandable global-level GNN explanations for humans, not to tackle the broader challenge of neural network interpretability. We use the MLP to learn the importance of candidate subtrees constructed based on their frequency, and this importance helps explain the GNNs. It's important to note that MLP is not mandatory; we could learn the importance of subtrees as learnable weights. We used an MLP because it allows us to potentially consider more detailed information, such as subtree embeddings, while learning the scores. Additionally, many recent works in local-level GNN explainability, a parallel research domain, use MLPs for generating explanations on data instances [1,2,3]. Therefore, we believe that using an MLP to learn scores is not a major issue.

[1] Mohit Bajaj, Lingyang Chu, Zi Yu Xue, Jian Pei, Lanjun Wang, Peter Cho-Ho Lam, and Yong Zhang. Robust counterfactual explanations on graph neural networks. Advances in Neural Information Processing Systems, 34:5644–5655, 2021.

[2] Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33:19620–19631, 2020.

[3] Yaochen Xie, Sumeet Katariya, Xianfeng Tang, Edward Huang, Nikhil Rao, Karthik Subbian, and Shuiwang Ji. Task-agnostic graph explanations. Advances in Neural Information Processing Systems, 35:12027–12039, 2022.

W4: The reviewer's interpretation for Figure 4 might be misleading. First, the figure only displays results for the top frequent subtrees. We do not have information on any “infrequent” subtrees. Only the results for top frequent subtrees are shown. Second, as we discussed in Section 5, Figure 4 illustrates that, despite some variance across runs, the results on all the datasets coverage as T increases. The variance stems from rerunning the model for different runs. Importantly, this figure and the corresponding experiments aim to choose the hyperparameter T on various datasets. It demonstrates that BA-2motifs and BAMultiShapes datasets require fewer subtrees compared to Mutagenicity and NCI1, aligning with our expectations as real-world datasets are more complex and contain more substructure types.

W5: Isomorphic subtrees will not have differing importance scores because we employ GNNs to identify subtrees, rather than manually selecting them. GNNs will always ensure that isomorphic subtrees yield identical embeddings. Consequently, the scores computed from these identical subtree embeddings would be the same.

We hope our explanations resolve your misunderstandings toward this work. We would appreciate it if the reviewer can reassess the quality of this work based on the research question it is addressing, its technical novelty as well as the outstanding performance in comparison to SOTA methods.

W1: Due to space limitations, we had moved more details about the experiments to Appendix A.1~A.6.

Q1: We have evaluated the Fidelity in accuracy in Section 5. As we defined in Section 5.2. The Fidelity metric in our paper, represents the percentage of prediction matching with the original graphs when only the explanation patterns are used to make prediction, for the instances covered by the global explanations. This metric is called “accuracy” in some literature. But to be consistent with the common terminology in this domain [1], we called it “Fidelity” in our paper.

[1] Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5): 5782–5799, 2022.

Q2: The main focus of our approach is to provide higher quality global-level explanations for GNNs. That is, we provide global explanations in a different form from the previous approaches, where our explanations are more intuitive and human-understandable graph concepts, and can potentially be easier to use in the downstream analysis (e.g. constructing building blocks), while the existing approaches provide either the latent representations or the human-defined rules as explanations (see Figure 2 and Figure 9). The empirical results demonstrate that our method provides significantly higher quality global explanations than the existing methods as also mentioned by Reviewer GgEn. Moreover, an advantage of our method is that we can quantitatively evaluate it by removing subgraphs from the original graph data. In contrast, existing methods provide either latent representations or human-defined rules, making such removal infeasible. As a result, these existing methods didn't conduct quantitative comparisons with any baseline in their own paper. Although we couldn't provide a quantitative comparison with them, we quantitatively assessed our approach using widely accepted metrics like Fidelity and Infidelity, as shown in Table 1. The high quantitative performance indicates that STExplainer effectively extracts global explanations aligning closely with the original GNNs’ behavior.

Thank you very much for the detailed review.

W2&Q1: As we discussed in the paragraph of “Intersections of the subgraph patterns in the same cluster” in Section 4.2, after we “sample S subgraphs” and before we “average to obtain a representative subgraph for the cluster”, we perform subgraph matching on the S subgraphs, ultimately yielding the intersection of these S subgraphs. The intersection is not necessarily one of the S subgraphs, but likely a new one, hence it can be better represented by the mean of the corresponding S subgraphs in comparison with a prototype in them.

W3: We provide global explanations in a different form from the previous approaches, where our explanations are more intuitive and human-understandable graph concepts, while the existing approaches provide either the latent representations of clusters or the human-defined rules as explanations (see Figure 2 and Figure 9). It's not that existing approaches sometimes fail to give intuitive global graph concepts; rather, they cannot provide them at all. We hope our work can help the community to give more attention to the global graph explanations because of their intuitiveness and potential for further analysis (e.g. constructing building blocks). Additionally, the existing works conducted experiments on 3~4 datasets, such as GLGExplainer on 3 datasets and GCNeuron on 4 datasets. Therefore, we believe demonstrating the effectiveness of our approach with 4 datasets is sufficient in comparison.

W1&Q2&Q3: We understand the reviewer's concern regarding hyperparameter settings and would like to provide clarification. Regarding $\tau$ and $k$-cluster, we would like to clarify that we did not fix $k=40$, but only let $k_{max}=40$, where $k_{max}$ is an argument to reproduce the results in this paper using our code, meaning that a maximum of 40 clusters is allowed. In our implementation, the exact number of clusters used for each dataset is dynamically determined. We have updated the manuscript by reporting the exact number of $k$ in the appendix (highlighted in red). For $\tau$, typically we want $\tau$ to be small, such that we are able to find the intersections on the S subgraphs in each cluster. As discussed in Section 4, we would discard a cluster in cases no common subgraphs are found in the cluster. We chose $\tau=2$ for the datasets since we find that we only need to discard a small ratio of clusters when $\tau \leq 2$. The choice of $\lambda$ is set to $\lambda=0.1$ as it is relatively more stable in achieving high performance. With other settings of $\lambda$, our method is still able to achieve high performance, which further demonstrates the robustness of our proposed pipeline. We updated the manuscript by the experiments for choosing $\tau$ and $\lambda$ in Appendix A.6. Regarding $T$, our choice is explained in Section 5.3 with Figure 4. The figure illustrates that BA-2motifs and BAMultiShapes datasets require fewer subtrees compared to Mutagenicity and NCI1. This aligns with expectations since real-world datasets are more complex and contain more types of substructures.

Q4: Thanks a lot for pointing out the typos, we have updated the manuscript accordingly (highlighted in red).

We hope our explanations and additional experiments resolve your concerns. Your response would be deeply appreciated.

W1: We want to highlight the novelty of our approach in two key aspects. First, our focus is on delivering higher-quality global explanations for GNNs in the form of graph concepts. In this realm, there are only a few existing works, which are GCExplainer, GLGExplainer, and GCNeuron. As detailed in Section 2, these methods aren't surrogate models, and the global explanations they generate are either less intuitive latent clusters or human-defined rules (see Figure 2 and Figure 9). In contrast, our method offers graph concepts as explanations, which are more intuitive and human-understandable, as highlighted by Reviewer GgEn. These concepts are also easier to use for further analysis compared to conventional approaches, such as constructing building blocks. Second, we introduce a novel approach by utilizing subtrees instead of enumerating subgraphs. This significantly reduces search complexity and has been recognized as "novel" and "a step in the right direction for global explanations of GNNs" by Reviewer GgEn. We learn the importance of subtrees across the entire dataset at a high level, without constructing a surrogate model to mimic GNN behavior on local instances. Our empirical results validate the effectiveness of this novel approach. In summary, we propose to extract global explanations with subtrees which are novel to this domain, producing intuitive global graph concepts that existing methods cannot provide.

W2&Q1: As we discussed in the response to W1, we provide global explanations in a different form from the previous approaches. We offer more intuitive and human-understandable graph concepts, while existing approaches typically present either latent representations or human-defined rules as explanations (refer to Figure 2 and Figure 9). An advantage of our method is that we can quantitatively evaluate it by removing subgraphs from the original graph data. In contrast, for existing methods, which provide latent representations or human-defined rules, such removal is not feasible, making quantitative comparisons challenging. These existing methods also didn't conduct quantitative comparisons with any baselines. Although we couldn't provide a quantitative comparison, we quantitatively assessed our approach using widely accepted metrics like Fidelity and Infidelity, as shown in Table 1. The high quantitative performance indicates that STExplainer effectively extracts global explanations aligning closely with the original GNNs’ behavior. Beyond the advantage of intuitiveness, STExplainer's ability to extract clear global-level graph concepts opens up possibilities for applications like constructing building blocks in tasks such as graph design. Additionally, the global explanation obtained by our approach can potentially be used to construct supernodes, offering opportunities to enhance network performance.

W3: Thank you for the advice. Figure 3 contains scatter plots of the global subtree explanations and the original graphs. In the plots of the global subtree explanations, the radius of each marker indicates the number of data samples each subtree covers. The larger a marker is, the more data samples it covers. While the scatter plots of the original graphs in different classes are largely overlapped, the plots of the subtrees in various classes are distanced from each other, clearly representing different concepts. This demonstrates the significance of our approach in producing clear subtree concepts. We have added this note to the caption of Figure 3 (highlighted in blue).