Explaining Hypergraph Neural Networks: From Local Explanations to Global Concepts

We thank the reviewer for their time in leaving such constructive feedback. We would like to address this below.

Related work is not thoroughly reviewed, and more recent studies should be discussed. The limitations of existing approaches for GNN explainability in the context of hyperGNNs are not clearly addressed. Since most existing methods are model-agnostic, they should be able to provide explanations for hyperGNNs too.

Due to the space constraints we only provided a brief summary of the related works, to create a general idea of the field. If the reviewer has a concrete list of studies or related work that they think it is suitable to include, we are happy to take these suggestions into account.

Regarding existing GNN methods, please refer to our overall comment.

The newly introduced datasets are not provided.

In our supplementary material, we included the code for our model, together with the code to generate the synthetic datasets. Upon acceptance, we plan to release publicly both the code and the generated synthetic datasets.

The presentation is not very good. For example, the caption of Fig 2 is confusing.

We are sorry for the potential clarity issues in our work. Section 5.1 Dataset Construction provides helpful context. Figure 2.a and 2.b shows samples of the “base hypergraph” used as the backbone for our datasets. Figure 2.c and 2.d depicts the motifs attached to the base hypergraph to create the dataset. Finally, Figure 2.e depicts a small example of a dataset, containing a random hypergraph as a base, and 2 house-like motifs attached to the base. We would take all the suggestions from the reviewers into account to improve the clarity of the presentation. If the reviewer has any additional questions which might impact the understanding of the method we are happy to address them.

The performance improvements on real world datasets seems minimal.

We would like to push back on the reviewer’s interpretation and argue that our results consistently demonstrate SHypX’s strong outperformance. We acknowledge that on real-world datasets, even simple baselines like gradient do well on the Fid-Acc metric; this motivated our introduction of the generalized fidelity metrics to better discern the differences in explainer quality. There we see significant gains of SHypX. We also highlight on these real datasets, SHypX explanations are smaller than the baselines’, so it is also superior in terms of concision.

Finally, we would like to reiterate that SHypX produces the most faithful and concise explanations across every dataset we tested. In the results of Table 1 and 2, each number is averaged over ~1000 nodes or all of the nodes in the hypergraph, and in Figure 3, we study the performance of all methods across a range of explanation budgets – SHypX’s outperformance is consistent and robust, with its curve clearly beating baselines and demonstrating a smooth faithfulness-concision tradeoff.

The evaluation on the global-level explainability is too few. It doesn't seem that this explainer actually produce global-level explanations.

We provide a series of qualitative results presenting the global concepts discovered by our model. The discovered sub-hypergraphs reflect the label semantics.

For example, in Figure 4, for class 0 which correspond to the nodes that are part of the random hypergraphs (the “base” of the dataset to which we attach the motifs), all the concepts are various random sub-hypergraphs frequently seen in the dataset. Class 1 represents the top of the house, and the concept discovered by our model is exactly a house with the target node on the top. Class 2 represents the middle of the house so the global explanation capture a house with the target node one of the nodes connecting the roof to the main body of the house, while Class 3 represents the bottom of the house so the global explanation discovered by our house extract a fragment of the house, with the target node being one of the nodes that are not part of the “roof”. Additional visualizations are in the supplementary material in Figure 5, Figure 6 and Figure 7.

In addition to these visual evaluations, we also provided the concept completeness score in Table 5 of the Supplementary Material. For all the datasets, our model obtained a high score, demonstrating that the explainer produces accurate global-level explanations. (Concept completeness was introduced in prior work. It quantifies how well we do on the original task of the hyperGNN if the original (i.e. node) features are replaced by the concept label only.)

CONTINUED

Dear Reviewer,

The authors have posted a rebuttal to the concerns raised. Please read the rebuttal and see if this changes your opinion on the work. We have only two days left. Hence, we urgently need your reactions to the rebuttal.

best,

AC

Thanks a lot for the author's rebuttal. My concerns are partially resolved. However, I agree with other reviewer's opinion that the motivation of proposing explainers for HyperGNNs stays unclear. Since GNNExplainer can be utilized to explain HyperGNNs, other GNN explainers should be compared as the baselines too. GNNExplainer is a relatively poor baseline in this domain. Therefore, I would maintain the score. Thanks a lot for your rebuttal. I appreciate it.

We warmly thank the reviewer for their time and questions! We are glad that you appreciate that we are the first to address both local and global explanations for hyperGNNs and regard our manuscript as well-written. We address your points below:

My main concern is that this paper only addresses explainability for the task of node classification in hypergraphs, which is a less interesting and important problem compared to (hyper)graph classification.

We thank the reviewer for their comments. Firstly, we would like to note that one cannot discern node classification more important than hypergraph classification, as it boils down to the task at hand. Many relevant problems, e.g. predictions about an entity in a complex network, are formulated as node classification. Secondly, the techniques we develop and test on node classification can be easily adapted to hypergraph classification as well as regression tasks; we briefly discuss these possibilities in Appendix A. However, we are not aware of any real-world benchmark for hypergraph-level classification. This is largely because hypergraph representation learning is a relatively new and evolving area of research. However, we would be glad to extend our experiments to include hypergraph-level tasks if the reviewer could kindly suggest relevant datasets.

The baselines used in this paper are not sufficient. While there might not be many related works on explainability in hypergraphs, explainability methods for graph neural networks could be applied and compared with the proposed method.

Please refer to our overall comment.

The quantitative evaluation on real-world datasets shows very low performance, and the differences between the various baselines are minimal, making it difficult to determine if the proposed method performs significantly better than the other baselines.

We would like to push back on the reviewer’s interpretation and argue that our results consistently demonstrate SHypX’s strong outperformance. We acknowledge that on real-world datasets, even simple baselines like gradient do well on the Fid-Acc metric; this motivated our introduction of the generalized fidelity metrics to better discern the differences in explainer quality. There we see significant gains of SHypX. We also highlight on these real datasets, SHypX explanations are smaller than the baselines’, so it is also superior in terms of concision.

Finally, we would like to reiterate that SHypX produces the most faithful and concise explanations across every dataset we tested. In the results of Table 1 and 2, each number is averaged over ~1000 nodes or all of the nodes in the hypergraph, and in Figure 3, we study the performance of all methods across a range of explanation budgets – SHypX’s outperformance is consistent and robust, with its curve clearly beating baselines and demonstrating a smooth faithfulness-concision tradeoff.

While having synthetic datasets for an explainability method is crucial, it is not clear how the proposed synthetic datasets are particularly useful in this setting.

Our primary motivation in introducing the synthetic datasets is to produce a challenging and discerning evaluation for hyperGNN explainers (see Section 5.1). Concretely, in creating the datasets, we ensured that the label strongly depends on the structural connectivity of the hypergraph. This way, we make sure that the hypergraph model that we are explaining are models that are forced to actually capture higher-order connectivity. Moreover, we would like to point out that these datasets represent a higher-order version of the pairwise datasets used in the graph explainability community. These datasets constitute a challenging testbed and are widely used for testing graph explainers [1,2,3]. If the reviewer disagrees with some specific reasoning contained there, we would appreciate a more specific pointer.

[1] Ying, Zhitao, et al. "Gnnexplainer: Generating explanations for graph neural networks." Advances in neural information processing systems 32 (2019).

[2] Vu, Minh, and My T. Thai. "Pgm-explainer: Probabilistic graphical model explanations for graph neural networks." Advances in neural information processing systems 33 (2020): 12225-12235.

[3] Yuan, Hao, et al. "On explainability of graph neural networks via subgraph explorations." International conference on machine learning. PMLR, 2021.

[4] Magister, Lucie Charlotte, et al. "Gcexplainer: Human-in-the-loop concept-based explanations for graph neural networks." arXiv preprint arXiv:2107.11889 (2021).

[5] Magister, Lucie Charlotte, et al. "Concept distillation in graph neural networks." World Conference on Explainable Artificial Intelligence. Cham: Springer Nature Switzerland, 2023.

CONTINUED

We warmly thank the reviewer for their thoughtful comments, for valuing our work as a significant contribution to hypergraph machine learning explainability, and for appreciating our multiple novel contributions in tackling both local and global explanations, sampling for hypergraphs, and synthetic datasets, among others.

We address the concerns below:

Insufficient Analysis of Graph-to-Hypergraph Explainability

We fully acknowledge there are similarities between the hyperGNN and GNN variants of the problem; this is why we have taken inspiration from the GNN methods. Our contribution is to design an explainer for hyperGNNs that is simple and effective rather than to closely adapt existing GNN explainers and identify where they fail. We believe the GNN-to-hyperGNN challenge comes down to the larger search space for potential explanation subhypergraphs, as noted by the reviewer. How this might manifest as failure modes of existing GNN explainers could vary greatly, but we summarize a few high-level themes:

• Some methods, such as GNNExplainer, rely on learning a fractionally-relaxed adjacency matrix and obtain the actual subgraph by thresholding. While this seems to have sufficed for GNNs, the performance is notably worse for hyperGNNs. We do a case study with GNNexplainer on our benchmarks and discuss the challenges – please refer to our overall comment.
• Many methods directly explore the combinatorial space of subgraphs e.g. SubgraphX by MCTS or XGNN by generating a graph with policy gradients. These suffer from the large action space of the hypergraph compared to the graph, as we have discussed (line 194).
• Concept-based methods rely on a clusterization of the latent space. While this was empirically validated on graph-based methods, we are the first work that validates a similar behaviour on hypergraphs.
• Global concept-based explainers designed for graphs (such as GCExplainer and CDM) are relying on n-hop neighborhood to provide the explanation. While for graphs this still outputs a reasonable-sparse structure, in the case of the higher-order structure, sub-hypergraphs obtained by extracting n-hop neighbourhoods are hard to interpret. We provide a visual comparison of this phenomena in Figure 8 where the top row displays explanations extracted with k-hop neighbourhoods (already very dense even for a small k, k=3), while the bottom row displays our concise explanations.

Finally, please refer to our overall comment for a case study that illustrates a failure case of applying a GNN explainer to hyperGNN.

Constrained Real-World Evaluation

To test our model in real-world scenarios, we are using the established benchmarks used in the hypergraph representation learning community [1-4]. We select a subset of datasets where using the hypergraph structure produces a substantial benefit, such that we can fairly test the capability of our structure-based explainer. While it is beyond the scope of the current paper, we are keen to test our model in more challenging scenarios such as datasets with higher number of nodes or more complex interactions. We welcome any suggestion of such benchmarks if the reviewer has concrete examples. Moreover, moving from the synthetic setup to the real-world domain is still a challenge in the graph community as well, even if the domain is much older and well developed compared to the hypergraph one, with most of the current advances in graph explainability being validated on the synthetic BA-based datasets [5-6] . Please remember that this is an explainability work and thus synthetic datasets are of utmost importance.

We also highlight that the lack of benchmarks is a well-known issue in the hypergraph community. This is clearly not a problem related to a potential “lack of substantial practical applications”, as several works [7-9] suggested the importance of higher-order interactions in modelling relations from various domains. However, hypergraph representation learning is a much more novel and slow-paced domain compared to its graph counterpart (with the first popular architecture being published in 2019 compared to GCN which started to be popular in 2017) so we can not expect the same level of resources and data available as in the graph literature. In fact, GNN literature evolved around the standard Cora-Citeseer benchmark for several years until the current large-scale datasets were made available.

CONTINUED

We thank the reviewer for their time and thoughtful comments. We are glad that you appreciate the value of the topic, the presentation of our paper, our strong results, and experimental design! We address each of the reviewer’s points below.

There is not a lot of theory in this paper, and the methods used are pretty straightforward.

As the reviewer rightly highlighted, designing explainers for hypegraph models is an unexplored territory, which we believe limits the applicability of hypergraphs, particularly in sensitive domains. Our proposed method is indeed straightforward, making it compatible with any existing hypergraph approach without introducing significant computational overhead, an important feature for explainer architectures. While this is not a theoretical paper, the components of the proposed method are clearly motivated and it generates high-quality explanations, as demonstrated in our experiments. This is well-aligned with the requirements of ICLR conference, which welcome not only theoretical papers, but also novel empirical work.

The literature could be a bit more developed...

Due to the space constraints we only provided a brief summary of the related works, to create a general idea of the field. Following the reviewer's suggestion, we will include a more detailed literature review in the supplementary material together with more details on preliminary methods. If the reviewer has any particular questions regarding the baselines or the method used in our model we are happy to answer them.

The local and global explanations techniques are completely decoupled...

We draw attention to the fact that the two explainers are not decoupled. As explained in Section 4.2 and in Figure 1, the local explainer may be used as a stand-alone explainer in order to produce instance-level explanations; furthermore, the global explainer relies on the local explainer to produce concise and legible explanation subhypergraphs based on the extracted concepts (line 256). This is a novelty to the global GNN method the reviewer alludes to, and without, the global explanations (e.g. Figure 4) would be dense 3-hop neighborhoods with poor concision.

There should be more local and global explanations derived from this work and derived from the GNNs explanation literature...

Please refer to our overall comment.

you use a mean-field approximation, can you justify this more...

We fully acknowledge that the mean field approximation is a simplifying assumption. Though stringent, it is frequently used in variational inference to make progress on an intractable joint probability. While we have not seen this explicitly in the hypergraph literature, the complex probability distribution we are dealing with fits the mould of those variational problems; furthermore, the approximation underlies (graph) methods like GNNexplainer which independently estimates for each edge whether that edge should exist in the explanation. Finally, we believe the validity of the approximation is justified by our strong results. Even though we use an approximation to optimize for the explanation subhypergraph, those explanations successfully replicate the original predictions, as reflected in the fidelity metrics.

Please define a concept line 251...

Thank you for the suggestion, we will clarify this in the final version. In our work, ‘concept’ denotes units of information that are easy to understand and interpret by humans, and frequently appear in the analysed data, following Ghorbani et al. (2019). Methods using concept-based explanations are popular in the explainability literature for vision (where image patches can be identified as concepts), language (where certain phrases or a bag of words can be identified as concepts) and also graph data (where network subgraphs can be interpreted as concepts). In explainability, a concept constitutes a repetitive substructure of the original input modality found across multiple input examples. On a technical level, concepts in neural networks can be discovered via clusters in the latent space. The clustered embeddings often exhibit similar semantics. For example, in the case of (hyper)GNNs, nodes clustered together have been found to exhibit similar feature vectors and neighbourhoods. Following Magister et al. (2021), we extract the nodes closest to the geometric centre of a cluster as the most representative candidates for the concept.

Can you specify what the latent embedding space is for a node?

Thank you for the question; we will make sure this is clearly stated in the final version. We are using the embedding after the final message passing layer. We expect similar concept extraction is possible using other late-stage layers in the architecture.

Have you tried other explanation...

Please refer to our overall comment.

CONTINUED