LogicXGNN:  Grounded Logical Rules for Explaining Graph Neural Networks
Authors: Chuqin Geng
Ziyu Zhao
Zhaoyue Wang
Haolin Ye
Yuhe Jiang
Xujie Si
Venue: ICLR 2026 Poster (2026)
Keywords: Graph Neural Networks
Interpretability
Explainability
Neural-symbolic
Logical Rules
AI for Science
XAI
Primary area: interpretability and explainable AI

Abstract: Existing rule-based explanations for Graph Neural Networks (GNNs) provide global interpretability but often optimize and assess fidelity in an intermediate, uninterpretable concept space, overlooking the grounding quality of the final subgraph explanations for end users. This gap yields explanations that may appear faithful yet be unreliable in practice. To this end, we propose LogicXGNN, a post hoc framework that constructs logical rules over reliable predicates explicitly designed to capture the GNN's message-passing structure, thereby ensuring effective grounding. We further introduce data-grounded fidelity ($Fid_D$), a realistic metric that evaluates explanations in their final-graph form, along with complementary utility metrics such as coverage and validity. Across extensive experiments, LogicXGNN improves $Fid_D$ by over 20% on average relative to state-of-the-art methods while being 10-100 times faster. With strong scalability and utility performance, LogicXGNN produces explanations that are faithful to the model's logic and reliably grounded in observable data.

Published as a conference paper at ICLR 2026
LOGICXGNN: GROUNDED LOGICAL RULES FOR EX- PLAINING GRAPH NEURAL NETWORKS
Chuqin Geng
Department of Computer Science McGill University; University of Toronto
gmag magi i ca; brngiinggeg@maii.. www.ooooooooooooo.oooo.oooo
Ziyu Zhao McGill University
Zhaoyue Wang McGill University
Haolin Ye McGill University
Yuhe Jiang
University of Toronto
Xujie Si
Department of Computer Science University of Toronto
six0cs.toronte edu
ABSTRACT
Existing rule-based explanations for Graph Neural Networks (GNNs) provide global interpretability but often optimize and assess fidelity in intermediate, uninterpretable concept space, overlooking grounding quality for end users the final subgraph explanations. This gap yields explanations that may appear faithful yet be unreliable in practice. To this end, we propose LOGICXGNN, a post-hoc framework that constructs logical rules over reliable predicates explic- itly designed to capture the GNN's mnessage-passing structure, thereby ensuring effective grounding. We further introduce data-grounded fidelity (Fidp), a re- alistic metric that evaluates explanations in their final-graph form, along with complementary utility metries such as coverage and validity. Across extensive experiments, LOGICX GNNI improves Fidp by over 20% on average relative to state-of-the-art methods while being 10-100x faster. With strong scalability and utility performance, LOGICXGNN produces explanations that are faithful to the model's logic and reliably grounded observable data. Our code is available at https::/ tww...c.tttoocoomooooomm a engeng 23/ 33/LogicXGNN
INTRODUCTION
Graph Neural Networks (GNNs) have emerged as powerful tools for modeling and analyzing graph- structured data, achieving remarkable performance across diverse domains, including drug discovery (Xiong et al.) [2021] Liu al.) 2022 Sun et al.) 2020), fraud detection (Rao al.] 2021), and recommender systems (Chen et al. 2022). Despite their success, GNNs share the black-box nature inherent to neural networks, posing challenges deployment in high-reliability applications such as healthcare (Amann et al., 2020: Bussmann et al. 2021b.
To address this, numerous explanation methods have been developed uncover the drcision-makinn mechanisms of GNNs. However, most existing approaches are limited to providing local explanations tailored to specific input instances rely on input-feature attributions for interpretability (Pope et al.) | .Yng al.] 2019 Vu & Thai 2020 Lucic et al.) [022 Tan et al.) 2022). A complementary line of work focuses on global explanations that characterize overall model behavior using rule-based approaches (Xuanyuan et al. 2023 Azzolin et al.) 2023 Armgaan et al. 2024). These methods map relevant substructures into an intermediate, abstract concept space and then optimize logical formulas over these concepts to produce class-de dlas--iicriminative explanations. For interpretability. the abstract concepts are subsequently grounded in representative subgraphs, which serve as the final explanations presented to end users.

---

Published as a conference paper at ICLR 2026
GraphTrail's explanations on Mutagenicity
Existing methods compute fidelity in their internediate, uninterpretable concept space.
U3 V 2178 = Class 1
Fidelity is computed in the GraphTrail's internal concept space: 66%
Concept space
Representative subgraphs of concepts
grounding
mapping
T 13
T178
N-6
Graph space
Chenically invalid:
We evaluate Fidelity in the final grounded form.
A hydrogen aton cannot have valency of 4.
(a) Existing methods compute fidelity the concept space.
(b) High fidelity yet meaningless explanations.
Figure 1:
Existing methods such GRAPHTRATI compute fidelity in an uninterpretable concept space while overlooking the grounding quality of final subgraph explanations presented to end users.
While intuitive, this grounding step can introduce unfaithfulness and unreliability: methods may (i) reconstruct invalid subgraphs by mismatching node attributes and concept structure, or (ii) select plausible yet poorly representative subgraphs as post hoc rationalizations. This echoes critical concern in explainable Al (Laugel et al., 2019 Lipton 2018). where explanations may reflect learned artifacts rather than genuine data evidence. More importantly, these approaches optimize and evaluate fidelity-the degree to which explanations align with model predictions-in their intermediate concept space, neglecting issues with the ill-grounded subgraph explanations ultimately presented, as illustrated in Figure [(a) This oversight risks producing explanations that appear highly faithful yet fail reflect concrete, observable patterns in the data, thereby undermining both usability and trustworthiness for end users (Camburu et al. 2020). For example, although the state-of-the-ar
method GRAPHTRAIL (Armgaan et al., 2024) reports 66% fidelity score in its concept space on the Mutagenicity dataset (Debnath et al. 1991). its final explanations are entirely imgrounded: not single explanation subgraph is chemically valid, and none matches an instance in the dataset (see Figure ((b)p. To address this gap, we propose a framework for evaluating rule-based explanations in their final, grounded form. Our approach centers on data-grounded fidelity (Fidp). a metric that assesses fidelity directly on the final subgraph explanations, supplemented by utility metrics such as coverage and validity. Under these criteria, the performance existing methods drops dramatically, highlighting the need for explanations that are both faithful and truly interpretable.
To this end, we propose LOGICXGNN, a novel post hoc framework for constructing explanation rules over reliable predicates. These predicates are explicitly designed to capture the structural patterns induced by the GNN's message-passing mechanism, providing a solid foundation for reliable grounding. As result, LOGICXGNN not only generates rich set of representative subgraphs but also learns generalizable grounding rules for each predicate, addressing unreliable grounding in existing methods. Furthermore, our data-driven approach is highly efficient and demonstrates superior scalability on large real-world datasets, advantages we validate through extensive experiments. In summary, our key contributions are:
We identify a key issue in existing blsed explanation methods for GNNs: they optimize and evaluate fidelity in an intermediate, uninterpretable concept space without proper data grounding, which undermines usability and trustworthiness. To quantify this effect, we introduce Fidp, computed directly on the final-graph explanations presented end users.
We introduce LOGICXGNN, a novel framework for generating faithful and interpretable logical rule-based explanations for GNNs. Unlike existing methods, LOGICXGNN pre- serves structural patterns from message passing, enabling effective grounding that produces not only more representative subgraphs but also generalizable grounding rules.
2

---

Published as a conference paper at ICLR 2026
Our experimental results show that LOGICXGNN significantly outperforms existing meth- ods, achieving an average improvement of over 20% in Fidp while being 10-100x faster in runtime. Additional metrics, including coverage. stability, and validity, further confirm the superior practical utility of our generated explanations over existing methods.
2 PRELIMINARY
2.1 GRAPH NEURAL NETWORKS FOR GRAPH CLASSIFICATION
Consider graph G = (Vg, Ec), where Va represents the set of nodes and EG represents the set of edges. For the graph dataset G, let V and & denote the sets of vertices and edges across all graphs in G, respectively, with [V] = n. Each node is associated with a dy-dimensional feature vector, and the imput features for all nodes are represented by matrix X R=xd, An adjacency matrix A E {0, 1] j is defined such that A.j- = 1 if an edge (i,j) E & exists, and Aij = 0 otherwise. A graph neural network (GNN) model M learns to embed each node v E V into a low-dimensional space h, E 12 through an iterative message-passing mechanism over the T. number of layers. At each layer I, the node embedding is updated as follows:
h = UPD (h AGG (h,, A.. = 1}))
(I)
where ho x,, is the feature vector of node v, and h represents the node embedding at the layer 1. The update function UPD, aggregation operation AGG, and message function MSG define the architecture of GNN. For instance, Graph Convolutional Networks (Kipf & Welling 2017) use an identity message function, mean aggregation, and a weighted update. A GNN model M performs graph classification by passing the graph embeddings hg to a fully connected layer followed by a softmax function. Here, h commonly computed by taking the mean of all node embeddings in ing.
the graph h2 == mean(h E VG) through the operation g aloball looal_mman__aa__eee
Node Classification, For node classification, the final embeddings are passed directly through softmax function for individual label prediction. This approach omits the global pooling operation.
2.2 FIRST-ORDER LOGICAL RULES FOR GNN INTERPRETABILITY
First-order logic (FOL) is highly interpretable to humans, making it an excellent tool for explaining the behaviour of neural networks (Zhang et al., 2021 In this paper, our proposed framework, LOGICXGNN, aims to elucidate the inner maciiinn-making process of a GNN M using Disjunctive Normal Form (DNF) formula ΦM. The formula dı is a logical expression that can be described as a disjunction of conjunctions (OR of ANDs) over set of predicates P. where each P; represents property defined on the graph structure A and input features X. Importantly, das incorporates the universal quantifier (A), providing global explanation that is specific to class of instances.
While this approach looks promising, generating a DNF formula dM that faithfully explains the original GNN M remains challenging. Specifically, must address the following key questions:
1. How to define predicates P that reliably capture genuine structural patterns in the dataset, rather than just abstract symbols that lack effective grounding?
2. How to derive faithful logical rules ΦM over P that explains the GNN's predictions?
3. Can we design an approach that is both efficient (with minimal computational overhead) and generalizable to different tasks and GNN architectures?
THE LOGICXGNN FRAMEWORK (ΦM)
3.1 IDENTIFYING HIDDEN PREDICATES P FOR dM
We begin by addressing the identification of hidden predicates for graph classification tasks. As discussed earlier. the desired predicates P should capture commonly shared patterns in both graph structures A and hidden embeddings 44 across set of instances in the context of GNNs. While graph
3

---

Published as a conference paper at ICLR 2026
0.
6:
Solecti:1
Activation Pettern Matrix +
Grounding Pair Predicates
Ag (3) 2 0.18
P1
P2
Ps
P4
Ps
Ph
oies
0
Pa
9]
TLAI
Q2
0
0.A1
jon 0.
A XJ
Q3
0
Magg 2 Ratcharne
Q4
Predicates
Example
14 1..
05
Pl ( ('coeBSSe,000 of
[
101, 0:1]
(011 o.g
foo 0.g
oair
Pa ('odeBBe", 11
Inputa C Labels
63
One mast typu Aomommatmmt ehenctipoee Bivt
12.00
12
12
10.3
0.48)
Naa
('d255NY,
Rute camner Dectiion Tree
+
Grounding Purely Structural Predicato
101, K
Ias, a.]
Ps (T610a6;
64
Pc ( ('3eeage,
+ Interpnetable Rules 4M vG, (Py(G) = tebsll vG, py(o) velabel (6.1)
Prenccaas dagns
14.00
Nos DX
Rutes based explemation 0M:
95
[1.
09
13-9 axg
Po ( (13ca9ee, 0)
VG2 (degpeslo) # labd[
Wo 30 (degren(v) = label(0 1))
Inputs
Embedding
Compute Predicates
Determine logical rules
Grounding ingical
(a) Identifying hidden predicates for PM.
(b) Extracting dM.
(c) Grounding ΦM.
Figure 2: An overview of the LOGICXGNN framework, which involves identifying hidden predicates, extracting rules, and grounding these rules in the input space for interpretability.
structure information can be encoded into hidden embeddings, it often becomes indistinguishable
due to oversmoothing during the message-passing process (Li et al. 2018 8 Xu et al. 2019).
The core of our approach is to explicitly model the recurring structural patterns that a GNN uses for computation. After L layers of message passing in a GNN, the receptive field of node v is the subgraph induced by its L-hop neighborhood. Our key insight is that nodes with structurally identical (isomorphic) receptive fields share the same fundamental computational pattern. To systematically capture and compare these patterns, we use Beisfeiler-Lemmae (WL) graph hashing to assign a unique identifier to each distinct receptive field topology This allows us to efficiently record and model these recurring structures. Formally, the structural pattern for a node v is computed as follows:
PatterRamel (v) Hash (Receptiieeeiilldd A, L)).
Next, discuss common patterns in the hidden embeddings. During GNN training. the hidden embeddings are optimized to differentiate between classes. Empirically, we find that a small subset of specific dimensions in the final-layer embeddings h is sufficient to distinguish instances from different classes using appropriate thresholds, often achieving accuracy comparable to the original GNN. Similar observations have been reported in Geng et al. (2025). In this work, we apply the decision tree algorithm to the collection of h/: from the training data to identify the most informative dimensions K along with their corresponding thresholds T. Formally, this is expressed as:
Decision Tree | G 9), (K,T)
(3)
where Y represents the prediction outcome of the GNN. We then leverage this information to construct embedding patterns at the node level, aligning with the definition of structural patterns. Recall that h mean(h | E VG), so we broadcast K and T' to each node embedding hī. Then, for an input node its embedding value h at each informative dimension k E K is compared against the corresponding threshold Tg. The result then abstracted into binary states: (activation) if the condition is met, and 0 (deactivation) otherwise. Formally, we have:
(bb)) 1 if [] Tk. clse 0
In summary, the embedding pattern contributed by given node v can be computed using the following function:
Pattermenb (v) (1))
'e use WL hashing without node or edge features to capture the pure topological structure upon which the GNN's pessage-passiigg operates. This ensures our structural patterns have an expressiveness equivalent to that of standard GNNs.
4

---

Published as a conference paper at ICLR 2026
Putting it together, we define the predicate function as f()) (PatterTsmuaa))) Patternemb (v)). To
identify the set of predicates, we iterate over each node v E V in the training set, collect all f(u), and transform them into set P. In addition, when node is evaluated against predicate Pj- the evaluation py()) is true only if both the structural and embedding patterns from f(w) match the predicate. To apply a predicate a graph instance G, we override its definition follows:
pi GG) = 1 if Bu E Va, pe(u) = 1, Pz(G) = 0 if Vu E VG, pe(v) = 0.
(6)
To better illustrate the process of identifying hidden predicates, we present simple example in Figure 2(a) This scenario involves binary graph classification task, a common setup in GNN applications. In this example, we have five input graphs, with each node characterized by two attributes: degree and type. The types are encoded as one-hot vectors. A GNN with single message- passing layer is applied, generating a 2-dimensional embedding for each node (i.c., dz 2) and achieving 100% accuracy. As only one message- passsin layer is used, structural patterns are extracted based on the nodes and their first-order neighbors.
Using decision trees, we identify the most informative dimension k 1, and its corresponding threshold 0.18 from the graph embeddings. This threshold is then applied to the node embeddings to compute embedding patterns. As a result, six predicates are derived. Notably, Ps ("83c89e", 1) and ps ("83c89e", 0) exhibit isomorphic structures, represented by identical hash strings, but differ in their activation patterns. Our predicates structural patterns from the training data, and model- faithful since they are constructed by design to align with the GNN's predictions, Y. This offers a significant advantage over prior methods, which often lack clear subgraph correspondence (Azzolin et al. 2023 Armgaan al. 2024).
therefore structurally grounded, as they capture concrete
3.2 DETERMINING THE LOGICAL STRUCTURE OF ΦM
The next task is to construct logical rules dus based on hidden predicates P for each class, which serve the explanation of the original GNN M. We process all training instances from class E C that are correctly predicted by M, evaluating them against the predicates P and recording their respective activation patterns. The results are stored in a binary matrix &. for each class c, where the columns correspond to the predicates in P. and the rows represent the training instances. Specifically, denotes that the j-th instance exhibits the i-th predicate, while Deli,
an entry & ( j] indicates otherwise, as illustrated in Figure 2(b)
From a logical structure perspective, each row in P. represents a logical rule that describes an instance of class c, expressed in conjunctive form using hidden predicates. For instance, in the simple binary classification task introduced earlier, G2 corresponds to the column (1, 1, O, 1, O, 0), which can be represented as pi Ap2 A -Pa Ap4 A -ps A -Po. Here, we omit G in (G) for brevity. To obtain more compact set of explanation rules, we input & and Ý into an off-the-shelf rule learner, such as decision trees or symbolic regression (Cranmer 2023). In this work, we use decision trees for computational efficiency. The tree depth serves as a tunable parameter for controlling the complexity of the rules. For instance, in our simple GNN setting, the decision tree yields the following explanation rules @as:
YG, (G) = label( 0), YG, Ps(G) + label(G, 1).
3.3 GROUNDING ΦM INTO THE INPUT FEATURE SPACE
The next challenge lies in grounding du. Prior work often simplifies this task by mapping each latent concept to a single representative subgraph, which can be poorly representative or even invalid (see our analysis of the root cause in the Appendix B.4). Such subgraphs can become especially meaningless when the input feature space X is continuous. To address these issues, LOGICXGNN goes beyond producing just individual explanation subgraphs. Moreover, it generates a set of generalized, fine-grained grounding rules that directly connect the hidden predicates P to the input space X. In particular, our predicate design explicitly integrates structural patterns, enabling both (i) the generation of diverse, representative subgraphs for each predicate and (ii) the construction of stracture-aware inputs Z for inferring the grounding nules.
Recall that each Pj can be represented by a collection of isomorphic subgraphs that activate p)- Formally, given a graph G (V, F), we consider the action of the automorphism group Aut(G) on its node set V. The orbit of a node o E V under this action is defined as
Orb(v) {u V 3 E Aut(G) such that (()) = u).
(8)
5

---

Published as a conference paper at ICLR 2026
Each orbit corresponds to equivalence class of nodes that structurally indistinguishable within G. To create a canonical representation. we partition the node set into these orbits and establish a consistent ordering using Algorithm (Appendix
((G) = (Orb(v1), Orb((2)....,,O(((x)))
where each Orb(u;) denotes the orbit of node e; under Aut(G), and the ordering is deterministic and can be reliably reproduced across isomorphic subgraphs (see proofs in Appendix D)
Definition 3.1 (Subgraph Input Feature Z). The input features of nodes in a subgraph G (represented by pattern p,) are aggregated in a structure-aware manner according to the orbit ordering OG))
Zg CONCAT (AGGREGATE ,..
(10)
where AGGREGATE applies frequency encoding (mean encoding) for multi-node orbits with dis- crete (continuous) features, and the identity function for singleton orbits. Since each subgraph G corresponds to the (.-hop neighborhood of central node v we adopt the notation Zu, r. in place of
Za for convenience. For example, as shown in Figure [ic) the subgraph input feature centered at node is 11, = (1, B). which represents the concatenated features of nodes 1 and 2.
Once obtain Z, we can derive interpretable grounding rules that approximate the embedding pattern function Pattermemt() (.) encoded by the GNN. To address this, we leverage off-the-shelf rule learners; in this work, we utilize decision trees due to their computational efficiency and inherent interpretability, For predicates that exhibit isomorphic subgraph structures but distinct embedding patterns, we recast this problem as a supervised classification task, where each predicate Pj is treated as a unique class label j. The training procedure constitutes a dataset for each predicate label j by collecting the subgraph representations of all nodes e that satisfy the predicate, formally defined as {Z..,. (v(v) = 1]. This process allows us to easily collect representative subgraphs, example, the training data for pt (identified as ("ede85e", 0)) is [Z Z3.1, Z22.1 ). while the training data for p2 (identified as ("cde85e", 1)) is (Z,,1, Z11.1. Z2 1. Applying the decision tree then generates rules [[]]= S 0.5 for p1 and the opposite for p2. Recall that Z[1], the first dimension of Z, encodes the central node type. Therefore, we recognize that P1 indicates that the central node is of type "A", while P2 indicates type "B", conditioned on the structural pattern being "cde85e".
shown in Figure 2(c) For
For purely structural predicates without direct embedding counterparts, explanations grounded in the presence of their topological structures. Consider the predicate ps. ("d255th", 1), which activates when input graph contains a subgraph isomorphic to the "d255th" pattern, corresponding to node with 2 edges, as illustrated in Figure 2 Since this is the only predicate in our GNN example that encodes this specific property, we can ground dM into the following interpretable logical rules:
VG, Ve E VG (degree(v) + 2) > label 0), YG, 3o E Va (degree(v) = 2) + label 1). (11)
However, such straightforward rules cannot always be derived in more complex scenarios. In general, the final rule-based explanation takes the form of logical rules over predicates, with predicates grounded either through grounding rules or representative subgraphs. More details about our ground- ing process, including the additional examples, handling of continuous features, and guidance on interpreting the grounding rule visualizations, are provided in Appendix D
Inference and Data-Grounded Fidelity. During inference, a definitive prediction for a class is made if and only if the logical rule for that class is uniquely satisfied, as determined by evaluating each predicate on the input graph (Fq. (). We then compute data-grounded fidelity (Fidp) as the class-weighted percentage of instances where this rule-based prediction exactly matches the original GNN's output. Note that a prediction is considered incorrect if it is ambiguous, which occurs when either no rule multiple class rules are satisfied simultancously. This issue prevalent in prior methods, as shown with examples in Section 4.2 In contrast, our approach is guaranteed to avoid such ambiguity because its rules are derived from decision trees a structure that inherently provides a unique classification for any given input. Further details on Fidp and inference are in Appendix B.2
Remark on Node Classification. Our framework naturally extends to node-level tasks by utilizing the predicate function f(v)- = (Patter (v), Patternems (v)) to encode class-informative signals
Note that the central node can he treated as singleton orbit, as adopted in our GNN example in Figure 2

---

Published as a conference paper at ICLR 2026
directly at the node level. Consequently, class-wise rules are obtained by aggregating the predicates associated with each class through a logical V (OR) operation, bypassing the graph-level activation- matrix construction.
3.4 ANALYSIS
Computational Complexity. Our approach models message passing each node to identify interpretable and reliable predicates. First, we extract activation patterns from pretrained GNNs and compute graph hashes over nodes' local neighhorhoods. Hashing the T.-hop neighborhood of node takes approximately O (v + E)) time, where v and denote the number of nodes and edges within the neighborhood. In practice, for well-structured and relatively sparse datasets, this hashing behaves nearly constant in runtime. Importantly, this step operates independently of the GNN's s size, with overall complexity O(D) L- + E)). Second, we determine the logical structure by constructing binary matrix of size (number of predicates) x (number of graphs), yielding a complexity of O(1V (9). Finally, grounding each predicate requires constructing dataset of representative subgraphs. Given that fitting small decision tree is typically fast, often taking near-constant time in practice, this yields a complexity of ((1))). A comprehensive analysis of the decision tree training overhead is provided in Appendix B.5 Empirical runtime results are reported in Table I
Generalization Across Different GNN Architectures. We show the theoretical generalizability of LOGICXGNN to any GNN architecture. First, we model stacked peassag--aassing computations using hidden predicates (activation patterns and local subgraphs), an architecture-agnoss then generate logical rules through binary matrix construction and decision tree analysis, maintaining architecture independence. Finally, we ground predicates by linking them to input features via decision trees, requiring no GNN-specific details. Empirical evidence is provided in Appendix C.44
formulation. We
4 EVALUATION
In this section, we conduct extensive experimental evaluations on a broad collection of real-world benchmark datasets to investigate the following research questions:
1. How does @as perform compared to existing rule-based explanation methods across key metrics, including data-grounded fidelity, efficiency, and scalability?
2. How does Φ improve explanation quality over existing approaches, and what are the key advantages of our generated explanations?
Consistent with prior work (Armgaan et al. 2024), we restrict our comparison to global rule-based explanation methods, excluding local approaches such as GNNEXPLAINER (Ying et al. 2019) and (sub)graph generation-based approaches such GNNINTERPRETER (Wang & Shen 2023 due to their different scope. For evaluation, we compare our approach against state-ol- ti-th-rrt art methods, GLGEXPLAINES (Azzolin al. 2023) and GRAPHTRAIL. (Armgaan et al. 2024 Our primary evaluation metric is data-grounded fidelity, Fidp. Additional results on other metrics are provided in Appendix C
Baselines.
Due to page limits, detailed descriptions of the datasets are provided in Appendix A while the experi- mental setup, including GNN training and baseline implementations, can be found in Appendix B
4.1 HOw EFFECTIVE IS du AS A LOGICAL BASSED EXPLANATION TOOL?
We report the data-grounded fidelity Fidp and runtime of proposed approach øw and baseline methods on commonly used datasets for GNN explanation research, with results presented in Table Results on large-scale real-world datasets are presented in Table 2 Notably, 9ы consistently outperforms both baselines by a substantial margin across all benchmarks. The performance gap arises because baseline explanation subgraphs are often poorly representative of the model's decision
'While GCNeuron (Xuanyuan et al. 2023 uses logic to describe individual neuron concepts. it relies on numerical importance scores rather than constructing explicit class-wise decision rules. Consequently, it lacks the translated logical rule-sets found in method and the haselines, leading to its exclusion as baseline.
7

---

Published as a conference paper at ICLR 2026
Table I: Data grounded fidelity FidD (%) on the test datasets and runtime (in 10 seconds) for various explanation methods. Results are reported over three random seeds. For each dataset, the highest fidelity and fastest runtime are highlighted in bold. " indicates no rules were learned.
BAMutiShapes
BBBP
Mulagenicity
NCII
IMDB
Method
Fido
Time
Fido
Time
Fidro 1
Time 1
Fidp
Time
Fido
Time 1
GLG
0.31
taz
0.73 :
9.61 2778
GTRAI
79.82 xM
2.54
50.00
1:000
5.65
65.93 a 189
20.01 1 11
60.04 2:4
24.07 11
35.35
1.385
1.07 g.0
dar (Ours)
82.67
0.02
85.32
0.14 600
81.36 + 2.2
0.61 2
73,81
0.44
74,16
0.02 00
Table 2: Data-grounded fidelity Fidp (%) on large-scale real-world datasets. TO indicates that the method did not complete within the allocated time limit of 12 hours. OM shows superior scalability compared baseline methods.
1.0
0.8
0.7
BASTADES
DOOP
Rodie
Twitch
Gitbab
0.6
Method
Fida 1
Time 1
Fidn 1
Time
Fido 1
Time
Patapercity
10
TO
0.5
GTmii
TO
TO
Troo Depth
der (Curs) 87.39 aaw
1:300
59.71 684
7.27
6:23
224
12.17
Figure Impact of tree depth on Fidp-
regions, or even fail to match any real graph instances in the dataset (e.g., GIGEXPLAINER yields 0% Fidp on IMDB). This performance gap is expected, as baselines often simplify grounding by mapping latent concepts to single representative subgraphs, which frequently results in poor representation or structural invalidity. We provide detailed analysis of these grounding failures in Appendix B.4 In contrast, Φar learns grounding rules that generalize well, explaining large portion of unseen test data. We further analyze the quality of their explanations using concrete examples and additional utility metries in Section 4.2) Another interesting observation is that dM achieve relatively high fidelity even with simple rules, as shown in Figure 3 The tunable depth also gives users the fiexibility to choose appropriate trade-off between fidelity and rule complexity.
In terms of runtime performance, both baseline methods are fundamentally bottlenecked by their reliance on computationally expensive operations for each instance. For example, GLGEXPLAINER must invoke a separate local explainer, PGEXPLAINER (Luo et al., 2020a), for every graph, while GRAPHTRAIL requires numerous, costly GNN forward passes to process its computation trees. In contrast, Φы employs highly efficient graph traversal algorithms and decision trees, yielding a dramatic speedup of one to two orders of magnitude (10-100x). This enables Φas to demon- strate significantly better scalability on large-scale weal-world datasets such as Reddit, Twitch, and Github (Rozemberezki et al. 2020), where both baselines time out, as shown Table? 2
4.2 DOES dM PROVIDE BETTER EXPLANATIONS THAN EXISTING METHODS?
To assess the quality of our generated explanations, we conduct both qualitative and quantitative evaluations. Figures 4fares//Jana [3 a direct comparison of explanations from baseline approaches and ΦM on the datasets Mutagenicity and BBBP (w et al. 2018). Here, we use simplified rules for the baselines and dM (we set the tree depth for ΦM to 2 to achieve comparable rule complexity) for clearer visualization. This does not affect the nature of all methods. We choose these molecular datasets as they represent a domain that demands explanations with real-world scientific utility rather than mere subjective interpretability. An extended set of explanations provided in Appendix [E.3]
We identify several issues with both baselines. First, GLGEXPLAINER often generates conflicting rules. For example, in its rules for Mutagenicity, 33333 is a subgraph of Z9g. yet they correspond to different classes. This creates ambiguity because both class rules can be simultaneously satisfied. Consequently, GLGEXPLAINER reports a very low Fidp of around 38.98%, as shown Table [ In some cases, it fails to yield any rules, as in BBBP. On the other hand, GRAPUTRAILL consistently produces chemically invalid motifs, such as I149 and Zuu in BBBP. Moreover, since it generates only unilateral rules, all class 0 instances match these invalid subgraphs. Although GRAPHTRAN appears to achieve a higher Fidp than GLGEXPLAID AINER, such explanations remain largely meaningless to end users. In contrast, ΦM not
trivially explained correctly, as they simply do not
8

---

Published as a conference paper at ICLR 2026
GUGExplainer Explanation for BBBP
GraphTrall Explanation BBBP hentororiatsxx/0u.tt333
GLGExplainer Explanation for Mutagenicity x3333 s3606 mx s89
Trail Explanation for Mutagenicity NetjOrpe (1111) Class
X3333
(a) GLG learned no rules or conflicted rules.
(b) GTRAIL. learned invalid chemical subgraphs.
Figure 4: Baselines' explanations exhibit conflicting rules and chemically invalid subgraphs.
Predicate
Regresentialive Subgraph
Grounding Rale Vissalization Each Prediatte
Grounding Itul Visual Visual for Each Pred
P3
p?
p??
Coo
A p7) (ps A P27) = BBBP class (-Ps A PT) (ps A P27) BBBP class
Pp A P20) V (p2 A PPs) + Mutag. class 0 (-p2 A P20) V (p2 P3s) Mutag. class
Figure 5: Besides representative subgraphs, approach ΦMs also provides general grounding rules for each predicate, effectively capturing more of the model's behavior, thereby achieving high fidelity.
only generates accurate representative subgraphs but also provides detailed general grounding rules for each predicate, resulting in a significantly higher Fidp than the baselines. Moreover, our final explanations expressed in DNF form, offering better readability than those of GRAPHTRAIL
To complement this qualitative analysis, we quantitatively evaluate the generated explanations using a set of objective metrics that reflect their practical utility for end users: (1) Coveruge: The proportion of target-class instances where the rule-based prediction remains correct when restricted to only valid subgraph patterns (i.e., after removing all invalid patterns). (2) Stability: The consistency of explanation subgraphs across multiple runs. (3) Validity: The proportion of explanation subgraphs
Table 3: Coverage of constructive explanations.
Table 4: Stability and Validity.
Mutagenicity
BBBP
Stability
Validity
Method
Class 0 (%)
Class 1 (%)
Class 0 (%)
Class 1 (%)
Method
Mutag.
BBBP
Mutag.
BBBP
GLG
6.11 2.17
75.03 27112
GLG
40.00
100.00 a u0
GTRAIL
0.00
78.48
0.00
+:
GTRAIL
37.50
20.00
61.90
0.00
dur (Ours)
80.06
82.58
47.86
98.16
Pu (Ours)
66.67
60.00
100.00 0.00
100.00 0,00

---

Published as a conference paper at ICLR 2026
corresponding to valid chemical fragments in the dataset. Additional details these metrics provided in Appendix E.I All results are computed and reported over three seeds in Tables 3 and 4
Note that our approach consistently outperforms all baselines across these metrics. The high coverage indicates that our method provides meaningful explanations to more instances, while higher stability suggests more reliable, reproducible explanations. The 100% validity scores further confirm that our explanations correspond to chemically meaningful substructures, making them interpretable and trustworthy for domain experts. Appendix B.2 provides additional analyses, which corroborate our qualitative findings and validate the effectiveness of our approach for high-quality graph explanations.
Validation on Synthetic Benchmarks. We evaluate dur's 's rule-learning capability using the BA- MultiShapes dataset. Despite substantial noise in the underlying graph structures, our method accurately recovers the governing logical rules. Specifically, the ground-truth rule for Class 1 the Disjunctive Normal Form: (H A W*) V (H A V A G) Class 1, where H, W, and G represent House, Wheel, and Grid motifs. As shown in Figure 12 (Appendix [E.3), our model extracts clauses mapping directly these logical components; for instance, at rule depth 5, clauses (P52 Pas) and (p2s0 A P11a) correspond to (H A W) and (W A G). The complete rule is fully recovered at depth 10. In contrast, state-of-the-art baselines, including GLGGEPLLAINER and GRAPHTRAIH fail to extract comparable rules on this benchmark (see Figure 5 in (Armgaan et al. 2024
5 RELATED WORK
Explainabilityy methods for Graph Neural Networks (GNNs) can be broadly categorized into local and global approaches. A significant portion of prior work has focused local explanations, which provide input attribution scores for a single prediction (Pope et al. 2019 Ying et al. [219 Luo et al., 2020b Vu & Thai 2020 Lucic et al.) 2022 Tan al. (022). These methods identify the most critical nodes and edges for a given decision, analogous to attribution techniques like Grad-CAM (Selvaraju al. 2017) used in computer vision. In contrast, global explanations aim capture the model's overall behavior, primarily through two strategies. (Sub)graph generation- base methods seek to
identify representative graph patterns that are highly indicative of particular class YYuan et al.) 2020
Wang & Shen 2023 Xuanyuan et al.) 2023 Wang & Shen 2024 Saha & Bandyopadhyay 2024 Lv
Chen 2023 Yu & Gaol 2025). Logical rule-based methods, however, offer more expressive and human-readable explanations by using subgraphs as interpretable concepts within formal logical formula. Our proposed method, LOGICXGNN, operates within this advanced domain of global rule-based explanations, aiming to generate precise and interpretable rules that clearly describe GNN's decision- makinn process. Another related line of work involves self-explainable GNNs, which aim to develop model architectures that are inherently interpretable by design (Dai & Wang 2021: Liu et al., 2025 Ragno et al. 2022). These methods are not directly compared in our work as they address different goal, building interpretable models from scratch, whereas our focus is on providing post-hoc explanations for any pre-trained GNN. We believe that generalizing our rule-based framework the domain of self-explainable models is promising direction for future research.
CONCLUSION
In this work, we identify fundamental limitation in existing rule-based explanation methods for GNNs: they optimize and evaluate fidelity in an intermediate, uninterpretable concept space while ne- glecting the grounding quality of final subgraph explanations presented to end users. This disconnect undermines both usability and trustworthiness, as methods often produce explanations that appear highly faithful yet fail reflect concrete patterns in the data. To address this critical gap, we propose LOGICXGNN, novel framework that constructs explanation rules over reliable predicates designed to preserve structural patterns inherent in GNN's pessaag-passingg mechanism. Our approach enables effective grounding that produces representative subgraphs and learns generalizable grounding rules. LOGICXGNN achieves an average improvement of over 20% in data-grounded fidelity Fidp while de- livering 10-100x computational speedup compared to existing methods. Comprehensive evaluation across coverage, stability, and validity metrics confirms that LOGICXGNN produces explanations with genuine practical utility, significantly advancing trustworthy GNN explainability. For future work, we aim to enhance explanation interpretability by integrating domain knowledge, particularly in biochemistry, to uncover novel structure-activity relationships within complex molecular datasets.
10

---

Published as a conference paper at ICLR 2026
ACKNOWLEDGMENTS
This work was supported, in part, by Individual Discovery Grants from the Natural Sciences and Engineering Research Council (NSERC) of Canada and the Canada CIFAR AI Chair Program. This research was also supported by the ProML project, a joint initiative funded by NSERC and the French National Research Agency (ANR) under the reference ANR-25-CE23-6715
REFERENCES
Julia Amann, Alessandro Blasimme, Effy Vayena, Dietmar Frey, Vince I. Madai, and Precise4Q consortium. Explainabilityy for artificial intelligence in healthcare: A multidisciplinary perspective. BMC Medical Informatics and Decision Making, 20(1):310, Nov 2020. doi: 10. 10.1186/s12111-000 01332-6. TRLLAtttss///c...r///11111//
020 1220-0133 01332-6
Burouj Armgaan, Manthan Dalmia, Sourav Medya, and Sayan Ranu. Graphtrail: Translating GNN predictions into human- inmaaninterpreetbbl logical rules. In Amir Globersons, Lester Mackey,
Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomezak, and Cheng Zhang (eds.),
Advances in Neural Information Processing Systems 38: Annual Conference Neural In- formation Processing Systems 2024, NeurlPS 2024, Vancouver, BC, Canada, December 10 15. 2024, 2024. URL http:::/paaerr..nssscco//aaaaaaa 3i2cheelccs32221ccccccclaaaaeeee
wallespaperr/000 / Abstraatbtttttttttt Confereeeeeeeeennn.... ort.rpeee...cttaaaaaooooeeeeeeaa
Steve Azzolin, Antonio Longa, Pietro Barbiero, Pietro Liò, and Andrea Passerini. Global explainabil- ity of gnns via logic combination of learned concepts. In The Eleventh International Conference on Learning Representaatinns, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023.
forum? 1i=-m1TTTTTTYYYYS URL httppsss//ppeneevee..eeee. htw.://ee////o....e..eeCTT11111
Niklas Bussmann, Paolo Giudici, Dimitri Marinelli, and Jochen Papenbrock. Explainable machine learning in credit risk management. Comput. Econ., 57(1):203 216, January 2021. ISSN 0927- 7099. doi: 10. 10.10007/1101144000000044 020 1002-0
URL
Maria Camburu, Brendan Shillingford, Pasquale Minervini, Thomas Lukasiewicz, and Phil Blunsom. Make up your mind! adversarial generation of inconsistent natural language explanations. In Dan Jurafsky, Joyce Chai, Natalie Schluter, and Joel R. Tetreault (eds.). Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020, pp. 4157-4165, 4165, Association for Computational Linguistics, 2020. doi: 10. 18653/V1 AAAL-MMA....3/ /R//ttpsss///i.o////////.
Ziheng Chen, Fabrizio Silvestri, Jia Wang, Yongfeng Zhang. Zhenhua Huang, Hongshik Ahn, and Gabriele Tolomei. Grease: Generate factual and counterfactual explanations for gnn-based recommendations, 2022. URL
abs 20t.bb//20002222222
Miles D. Cranmer. Interpretable machine learning for science with pysr and symbollcregrression.]. CoRR, abs/2305.01582. 2023. doi: 10.48550/ARXIV.23006 23w.XXV2..3330503333 URL httpp:://oii.oor
0..4550/arxi.22005.007
Enyan Dai and Suhang Wang. Towards self-explainable graph neural network. In Gianluca Demartini, Guido Zuccon, J. Shane Culpepper, Zi Huang, and Hanghang Tong (eds.), CIKM '21: The 30th ACM International Conference Information and Knowledge Managemeni, Virtual Event, Queens- land, Australia, November 5, 2021, pp. 302-311 311. ACM, 2021. doi: 10. 0t.114//345963734482222
URL hatpps://das http:///............1.3//3333333
Asim Kumar Debnath, Rosa L. Lopez de Compadre, Gargi Debnath, Alan Shusterman, and Corwin Hansch. cauucture-actvvity relationship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of Medicinal
Chemistry, 34(2):786-797, 1991. doi: 10. 1021/m000000 06a046. URL. https: i.org/
(0.0211/m0000060444
Chuqin Geng, Xiaojie Xu, Zhaoyue Wang, Ziyu Zhao, and Xujie Si. Decoding interpretable logic rules from neural networks, 2025. htt./nttss///arrttarr/aa//////..
11

---

Published as a conference paper at ICLR 2026
William L. Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning large graphs, 2018. URL/tttps: /ttp://ww..///////////00000000 /ttp///////////////////////////0
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In Sth Interaational Conference on Learning Representations, ICLR 2017, Toulon, Frunce, April 24-26, 2017, Conference Truck Proceedings. OpenReview.net, 2017. URL
https: fttts:://pperewse ww.net/ htt.:/oormmmiisd//r//
Thibault Laugel, Marie-Jeanne Lesot, Christophe Marsala, Xavier Renard, and Marcin Detyniecki. The dangers of post-hoc interpretability: Unjustified counterfactual explanations. In Sarit Kraus (ed.), Proceedings of the Twenty-Eightt International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019. pp. -8077 ijcai.org, 2019. doi: 10.24963/ UCCAL2201/388 https: http://t..oorgoooooooooo 0tt./10.24499 0......443.... jaa .2. 9/888
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Sheila A. Mcllraith and Kilian Q Weinherger (eds.), Pro- ceedings of the Thirty-Second AAAI Conference on Artificial Intelligence, (AAAI-18), the 30th innovative Applications of Artificial Intelligence (IAAI-18), and the 8th AAAI Symposium on Educational Advances in Artificial Intelligence (EAAI-18), New Orleans, Louisiana, USA, Febru- ary 2-7, 2018, pp. 3538 3545. AAAI Press, 2018. doi: 10.1609//AAALV3221.1 /ttpp:://abl.orgg/1111000/////// (09.00..11000/aaa.
URL
Zachary C. Lipton. The mythos of model interpretabilityy Commun. ACM, 61(10):36 43, 2018. doi: 10.1 145/33333333311 UK/ppppes///oo..orr//11111///333
Fanzhen Liu, Xiaoxiao Ma, Jian Yang, Alsharif Abuadbba, Kristen Moore, Surya Nepal, Cécile Paris, Quan Z. Sheng, and Jia Wu. Towards faithful class- self-explainability in graph neural networks by subgraph dependencies, CoRR, 2btp2508..11133333 2025, doi: 10.48550/ARXIV 25....21511..11
Yunchao Liu, Yu Wang, Oanh Vu, Rocco Moretti, Bobby Bodenheimer, Jens Meiler, and Tyler Derr. Interpretable chirality-aware graph neural network for quantitative structure activity re-
lationship modeling. In The First Learning on Graphs Conference, 2022. URL https 3
fow.mmmiddd //
Ana Lucic, Maartje Hoeve, Gabriele Tolomei, Maarten de Rijke, and Fabrizio Silvestri. Cf- gnnexplainer: Counterfactual explanations for graph neural networks, 2022. URL https !
//axxivorgg/as//2022.00
Dongsheng Luo, Wei Cheng. Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network. In Hugo Larochelle, Mare Aurelio Ranzato, Raia Hadsell, Maria-FForina Balcan, and Hsuan-Tice Lin (eds.), ), Advances in Neural Information Pro- cessing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, viriual, 2020a. URL htrp//tttpp///prrreeenn..eeerrr e 210//////....2.2.0.0003333333333
Dongsheng Luo, Wei Cheng, Dongkuan Xu, Wenchao Yu, Bo Zong, Haifeng Chen, and Xiang Zhang. Parameterized explainer for graph neural network, 2020b. URL 20111.4573
abs/
Ge Lv and Lei Chen. On data-aware global explainability of graph neural networks. Proc. VLDB Endow,, 16(11)3447-3460, 2023. doi: 10. 14778778/3 1479.361 11777//331147.361 1538. URL |ttps
//ww.vv I /ttbb//g///oobb/oooo//////331110
db/
Christopher Morris, Nils M. Kriege, Franka Bause, Kristian Kersting, Petra Mutzel, and Marion Neumann. Tudataset: A collection of benchmark datasets for learning with graphs. CoRR, abs/2007.08663 2020. URL http::tttt://att /RL//t/ps////awwworrrr/a//////
Phillip E. Pope, Soheil Kolouri, Mohammad Rostami, Charles E. Martin, and Heiko Hoffmann. Explainability methods for graph convolutional neural networks. In 2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pp. 10764-10773, 2019. doi: 10.1 CVPR 2P1..2019.0110 103.
12

---

Published as a conference paper at ICLR 2026
Alessio Ragno, Biagio La Rosa, and Roberto Capobianco. Prototype- interpretable graph neural networks. IEEE Transactions on Artificial Intelligence, 5(4):
2022.
Susie Xi Rao, Shuai Zhang, Zhichao Han, Zitao Zhang, Wei Min, Zhiyao Chen, Yinan Shan, Yang
Zhao, and Ce Zhang, xfraud: explainable fraud transaction detection. Pruceedings of the VLDB Endowment, 15(3))427-336, November 2021. ISSN 2150-8097. doi: 10. 10.14778//49414444994 URL
Benedek Rozemberczki, Oliver Kiss, and Rik Sarkar. Karate Club: An API Oriented Open-source Python Framework for Unsupervised Learning on Graphs. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM '20), pp. 312--3132. ACM, 2020.
Sayan Saha and Sanghamitra Bandyopadhyay. Graphon-explainer: Generating model-level expla- nations for graph neural networks using graphons. Trans. Mach. Learn. Res., 2024, 2024. URL https: www.eeveeveeeeeeeeeeeeeee www.et...aa...mm................ forum? www.:u/mmmmiiuuuuuoooooooo
Ramprasaath R. Selvaraju, Michael Cogswell, Abhishek Das, Ramakrishna Vedantam, Devi Parikh, and Dhruv Batra. Grad-cam: Visual explanations from deep networks via gradient-based localiza- tion. In IEEE International Conference on Computer Vision, ICCV 2017. Venice, Italy, October 22-29, 2017, pp. 618-626. IEEE Computer Society, 2017. doi: 10. 10.1109/CCV.22117.70 URL
atttss///doi.o htt.pss://bi.org/1..119999 htt.://gg.00..11001.............
ICCV.2017.75
Mengying Sun, Sendong Zhao, Coryandar Gilvary, Olivier Elemento, Jiayu Zhou, and Fei Wang. Graph convolutional networks for computational drug development and discovery. Briefings in Bioinformatics, 21(3):919-935, 2020. doi: 10. 19/0b//bbb//
Juntao Tan, Shijie Geng, Zuohui Fu, Yingqiang Ge, Shuyuan Xu, Yunqi Li, and Yongfeng Zhang. Learning and evaluating graph neural network explanations based on counterfactual and factual reasoning. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel Médini (eds.), WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pp. 1018-1027 ACM, 2022, doi: 10.1145/ 3485447.351 /tt.atttee//....t///111111333113
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018.
oo dwr.a kCZ
Minh N. Vu and My T. Thai. Pgm-explainer: Probabiliiticc grabbbbl model explanations for graph neural networks, 2020. URL Btr.a///e///axxuorr////////00..0
Nikil Wale, Ian A Watson, and George Karypis. Comparison of descriptor spaces for chemical compound retrieval and classification. Knowledge and Information Systems, 14:347-375, 2008
Xiaoqi Wang and Han-Wei Shen. Gnninterpreter: A probabilistic generative model-level ex- planation for graph neural networks. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL htttps://openrevieet www.teeeeeeeeeeeeemeeemmm....eee forum?
Xiaoqi Wang and Han-Wei Shen. Gnnboundary: Towards explaining graph neural networks through the lens of decision boundaries. In The Twelfth International Conference on Learn- ing Representations, ICLR 2024, Vienna, Austria, May 7-11, 2024. OpenReview.net. 2024. URL TttEp:://openrevieee
Zhenqin Wu, Bharath Ramsundar, Evan N. Feinberg, Joseph Gomes, Caleb Geniesse, Aneesh S. Pappu, Karl Leswing, and Vijay Pande. Moleculenet: A benchmark for molecular machine learning, 2018 URL httts: http:////wwwwwvo/////////ss
Jiacheng Xiong, Zhaoping Xiong, Kaixian Chen, Hualiang Jiang, and Mingyue Zheng. Graph neural networks for automated de novo drug design. Drug Discovery Today, 26(6): 1382-1393., 2021. doi: 10.101 1..1006/..drddis... 2021.02.011
13

---

Published as a conference paper at ICLR 2026
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA. USA, May 6-9, 2019. OpenReview.net,, 2019. URL/Ltpp::///peeeeeeewwee
61 A5Km. forum? A5kmm
Han Xuanyuan, Pietro Barbiero, Dobrik Georgiev, Lucie Charlotte Magister, and Pietro Liò. Global concept-based interpretability for graph neural networks via neuron analysis. In Brian Williams, Yiling Chen, and Jennifer Neville (eds.). Thirty-Seventl AAAI Conference on Artificial Intelligence, AAAI 2023, Thirty-Fifth Conference on Innovative Applications of Artificial Intelligence, IAAI 2023, Thirteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2023, Washington, DC, USA, February 7-14, 2023, pp. 10675-10683, AAAI Press, 2023, doi: 10.1609/
URL /tt.a//teae///ooooo////////////.
Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. Gnnexplainer: Generating explanations for graph neural networks, 2019. htK/:tttss///axx.ooo////bb
1903.03894
Zhaoning Yu and Hongyang Gao. MAGE: model-level graph neural networks explanations via motif-based graph generation. In The Thirteenth International Conference Learning Representations, ICLR 2025, Singapore, April 24-28, 2025. OpenReview.net, 2025. URL
https:://opereeiier net www.urewwweweeeefoouuuuu iideueddiieeee PP
1Ypk6
Hao Yuan, Jiliang Tang, Xia Hu, and Shuiwang Ji. Xgnn: Towards model-level explanations of graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.
ACM, August 2020. doi: 10. 145/33944866.4400333
Yu Zhang, Peter Tiño, Ales Leonardis, and Ke Tang. A survey neural network interpretability.
IEEE Trans. Emerg, Top. Comput. Intell,, 5(5):726-742, 2021, doi: 10.1100/EETC112221.11000
htt.httts///o...o /0tp://0000000000000000000000000
14

---

Published as a conference paper at ICLR 2026
A
DATASET DETAILS
We evaluate our approach on diverse set of graph classification benchmarks commonly used in GNN explanation research. Table summarizes the statistics of these datasets.
Molecular Graphs: Mutagenicity (Debnath et al., 1991). NCT (Wale et al., 2008), and BBBP (Wu et al., 2018) are molecular datasets where nodes represent atoms and edges represent chemical bonds. In NCII, each graph labeled according to its anticancer activity. Mutagenicity contains compounds labeled based their mutagenic effect on the Gram- negative bacterium (Label indicates mutagenic). BBBP labels molccules by their ability to penetrate the blood-brain barrier.
Synthetic Graphs:
BAMultiShapes (BAShapes) consists of 1,000 Barabási-Albert (BA) graphs with randomly placed network motifs such as house, grid, and wheel structures (Ying al. 2019). Class 0 contains plain BA graphs those with one more motifs, while Class contains graphs enriched with two motif combinations.
Social Graphs: IMDB-BINARY (IMDB) represents social networks where each graph corresponds to movie; nodes actors and edges indicate co-appearances in scenes (Morris et al. 2020).
Table Statistics of standard graph datasets.
BAMultiShapes
Mutagenicity
BBBP
NCII
IMDB
#Graphs Avg. [V]
1,000
4,337
2,050
4,110
1,000
40
30.32
23.9
29.87
19.8
Avg. [
87.00
30.77
51.6
32.30
193.1
#Node features
10
14
37
0
To assess scalability, we also benchmark our approach and baselines on large-scale, real-world datasets from Rozemberezki et al.] (2020): Reddit Threads, Twitch Egos, and GitHub Stargazers.
Table summarrzee their statistics.
Reddit Threads (Reddit): Labeled discussion- based non-discussion-based The task is to predict whether a thread discussion-orientee.
Twitch Egus (Twitch): Ego networks of Twitch users. The task to predict whether the central gamer plays single game multiple games.
GitHub Stargazers (GitHub): Social networks of developers who starred popular machine learning or web development repositories. The task is to classify whether a social network belongs to web or machine learning repository.
Table 6: Statistics of Graph Datasets: Nodes, Density, and Diameter
Dataset Graphs
Nodes
Density
Diameter
Min
Max
Min
Max
Min
Max
Reddit 203,088
11
197
0.021
0.382
27
Twitch 127, 127,094
14
452
0.038
0.967
1
12
GitHub 12,725
10
957
0.003
0.561
18
B EXPERIMENTAL SETUP AND REPLICATE BASELINES
B.1 EXPERIMENTAL SETUP
All experiments are conducted on an Ubuntu 22.04 LTS machine with 128 GB RAM and an AMD IPYCIM 7532 processor. Each dataset is split into training and testing using 80/20 ratio, and
15

---

Published as a conference paper at ICLR 2026
Predicates
New Instance G
Inference
Rule:
Rg(C) pi (x))
Assignment of PL(C) Px(C)
P1
P2
Prediction:
Ra(G) Folse
Figure 6: The example for inference.
all experiments are repeated with three different random seeds to ensure robustness. The seeds affect the entire pipeline, including GNN training. Although our method itself deterministic, we evaluate it on GNNs trained with different seeds to ensure fair comparison and to assess robustness under natural variations, following standard XAI practice.
The default GNN architecture is GCN (Kipf & Welling, 2017 for all benchmarks. To demonstrate the -odel-agnostic nature of LOGICXGNN we additionally benchmark against multiple GNN architectures, including 2-layer GraphSAGE (Hamilton et al.) 201 8). 3-layer GIN (Xu et al. 2019). and 2-layer GAT (Velickovic et al.) 2018). Results are reported Table 13 For GNN training, we use the Adam optimizer with learning rate of 0.005. Each GNN is trained for up to 500 epochs with early stopping after a 100-h warm-up validation accuracy does not improve for 50 consecutive epochs. All explanation methods are trained and learned the same training data as the base GNNs, and their performance is evaluated on the test splits. The main metric is data- suuta-grounded fudlity Fidp-
As for approach, LOGICXGNN, we employ the CART algorithm for all decision trees used in LOGICXGNN, To compute the predicates, we first select the top K most informative dimensions from the decision tree that achieves least 95% accuracy (Eq. 3 We then use these dimensions to generate activation embeddings for each predicate and apply Weisfeiler-Lchman (WL) hashing capture their topological structure. We report the best results across different tree depths for the final
explanations. For each explanation method, we allocate time limit of 12 hours, excluding the training time of the GNNs.
B.2 INFERENCE WITH RULE-BASED EXPLANATIONS ON GRAPH SPACE
Rule-based GNN explanations operate by evaluating a set of logical formulas defined over an input graph. During inference, these formulas are applied to an input graph G to generate a prediction. Typ- ically, each symbol-i.ch a predicate or concept-in a formula evaluates to True if its corresponding subgraph is present in G' (i.e., an isomorphic subgraph is detected).
To provide a concrete example, to make a final prediction for an input graph G, we define R, as the logical rule for given class The graph G is classified class if the rule R, evaluates to True based on the values of the predicates (symbols) appearing in that formula. For instance, consider a GNN trained predict mutagenicity, with rule for the class "Mutagenic" (Rp). The explanation method might produce the following rule based on chemical substructure predicates:
Predicate pI: True if the input graph contains nitro group (NO2).
Predicate p2: True the input graph contains a 6-carbon ring.
Rule Rg (Mutagenic): P1 P2
Now, consider an input molecule G that contains a 6-carbon ring but no nitro group. Predicate pi (G) evaluates to False, while predicate pa (2( evaluates to True. The rule Ro Ro(G) pı (G) A (2)
therefore becomes False A True, which evaluates to False. Consequently, the input graph G is not classified as "Mutagenic" according to this rule, illustrated in Figure
We use an efficient subgraph isomorphism matching algorithm (igraph. www.h.uusssssooo.. subiscmorphic. ( vf2) to perform subgraph matching and evaluate the rules for the baseline approaches. A timeout of 10 minutes is applied to each instance (only few cases in our experiments reached this limit). Final results computed over all instances, excluding those that timed out.
16

---

Published as a conference paper at ICLR 2026
Note that in our approach, LOGICXGNN, predicate evaluates to True under either of two con- ditions: (1) when matching subgraph is found in G. or (2) when a subgraph in G satisfies the corresponding grounding rule over its features Z, given that it matches the structural pattern. We adopt condition (2) as it provides a more comprehensive evaluation framework, incorporating both structural and feature-based constraints and going beyond simple pattern matching to rule-driven assessment. This design allows LOGICXGNN to identify functionally equivalent subgraphs by leveraging the GNN's learned representations, offering more accurate explanations and better generalization than baselines, which rely solely on purely structural matching.
Computing Gron-Gro Fidelity Fidp. Following the rule-inference paradigm introduced earlier, the ground truth for computing data-grounded fidelity (Fidp) is taken to be the GNN's own predictions. Consider binary classification setting where the GNN label is either 0 or 1. The rule-based explainer produces a tuple of outputs, for example (ruleo(G)) rule, (G)). indicating whether the corresponding class rule evaluates to True. For example, in the binary classification setting, the possible outputs are:
(0,0), (0, 1), (1,0), (1,1).
When computing Fidp, the cases (0, 0) and (1, are treated False, since they indicate either multiple or no classes are satisfied, making the prediction ambiguous. A prediction is counted as correct only when there is an exact match between the GNN label and the rule-based prediction; for example, if the GNN label is O, then the rule output must be (1, 0) for it to be considered correct. The same computation scheme is also applied to other metries used in this paper, such as accuracy, recall, precision, and Fl score. Finally, to address class imbalance, we incorporate a weighting scheme so that underrepresented classes are not penalized disproportionately in the fidelity computation.
Formally, let (G) denote the GNN prediction for graph G, and let Vrale()) denote the prediction of the rule-based explainer (defined only when exactly one class rule fires). With class weights We > O, the data-groumt aata-groodded fidelity is defined as:
Fidp = EGEDa.. W (G) [[ = MGNN(G))
(12)
EGED.. W (vxo(G)
where II() is the indicator function. This weighted formulation ensures that classes with fewer samples contribute proportionally, making Fidp a fair measure of agreement between the GNN and the rule-based explainer.
B.3 REPRODUCTION OF BASELINE APPROACHES
Reproduction of GLGEXPLAINER. We conducted experiments on GLGEXPLAINER Azzolin
al. 2023) using their official GitHub repository] Following the original paper, we adopted the default hyperparameter settings and consulted with the original authors to verify our understanding and methodology, ensuring a fair and faithful evaluation.
During our study on this baseline, we made several important observations:
1. Incomplete Implementation:
The public codebase for GI.GEXPLAANNE relies on pre- computed local explanations from PGEXPLAINER (Luo et al. 2020a) but omits the code for generating them. This prevents the method from being applied to new datasets out of the box. Following the authors' guidance, we integrated the official PGEXPLAINER repository and performed the necessary hyperparameter tuning to generate these essential local explanations running properly for our experiments.
2. Instability: We observed that the explanation quality of both PGEXPLAINER and GLGEX- PLAINER is highly sensitive to hyperparameter choices and random seeds. The original authors confirmed they also faced challenges in consistently reproducing results, attributing it to "high stochasticity" in the training process. This inherent instability means that expla- nations can differ substantially across runs, affecting direct reproducibility- limitation they themselves highlight in the paper.
3. Reliance on Domain Knowledge:
The method requires external domain knowledge to derive concept representations from local explanations. To replicate the original authors' setup. we used concepts learned from our own approach to supply this necessary domain knowledge to GI.GEXPLAINER.
17

---

Published as a conference paper at ICLR 2026
In summary. reproduced results are largely consistent with those reported in the original paper, as shown in Table Specifically, the reproduced fidelity in the intermediate abstract concept space aligns closely with the results reported in the original paper (Azzolin al. 2023) and in subsequent with new datasets were confident that
work (Armgaan et al. 2024). Moreover, our experiments on GRAPH
carefully conducted under the guidance of the original authors. Taken together,
our experimental setup is fair and that our results on GRAPHTRAIL constitute a valid comparison.
Reproduction of GRAPHTRAIL. We conducted experiments on GRAPHTRAIL (Armgaan et al. 2024) using their official GitHub repository Following the original paper, adopted the default hyperparameter settings and consulted with the original authors to verify our understanding and methodology, ensuring fair and faithful evaluation.
During our study on this baseline, we made several important observations:
1. Instability: We observed that the explanations vary significantly across different seeds. The authors also acknowledged this issue. They confirmed that final subgraph explanations may indeed vary from seed to seed, although the fidelity values remain stable. This highlights that GraphTrail's s symbolic rules are not deterministic and depend on stochastic elements of the pipeline.
2. Chemically Invalid Motifs: We observed many invalid subgraph explanations for molecular datasets. The authors admitted that invalid-looking subgraphs (e.g., a hydrogen atom appearing in a ring, which is chemically impossible) can occur. In the paper, they stated that subgraphs were manually redrawn to avoid such errors. This admission suggests that the published qualitative results required manual intervention and that the current pipeline cannot guarantee chemically valid visualizations.
3. Fidelity Concerns:
The authors claimed that issues such as invalid subgraphs do not affect fidelity, since fidelity is based on c-trees. However, this also means that fidelity does not fully capture the validity or interpretability of the symbolic rules. In practice, fidelity values may be correct while the extracted rules remain trivial or domain-invalid.
In summary, our reproduced results are largely consistent with those reported in the original paper, as shown in Table g In particular, the reproduced fidelity in the intermediate abstract concept space aligns closely with the original findings (Armgaan et al.) 2024). Taken together with our direct communication with the original authors, we are confident that our experimental setup is fair and that our results on GRAPHTRAIL provide a valid comparison.
Moreover, the issue of chemically invalid motifs, which the original authors themselves acknowledged, provides further motivation for the development of our proposed LOGICXGNN, By explicitly addressing the unreliable grounding of baseline methods, LOGICXGNN ensures that the learned explanations are not only faithful but also scientifically valid and interpretable.
B.4 THE INEFFECTIVE GROUNDING ISSUE BASELINE APPROACHES
The grounding issue of GLGEXPLAINER. While the subgraphs produced by GLGEXPLAINER
are structurally valid, their grounding often results in explanations that are unrepresentative or trivial. The primary issue lies in its two-stage, post-hoc process, which first clusters large set of local explanations into abstract concepts and then selects a representative subgraph for cach.
As the code in Figure 7 illlusraates the method simply visualizes the top examples that best match a learned prototype after the concepts have already been formed. The critical weakness that the initial clustering groups dissimilar or noisy local explanations together, the resulting "concept" becomes incoherent. Consequently, the final representative subgraph, though a valid member of the cluster, may only be trivial poorly representative example, leading an unfaithful explanation of the model's behavior.
The grounding issue of GRAPHTRAIE During our analysis, we identified a critical issue with how GRAPHTRAIL grounds its explanations by generating subgraphs from computation trees, problem the original authors acknowledge as a bug. Upon inspection, we found that the method reconstructs invalid subgraphs by mismatching node attributes with the underlying graph structure.
18

---

Published as a conference paper at ICLR 2026
materialize prototypes
[M6)
churge maxdan furetion to scovdtaccnte ose just to cospate ststance betveer local aipla, and prototypes prototyser
best, Loppuonl hts.yr///essstttteee sasitgntaas"") "sua"
Kutraln cerooptsasssgreeenn
Te,classes 16.ides best_eapl,
www.ppyyyeerepppooooooooo ("arstgn_hatt"")
preis_naecs rathers". "991_2""
Torch.menual seed fig - www.re/iigiiee-iiaii
for caspechest hyper Preu protatyses"))
ioc zdre Iterch randpam lan Lddall a for randon dxanptes
concepts sopigroeest assigsenesi
L0xe (terch.argap arguortiaa descendangerroel)
satplest
util Lewelculleeee datesess trasltttdiieeettaaaaliiaa trapeeeiiiaaaatttaaiaaa Car.aanniiooilllii cerssiteepluutrree
(rrs protatyses"")
glt ussa at ltes Loull-rrer pww.ggrotaatsesaaaa. "1.5 Sep pitaylasesi (grate_
plt shoul
Figure Code from GLGEXPLAINER for selecting representative subgraphs. This post-hoc selection can yield unrepresentative examples if the underlying concept cluster is poorly defined or contains noisy local explanations.
This еπгог originates in the utils. dfs function, shown in Figure 8 The function attempts to merge two different graph representations: ctree (containing rich attributes like atom types) and stree_id d (using simple integer IDs). It operates on the flawed assumption that the nodes in both graphs are identically ordered, mapping them by their list position rather than a stable identifier. Crucially, the original author's comment in the code, Incorrect, explicitly acknowledges this flawed premise. Consequently, the subgraphs produced by this function are often structurally invalid, undermining their reliability as faithful explanations.
96
def dfstetree, ciree_id, indk.seoppingnteenn::
90
Incorrect
generated writing
109
genersted, llence, the node order between the tvo preserved, Therefore, we car map attriburtes ctree_ls's attributes. Grapht)
182
184
for in ranger Lentetree Lown:crro_dd.nneesll. nd.notts)
noda_ mapping None:
186
altr nale, easping irveunades [i] [3attr
else:
ctree. ['attr!
185
Guadd, nadelctree, ro.rodes Patter1, attrratte)
ctree_is.esgee
111
src, dest s
larcl l'attrl| 113 dest = (ess)) ('sttr')
G.adi_ctgetsre, attrectree_ds.ckt ("attr'])
135 reture G
Figure 8: The flawed sttilsaae d.s function from the official GRAPHTRAIL repository. The original author's comment (! Incorrect) confirms the function's incorrect assumption about node ordering when reconstructing subgraphs.
Why our approach du achieves effective grounding? The effectiveness of our grounding process for ΦM stems from its rigorous, data-driven foundation. Our method begins with systematic cataloging of all structural patterns as they appear in the training data. This detailed "bookkeeping" ensures that every subgraph used for grounding is guaranteed to be both structurally valid and highly representative, as drawn directly from real instances.
Furthermore, dM moves beyond simply showing these examples. It learns formal grounding rules top of this empirical collection, providing a precise, logical explanation for why given structural pattern is important for the model's prediction. This combination of data-backed, representative
19

---

Published as a conference paper at ICLR 2026
subgraphs and the formal rules that govern them provides grounding that is both faithful to the data and deeply interpretable.
B.5 ADDITIONAL RUNTIME COMPLEXITY ANALYSIS
The complexity analysis in the main paper simplifies the overhead of training decision trees due to space constraints. We clarify here the computational cost associated with training the grounding decision trees. For each predicate p. we construct dataset of representative subgraphs and train shallow decision tree low-dimensional structural features. Standard CART-style training has complexity of (dg, N, log Np). In our implementation, the feature dimension dp is small constant representing simple predicate-level statistics. Furthermore, the number of training examples N₂ S [V] because each example corresponds to grounded subgraph, and the total number of predicates is bounded by O(V)).
Summing the cost across all predicates yields the total complexity:
Σ OldpN Nog S
Σ O(VD)
0(1 log VI) = O(D2 log [V]).
(13)
This result is consistent with the O(I))2) grounding term reported in the main paper. The additional log |V] factor is mild in practice; since the trees intentionally kept shallow and dy is constant, this overhead remains negligible compared to the costs of subgraph extraction and predicate construction.
C ADDITIONAL EVALUATION RESULTS
Table 7: Running record on three large datasets using 4 CPU cores.
Dataset
Seed
Fid (%)
Mem. (GB)
Time
CPU usage
Reddit Threads
0
86.82
36.1
h 06 min
102
Reddit Threads
1
87.35
36.7
h 06 min
103
Reddit Threads
2
87.99
36.7
h 10 min
98
Twitch-Egos
0
57.49
69.2
2 h 02 min
98
Twitch-Egos
1
57.81
69.5
2 13 min
92
Twitch-Egee -goos
2
55.01
69.2
2 18 min
95
Github Stargazers
0
65.79
64.9
3h35 min
Github Stargazers
1
59.49
84.6
3 h min
95
Github Stargazers
2
66.85
79.9
3 18 min
C.1 FIDELITY COMPARISON
We compare the original eiceity-computdd in the intermediate, uninterpretable concept space and reported by the baselines- against their data-grounded fidelity (Fidy), computed in the final grounded form, in T Under this more rigorous metric, the performance of existing methods drops significantly, underscoring the need for explanations that both faithful and genuinely interpretable.
C.2 RUNNING RECORD ON THREE LARGE-SCALE BENCHMARKS
We report the running record of our approach, LOGICXGNN, on three large-scale benchmarks in Table 7 Our method is the only existing approach that scale to this size with high efficiency, as indicated by its low and stable memory usage.
C.3 ADDITIONAL METRICS ON EXPERIMENTS OVER FIVE COMMON DATASETS
To ensure robust and reliable comparisons, addition to Table we also report the weighted test accuracy, precision, recall, and Fi-score, averaged across three runs, in Tables 9 10 11 and T2
20

---

Published as a conference paper at ICLR 2026
Table 8: Data-grounded fidelity Fid (%) in percentage and original fidelity Fid of all baselines, averaged over three random seeds. For each dataset, the highest fidelity is highlighted in bold. Since our approach reports only Fidp, its Fid entries are omitted and marked with "_" indicates cases where no rules were learned.
BAShapes
BВBP
Mutagenicity
NCI1
IMDB
Method
Fid
Fido
Fid
Fide
Fidp
Fid
Fide
Fid
Fide
GLG
57.50 uus
31,09 131
52.50
0.50
62.16
38.98 1:300
58.09
2.11
9.61 1:776
$2.50 0.5
0.00 4:00
G-TRAU.
84.67
79
97.
50.00
68.70
60.04
35, 35.351
der (Ouns)
82.67 1.8
85.32 196
81.36 2:13
73.81 236
74.17=
respectively. The highest scores are highlighted in bold. Note that precision, recall, and -core are computed against the GNN predictions, following the evaluation protocol used in GraphTrail Armgaan et al. (2024).
Table 9; Test accuracy of various explanation methods (%) graph classification datasets.
Method
BAShapes
BBBP
Mutagenicity
NC11
IMDB
GLG
41.14 + 4.81
38.37 + 0.46
3.73 + 8.57
0.00 + 0.00
G-TRAIL.
78.88 5.14
55.10 + 3.82
59.72 4.37
56.69 + 1.46
30.20 + 4.23
ΦM (Ours)
82.67 0.57
78.06 + 4.28
68.69 = 2.01
63.63 + 2.93
74.16 + 6.75
Table 10: Weighted precision of various explanation methods (%) on graph classification datasets.
Method
BAShapes
BBBP
Mutagenicity
NCI1
IMDB
GLG
28.85 + 5.49
70.63 + 6.59
67.64 + 4,45
0.00 + 0.00
G-TRAIL.
80.05 + 6.48
59.12 + 2.81
64.45 + 1.14
61.18
+ 2.51
39.60 + 9.66
ΦM (Ours)
82.76 + 0.61
92.10 + 0.88
81.71 + 1.77
74.19 + 1.73
82.78 2.68
Table 11: Weighted recall of various explanation methods (%) on graph classification datasets.
Method
BAShapes
BBBP
Mutagenicity
NCI1
IMDB
GLG
31.09 + 5.81
38.98 = 3,01
9.61 + 7.76
0.00 + 0.00
G-TRAIL.
79.82 + 3.65
50.00 + 0.00
65.93 + 3.83
60.04 +: 4.91
35.35 + 2.85
ΦM (Ours)
82.67 + 0.57
85.32 + 2.96
81.36 2.12
73.81 + 2.26
74.16 + 6.75
Table 12: Weighted Fl-score of various explanation methods (%) on graph classification datasets.
Method
BAShapes
BBBP
Mutagenicity
NCI1
IMDB
GLG
31.77 3.46
32.08 0.46
11.66 + 8.29
0.00 + 0.00
G-TRAIL
78.26 + 5.15
66.84 + 2.49
57.53 + 5.82
53.01 + 3.92
32.45 + 1.94
ΦM (Ours)
82.68 + 0.56
92.11 + 0.78
81.44 + 1.92
73.66 + 2.02
71.43 + 7.82
C.4
EMPIRICAL EVIDENCE FOR GENERALIZABILITY ACROSS GNN ARCHITECTURES
Table 13 reports the best baseline fidelity (Base.) and the fidelity of our approach, Φv. across multiple GNN architectures. The table also includes the classification accuracy the underlying GNN models (M) for reference. Note that the GNN architectures GraphSAGE and GAT achieve only 47.50% accuracy on the BAShapes dataset due to their limited expressive power. These results are consistent with the findings reported in Armgaan et al. (2024). dы consistently achieves high fidelity across all architectures and datasets, uniformly outperforming the baselines. This demonstrates both (1) the strong generalizability of ΦM across different GNNs and (2) its sfate-of-the-arr explanatory fidelity.
21

---

Published as a conference paper at ICLR 2026
Table 13: Fidelity comparison of LOGICXGNN against baseline methods across multiple GNN architectures. M denotes the underlying model's classification accuracy (%), Base. denotes the best baseline fidelity (%) from the better of GLGEXPLAINER and GRAPHTRAIL; and ΦM denotes the fidelity of our method, LOGICXGNN (%).
GCN
GraphSAGE
GIN
GAT
Dataset
M
Base.
4M
M
Base.
M
Base.
M
Base.
BAShapes
80,50
72.02
82.67
47.50
73.69
100.00
80.50
72.81
83.00
47.50
82.98
100.00
BRBP
80.88
50.00
85.32
84.80
50.00
86.76
50.00
80.08
80.88
50.00
83.75
Mutagenicity
78.69
65.93
81.36
76.15
61.69
79.23
76.73
61.80
77.96
76.61
61.80
77.27
IMDB
74.50
35.35
74.16
73.50
25.67
76.00
74.00
25.67
75.00
76.00
26.98
72.50
NCII
70.56
60.04
73.81
70.07
59.25
69.70
70.56
61.84
74.20
70.32
57.67
68.11
D
MORE DETAILS ON GROUNDING ΦM INTO THE INPUT FEATURE SPACE X
D.1 ON THE CANONICAL REPRES SUBGRAPH INPUT FEATURE Z
To create a canonical representation, we partition the node set into orbits and establish a consistent ordering using Algorithm The ordering scheme employs hierarchical multi-criteria approach that ensures deterministic results:
The orbit containing the anchor node is always placed first Remaining orbits are sorted by cardinality in ascending order 3. Degree signature: sequences
1. Anchor priority:
2. Size ordering:
Orbits with identical sizes are distinguished their sorted degree
4. Distance profile: Further ties are resolved using sorted distances from the anchor node
5. Node identifiers: Ultimate disambiguation is achieved through sorted node identifiers
We prove in Theorem D.I that this multi-criteria lexicographic ordering produces deterministic total order, ensuring the canonical representation can reliably reproduced across identical graph structures.
Algorithm 1: Stable Orbit Decomposition with Anchor
Input: Graph G, anchor node
Output: Orbit labels L and sorted orbits O
Function Stable@OrbitDecomppss
ion (G,
D + CompuueAnnchorrDDstuesCCCC.CC. /* Calculate shortest path distances from
anchor //
+ FindAlllAutomorrphissssCC
/+ Enumerate all graph symmetries +/ Group nodes into symnetry equivalence
Oraw ExtractoodOrrbiis2... G)
classes +/
Oanchor +- IdentifAAnchorOrbii( rraw; a) /x locate orbit containing anchor node
w/
O StableSortOrbis((Ora... CaaanOOrrn..naaaaa Ounchor, D.G) /s Sort by size, degree, distance, node IDs +/ t- AssignCanmmicallaacts(....0 priority +/ return (L,
/* Map nodes to orbit labels with anchor
Theorem D.I (Orbit Sorting Consistency). The multi-criteria orbit sorting scheme employed in Algorithm produces deterministic total ordering for any graph with fixed structure and anchor node.
Proof. Let O = {0,, Oz...., Ox} be the set of orbits obtained from the automorphism group decomposition. We define the sorting key for orbit O as:
Key(O,) |, d; dist, ids;)
(14)
where:
22

---

Published as a conference paper at ICLR 2026
O is the orbit size
d sorted O:]) is the sorted degree sequence
dist; sorted((da(a, u) v E O:]) is the sorted distance sequence from anchor
ids; sorted(O;) is the sorted node identifier sequence
We prove that this lexicographic ordering induces a strict total order on O.
Well-definedness: Each component is well-defined for any finite graph: |O:| N, d; Nlo., dist, (N U (oo)))oo, and ids; finite sequence of distinct node identifiers.
Totality: For any two distinct orbits Oz, Og with i # j. we have O, Do = 0 by definition of orbit decomposition. We show Key(O,) + Key(O,) by case analysis:
1. If |0,| + 10,], then Key(O.) + Key(O,) immediately.
2. If |0, |001 but d; # dj. then the orbits have different degree signatures, so Key(O,) + Key(O,).
3. If [0,| 10,1 and d, = d, but dist, * dist,, then the orbits have different distance profiles from the anchor, so Key(O,) Key(O,).
4. If 0,, 10 d, d and dist, = dist, but ids; + ids,, then the orbits contain different sets of nodes (since node identifiers are unique), so Key(O,)) + Key(O,).
Tiebreaker completeness: The final case cannot oceur when O O,- Suppose |0,| 10yl- d; = -j. dist, dist,, and ids; idsy. Then sOrted(O;) = sorted(Oj), Since node identifiers unique within graph, this implies O, and Oj contain exactly the same nodes, contradicting the assumption that i * (orbits are disjoint).
Determinism:
Each component of Key(O,) is computed deterministically from the graph structure and anchor choice. Since lexicographic comparison admits no ties between distinct orbits and standard sorting algorithms are deterministic, the resulting orbit ordering is completely determined by the graph structure.
Therefore, the multi-criteria sorting scheme produces a unique, deterministic total ordering of orbits for any fixed graph structure and anchor node.
Remark D.2. This result ensures that the stable orbit decomposition is reproducible across multiple runs for the same graph instance. The hierarchical sorting criteria are designed to resolve ties progressively finer granularities, with the node identifier sequence providing ultimate disambiguation. Since our method operates on graphs with consistent structural representations, the deterministic ordering property is sufficient for ensuring algorithmic reliability.
D.2 EXAMPLES WITH GUIDANCE READING GROUNDING RULE VISUALIZATIONS
We show an example of our generated explanations for a single predicate Pac from the real-world dataset BBBP in Figure with the grounding rule visualization presented in Figure (aa] Note that each orbit in the visualization is labeled and colored differently. The figure illustrates three node orbits, such Orbit 0 (the central red node) and Orbit (the blue node). and an edge orbit. Orbit (the four thick teal edges). This distinction improves the fine-grained expressiveness of our grounding rules, enhancing the structural specificity of the explanation.
The grounding rules are presented in Disjunctive Normal Form (DNF), where the overall explanation disjunction cases (clauses) connected by an implicit "or." Each case a conjunction of conditions on different orbits. To interpret these rules:
Case Structure: In Figure ((a) two cases are shown. Case 1 is the conjunction of the condition on Orbit 2 (' #0 I') and the condition Orbit 3 (? # (C, 0) >= 1'). Case 2 is the conjunction of the condition on Orbit 2 (' 40 0r) and the conditions on Orbit (? # (C, () 2 and # (C, N) 0')
23

---

Published as a conference paper at ICLR 2026
Grounding Rule Visualization for p36
(hods)
crbit mode) Drbat (idgga)
Orbit
DIbR
Drbik 2
Case 1: orbit 2: +0 and arbit 3: '#EC. Q) >
Case 2: orbit 2: 80 0 and arbit 3: *#(C. Q) >- 2 and #CC, N)
(a) An example of ground-rule explanations for a single predicate pao.
explanation graphs for p36
Doverig:: 28 00%
Conoragg: 22 60%
Coviaage: 7.33%
Covcrage: 7.27%
Diveaag:: 5.00%
(b) Top 5 subgraph explanations for a single predicate Pao- Coverage below each subgraph indicates the percentage of instances that activate the predicate Pas in which this subgraph occurs as an explanation.
An example of grounding rule explanations (top) and subgraph explanations (bottom) generated by our proposed approach dv-
Figure 9:
Node Orbit Interpretation: Orbit 2 is node orbit. The condition ' #0 1' in Case 1 means that the node(s) in Orbit 2 must include exactly one Oxygen (O) atom; #0 or in Case 2 forbids Oxygen in that orbit.
Edge Orbit Interpretation: Orbit 3 is an edge orbit. The condition # (C, 0) >= 2' in Case 2 means that at least two of the edges in Orbit must connect Carbon (C) atom to an o forbids Carbon-Nitroge edges in that orbit.
Oxygen (O) atom, while 4 (C, N)
Case Satisfaction: A specific case is satisfied only if all of its conjunctive conditions are met simultaneously. The model's prediction is explained the input graph satisfies least one of the listed cases.
major limitation of existing explanation methods their ineffective grounding, as they often associate each concept with single, possibly cherry-picked subgraph. Our approach provides shown in Figure (b) we display the top-5 representative
a richer, data-driven alternative. subgraphs for each rule, ranked by their frequency in the dataset. Coverage quantifies the proportion of instances activating predicate P36 in which each subgraph occurs as an explanation, providing a more comprehensive view of the concept's presence across the data.
This strong alignment between our abstract rules and concrete examples is a direct result of our methodology. We first extract these subgraph instances directly from the data and then learn the general grounding rules from this empirical collection. The resulting dual representation a formal logical rule paired with ranked set of visual instances-offers more detailed and multifaceted
24

---

Published as a conference paper at ICLR 2026
Grounding rule explanation for p38
DIDIt
0 Node
orb 1 No
OrB hode
Node
Orbit
Orbat
Orbit
(arbit (arbit
Figure 10: An example of grounding rule explanations on continues feature space generated by our proposed approach ΦM.-
explanation than existing methods, yielding deeper, more robust, and ultimately more interpretable grounding of the GNN's behavior.
D.3 EXAMPLE: GROUNDING (6M) IN A CONTINUOUS FEATURE SPACE
We demonstrate our method's ability to generate explanations continuous feature space using predicate Pas example (Figure TOP. For demonstration only, Pas is trained synthetic dataset constructed by replacing discrete node features with continuous random features in a subset of Mutagenicity. To the best cases effectively. Their reliance on discrete attributes means their subgraph explanations lose meaning when faced with continuous feature distributions. Our approach addresses this limitation by leveraging orbit-based feature aggregation combined with learnable, threshold based rules. The grounding rules are formulated in Disjunctive Normal Form (DNF), where different cases are connected with an implicit "or." To interpret these rules:
knowledge, most existing explanation approaches cannot handle such
Case Structure: Case 2 is a conjunction of three conditions: the condition on Orbit
(f_0 (orbit 0) > 0 0.94), on Orbit 3 (f_1 (orbit 3) > 0. 0.04), and on Orbit
(f_4 (orbit 2) <= 0.1.).
Orbit-based Aggregation: Each orbit aggregates continuous features from its constituent nodes using a statistical function (e.g., mean). This provides a robust summary of the features for all structurally equivalent nodes within the pattern.
Continuous Feature Interpretation: The condition f_0 (orbit: 0) 0 94 means the aggregated value of the O)-hh feature dimension across the nodes in Orbit 0 must exceed 0.94. Similarly, other conditions apply learned thresholds to different feature dimensions of their respective orbits.
Adaptive Threshold Learning: These numerical thresholds (e.g., 0.94, 0.04, 0.14) are not fixed but are learned during training to define optimal boundaries that best discriminate between prediction classes.
Case Satisfaction:
Case 2 is satisfied only when all three of its threshold conditions are met simultaneously, ensuring that both structural and feature constraints work in conjunction.
25

---

Published as a conference paper at ICLR 2026
Traditional subgraph-based explanations are ill-suited for this setting. They typically produce single graph structure with discrete labels, which fails to capture the nuances of how continuous feature distributions influence model's prediction. In contrast. our orbit-based rules provide more robust and expressive explanation. By aggregating features across structurally equivalent nodes and learning discriminative thresholds, our method specifies how continuous feature values within a given topological pattern collectively drive the model's 's decision. This capability enables our method to deliver meaningful, interpretable explanations for complex real-world datasets where traditional approaches fail due to the prevalence of continuous attributes.
E
ADDITIONAL. DETAILS OF RULE-BASED EXPLANATIONS
E.1 THE METRICS: COVERAGE, STABILITY, AND VALIDITY
To complement this qualitative analysis, we quantitatively evaluate the generated explanations using set of objective and reproducible metrics that reflect their practical utility to end users:
The proportion of target-class instances for which the rule-based prediction remains correct when restricted to only valid subgraph patterns (i.e., after removing all invalid patterns). Formally,
Coverage:
Coverage( (6) 1x E Do d(x) = True)
(15)
[Del
where 6(x) is True iff evaluating the rule on æ using only valid subgraph patterns (i.e., considering their presence or absence) predicts class Here, "valid" refers to subgraph patterns that appear actual subgraphs of molecules in the dataset, ensuring they are derived from structurally valid molecular graphs rather than artificially constructed or chemically impossible fragments.
Stability: The consistency of explanation subgraphs across multiple runs with different random seeds. This metric is crucial for building user trust, as inconsistent explanations undermine confidence in the model's reasoning. We measure stability as the fraction of subgraphs repeated in all runs relative to the largest number of subgraphs in any single run:
n 01
Stability((o:):.))
(16)
max;=1,.... |6b]|'
where o denotes the set of subgraphs discovered in the i-th and & is the total number of runs. In this case of k = 3 (3 runs), this simplifies to
Stability = 161 n 62 n 0s)
(17)
maax(1on 102) [oal}
Validity: The proportion of explanation subgraphs that correspond to valid chemical frag- ments or structural motif's found in the dataset. For molecular datasets, this ensures that the generated explanations respect chemical constraints and represent realistic molecular substructures. Invalid fragments (e.g.. impossible bond configurations or non-existent func- tional groups) reduce the practical utility of explanations for domain experts. We define validity as:
|[ E $ / Fvatial
Validity
(18)
[
where & is the set of all generated fragments and Fralid represents the set of chemically valid fragments derived from the training data.
In Figures 4 and 5 we normalized the complexity of the generated rule-based explanations for all approaches for clearer visualization. Specifically, we configured each approach-sstting the tree depth for ΦM, specifying the number of concepts for GRAPHTRAIL, and selecting the top-k subgraphs for GLGEXPLAINER predicates) per class. This choice does not affect the fundamental nature of the methods, and we maintain hyperparameter and random seed settings consistent with the results in Table ??.
generate rules of comparable scale, using 3 concepts (or
26

---

Published as a conference paper at ICLR 2026
however, different complexity was required. A fair comparison of stability necessitates normalizing explanation complexity to a level that is both chal- lenging and informative. Through preliminary analysis, we found that a low complexity setting (e.g.. 3 concepts) was insufficiently discriminative for a rigorous comparison. In this setting, our method achieved near-perfect stability, creating ceiling effect that, while demonstrating its robustness, prevented a more nuanced assessment of relative performance against the baselines. To create a more challenging benchmark that allows for a fine-grained evaluation across all methods, we chose a moderate complexity of approximately 5-6 concepts per class, as this was empirically determined to be the most informative for comparing the stability of the different approaches. For all other metries, we use the default hyperparameter and seed settings for each explainer, consistent with Table ??.
For the stability experiment in Section 4.2
E.2 FURTHER ANALYSIS OF TABLES AND
Table reveals important distinction between the baselines in the binary classification setting. GLGEXPLAINER produces rules for both classes, but these rules are often conflicting and rely on less representative subgraphs. resulting in very low coverage (c.g.. only 6.11% for Mutagenicity class 0). Another major limitation of GLGEXPLAINER is its reliance on prior knowledge and its high sensitivity to hyperparameter choices an issue explicitly acknowledged by the original authors (Azzolin et al. 2023). This makes the method less applicable to new datasets; for example, despite replicating their settings with direct guidance from the authors, GLGEXPLAINER failed to learn any rules on BBBP. We discuss these reproducibility challenges in more detail in Section B.3 By contrast, GRAPHTRAIL generates only unilaterul rules. This design makes it artificially easier for GRAPHTRAIL to appear correct-since all instances of the opposite class are explained by default-but at the cost of explanatory quality, as the method produces only discriminative rules rather than descriptive rules for each class. Furthermore, because GRAPHTRAI frequently produces chemically invalid subgraphs, many of its explanations cannot be considered constructive, as they depend merely on the presence or absence of subgraphs that never occur in the dataset, further reducing effective coverage. We also consulted with the original authors and confirmed this issue, as discussed in Section B.3 This combination of unilateral shorteuts and invalid fragments underscores why GRAPHTRAIL 's explanations are unsuitable for faithful or practical interpretability.
In sharp contrast, our approach dm learns rules for both classes while still achieving very high coverage (e.g., 80.06% and 82.58% for Mutagenicity, and 47.86% and 98.16% 16% for BBBP). Achieving strong performance under this stricter and more balanced setting is particularly noteworthy, as demonstrates that dM provides class-wise explanations without relying on unilateral shortcuts or invalid patterns. This fairness in rule construction makes the comparison against baselines more rigorous and highlights the strength of our method in generating meaningful explanations that remain faithful to the underlying model.
Table 4 complements this picture with stability and validity. Φæs attains the highest stability across seeds (66.67% on Mutagenicity, 60.00% on BBBP), surpassing GLGEXPLAINER on Mutagenicity (40.00%) and GRAPHTE AAI (37.50% on Mutagenicity, 20.00% BBBP). High stability suggests that ΦM learns rules that are robust to randomness in training and sampling. On validity, &M reaches 100.00% + 0.00 both datasets, matching GLGEXXLAINER on Mutagenicity but far exceeding GRAPUTRAIL (61.90% + 6.73 on Mutagenicity and 0.00% on BBBP).
Taken together, the results across coverage, stability, and validity form consistent narrative: while GI.GEXPLAINEE suffers from conflicting rules and poorly representative explanations, and GRAPH- TRAIL exploits unilateral shortcuts compounded by invalid and equally unrepresentative subgraphs. σM generates balanced rules for both classes that are faithful, reproducible, and chemically valid. This balance is particularly rare in explanation methods, underscoring the robustness and scientific reliability of dM as a framework for generating high-quality graph explanations.
Why don't we use human study in this work to assess the final explanations? While human studies are widely employed in XAI for interpretability assessment, they are particularly ill-suited for scientific domains like biochemistry for several key reasons: (1) Meaningful evaluation in such contexts demands domain expertise, making large-scale recruitment of qualified participants prohibitively difficult and expensive. (2) Laypeople's subjective perceptions of "understandabilitt"" often diverge significantly from scientific validity explanations that appear intuitively clear may be biochemically erroneous fundamentally misleading. (3) Human evaluations inherently introduce
27

---

Published as a conference paper at ICLR 2026
substantial variability due differences in participant expertise levels, experimental design choices, and evaluation criteria, thereby compromising the reprodueibility essential for scientific validation.
We therefore adopt objective, quantitative metrics, coverage, stability, and validity, specifically designed to evaluate biochemical explanation quality. This framework prioritizes generalizability. consistency, and scientific accuracy, providing rigorous alternative to subjective assessments that aligns with the precision requirements of scientific inquiry.
E.3 MORE EXAMPLES
We present the generated rule-based explanations of our approach ΦM on BAShapes, BBBP, Mu- tagenicity, and IMDB. NCII is excluded because the information its feature attributes is not available. Although the features are one-hot encoded for atoms, the mapping between atoms and feature indices has not been released, we chose report results for NCI1.
IMDB Dataset Classification Rules (Depth 10)
(7Po A PP24 A PP267 A P2268 A 7P1 A P220 A P276 A P333 A P278 A P2222
V (TPo PP27 P227 A P226 P16)
V (Po) = IMDB Class O;
(-po A -P274 A PP67 P266 A PPG A P270 A P276 A -P333 A -P78 A p282)
V (TPO A PP74 P267 A P268 PPG P270 P276 A P333 P278)
V (-po/ A -P274 A PP27 A 12268 A PP1 A P270 A -226 A P333)
V (-po A -P274 PD27 A P2668 A PPI A P220 A P276)
V (-PO A -P274 P267 A P2268 A PPG A P270)
V (TPo A PP27 'P26 A '2268 A P268)
V (-Po A P274 A -D267 A P267)
V (-Po A P274) + IMDB Class
BAShapes Class O Rules: (Depth = 5)
BAShapes Class 1 Rules: (Depth = 5)
(-P250 A Ps2 A Pa22 A Pss A -P4495)
P2200 A Ps2 A Pu22 A PPs A P4495)
V (-P280 A P52 PP32 A P55 A -P11)
V (-p280 A Pp5 A -P321 A Pss A P11)
V ( (-P280 A Ps2 A P524 A Ps87 A P49)
V ( P-2280 A Ps5 A Ps24 ^ Ps877 PP1)
V (7P280 Pas Ps24 P587)
V P-P280 A P52 A -ps -P324 A Ps5) V ( (-P280 A P52 A -p P321)
(-P280 A Ps2 A -ps A P324 A PP55)
V (-P280 A P52 A Ps A -ps6 A P1207)
V (-P280 A P52 A Ps Pas -P1207)
V ( (-P28u A P52 A Ps A PsG)
V (p280 A P204 A P698 A P1817 A PP1s))
V. (p280 A P204 P6998 A P1817)
V (p280 A -P204 A P698 P1817 A p11))
V. (p280 A -P201 P698)
+ BAShapes Class
V (p2so A P204)
BAShapes Class 0
BBBP Dataset Classification Rules (Depth = 3)
(<Pas A "Ps A Pa1) V (-Pas Ps A PP59) V (-Pas A Ps A P59) V (Pas P61 P20) V (Pas A Per A -P54) V (Pas A Pei A P54) + BBBP Class 0;
(-pss A 7Ps A PP3) V (pas P61 P22)
BBBP Class
28

---

Published as a conference paper at ICLR 2026
p274
p276
p278
p282
p313
Figure 11: Our approach's 's grounded explanation (ØM) for IMDB.
p8
p14
p36
p49
p52
Figure 12: Our approach's 's grounded explanation (Φxr for BAMultiShapes.
Mutagenicity Dataset Classification Rules (Depth = 3)
(~p2 P20 pps) V (p2 A "Pas A -pe4) V (p2 A pas A p17) Mutagenicity Class O;
(-p2 P220 P11) (-p2 A P22 A p1) V (-P2 A P2o Pas) V (p2 A -aas A P61) V (p2 A P3s A P17) = Mutagenicity Class 1
29

---

Published as a conference paper at ICLR 2026
Exprosetaiio Eangrphy
Reprosmnaiio
teprsentativ Bubyrauh
Te hepesse merive Sulgrrate
Ty Eepererettttooo boyte
Greandnng Bude ahbtbbe
Figure 13: Our approach's 's grounded explanation (dM) for BBBP.
30

---

Published as a conference paper at ICLR 2026
Top ddggoph
Top Augrephi kor??
broatdin F VIAI CatEn
Scceniing Kine Fitaataatoo for pilt
SreaN
RAIN
Figure 14: Our approach's 's grounded explanation (6x) for Mutagenicity.
31

---

Published as a conference paper at ICLR 2026
F LLM USAGE
Large Language Models (LLMs) were used as general-purpose assistive tool in the preparation of this work. Specifically, LLMs supported tasks such as refining the clarity of writing, suggesting alternative phrasings, and checking the consistency of technical terminology. They were not used for generating research ideas, conducting experiments, or producing original scientific contributions. All substantive research decisions, analysis, and results presented in this paper are the responsibility of the authors. The authors have carefully reviewed and verified LL--assisted text to ensure accuracy and originality.
32


Reviews:
[{"review_id": "UVdDUJxwoh", "reviewer": "Reviewer_AscN", "summary": "The paper proposes a novel approach to post-hoc explanations of graph classification, based on concepts. Differently from previous methods, however, it grounds the explanations into actual patterns in the data by means of Weisfeiler–Lehman (WL) graph hashing.", "questions": "My main question is regarding the applicability of the proposed method to node classification task:\n- is it feasible to consider the same framework also in this case? \n\nMy guess is that the hashing could be re-used similarly but possibly also the decision trees to select the patterns over the embeddings and the one over the activation matrix.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "- The paper is well written and presented. \n- The methodology is not particularly complex, but it allows creating a very effective method\n- Section 3.4 reports a very nice Analysis subsection, theoretically describing the computational complexity of the method and its applicability to different gnn architectures\n- The experiments show a clear advantage of the proposed method against a couple of state-of the-art baselines", "weaknesses": "General weaknesses:\n- The paper does not have a limitation paragraph, which is now considered almost mandatory in top-level conferences\n- The scope of the proposed method is focused to explanations regarding graph classification only (similarly to the baselines). It would be very interesting if the authors could show or even just describe whether the proposed method could be applied to node classification, or if any methodological assumptions fail to hold in that case. \n- Also in several parts there are mentions of graph tasks, suggesting that different types of tasks have been considered, which does not seem the case: only multiple instances of the graph classification task have been tested. I would recommend rephrasing as it is currently misleading.\n- One of the main result of the paper is that previous baselines provide explanations that are not grounded. However, in the main paper (I saw them in the appendix) there are no mentions regarding how the baselines have been reproduced. Without at least a footnote saying how the explanations for the baselines have been extracted, Figure 1 results too strong and may rise critiques.\n\n\nSpecific weaknesses:\n- The sentence \"As a result, LOGICXGNN not only generates a rich set of representative subgraphs but also learns generalizable grounding rules for each predicate, addressing unreliable grounding in existing methods.\" is not very clear I would suggest rephrasing.\n- $p_j$ and $P$ are not properly defined", "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": "4wmFFbyxoP", "reviewer": "Reviewer_nxGX", "summary": "This paper presents a framework to extract logic rules as explanation structures for GNN outputs. The method encodes node receptive fields using a WL kernel-based hash function and trains a decision tree to generate regulations that consistently classify the model's predictions. Conjunctive logic rules are extracted as grounding rules to link predicates with the input feature space. An experimental study verified the methods' efficiency, fidelity, and scalability.", "questions": "D1. A main challenge is how to ensure the explanation structures are better grounded in genuine real-world evidence, while the process yields rules based on GNNs that still seem to focus on the models' faithfulness. Have any human experts or authorities assisted in evaluating the generated rules?  How will such a measure be quantified, if possible? \n\nD2. The time cost omits several sources of overhead, such as training decision trees; a more complete analysis is not in place. \n\nD3. Is the method model-specific? Meaning: if one changes to another test set or another model, does the method need to be restarted from scratch, even when the graph is not changed? How may the method respond to larger-scale analysis?\n\nD4. There is a lack of in-depth analysis of how likely the rules are to be redundant or logically entailed by others—a missed opportunity for optimization? \n\nD5. Other approaches, including motif-based GNN explanation, directly output graph patterns or subgraphs, which can be readily converted to conjunctive triple patterns or rules. Representative work needs to be compared with.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "S1. There is novelty in WL hashing-based structural encoding and decision tree for generating logic rules. \nS2. The overall method is justified with a cost analysis. \nS3. Results support the major claims.", "weaknesses": "W1. The link between the quality of the generated rules and their closeness to real-world evidence remains unevaluated. \nW2. The time-cost analysis lacks a more rigorous elaboration. Important steps seem overly simplified or omitted. \nW3. More baselines are needed, such as motif-based GNN explanation, which can directly generate explanations as subgraphs.", "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": "wguFS2EDiI", "reviewer": "Reviewer_kLwi", "summary": "The paper addresses a real limitation in current global explainability methods for GNNs: they derive logical rules in a latent or concept space, and only afterwards associate these latent concepts with illustrative (sub)graphs; as a result, the generated example (sub)graphs often fail to correspond to real structures in the dataset (in molecular datasets, some are even chemically invalid). \nThe author propose a multi-step framework that learns logical rules whose predicates are directly grounded in subgraphs observable in the input data. The method is compared against two relatively recent baselines (GLGExplainer and GraphTrail), which the authors re-evaluate by substituting their latent concepts with the representative subgraphs provided by those methods. A new evaluation metric called data-grounded fidelity is introduced to assess how well the logical explanations reproduce the model’s behavior on real graphs rather than on latent representations. \n\nOverall, the motivation is clear and the addressed problem appears real and relevant. However, the paper is occasionally difficult to follow, mainly because the pipeline uses several dense steps, sometimes similar (e.g. different decision trees for different purposes). The provided implementation also raises minor concerns: the released code explicitly skips the grounded part of the pipeline for all datasets except BBBP, Mutagenicity, and NCI1, and it appears not to run correctly for IMDB-BINARY.", "questions": "1. The released code explicitly skips the grounded part of the pipeline for all datasets excepts BBBP, Mutagenicity, and NCI1. Could the authors clarify whether this was intentional and whether the grounded evaluation can be extended to other datasets (e.g., IMDB-BINARY doesn’t seem to work)?\n2. The procedure is difficult to follow. Have the authors considered simplifying the exposition, for example through a schematic overview?\n3. An ablation study could help isolate which steps in the pipeline are most important. In addition, testing against more baselines would strengthen the empirical evidence.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper identifies a genuine limitation of current global explainability methods for GNNs: the lack of grounding of logical explanations in real graph instances. The proposed framework offers a systematic and sound solution. The proposed metric is reasonable. The presentation of the baseline results seems rigorous: tha appendix states that the authors of the original methods were consulted to verify the correctness of the reproduction.", "weaknesses": "The proposed procedure is quite convoluted, and the absence of ablation studies makes it difficult to understand which components of the pipeline are essential and which could be simplified. For similar reasons, the methododgical explanation is hard to follow: the paper requires several readings to fully grasp the role of each step (e.g., the multiple decision trees used for different purposes). The experimental comparison includes only two baselines.", "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": "oa75c4IEHl", "reviewer": "Reviewer_kSni", "summary": "This paper tackles post-hoc rule-based model-level GNN explainabiltiy, aiming to ground the extracted global rules to human understandable data-level. They propose LOGICXGNN, which constructs logical rules directly grounded in data, ensuring that explanations correspond to real subgraphs. It introduces a new metric, data-grounded fidelity (FidD), which measures how well explanations match the GNN’s outputs in the actual input space, not in an abstract one.", "questions": "n/a", "limitations": "", "rating": 4, "confidence": 4, "soundness": 1, "presentation": 1, "contribution": 3, "strengths": "1. Quantitative results are consistently strong. Strong empirical performance on fidelity, coverage, stability, validity and efficiency.\n2. Well motivated. The paper identifies a valid and underexplored problem. Clear identification of an overlooked issue in prior rule-based explainers. \n3. The framework is complete and reproducible.", "weaknesses": "1. **Missing clear discussion and comparison on an important baseline.** The paper briefly mentions GCNeuron (Xuanyuan et al., AAAI 2023) in the related work section, categorizing it as a “concept-based global explanation”. However, it does not clearly articulate the methodological differences or justify the absence of a direct comparison. Given that GCNeuron is also a rule-based, model-level GNN explainer that produces logical rules to characterize model behavior, a clearer discussion of methodological distinctions, or at least a brief justification for not comparing, would strengthen the completeness of the evaluation.\n2. **Overly domain-specific evaluation. Lack of validation on simple synthetic tasks.**\nThe paper claims to propose a general and scalable global rule-based GNN explainer, but almost all examples and visualizations are from molecular datasets (Mutagenicity, BBBP, NCI1). This makes the work look domain-specific rather than general. The authors did not include enough simple synthetic datasets where the ground-truth reasoning patterns are known. On such datasets, an effective rule-based method should ideally achieve near 100% data-grounded fidelity, clearly showing that it can capture the model’s true decision rules. Without this type of controlled experiment, it remains unclear whether the proposed rules genuinely reflect model reasoning or are just fitting chemical regularities in the data.\n3. **Excessive complexity of grounded rules without well-clarifications.** While the proposed orbit-based grounding mechanism improves formal precision, it significantly increases the structural and logical complexity of the resulting rules. The grounded rules involve multi-level orbit decomposition, nested logical conjunctions, and numerical thresholds, which make them difficult for non-expert users to interpret. Compared to prior rule-based explainers such as GLGExplainer and GraphTrail that generate concise and human-readable logic, the grounded rules here are overly abstract and cumbersome. This undermines one of the central goals of grounding in this paper, which was explicitly framed as aiming for \"human-understandable\" explanations.\n4. **Insufficient justification for the rule-based paradigm.** Although the paper emphasizes the importance of rule grounding, it does not convincingly demonstrate why a rule-based approach is preferable to other established global explanation paradigms, such as generation-based (XGNN, GNNInterpreter) or subgraph-based (TreeX) methods. There is no human study, no qualitative comparison of interpretability, and no synthetic benchmark explicitly designed to evaluate rule quality. As a result, the claimed advantage of rule-based grounding remains conceptually appealing but empirically unproven.\n5. **Questionable novelty of the proposed evaluation metric.** The proposed “Data-grounded Fidelity (Fid$^D$)” metric appears conceptually aligned with the instance-level fidelity evaluation already used in prior work such as TreeX, where global explanations are mapped back to instances to check whether they reproduce the original GNN’s predictions. The paper reframes this idea under a new term “data-grounded fidelity”, but this seems more like a terminological reframing than a fundamentally new metric design. Moreover, TreeX also provides motif-level global explanations evaluated on instances, making it a highly relevant baseline. However, the authors neither compare with TreeX nor acknowledge this conceptual overlap. This omission weakens the claimed novelty of Fid$^D$ and leaves the evaluation incomplete. \n6. **Limited technical novelty.** The proposed framework largely combines existing ideas: constructing logical rules from learned predicates (as in GLGExplainer, GCNeuron and GraphTrail), grounding them to data (as in motif-based explainers like TreeX and PAGE), and evaluating instance-level fidelity (similar to TreeX).", "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)