Paradigm Shift of GNN Explainer from Label Space to Prototypical Representation Space
Authors: Jun Yin
Senzhang Wang
Ziluowen Luo
Peng Huo
Hao Yan
Hao Miao
Chaozhuo Li
Shirui Pan
Chengqi Zhang
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Networks
GNN Explanation Method
Vector Quantization
Primary area: interpretability and explainable AI

Abstract: Post-hoc instance-level graph neural network (GNN) explainers are developed to identify a compact subgraph (i.e., explanation) that encompasses the most influential components for each input graph. A fundamental limitation of existing methods lies in the insufficient utilization of structural information during GNN explainer optimization. They typically optimize the explainer by aligning the GNN predictions of input graph and its explanation in the graph label space which inherently lacks expressiveness to describe various graph structures. Motivated by the powerful structural expression ability of vectorized graph representations, we for the first time propose to shift the GNN explainer optimization from the graph label space to the graph representation space. However, the paradigm shift is challenging due to both the entanglement between the explanatory and non-explanatory substructures, and the distributional discrepancy between the input graph and the explanation subgraph. To this end, we meticulously design IDEA, a universal dual-stage optimization framework grounded in a prototypical graph representation space, which can generalize across diverse existing GNN explainer architectures. Specifically, in the Structural Information Disentanglement stage, a graph tokenizer equipped with a structure-aware disentanglement objective is designed to disentangle the explanatory substructures and encapsulate them into explanatory prototypes. In the Explanatory Prototype Alignment stage, IDEA aligns the representational distributions of the input graph and its explanation unified in the prototypical representation space, to optimize the GNN explainer. Comprehensive experiments on real-world and synthetic datasets demonstrate the effectiveness of IDEA, with the average improvements of ROC-AUC by 4.45% and precision by 48.71%. We further integrate IDEA with diverse explainer architectures and achieve an improvement by up to 10.70%, which verifies its generalizability.

Published as a conference paper at ICLR 2026
PARADIGM SHIFT OF GNN EXPLAINER FROM LABEL SPACE TO PROTOTYPICAL REPRESENTATION SPACE
Jun Yin Senzhang Wang Ziluowen Luo', Peng Huo Hao Yan', Hao Miao?,
Chaozhuo Li Shirui Pan", Chengqi Zhang²
'Central South University, Hong Kong Polytechnic University, *Griffith University, "National Super Computing Center, 'Beijing University of Posts and Telecommunications
yinjun20008csu. edu. en, swwangecsu. eew.geeussuuuuuueeeeeee en, 12lwdd1@csu edu. cn, huopengensco-tj-.. we edu. en, hao hao.miao@polly. edu. hk, 1 1 tichazhhc@bbpt.cco edu, en, wta.ee.a....aa.gggfiiii......... edu. au, chengi. zhang yu. edu.hk
ABSTRACT
Post-hoc instance-level graph neural network (GNN) explainers are developed to identify compact subgraph (i.e., explanation) that encompasses the most influen- tial components for each input graph. A fundamental limitation of existing meth- ods lies the insufficient utilization of structural information during GNN ex- plainer optimization. They typically optimize the explainer by aligning the GNN predictions of imput graph and its explanation in the graph label space which inher- ently lacks expressiveness to describe various graph structures. Motivated by the powerful structural expression ability vectorized graph representations, we for the first time propose to shift the GNN explainer optimization from the graph label space to the graph representation space. However, the paradigm shift is challeng- ing due both the entanglement between the explanatory and non-explanatory substructures, and the distributional discrepancy between the input graph and the explanation subgraph. To this end, we meticulously design IDEA universal dual-stage optimization framework grounded in a prototypical graph representa- tion space, which can generalize across diverse existing GNN explainer architec- tures. Specifically, in the Structural Information Disentanglement stage, graph tokenizer equipped with a structure-awan disentanglement objective is designed to disentangle the explanatory substructures and encapsulate them into explana- tory prototypes. In the Explanatory Prototype Alignment stage, IDEA aligns the representational distributions of the input graph and its explanation unified in the prototypical representation space, to optimize the GNN explainer. Comprehensive experiments real-world and synthetic datasets demonstrate the effectiveness of IDEA, with the average improvements of ROC-AUC by 4.45% and precision by 48.71% % We further integrate IDEA with diverse explainer architectures and achieve an improvement by up to 10.70%, which verifies its generalizability.
INTRODUCTION
Post-hoe instance-level graph neural network (GNN) explainer (Ying et al.; 2019 Luo al.) 2020
Schlichtkrull et al. 2021 Wang et al. 2021 Chen et al. 2023 Wang et al.) 2023b Zhang et al., 2023 Zhao et al. [023]] Chen et al. 2024) prominent research line reveal the opaque decision-
making mechanism of GNNs utilized in different domains (Fan et al. 2019 He et al. 2020b Wu al.] 2023b] Liu et al.] 2022 Yang al.) [2224b] Li et al. [020]] Mao et al. 2020). For each input
graph, post-hoc instance-level GNN explainer aims to identify a compact explanation subgraph that is the most influential to the prediction made by the target GNN model.
Most existing GNN explainers are developed under the label preserving framework (Zhao et al.) 2023 Zhang et al., 2023) as illustrated in Figure Within this framework, a variety of explainer
* "This research is initiated at Central South University and completed Hong Kong Polytechnic University. Cooresponning Author.
Our code and datasets available http:///giiiaii.ooo//yseammmmnmn

---

Published as a conference paper at ICLR 2026
architectures have been proposed. For example, GNNExplainer (Ying et al. 2019) determines the importance of edges and nodes through optimizable soft masks. PGExplainer (Luo et al. 2020) in- troduces a parametric graph generator capture global explanatory structures. D4Explainer (Chen 2023) combines the explanation search process with the denoising diffusion model (Ho et al.)
et al.
2020
V-In (Wang al., (023b) and ProxyExplainer (Chen al. 2024) incorporate the varia- tional graph auto-encoder (Kipf& & Welling) 2016) to improve the robustness of GNN explainer.
Despite promising achievements, the label preserving framework exhibits fundamental limitation in utilizing structural information to identify the explanation subgraphs, thus restricting the perfor- mance of GNN explainers. As shown in Figure [a), the label preserving framework optimizes the explainer by aligning the GNN predictions of the input graph and the explanation subgraph in the graph label space. Nevertheless, the graph label inherently lacks expressiveness to capture the characteristics of topological structures (Yang et al.) [224aa] Wang et al., 2023a). During the GNN explanation process, the topological structures are eritical, especially for complex graph domains
such molecular property prediction (Kazius al. 2005 Agarwal et al. 2023 Wu et al. 2023a
Funke et al. ) where multiple distinct substructures can correspond to the same label.
In order to mitigate the limitation of label preserving framework, we ad- vocate, for the first time, to shift the GNN explainer optimization frame- work from the graph label space to the graph representation space. Com- pared with discrete graph labels, the continuous graph representations can
(a). Label Preserving Framework
Input Graph
GNN Predictor
9G
Align
GNN Encoder
Graph Label Space
Pg
provide fine-graine anneggrined descriptions of
GNN Explainer
(b). Direct Alignment Framework
topological structures (Sun et al. 2020
Hg
Thakoor et al., 2022 Tian
Align
et al. 2022 Yang et al. (024a). Con- sequently, developing a graph rep- resentation space based optimization framework is promising to facilitate the GNN explainer to sufficiently uti- lize structural information during ex- planation process. As shown in Fig- Tb), a straightforward implemen-
Explanation
GNN Encoded Space
g ff.
Hg
Figure 1:
Overview of (a). Currently prevalent label pre-
serving framework and (b). Direct alignment framework in GNN encoded representation space.
tation of this blueprint is the direct alignment framework, which optimizes the explainer by aligning the GNN encoded representations of the input graph and the corresponding explanation. However, the direct alignment framework far from being an effective optimization framework for GNN explainers, due to the following two critical challenges.
The first challenge lies in the entanglement between the explanatory and non non- eenxeaallnttrry substruc- tures of the input graph. As revealed by causal inference theory (Wu et al. 2022, Sui et al.) 2022). the explanatory substructure causally determines the GNN prediction, while the non-explanatory counterpart merely exhibits statistical correlations. Due to the message passing mechanism (Kipf & Welling 2017 Veličković et al. 2018; Xu et al. 2019). the GNN encoded representation of the input graph invitably aggregates explanatory and non exn-exxlanatory substructures. Directly aligning the representations of the input graph and the explanation risks misleading the GNN explainer to non-explanatory substructures. The second challenge arises from the distributional discrepancy be- tween the input graph and its explanation subgraph within the GNN encoded representation space. Since the explanation subgraph is structurally reduced version of the input graph, the explanation representation naturally follows a deviated distribution in the GNN encoded representation space (Zhang et al. 2023 Chen al. 2024). Simplistically enforcing the representation similarity within the GNN encoded space tends to obscure the most influential subgraph rather than reveal it.
To overcome the challenges above, we propose IDEA, a universal dual-stage GNN explainer opti- mization framework grounded in a prototypical graph representation space, which is generalizable across various existing GNN explainer architectures. Specifically, IDEA consists of a Structural Information Disentanglement stage and an Explanatory Prototype Alignment stage. In the struc- tural information disentanglement stage, we design a hierarchical graph tokenizer equipped with a customized structure-awe aware disentanglement objective, to disentangle the explanatory substructures
2

---

Published as a conference paper at ICLR 2026
from confounding non-xxplanatory counterpart and then cluster them into prototypical representa- tions. In the explanatory prototype alignment stage, IDEA first unifies the GNN encoded represen- tations of the imput graph and the explanation in the prototypical representation space. to mitigate the distributional discrepancy. Subsequently, IDEA aligns the unified representational distributions to optimize the GNN explainer, enabling accurate identification of GNN explanations.
The main contributions of this work are summarized as follows.
We propose, for the first time, the paradigm shift of GNN explainer optimization framework from the graph label space to the graph representation space. Furthermore, we design IDEA, the first graph representation space based GNN explainer optimization framework.
We propose a hierarchical graph tokenizer equipped with structure-aware disentanglement ob- jective, to disentangle the explanatory substructures and encapsulate them into prototypical rep- resentations. We formulate a novel explanation identification strategy based on the prototypical representation space, which aligns the unified representational distributions of the input graph and the explanation, to circumvent the deviated distribution of the explanation subgraph.
Extensive experiments conducted real-world and synthetic datasets validate the effectiveness of IDEA compared with SOTA GNN explainers, with the average improvements of ROC-AUC by 4.45% and precision by 48.71% %. Meanwhile, the consistent superiority of the collaboration between IDEA and various explainer architectures demonstrates the generalizability of IDEA.
NOTATION AND PROBLEM FORMULATION
Notation. We use G (A, with the adjacency matrix A E NNN and the feature matrix X E IR to denote graph data of N nodes, where D represents the graph feature dimension. If node v, and node vj are connected, the element in the i-th row and the j-th column A, = and O otherwise. Without losing generality, in this work, we focus on the graph classification task (Hu 2022; Li al., 2017). since node classification can be converted into a computation graph classification problem (Chen et al.] 2024). For graph classification, each graph G' is associated with a label y E IR where denotes the total number of classes. The target graph neural network model f(-) has been well-trained to predict the class of any given graph G. Generally, the to-be- explained GNN model consists of the following three modules, the feature encoder (-).). the pooling
function Pool(-) (e.g., mean pooling and max pooling) (Ying et al. 2018 Du et al. 2021), and the task predictor f-(.). The GNN prediction procedure can be represented as tollows,
Hx fe(G), HG = Pool(Hx),
(p())),
(1)
where HN E Nxd is the matrix of d-dimensional node representations, HG E R1 xd is the pooled graph representation, and ý is the predicted label. Refer to Appendix A for notation summary.
Given a well-trained GNN model f(-) to be explained and an input graph G. the post-hoe instance-level GNN explainer -) aims to identify compact subgraph g" J) C G. which retains the most influential components during the GNN predicting procedure. Within the label preserving framework, the identified subgraph is reinforced to maintain the original prediction of G. Typically, the optimization objective of the label preserving framework is defined as the mutual information between the predictions of the input graph and the explanation subgraph, i.e. (g) (G)). In this work, we shift the GNN explainer paradigm from the label space to the graph representation space, to sufficiently utilize the structural information for GNN explanations.
Problem Formulation.
METHODOLOGY
Procedurally, IDEA consists of two successive stages, the Structural Information Disentanglement and the Explanatory Prototype Alignment, centered on the hierarchical graph tokenizer (HGTok- enizer). To tackle the structural entanglement problem, in the first stage, we design a structure-awar disentanglement (SAD) objective for HGTokenizer to stratify the explanatory and non-explanatory substructures. During the disentanglement process, the explanatory substructures are clustered into a collection of explanatory prototypes. In the second stage, based on the HGTokenizer and the pro- totypes, first unify the representations of the input graph and the explanation subgraphs into the prototypical representation space, to circumvent the distribution discrepancy problem. Afterwards, the GNN explainer is optimized by aligning the two unified representational distributions.
3

---

Published as a conference paper at ICLR 2026
HGTokenizer
Disentanglement Objective
Input Graph
Shallow Quantization
Uniform
Shallow Graph Quantizer A
GNN eredieta
Ys
1
2
6
YD
Hn
Q
Encoder
Quantized Residual H/y
Structure-Awareness Objective
1e(l">
1
2
3
5 6 ...
K
MLP Decoder
Dot Product
Node Representation Nl
Deep Graph Quantizer
Deep Quantization Q
0000Q"
Figure 2: Overview of the Structural Information Disentanglement in IDEA. The node representa- tion HN is decomposed into two quantization representations Q3 and Qh, by the cascade-connectee graph quantizers in HGTokenizer. The two quantizers aim to capture the explanatory and non- explanatory substructures respectively, following the guidance of the SAD objective.
3.1 STRUCTURAL INFORMATION DISENTANGLEMENT
In Figure we outline the overview of structural information disentanglement, which empowers the HGTokenizer with the ability to decouple the explanatory substructures from the non-explanatory counterpart. Technically, the HGTokenizer consist of two cascade-connected graph quantizers (Zeghidour et al., 2021) which take insights of the semantic tokenization (Rajput et al., 2023 Yin al. 2025). to compactly represent the structural information with discrete codebooks.
Given the node representation matrix HN. HGTokenizer approximates it based on the shallow and the deep graph quantizers. For the representation to be quantized, the graph quantizer looks up the nearest codeword in the codebook. Since the codebook scale K is significantly smaller than the total
number of nodes, it can serve as a collection of prototypes (Dai Wang 2025 Zhu et al., 2025) that succinctly summarizes the input representations. Using the representation h, of node as an example, the cascade quantization procedure of HGTokenizer formulated as follows,
S = (h&) = arg min Dh2 4), h4 h1 - gs..
(2)
qECs
4D GQD( = arg min D(,, q), of 95.; + 4..s
(3)
,ECp
where G-s(-) and GQD(.) denote the shallow graph quantizer and the deep graph quantizer, Cs and CD denote the codebooks of quantizers, q denotes the codeword inside, and D(.:)) is the distance metric for quantization. The deep graph quantizer takes the residual of the shallow one, in order to spontaneously dichotomize the fused representations encoded by the target GNN model.
The SAD objective utilized to optimize the HGTokenizer consists three terms, i.e., the structure- awareness objective, the disentanglement objective, and the standard quantization objective. The structure-awarenee objective Ls aims to recover the topological structures and node features based on the quantized node representations, enhancing the ability of HGTokenizer capture the graph structural characteristics. Formally, Ls is defined as follows,
Ls C- = A-000QQ0 -
- fa(
(4)
where Q" is the matrix of quantized node representations qf (-) I-) is the sigmoid function, and fa(-) a linear decoder. The disentanglemen objective LD enforces the prediction of the non-explanatory substructures towards uniform distribution, and guides the prediction of the explanatory substruc- tures towards the original prediction. Formally, Ln is defined as follows,
LD KL [[]] + CrossEntropy (ūni Ú),
(5)
where US and Un denote the GNN predictions the shallow and deep quantized representations, respectively. U, denotes the uniform distribution in the graph label space.
4

---

Published as a conference paper at ICLR 2026
By minimizing the Kullback-Leibe divergence between ts and Ug. IDEA reinforces the shallow graph quantizer to capture non-explane non-explanatory substructures that are unable to determine the GNN decision-making process. Mcanwhile, the second tern instructs the deep graph quantizer to encap- sulate the explanatory substructures that are more influential. Consequently, the codebook Cp inside GQD not only maintain the GNN prediction of the input graph, but also recover the graph topo- logical structures along with Cs. IDEA regards Cp as collection of explanatory prototypes which naturally induces a prototypical representation space for the GNN explainer optimization.
In addition, following the standard vector quantization process (van den Oord et al. al. 202I), the quantization objective L below is adopted for the basic quantization ability.
a 2017 Zeghidour
L HN - Q
Hence, the structure-aware disentanglement objective is defined as follows,
CSAD Lp + As + λo Lo. where Äs, Λy are the weighted
We present hyper-parameter analysis on the weights Äs and lo of the structure-aware disentanglement objective in Appendix C.T.
3.2 EXPLANATORY PROTOTYPE ALIGNMENT
Following the guidance of the SAD objective, the HGTokenizer disen- tangle the explanatory in- formation from the fused graph representation en- coded by the target GNN. The deep quantizer fur- ther encompasses a col-
Input Graph G
Input Graph Representation Hy
Assignment Distribution Purified Input Graph
HGTokenizer
Shallow GO
1 Encoder of Target GNN
P
Purified Imput Graph
GNN Explainer
Representation Hi
Minimize W, (Pg.P))
lection of prototypes to describe the explanatory information. To circum- vent the deviated distri- bution of the explana- tion subgraphs, we for- mulate novel explana- tion identification strat- egy on the basis of the prototypical representa- tion space. The overview of the explanatory proto- type alignment illus- trated in Figure 3
Deep GQ: Prototype
Assignment Distribution of Explanation
Explanation g
Explanation Representation H
Figure 3: Overview of the Explanatory Prototype Alignment in IDEA. The input graph representation Hg is first purified by the shallow graph quantizer, to eliminate the non-explanatory information. Then, the planation representation Hg and the purified input graph representation H'/ are implicitly projected into the prototypical space. At last, IDEA aligns the assignment distributions P' and Ps to optimize the explainer.
Given the targer GNN model f()) be explained and an input graph G, the explanation subgraph 9 is generated by (G, f), where z denotes the GNN explainer. In our implementation, typical probabilistic generator, which is well-investigated among the GNN explanation community (Luo) et al. 2020; Wang al. 202T 20236 |Wang & Shen 2023). is adopted the GNN explainer backbone. The implementation details are elaborated in Appendix B.3 Formally, we denote the GNN encoded representation of the input graph as HG and that of the explanation subgraph Hg-
To filter out the non-explanatory information from the input graph representation, we feed Ha to the HGTokenizer (i.e., the cascade of GQs and GQn). formulated as follows,
Hs.c GQs(Hc), H' = Ha Hs,G. Hp.G = GQD(H'),
(8)
where H5.G is the non-explanatory fraction the input graph representation and H'G is the purified input graph representation after removing H.... For the explanation representation H,, we directly feed it into the deep graph quantizer GQp, formulated as follows,
HD GQp (H,)
5

---

Published as a conference paper at ICLR 2026
Based on the quantization procedure of GQD, of the input graph H'g and the explanation representation Hg into the prototypical representation space, instead of explicit representation projection. To be more specific, the assignment distribution of the to-he-quantized representation (i.e., H' or Hg) over the explanatory codebook CD E IR 1 is able to indicate its location within the prototypical representation space. Formally, the assignment distributions corresponding to Hi and H, are measured as follows,
implicitly unify the purified representation
Pc Norm NormoDDH'',, (D(H), Pg Norm Norm(D(H,,
(10)
where P and P,, denote the assignment distributions and Norm(-) normalizes the quantization dis- tance to the probability value. Theoretical justification for this practice is presented in Appendix G
Since the assignment distributions P and Pa are identically measured over the implicit prototypical representation space, the distribution discrepancy of the explanation subgraph in the GNN encoded space ingeniously circumvented.
Subsequently, IDEA adopts the entropy-regee regulariee Wasserstein distance (Reshetova et al. 2024) between Pg and Pa as the optimization objective of the GNN explainer vb. The Wasserstein distance not only encourages the consistency between the two assignment probabilities Pg and P., but also insensitive to the sparsity issue of probabilistic distributions. For the stability of the explainer optimization, IDEA adopts the symmetric variant defined follow,
CIDEA = We(P'. Pg) + 2
W. W. P()) + W. Pg))
(11)
Pp)
min TEIT(P
SijSij +e Σ
Vij log Tij
(12)
i
[I(',, P3) denotes the transport polytope and S denotes the cost matrix defined as follows,
IIP', Pg) E III P'. 1 Pg). Sij (Pa.. -P
(13)
We implement IDEA as a dual-stage framework in order to avoid the counteraction between the optimization terms within LSAD and LIDEA. In Appendix F.1 we further investigate a variant of IDEA where the two stages are conducted jointly.
4 EXPERIMENT
To comprehensively validate the practicality of IDEA, conduct extensive experiments which designed to investigate the following research questions.
RQI: How effective IDEA compared to the label preserving based SOTA baselines?
RQ2: How generalizable IDEA collaborated with different explainer architectures?
RQ3: How does each component of IDEA influence the overall explanation performance?
Furthermore, present the hyper- hyper-paramene parameter analysis, the explanation visualization, and the time complexity analysis in Appendix C and respectively.
4.1 EXPERIMENTAL SETUP
Dataset. We evaluate IDEA and baselines on both real-world and synthetic datasets. The evalu- ated real-world datasets include Mutagenicity (Kazius et al. 2005). Benzene (Sanchez-lengeling ct al. 2020). Fluoride- -Carboyy "Sanchez-Lengellnng et 2000)). and Alkane- Alkane-Carbonyl (Sanchez- Lengeling al. 2020). The synthetic datasets is BA MMotifs (Luo et al. 2020).
Baseline. The baselines include SOTA post-hoc instance-level GNN explainers based on various techniques, i.e., GNNExplainer (Ying al., 2019), PGExplainer (Luo et al., 2020), GraphMask
(Schlichtkrull et al. 2021). ReFine (Wang et al. 2021), V-InFoR (Wang et al. 2023b), D4Explainer
CCen et al. 2023 MixupExplainer (Zhang al. 2023). ProxyExplainer (Chen et 2024).
Evaluation. Following the standard experimental settings (Luo et al. 2020 Chen et al. 2024). train 3-layer Graph Convolutional Network (GCN) model (Kipf & Welling 2017 each

---

Published as a conference paper at ICLR 2026
Table 1: Explanation performance (ROC-AUC 1) of IDEA and eight SOTA post-hoc instance-level GNN explainers on five datasets, in the form of isd. Average reports the mean result over all the evaluated datasets. improvement is defined as (IDEA Best-Basel BastttBBeeiinn)) /BeellttttBBBBBeeeeeeee BBest-Baseling superscript indicates the improvement is statistically significant with the p-value less than 0.01. Bold font and underline highlight the best and the runner-up performance, respectively.
The
Model
Mutagenicity
Benzene
Alkane
Fluoride
BA-2Motifs
Average
GNNExplainer
0.6155=0x0a
0.6863=am0z
0.5399 0.6884+ooms
0.5619#00ic
+
PGExplainer
0.7016aumm
0.8855
0.7446
0.809 I 10000
0.85942000m7
0.8000
GraphMask
0.6377 2000
0,5523
0.631 1 1001
0,5843 18843gomm 2002
0.61 100000s
0.6035
ReFine
0.68332omss
0.8720
0.7293 1000007
0.5600
0.61 15:1:::: 1100007
0.69 12: 100004
V-InfoR
0.6075
0.66422ammz
0.6500 1000102
0.6437 20.00
0.7755 1100004
0.6683110014
D4Explainer
0.7239 mos
0.773610000
0.7484 00000
0.7478100mm
0.708 1norm
MixupExplainer
0,5428
0.5399=amma
0.7385
+0,0043
0,5400
0.8355
H:00129
0.6393 +00005
ProxyExplainer
0.6948
0.8593=a.mz
0.9334
0.8804=onza
0.8717 =e000os
0. 0.8479 000006
Direct-Align
0.6567
0,8809
0.3562+00010
0,7988 =00042
0,8653=00cce
0.71 16:00006
IDEA
0.7379 #000004
0,9138
+000002
0.9355 +000000
0.8868
119541"=a.00"
0.8856 -0.0047
Improvement
5.17%
3.20%
0.22%
0.73%
9.45%
4.45%
Table 2: Explanation performance (Precision f) of IDEA and SOTA baselines across five datasets.
Model
Mutagenicity
Benzene
Alkane
Fluoride
BA-2Motifs
Average
GNNExplainer
0,073640000
0.1901 200024
0.0104gno0s
0.065220001
0.1333
0.0953an302
PGExplaincr
0.1038 10388000::
0.448440004
0.0761 gno0r
0.3253.:omm
0.6072ancmm
0.3122
GraphMask
0.0748+0aom
0.1373
0.0104=ncme2
0.0443=00029
0.2337=0c0a
0.1001 #0,006
ReFine
0.0833 (U833+oode +oooss
0,1951 0.1951==ome =00272
0.1304=n012
0.3027 =00017
0,5054=0c0sa
0.2434+00119
V-InFoR
0.1 11133
0.3195 20013
0.2374_0001
0. 1.1000n
0. 1.11899nnno anoos
D4Explainer
0,2087 k:owww
2oo5 0.3538 gomoo
0.0109 mo00s
0,3685 Loo000s
0.3153gnevrs
0.251141aom
MixupExplainer
0,0682+0000s
0,1385
2
0,2929=0mm3
0.3194=noos
0. 70.776++0000
ProxyFxplainer
0.3365 1ovonss
0.5908 1o
0.326 coooess
0.6229 noee
0.4050
Direct-Align
0,0805 touccon
0.5443 =00000
0.0109 a000s
0.4890
0.5872
0.3424
IDEA
0.4020" 1000007
0.7523 110000ss
0.4565 .10mm
0.6119
1000ss
0.7885'
0.6022 10000
Improvement
19.47%
27.34%
39.99%
25.13%
26.59%
48.71%
dataset, as the target model to be explained. To evaluate the explanation quality, we reformulate the explanation task as an edge binary classification task. Edges that belong to the expert-notated ground truth are labeled as positive, and negative otherwise. Hence, we adopt the ROC-AUC score
as the main metric to evaluate the explanation performance (Ying et al. 2019 Refer to Appendix B for the experimental details.
Luo et al. 2020
4.2 EXPLANATION PERFORMANCE (RQ1)
The evaluation result of IDEA and SOTA post-hoe instance-level GNN explainers is presented in Table [ in terms of the ROC-AUC score. Direct-Align corresponds to the direct alignment frame- work Figure [b), which optimizes the GNN explainer by directly aligning the GNN encoded representations of the input graph and the explanation.
The result sufficiently demonstrates the effectiveness of IDEA, which can consistently achieve the supreme performance on all the evaluated datasets. On average, the improvement of IDEA over the best baseline is 4.45%. For the Mutagenicity dataset, which is a complex molecular property predic- tion dataset, IDEA advances the explanation quality by up to 5.17%, compared to the benchmark- leading baseline PGExplainer (Luo et al. (020). Despite the primitive explanation identification strategy, Direct-Align achieves the second-tier performance among the evaluated explainers, show- casing the considerable potential of GNN explainer optimization framework based on the graph representation space. On the other hand, the inferiority of Direct-Align to the top-tier explainers, in- cluding PGExplainer, ProxyExplainer (Chen et al. 2024), and IDEA, justiffy the necessity of further advance on the direct alignment framework.
In light of the critical importance of precision in the GNN explanation evaluation, we further report the result of IDEA and SOTA baselines in Table 2 In general, the average precision of IDEA is 0.6022, achieving a significant improvement by 48.69% over the runner-up ProxyExplainer. Specif- ically, for the Alkane-Carbon dataset, whose ground-truth explanation is the union of alkane
7

---

Published as a conference paper at ICLR 2026
Table 3: Explanation performance (ROC-AUC 1) of IDEA with different explainer architectures.
Model
Mutagenicity
Benzene
Alkame
Fluoride
BA-2Motif's
Average
PGExplainer
0.8855a000
0.7446:0086
0.809 =
0.85
0. g0800
+IDEA
0.7379 1,000
0,9138 10000
0.9355 1iccon
0.8868 cooms
0.9541 inowc
0.8856' 1oowr
Improvement
5.17%
3.20%
25.64%
9.60%
11.02%
10.70%
ReFine
0.6833goms2
0.8720
0.7293:20077
g.5600
0.61 00022
0,6912
+IDEA
0.7832 ++00025
0.8759=aom
0.8428 +00001
0,5809
=0.0044
0.6861 +00001
0.7538'
#000007
Improvement
14.62%
0.45%
15.56%
3.73%
12,20%
9.0.5
V-InfoR
2..075.0mma
0.6642:ten12
0.6507=a0ms
0.6437
0.7755
0,6683 20.0..
+IDEA
0.5734gomm7
0.6713.uome
0.6776
0.6483nnom
0.7772-.0x2
0.6696 1000s
Improvement
-5.61%
1.07%
4.13%
0.71%
0.22%
1.38%
ProxyExplainer
0,6948 g000s
0.85932m012
0.9334
O 8804
0.87 0.8717
0.8479
+IDEA
0.7215' 100014
0.8864 1o00e
0.9509
0.8931
0.8930
0.8690 100081
Improvement 3.84%
3.15%
1.87%
1.44%
2.44%
2.48%
chain H2n+2) and carbonyl group (C=O), the improvement of IDEA is the highest over the five evaluated datasets, by up to 39.99%. This advancement demonstrates the ability of IDEA to explain graphs from complex domains. Similarly, the naive contestant Direct-Align maintains the moderate position among the evaluated GNN explainers.
4.3 GENERALIZABILITY ACROSS EXPLAINER ARCHITECTURE (RQ2)
We scrutinize the generalizability of IDEA by integrating various leading GNN explainer architec- tures and the evaluation result in terms of ROC-AUC is presented in Table In detail, PGExplainer [uo et al. 2020) adopts a vell-investigated subgraph generator based on the concrete distribution Maddison et al. 2017). ReFine (Wang et al.) 2021) implements subgraph generator for each graph class to capture the contrastive information. V-InFoR (Wang et al. 2023b) introduces a graph vaira- tional auto-encoder (GVAE) to refine the GNN encoded representations for robustness to structural corruptions. ProxyExplainer (Chen et al. 2024) merges a GAVE and a standard graph auto-encoder as the proxy generator to resist distribution discrepancy caused by the explanation subgraph.
The evaluation result sufficiently demonstrates that IDEA is generalizable across four different GNN explainer architectures, with the average improvement by 10.70%, 9.05%. 1.38%. and 2.48%, re- spectively. The greatest advancement is achieved by the IDEA-enhanced PGExplainer, whose av- erage performance (0.8856) even slightly exceeds the counterpart of the current leading baseline ProxyExplainer (0.8690). For ProxyExplainer that already exhibits strong performance, IDEA can further advance its explanation capacity. The IDEA-enhanced ProxyExplainer provides the best explanations for the Alkane-Carbon plainers. The sole exception occurs with the IDEA-enhanced V-InFoR on the Mutagenicity dataset, where the explanation performance drops by 5.61%. The possible reason for the degradation and the marginal improvement of IDEA-enhanced V-IRFoR is that V-InFoR is specialized for structurally corrupted graphs, while the evaluated graphs are uncorrupted.
and Fluoride-Carbony datasets, among all the evaluated ex-
4.4 ABLATION STUDY (RQ3)
In this section, we probe into the influence of each component in the IDEA framework. First, replace the Wasserstein distance in Eq II with the Kullback-Leibler divergence KL[P, Pa and denote the variant as IDEA-KL. Afterwards, to validate the effectiveness of the Explanatory Prototype Alignment stage, we implement two variants, ID-MSE and ID- InfoNCC, which optimize the GNN explainer by aligning the purified representation of input graph H'G and the explanation representation Hg. ID-MSE adopts the mean square error MSF (SS. H')) as the loss function, and ID- ID-IffoCEE adopts the InfoNCE loss function (He et al. 2020a) for in-batch contrastive learning. At last, we omit the Structural Information Disentanglement stage and denote the variant as EA. The evaluation result of IDEA and four variants is presented in Figure
We can draw the following conclusions according to the ablation result. First, the distributional dis- crepancy caused by the explanation subgraph deteriorates the explanation performance. By unifying the representations of the input graph and the explanation subgraph, IDEA and IDEA-KL signifi- cantly surpass the two variants ID-MSE and ID-InfoNCE that straightforwardyy align the disunified
8

---

Published as a conference paper at ICLR 2026
019541
0,9555
Explanation Performance (ROC-AUC)
0.95
ID MSE
IDEA-KL
IDEA
0.9125
0.00000
0.5935
0,9026
0,9148
0.8884
0,5770
0,9811
0,8856
0,8577
0.8587
0,855S
0,857
BA
0.85
MM141
0.8144
0,2926
0.80
0.7056
0,2370
0.75
0,7227
0.7186
B.7097
0,6820
0,70
0.65
0
0.60
Mutagenicity
Benzene
Alkane
Fluoride
BA-2Motifs
Average
Figure 4: Explanation performance (ROC-AUC 1) of IDEA and its four variants.
0.76
0.90
ROC-AUC
0.85
0.85
0.80
0,80
0.75
0.70
0.0
0.1
0.3
0.5
0.7
0.9
1.0
0.0
0.1
0.3
0.5
0.7
0.9
1.0
0.1
0.3
0.5
0.7
0.9
1.0
(a). Mutagenicity
(b). Benzene
(c). Alkane
0.96
0.875
ROC-AUC
0.8
0.92
0.825
0.90
0.800
0.0
0.1
0.3
0.5
0.7
0.9
1.0
0.0
0.1
0.5
0.7
0.9
0.3
0.5
0.7
0.9
(d). Fluoride
(e). BA-2Motifs
(f). Average
Figure 5: Explanation performance (ROC-AUC t) of the combination of the IDEA objective and the label preserving objective, Mutagenicity, Benzene, Alkane, Fluoride, and BA-2Motifs.
representations. Second, although EA is a competitive baseline, structural information disentangle- ment can further boost the explanation performance. EA inferior the unabridged IDEA, with an average performance gap by 0,0682. Third, compared with KL divergence, Wasserstein distance more suitable for GNN explainer optimization in the prototypical representation space. IDEA consistently outperforms IDEA-KI, with an average improvement of 3.33%.
Weighted Combination. As natural expansion, we integrate IDEA with the label preserving framework, and the mixed optimization objective is defined as the convex combination as follows,
LMix LIDEA + (1 a)) Lap 0 05 a 11
(14)
where E. denotes the label preserving loss. Typically, L.s is defined the mutual information be- tween the predictions of the input graph and the explanation subgraph, i.c., MI(9. ú.). The evalua- tion results in Figure&Jreves that the effectiveness of the integration depends on the specific dataset. For the Mutagenicity dataset, the integration with a equals 0.3 achieves a significant improvement over both IDEA and the label preserving framework. However, for the Benzene, Alkane, and Fluo- ride datasets, the weighted integration is inferior to both IDEA and the label preserving framework, which might be caused by the counteractive effect between the optimization objectives.

---

Published as a conference paper at ICLR 2026
1.0
Codebook Size
0.954
0.038
00930
05000
0.9105
0.122
0.0089
6.9131
Explamation Performince (ROC-AUC)
16
0,67K5
10-900
0
0.7000
0.79447
7.99
0.8
0.7500
0.71K
0.7378
0.720
07714
0.710
0,674
0.7
0.6
Mutagenieity
Benzene
Alkane
Fluoride
BA-2Motifs
Figure 6: Explanation performance (ROC-AUC t) versus the codebook size in IDEA framework, on Mutagenicity, Benzene, Alkane, Fluoride, and BA-2Motifs datasets.
4.5 INVESTIGATION ON CODEBOOK SIZE
We further investigate the impact of the codebook size, i.c., the number of codewords within the graph quantizer. As shown in Figure 6 the codebook size ranges among {4, 8, 16, 32, 48, 64). In general, a codebook of appropriate size can improve the explanation performance, since it serves as the foundation during structural information disentanglement and explanatory prototype modeling. For the Fluoride dataset, a codebook consisting of 8 codewords causes performance degradation of 0. 1299. Empirically, the recommended value set of K is {16, 32, 48), where IDEA achieves the best performance on most of the evaluated datasets.
5 RELATED WORK
Post-hoc Instance-level GNN Explainers have become primary approach to explain GNNs, with various methods proposed to identify the critical substructures responsible for predictions. GNNEx- plainer Ying et al.) 2019) perturbs graph components to estimate their importance. PGExplainer (Luo et al. (020) introduces parametric generator to capture global explanatory signals. Graph- Mask (Schlichtkrull et al. (2021) and ReFine (Wang al., 2021) advance explanations through edge selection and mualti- analysis, respectively. D4Explainer (Chen et al. 2023) adopts diffusion models to generate explanations from random noise. V-InFoR (Wang al. 2023b) and ProxyEx-
plainer CCen et al., 2024) employ variational autoencoders to enhance explanation robustness.
of Prototype-based GNN explanation methods aim to improve the intrinsic interpretability of GNNs. ProtGNN (Zhang et al. 2022) introduces prototype learning into GNNs, enabling prototypical sub-
graphs serve intuitive analogical explanations. PAGE (Shin al. 2024) extends this idea to model-level interpretability by constructing a latent prototype dictionary, offering explanations of the overall decision boundary. Dai & Wang (2025) further integrate prototype learning with self- explaining mechanisms, jointly optimizing prediction and interpretability.
CONCLUSION
We, for the first time, propose the paradigm shift of the GNN explainer optimization framework from the graph label space the graph representation space, and we design IDEA, the first GNN explainer optimization framework grounded in prototypical graph representation space. IDEA consists of structural information disentanglement stage, which disentangles and encapsulates the explanatory substructures into prototypes, and an explanatory prototype alignment stage, which aligns the rep- resentational distributions of the input graph and the explanation unified the prototypical space. Extensive experiments demonstrate the effectiveness and generalizability of IDEA.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGEMENT
J Yin and S Wang are supported by the National Natural Science Foundation of China (No. NNo.62572489.. C Li is supported by the Beijing Natural Science Foundation (No.L251037) and the Fundamental Research Funds for the Central Universities. In particular, this work is carried out using computing resources supported by HyperAl
REFERENCES
Chirag Agarwal, Owen Queen, Himabindu Lakkaraju, and Marinka Zitnik. Evaluating Explainabil- ity for Graph neural Networks. Scientific Data, 10, 2023.
Jialin Chen, Shirley Wu, Abhijit Gupta, and Rex Ying. D4Explainer: In-distribution Explanations of Graph Neural Network via Discrete Denoising Diffusion. In Proceedings of the International Conference on Neural Information Processing Systems, 2023.
Zhuomin Chen, Jiaxing Zhang. Jingchao Ni, Xiaoting Li, Yuchen Bian, Md Mezbahul Islam, Ananda Mondal, Hua Wei, and Dongsheng Luo. Generating In- In-Distribution Proxy Graphs for Explaining Graph Neural Networks. In Proceedings of the International Conference on Machine Learning. 2024.
Enyan Dai and Suhang Wang. Towards Prototype-Base Baased Self-Explainable Graph Neural Network. ACM Transactions on Knowledge Discovery from Data, 19(2), 2025.
Jinlong Du, Senzhang Wang. Hao Miao, and Jiaqiang Zhang. Networks. In International Joint Conference Artificial Intelligence, 2021.
Pooling Graph Neural
Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph Neural Networks for Social Recommendation. In Proceedings of The World Wide Web Conference, 2019.
Thorben Funke, Megha Khosla, Mandeep Rathee, and Avishek Anand. Zorro: Valid, Sparse, and Stable Explanations in Graph Neural Networks. IEEE Transactions Knowledge and Data Engineering, 2023.
Kaiming He, Haoqi Fan, Yuxin Wu, Saining Xie, and Ross Girshick. Momentum Contrast for Unsupervised Visual Representation Learning. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2020a.
Xiangnan He, Kuan Deng, Xiang Wang, Yan Li, Yong-Dong Zhang, and Meng Wang. LightGCN: Simplifying and Powering Graph Convolution Network for Recommendation. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval, 2020b.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising Diffusion Probabilistic Models. In Proceed- ings of the International Conference on Nearal Information Processing Systems, 2020.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Proceedings of the International Conference Neural Information Processing Systems, 2022.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical Reparameterization with Gumbel-Softman In International Conference Learning Representations, 2017.
Jeroen Kazius, Ross McGuire, and Roberta Bursi. Derivation and Validation of Toxicophores for Mutagenicity Prediction. Journal of Medicinal Chemistry, 48(1), 2005.
Thomas N. Kipf and Max Welling. Variational Graph Auto-Encoders. In Proceedings of the Inter-
national Conference Neural Information Processing Systems, 2016.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net-
works. In International Conference on Learning Representations, 2017.

---

Published as a conference paper at ICLR 2026
Chaozhuo Li, Senzhang Wang, Dejian Yang, Zhoujun Li, Yang Yang, Xiaoming Zhang, and Jianshe Zhou. PPNE: Property Preserving Network Embedding. In International Conference on Database Systems for Advanced Applications, 2017.
Xiangsheng Li, Maarten de Rijke, Yiqun Liu, Jiaxin Mao, Weizhi Ma, Min Zhang, and Shaoping Ma. Learning Better Representations for Neural Information Retrieval with Graph Information. In Proceedings of the ACM International Conference on Information & Knowledge Management, 2020.
Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. Pick and Choose: A GNN-based Imbalanced Learning Approach for Fraud Detection. Proceedings of the Web Conference, 2021.
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized Explainer for Graph Neural Network. In Proceedings of the International Conference on Neural Information Processing Systems, 2020.
Chris Maddison, Andriy Mnih, and Yee Whye Teh. The Concrete Distribution: A Continuous Relaxation of Discrete Random Variables. In International Conference on Leurning Representa- lions, 2017.
Kelong Mao, Xi Xiao. Jieming Zhu, Biao Lu, Ruiming Tang, and Xiuqiang He. Item Tagging for Information Retrieval: A Tripartite Graph Neural Network based Approach. In Proceedings of the International ACM SIGIR Conference on Research and Development in Information Retrieval, 2020.
Phillip E Pope, Soheil Kolouri, Mohammad Rostami, Charles Martin, and Heiko Hoffmann. Explainability Methods for Graph Convolutional Neural Networks. In IEEE/CVF Conference on Computer Vision and Pattern Recognition, 2019.
Shashank Rajput, Nikhil Mehta, Anima Singh, Raghunandan Hulikal Keshavan, Trung Vu, Lukasz Heldt, Lichan Hong. Yi Tay, Vinh Q. Tran, Jonah Samost, Maciej Kula, Ed H. Chi, and Mah- eswaran Sathiamoorthy, Recommender Systems with Generative Retrieval. In Proceedings the International Conference on Neural Information Processing Systems, 2023.
Daria Reshetova, Yikun Bai, Xiugang Wu, and Ayfer Özgür. Understanding entropic regularization in GANs. The Journal of Machine Learning Research, 25(1), 2024.
Benjamin Janchez-Lengeling Jennifer Wei, Brian Lee, Emily Reif, Peter Y. Wang. Wesley Wei Qian, Kevin McCloskey, Lucy Colwell, and Alexander Wiltschko. Evaluating Attribution for Graph Neural Networks. In Proceedings of the International Conference on Neural Information Processing Systems, 2020.
Michael Schlichtkrull, Nicola De Cao, and Ivan Titov. Interpreting Graph Neural Networks for NLP With Differentiable Edge Masking. In International Conference on Learning Representations, 2021.
Yong-Min Shin, Sun-Woo Kim, and Won-Yon Shin. PAGE: Prototype-Basee Model-Level Ex- planations for Graph Neural Networks. IEEE Transactions Pattern Analysis and Machine Intelligence, 46(10), 2024.
Teague Sterling and John J. Irwin. ZINC - Ligand Discovery for Everyone. Proceedings of the International Conference on Neural Information Processing Systems, 55(11), 2015.
Yongduo Sui, Xiang Wang, Jianean Wu, Min Lin, Xiangnan He, and Tat- Tat-Seng Chua. Causal At- tention for Interpretable and Generalizable Graph Classification. In Proceedings of the ACM SIGKDD Conference on Knowledge Discovery and Data Mining, 2022.
Fan- Yun-Yun Sun, Jordan Hoffmann, Vikas Verma, and Jian Tang. InfoGraph: Unsupervised and Semi- supervised Graph-Level Representation Learning via Mutual Information Maximization. In In- fernational Conference on Learning Representations, 2020.
12

---

Published as a conference paper at ICLR 2026
Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L. Dyer, Rémi Munos, Petar Veličković, and Michal Valko. Large-Scale Representation Learning on Graphs via Bootstrapping, In International Conference on Learning Representations, 2022.
Yijun Tian, Chuxu Zhang, Zhichun Guo, Xiangliang Zhang, and Nitesh V. Chawla. NOSMOG:
Learning Noise-robust and Structure-aware MLPs Graphs. In NeurlPS 2022 New Frontiers in Graph Learning Workshop, 2022.
Aaron van den Oord, Oriol Vinyals, and Koray Kavukcuoglu. Neural Discrete Representation Learn- ing. In Proceedings of the International Conference on Neural Information Processing Systems, 2017.
Laurens van der Maaten and Geoffrey Hinton. Visualizing Data using t-SNE. Journal of Machine Learning Research, 9(6),, 2008.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph Attention Networks. In International Conference Learning Representations, 2018.
Jihong Wang. Minnan Luo, Jundong Li, Yun Lin, Yushun Dong, Jin Song Dong, and Qinghua Zheng. Empower Post-hoc Graph Explanations with Information Bottleneck: A Pre-training and Fine-tuning Perspective. In Proceedings of the ACM SIGKDD Conference Knowledge Discovery and Data Mining, 2023a.
Senzhang Wang, Jun Yin, Chaozhuo Li, Xing Xie, and Jianxin Wang. V-InFR: A Robust Graph Neural Networks Explainer for Structurally Corrupted Graphs. In Proceedings of the Interna- fional Conference on Neural Information Processing Systems, 2023b.
Xiang Wang. Ying-Xin Wu, An Zhang, Xiangnan He, and Tat-Seng Chua. Towards Multi-Grained Explainability for Graph Neural Networks. In Proceedings of the International Conference Neural Information Processing Systems, 2021.
Xiaoqi Wang and Han Wei Shen. GNNInterpreter: A Probabilistic Generative Model-Level Expla- nation for Graph Neural Networks. In International Conference on Learning Representations, 2023.
Fang Wu, Siyuan Li, Xurui Jin, Yinghui Jiang, Dragomir Radev, Zhangming Niu, and Stan Z. Li. Rethinking Explaining GNNs via Non-parametric Subgraph Matching. In Proceedings of the International Conference on Machine Learning, 2023a.
Shiwen Wu, Fei Sun, Wentao Zhang, Xu Xie, and Bin Cui. Graph Neural Networks in Recommender Systems: A Survey. ACM Computing Surveys, 55(5), 2023b.
Ying-Xin Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. Discovering Invariant Rationales for Graph Neural Networks. In International Conference on Learning Representations, 2022.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference Learning Representations, 2019.
Ling Yang, Ye Tian, Minkai Xu, Zhongyi Liu, Shenda Hong, Wei Qu, Wentao Zhang, Bin CUI, Muhan Zhang, and Jure Leskovec. VQGraph: Rethinking Graph Representation Space for Bridg- ing GNNs and MLPs. In International Conference on Learning Representations, 2024a.
Ling Yang, Jiayi Zheng, Heyuan Wang, Zhongyi Liu, Zhilin Huang, Shenda Hong, Wentao Zhang, and Bin Cui. Individual and Structural Graph Information Bottlenecks for Generalization. IEEE Transactions Knowledge and Data Engineering, 36(2), 2024b.
Jun Yin, Zhengxin Zeng Mingzheng Li, Hao Yan, Chaozhuo Li, Weihao Han, Jianjin Zhang, Ruochen Liu. Hao Sun, Weiwei Deng, Feng Sun. Qi Zhang, Shirui Pan, and Senzhang Wang. Unleash LLMs Potential for Sequential Recommendation by Coordinating Dual Dynamic Index Mechanism. In Proceedingy of the ACM on Web Conference, 2025.
13

---

Published as a conference paper at ICLR 2026
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical Graph Representation Learning with Differentiable Pooling. In Proceedings of the International Conference Neural Information Processing Systems, 2018.
Zhitao Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNNExplainer: Generating Explanations for Graph Neural Networks. In Proceedings of the International Con- ference on Neural Information Processing Systems, 2019.
Neil Zeghidour, Alejandro Luebs, Ahmed Omran, Jan Skoglund, and Marco Tagliasacchi. Sound- stream: An end-to-end neural audio codec. IEEE/ACM Transactions Audio, Speech, and Language Processing, 31, 2021.
Jiaxing Zhang, Dongsheng Luo, and Hua Wei. MixupExplainer. Generalizing Explanations for Graph Neural Networks with Data Augmentation. In Proceedings of the ACM SIGKDD Confer- ence on Knowledge Discovery and Data Mining, 2023.
Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Checkong Lee. ProtGNN: Towards Self- Explaining Graph Neural Networks. In AAAI Conference on Artificial Intelligence, 2022.
Tianxiang Zhao, Dongsheng Luo, Xiang Zhang, and Suhang Wang. Faithful and Consistent Graph Neural Network Explanations with Rationale Alignment. ACM Transactions Intelligent Sys- tems and Technology, 14(5). 2023.
Zhiqiang Zhong, Yangqianzi Jiang, and Davide Mottin, On the Robustness of Post-hoc GNN Ex- plainers to Label Noise. In Proceedings of the Learning on Graphs Conference, 2023.
Zhijie Zhu, Lei Fan, Maurice Pagnucco, and Yang Song. Interpretable Image Classification via Non- parametric Part Prototype Learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Puttern Recognition, 2025.
14

---

Published as a conference paper at ICLR 2026
A
NOTATION
In Table
wc summarize the notations used throughout this manuscript and their descriptions.
Table Notations and corresponding descriptions.
Notation
Description
G
Graph instance
A, X
Adjacency matrix, node feature matrix Number of graph nodes Node feature dimension The i-th node Element at the i-th row, j-th column of adjacency matrix A Graph label, GNN prediction
N
D
Di
Aij
V.Y
C
Number of graph classes
fefeJJp
Graph neural network model, encoder of f. predictor of f Node representation matrix, graph representation vector Node representation of t; Post-hoc instance- level GNN explainer
Hn, HG
h
9.9"
Explanatory subgraph (i.e., explanation)
by
Label preserving loss of Regularization term
Xg
Weighted apper-parameter of Ω
GQs, GQD
Shallow graph quantizer, deep graph quantizer Codebook of GQs, codebook of GQD
Cs,CD CD
D
Distance metric of vector quantization Codeword, the nearest codeword
q, q"
Is 4D
The nearest codeword in GQs, the nearest codeword in GQD Residual representation after GQs quantization
h
Lo Cs. LD
Quantization objective, structure-await objective, disentanglement objective Quantization matrix Sigmoid function
Q
fa
Linear decoder
gs
GNN prediction of GQs quantized representation GNN prediction of GQp quantized representation Uniform distribution
jD
ue
Lsad
Structure- aware disentanglement objective
Aq As
Weighted hyper-parameter of Lo and Ls
Ha. Hg
Representation of original graph, representation of explanation
H'
Residual representation of H, after GQs quantization
P Po
Assignment probability of H', and He representation of explanation Entropy-regularized Wasserstein distance Transport polytope and cost matrix of W.
W.
II,S
LIDEA
IDEA optimization objective
LMix
Weighted combination of Las and LIDEa
Weighted parameter in LMix
B EXPERIMENTAL DETAIL
Here, we claborate the details of the evaluated datasets, baselines, and IDEA implementation.
B. DATASET
The dataset details are introduced as follows and the dataset statistics are summarized in Table 5
Mutagenicity Kazius et al. 2005) a collection of molecular compounds labeled for their ability to mutations (i.e., mutagenic vs. non-mutagenic), widely used in cheminformaties and toxicology for developing predictive models. Mutagenicity contains 4,337 molecule graphs with NO₂ and NH, chemical groups notated ground truth explanations.
15

---

Published as a conference paper at ICLR 2026
Table 5: The statistics of the evaluated datasets.
Statistic
Mutagenicity
Benzene
Alkane
Fluoride
BA-2Motifs
Graphs
4,337
12,000
4,326
8,671
1,000
Average Nodes
30.32
20.58
21.13
21.36
25.00
Average Edges
30.77
43.65
44.95
45.37
50.90
Node Features
14
14
14
14
10
GNN Accuracy
0.8300
0.9054
0,9620
0,9340
1.0
GT Explanation
NO2, NH₂
Benzene
Alkane C=O F C=O
Motif
Benzene (Agarwal al., 2023) a binary classification dataset of 12,000 molecular graphs sam- pled from ZINC15 (Sterling & Irwin 2015). The goal is to decide whether molecule contains at least one benzene ring. Within this dataset, the atoms that constitute the benzene ring serve as the ground-truth explanation. Multiple disjoint benzene rings are treated as separate explanations.
A Akane-Carbonyl (Agarwal et al. 2023) is a binary classification set of 4,326 molecular graphs. positive label marks a molecule that simultaneously contains an unbranched alkane chain and a carbonyl (C=0) group. The ground-truth explanation is defined as the arbitrary union of these two functional fragments present the structure.
Carrbonl (Agarwal et al. 2023) contains 8,671 molccular graphs. A molccule is la- beled positive only if it contains both fluoride atom (F) and carbonyl group (C=0). The expla- nation is defined as the arbitrary union of these two functional units found the structure.
BA-2Motif's (ing et al. 2019) is a synthetic binary class dataset designed to benchmark GNN explanation methods. Each graph is labeled by the presence of either house cycle motif, and the respective motif itself provides the ground truth explanation for that class.
We present the accuracy of the to-be-explained GNN model for each dataset in Table as well.
B.2 BASELINE
The evaluated baselines include eight SOTA post-hoc instance-level GNN explainers based on vari- ous search strategies. The details are introduced as follows.
GNNExplainer (Ying al., 2019) is GNN explainer based data perturbation that jointly masks edges and node features, then scores their contribution by searching for subgraph Gg that maximizes the mutual information with the model's overall prediction ÿ.
PGExplainer (Luo et al. 2020) masks graph topology and uses learnable neural network to assign edge importance scores, optimizing the same nuutual-informann
objective.
GraphMask (Schlichtkrull et al. 2021) learns an amortized classifier that predicts whether the edge can be dropped (replaced by a learned baseline) for every edge in every GNN layer, without changing the model output, yielding sparse post-hoc explanation.
ReFine (Wang et al. 2021) adopts pre-train and fine-tune strategy probe GNN decisions, delivering multi multi-granulane granulaaannn granularity insights into the model's reasoning process.
V-InfoR (Wang et al. 2023b) is a robust GNN explainer specialized for the structurally corrupted graphs, which employs the variational inference learn the robust graph representations and gen- eralizes the GNN explanation exploration to a graph information bottleneck (GIB) optimization task without any predefined rigorous constraints.
D4Explainer (Chnn al. 2023) a generative explainer for counterfactual and model-level expla- nations based on a discrete denoising diffusion model, which frames the explanation problem as distribution learning task for more reliable explanations with better in-distribution property.
MixupExplainer (Zhang et al., 2023) addresses the distribution shifting issue by mixing up the explanation with randomly sampled base graph structure.
Pxpainxplaieer (Chen al., 2024) extends the GIB by innovatively including in-distributed proxy graphs and derives a tractable objective function for practical implementations, where two graph auto-encoders are utilized generate proxy graphs.
16

---

Published as a conference paper at ICLR 2026
B.3 IDEA IMPLEMENTATION
Within the main experiment, we adopt a well-investigated subgraph generator as the backbone im- plementation of the IDEA framework. According the Gilbert random graph theory, an arbitrary graph G can be represented as a random graph variable, and each edge of G is associated with a binary random variable r to reveal its existence. Additionally, the existence of one edge con- ditionally independent of the other edges. Egj 1 means there is an edge (i.j) from to ey, otherwise Eij 0. Hence, an arbitrary graph G can be represented as follows,
GG) II p(Ea)) (4.5)
(15)
A common instantiation of the binary variable exj is the Bernoulli distribution Eij Bern(as) where 2ij = p(Eig = 1) is the probability of edge (i.j) existing in the random graph G. Since the Bernoulli distribution cannot be directly optimized, we introduce categorical reparameterization (ang et al. 2017) to Eij. The continuous relaxation of Eij can be formulated as follows,
Eij a (logu - log (1 u) - paj log 1 Dij
Lú
U Uniform(O, 1).
(16)
where T controls the approximation between the relaxed distribution and Bern( When 7 ap- proaches 0, the limitation of (6, is Bern(2:;).
According to Eq.(T6), the Bernoulli parameter Pi is associated with the parameter Pij. To enable multi-layer perceptron (MLP) compute Paj. The MLP takes
end-to-end optimization, the GNN node representation as input and concatenates the representations of two nodes u, Uj as the representation of the corresponding edge (i.j), which can be formulated as follows,
Pi MLP (heP((()llh)))
(17)
where [-I]-] is the concatenation operator. Based on = {uL [., = 1, ... .N and Eq. (16). we obtain the probability matrix M,, whose elements indicate the existence of the corresponding edges. Afterwards, we can sample the explanation g based on the probabilities in the matrix Mp as follows,
(Xs. As Mμ O A).
(18)
So far, we have derived the optimizable representation of utilized in IDEA. All experiments are finished on machine with 4 NVIDIA Geforce RTX 3090 24GiB GPUs.
B.4 STEP-BY-STEP BREAKDOWN OF HGTOKENIZER
Given the input embedding h4 E 11 the shallow codebook Cs E R xd and the deep codebook CD R xd the details of HGTokenizer process are elaborated follows.
Step 1. Feed the input embedding h; into the shallow quantizer. The shallow quantizer first calculates the pair-wise distance between ht and each codeword q E IR Ixd within the shallow codebook Cs. Afterwards, the shallow quantizer select the closest codeword to h; according to the K K-dimensional distance vector. Step is formulated by the formula g3.; = GQs(h,) = arg min D(g. h2) in Equation
Step 2. Calculate the quantization residual of the shallow quantizer, which is formulated by the
formula hy = h4 4 in Equation [
Step 3. Feed the residual embedding M/ into the deep quantizer, the detailed quantization process is the same as that in Step 1. The deep quantizer will select the closest codeword 4b.; = GQ) = arg min D(g, ht), as shown in Equation
Subsequently, the quantized representations d'ss and 9b.; provide by the shallow and deep quantizers are used to compute the disentanglement loss LD. The sum of them, i.e., of = 4S,, + in Equation B is used to compute the arructureawwareness awareness loss Ls.
C PARPAEER ANALYSIS
In Table 6 we summarize the optimal configuration of hyper-parameters in IDEA for each dataset.
17

---

Published as a conference paper at ICLR 2026
Table 6: The optimal configuration prrrmeeerameters in IDEA.
Hyper-parameter
Mutagenicity
Benzene
Alkane
Fluoride
BA-2Motifs
ID Epochs
10
10
5
ID Learning Rate
0.01
0.01
0.005
0.0005
0.001
EA Epochs
20
10
15
10
EA Learning Rate
0.0001
0.0005
0.001
0.001
0.0001
Batch Size
20
64
32
Codebook Size
16
32
64
32
48
0.738
0,7261
0.7261
0.7261
0.7261
0.7261
65
0,9129
0.9122
0,9129
0.9154
0.9138
0.736
0.7148
0.7311
0.9136
0.9136
0.9130
0.9138
0.9134
0.7360
0.7378
9,7378
0.7500
U.7378
0.732
0.9135
0.9134
0,9138
0,9151
0.9129
0.9132
0.750
0.728
0.7367
0.7285
0.7301
0.7269
0,7269
0.9130
0.9134
0.9134
0.9136
0.9129
0.9128
6.1
0.5
1.0
2.0
0.1
0.5
2.0
5.0
(a). Mutagenicity
(b). Benzene
3.9341
0.996
0.8849
0.9560
0.9345
0,9364
0.9342
0.9364
0,9389
0.9355
0,8996
0.8851
0,8868
0,8851
0.8864
0,899
0.888
0.9355
0.8873
0.9455
8.861
0.9864
0.9351
0.5477
0.9328
0.9500
0,8907
0.8500
0.8870
0,8890
0:888:6
0.335
0.886
0.9250
0,9368
0.9366
0.9328
0,8099
0,8897
0,590)
0,8399
0.8805
0.885
(c). Alkane
(d). Fluoride
Figure 7: Explanation performance (ROC-AUC 1) versus the weighted parameter Xo (y-axis) and As (r-axis) in the SAD objective, on (a). Mutagenicity, (b). Benzene, (c).Alkane, and (d). Fluoride.
C.I STRUCTURE-AWARE DISENTANGLEMENT OBJECTIVE
Here, we investigate the impact of the weighted parameters xo and Ag in the struttre-aware disen- tanglement objective defined as Eq
LSAD = Lp + As Cs \q Lq-
The evaluated result presented in Figure 7 As the weighted 5.0. we can notice that the optimal performance is more likely to be achieved when the objective weights are balanced, i.e., along the diagonal direction of the heatmap. For the Mutagenicity and
range from 0.1 to
Benzene datasets, the best performance is achieved by setting Às λo = 1.0. For the Alkane and Fluoride datasets, the best configurations weighted parameters are Às = 0.5, Ag and Às 0.1, 0.5, without severe unbalance.
D EXPLANATION VISUALIZATION
From Figure X to Figure II
we present the explanation visualization of the ground truth, IDEA, and four SOTA GNN explainers based on the lahel preserving framework.
18

---

Published as a conference paper at ICLR 2026
Table 7: Runtime (Second () of four native explainers with different architectures and the corre- sponding IDEA variants. Times is defined as IDEA/Nat:1n
Model
Mutagenicity
Benzene
Alkane
Fluoride
Average
PGExplainer
4.92
3.80
2.24
6.67
4.41
+IDEA
14.53
10.34
5.43
19.13
12.36
Times
2.95
2.72
2.42
2.87
2.80
ReFine
13.14
39.44
13.21
28.10
23.47
+IDEA
21.04
61.90
20.29
50.45
38.42
Times
1.60
1.57
1.54
1.80
1.64
V-InFoR
5.31
11.70
7.17
18.69
10.72
+IDEA
13.66
29.19
19.25
45.48
26.90
Times
2.57
2.49
2.68
2.43
2.51
ProxyExplainer
20.90
15.23
7.33
14.82
14.57
+IDEA
21.52
16.52
7.90
15.85
15.45
Times
1.03
1.08
1.08
1.07
1.06
1.0
Atom
Atort
Atom
0.8
Importance
0.6
0.8
(a). Ground Truth
(b). IDEA
(c). GNNExplainer
(d). PGExplainer
(e). V-InFoR
(1). ProxyExplainer
Figure 8: Explanation visualization of ground truth, IDAE, and four baselines on Mutagenicity.
As shown Figure g only IDAE assigns the highest importance score to NH2. PGExplainer and ProxyExplainer assign medium scores to NH2. V-InFoR identifies part of the NH₃ group, and GN- NExplainer fails to detect NH2. In Figure 9 IDEA, PGExplainer, and ProxyExplainer successfully identify the benzene ring. In particular, IDEA detects the rings within the molecule, while PGExplainer and ProxyExplainer notice only part of the second benzene ring. GNNExplainer and V-InFoR fail assign high scores to the benzene rings. For the Alkane dataset, IDEA and GNNEx- plainer identify the chlorine atom CI as the explanation, yet the other three explainers completely ignore the influential substrcutures. In Figure 11 only IDEA and V-InFoR can discriminate the explanatory structure from the confounding structures to some extent. The other three explainers assign nearly identical scores to all edges.
E TIME COMPLEXITY
In this section, we first provide a theoretical analysis of the time complexity of the IDEA framework. Then, report the runtime of diverse explainer architectures, incorporating with both the IDEA framework and the label preserving framework. Given the node presentation matrix Hy e Nxd HGTokenizer approximates it by graph quantizers, including matrix multiplication opera-
19

---

Published as a conference paper at ICLR 2026
Edge Impoeteenee
9.5
94
62
(a). Ground Truth
(b). IDEA
GNNExplainer
Alam
Armm
(d). PGExplainer
(e). V-InFoR
(f). ProxyExplainer
Figure 9: Explanation visualization of ground truth, IDAE, and four baselines on Benzene.
Alax
Bidex Inportaate
Ground Truth
IDEA
GNNExplainer
Abax
(d). PGExplainer
V.InFoR
ProxyExplainer
Figure 10: Explanation visualization ground truth, IDAE, and four baselines on Alkane.
tions and two argmin operations. The codebook within the graph quantizer belongs to a matrix in R kxd Hence, the time complexity of quantization distance
@p = NKd.
(19)
Since the time complexity of argmin is NK, the total complexity of HGTokenizer is
QHGT = (d
(20)
Therefore, the complexity of IDEA, including the structural information disentanglement and the explanatory prototype alignment, is derived as.
VDDE = (( + 1) + 3K(d+ 1) = O(Ndd).
(21)
According to Eq 21 the time complexity is linear the node number of input graph, the codebook size, and the hidden dimension target GNN.
In Table 7 report the runtime of four different GNN explainers and their counterparts shifted to the IDEA framework. One can note that the runtime of IDEA variants of the same magnitude, compared with the native explainer adopting the label preserving framework.
F SUPPLEMENTARY EXPERIMENT
F.1 CONJOINT OPTIMIZATION OF IDEA
In our main experiment, IDEA dual-stage framework, where the Structural Information Dis- entanglement and the Explanatory Prototype Alignment conducted separately. The dual stage
20

---

Published as a conference paper at ICLR 2026
Edge Improtuns
-04
(6). Ground Truth
(b). IDEA
[c). GNNExplainer
Atzi
PGExplainer
(e). V-InFoR
(i) ProxyExplainer
Figure 11: Explanation visualization of ground truth, IDAE, and four baselines on Fluoride.
Table 8: Explanation performance (ROC-AUC 1) of IDEA and the conjoint variant.
Model
Mutagenicity
Benzene
Alkane
Fluoride
Average
IDEA
0.7379
0.9138 0.5447
0,9319
0.8868 0.8349
0.8676
IDEA-Joint
0.4805
0.8725
0.6832
implementation not only reduces the difficulty of IDEA optimization, but also avoids the counter- action effect between the optimization objectives. To empirically validate the rationality of dual- stage IDEA, we further implement an IDAE variant IDEA-Joint where the two stages are conducted jointly. The optimization objective of IDEA-Joint is defined follows,
Loint LIDAE + ASAD LSAD.
(22)
with LIDEA and LSAD defined by Eq I1 and Eq] 7 respectively. In Table S we present the perfor- mance comparison between IDEA and the conjoint variant, within the same hyper-parameter search
range. We can notice the evident gap between IDEA-Joint and IDEA, which implies the difficulty of IDEA-Joint optimization, despite possible performance upper bound better than IDEA.
F.2 ROBUSTNESS TO LABEL NOISE
To investigate the robustness of the IDEA explainer label noise (Zhong et al. 2023); we perturb the information disentanglement stage by flipping the GNN prediction Eq and present the result in Table 9 For comparison, we evaluate the explanation performance of two typical explainers, i... GNNExplainer (Ying al. 2019) and PGExplainer (Luo et al. 2020 with the same setting of label noise. Specifically, the intensity the label noise ranges from 0.00% to 50.00%, with an interval of 5.00%. As shown by the result, the IDEA explainer stably maintains the high quality of the generated explanation, with the maximum performance degradation of 0,0076 and 0.0070 in the Mutagenicity and Benzene datasets, respectively. In contrast, typical GNN explainers based the label preserving framework, GNNExplainer and PGExplainer, suffer from severe performance degradation, which is x4.03 times and 22.58x times greater than that of IDEA.
G THEORETICAL JUSTIFICATION
During the explanatory prototype alignment stage, we adopt the assignment probability of the input representation (H'; or Hg) over the explanatory codebook Cp to reflect its location within the pro- totypical representation space. In this section, elaborate the justification of this practice. Within the explanatory codebook Cp, we have K prototype codewords {qi, 42, ....... -q } C. Rd, which ex- pand the prototypical representation space. Taking the prototype codewords {g) 42, qKk the
21

---

Published as a conference paper at ICLR 2026
Table Explanation performance (ROC-AUC 1) versus label noise intensity on Mutag and Benzene datasets. Amax presents the maximum performance degradation with noise intensity increasing.
Mutagenicity
Benzene
Noise Intensity
GNNExplainer
PGExplainer
IDEA
GNNExplainer
PGExplainer
IDEA
0.00%
0.6155
0.7016
0.7379
0.6886
0.8855
0.9138
5.00%
0.6140
0.6989
0.7358
0.6662
0,8856
0,9128
10.00%
0,6063
0,6824
0.7359
0,6505
0.8856
0.9135
15.00%
0,5937
0.6819
0.7363
0.6326
0.8860
0,9139
20.00%
0,5954
0.6810
0.7320
0.6149
0,5784
0.9132
25.00%
0,5965
0.6805
0.7366
0,5966
0,5931
0,9128
30.00%
0.6050
0,6802
0.7319
0,5788
0,5932
0.9128
50.00%
0.6048
0.6801
0.7303
0,5636
0.6302
0.9132
40.00%
0.6065
0.6798
0.7366
0,5431
0.6591
0,9131
45. 35.00%
0. 0.6048
0,6795
0.7327
0,5282
0.7033
0,9068
50.00%
0.6058
0.6791
0.7328
0,5056
0.7340
0.9130
A
0.0218
0.0225
0.0076
0.1830
0.3071
0.0070
anchors, the L2 distance between the input representation h and the anchor qu is
.kk = || 9x = h h + th lse 24
(23)
For 2 2, by subtracting 91 = ||/ 9111² we can derive the following equation
6pk P (9 au of 41) 2(gx "
(24)
which is equivalent the equation below,
(0x- 21)"² (Ta-11)²1 2
( 9h 9k - g6 91 + 91 px).
(25)
For = 2,3 stacking (gx- q1) induces the following equation in matrix formulation,
(g2 91) T
_h 92 q + P1 P22
(gs 7²
us 13 of + 41 4P3
h 2
(26)
(ĄK - 9T) which can be briefly noted as
4k of q1 + PK
Ah = b, A R(K-)xx) be ((-1).
(27)
Theoretically, the prototype codewords and the induced prototypical representation space are gen- erated by collection latent variables {21, 22. ... 21 C Ed' with d' < d. which objectively determine the explanatory substructures while being unobservable. Therefore, Eq 27 27mplies coun- terpart in the latent space Rd follows,
A'K'= =b, b,, A'E ((K U' E(K-11)
(28)
In this equation, when K 2 d' + 1, It' has a unique solution. Therefore, we adopt the assignment probability based on the quantization distance to indicate the location of the input representation, instead of training an additional projector.
We denote the unknown mapping function from the latent space Rd' to the prototypical space Rd as H. : Rdd + Rd. For two representations
E Rd, the corresponding representations in I2 are denoted as x' = -- (x)) and y/ H H-'(y). In our method, we minimize the difference between the assignment probabilities of x and over the prototypes (41, 82. 9K') ). in order to minimize the distance between x' and y' in the latent space. Theoretically, the strict validity this measurement lies in three conditions. First, K > d', which holds with large probability. Second, the prototype representations {q1. 92. ... 9g are linearly independent. As illustrated Figure 12 we present the cosine similarity of the codewords, demonstrating that the codewords approximately satisfy the linearly independent requirement. Third, the hypothetical mapping function H. is linear or can be approximated by linear functions.
22

---

Published as a conference paper at ICLR 2026
15
14
1.00
1.00
0.75
0.50
10
0,25
0.25
0.00
0.000
0.25
-0.50
0.75
0.75
10
11
12
13
14
15
10
12
13
14
15
(a). Mutagenieity: -0.05920.31
Benzene: -0.06220.51
1.00
0.75
0.50
0.25
0.25
0.00
-0.00
-0.25
0.25
-0.50
-0.50
0.75
(c), Alkane: 0.016+0.44
(d). Fluoride: 1.83e-0510.44
Figure 12: Pair-wised cosine similarity of codewords. The number behind the dataset name repre- sents Mean + Std.
Shallow Codebook Class 0
Deep Codebook Class 0
Shallow Codchook Closs
Drop Codebook
Class
Probabilit
Probbbiity
Probability
Polubiltyy
Shallow Codebook Class
Deep Codebook Class 1
Shalloo Codebook Class
Codebook
Class
Probability
Probathiln Iny
Probubcity
Probubiitt
(a). Assignment probabilities Benzene dataset
(b). Assignment probabilities on BA-2Motifs dutaset
Figure 13:
Average probabilistic distributions the shallow and deep codebooks (a). Benzene
dataset and (b). BA-2Motifs dataset.
H PROTOTYPE CASE STUDY
Assignment Probability. First, to explore the implicit relationship between the prototypical embed- dings (i.e., codebooks) and human-intelligibbe substructures, present the assignment probabilities
23

---

Published as a conference paper at ICLR 2026
1SSN Dimensian 2
Dimension 2
Initial State
t-SNE Dimension
1-NNE Dimension
fndinw Callock
Optimized State
i-SNE Dimemsion
SNE Dimession
(a). Mutagenicity
(b). Benzene
Figure 14: t-SNE visualization of codewords on (a). Mutagenicity dataset and (b) Benzene dataset.
Specifically, for real-world dataset Benzene and synthetic dataset BA- 2Motifs, we visualize the average probabilistic distributions of class and class over the shallow and deep codebooks. For the real-world dataset Benzene, the distributions of class 0 and class over the shallow codebook are similar, and the codeword 5 with the largest probability may correspond the most frequent non-explanatory substructure (carbon-chlorine bond). On the deep codebook, the distribution patterns obviously differ. For the deep codebook, the codeword 0 may correspond to the benzene rings which directly decides the labels of class 1, and the codeword 2 may correspond to the carbon-oxygen bond which is common in class 0. For the synthetic dataset BA-2Motif's the shallow distribution patterns of class 0 and class are also similar. The deep shallow distribution has two peaks, i.e.. codeword and codeword 5, which may correspond to the two kinds of motifs in BA-2Motifs. To sum up, the similar distribution pattern on shallow codebook and significantly dif- ferent patterns on deep codebook can indicate that the learned prototypes in codebooks are implicitly related to substructures.
distribution in Figure 13
t-SNE Visualization. Furthermore, we visualize the learned codewords in shallow and deep code- books based on t-SNE algorithm (van der Maaten Hinton 2008). shown by Figure 14 and Figure 15 the first row presents the t-SNE visualization of the initial codewords, and the second row presents that of the codewords after optimization, i.c., prototypes. We can notice that in the initial state, the shallow and deep codewords mix together without clear boundary. After optimization, the deep codewords are approximately separable from the shallow ones. The deep codewords prefer to cluster into mass, while the shallow codewords still distribute dispersedly.
LIMITATION
Accessibility to target GNN. According to the taxonomy of GNN explanation methods, the acces- sibility of the GNN explainer the target GNN be explained can be categorized into black-box, gray-box, and woiit--bxx. The black-box box accessibility takes the GNN model as an oracle and only requires the GNN predictions. On the contrary, the white-hox accessibility demands the permission
24

---

Published as a conference paper at ICLR 2026
Initial State
L-SNE: Dimension
L-NNE Dimnerssin
S-NE Dimension
I-SNE Dimension
Optimized State +SNE Diseesion 2
SSNE Denension 2
LSNE Dimension
&SNE Dimension
(a). Alkane
(b). Fluoride
Figure 15: t-SNE visualization of codewords on (a). Alkane dataset and (b) Fluoride dataset.
to the model internal parameters or the model gradients (Pope et al. 2019). Actually, IDEA requires the gray-box accessibility to utilize the GNN encoded representations, which limits the application of IDEA to completely black-box GNN models.
Approximately linear assumption on unknown mapping function H. In Appendix G
intro-
duce a unobserved function H that maps the latent space R2d our prototypical space Rd The strict validity of LIDEA in the explanatory prototype alignment stage necessitates that H is approximately linear least. Hence, a highly non-linear function might become potential limitation of IDEA.
FUTURE WORK
promising direction for future work is extend the proposed quantization- explanation framework from instance-level to model-level interpretability. One possibility is to construct global dictionary of reference quantization prototypes that summarizes the model's decision be- havior across the entire dataset. By analyzing how deep quantization patterns cluster in latent space, such a dictionary could reveal class-level structural regularities or decision boundaries, analogous to prototype-base global explanations in prior work. Furthermore, integrating hierarchical or dy- namic prototype discovery may help capture more nuanced variations quantized representations, enabling more comprehensive characterization of the model's reasoning process.
K
USE OF LARGE LANGUAGE MODELS
Large language models (LLMs) used in this work solely for auxiliary purposes. Specifically, they assisted in improving the accuracy of writing by identifying and correcting grammatical issues, refining terminology choices, well in suggesting appropriate color schemes for figure design. All research ideas, methodological developments, experiments, and the main body the manuscript independently conceived, conducted, and written by the authors.
25


Reviews:
[{"review_id": "fuIZSHhJRP", "reviewer": "Reviewer_dWjn", "summary": "This paper proposes a novel paradigm shift for post-hoc instance-level GNN explanation: moving the optimization target from the label space to a learned prototypical representation space. The authors identify two key obstacles in directly aligning GNN-encoded representations: (1) entanglement of explanatory and non-explanatory substructures, and (2) distributional mismatch between the original input graph and its sparse explanation subgraph.\n\nTo tackle these, the authors introduce IDEA, a two-stage optimization framework. In the first stage, a Hierarchical Graph Tokenizer (HGTokenizer) equipped with a structure-aware disentanglement (SAD) objective separates explanatory from non-explanatory components and clusters the explanatory parts into prototypes. In the second stage, assignment distributions of the purified input and explanation subgraphs over these prototypes are aligned via an entropy-regularized Wasserstein distance.\n\nExtensive experiments across both real-world and synthetic datasets demonstrate IDEA's superiority in ROC-AUC and precision, and its generalizability across various explainer backbones is also validated.", "questions": "1. Regarding Equation (5): Could you justify why minimizing CrossEntropy($\\hat{y}_D$, $\\hat{y}$) is valid given that $\\hat{y}_D$ is OOD with respect to the frozen predictor?\n2. Could you evaluate IDEA on larger or structurally more complex datasets to support scalability?\n3. Is it always appropriate to enforce the shallow quantized representation to produce a uniform prediction distribution (first term in Equation (5))?\n4. How are the prototype codebooks $C_S$ and $C_D$ initialized? Is the method sensitive to different initialization schemes?\n5. Can the authors provide qualitative or quantitative analysis of the learned prototypes? E.g., do deep prototypes align with known substructures (e.g., benzene rings)?\n6. Do shallow and deep prototypes exhibit distinguishable structural roles? Can visualizations or clustering be used to support this?\n7. Some baseline results seem lower than in original papers. Are all results averaged over multiple runs? Could standard deviations be reported?\n8. Hyperparameter tuning varies significantly across datasets (e.g., codebook size $K$). How practical is IDEA in scenarios without access to per-dataset tuning resources?\n9. In Table 3, IDEA with V-InFoR shows performance degradation on Mutagenicity. Can the authors explain why IDEA is incompatible in this case?\n10. The paper mentions that node-level tasks can be reformulated as graph-level tasks using computation graphs. Could the authors validate this claim with experiments, or clarify the scope as graph-level only?\n11. How does IDEA differ fundamentally from prior prototype-based GNN explainers? Is the key contribution the new optimization paradigm (label space → representation space), or the hierarchical disentanglement mechanism?", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The shift from label alignment to prototype-based representation alignment is novel and addresses a fundamental limitation in current GNN explainers.\n\n2. The two-stage IDEA framework is carefully designed. The use of shallow and deep vector quantization for disentangling, and Wasserstein distance for alignment, is both elegant and sound.\n\n3. Comprehensive experiments across diverse datasets and explainer architectures convincingly validate the effectiveness and generality of IDEA. Ablation studies, visualization, and extended appendix analyses (e.g., noise robustness, hyperparameter analysis) are particularly thorough.\n\n4. The paper is exceptionally well-written, and all figures and diagrams are highly informative and polished.", "weaknesses": "1. **Limited dataset diversity**: The method is only evaluated on five datasets. Testing on more diverse or larger real-world datasets (e.g., citation networks, program graphs) would strengthen the paper’s applicability.\n\n2. **Lack of clarity on prototype initialization**: The paper does not describe how the prototype embeddings (codewords in $C_S$ and $C_D$) are initialized. This is important for reproducibility and could affect convergence behavior.\n\n3. **Possible invalid supervision in Equation (5)**: The second term of Equation (5) uses CrossEntropy between $\\hat{y}_D$ and $\\hat{y}$. However, $\\hat{y}_D$ is generated from the deep quantized representations $q^\\*_D$, which are OOD with respect to the frozen GNN predictor. If the predictor was trained on original (non-disentangled) representations, its output for $q^\\*_D$ may not be meaningful.\n\n4. **Residual OOD inconsistency in optimization**: Although the paper claims that aligning in representation space avoids the OOD issue, Equation (5) still uses frozen GNN predictions $\\hat{y}$ as supervision for deep quantized vectors $\\hat{y}_D$, which remain out-of-distribution. This inconsistency needs to be addressed.\n\n5. **Incomplete related work**: The paper largely overlooks existing prototype-based explanation approaches. In addition to Dai & Wang (2025), key missing references include:\n   - ProtGNN (Zhang et al., AAAI 2021)\n   - PAGE (Shin et al., TPAMI 2022)\n   - Prototype-Based Interpretable GNNs (Ragno et al., IEEE TAI 2024)\n   - Towards Prototype-Based Self-Explainable GNN (Dai & Wang, TKDD 2022)", "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": "CbkXCBj5tn", "reviewer": "Reviewer_dsYU", "summary": "This paper identifies a limitation in existing post-hoc GNN explainers: they are typically optimized under a label-preserving framework, which aligns the GNN's label prediction for the original graph with that of the explanation subgraph. The authors argue that this label space is not expressive enough to capture the rich structural information GNNs use, especially when multiple distinct graph structures can map to the same label. The authors first demonstrate that a naive Direct Alignment in this space is ineffective due to two key challenges and provide a novel dual-stage optimization framework designed to overcome these challenges. Experiments show that IDEA outperforms state-of-the-art baselines.", "questions": "Please refer to the weaknesses above.", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "S1. The paper clearly and convincingly articulates a fundamental, yet often-overlooked, weakness of the dominant label-preserving framework.\n\nS2. The proposed IDEA framework, with its use of vector quantization for disentanglement and prototypical distribution alignment, provides a reasonable solution to both problems.\n\nS3. IDEA demonstrates consistent and significant performance gains over a wide range of SOTA eplainers on five datasets", "weaknesses": "W1. The entire framework's success hinges on the Stage 1 HGTokenizer correctly separating explanatory from non-explanatory information. This separation is enforced by the proxy objective $\\mathcal{L}_D$, which pushes the $Q_S$-based prediction to a uniform distribution and the $Q_D$-based prediction to the original GNN prediction. While this is a common proxy, it's not a guarantee. It's plausible that in some cases, the explanatory signal could be simple and captured by the shallow quantizer, while a complex confounder is relegated to the deep quantizer. \n\nW2. The theoretical justification in Appendix G for using assignment probability as a proxy for latent space location is insightful but relies on several strong, unverified assumptions. Specifically, it assumes that the (unobserved) mapping from the true latent space to the prototypical space is linear or can be approximated linearly. It is not clear how the method would perform if this mapping is highly non-linear, which is very possible in deep models. A discussion of this limitation or a more robust justification would be beneficial.\n\nW3. The paper relies on ground-truth-based metrics (ROC-AUC and Precision). While standard, GNN explanation evaluation also benefits from model-centric metrics that measure faithfulness (i.e., how much the model's prediction actually changes when the identified subgraph is removed or masked).", "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": "jKNH3S1VWQ", "reviewer": "Reviewer_GAVp", "summary": "The paper proposes IDEA, a two-stage framework for post-hoc, instance-level GNN explanations. It learns a prototype space of “explanatory” substructures and then aligns the explanation with the original graph in that prototype space using an entropy-regularized objective. Then the paper claimed and positioned as a shift from label-preserving objectives toward representation-level alignment, which aims to better capture fine-grained molecular motifs. After reviewing this paper, I am leaning towards a **weak accept rating (6), since parts of the technical formulation and experimental results, like the transport cost and the disentanglement guarantees, still need necessary clarification.**", "questions": "1. How is the prototype cost matrix $S_{ij}$ justified? Do you sort prototypes in some interpretable order (e.g., via clustering in latent space) before computing transport cost, or is the index order arbitrary? If it is arbitrary, why does the Wasserstein distance remain meaningful? \n\n2. When defining $P'_G$ and $P_g$, are these distributions aggregated at the graph level, node level, or edge level? How do gradients from the Wasserstein loss translate back into edge selection probabilities in the explainer so that you can evaluate edge-wise ROC-AUC and precision against ground truth substructures? Please clarify the pipeline. \n\n3. Does the shallow codebook actually avoid encoding predictive motifs? Can you quantify how predictive shallow vs deep codebooks are (e.g., accuracy drop if you only use shallow vs only use deep)? Right now LD encourages this split, but LS might leak class-relevant structure back into the shallow part. Some empirical evidence would strengthen the causal interpretation. \n\n4. Can you report mean ± std over multiple seeds for Tables 1–3? Current results seems can not assess robustness of the claimed 4–5% ROC-AUC gain and 40%+ precision gain.\n\n5. For the one negative case (IDEA hurts V-InFoR on Mutag), can you provide evidence on a corrupted-graph benchmark where V-InFoR is useful?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. The core pitch, “same label” is often too coarse for chemistry-level reasoning, and aligning explanations in a learned prototype space is a clean and intuitive step forward. \n\n2. The framework is conceptually coherent and is advertised as attachable to different explainer backbones, which increases practical impact.", "weaknesses": "1. **Wasserstein cost matrix feels underdefined.** The prototype alignment uses an entropy-regularized Wasserstein distance with cost matrix \\(S\\). Since the ordering of learned prototypes is arbitrary, for $S_{ij} = (i-j)^2\\$ has no obvious semantic meaning. Without a principled metric over prototypes, I am not fully convinced the transport cost is meaningful or stable. Please justify how the indices are ordered or provide an alternative cost.\n   \n2. **Granularity / supervision path.** The paper defines distributions $P'_G$ (for the “purified” original graph) and $P_g$ (for the candidate explanation subgraph) over explanatory prototypes, then matches them. It is not fully clear whether these are node-level, edge-level, or graph-level histograms, and how gradients from that distributional alignment are pushed back to edge scores that are later evaluated using ROC-AUC and precision against ground-truth substructures. A short dimensional walkthrough in the main text would make the method easier to trust.\n   \n3. **Disentanglement may leak.** The hierarchical tokenizer is trained so that the “shallow” codebook should become non-explanatory and the “deep” codebook should become explanatory, by pushing shallow predictions toward uniform and deep predictions toward the original GNN output. But the same quantized representation is also forced to reconstruct structure (adjacency and node features), which could let shallow codes still absorb predictive motifs.\n   \n4. **No std/var or statistical robustness report.** The tables report averages but no standard deviations across random seeds, and there is no statistical test. For some benchmarks the margins over strong baselines are a few percent. Without error bars it is difficult to judge how robust the reported ~4–5% ROC-AUC and ~49% precision improvements really are. \n\n5. **Scope of novelty claim.** The paper repeatedly frames IDEA as a “paradigm shift” from label-preserving explanations to representation-level alignment. I do think the formulation is interesting and practically useful. Still, prior methods like ProxyExplainer already started to address distribution shift between a full graph and an explanatory subgraph using learned proxy distributions, not just raw label matching. So personally, I think the final version should position IDEA as a principled instantiation of this direction, rather than implying absolute first. \n\n6. **(Minor) writing / notation issues.** Some notation is inconsistent or rushed. E.g. the paper alternates between $U^C$, $P_u$, and “uniform” when describing how shallow codes are encouraged to be non-predictive; it is not always obvious these are the same object. There are also a few typos and spots where a symbol appears before it is defined. Cleaning up these points would improve readability.", "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": "JCSwAso1YF", "reviewer": "Reviewer_u3DN", "summary": "The authors propose a paradigm shift from label space to graph representation space, which enforces the preservation of encoded information when generating local explanations, consequently providing more accurate and robust explanatory subgraphs.", "questions": "- Why are both shallow and deep quantizers necessary? Is a single quantizer insufficient for your framework? Providing clearer motivation for this dual-quantizer design would significantly enhance the paper's clarity.\n- The explanation of vector arithmetic operations in Equations 2 and 3 needs more detail. Could you provide a step-by-step breakdown of these operations?\n- Given that you position deep quantization as the relevant source of explanation with reference quantization serving as prototype explanation, could this framework potentially be extended to model-level explanations? Are there promising directions for future work in this area?\n\nPlease refer to the weaknesses along with the questions.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The proposed method is model-agnostic and can be applied to other post-hoc local explanation methods on graphs. Experimental results demonstrate consistent performance improvements across multiple datasets. Moreover, the method exhibits robust performance compared to other baselines under noisy conditions.\n- While existing literature has primarily focused on label space, there has been limited research on leveraging informative features from graph representations for explanations. In this regard, this paper presents novelty by introducing a new perspective on graph explainability.\n- The paper is well-written and easy to understand.", "weaknesses": "- There is a lack of justification for why both shallow and deep quantizers are necessary. While the authors explain that shallow quantization handles non-explanatory substructures and deep quantization captures explanatory substructures, the transition from quantization to disentanglement (similar to MixupExplainer) feels abrupt when first reading the methodology section, which weakens the clarity of presentation. I recommend that the authors provide additional explanation and stronger justification for this design choice.\n- The representation in Equations 2 and 3 is a little bit complicated. And there is insufficient explanation of the vector arithmetic operations. The authors are recommended to provide a detailed explanation about equations 2 and 3. Additionally, shouldn't L_D (rather than L_S) in lines 205~7  be the loss that enforces the prediction of the non-explanatory subgraph towards a uniform distribution? (In Figure 2, only y_S is related to the uniform distribution). \n- Lack of theoretical analysis. \n\n- Minor issue: in Table 2, rank information is not provided.", "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)