From GNNs to Trees: Multi-Granular Interpretability for Graph Neural Networks

Authors: Jie Yang, Yuwen Wang, Kaixuan Chen, Tongya Zheng, Yihe Zhou, Zhenbang Xiao, Ji Cao, Mingli Song, Shunyu Liu
Primary area: interpretability and explainable AI
Keywords: Graph Neural Networks, Multi-Granular Interpretability, Graph Classification

Abstract:
Interpretable Graph Neural Networks (GNNs) aim to reveal the underlying reasoning behind model predictions, attributing their decisions to specific subgraphs that are informative. However, existing subgraph-based interpretable methods suffer from an overemphasis on local structure, potentially overlooking long-range dependencies within the entire graphs. Although recent efforts that rely on graph coarsening have proven beneficial for global interpretability, they inevitably reduce the graphs to a fixed granularity. Such an inflexible way can only capture graph connectivity at a specific level, whereas real-world graph tasks often exhibit relationships at varying granularities (e.g., relevant interactions in proteins span from functional groups, to amino acids, and up to protein domains). In this paper, we introduce a novel Tree-like Interpretable Framework (TIF) for graph classification, where plain GNNs are transformed into hierarchical trees, with each level featuring coarsened graphs of different granularity as tree nodes. Specifically, TIF iteratively adopts a graph coarsening module to compress original graphs  (i.e., root nodes of trees) into increasingly coarser ones (i.e., child nodes of trees), while preserving diversity among tree nodes within different branches through a dedicated graph perturbation module. Finally, we propose an adaptive routing module to identify the most informative root-to-leaf paths, providing not only the final prediction but also the multi-granular interpretability for the decision-making process. Extensive experiments on the graph classification benchmarks with both synthetic and real-world datasets demonstrate the superiority of TIF in interpretability, while also delivering a competitive prediction performance akin to the state-of-the-art counterparts.

Decision: accept (poster)
Reviewer scores: 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1729261666137

thread_type:
official_review

<thread_object>
creator: reviewer_hgdz

<content>
summary:
The authors propose a novel interpretable graph learning method, i.e., TIF, which transforms the GNN into a hierarchical tree. Within the hierarchical tree, each layer represents a graph granularity and each node represents a coarsened graph. In detail, the hierarchical graph coarsening module clusters the graph nodes into coarser clusters and then the learnable graph perturbation module introduce various perturbations to propel the robustness and the diversity of the coarsened graph. At last, an adaptive router identifies the best root-to-leaf path and provides the prediction result. Sufficient experiments demonstrate the effectiveness of TIF in both interpretation and prediction.

strengths:
1. The tree structure based interpretation method is intriguing and can further enlighten the GNN explanation field.
2. The manuscript is well-organized and the proposed TIF framework is clearly introduced, making the whole work easy to understand.
3. The experiments are sufficient and discussed in detail, verifying the effectiveness of the proposed TIF model.
4. The Figures and Tables are insightful and well-analyzed, deriving meaningful conclusions that facilitates the understanding to TIF.

weaknesses:
1. The definition of interpretation in this work is opaque. Whether the selected root-to-leaf path or the final leaf node serves as the interpretation to the input graph? Furthermore, why the coarsened graph can be considered as a kind of explanation? An example of input graph, the prediction result, and the corresponding explanation is helpful to figure this issue out.
2. The evaluation metrics adopted in experiments fail to reflect the sparsity of the generated explanation. A trivial explanation, such as the original graph, is meaningless to practical applications.
3. Some terminologies are used before giving definition. In Figure 3(c), the definition of path importance is missing in the manuscript. In Section 4.4, the compression ratio q is discussed without introduction or definition.
4. In Figure 4 and Figure 5, what is the principle to measure the quality of the generated explanations? For example, which instance of the finer graphs in Figure 4 is closer to the ground-truth explanation? Furthermore, the explanation provided by GIP is grey (without color), while that of TIF is colorful. If this difference represents some superiorities of TIF, and please elaborate if yes.
5. In Figure 7, the notations "IAR" and "LV" lack definition and the discussion of Figure 7 mismatches with it.

questions:
1. Could you provide an example which contains the input graph, the root-to-leaf path, the coarsened graphs of each layer, and the final prediction. A detailed analysis to  the input, the explanation, and the prediction can facilitate the comprehension of TIF.
2. An ablation study towards the graph perturbation module is recommended, to demonstrate the effectiveness of enhancing diversity.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730277659615

thread_type:
official_review

<thread_object>
creator: reviewer_yj5d

<content>
summary:
This paper introduces a Tree-like Interpretable Framework (TIF) for inerpretable graph classification, transforming standard GNNs into hierarchical trees that represent graphs at varying granularities. TIF uses a graph coarsening module to compress graphs while maintaining diversity among tree nodes, and an adaptive routing module to highlight the most informative paths for decision-making. Extensive experiments show that TIF improves interpretability and achieves competitive prediction performance compared to state-of-the-art methods.

strengths:
1. It is reasonable to require hierarchical explanations for the graph classification tasks of GNNs, and the issue addressed in this paper is of practical significance.
2. The paper employs sufficient comparative algorithms to demonstrate the effectiveness of the proposed algorithm.
3. The introduction is well-written and provides clarity, greatly aiding in the understanding of the paper's contributions and innovations.

weaknesses:
1. The notation in the methods section is quite confusing due to the various subscripts, making it very difficult to follow.
2. The evaluation metrics used to measure the effectiveness of model explanations are not sufficiently convincing.
3. There is a lack of visual comparisons between the various interpretable GNNs, such as GSAT vs the proposed method.
4. There is a lack of analysis regarding the algorithm's complexity and running efficiency.
5. The proposed algorithms lack clear theoretical foundations and appear to be based solely on heuristic designs.

questions:
1. In Fig. 1, what do "finer graph" and "moderate graph" represent? Why is the progression from finer to moderate to coarsen? It is recommended to explain this in the caption or the main text.
2. what is the relationship between $ \hat A$ and $A^{(l+1)}$?  Additionally, as shown in eq (5), does the coarsened adjacency matrix $ \hat A$ have the same dimensions $n*n$ as the adjacency matrix of the original graph? Why eq(5) can help the model ensure the connectivity of the coarsened graph?
3. Regarding the explanation accuracy metric, can the softmax output from the GNN be considered as confidence? This lacks theoretical justification.
4. Regarding the consistency metric, is the capability of graph kernels sufficient for distinguishing structural differences?
5. Conducting explanation experiments on the Mutag dataset is necessary.
6. Please provide visual explanations of algorithms like GSAT on the MultipleCycle dataset.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730691056648

thread_type:
official_review

<thread_object>
creator: reviewer_ka23

<content>
summary:
The paper proposes a TIF that transforms GNNs into hierarchical tree structures to provide multi-granular interpretability for graph classification tasks.

strengths:
The paper is very interesting, and the author finds that multi-granular interpretability in GNNs is important but was overlooked by previous works. Thus, they propose TIF to enhance multi-granular interpretability. Extensive experiments show that the proposed method is effective and demonstrates good interpretability.

weaknesses:
Overall the paper is good but why does Table 2 have no std value?

The framework requires significant computational resources to maintain and process multiple branches and paths per node, along with multiple perturbation matrices for each node. The hierarchical tree structure adds computational complexity at each level.

The architecture is complex with three major modules (coarsening, perturbation, routing) and requires careful tuning of 5 different hyperparameters (α1-α5). This makes it more difficult to implement and maintain than simpler interpretability approaches, especially considering the additional logic needed for the dynamic hardening mechanism.


There is no formal mathematical justification for why the multi-granular approach improves interpretability, nor are there guarantees regarding the optimality of the tree structure.

questions:
The training process requires balancing various loss terms, but the paper offers limited guidance on optimizing this process.
</content>
</thread_object>

</thread>


Metareview:
metareview:
### Summary
The paper proposes a Tree-like Interpretable Framework (TIF) to improve interpretability in graph neural networks (GNNs) for graph classification tasks. TIF transforms GNNs into hierarchical tree structures, where each layer represents different graph granularities. It includes three major components: Graph Coarsening Module (Compresses graphs into coarser representations while preserving diversity), Graph Perturbation Module (Introduces perturbations to enhance robustness and diversity), and Adaptive Routing Module (Selects the most informative root-to-leaf path for interpretation and prediction).
Experiments show that TIF improves multi-granular interpretability while maintaining competitive predictive performance compared to state-of-the-art interpretable GNNs.

### Strengths
- The hierarchical tree structure provides a multi-granular approach to graph interpretability, addressing an overlooked need in prior works.
- The paper conducts extensive experiments with comparisons against multiple baseline methods, demonstrating the effectiveness of TIF in both prediction and interpretation.
- The manuscript is well-structured, and the figures and tables are insightful, making the proposed framework easy to understand.

### Weaknesses
- The hierarchical tree structure and multi-module design significantly increase computational cost. Multiple hyperparameters and perturbation matrices per node add complexity, making implementation and maintenance challenging.
- The framework relies heavily on heuristics without clear mathematical justification for why the multi-granular approach improves interpretability. The optimality of the tree structure is not guaranteed.
- Some evaluation metrics fail to reflect the sparsity or quality of explanations, limiting their practical relevance. Key definitions (e.g., interpretation, path importance, compression ratio) are missing or introduced late, causing confusion. Figures and comparisons lack sufficient detail (e.g., how TIF explanations compare to ground-truth or baseline methods).

The paper proposes an innovative and practical framework for improving interpretability in GNNs, addressing a significant gap in graph classification tasks. The multi-granular interpretability provided by the hierarchical tree structure is a valuable contribution, and the extensive experiments demonstrate the potential of TIF to advance interpretable GNNs. While theoretical justifications and computational efficiency could be improved, the novelty and practical implications of the framework justify its acceptance.