Explaining Hypergraph Neural Networks: From Local Explanations to Global Concepts

Authors: Shiye Su, Iulia Duta, Lucie Charlotte Magister, Pietro Lio
Primary area: interpretability and explainable AI
Keywords: graph neural nets, hypergraph neural nets, explainability, concepts

Abstract:
Hypergraph neural networks are a class of powerful models that leverage the message passing paradigm to learn over hypergraphs,
a generalization of graphs well-suited to describing relational data with higher-order interactions. However, such models are not naturally interpretable, and their explainability has received very limited attention. We introduce SHypX, the first model-agnostic post-hoc explainer for hypergraph neural networks that provides both local and global explanations. At the instance-level, it performs input attribution by discretely sampling explanation subhypergraphs optimized to be faithful and concise. At the model-level, it produces global explanation subhypergraphs using unsupervised concept extraction. Extensive experiments across four real-world and four novel, synthetic hypergraph datasets demonstrate that our method finds high-quality explanations which can target a user-specified balance between faithfulness and concision, improving over baselines by 25 percent points in fidelity on average.

Decision: reject
Reviewer scores: 3, 5, 5, 3

Reviews and discussion:
<thread>
creation date:
1729817699558

thread_type:
official_review

<thread_object>
creator: reviewer_agpw

<content>
summary:
This paper proposes an explainer for hyperGNNs at both instance-level and global-level, which is called SHypX. At both instance-level and global-level, they extract salient subhypergraphs as the explanation. Four synthetic datasets were introduced in this paper, although none of them are open-sourced.

strengths:
1. This paper is the second work on hyperGNN explainability. 
2. They introduce a new benchmark that contains four synthetic datasets to evaluate hyperGNN explanations.

weaknesses:
1. 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. 
2. The newly introduced datasets are not provided. 
3. The presentation is not very good. For example, the caption of Fig 2 is confusing. 
4. The performance improvements on real world datasets seems minimal. 
5. The evaluation on the global-level explainability is too few. It doesn't seem that this explainer actually produce global-level explanations.  
6. Some concerns about motivation and metrics. See questions.

questions:
1. In Line 171, it says "our goal is to produce an explanation subhypergraph" for the local explainer. However, a single subhypergraph may not be enough to fully explain the prediction. Why do you only consider to produce a single explanation subhypergraph for each graph sample? 
2. The proposed method doesn't look to be specifically designed for hyperGNNs. For example, modules like Gumbel-Softmax samplers and global clustering. Why don't apply your method also to traditional GNNs? And why not use the explainers for those traditional GNNs, (which didn't use Gumbel-Softmax samplers, but some other methods to pick crucial subgraphs) to explain hyperGNNs? 
3. For the Fidelity evaluation, why do you only evaluate the Fidelity-, how about Fidelity+?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730329655392

thread_type:
official_review

<thread_object>
creator: reviewer_kdsz

<content>
summary:
This paper addresses the post-hoc explainability of hypergraph neural networks (HyperGNNs) for the task of node classification in hypergraphs. The authors propose a method for providing both instance-level and global-level explanations for these models. The core idea of their approach is to sample node-hyperedge pairs in the computation graph of a specific node in a way that minimizes the loss function. Additionally, they introduce a set of synthetic hypergraphs to evaluate their method. Their experimental results demonstrate that the proposed method outperforms existing baselines.

strengths:
- The paper is well-written and clearly presented.
- The authors address both instance-level and global-level explainability for HyperGNNs while latter has not been addressed previously.

weaknesses:
- 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.
- 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.
- 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.
- 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.

questions:
- For the task of node classification, what would happen if a method returns only the first immediate neighbors of a node as the most important sub-hypergraph? Specifically, how would the fidelity metrics mentioned in this paper perform in this scenario? My main point is that having only an explainability model for node classification may not be of significant importance.

- Could you present a hypergraph as a bipartite graph and apply graph-based explainability models to compare their performance with your method? It would be particularly useful to try GNNExplainer, as this method is very intuitive, and it is not immediately clear why it would not perform well in your setting.

- For the global explainer, you are introducing yet another black-box, despite mentioning that SHypX "doesn’t rely on additional black-box networks." Could you clarify this contradiction?

- It is necessary to visualize the results of the explanations for at least the synthetic datasets to visually assess which sub-hypergraphs SHypX identifies as important.

- Figure 4 is very confusing, and the results you are trying to convey are not clear. Is there an alternative way to evaluate global explanations that might be more effective?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730388223970

thread_type:
official_review

<thread_object>
creator: reviewer_4e64

<content>
summary:
The paper introduces SHypX, the first model-agnostic post-hoc explainer for hyperGNNs that provides both local and global explanations. 
At the local level, it finds salient subhypergraphs to explain individual predictions using Gumbel-Softmax sampling, while balancing faithfulness and concision. 
For global explanations, it extracts concepts by clustering network representations and visualizing representative examples.

In experiments, the paper introduces four synthetic hypergraph datasets and generalized fidelity metrics for proper evaluation. 
Through experiments on both synthetic and real datasets, SHypX demonstrates superior performance over existing baselines while maintaining architecture independence, making it a significant contribution to hypergraph machine learning interpretability.

strengths:
The paper presents multiple novel contributions: 
1. The first to provide both local and global explanations for hyperGNNs. 
2. Introduces a new sampling-based approach for local explanations that avoids using attention mechanisms. 
3. It develops techniques specifically designed for hypergraph structures. 
4. The synthetic datasets also represent an original contribution by creating structure-dependent tasks for evaluating hypergraph explainability.
5. This work addresses an important gap in making hyperGNNs more interpretable.

weaknesses:
**Insufficient Analysis of Graph-to-Hypergraph Explainability**

**Constrained Real-World Evaluation**

questions:
**1.Insufficient Analysis of Graph-to-Hypergraph Explainability**
The paper provides some reasons why hypergraphs need specialized explainers, such as larger search spaces and structural differences. However, it lacks an in-depth analysis of what specifically would fail if traditional GNN explainers were used on constructed hypergraphs, which can be represented as graphs. Including a comparative study that illustrates concrete failure cases when applying regular GNN explainers to hypergraphs would significantly strengthen the motivation for developing specialized hypergraph explainers.

**2. Constrained Real-World Evaluation**
- The real-world datasets used in the paper are relatively small, which limits the ability to generalize the results. 
- Moreover, the paper acknowledges that the selected datasets may not sufficiently test the model's ability to understand hypergraph structure, given that even simple MLPs achieve competitive performance. While the inclusion of synthetic datasets partially addresses this limitation, it would be more compelling to include more complex real-world hypergraph datasets that present a greater challenge. Such datasets would better demonstrate the practical utility and robustness of the proposed method. - Furthermore, the constrained real-world evaluation raises the question: does the limited complexity and availability of these datasets indicate that the problem lacks substantial practical applications?

Minor Comment: In Figure 1, what does the "concept-to-class decision tree" icon represent? Providing a brief explanation would help improve clarity.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730594935766

thread_type:
official_review

<thread_object>
creator: reviewer_ngzs

<content>
summary:
The paper studies a relatively unexplored problem of hypergraphs neural networks explanation for the task of node classification, both from the local and global perspective. The authors describe two methods they use for local and global explanations. They
then benchmark the methods on synthetic and real-world datasets against current baselines, notably with an updated fidelity metric.

strengths:
- The topic is interesting, and still in unexplored territory.
- The paper is well written, the experiments seem to yield good results and the experimental design looks solid.

weaknesses:
- There is not a lot of theory in this paper, and the methods used are pretty straightforward. 
- The literature could be a bit more developed (the one other baseline on the problem, global explanations of GNNs, mean field approximation in the hypergraphs context).
- The local and global explanations techniques are completely decoupled, with the global
explanation in particular being transposed from a method already studied for GNNs. This is a liitle surprising, as the titled implied a deeper relationship.
- There should be more local and global explanations derived from this work and derived
from the GNNs explanation literature: benchmark different global explainer heuristic
based on the local explanation (as opposed to just one); for the local explanation, an
approximation technique with a more refined method, or at least explain why other
methods would not work.

Overall the paper needs a major revision.

questions:
- Line 212 you use a mean-field approximation, can you justify this more, add some
literature that justifies such approximations for hypergraphs? Why can you do that
(specially in the context of hypergraphs)? Are there other approximations you explored
or considered? This is a pretty strong assumption.
 
- Please define a concept line 251; it seems to be specific to a GNN, and to be a cluster
of points in the GNN embedding space, and its ”representative” is the node closest to
the geometric center in the embedding space, is that correct?

- Line 249: Can you specify what the latent embedding space is for a node? Is it the
final layer’s output before the softmax?

- The local and global explainer seem to be two completely decoupled methods; please
point this out in the paper. How are they related?
 
- Have you tried other types of global explanations (e.g., GLGex-
plainer [1]) based on this local explainer? 

- Have you tried other local explanations techniques (there are plenty of work [2])?

- Has a similar sampling method for local explanations been used in GNN explanations?

Some minor comments:

– Equation (3) line 209 is not clear, I would write it differently.

– Some typos: “explainiability” line 75, “P r(v ∈ esub = 0)” line 206

– “coherent explanations” line 80: please clarify what this means.

– What is “InfoNCE” line 106? add context about noise-contrastive estimation.

– Line 259, GCExplainer is mentioned in the method, but there has not been a
reference since the introduction. It should be added on line 244 along with the
Magister paper.

– For the results, it would be helpful to separate the local from the global explanations.

– The paragraph starting line 259 compares GCExplainer with the method of the
paper, this is not clear, as it is never explained what GCExplainer does.

[1] Azzolin, Steve, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. "Global explainability of gnns via logic combination of learned concepts." arXiv preprint arXiv:2210.07147 (2022).

[2] Kakkad, Jaykumar, Jaspal Jannu, Kartik Sharma, Charu Aggarwal, and Sourav Medya. "A survey on explainability of graph neural networks." arXiv preprint arXiv:2306.01958 (2023).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732353042574

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
regarding GNN explainers

comment:
We thank the reviewers for taking the time to comment so thoroughly on our paper! We would like to reply to a few common comments.

Several reviewers asked about comparisons to GNN methods and why explaining hyperGNNs is different from explaining GNNs. 

First, we would like to note that porting methods from GNN to hyperGNNs often involves non-trivial adaptation. In the realm of (hyper)graph architectures, such developments have constituted several independent works in the literature (HGNN, HCHA, HNHN, HyperGCN etc.). Similarly, in the realm of explainability, the extension of computer vision explainers to effective GNN explainers have also themselves warranted single papers [1,2]. Our contribution is to design an explainer for hyperGNNs that is simple and effective rather than to closely adapt many existing GNN explainers and identify where they fail. 

As a case study, we investigate GNNexplainer as a baseline, and this illustrates some new challenges of the hyperGNN setting, in addition to our observation about the larger search space (line 194). We adapt PyG’s GNNexplainer implementation for hypergraphs and otherwise use defaults, thresholding edge weights at 0.5 as suggested, and increasing epochs to 400 to match the setting for SHypX. The current PyG implementation is too slow to produce many explanations for large graphs, so currently we just report results for CoauthorCora, Zoo, and all synthetic datasets:

| | | fid-acc | fid-kl | fid-tv | fid-xent | size | density  |
|---|---|---|---|---|---|---|---|
|
| H-RandHouse | GNNexplainer | 0.54 | 0.85	| 0.44 | 1.39 | 3.3 | 0.10 |
| | SHypX | 0.01 | 0.04	| 0.06 | 0.59 | 9.2 | 0.19 |
|
| H-CommHouse | GNNexplainer | 0.66 | 3.12 | 0.67 | 3.27 | 4.1 | 0.08 |
| | SHypX | 0.00 | 0.02 | 0.03 | 0.18 | 9.2 | 0.20 |
|
| H-TreeCycle | GNNexplainer | 0.19 | 0.69 | 0.26 | 0.75 | 2.1 | 0.07 |
| | SHypX | 0.00 | 0.01 | 0.01 | 0.07 | 5.6	| 0.22 |
|
| H-TreeGrid | GNNexplainer | 0.75 | 1.59 | 0.64 | 1.78 | 3.3	| 0.09 |
| | SHypX | 0.01 | 0.02	| 0.04 | 0.22 | 15.1 | 0.45 |
|
| CoauthorCora | GNNexplainer | 0.31 | 0.60	| 0.26 | 0.66 | 1.6 | 0.20 |
| | SHypX | 0.00 | 0.00 | 0.00 | 0.07 | 2.1 | 0.29 |
|
| Zoo | GNNexplainer | 0.02 | 0.07	| 0.04 | 0.25 | 21.8 | 0.02 |
| | SHypX | 0.03 | 0.01 | 0.01 | 0.19 | 6.7	| 0.01 |

We see that GNNexplainer significantly underperforms SHypX (whose results we reproduce here), and in some cases also the other baselines (refer to Table 1 and Table 2 in manuscript). Note that we actually gave GNNexplainer a comparable or more generous size budget than SHypX (size penalty of 0.005 vs. 0.05 on synthetic datasets and 0.005 on real datasets). GNNexplainer explanations are small because few node-hyperedge links are given high attributions.

To better understand where GNNexplainer is struggling, we also look into the fidelity metrics on the pre-thresholding ‘soft mask’. Here, the whole computational subhypergraph is present but with edge weights. We see that this ‘soft mask’ is more faithful, but still generally worse than SHypX. The thresholding to obtain a subhypergraph introduces further error. From these observations, we hypothesize that for hyperGNNs 1) GNNexplainer tends to get stuck in local minima, unlike our sampler which introduces some randomness through Gumbel-Softmax, and 2) GNNexplainer’s entropy penalty fails to make the ‘soft mask’ seen during optimization sufficiently similar to the thresholded final explanation. SHypX avoids this problem by discrete sampling.

| | | fid-acc | fid-kl | fid-tv | fid-xent |
|---|---|---|---|---|---|
| H-RandHouse | GNNexplainer 'soft' | 0.48 | 0.68 | 0.40 | 1.22 |
| CoauthorCora | GNNexplainer 'soft' | 0.00 | 0.01	| 0.01 | 0.07|
| Zoo | GNNexplainer 'soft' | 0.00 | 0.04 | 0.05 | 0.22 |

[1] Pope, Phillip E., et al. "Explainability methods for graph convolutional neural networks." Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 2019.

[2] Huang, Qiang, et al. "Graphlime: Local interpretable model explanations for graph neural networks." IEEE Transactions on Knowledge and Data Engineering 35.7 (2022): 6968-6972.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a model-agnostic post-hoc explainer for hyperGNNs, providing both local and global explanations. For local explanations, it identifies important sub-hypergraphs to explain individual predictions using Gumbel-Softmax sampling, balancing faithfulness and conciseness. On the other hand, for global explanations, it derives concepts by clustering network representations and visualizing representative examples.

However, despite the rebuttal discussion, the reviewers remain unconvinced about the comprehensiveness of the empirical benchmarking and the validity of claims regarding human interpretability. As a result, the paper is considered not ready for publication in its current form.