The Intelligible and Effective Graph Neural Additive Network

We thank the reviewer for the thoughtful comments and encouraging remarks.

Weakness 1:

The reviewer mentions that no hyper-parameters were tuned. We did tune the hyper-parameters, and the grid of hyper-parameters is presented in Appendix D3 and referred to in line 252.

Weakness 2:

The reviewer suggests testing the interpretability of GNAN. GAMs are considered explainable models [1,2]. The explanations they provide make the model transparent in the sense that the way the model makes its predictions is humanly comprehensible. However, it is important to distinguish between explaining the model and explaining the underlying data, which often requires causal analysis [3].
While the model may have some inductive biases, the visualization makes the model transparent to users, allowing them to scrutinize and adjust it if needed. Performing a usability study to check the interpretability of the solution is a great idea but is beyond the scope of this study.

Weakness 3:

The reviewer asks about the intelligibility of GNAN and refers to a paper that extends NAMs to a stronger neural architecture and proposes methods to extend the intelligibility of NAMs. We thank the reviewer for the suggestion showing that there is great potential for further research in this field. Regarding intelligibility, as GNAN is an instance of GAMs, it is intelligible in the same sense that GAMs are.

Weakness 4:

The reviewer mentions that MLPs are outdated with respect to the NAMs literature and referred to newer approaches. We thank the reviewer for these references. GNAN is the first extension of GAMs to graphs, and we decided to utilize the commonly used MLPs. The fact that there is potential for improving GNAN even further presents a great future research direction.
We demonstrated that even with MLPs, GNAN is on par with black-box GNNs while providing full interpretability. We will make sure to refer to these studies and the future research direction in our camera-ready version.

Weakness 5 minors:

The reviewer suggests improving the introduction of GNAN. We appreciate this comment and we will improve it in the camera-ready version.

Weakness 6 minors:

The reviewer suggests improving the appendix. We appreciate this comment and we will improve it in the camera-ready version.

Question 1:

The reviewer asks how GNAN outperforms fully connected networks despite its limited capacity. We would greatly appreciate it if the reviewer could clarify what they mean by “fully connected networks” in the context of graph networks.
We compare GNAN to methods that are not restricted in the same way GNAN is, including sparse graph transformers [4]. The empirical evidence reported in this paper shows that GNAN is mostly on par with these methods and sometimes even outperforms them.

Question 2:

The reviewer asks why different hyperparameters are selected for different models if no hyperparameter tuning was performed. We wish to reiterate our response to Weakness 1: we did tune hyperparameters in a standard fashion as described in Appendix D3.

Question 3:

The reviewer suggests replacing MLPs with other newer networks. Please see our response to Weakness 4.

Question 4:

The reviewer asks what the parameters in GNAN are. If the reviewer is referring to hyperparameters, these are listed in Appendix D3.

[1]Interpretability, then what? editing machine learning models to reflect human knowledge and values, Chang et al, 2021.
[2]How interpretable and trustworthy are gams, Wang et al, 2021.
[3] True to the model or true to the data? Chen, H., Janizek, J. D., Lundberg, S., & Lee, S. I., 2020.
[4] Masked label prediction: Unified message passing model for semi-supervised classification, Shi et al, IJCAI 2021.

We thank the reviewer for the comments and additional questions.

1. The reviewer suggests adding information on the number of trials conducted for each model. We thank the reviewer for the suggestion. This information is provided in lines 272-276 in the main paper.

2. The reviewer raises a valid point that “traditional GAMs” can be fitted with confidence intervals and thus support hypothesis testing, whereas NAMs do not possess this capability. Since GNAN is an adaptation of NAM, it prioritizes interpretability but does not inherently support hypothesis testing without additional methods, such as bootstrapping. This is an important observation, and we will clarify this in the camera-ready version of the paper. However, we would like to emphasize that our primary claim is that GNAM makes the model interpretable, rather than providing an explanation of the data itself. As highlighted in [1], these are distinct concepts. For this reason, we do not claim that GNAN reproduces any underlying structure of the data, nor do we compare it to such structures. Instead, GNAN is transparent in its decision-making process, making it valuable for debugging models, identifying biases, and gauging whether the model is trustworthy. We do not claim that it can be used, in its current form, for causal analysis. To prevent any ambiguity, we will explicitly mention this in the camera-ready version.

3. Regarding the comment that “the paper simply displays some graphics of GNAMs’ predictions,” we would like to clarify that the plots presented in the paper are representations of the model itself, not just “graphics of its predictions.”
   The predictions made by the model for any point can be directly computed from these graphs without requiring any additional information. To the best of our knowledge, no post-hoc method shares this property. Post-hoc models provide explanations of a model’s behavior, but they do not make the model as transparent as GNAN does. In terms of accuracy, post-hoc methods inherit the accuracy of the underlying predictive model they explain, such as GIN. Our experiments demonstrate that GNAN is comparable in accuracy to these models while also offering interpretability.
   
   These surprising high accuracies were acknowledged by the reviewer since the additive constraint in GNAM did not lead to a reduction in performance. We hypothesize that this reflects some underlying properties of common graph learning tasks, as was noted by previous works [2,3,4] and discussed lines 283-288.

[1] True to the model or true to the data? Chen, H., Janizek, J. D., Lundberg, S., & Lee, S. I., 2020.
[2] Simplifying Graph Convolutional Networks, Wu et al, 2019.
[3] A Fair Comparison of Graph Neural Networks for Graph Classification, Errica et al, 2022.
[4] Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs, Yang et al, 2023.

We thank the reviewer for the thoughtful comments and encouraging remarks.

Weakness 1:

The reviewer suggests improving the presentation of formulas in the methods section. We thank the reviewer for this suggestion, and we use it to improve the camera-ready version.

Weakness 2:

The reviewer mentions that calculating shortest paths between any two nodes can be costly for large graphs. This is indeed true, but this limitation is not unique to GNAN, and remedies for this problem exist.
First, note that pre-computing the shortest paths between nodes is a common practice in the GNN literature as a way of improving the expressive power of the model. For example, in the shortest-path GNN [1], the authors apply message-passing over shortest paths in graphs. In [2], the shortest path length is used as a positional encoding for the graph transformer. These approaches inspired us to utilize shortest-path information to incorporate the graph into the GAMs framework.
Second, in cases where the cost of computing all shortest paths is prohibitive, a natural remedy is to clip distances greater than a threshold D. This can be used in many scenarios as it makes sense that remote nodes should have a small influence on each other.
Importantly, the distance computation is only required once, and the determined neighborhoods can subsequently be reused at no additional cost. Hence, in some cases, this cost can be amortized over multiple runs on the same graph or executed as a preprocessing step that does not affect the online running time of the model.
We demonstrate in the paper several applications to tasks where graph sizes allow the computation of shortest paths. Additionally, we wish to note that GNAN is the first approach to extend GAMs into graph learning, and we believe it opens up many new directions for future research, including finding more efficient methods.

Weakness 3:

The reviewer claims that using only node-level information may not be sufficient to replace subgraph-level explanation schemes and that further analysis is required on that matter. We thank the reviewer for this important note. It is true that there may be cases where subgraph-level information is crucial for accurate predictions. Surprisingly, this was not the case in the many datasets we experimented with.
Moreover, it is important to note that existing subgraph-level explanations are post-hoc explanations used with black-box GNNs. In contrast, GNAN is an inherently interpretable white-box model rather than a post-hoc explanation. As discussed in the paper in detail in lines 31-44 and 114-125, post-hoc explanations over black-box models are not suitable for high-stake applications where transparency is crucial, such as in healthcare and criminal justice. Therefore, while post-hoc subgraph explanations may be useful in some cases, they are not suitable in many domains. We claim that GNAN may serve this unmet need as it provides full transparency for decision-makers in such applications.

[1] Shortest Path Networks for Graph Property Prediction, Abboud wt al. LOG 2022.
[2] GRPE: RELATIVE POSITIONAL ENCODING FOR GRAPH TRANSFORMER, Park et al. ICLR 2022.

We thank the reviewer for the thoughtful comments and encouraging remarks.

Weakness 1:

The reviewer claims that GNAN is a special type of transformer and asked for clarifications in Question 1. We think there might be some confusion here that we are happy to clarify. We do not see GNAN as an instance of a transformer.
The fundamental idea in GNAN is that each feature is processed separately by the network using a univariate shape function. The values computed by these shape functions are sum-pooled only in the last layer. This is in contrast to transformers, where each layer may compute functions that mix arbitrary numbers of features. GNANs also restrict the way distance and features interact, which allows for their interpretability.
While it is true that both GNANs and transformers allow information propagation between any pair of nodes, they are considerably different, as evidenced by the interpretability of GNANs compared to the black-box nature of transformers.

Weakness 2:

The reviewer commented that GNAN does not outperform other baselines. We would like to emphasize that the main goal of GNAN is to provide interpretable model for graph learning. The interpretability requirement restricts the type of models that can be used but surprisingly, we show that in many settings, there is no tradeoff between explainability and accuracy since GNAN is comparable to the commonly used (non-explainable) models, and in some cases, it is even better. As we mentioned in the paper, e.g., line 284, this is non-trivial as it is usually assumed that interpretability comes at the cost of accuracy. Second, we note that GNAN did outperform the tested baselines on the Tolokers, ogb-arxive, and alpha, mu, and alpha-homo tasks.

Weakness 3:

The reviewer asks how debugging is done. We thank the reviewer for the question. GAMs, including GNAN, allow for debugging and adjustment of the model in several ways. As mentioned in lines 210-215, because GNAN is transparent and can be fully visualized, this allows for several debugging methods.
One example given in lines 210-215 suggests using the visualizations of the model for model selection. Specifically, one can select models not only based on accuracy but also based on their alignment with prior knowledge.
The visualizations of GAMs also enable debugging biases in the model, which can be addressed in different ways [1, 2, 3].
Additionally, the ability to visualize exactly what the model has learned and observe whether it "makes sense" can help detect code bugs. For instance, we used this property to hunt bugs during the development of the model.

[1] Interpretability, then what? editing machine learning models to reflect human knowledge and values, Wang et al., 2021.
[2] How interpretable and trustworthy are gams, Chang et a.l, 2021.
[3] Gam changer: Editing generalized additive models with interactive visualization, Wang et al. 2021.

Question 1:

The reviewer asks how GNAN is different from a transformer. This is addressed in Weakness 2

Question 2:

The reviewer asks how the visualization of GNAN can be used for debugging. This is addressed in Weakness 3.

We are gratified by the reviewer’s appreciation of the novelty and interest of our work and thank the reviewer for the valuable feedback.

Weakness 1:

The reviewer claims it could be problematic to apply GNAN to large graphs with many features and asks for methods to prune the space as a pre-processing step. We thank the reviewer for the question.
One approach is to clip distances greater than a predefined threshold. One can also mask distances using other rules rather than one threshold. If needed, there are also many methods for reducing the graph size in advance [1, 2].
We also note that GNAN is implemented in a tensor-multiplication formulation as described in Appendix A, which is therefore optimized when using GPUs.
Regarding the cases where the number of features is large, any feature-selection method, e.g., variance-threshold or univariate feature selection, can be applied as a pre-processing step to reduce the number of features. We also addressed the case of limiting the number of feature visualizations in our answer to Question 3.

[1] On the Ability of Graph Neural Networks to Model Interactions Between Vertices, Razin et al.,ICML 2023.
[2] DropEdge: Towards Deep Graph Convolutional Networks on Node Classification, Rong et al., ICLR 2020.

Question 1:

The reviewer asks how sensitive are the explanations of GNAN to initializations. We thank the reviewer for this important question as it allows us to clarify important aspects of our proposed algorithm. \ In the literature about explainability, there is a distinction between explaining the model and explaining the data [3]. The explanations in GNAN are explanations of the model. Regardless of the initialization, the explanation will always describe precisely the model. Therefore, the sensitivity of explanations would simply visualize the model’s sensitivity to initializations.
Nonetheless, following the reviewer’s question, we visualized the heatmap of the mutagenicity experiment using a GNAN trained with 3 different seeds. The heatmaps are attached in the PDF file allowed in the global comment. The values in the heatmap slightly differ, but the trend is stable.

[3] Chen, H., Janizek, J. D., Lundberg, S., & Lee, S. I. (2020). True to the model or true to the data?. arXiv preprint arXiv:2006.16234.

Question 2:

The reviewer asks for a concrete example of a local explanation corresponding to a query node in node classification. We thank the reviewer for the opportunity to address this topic. Given a query graph and node, we highlight other nodes in the graph in a way that corresponds to their contribution to the query node’s prediction based on the learned distance and feature functions. For example, if we observe from the visualization that neighbors of distance x with feature k contribute towards positive labels, we can highlight such nodes in the given query graph, and the distances are computed with respect to the query node. We will make sure to add such examples to the camera-ready version.

Question 3:

The reviewer asks how to conclude which features to inspect in the case of large feature spaces. We thank the reviewer for this important question.
This is a fundamental problem in explainability that is common to many methods. Even a linear model or a tree may lack human interpretability in the context of a large feature space. A plausible method to mitigate the problem is to use regularization terms to induce sparsity in the use of features or use feature selection. \ Another approach is to use a post-processing step of removing the contribution of features for which the shape-function has low variance.
Additionally, in some cases, users have pre-defined features of interest to examine. For example, doctors may be interested in observing the effect of specific genes.
We will add this important discussion to the camera-ready version.