GOAt: Explaining Graph Neural Networks via Graph Output Attribution

Summary

This paper proposes a novel local-level post-hoc GNN explainer (GOAt) that takes the issue of discriminability and consistency into consideration. The discriminability and consistency of graph explanation are significant and meaningful for the community’s understanding of the GNN decision-process. The GOAt explainer attributes the prediction of the trained GNN to the input graph features, i.e., the node feature matrix and the adjacency matrix, based on the Equal Contribution technique. The authors implement the specific GOAt with regard to GCN, GraphSAGE, and GIN. Sufficient experiments, including both qualitative and quantitative evaluation, verify that GOAt outperforms the SOTA GNN explainers in terms of both fidelity, discriminability, and stability.

Strengths

S1: The issue of discriminability and consistency (i.e., stability) in GNN explanation methods is thought-provoking. However, it is neglected by previous methods. The GOAt explainer bridges the research gap. S2: The mathematical derivation of the equal contribution technique is solid and ingenious, which well support the design of GOAt explainer. S3: The experiments to verify the superiority of GOAt are sufficient and the results are discussed in detail.

Weaknesses

W1: My main concern is about the effectiveness of the attribution strategy based on equal contribution. Though the experimental results have shown it outperformance, the intuitive reason why equal contribution can improve the discriminability and stability of GOAt explanation is still obscure for me. In other words, the motivation behind GOAt is not well-illustrated. W2: The organization and writing of this manuscript need to be improved. Some contents are a little confusing. For example, in line 155, the authors claim that the number of occurrences is not necessarily equal to the number of unique variables. However, the example following does not explain this claim well.

Questions

Q1: If GOAt take the node feature matrix X as constant finally (as stated in line 209), introducing this setup at beginning may be able to accelerate the GOAt inference. Moreover, why not take both node feature and topological structure as explanation, as done in GNNExplainer? See WEAKNESSES for more detailed questions.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors have discussed some limitation about GOAt, including the requirement of expert knowledge, the failure in explaining deep models (e.g., Transformer). In my regard, as a post-hoc explainer, GOAt has to access the detailed architecture of the GNN model to be explained, which may serve as the main limitation in real-world application.

Summary

In this paper, the local explanation algorithm for Graph Neural Networks (GNN), Graph Output Attribution (GOAt), is proposed. The key idea of the algorithm is decomposing the GNN's forward propagation as sum of product form. After decomposing, authors compute the contributions of nodes and edges by proposed measure. Next, (sum of the contribution including the interest node or edge) - (contribution from global bias) becomes the contribution (explanation) of the node or edge. The experiments show (1) the explanation can capture the importance of edges (fidelity, discriminability) (2) the explanation is consistence (Stability).

Strengths

1. The algorithm is general for graph neural networks. 2. The examples help the reader understand the explanations. 3. The experiments show the performance of proposed model with regard to baselines for various criteria.

Weaknesses

1. The paper used zero-vector as base manifold. It makes that the contributions for all variables are always equal. 2. The contribution does not consider the value of variables. 3. It would be better to explain the difference between the baseline algorithms and proposed algorithm.

Questions

1. What is motivation of setting base manifold as zero-vector? It seems to make equal contribution, but I think the other resonable explanation is necessary. 2. When we consider the 3 variables (x1',x2',x3'), the manifolds at (x1,x2,x3) are {(x1,x2',x3'), (x1',x2,x3'), (x1',x2',x3)}? If so, why {(x1,x2,x3'),(x1,x2',x3),...} are not considered like shapley value? 3. In lemma 4, why "when the number of nodes N is large" is necessary? 4. In line 144, the |V(x^2y)|={x,y}, this makes x and y have same contribution for x^2y. It is not reasonable. 5. In line 154, it is hard to understand O(v,z) (the number of occurrences of ν among the variables of z). 6. In line 217, I think it is unfair to compare the proposed edge explanation and the edge explanation from node explanations of baselines by [3]. Because the proposed algorithm can compute the node explanation like baselines, same process [3] should be used for edge explanation from proposed node explanation. 7. In figure 3 (h), the plot seems like there are less points than others. 8. In figure 3, what kinds of algorithms is used for 2D plotting? How the position of green scatter points is consistent for various embeddings? I think the different 2D projections should be used for each embeddings. 9. In line 282, why the figure 3 (h) explains the data samples use only 3 explanation? If 3 explanations used, I think 2^3 points (existence of each explanation) should exist in figure 3. 10. In table 1, there is no motifs for "This indicates that the presence of more carbon rings in a molecule increases its likelihood of being mutagenic (Class 0)" (line 293) and "GOAt discovers that the GNN considers a higher number of carbon rings as evidence of chemical compounds being active against non-small cell lung cancer" (line 296) (minor comment) there is no definition for the j-th feature of i-th node (line 126)

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

2 fair

Limitations

The paper used zero-vector as base manifold. It makes that the contributions for all variables are always equal. Also, the proposed contribution consider absence or presence of variable only without the value of variable.

Summary

It proposes a local GNN explanation method called GOAt by analysing the output attribution of graphs. Specifically, it proposes a novel explanation framework by the notion of equation contribution, which is transparent compared to the existing black-box type explanation models. Experiments on real and simulation data are tested on several metrics, where the results are convincing.

Strengths

1. The point of equation contribution is quite novel and interesting. Especially its transparency compared to current baselines. 2. The experiments are extensive and convincing.

Weaknesses

1. In line 28, it seems that "their effectiveness relies heavily on the quality of local-level explanations" is the main point of abandoning the global style in this paper, could you explain more about this in the rebuttal phase or say more about it in section 2 - see second con below. 2. In section 2, the differences between global and local explanatory methods should be introduced in a proper way to show the superiority of global explanations. Also, please consider including the matrices in lines 66-69 as another subsection to introduce the matrices together.

Questions

1. Major: 1. In lines 103-107, the reasonableness of the independence between the variables $X$ and $A$ in the contribution for $f(A,X)$ should be further improved. As I understand it, the equal contribution property of $f_{i,j}(A,X)=\sum_k\sum_l A_{i,k} X_{k,l} W_{l,j}$ is not identical to $A_{i,k} X_{k,l} W_{l,j}$, because the distribution of $A$ can never be independent of $X$. In line 103 the authors mention that "since $A_{i,k}$ is usually independent of $X_{k,l}$ under proper data cleaning" - this is true, while it is not equal to $\sum_k\sum_l A_{i,k} X_{k,l} W_{l,j}$. 2. Could you please explain more about the reduction of equation (7)? 3. For the proof of Lemma 4 and Theorem 5, what's the use of the condition requiring a large number of nodes? It is highly recommended that the authors make this condition more practical or reanable in real-world cases. 2. Minor: 1. In lemma 2, better include the condition of $x_k \neq 0$; 2. Is the number of variables $|V(z)|$ of equation (8) equal to the number of parameters? 3. I'm also wondering if there is a gap between node-based and edge-based explanation methods, since in the experiments the node-based approaches are aligned with the edge-based ones by using their induced subgraphs. Can the authors explain more about the correct explanation is symmetric in both types of methods, or provide some basic intuition of this? 4. In lines 173-177 the authors mention the property of completeness. A question here is whether in the experiments the top-k edges are still selected to compute the evaluation matrices? 5. Following the idea of matrix-based understanding of GNNs, there is a recent paper you might consider citing: https://arxiv.org/abs/2305.06142 Feature expansion for graph neural networks. J Sun, L Zhang, G Chen, P Xu, K Zhang, and Y Yang. ICML'23. You can use it to extend your framework to more GNN approaches.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

The authors presented the limitations in the Appendix about wider range of model architectures.

Summary

Unlike existing methods that rely on training auxiliary models, the paper introduces a computationally efficient instance-level GNN explanation technique (called GOAt), which enables attribution of GNN output to input features by direct algebraically computation. More specifically, a GNN is represented in an expansion form as a sum of scalar product term, involving input graph features, model parameters, and activation levels. Based on the assumption that all scalar variables in a scalar product term contribute equally to the term, each product term can be attributed to its corresponding factors and thus to input features, which gives the importance of each node or edge feature in the input graph to GNN outputs. Besides that, the paper also introduce two new metrics called discriminability and stability, which assess the ability of explanations to distinguish between classes and the ability to generate consistent explanations across similar data instances, respectively. Through extensive experiments on synthetic and real data, the paper show that GOAt has consistently outperformed various state-of-the-art GNN explainers in terms of fidelity, discriminability, and stability.

Strengths

1. The assumption that all scalar variables in a scalar product term contribute equally to the term is acceptable to me. And the derived lemmas and theorems are well proved and practically applicable. 2. The proposed explanation method is computationally efficient, and does not rely on back-propagation with gradients, hyper-parameters or training complex black-box models, which is novel to me. 3. The work contributes a new attribution method to the field of explaining GNNs (might extend to other types of neural networks, e.g., CNN) .

Weaknesses

1. The specific calculation expression of the attribution process needs to be carefully derived with expert knowledge for different neural network architectures and becomes very complex as the network goes deeper, which greatly limits its widespread use, though it shows superior explanation ability. 2. The main argument that existing methods struggle with issues such as overfitting to noise, insufficient discriminability, and inconsistent explanations across data samples of the same class is not well elaborated. Though the experiments seem to have verified this argument, it will be more motivated if some detailed illustrations (e.g., by presenting a toy example) could be provided in the introduction part.

Questions

1. The assumption that the number of nodes of the input graph is large in the key lemma(Lemma 4) and the theorem(Theorem 5) is not well established in the datasets used in experiments.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

a) Build an algorithm to automatically derive the attribution expressions based on the network architecture. b) Although the experiments seem to corroborate the main argument, bolstering the introduction with some detailed illustrations (for instance, by incorporating a simple, illustrative example) could make the paper more compelling.

Summary

This work studies the problem of GNN local explanation. It points out that existing GNN explainers are suffering from a few limitations including insufficient discriminability, inconsistency on same-class data samples, and overfitting to noise, and the aim to address these limitations by proposing the GOAt method. Given a pre-trained GNN model, GOAt defines a contribution score on each node feature and each edge feature (i.e. values on each edge) by expanding the GNN as a sum of scalar products involving these features, and thus would be able to find the edges that contribute more to the GNN's output. The authors evaluate GOAt with the frequently used fidelity metric, as well as the newly proposed discriminability and stability metric in this paper.

Strengths

1. Results are impressive. 2. Code is provided in the supplementary. 3. The newly introduced discriminability and stability metric for explanation evaluation makes sense to me.

Weaknesses

1. The writing for the method section is not easy to follow. 2. The motivation of why the contribution should be designed in this way is not clearly explained. Why the current design can address the insufficient discriminability, inconsistency on same-class data samples, and overfitting to noise issues also remains unclear to me. Some minor weaknesses: 1. There seems to be one typo in the appendix proof lemma 2: line 11 should be X_j not E_j? 2. The term ``feature`` is used to describe all X_{ij}s and A_{ij}s, which looks a little bit confusing for me. I think usually people use the term ``feature`` to describe the attributes on nodes and edges, but here A_{ij} is more like a weight scaler on edge instead of the edge attributes? I feel it would be clearer to put a note to clarify that the term ``feature`` is used to describe all node attributes and edge weights. 3. It would be clearer if the authors can explain what does each lemma and theorem imply.

Questions

Q1. I am still very confused about, why the contribution should be defined in this way? In other words, what does this formula imply and why it can act as an evaluation of contribution? Q2. Why GOAt can achieve better discriminability? Q3. What is the scope of GNN designs that can be explained by GOAt? (For example, is every GNN model that can be formulated in the form of formula (1) covered in the scope?)

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

2 fair

Contribution

2 fair

Limitations

Please refer to ``weaknesses``.

Thanks for the rebuttal

Thanks to the authors for their detailed responses. The minor concerns are mostly well addressed and the theoretical requirements of a large number of nodes are also noted. However, two questions/suggestions remain. 1. (W1&W2): This paper actually proposes another novel local level explicator equipped with several ideal characters, which global types also require. Thank you for your explanation on this - it is fatal, and I strongly recommend the authors to rearrange the introduction and literature review parts to include this connection to make the motivation clearer. For example, in section 2, talk about global type and make comparisons. 2. (Q 1.1): this is not just a question of terminology, but of the mathematical definition that the whole paper will follow. If the independent feature is not important, you can just omit it; otherwise, make it clear, e.g. that this is a theoretically friendly way and will not affect the empirical results, or give some solid hint that this assumption works. Thanks again for the rebuttal, and I am happy to raise the score to 6. Please the authors take the issue of motivation seriously.

Response to author.

Thank you for your response. These have addressed the majority of my questions. I appreciate the effort and insights the authors put into the paper. I will maintain my original score.