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
Venue: ICLR 2025 Poster (2025)
Keywords: Graph Neural Networks
Multi-Granular Interpretability
Graph Classification
Primary area: interpretability and explainable AI

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.

Published as a conference paper at ICLR 2025
FROM GNNS TO TREES: MULTI-GRANULAP INTER- PRETABILITY FOR GRAPH NEURAL NETWORKS
Jie Yang', Yuwen Wang', Kaixuan Chen Tongya Zheng
Yihe Zhou', Zhenbang Xiao', Cao', Mingli Song"., Shunyu Liu
'Zhejiang University,
State Key Laboratory Blockchain and Data Security, Zhejiang University.
3 Hangzhou High-Tech Zone (Binjiang) Institute of Blockchain and Data Security,
BBig Graph Center, Hangzhou City University,
Nanyang Technological University (yang-jie, yuwenwang,
s chenkx, zhouyihe, xiaozhb, brookkon)) @z @zju. edu. cn, poujjang-zhenglee 63. com, shunyu. liuêntu. edu.sg
ABSTRACT
Interpretable Graph Neural Networks (GNNs) aim to reveal the underlying reason- ing behind model predictions, attributing their decisions to specific subgraphs that are informative. However, existing subgraph-basee interpretable methods suffer from an overemphasis on local structure, potentially overlooking long-range de- pendencies within the entire graphs. Although recent efforts that rely on graph coarsening have proven beneficial for global interpretability, they inevitably re- duce the graphs to fixed granularity. Such inflexible way only capture graph connectivity at 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 novel Tike-like Interpretable Framework (TIF) for graph classifi- cation, where plain GNNs are transformed into hierarchical trees, with each level featuring coarsened graphs of different granularity as tree nodes. Specifically, TIF iteratively adopts graph coarsening module to compress original graphs (ie.. root nodes of trees) into increasingly coarser ones (ie., child nodes of trees), while preserving diversity among tree nodes within different branches through a dedicated graph perturbation module. Finally, we propose an adaptive rout- ing 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- state-of-the of-the-art counterparts. Our code will be made publicly available at https://gtttu...omm// com/duyy2022///11
INTRODUCTION
Graphs, as ubiquitous structures, are extensively employed represent complex relationships in various fields, such as social networks (Bu & Shin 2023 Tian & Zafarani, 2024 biological sys-
tems (Caufield et al.] 2023, Garg 2024). and transportation networks (Rahmani al.)
2023 Xu
al. 2022). To effectively model the connectivity patterns inherent in graphs, Graph Neural Net- works (GNNs) have demonstrated extraordinary capabilities, enabling significant advancements in
variety of graph-based downstream tasks (Levie al.) 2018 You al. 2020 Vrček al.) 2023).
However, despite their effectiveness, key challenge remains in the interpretability of GNNs, as their complex mechanisms often act "black boxes" (Yuan et al. 2022 Li al. 2022b). This lack of transparency makes difficult to understand and trust their inner decision-making processes, which
essential for many security-critica applications (Zhao & Barati 2023 El-Dawy et al. 2024)
"Corresponding author.

---

Published as a conference paper at ICLR 2025
To alleviate this issue, interpretable GNNs have emerged as promising paradigm from research communities, aiming to identify and elucidate the role of specific subgraphs in shaping the decisions made by the models (Ming et al.] 2019; Chen et al. 2022 Yin et al. 2023 Tygesen et al.) 2023 Lan ctt al. ).24). as depicted
Local
(c) Ours
subgraph
original graph (egg legenayme and non-enzyme proteins)
original graph
&
finer groph (e.g functional groups level)
N
N
(b) Global
moderate graphle amino adiss level
coarsened graph
original groph
courser graph(e protein molecular level)
Figure 1: Comparing different interpretable methods for GNNs.
in Figure a However.
interpretable methods often prioritize local structure at the expense of global context, potentially neglecting long-range dependencies within the entire graphs. Recent advance-
these subgraph-
ments highlight global interactions' importance for graph-level tasks, significantly improving
GNNs' representation capacity (Yao et al., 2022; Ding et al., 2023 Zhili et al. 2024 Li al. 2023
Liu at. 2023). In light of this, very recent work, GIP (Wang et al. 2024), introduces a learnable
graph coarsening mechanism for global interpretabiilty, as depicted
Figure [bb.. GIP aligns the
coarsened graph instance with various self- self-interpretable graph prototypes, unveiling the model reasoning process from a global perspective. However, this global based interpretable method inevitably reduces the graphs to fixed granularity. capturing graph connectivity solely at the output level, thus failing to account for multi-granularityy at intermediate levels. The fixed granularity may obscure intricate details in the inherent graph structure necessary for effective interpretability. Additionally, such an inflexible way can limit the model's 's adaptability to different graph types with diverse sizes and structures, thus compromising its robustness across various applications.
Graph-based tasks in roal-world scenarios often involve relationships at multiple levels of granu- larity (Stawiski et al., 2000 Fan al.) 2019). For instance, the distinction between enzyme and non-enzyme proteins can be attributed to structural differences observed across varying granulari- ties, ranging from functional groups and amino acids to protein molecular level (Hu et al. 2024 Zhai et al. 2024). At the level of functional groups, the functional groups in enzymes are organized into active sites with specific structures and orientations to facilitate catalysis, while non-enzymes lack such organized formations. When considered at the amino acid level, enzymes of the same type typically exhibit highly conserved amino acid sequences, ensuring consistency in structure and func- tion across different instances of the enzyme. At the protein molecular level, enzymes often exhibit fewer helices and more elongated loops compared to non-enzymes, while also demonstrating tighter packing of their secondary structures (Stawiski et al., 2000). Thus, suggest that interpretable GNNs can benefit from employing a multi-granular perspective. By spanning from local to global perspectives, interpretable GNNs can elucidate the underlying factors influencing model predictions across different levels of granularity, thereby enhancing trustworthiness for decision makerrs.
In this paper, we introduce new tree-like interpretable framework for graph classification, termed TIF, to explicitly transform original GNNs into hierarchical trees with each level representing coars- ened graphs of varying granularities tree nodes, depicted in Figure mc). This tree-like struc- ture is essential for multi-granular interpretability, as it can layer different granularities while using branches to capture diverse structural variations. TIF comprises three key modules that enable ef- ficient tree construction and search. In the tree construction phase, TIF iteratively uses the graph coarsening module to reduce the original graphs (serving as root nodes of trees) into increasingly coarser graphs (serving as child nodes of trees), adding depth to the tree structure. Next, the graph perturbation module introduces learnable perturbations to ensure diversity among the tree nodes (i.e., coarsened graphs) across different branches, which broadens the tree structure. In the tree search phase, the adaptive routing module dynamically identifies the most informative root-to-leaf paths, providing both the final prediction and multi-granulaa interpretability of the decision-making process. Our main contributions can be summarized as follows:
We investigate a new challenge of multi gaatulgr interpretability in GNNs, a highly important ingredient for graph-level tasks yet largely overlooked by existing literature.
2

---

Published as a conference paper at ICLR 2025
We propose a novel Tree-like Interpretable Framework (TIF) to transform plain GNNs into inter- pretable trees, thereby facilitating multi granular interpretability. TIF employs the graph coarsen- ing module and the graph perturbation module to build the tree structure, focusing on depth and breadth aspects respectively. Then the adaptive routing module is responsible for highlighting the valuable root-to-leaf paths for both model prediction and interpretability.
Extensive experiments conducted on both synthetic and real-world datasets demonstrate that TIF yields competitive performance compared to Wate-of-the-aa competitors, while significantly en- hancing interpretability through multi-granular insights.
2
RELATED WORK
2.1
INTERPRETABLE GRAPH NEURAL NETWORKS
Traditional interpretable GNNs aim to uncover and explain the contribution of specific subgraphs to model decisions. These subgraph-based interpretable methods can be categorized into two main types: post-hoc methods and intrinsic methods. Post-hoc methods (Chen et al. 2022 Zhong et al. 2023 Fang et al. 2023), such as GNNExplainer (Ying et al. 2019) and PGExplainer (Luo et al, 2020 aim to explain model decisions by retrospectively finding key subgraphs after training. In- trinsic methods (Ynn et al.] 2023: Tilli & Vul 2024 La Rosa 2024), like GIB (Ming et al.) 2019),
incorporate explainability into the training process by emphasizing salient subgraphs. However, these subgraph-baser methods tend to focus on local structures, often failing to capture long-range dependencies or global graph-level interactions (Ding al. 2023).
Recent progress in GNN research has placed growing emphasis on the significance of global inter- actions in graph-level tasks (Yao al. 2022 Ding al. 2023 Zhili al. 2024 Li et al. 2023 Liu et al. 2023). To address the limitations of subgraph-basee based interpretable methods in capturing global interactions, GIP (Wang al. 2024) seeks provide global interpretability by capturing in- teractions across the entire graph during training. While this global- based method improves global interpretability, it often constrained by output level, limiting ability to capture multi-scale rela- tionships that are crucial for complex graph structures (Yao et al. 2022).
2.2 NEURAL TREES
Neural Trees (NTs) are the result of integrating Neural Networks (NNs) and Decision Trees (DTs). NTs can be classified into non-hybrid, semi-hybrid, and hybrid (Li et al. 2022a). Non-hybrid ap- proaches extracted rules from trained NNs, but the two models were not integrated into a hybrid model (Costa & Pedreira 2023) Ferigo et al., 2023) -eecheer-Seichhee et al. 2024 Costa et al., 2024]. Semi-hybrid methods draw on the class hierarchy from DTss and incorporate into NNs, but do not adopt the decision branch mechanism (Li et al. 2022a). Hybrid methods, or Neural Decision Trees (NDT's) (Zheng et al. 2023 Aissa et al. 2024), combine class hierarchy and deci- sion branches (Li et al. 2022ah, offering ad advattages in interpretability (Ji et al. 2020 Wan et al. 2021 Nauta et al. 2021). DNDF (Kontschieder et al. 2015) optimizes leaf predictions by mini- mizing a convex objective, but its explanations are derived solely from the final layer of the CNNs. Tanno et al. (2019) proposes dynamic tree generation to introduce interpretability into each layer of neural networks, but its greedy algorithms can result in suboptimal structures (Tanno et al.. 2019). NBDT (Wan et al. (021)) uses predefined concepts to prevent suboptimal structures but relies on manual WordNet (Brust& Denzler 2019) data. These works have developed quite richly in CNNs but are largely underexplored in GNNs. To address these limitations, we propose the TIF, enabling multi-grann multi-granular and comprehensive interpretability GNNs.
3 METHODOLOGY
In this section, we elaborate the details of the proposed TIF. Figure illustraaees its workflow, which includes three modules: 1) The hierarchical graph coarsening module progressively com- press the original graphs into coarser ones; 2) The learnable graph perturbation module introduces controlled perturbation matrices to preserve diversity among branches; 3) The adaptive routing module identifies the most informative root-to-leaf paths make prediction and provide the multi-
3

---

Published as a conference paper at ICLR 2025
Tel Hersrched Grash Cocraciing
Tree building process
GCN
Portition Iteration cycle for modie (4) (b)
Encoder
Logical partition
O
Each
Build tree
(a) Hierarchical Graph Coarsening Module
Adaptive
Reueer
Colcom
GCNCor
Learnable Graph
Routing
Come
Perturbation Module
(g) Learnasie Groph Perturbatioo Modille
Adaplive Routing
Predict Explain
MLF from modidaa
MLP
Linear
Linear
Softmox
PM
S
2
Prediction
Expicaatii
Figure 2: The workflow of the proposed TIF framework.
granular interpretability for decision-making. A detailed explanation of the formula notation this chapter can be found in Appendix A.4
3.1 HIERARCHICAL GRAPH COARSENING MODULE
In this section, we adopt classical hierarchical graph pooling strategy (Ying et al. 2018 Duval & Malliaros 2022 Islam al.) 20233] Wang al.) (2024)to build tree-like interpretable framework with our dedicated perturbation and routing design in the next section. By iteratively applying this module, we capture guati-granular structural information.
Specifically, first extract the node embeddings Z each layer using Graph Convolutional Networks (GCNs) (Kipf & Welling 2016). The update rule for the node embeddings given by:
z (D- (D- AD (ab-tz(--)w!!)
where ()) = X denotes the input feature matrix, = A+Iis is the adjacency matrix with self-loops, D is the degree matrix of Å, w()) is the weight matrix, and af-) is the activation function. Then, we implement soft coarsening strategy by using multi-layer perceptron (MLP) with softmax on the output layer generate clustering assignment matrix (!)) (Wang et al. 2024):
((9) softmax (MLP(1) (MLP)
where OMLP denotes trainable parameters, and S represents the probability that node U; belongs to cluster Subsequently, the (( to generate new adjacency matrix A (1+1) and embedding matrix X (1+1) for coarser graph (Ying et al. 2018). We apply the following equations:
N
(1+1)
Σ
Z
Vj =j= 1, K
(3)
A (1+1)
ΣΣ
S
UT
A
(1) kj
Vj L..., K.).,
(4)
4

---

Published as a conference paper at ICLR 2025
where N is the number of nodes in the current layer, and K(O is the cluster count at layer I. To pre- serve graph connectivity during coarsening, we apply edge prediction loss to constrain the process:
Link
Σ
(Ais log As + (1 log) An))
where Aij is the original adjacency matrix, and Aig is the adjacency matrix after coarsening.
3.2 LEARNABLE GRAPH PERTURBATION MODULE
In this module, introduce multiple learnable perturbations for the coarsening process of each parent node in the tree, enhancing its representation diversity and robustness (Ying et al., 2019] Luo et al. 2020 Yuan al. 2022). These slight perturbations allow similar child nodes to fully capture their similarity and share semantic paths across similar graphs, which not only facilitates the aggregation of structural information but also enriches the diversity of the tree, thus promoting the training of interpretable tree models.
Taking the expansion process of the k-th node in the (-th layer of the tree as an example, we first de- fine M learnable perturbation matrices for this node, i..., pl. (P()) ((),((2) ..... (()),(())) Then, use these perturbation matrices to perturb the clustering assignment matrix (1).. obtained by the graph coarsening module, which can be defined as:
g())&(())) ((1).: & + p(),k()) i= 1,2,,.....
(6)
where S00.k represents the original clustering assignment matrix for the k-th node in the I-th layer of the tree. The perturbed node embeddings (()).(()) will be computed based on the perturbed assignment matrices, which can be formulated as follows:
x (() = (()) ( (1))k = (()) Z(),k + ((O) ().k
where (1),k is the node embedding matrix for k-th parent node expansion at level / of the tree. To ensure that the perturbed embeddings remain both useful and diverse, we introduce two regular- ization terms: similarity regularization and diversity regularization. The similarity regularization ensures that each perturbed embedding (!). remains close to the original embedding (1), pre- serving important graph structure while applying perturbations:
R(O
Csimilarity
ΣΣM
X x - x11
(8)
where A; controls the strength of the similarity term, M, K(O) and J. respectively represent the number of branches of the parent node, the number of parent nodes in each layer, and the number of layers in the tree. Additionally, we add the diversity regularization to promote variation between the perturbed embeddings, ensuring that each branch represents different variant of the original graph:
I. K!
X (1)A(0 -000,60)13
Ldiversity
1=1 k=1
where a controls the degree of diversity.
In summary, these two terms form the total regularization loss Lppeturb which balances the preserva- tion of the core graph structure with the need for diversity across branches at different levels:
Lsimilarity + Laiversity.
(10)
3.3 ADAPTIVE ROUTING MODULE
In this module, we assign routers to each non-leaf node at every layer of the tree-like model for dynamically selecting the most informative root-to-leaf paths in the hierarchical structure.
First, we assign a router to each non-leaf node k of layer I, which concatenates the perturbed embed- dings ((1), (2)) Z())(M)) generated by the learnable graph perturbation module as inputs:
(0.4 (L.((Z(0).C)) Z (0)4 ... ((MMM)))
(11)
5

---

Published as a conference paper at ICLR 2025
Next, the router generates set of routing logits r())* based on the final node embedding ( which is used to represent the likelihood of choosing each path:
r (0,k & W(2).n.k (((()). ()) + b(0ink) + (2))...)
(12)
where w(1). and w(2k,,,k are the weight matrices for parent node k, b(2),rk and b (2)), are bias terms, and is nonlinear activation function (e.g., ReLU). The routing logits are then passed through a softmax function to yield the probability distribution p()),.,, representing the probability of choosing each path for parent node k at layer l: p(0,,, = softmax(r(")x) Based on the probability distribution, the most probable path j.2 is selected: itA arg max; p (()),, The node embedding and adjacency matrix the next layer [+1 are updated accordingly based on the selected path:
X ((+1),5%* S(()) pooled
(1+1) -(U, A (gg()
(13)
pooled
This process is repeated across all layers, progressively coarsening the graph and refining path se- lection until the final node embeddings (L++) and adjacency matrix A (L+1) are obtained. To encourage the exploration of multiple paths, we introduce an entropy-based regularization, which promotes diversity in the path selection process:
K M log (..N),
enntruy
ΣΣΣ
p
(14)
where p())A is the probability assigned to each path for parent node k at layer I.
3.4 INTERPRETABLE CLASSIFICATION BASED ON NEURAL TREE STRUCTURES
In this module, we make graph classification based on the constructed hierarchical tree-like model, which integrates multi-gran granularttt information from different levels of the tree by tracking the iden- tified root-to-leaf path, thus providing accurate and interpretable decisions.
For each test graph G. we calculate the probability of path selection (ath (1),k at each layer of the tree:
(Path (1) ()*,,,))
p(Path (0,, ( Σ3 exp(] (i. (.S, G.))
(15)
where (Path (..k Ge) is scoring function that measures the relevance of path l at layer for the classification of graph G.. Then, we choose the path with the highest probability from all the options:
00) arg max p( (Path (f).k Ge).
(16)
This process is repeated iteratively for each layer until reaching the leaf node, resulting in sequence of paths {i-1 122 k....., i to denote the multi- granularity interpretation results of our method, where L is the total number of layers in the tree.
The embeddings from the last selected path, z is directly used as the final embedding: 2 k² which will be passed through scoring function f(-) along with softmax to obtain the probability distribution for classification: h; = softmax (())). where h; represents the model's predicted prob- abilities for assigning graph G, each class. To ensure the accuracy of the proposed framework, we use the cross-entropy loss as the optimization objective, which can be denoted as:
M Crs.nn((h.,ys)
1 M
LCF
(17)
where M is the batch size, y; is the true probability distribution.
In summary, the final loss function combines the classification loss, edge prediction loss, entropy regularization, and perturbation regularization:
Lioaal LC + aj Lrink + azCpatur + as Centroy,
(18)
where a, a22 and ag control the strength of edge prediction regularization, perturbation regulariza- tion, and entropy regularization, respectively.

---

Published as a conference paper at ICLR 2025
4 EXPERIMENTS
4.1 EXPERIMENTAL SETTINGS
4.1.1 DATASETS
We first conduct experiments five real-world datasets across different domains evaluate the effectiveness of our framework. Additionally, we use three synthetic datasets to better demonstrate the interpretability our framework. The specifics of the datasets are follows:
Real-world datasets: To explore the effectiveness of our framework across different domains, we protein datasets including ENZYMES, PROTEINS (Feragen et al.] 2013), and D&D (Dobson & Doig 2003). molccular dataset MUTAG (Wu et al., 2018), and scientific collaboration dataset
COLLAB (Yanardag & Vishwanathan 2013). Please refer Appendix A.I more details.
Synthetic datasets: We further adopt manually constructed datasets: GraphCycle, Graph- Five (Wang et al. 2024), and the MultipleCycle dataset we designed to better illustrate the inter- pretability of our framework. These datasets are composed based on the combination of structures at certain granularity levels, thus possessing a multi-level granular information structure. Graph- Cycle consists of two classes: Cycle and Non-Cycle, while GraphFive comprises five classes: Wheel, Grid, Tree, Ladder, and Star. MultipleCycle consists of four classes: Pure Cycle, Pure Chain, Hybrid Cycle, and Hybrid Chain. Implementation details provided in Appendix A.1
4.1.2 BASELINES
We extensively compare our framework against three categories of baseline models:
We evaluate prediction performance of TIF with several powerful GNNs, including GCN (Kipf & Welling 2016), DGCNN (Wang et al. 2019). DiffPool (Ying et al. 2018),
Widely-used GNNs:
RWNN (Nikolentzos & Vazirgiannis 2020), and GraphSAGE (Hamilton et al.) 2017).
Subgraph-based Interpretable GNNs: We compare the explanation performance with methods that adopt post-hoc interpretation strategy, including GNNExplainer (Ying et al.) 2019), Sub- graphX (Yuan et al. (022), and XGNN (Yuan et al.) (020). We also compare both prediction and explanation performance with methods that adopt intrinsic interpretation strategy, such Prot-
GNN (Zhang et al. (0222). KerGNN (Feng et al. (2022). T-GNN (Yin et al. 2023) GIB YYu et al.)
2020). GSAT (Miao et al. 2022), ). and CAL (Sui et al. 2022).
Global-based Interpretable GNNs: We also use GIP (Wang et al. 2024). which focuses on global interpretability, as a baseline to evaluate both the prediction performance and the explana- tion performance with our framework.
Neural Tree: In addition, we construct a variant of TIF, which is binary tree model with a single layer of linear routers, called Bi-Tree, for comparing the stability of the explanation.
More details about the baseline models and settings can found Appendix
A.2 and
A.3
4.1.3 METRICS
We follow previous work (Wang et al. 2024 to employ prediction and explanation performance for quantitative analysis. For prediction performance, we use classification accuracy and F1 score for evaluation. For explanation performance, considering that evaluating intrinsic explanations is non-trivial due to the lack of common evaluation criteria, we design four unique metrics:
We use trained GNN to predict the explanations generated by different methods and use the predicted confidence scores as a measure of explanation accuracy.
Explanation Accuracy:
Consisteney: We adopt random walk graph kernel to calculate the similarity between the expla- nations generated by different methods and the ground truth measure of consistency.
Path Consistency and Path Importance: In order to compare the explanation stability with Bi-tree, we repeatedly input test samples into the model, record the path selection during each run, and calculate the consistency rate measure path consistency. Additionally. we analyze the frequency of path utilization across a sample set, integrating gradient- or feature contribution analyses, and using normalized entropy to measure the path importance.
7

---

Our framework exhibits a well-balanced distribution of path importance across all datasets. We conduct comparative experiment on the path importance between Bi-Tree and our frame- work, the results are shown in Figure 3 c). It indicates that the path importance distribution of method is balanced across all datasets, with no single path disproportionately dominating in Published as a conference paper at ICLR 2025
4.2 QUANTITATIVE ANALYSIS
To validate the effectiveness of our framework, we first compare its performance in terms of predic- tion and interpretability against baseline models across several graph classification datasets.
4.2.1 PREDICTION PERFORMANCE
To validate the predictive performance of our approach, we compare our framework with widely used GNNs and interpretable GNN models on real-world and synthetic datasets. We apply three independent runs and represent the results in Table 1 We can draw the following observations:
Our framework matches surpasses widely used GNN models in prediction performance. Our framework improves accuracy by 0.09% to 35.77% % on MUTAG and achieves top or second- best Fl scores in six of eight datasets, with comparable performance elsewhere.
Our framework outperforms existing interpretable GNN models significantly. It achieves higher accuracy six of eight datasets and higher Fl score four.
Table 1: Comparison of different methods terms of classification accuracy (%) and F1 score (%). We analyze the average results of three independent runs Bold and underline denote the best and the second-best results, respectively. The results with std values can be found Appendix C.I
Method
ENZYMES
D&D
PROTEINS
MUTAG
COLLAB
GraphCycle
GraphFive
MultipleCycle
Acc.
F1
Acc.
F1
Acc.
F1
Acc.
F1
Acc.
F1
Acc.
Fl
Acc.
Fl
Acc.
F1
GCN
57.23
51.32
76.15
69.12
78.89
72.21
71.82
63.18
72.56
65.78
79.45
71.56
$7.37
53.44
59.64
55.56
DGCNN
59.12
54.89
78.23
71.76
75.36
71.43
58.67
49.21
74.88
68.22
81.12
75.34
57.29
54.43
60.71
56.33
Diffpool
61.01
56.98
81.56
75.43
79.52
78.22
84.12
72.45
72.89
70.12
78.34
71.87
55.46
53.57
56.87
53.21
RWNN
54.76
48.12
76.89
74.67
76.12
70.89
88.21
85.04
73.45
68.45
78.89
78.76
56.25
52.45
57.16
$4.09
GraphSAGE
58.12
44.89
79.34
79.23
79.04
68.45
74.23
71.78
71.23
77.45
72.12
59.11
52.72
62.66
ProtGNN
53,21
43.89
75.23
72.45
56.38
54.32
60.26
KerGNN
55.67
48.45
72.89
68.23
76.12
71.12
71.45
62.12
74.12
69.12
80.21
73.89
58.06
50.82
63,22
57.94
x-GNN
55.34
47.12
79.12
73.89
72.34
62.12
90.12
75.12
73.45
68.34
81
76.78
60.14
54.07
64.74
62.48
GIB
3167
77.34
66.45
75.12
70.34
82.12
73.34
80.67
59.24
63.23
63.02
GSAT
61.34
55.12
72.12
62.12
74.45
71.89
94.35
82.34
75.87
63.78
80.12
75.08
59.58
54.13
66.49
65.24
CAL
61.12
58.12
78.12
68.78
74.56
67.12
89.78
85
77.12
64.12
81.42
78.12
56.49
50.93
61.77
58.94
GIP
60.61
57.41
79.32
75.78
79.55
75.28
91.21
86.73
77.49
67.47
82.15
78.31
60.38
54.98
68.72
66.45
Ours
58.66
55.44
84.19
81.01
79.96
77.21
94.44
86.23
77.29
67.82
84.77
78.49
64.35
55.07
69.04
67.91
4.2.2 EXPLANATION PERFORMANCE
We further compare our approach against subgraph- and global-based based interpretable methods in terms of explanation performance. We analyze the average results, and obtain four observations:
The accuracy of the explanations provided by our framework is competitive. We compare our approach with subgraph-based and dobbal-based interpretable methods, and the results are shown Table 2 Compared to subgraph-based interpretable methods, our approach achieves the highest explanation accuracy five of eight datasets and the second-best on the rest. Compared only global- interpretable baseline GIP, our approach also achieves comparably on most datasets.
Our framework provide the most similar explanation to the ground-truth. We compute the consistency between the explanations generated by different methods and the ground truth on two synthetic datasets, as shown in Figure a)). The consistency of our framework significantly higher than most subgraph- based and global- based interpretable methods.
Our framework maintains relatively stable decision paths under varying conditions for the same input. We compare path consistency between Bi-Tree and our model, the results are shown in Figure bb). It can be observed that our method achieves higher path selection consistency than the built ex explanation baseline of Bi-Tree on all datasets.
importance. This balance suggests that the model does not overly rely on a few decision paths.
8

---

Published as a conference paper at ICLR 2025
Table 2: Comparison of different methods in terms of explanation accuracy.
Method
ENZYMES
COLLAB
Graphiyydl
GraphFive
MultipleCycle
ProtGNN
2.12
80.31
= 2.45
69.12
3.12
71.23 2.56
80.67 2 2.78
$1.23 = 1.56
72.12
1.34
74.86 2:15
KerGNN
63.45 4: 2.45
60.78 a 2.12
79.12 1 1.45
88.12 0.778
84.11 1.12
85.78 0.34
75.67 1: 0.67
76.41
T-GNN
25.12
70:51
GIB
72.89
2.12
76.34
82.78 + 1.67
85.12
2:33
86.08 1.01
79.07
+ 0.56
80.74
2.54
GSAT
82.45 2.67
60.34
75.34 3.56
2.78 75.89
90.12
-.312
59.12
1.11
68.38
1.79
74.12
76.12
84.12
GNNExplainer
80.12
79.45
2.12
87.12 2.45
12.13
71.34
85.41
70.12 2.45
77.34 2.0.5
SubgraphX
81.67 2.45
71.23
1.01
75.89 1: 2.12
87.45 4: 3.12
76.34 H: 3.12
91.12 =: 2.01
69.50 4: 3.45
80.44 2,06
2.01
GIP
86.08 + 2.60
83.47 2.74
86.04 2.36
90.05 1.44
85.21 3.72
92.79 1.32
78.76 1.57
85. 15.16 2.68
Comparison
consistency
Censislency
0.75
0.25
Dure
GraphCyde
GraphFive
Corelelency
(b) Comparison of different methods in terms path consistency
Path importance
(c) Comparison different methads terss path importance
0.5
CN2YV25 060
MIOTERS
MUTAS
COILAS
DiepCrolee Wnge
ENCYIESS
D60
PIOTEING
NUTAS
COLLAS
OnenCyyle Drape wwweeeeleelaaaaaeooeeooo
Dalasets
Datasals
Figure 3: Explanation comparison on (a) consistency, (b) path consistency, (c) and path importance.
4.3 QUALITATIVE ANALYSIS
To comprehensively evaluate the interpretability of our proposed TIF, we conduct detailed analysis of the multi-gu muatt-g graph-level nodes and root-to-leaf paths it captures. To facilitate the observa- tion of relationships between structures at different granularities, we visualize our framework 's rea- soning process for the MultipleCycle dataset and use different colors to distinguish between various substructures, as illustrated in Figure 4 We observe that TIF effectively captures both local sub- structures in finer explanations and global graph patterns in coarser explanations, ensuring that key features at different granularities are preserved. The adaptive routing module dynamically selects the most informative paths through the tree based on multi-granular complexity. We also process the MultipleCycle dataset using the GIP model and compare the explanations it generates with those produced by our Framework, as illustrated in Figure 5 Compared to GIP, TIF's capability to span from fine-grade ane-grained local interactions coarse-graines sereeegrannedd global structures provides more transparent and interpretable decision making process, elucidating how various levels of graph information con- tribute final model predictions. More results of the explanation will be presented Appendix B
path
unselested path
The moat occurate explanation Reiativaly lesk optimal explanation
prediction
router
router
original graph
finer groph
graph
Figure Explanations generated by our framework on MultipleCycle.

---

Published as a conference paper at ICLR 2025
Somple From Closs "Pure Cycle"
A Somple From Closs "Pure Chain'
Somple From Class "Hybrid Cycle"
Our framewors
GIP
Our fromeoork
GDP
Our framework
GIP
Figure Explanation comparison generated by our framework and GIP on MultipleCycle.
(8) Accuracy with different Raties
Aocuracy with different Paths
(a) Classification Accuracy
(b) Explanation Accuracy
with different Modules
different Modules
100
100
Accurscy
75
Aocurasyy55
10
CeseficatonAcs, Exslanatio
ClarsficaionAes ExpanationAcs. Matric
Metric
PROTE TWbbtranCCcc
Datasets
Dalasets
Figure 6: Performance w.r.t (a) compression ra- tios, (b) paths per node.
Figure Performance w.r.t different modules.
4.4 ABLATION STUDIES
We conduct ablation studies to evaluate the impact of key components in our model: the compression ratio, the number of paths, and the routing complexity. More results will be shown in Appendix C.3
First, we analyze the effect of the compression ratio q (the ratio of nodes between layers). We vary q across {0.1, 0.2, 0.3, 0.5). We conduct experiments the D&D dataset. Results in Figure 6(a) show that both classification and interpretability accuracy decrease when is too high or too low. A low q retains noisy structures, while high q leads loss of critical information.
Next, we investigate the number of paths N by adjusting N to {2, 4, 8). We conduct experiments on the D&D. Results in Figure show that the best classification performance was achieved with 4 paths while using fewer paths constrained information fusion and more paths introduced noise. and noise control. Based the
Thus, paths offer effective balance between information explanation accuracy metric, it can be observed that the best interpretability was achieved with 4 paths while using fewer paths constrained information fusion and more paths introduced noise.
Finally, we examine routing complexity and perturbation effect by replacing the MLP-based rout- ing module with a simpler linear souucturewwithor the inter-layer adaptive routing mechanism, w/o IAR) and replacing the perturbation module Figure show that TIF outperforms the other two variants in both classification and interpretabil- ity tasks. This suggests that TIF's routing structure better captures complex relationships between paths, while its perturbation structure effectively captures and learns information that benefits both classification tasks and interpretability.
the perturbation module, w/o PM). The results
CONCLUSION
In this paper, we propose the Tree-like Interpretable Framework (TIF), a novel approach for graph classification that introduces multi-granular interpretability by transforming GNNs into hierarchi- cal trees. Unlike existing methods focused on local subgraph analysis or fixed granularity, TIF leverages iterative graph coarsening and perturbation mechanisms to capture diverse structural pat- terns across multiple granularities, ensuring more comprehensive understanding of both global and local dependencies. The adaptive routing module dynamically selects the most informative root-to- leaf paths, improving both classification performance and interpretability. Extensive experiments on synthetic and real-world datasets demonstrate the superiority of TIF in providing competitive predictive performance while significantly enhancing the multi-granular interpretability of decision- making processes. By addressing the overlooked challenge of gratulgranuarr interpretability, our work opens new avenues for the development of flexible, transparent, and robust graph neural net- works in real-world applications. In the future, we will further explore scaling the interpretation framework from medium-scale graphs to large-scale graphs at moderate computational costs.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
This work was supported in part by the CCF-Baidu Open Fund under Grant No. CCF-BAIDU OF202410, in part by the Hangzhou Joint Funds of the Zhejiang Provincial Natural Science Foun- dation of China under Grant No. LHZSD24F020001, in part by the Zhejiang Province High-Level Talents Special Support Program "Leading Talent of Technological Innovation of Ten- Ten-Thouss Talents Program" under Grant No. 2022R52046, in part by the Zhejiang Provincial Natural Science Foundation of China under Grant No. LMS25F020012, and in part by the advanced computing resources provided by the Supercomputing Center of Hangzhou City University.
REFERENCES
Oualid Aissa, Abderrahim Reffas, Abdelbasset Krama, Rabah Benkercha, Hicham Talhaoui, and Haitham Abu-Rub. Advanced direct torque control based on neural tree controllers for induction motor drives. ISA transactions, 148:92-10 104, 2024.
Maya Rechler-Speicheer Amir Globerson, and Ran Gilad-Bachrach. Tree-g: Decision trees testing graph neural networks. In AAAI Conference on Artificial Intelligence, pp. 11032-11042, 2024.
Clemens-Alexander Brust and Joachim Denzler. Integrating domain knowledge: using hierarchies to improve deep classifiers. In Asian conference on pattern recognition, pp. 3-16, 2019.
Fanchen Bu and Kijung Shin. On improving the cohesiveness of graphs by merging nodes: Formu- lation, analysis, and algorithms. In ACM Knowledge Discovery and Data Mining, pp- 117-129, 2023.
J Harry Caufield, Tim Putman, Kevin Schaper, Deepak R Unni. Harshad Hegde, Tiffany J Callahan, Luca Cappelletti, Sierra AT Moxon, Vida Ravanmehr, Seth Carbon, et al. Kg-hub-buildin and exchanging biological knowledge graphs. Bioinformatics, 39(7):btad418, 2023.
Kaixuan Chen, Jie Song, Shunyu Liu, Na Yu, Zunlei Feng, Gengshi Han, and Mingli Song. Dis- tribution knowledge embedding for graph pooling. IEEE Transactions on Knowledge and Data Engineering, 35(8))7998-7908 2022.
Vinícius Costa and Carlos Pedreira. Recent advances in decision trees: An updated survey. Artificial Intelligence Review, 5665):4765-4800, 2023.
Vinícius G Costa, Jorge Pérez-Aracil, Sancho Salcedo-Sanz, and Carlos Pedreira. Evolving inter- pretable decision trees for reinforcement learning. Artificial Intelligence, 327:104057, 2024.
Kaize Ding, Yancheng Wang, Yingzhen Yang, and Huan Liu. Eliciting structural and semantic global knowledge in unsupervised graph contrastive learning. In AAAI Conference on Artificial Intelligence, pp. 7378-7386, 2023.
Paul D Dobson and Andrew Doig. Distinguishing enzyme structures from non-enzymes without alignments. Journal of molecular biology, 337,4) 2003.
Alexandre Duval and Fragkiskos Malliaros. Higher-order clustering and pooling for graph neural networks. In ACM International Conference on Information and Knowledge Management, pp- 426 066-435,220 2022.
Sarah El-Dawy, Abdallah Hussien, Mostafa Ammar, and Ahmed El-Dawy. Safeguarding smart vehicles: Gnn-powered real-time ids for can networks. In International Conference on Machine Intelligence and Smart Innovation, pp. 228-231, 2024.
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In World Wide Web Conference, pp. 417-426, 2019.
Junfeng Fang, Wei Liu, Yuan Gao, Zemin Liu, An Zhang, Xiang Wang, and Xiangnan He. Evalu- ating host-hoe explanations for graph neural networks via robustness analysis. In Annual Confer- on Neural Information Processing Systems, pp.
2023.

---

Published as a conference paper at ICLR 2025
Aosong Feng, Chenyu You, Shiqiang Wang, and Leandros Tassiulas. Kergnns: Interpretable graph neural networks with graph kernels. In AAAI Conference on Artificial Intelligence, pp. 6614 6622, 2022.
Aasa Feragen, Niklas Kasenburg. Jens Petersen, Marleen de Bruijne, and Karsten Borgwardt. Scal- able kernels for graphs with continuous attributes. In Annual Conference Neural Information Processing Systems, pp. 216-224, 2013.
Andrea Ferigo, Leonardo Lucio Custode, and Giovanni lacca. Quality diversity evolutionary learn- ing decision trees. In Proceedings of ACM/SIGAPP Symposium on Applied Computing, pp- 425 432, 2023.
Vikas Garg. Generative ai for graph-based drug design: Recent advances and the way forward. Current Opinion in Structural Biology, 84: 2024.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Anmual Conference on Neural Information Processing Systems, pp. (025-1035, 2017.
Hao Hu, Wei Hu, An-Di Guo, Linhui Zhai, Song Ma, Hui-Jun Nie, Bin- Sin-Shan Zhou, Tianxian Liu, Xinglong Jia, Xing Liu, al. Spatiotemporal and direct capturing global substrates of lysine- modifying enzymes in living cells. Nature Communicationss 15(1):1465, 2024.
Muhammad Ifte Khairul Islam, Max Khanov, and Esra Akbas. Mpool: motif-based graph pooling. In Pacific-Asia Conference on Knowledge Discovery and Data Mining, pp. 105-117, 2023.
Ruyi Ji, Longyin Wen, Libo Zhang, Dawei Du, Yanjun Wu, Chen Zhao, Xianglong Liu, and Feiyue Huang. Attention convolutional binary neural tree for fine-grained visual categorization. In JEEE Conference Computer Vision and Pattern Recognition, pp. 10468- 10487, 2020.
Thomas N Kipf and Max Welling- Semi-super classification with graph convolutional net- works. In International Conference on Learning Representations, 2016.
Peter Kontschieder, Madalina Fiterau, Antonio Criminisi, and Samuel Rota Bulo. Deep neural decision forests. In International Conference on Computer Vision, pp. 1467-1475, 2015.
Biagio La Rosa. Explaining deep neural networks by leveraging intrinsic methods. arXiv preprint vrXiv:2407.12243 2024.
Zixun Lan, Binjie Hong, Ye Ma, and Fei Ma. More interpretable graph similarity computation via maximum common subgraph inference. IEEE Transactions on Knowledge and Data Engineering. 2024.
Ron Levie, Federico Monti, Xavier Bresson, and Michael M Bronstein. Cayleynets: Graph con- volutional neural networks with complex rational spectral filters. IEEE Transactions on Signal Processing, 67(1):97-109 2018.
Haoling Li, Jie Song, Mengqi Xue, Haofei Zhang, Jingwen Ye, Lechao Cheng, and Mingli Song. A survey of neural trees. arXiv preprint 2rX1v:2209.03415, 2022a.
Yiqiao Li, Jianlong Zhou, Sunny Verma, and Fang Chen. A survey of explainable graph neural networks: Taxonomy and evaluation metrics. arXiv preprint arXiv:2207.12599 2022b.
Zhixun Li, Xin Sun, Yifan Luo, Yanqiao Zhu, Dingshuo Chen, Yingtao Luo, Xiangxin Zhou, Qiang Liu, Shu Wu, Liang Wang, et al. Gslb: the graph structure learning benchmark. In Annual Conference on Neural Information Processing Systems, 2023.
Yixin Liu, Kaize Ding, Qinghua Lu, Fuyi Li, Leo Yu Zhang, and Shirui Pan. Towards self- interpretable graph-level anomaly detection. In Annual Conference on Neural Information Pro- cessing Systems, 2023.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Annual Conference on Neural Information Processing Systems, pp. 19620-19631, 2020.
12

---

Published as a conference paper at ICLR 2025
Siqi Miao, Mia Liu, and Pan Li. Interpretable and generalizable graph learning via stochastic atten- tion mechanism. International Conference on Machine Learning, pp. 25524-1553,, 2022.
Yao Ming, Panpan Xu, Huamin Qu, and Liu Ren. Interpretable and steerable sequence learning via prototypes. ACM Knowledge Discovery and Data Mining, pp. 903-913, 2019.
Meike Nauta, Ron Van Bree, and Christin Seifert. Neural prototype trees for interpretable fine- grained image recognition. In JEEE Conference on Computer Vision and Pattern Recognition, pp. -4933-14943, 2021.
Giannis Nikolentzos and Michalis Vazirgiannis. Random walk graph neural networks. In Annual Conference on Neural Information Processing Systems, pp. 16211-16222, 2020.
Saeed Rahmani, Asiye Baghbani, Nizar Bouguila, and Zachary Patterson. Graph neural networks for intelligent transportation systems: A survey. IEEE Transactions on Intelligent Transportation Systems, 24(8):8846-95 8885, 2023.
Eric W Stawiski, Albion E Baucom, Scott Lohr, and Lydia M Gregoret. Predicting protein function from structure: unique structural features of proteases. Proceedings of the National Academy of Sciences, 9765):3554-3958 2000.
Yongduo Sui, Xiang Wang, Jiancan Wu, Min Lin, Xiangnan He, and Tat-Seng Chua. Causal atten- tion for interpretable and generalizable graph classification. In ACM Knowledge Discovery and Data Mining. pp. 1696-1705, 2022.
Ryutaro Tanno, Kai Arulkumaran, Daniel Alexander, Antonio Criminisi, and Aditya Nori. Adaptive neural trees. In International Conference on Machine Learning, pp. 6166-6175, 2019.
Hao Tian and Reza Zafarani. Higher-order networks representation and learning: A survey, ACM SIGKDD Explorations Newsletter, 26(1):1-18, 2024.
Pascal Tilli and Ngoc Thang Vu. Intrinsic subgraph generation for interpretable graph based visual question answering. arXiv preprint wwXiv:2403./7644 2024.
Mathias Niemann Tygesen, Francisco Camara Pereira, and Filipe Rodrigues. Unboxing the graph: Towards interpretable graph neural networks for transport prediction through neural relational inference. Transportation research part C: emerging technologies, 146: 146:103946, 2023.
Lovro Vrček, Xavier Bresson, Thomas Laurent, Martin Schmitz, and Mile Šikić. Reconstruction of short genomic sequences with graph convolutional networks. In MIPRO ICT and Electronics Convention, pp. 403-409, 2023.
Alvin Wan, Lisa Dunlap. Daniel Ho, Jihan Yin, Scott Lee, Henry Jin, Suzanne Petryk, Sarah Adel Bargal, and Joseph E Gonzalez. Nbdt: Neural-backed decision tree. International Conference on Learning Representutions, 2021.
Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E Sarma, Michael M Bronstein, and Justin M Solomon. Dynamic graph cnn for learning on point clouds. ACM Transactions on Graphics, 38(5):1-12, 2019.
Yuwen Wang, Shunyu Liu, Tongya Zheng, Kaixuan Chen, and Mingli Song. Unveiling global inter- active patterns across graphs: Towards interpretable graph neural networks. In ACM Knowledge Discovery and Data Mining, pp. 3277-3288, 2024.
Zhengin Wu, Bharath Ramsundar, Evan N Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh Pappu, Karl Leswing, and Vijay Pande. Moleculenet: benchmark for molecular machine learn- ing. Chemical science, 9(2):513 2018.
Aikun Xu, Ping Zhong, Yilin Kang, Jiongqiang Duan, Anning Wang, Mingming Lu, and Chuan Shi. Than: Multimodal transportation recommendation with heterogeneous graph attention networks. IEEE Transactions on Intelligent Transportation Systems, 24(2):1533-1533 2022.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. In ACM Knowledge Discovery and
Data Mining, pp. 1365-1374, 2015.
13

---

Published as a conference paper at ICLR 2025
Di Yao, Haonan Hu, Lun Du, Gao Cong, Shi Han, and Jingping Bi. Trajgat: A graph-based long- term dependency modeling approach for trajectory similarity computation. In ACM Knowledge Discovery and Data Mining, pp. 2275-2285 2022.
Jun Yin, Chaozhuo Li, Hao Yan, Jianxun Lian, and Senzhang Wang. Train once and explain ev- erywhere: Pre-training interpretable graph neural networks. In Annual Conference on Neural Information Processing Systems, 2023.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Annual Conference on Neural Information Processing Systems, 2018.
Zhitao Ying. Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovee. Gnnexplainer: Generating explanations for graph neural networks, In Annual Conference on Neural Information Processing Systems, 2019.
Jiaxuan You, Zhitao Ying, and Jure Leskovec. Design space for graph neural networks. In Annual Conference on Neural Information Processing Systems, volume 33, pp. 17009-17021, 2020.
Junchi Yu, Tingyang Xu, Yu Rong, Yatao Bian, Junzhou Huang, and Ran He. Graph information bottleneck for subgraph recognition. In International Conference Learning Representations, 2020.
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Xgnn:
Towards model-level explanations of graph neural networks. In ACM Knowledge Discovery and Data Mining, pp. 430-438, 2020.
Hao Yuan, Haiyang Yu, Jie Wang, Kang Li, and Shuiwang Ji. On explainability of graph neu- ral networks via subgraph explorations. In International Conference on Machine Learning, pp. 12241-12252, 2021.
Hao Yuan, Haiyang Yu, Shurui Gui, and Shuiwang Ji. Explainability in graph neural networks: A taxonomic survey, IEEE Trans on Pattern Analysis and Machine Intelligence, 45(5):5782-5799 2022.
Yansheng Zhai, Xinyu Zhang, Zijing Chen, Dingyuan Yan, Lin Zhu, Zhe Zhang, Xianghe Wang, Kailu Tian, Yan Huang, Xi Yang, et al. Global profiling of functional histidines in live cells using mooel-mo photosensitizer and chemical probe relay labelling. Nature Chemistry, pp. 1-12, 2024.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Cheekong Lee. Protgnn: Towards self- explaining graph neural networks. In AAAI Conference on Artificial Intelligence, pp. 9127-9135, 2022.
Meng Zhao and Masoud Barati. Substation safety awareness intelligent model: Fast personal pro- tective equipment detection using gnn approach. IEEE Transactions Industry Applications, 59 (3):3142-3150, 2023.
Yongqiang Zheng, Jie Ding, Feng Liu, and Dongqing Wang. Adaptive neural decision tree for eeg based emotion recognition. Information Sciences, 643:119160, 2023.
Wang Zhili, Di Shimin, Chen Lei, and Zhou Xiaofang. Search to fine-tum tueettne pre-trained graph neural networks for graph-level tasks. In IEEE International Conference Data Engineering, pp- 2805-2819, 2024.
Zhiqiang Zhong, Yangqianzi Jiang, and Davide Mottin. On the robustness of post-hoc gnn explainers to label noise. arXiv preprint arXiv:2309.01706, 2023.
14

---

Published as a conference paper at ICLR 2025
A MORE IMPLEMENTATION DETAILS
A.1 DATASETS
The ENZYMES dataset, a collection of protein data obtained from the BRENDA database (Feragen ct al. 2013), involves the classification of enzymes into one of six primary EC categories. Detailed statistics of this dataset are presented in Table 3
The PROTEINS dataset, derived from the Dobson and Doig collection (Feragen et al. 2013). con- sists of protein data with the objective of distinguishing between enzymes and non-enzymes. Table provides detailed statistics this dataset.
The D&D dataset (Dobson & Doig 2003) comprises high-resolution protein structures taken from a non-redundant selection of the Protein Data Bank. In this dataset, nodes represent amino acids, and edge is formed between two nodes if they are less than 6 angstroms apart. Detailed statisties of the dataset can be found in T
The MUTAG dataset (Wu al., 2018) is designed for predicting molecular properties, with nodes representing atoms and edges corresponding to chemical bonds. Each graph carries a binary label that indicates its mutagenic effect. Table displass detailed statistics for the dataset.
The COLLAB dataset (Yanardag & Vishwanathan, 2015) focuses on scientific collaborations. In this dataset, each graph represents the ego network of a researcher, with nodes depicting the searcher and their collaborators, and edges signifying collaborations between researchers. The ego network of researcher can be labeled with one of three categories: High Energy Physics, Con- densed Matter Physics, or Astro Physics, reflecting the researcher's 's field of study. Detailed statistics of the dataset can be found in Table
The GraphCycle dataset (Wang et al. 2024 synthetic dataset. Initially, 815 Barabási-Albert graphs are generated communities, each with to 200 nodes. These BA graphs are then inter- connected to form two predefined shapes: Cycle and Non-Cycle. Edges between nodes in different communities are randomly added with probability between 0.05 and 0.15. Detailed statistics of the dataset are given in Table 3
The GraphFive dataset (Wang et al., 2024 is a synthetic dataset. Initially.8 Barabási-Albert graphs are generated communities, each consisting of 10 to 200 nodes. These BA graphs subsequently connected five predefined shapes: Wheel, Grid, Tree, Ladder, and Star. To estab- lish connections between nodes in different clusters, edges randomly added with probability between 0.05 and 0.15. Detailed statistics of the dataset can be found Table
MultipleCycle is delinnesi synthetic dataset. Specifically, first generate random first-level structures, which consist of either a cycle or non-cycle structure. For each node in this first-level structure, further expand it by randomly generating second-level structures, which can either be a cycle or non-cycle structure. Additionally, each node in the second-level structure is further expanded into one of four third-level structures: a triangle, star, trapezoid, cycle. The dataset consists of four predefined categories: Pure Cycle, Pure Chain, Hybrid Cycle, and Hybrid Chain, determined based on whether the majority of the nodes at each level form cycle-based or chain-based structures. This hierarchical generation method ensures that each graph exhibits multiple levels of nested structures, with connectivity and patterns varying across the different classes. Specific statistics of the dataset are shown in Table
Table 3: The statistics of real-world datasets.
#Avg, Nodes
#Avg. Edges
#Classes
#Graphs
ENZYMES
32.63
62. 14
6
600
D&D
284.32
715.66
2
1178
PROTEINS
39.06
72.82
2
111.
MUTAG
17.93
19.79
2
188
COLLAB
74.49
2457.78 78
3
5000
GraphCyele
297.70
697.18
2
2000
Graphliive
375.98
1561.77
5
5000
MultipleGraph
175.33
263.41
5000 4
15

---

Published as a conference paper at ICLR 2025
A.2 BASELINE
To simplify the Tree-like Interpretable Framework (TIF) and investigate the impact of its core com- ponents on model performance, we designed simplified model, named Bi-Tree,
A.2.1 SIMPLIFIED LEARNABLE GRAPH PERTURBATION MODULE
In Bi-Tree, the learnable graph perturbation module from TIF has been simplified to use a set of fixed perturbation terms for each layer. Specifically, while TIF allows each parent node to have independent learnable perturbation matrices, Bi-Tree defines set of fixed perturbation matrices p!!) for each layer 1, corresponding path i. The equation is follows:
1
1 PP) i= 2...,... M,
(19)
where (()) represents the clustering assignment matrix generated by the graph coarsening module, and (()) is the fixed perturbation matrix for path in layer I.
A.2.2 BINARY TREE STRUCTURE WITH LINEAR ROUTERS
Bi-Tree constructs binary tree structure, where each parent node has only two child nodes. Unlike TIF, which uses multi-level routers, Bi-Tree simplifies each layer's routers to linear transformations instead of multi-layer perceptrons (MLP). Specifically, the router computes the routing logits r based on the node embeddings 7
(!)
(
Wre L00 + by.ks
rk
(20)
where W., is the weight matrix for parent node k; and by is the bias term.
A.3 HYPER-PARAMETER SETTINGS
The hyper-parameters used in our framework include batch size, optimizer, learning rate, and epoch. Additionally, several key hyper-parameter parameters control the various loss terms in the model. Specifically, a1 controls the contribution of the edge prediction loss Link. which ensures the preservation of graph connectivity during the hicrarchical graph coarsening process. a2 governs the perturbation regularization loss Lperuurs. balancing similarity regularization Lsimilaiiy and diversity regularization Laivenity ensure the embeddings remain diverse yet close the original during the learnable graph perturbation module. adjusts the entropy regularization loss Centropy, which promotes diverse path selection in the adaptive routing module. The specific settings are provided in Table 4
Table 4: The statistics of parper-rrameterss setting.
ENZYMES
PROTEINS
MUTAG
COLLAB
GraphCyyde
GraphFive
MultipleGraph
Ratch Size
64
64
128
128
Optimizer
Adam
Adam
Adam
Adam
Adam
Adam
Adam
Adum
Learpiing Kate
0.0011
0.003
0.001
0.000
0.005
0.01
0.01
0.01
Epach
on/ /n//xg
0.3/12
0.3/0.2
A.4 MORE DETAILED EXPLANATION OF THE NOTATION
To enhance the readability of the formulas, we will provide a symbol table to further elaborate on the specific meanings of each subscript, offering detailed explanations for each subscript and its function. This will particularly focus how these subscripts are used in the tree structure model to represent different levels, nodes, and perturbation terms, helping readers better understand our notation system. For details, please refer to Table 7
T0 and 11
16

---

Published as a conference paper at ICLR 2025
Table 5: Node-related symbols.
Symbol
SubscriptSuperseriitt
Meaning and Role
The i-th node graph, representing a specific Node embedding matrix after graph convolution layer i, containing embeddings nodes. Node embeddings belonging node layer used for representing tree nodes.
1
2
2 (
1
Emnhecdings of node perturbed by the i-th perturbation at layer I. Final aggregated embedding for node at layer i, used for routing and decisions.
2
Table 6: Feature and weight-related symbols.
Symbol
Subserigu/Sppersrript
Meaning and
X
None
Input feature matrix, containing the original graph's is node features.
X(),A
I,
Feature matrix of mode & at layer I, describing its feature state. after applying the i-th perturbation at layer I.
X(1.00
M(S.1
Fenture matrix
X(+1)
[+1
Feature matrix the coursened gruph layer + 1.
W
Weight matrix of the graph convolution at layer i, used for learning graph structural features. Router weight matrices for node at layer I, used to compute path selection probabilities. terms the router mode at layer
W W
r,
Table 7: Graph structure-related symbols.
Symbol
Sabseript/Superccript
Meaning and Role
None
Adjacency matrix the original graph, representing node connectivity. Adjaceney matrix with self-loops added. improving the stability of graph convelution operations,
A
Adjacency matris the graph layer describing node connectivity in the coarsened graph.
Apodia
pooled, 20 1
Adjaceney matrix of the coarsened graph gencrated for selected path 3*a,
Table 8: Clustering-relaten symbols.
Symbol
Subseripu/Sppesccrittt
Meuning und Role
8:0
Clustering assignment matrix at layer I, representing the probabilities of nodes belonging to different clusters, Clustcring assignment matrix for at layer I.
S S0.
k. A
Clustering assignment matrix for node à under the 1-th perturbation at layer I.
Table 9: Loss and regularizzation-elate symbols.
Symbol
SubsrriptSaperscript
Meaning and Role
Last
link
Edge prediction loss, ensuring connectivity of the adjacency matrix during graph coarsening. Similarity regularization, constraining perturhed embedkings remain close the original embeddings. Diversity regularization, promoting differences between perturbed embeddings. Entropy regularization, encouraging diversity path selection. Cross- entropy loss, optimizing classificatin objectives.
Cuntaty
similarity
Larany
diversity
entropy
Lez
Lisal
total
Total loss fuaction, combining classiflcation, edge prediction, perturbation, and entropy losses.
Table 10: Path and routing-related related symbols.
Symbho
Sabserit/Superecript
Meaning and Role
Routing logits for node at layer I. used to compute path selection probabilities. Path selection probability for node layer/, representing the likelihood of selecting branch Optimal path index for node at layer I selected based the maximum probability. Pach set at layer 1, describing the paths associated with node i.
R 1
1,k
Table 11: Parameters and hyperparameters.
Symbol
Subseripu/Superscriit
Meaning Role
A
Weight of the similarity regularication term, controlling the strength of the i-th perturbation.
J
Noac
Weight of the diversity regularization term, controlling variation between penturbations.
Og.
1, 2,3
Woight coefficients for edge prediction, perturbation, and entropy regularization terms, respoctively. Number of perurbariin branches each node. Number of nodes in the current layer.
None
NN.
None
ge(
Number of clusters at layer I. Total number of layers in the
Z.
None
17

---

Published as a conference paper at ICLR 2025
B ADDITIONAL VISUAL EXPLANATIONS
B.1 ADDITIONAL VISUAL EXPLANATIONS FOR THE TREE STRUCTURE
To comprehensively evaluate the interpretability of our proposed TIF, provide example that contains the input graph, the root-to-leaf path, the coarsened graphs of each layer, and the final prediction. We conduct detailed analysis of the multi-granular graph-level nodes and root-to- leaf paths it captures. To facilitate the observation of relationships between structures at different granularities, we visualize our framework's 's reasoning process for the MultipleCycle dataset and use different colors to distinguish between various substructures, as illustrated in Figure g We observe that TIF effectively captures both local substructures in finer explanations and global structure in coarser explanations, ensuring that key features at different granularities are preserved. The routing module selects the most informative paths through the tree based on multi-granulat complexity.
Below, we will take Figure 8 as an example and provide detailed analysis of the entire process, starting from the input graph, progressing through each intermediate layer and the root-to-leaf path, and finally arriving at the output graph and prediction results and elaborate correlation between the coarsened graph at each layer and the ground-truth.
Firstly, the input graph is sample from the MultipleCycle dataset, and its category is "Hybrid Cycle". It corresponds to different ground truths at different levels of granularity. Specifically:
Its first-level structure is set as a cycle structure based on the ground truth at this granularity level, which determines its cycle attribute.
Its second-level structure is built on the first-level structure, configured as a mixed combination of cycle and non-cycle structures according to the ground truth this granularity level. The clockwise sequence is cycle, non-cycle, cycle, and cycle, which determines its mixed attribute. (for more detailed information on the dataset, please refer Appendix A.T)
Therefore, the final prediction for the input graph in this dataset requires the model determine:
whether its first-level granular structure is cycle or non-cycle.
whether its second-level granular structure represents mixed combination.
In other words, the model is expected to analyze and make determinations at different granularity levels for this dataset.
Secondly, when the input graph is fed into the model. After passing through series of graph convolution layers and being processed by the Graph Perturbation Module and Routing Module at the root node of the TIF, the model produces four finer graphs.
We can observe that the finer graphs clearly display the second-level structure of the input graph (in the figures, different colors used to annotate the nodes of the finer graphs, distinguishing the various second-level structures). From left to right:
The first finer graph shows second- structure starting from the top-left and proceeding clock- wise as cycle, non-cycle, cycle, and non-cycle (this structure is not clearly represented).
The second finer graph shows second-level structure proceeding clockwise as non-cycle, cycle (which is somewhat ambiguous and not purely cycle), cycle, and cycle.
The third finer graph shows clockwise cycle, non-cycle, cycle, and cycle.
The fourth finer graph shows clockwise as cycle, non-cycle, cycle, and non-cycle.
The model selects the third finer graph, which best reflects the structural information the input graph. From an interpretability perspective, this layer of finer graphs in the TIF tree model captures the second-level structural information of the input graph. Furthermore, the model selects the finer graph that most effectively represents the second-level structure of the input graph (clockwise: cycle, non-cycle, cycle, cycle). From the perspective of ground truth, the model selects the finer graph that closest to the ground truth structure and layout of the input graph at this granularity level.
18

---

Published as a conference paper at ICLR 2025
Subsequently, the selected finer graph undergoes another series of graph convolution layers and is processed by the Learnable Graph Perturbation Module and the Adaptive Routing Module at the next layer of the TIF. The model then produces four coarser graphs.
We can observe that the coarser graphs clearly capture the first-level structure of the input graph, which is the cycle structure. To illustrate this correspondence, we have used different colors in the figures to annotate the nodes of the coarser graphs, aligning them with the structures of the finer graphs from the previous layer. From left right:
The first coarser graph has two nodes extending outward as small structures from the cycle. The second coarser graph has three discontinuous nodes extending outward from the cycle.
The third coarser graph has two nodes extending outward as small structures from the cycle.
The fourth coarser graph has three nodes extending outward as small structures from the cycle structure, corresponding to the second-level structure depicted in the finer graph from the previous layer (three cycles organized consecutively).
The model selects the fourth coarser graph, which best represents the structural information of the input graph, as the root node of the TIF. From an interpretability perspective, this layer of coarser graphs in the TIF captures the first-level structural information of the input graph. Additionally, the model selects the coarser graph that not only most effectively represents the first-level structural information of the input graph but also retains the second-level structural information (clockwise: cycle, non-cycle, cycle, cycle, i.e., three cycles organized consecutively). From the perspective of ground truth, the model selects the finer graph that is closest to the ground truth structure and layout of the input graph at this granularity level, while also most accurately preserving the ground truth structural information from the previous granularity level.
Finally, at the root node of the TIF, the prediction is performed, and the model successfully identifies the data as "Hybrid Cycle". From interpretability perspective, the TIF effectively captures and explains the key attributes of the MultipleCycle dataset at two distinct granularity levels.
The second-level granularity characterizes the attributes of being purely cycle, purely non-cycle, mixed combination of cycle and non-cycle structures.
The first-level granularity identifies whether the structure is cycle non-cycle.
Based on these attributes at the two different granularity levels, the model successfully makes the final prediction for the input graph, completing the classification task.
In addition, the relationship between each coarsened graph and the ground truth lies in the fact that each coarsened graph in the TIF strives represent the critical structures constructed by the ground truth at the granularity level that the layer aims to explain for the input graph. That is, the coarsened graph obtained each level by TIF corresponds the ground truth at that level of granularity.
B.2 ADDITIONAL VISUAL EXPLANATIONS ON DIFFERENT DATASETS
In this section, we will present additional visualization outcomes of explanations on different datasets. We visualize the explanations generated by our framework on the PROTEINS and D&D datasets. The outcomes are presented in Figure 9 and Figure 10 For clarity of presentation, we only show partial sections of the full explanations for the finer graph granularity and moderate graph granularity. can be easily observed that TIF effectively captures both local substructures and global graph patterns, ensuring that key features at different granularities are preserved.
For example, the PROTEINS dataset, compared to the explanations for non-enzymes, the expla- nations for enzymes at the protein molecular level, the coarser graph granularity, display more long loops and tighter connections. At the amino acid level, or the moderate graph granularity, enzyme explanations show relatively fixed structural combinations. At the functional group level, or the finer graph granularity, enzyme explanations reveal denser connections at the active sites.
This observation offers new insights into differentiating graphs with varying properties, without specialized knowledge. In the future, we plan to collaborate with domain experts to perform more thorough analysis.
19

---

Published as a conference paper at ICLR 2025
The selected path(root-to-leat path) unselected path
original graph(input graph)
The most accurate explonation Relatively less optimal explonation
router
finer graph
router
Thumbnail
first-level structure
Cycle
Cycle
Non-Cycle Non-Oycle
coarser graph
second-level structure
Cycle
Cycle
Non-Cycle Non- Cycle
prediction
ground truth
Figure 8: An example which contains the input graph, the root-to-leaf path, the coarsened graphs of each layer, and the final prediction.
Enzymes
redivtte www.ennnnnnnnnttoooooooooo
Non-Eraymes
appenciioneetttt
Figure 9: Explanations generated by our framework on the PROTEINS dataset.
Wade with vere connections
Spectic atrccuudi contination
Ensymes
gresh grasdarity auplanatangguria viea)
maderds graah gramuarity aglaaattorigmmii vid)
conaar grazh grandari acdasuionn
Non-Eraymes
raciasation
Figure 10: Explanations generated by our framework on the D&D dataset.
20

---

Published as a conference paper at ICLR 2025
B.3 ADDITIONAL VISUAL EXPLANATIONS ON DIFFERENT METHODS
In this section, we observe that TIF effectively captures both local substructures in finer explanations and global graph patterns coarser explanations, ensuring that key features at different granularities are preserved. The adaptive routing module dynamically selects the most informative paths through the tree based on -ulti-granular complexity. We also process the same samples using the GTP, GSAT, and ProtGNN and compare the explanations it generates with those produced by Framework, as illustrated Figure [1] Our standard for explaining quality is the ability to accurately capture the important features and structural information at each granularity level. Different colors represent structural information learned or captured from the previous level of gramularity. Therefore, models like GIP only provide template based on the entire graph, the generated explanation is depicted in gray. Compared to those models, TIF's capability to span from fine-grained local interactions coarse-grained global structures provides more transparent and interpretable decision-making process, clucidating how various levels of graph information contribute to final model predictions.
A Somple From Closs "Pure Cycle"
A Somple From Closs "Pure Chain"
A Somple From Class "Hybrid Cycle"
GEP
QSAT
ProtGNN
GOAT
ProrCee
GSAT
ProtON
Figure 11: Explanation comparison generated by TIF, GIP, GSAT and ProtGNN on MultipleCycle.
C MORE DETAILED EXPERIMENTAL RESULTS
C.I PREDICTION PERFORMANCE WITH STD VALUE
To validate the predictive performance of approach, we compare framework with widely used GNNs and interpretable GNN models on real-world and synthetic datasets. We apply three independent runs and report the results along with their corresponding std values in Table I2
Table 12: Comparison of different methods in terms of classification accuracy (%) and Fl score (%) along with their corresponding standard deviations.
POYMES
PRITEINS
METAG
COLLAR
GraphCycle
Gropkliee
MattphCrole
Adc.
Ft
Adc.
F1
Alc.
F1
Anc.
F1
F1
Act.
F1
31
Alc
Ft
IGUNN
16
Net
35
54 18:001100
12
IN 1ea
440944 91
1345GLA7
201221211
12341124
262834211
102863335
25 22
48458253
12.911144
05351233
56123330
8212112
00128190
21 548835
P-GNN
16:14551
12333332
12.341.99
054551300
1512343
12128136
1334-179
14128156
GSAT
14112.441
(17514N)
51505430
62124431
85126431
0412662
01-31333
741541331 15766133
75366000
11.1--2
8474-290
77.8-436
07476311
75-165566
(8:26123)
5199-195
(8735822
54 19:01: 41 81 51791054 11:81:9%
4.:0-5.44
77:0:31
013063.1
9677-600
(5.851116
#8801631 0--11
C.2 EFFICIENCY STUDY
In this section, we analyze the efficiency of the proposed TIF framework and compare its efficiency with several interpretable baselines.
The modular design of TIF ensures efficient computation by progressively reducing the number of nodes through hierarchical coarsening, while controlled perturbations and adaptive routing maintain computational feasibility without compromising model diversity and interpretability.
21

---

Published as a conference paper at ICLR 2025
The running efficiency of the proposed TIF framework is analyzed as follows. In Table B present the time required to complete the training of each interpretable model. The dataset is divided into 10 equal subsets for 10-fold cross-validation, with the time taken by each model being the average of the times required for each fold. Specifically, in each iteration, one fold is held out as the validation set, while the remaining folds used for training. It should be noted that r-GNN requires an additional pre-training process that takes nearly 72 hours, which significantly impacts its overall computational efficiency. Therefore, the efficiency of r-GNN considerably lower than our framework. It can be seen that our framework is only slightly less efficient than the KerGNN model and GIP model. Given that our model outperforms KerGNN and GIP terms of prediction and explanation performance on the vast majority of datasets, as analyzed above, we believe that this slight additional time cost is justified.
Table 13: Time consumption of different methods. The table shows the time required (in seconds) finish training for each interpretable model on various datasets. "*" indicates the method requires an additional pre-training process which takes nearly 72 hours.
Methods
ENZYMES
D&D
COLLAB
MUTAG
GraphCycle GraphFive
ProtGNN
10245.65s
19312.87s
38021.49s
9239.15s
14396.76s
5022.81s
KerGNN
384.73s
1313.59s
1927.34s
401.34s
198.45s
458.22s
T-GNN
406.18s
966.94s
1747.55s
462.94s
283.74s
429.82s
GIB
711.57s
2923.67s
4681.74s
3107.31s
1159.82s
78s
GSAT
482.61s
1388.45s
2979.63s
828.19s
568.27s
649,34s
GIP
437.51s
1134.20s
2008.77s
452.26s
235.67s
423.87s
Ours
433.17s
1109.70s
2251.30s
503.18s
359.69s
488.15s
C.3
ADDITIONAL ABLATION STUDIES
C.3.1 IMPACT OF THE COMPRESSION RATIO
In this section, extend the analysis the impact of the compression ratio model perfor- mance, conducting experiments across datasets such as MUTAG, and PROTEINS. The results are presented in Figure 12 and Figure 13
As discussed the main text, we observe that both classification accuracy and interpretability ac- euracy tend to decline when the compression ratio is either too high too low. Specifically, low compression ratio may introduce noisy structures, thereby hindering the extraction of global information, while a high compression ratio might lead the loss of critical information.
C.3.2 IMPACT OF THE NUMBER OF PATHS
In this section, we present further results on the impact of the number of paths on model perfor- mance, covering datasets such ENZYMES, COLLAB, and FiveGraph shown in Figure 14
Consistent with the observations in the main text, the experiments reveal that the model achieves the best interpretability when the number of paths is set to four, while performance deteriorates when the number of paths is either too few or too many. Specifically, with only two paths, the model's choice space constrained, resulting in insufficient information fusion and an inability to fully leverage the diversity of the graph structure. Conversely, when the number of paths is increased to eight, although potential information channels expanded, additional noise introduced, making it challenging for the model to focus on the most critical features. Thus, setting the number of paths four strikes balance between information utilization and noise control, effectively improving the model's interpretability and stability.
C.3.3 IMPACT OF DIFFERENT MECHANISMS
In this section, further examine routing complexity and perturbation effect by replacing the MLP- based routing module with simpler linear structure(withor the inter-layer adaptive routing mech- anism, w/o IAR) and replacing the perturbation module(withour the perturbation module, w/o PM).
22

---

Published as a conference paper at ICLR 2025
Experiments conducted across various datasets such ENZYMES, COLLAB, and GraphFive, with results for classification accuracy and interpretability accuracy presented Figure I5
As shown in the figure, the experimental results indicate that the performance is slightly inferior when these mechanisms are used individually, while the combination of these mechanisms achieves the best performance. This superiority stems from the fact that the combination of these mechanisms helps to identify common characteristics in the graph from the perspective of global structure inter- actions, thereby effectively enhancing the model's ability extract global information and interpret key features in complex graph structures. Specifically, the hierarchical graph coarsening module iteratively aggregates components with similar features or close connections each layer, forming graph-level representations with higher levels of abstraction. Mcanwhile, the graph perturbation module integrates learnable perturbation mechanisms within each lateral layer, resulting in graph- level representations that better reflect the hierarchical structure's 's layer-wise characteristics. The combination of these mechanisms is crucial for improving the overall performance of the model.
C.3.4 IMPACT OF LEARNABLE GRAPH PERTURBATION MODULE
In this section, we analyze the impact of the Learnable Graph Perturbation Module on the model and its effectiveness in enhancing diversity. Based on TIF, we created two variants. The first variant re- places the original perturbation terms for each parent node with a of learnable perturbation terms shared across all parent nodes in each layer( the model by removing the branching structure entirely, effectively eliminating the Learnable Graph Perturbation Module(without the perturbation module, w/o PM).
version, SV). The second variant degrades
Experiments were conducted across various datasets, with results for classification accuracy and interpretability accuracy presented in Figure 16
As shown the figure, the experimental results indicate that TIF outperforms the other two vari- ants in both classification and interpretability tasks. This suggests that TIF's s perturbation structure effectively captures and learns information that benefits both classification tasks and interpretability.
(a) Classification Accuracy with different Ratios
(b) Explanation Accuracy with different Ratios
100
80
Accurary
60
30
0.2 Compression
Compression Ratio
Figure 12: The influence of different compression ratios on the model on MUTAG dataset.
(a) Classification Accuracy d different Ratios
Explanation Accuracy different Ratios
130
AccureoAAN
63
40
20
0.1
02
0.3
0.5
0.1
0.3
05
Compression Retio
Compression Ralioq
Figure 13: The influence of different compression ratios on the model on the PROTEINS dataset.
23

---

Published as a conference paper at ICLR 2025
(a) Classification Accuracy
(b] Explanation Accuracy
80
Classliicatonn
50
Number of Paths Node
Number Path Node
Figure 14: The influence different numbers of paths per node on the model's effectiveness.
(d) Exolanation Accuracy with different Modules
with different Madules
000
80
Recurscy (8)
600
30
Wio
Curs
Oum
ENZYMES
GraphFive
ENZYMES
COLLAB Datasets
GraphFve
Datasets
Figure 15: The influence of different modules on the model's effectiveness.
(a) Classification Accuracy with different Modules
(b) Explanation Accuracy
different Modules
100
100
75
Accuracy( (%)
75
Accuracy(S))
-0
50
25
25
Wib-VV
PRO PROTEINNSKIAACCOPPhyyyak Dalasets
Dalasets
Figure 16: The influence of the learnable graph perturbation module on the model's effectiveness.
24


Reviews:
[{"review_id": "gXgwBdqPMG", "reviewer": "Reviewer_ka23", "summary": "The paper proposes a TIF that transforms GNNs into hierarchical tree structures to provide multi-granular interpretability for graph classification tasks.", "questions": "The training process requires balancing various loss terms, but the paper offers limited guidance on optimizing this process.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "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?\n\nThe 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.\n\nThe 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.\n\n\nThere is no formal mathematical justification for why the multi-granular approach improves interpretability, nor are there guarantees regarding the optimality of the tree structure.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uU6iSPzUwN", "reviewer": "Reviewer_Yj5d", "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.", "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.\n2. 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?\n3. Regarding the explanation accuracy metric, can the softmax output from the GNN be considered as confidence? This lacks theoretical justification.\n4. Regarding the consistency metric, is the capability of graph kernels sufficient for distinguishing structural differences?\n5. Conducting explanation experiments on the Mutag dataset is necessary.\n6. Please provide visual explanations of algorithms like GSAT on the MultipleCycle dataset.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "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.\n2. The paper employs sufficient comparative algorithms to demonstrate the effectiveness of the proposed algorithm.\n3. 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.\n2. The evaluation metrics used to measure the effectiveness of model explanations are not sufficiently convincing.\n3. There is a lack of visual comparisons between the various interpretable GNNs, such as GSAT vs the proposed method.\n4. There is a lack of analysis regarding the algorithm's complexity and running efficiency.\n5. The proposed algorithms lack clear theoretical foundations and appear to be based solely on heuristic designs.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Bg8ejkeex3", "reviewer": "Reviewer_hGDZ", "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.", "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.\n2. An ablation study towards the graph perturbation module is recommended, to demonstrate the effectiveness of enhancing diversity.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The tree structure based interpretation method is intriguing and can further enlighten the GNN explanation field.\n2. The manuscript is well-organized and the proposed TIF framework is clearly introduced, making the whole work easy to understand.\n3. The experiments are sufficient and discussed in detail, verifying the effectiveness of the proposed TIF model.\n4. 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.\n2. 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.\n3. 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.\n4. 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.\n5. In Figure 7, the notations \"IAR\" and \"LV\" lack definition and the discussion of Figure 7 mismatches with it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)