Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective
Authors: Steve Azzolin
SAGAR MALHOTRA
Andrea Passerini
Stefano Teso
Venue: ICML 2025 poster (2025)
Keywords: GNNs
Interpretability
Self-Explainable models
Formal Explainability
Self-Explainable GNNs
Primary area: deep_learning->graph_neural_networks
TL;DR: We formalize explanations extracted Self-Explainable GNNs, highlighting their links to existing definitions and their strengths and limitations. To address some of these limitations while preserving their benefits, we propose a simple model.

Abstract: Self-Explainable Graph Neural Networks (SE-GNNs) are popular explainable-by-design GNNs, but their explanations' properties and limitations are not well understood.
Our first contribution fills this gap by formalizing the explanations extracted by some popular SE-GNNs, referred to as Minimal Explanations (MEs), and comparing them to established notions of explanations, namely Prime Implicant (PI) and faithful explanations.
Our analysis reveals that MEs match PI explanations for a restricted but significant family of tasks. 
In general, however, they can be less informative than PI explanations and are surprisingly misaligned with widely accepted notions of faithfulness.
Although faithful and PI explanations are informative, they are intractable to find and we show that they can be prohibitively large.
Given these observations, a natural choice is to augment SE-GNNs with alternative modalities of explanations taking care of SE-GNNs’ limitations. To this end, we propose Dual-Channel GNNs that integrate a white-box rule extractor and a standard SE-GNN, adaptively combining both channels.
Our experiments show that even a simple instantiation of Dual-Channel GNNs can recover succinct rules and perform on par or better than widely used SE-GNNs.

Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective
Steve Azzolin 1
Sagar Malhotra 22
Andrea Passerini Stefano Teso
Abstract
discriminative subgraph of the input and classifier map- ping said subgraph onto a prediction. Since this subgraph, taken in isolation, is enough to infer the prediction, it plays the role of a local explanation thereof. Despite the popular- ity SE-GNNs (Miao et al., 2022a; Lin et al., 2020; Serra & Niepert, 2022: Zhang et al., 2022; Ragno et al., 2022; Dai & Wang, 2022), little is known about the properties and limitations of their explanations. Our work fills this gap.
Self-Explainable Graph Neural Networks (SE- GNNs) are popular explainable-by-despe GNNs, but their explanations' properties and limitations are not well understood. Our first contribution fills this gap by formalizing the explanations extracted by some popular SE- SE-GNNs GNNs, referred to as Mini- mal Explanations (MEs), and comparing them to established notions of explanations, namely Prime Implicant (PI) and faithful explanations. Our anal- ysis reveals that MEs match PI explanations for a restricted but significant family of tasks. In gen- eral, however, they can be less informative than PI explanations and are surprisingly misaligned with widely accepted notions of faithfulness. Although faithful and PI explanations are informative, they are intractable to find and we show that they can be prohibitively large. Given these observations, a natural choice is to augment SE-GNNs with al- ternative modalities of explanations taking care of SE-GNNs limitations. To this end, we propose Dual-Channel GNNs that integrate a white-box rule extractor and standard SE-GNN, adaptively combining both channels. Our experiments show that even a simple instantiation of Dual-Channel GNNs can recover succinct rules and perform on par or better than widely used SE-GNNs.
Focusing on graph classification. we introduce the notion of Minimal Explanations (MEs) as the minimal subgraphs of the input ensuring that the classifier outputs the target prediction. We then show that some popular SE-GNNs are implicitly optimized for generating MEs. We further com- pare MEs with two other families of formal explanations: Prime Implicant explanations' (PIs) and faithful explana- tions. Faithful explanations are subgraphs that are sufficient and necessary for justifying a prediction, i.c., they capture all and only those elements that cause the predicted label (Yuan et al., 2022; Tan et al., 2022; Agarwal et al., 2023; Azzolin et al., 2025). PIs, instead, are minimally sufficient explanations extensively studied in formal explainability of tabular and image data (Marques-Silva 2023; Darwiche & Hirth, 2023; Wang et al., 2021). They are also highly informative, e.g., for any propositional formula the set of PIs is enough to reconstruct the original formula (Ignatiev et al., 2015). Moreover, both PI and sufficient explanations are tightly linked to counterfactuals (Beckers, 2022) and adversarial robustness (Ignatiev al., 2019). An example of these familics' nuances is shown in Fig. 1.
1. Introduction
Our results show that MEs match PI explanations in the restricted but important family of motif- prediction tasks, where labels depend on the presence of topological motifs. Although in these tasks MEs inherit all benefits of PIs, in general they are neither faithful nor Pls.
Seff-xxxlainable GNNs (SE-GNNs) are Graph Neural Net- works (Scarselli et al., 2008; Wu et al., 2020b) designed to combine high performance and ante-hoc interpretability. In nutshell, a SE-GNN integrates two GNN modules: an explanation extractor responsible for identifying a class-
These observations motivate augmenting SE-GNNs with alternative explanation modalities to address their limita- tions. To this end, we introduce Dual-Channel GNNs (DC- GNNs), a novel family of SE-GNNs that aim to extend the perks of motif- based tasks to more general settings. DC- GNNs combine a SE-GNN and a non-relational white-box
'Equal contribution 'DISI. University of Trento, Trento, Italy "TU Wien, Wien, Austria. Correspondence to: Sagar Malhotra
Steve Azzolin ara.veezzziiimuiii... <sagar.malhotra Satiallhottttuiiina...... @c.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 20255 by the author(s).
Also known as sufficient reasons (Darwiche & Hirth, 2023).

---

Beyond Topological Self- Self-Explainable GNNS
R C G' contain all, less, or none of the features of the nodes (or edges) in G. We will use |G] indicate the size of the graph G. The size may be defined in terms of the number of nodes, edges, features, or their combination, and the precise semantics will be clear from the context.
Minimal Explanation
Pl Explanation
Faithful Explanation Explanation (SUF= = 1) (NEC 0)
Faithful
Jy B(a,8)
Self-explainable GNNs. SE-GNNs are designed to comple- ment the high performance of regular GNNs with ante-hoc interpretability. They pair an explanation extractor q map- ping the input G to a subgraph g(G) = R C G playing the role of local explanation, and classifier f using R to infer prediction:
Vrr, v)
Figure 1: Examples of a Minimal, Pl, and faithful explana- tion (w.rt Proposition 5.3 and Proposition 5.4) for the predic- tions of the two classifiers Ex.y.E(x: y) and Vr, y) introduced in Section 2 on a triangle. Solid nodes and edges represent the explanation R, whilst dashed ones represent the complement C' = G R. At high level, MEs high- light the smallest label- pressrvvng subgraphs, PIs and faith- ful sufficient explanations encode the subgraph ensuring that no complement perturbation can change the prediction, while faithful necessary explanations highlight subgraphs that once removed bring a prediction change.
g g - f(a())
(I)
In practice, the explanation extractor outputs per-edge relevance scores Pau E IR, which are translated into an edge- induced subgraph R via thresholding (Yu et al., 2022) or top- k selection (Miao et al., 2022a; Chen et al., 2024). While we focus on per-edge relevance scores due to their widespread use, our results equally apply to per-node relevance scores.
Approaches for training SE-GNNs are designed to extract an interpretable subgraph that suffices to produce the target prediction, often formalized in terms of sparsity regular- ization (Sparsity) (Lin et al., 2020; Serra & Niepert, 2022) or the Information Bottleneck (IB) (Tishby et al., 2000). Since the exact IB is intractable and difficult to estimate (Kraskov et al., 2004; McAllester & Stratos, 2020), com- mon approaches devise bounds on the divergence between the relevance scores and an uninformative prior controlled by the parameter r E [0, 1] (Miao et al., 2022a;b). This work focuses on representative training objectives for both Sparsity- and IB-based SE-GNNs, indicated in Table 1.
predictor, adaptively employing one or both depending on the task. Intuitively, the non-relational channel handles non- topological aspects of the input, leaving the SE-GNN free to focus on topological motifs with MEs. This setup encour- ages the corresponding MEs to be more compact, all while avoiding the (generally exponential (Marques-Silva., 2023)) computational cost of extracting PIs explicitly. Empirical results on three synthetic and five real-world graph classifi- cation datasets highlight that DC-GNNs perform as well or better than SE-GNNs by adaptively employing one channel or both depending on the task.
Contributions. Summarizing, we:
Logical classifiers. To prove our theoretical results, will use basic concepts from First-Order Logic (FOL) as described in Barceló et al. (2020) and Grohe (2021), and use B(x, y) to denote an undirected edge between æ and y. A FOL boolean classifier is a FOL sentence & that labels an instance G positively if G - & and negatively otherwise. For ease of discussion, we fix two FOL classifiers that will be used to provide examples and intuition in the remainder of the paper: Erey. E(x, y) classifies a graph positively if it has an edge, while E(x, y) when it has no isolated nodes. Note that both can be expressed by a GNN, as they are in the logical fragment C2 (see Theorem IX.3 in Grohe (2021)). We say that two classifiers are distinct if there exists at least one instance where their predictions differ. Although most of our results discuss general graph classifiers, they equally apply to the specific case of GNNs.
Formally characterize the class of explanations that popular family of SE-GNNs optimizes for, namely MEs.
Show that MEs share key properties of PI and faithful explanations for motif-based prediction tasks.
Propose Dual-Channel GNNs and compare them em- pirically to representative SE-GNNs, highlighting their promise in terms of explanation size and performance.
2. Preliminaries
We will use g to represent graph classifier, usually rep- resenting GNN. Given graph G = (V, E), we will use G() to denote g's is predicted label on G. Addition- ally, graphs can be annotated with edge or node features. Throughout, we will use the notation R C G to denote that R is a subgraph of G and R C G to denote that R may be a subgraph or G itself. Note that we assume that a subgraph
3. What are SE-GNN Explanations?
Despite being tailored for explainability, SE-GNNs lack a precise description of the properties of the explanations they
2

---

Beyond Topological Self-Explainable GNNs
MODEL
GROUP
LEARNING OBJECTIVE
GISST (Lin et al., 2020), SMGNN (ours)
Sparsity
L+ [8]
((.o)EE Puu + (8) DiwereD Puo log(puu) + (1 Puo) log(1 Puv)
GSAT, LRI (Miao et al., 2022a:b).
IB
L+ Eiu,oreD Puo log( (ee) - (1 - Puw) log( P (
GMT (Chen ul., 2024)
Table I: Training objectives of popular SE-GNNs. L is the cross-entropy loss between model predictions of f(((G)) and the target variable Y. For GISST and SMGNN, the second term in the objective pushes the relevance score Puv of each edge to be sparse, while the last term pushes scores align either 0 or 1 via an entropy loss (Lin et al., 2020). For GSAT, LRI, and GMT instead, the second term is the IB regularization pushing relevance scores close to the uninformative value controlled by the Theorem 3.2 shows that all of them optimize for generating Minimal Explanations (Definition 3.1).
(Miao et al., 2022a). A1 and X are the relative strengths of each regularization term.
extract. In this section, we present a formal characterization (in Definition 3.1) of explanations extracted by SE-GNNs: called Minimal Explanations (MEs). In Theorem 3.2 we show that, for an SE-GNN with perfect predictive accu- racy and a hard explanation extractor, the loss functions in Table 1 are minimal iff the explanation R is a ME.
for both cases, the risk is minimized when (G) is the small- est subgraph that preserves the label, i.e. an ME.
Proofs relevant to the discussion are reported in the main text, while the others are available in Appendix A. Having established link between SE-GNNs and MEs, we proceed to analyze the formal properties of MEs, starting from the following remark encoding broad notion of informative explanation.
Definition& 3.1 (Minimal Explanations). Let be a graph classifier and G be an instance with predicted label g(G), then R is a Minimal Explanation for (G) if:
Remark 3.3. A simple desideratum for any type of explana- tion is that it gives information about the classifier beyond the predicted label. A weak formulation of this desideratum is that explanations for two distinct classifiers should differ on at least one instance where they predict the same label'
1. RCG
2. g(G)= = gR)
3. There does not exist an explanation R' C G such that
| < [R] and g(G) = g((t'.
Note that Remark 3.3 can be seen as the dual of the Im- plementation Invariance Axiom (Sundararajan et al., 2017). The following theorem, however, shows that MEs can fail to satisfy this desideratum for certain prediction tasks, indi- cating potential limits in the informativeness of MEs.
Minimal Explanations are not unique, and we use GE) to denote the set of all MES for (G))
Since our goal is to formally analyze explanations extracted by SE-GNNs, we make idealized assumptions about the classifier f. Hence, we assume that the SE-GNN is expres- sive enough and attains perfect predictive accuracy. i.e., it always returns the correct label for G. We also assume that it learns a hard explanation extractor, i.c., outputs scores saturated to {0, } (Yu et al., 2020). Under these assumptions, we show that SE-GNNs in Table 1 optimize for generating MFs.
Theorem 3.4. There exist two distinct classifiers and g' such that for any G where g(G) = g'G we have that
ME(g(G)) = ME(g'(G))
(2)
Proof. Let and gو be boolean graph classifiers given by FOL formulas Rr F(x,, u) and y' V> F(r, v) respectively. Let G be any positive instance for both and g', and let E and V be the set of edges and nodes in G, respectively. For any e E E, we have that e is a Minimal Explanation for both g(G) and g' gG) (e.g. see Fig. 1). Hence, ME(g(G)) = ME (G)) E. Similarly, if G is negative instance for both g and g', we have that Minimal Explanation is subgraph consisting of any single node from G. and ME(g(G)) = ME(g
Theorem 3.2. Let g be SE-GNN with ground truth classifier (i.e., f(G) always returns the true label for G), hard explanation extractor q, and perfect predictive accuracy. Then, g achieves minimal true risk (as indicated in Table 1) if and only if for any instance G. g(G) provides Minimal Explanations for the predicted label g(G).
V.
Proof Sketch. For a hard explanation extractor g, the risk terms Table reduce to L(((g(G)) Y) A \ and C(f(g(G), +))+)1g(G)) lo (1). ). Since g attains per-
Intuitively, this result indicates that there exist two distinct graph classifiers for which MEs are the same for any input.
fect predictive accuracy, (()()(G)), Y) is minimal. Hence,
"To avoid this desideratum being vacuously satisfied, we as- sume that there exists at least one instance where the two classifiers predict the same label.
FFor (B-dased losses in Table 1 scores saturate to (r; 1}.
3

---

Beyond Topological Self- Eelf-Explainable GNNS
Hence, inspecting explanations alone makes it impossible to tell the two apart, meaning that MEs can fail be infor- mative wrt Remark 3.3.
Like MEs, Pls are not unique, and we use Pl(g(G)) to denote the set of all Pls for g()).
PIs feature several nice properties, in that they are guar- anteed to be the minimal explanations that are provably sufficient for the prediction (Shih et al., 2018; Beckers, 2022; Darwiche & Hirth, 2023). To illustrate the differ- ence between MEs and Pls, we provide an example for two different classifiers in Fig. 1. Note that for the classifier Mr y), MEs match Pls. This observation indeed generalizes all existentially quantified positive FOL for- mulas, shown next.
Theorem 3.4 highlights additional insights worth discussing. Consider again the classifier g' = Vr [x; y), and let G be a negative instance for g' composed of three nodes {ui, u2, us}. only two of which are connected by the edge (ui, u2) E E. In this case, user may expect see the isolated node uy an explanation. However, any subgraph consisting of a single isolated node from the set (u1, W2, uz) } is a valid ME. This highlights that as MEs focus only on the subgraphs allowing the model to reproduce the same prediction, they may lead to counter- counter-intuitive explanations.
4.1. MES Match PI for Positive Existential Classifiers
Furthermore, Theorem 3.4 implies that
We now show that our previous observation that MBs equal PIs for Ex,..E(a, y) generalizes to all positive existential tasks. This reinforces the use of SE-GNNs in various practi- cal applications and our proposed method, as discussed at the end of this section and in Section 6.
UGe ME( = Uceate (E)
(3)
where 1261 is the set of all instances G such that g(G) g'(G) = y, with g = Ez (2x, y) and g' is as above. Intu- itively, Eq. (3) shows that the insight of Theorem 3.4 applies even when aggregating MEs across all instances where the two classifiers yield the same prediction. Hence, there are classifiers where model-level explanations built by aggre- gating over local explanations (Setzu et al., 2021; Azzolin et al., 2022) may also not be informative w.r.t. Remark 3.3,
Theorem 4.2. Given a classifier g expressible as purely existentially quantifed positive first-order logic formula and a positive instance G of any size, then a Minimal Explana- tion for g(G) is also a Prime Implicant explanation for g(G).
Proof sketch. A purely existentially quantified positive FOL. formula g is of the form =.,,--.; (fr,.- -.g)), where Tb is quantifier-free and does not contain any negation. For a positive instance G. a ME is the smallest subgraph R induced by nodes in a tuple ā = (a1..... ax), such that (a) holds. Now, any supergraph of R necessarily contains a and hence witnesses 3æ1, 3x D(5 ..... ......,,,,,,,,) while any smaller subgraph violates ........ Arx. ((1),....... ax)), as ā is minimal by construction. Hence, R is a PI.
In the next section, we investigate widely accepted for- mal notion of explanations, namely Prime Implicant ex- planations (Pis). We analyze the informativeness of MEs compared to PIs and characterize when they match.
4. Minimal and Prime Implicant Explanations
Having established the link between SE-GNNs and MEs in Section 3, in this section, we provide formal comparative analysis between MEs and Pis for graph classifiers. While PIs are extensively studied for tabular and image-like data (Marques-Siie Silla et al., 2020; Marques-Sile Silva, 2023), little investigation has been carried out for graphs. Our analysis shows that MEs match PIs for large class of tasks those based the recognition of motifs- but they do not align in general. We also show that PIs can be more informative than MEs w.n.t the desideratum in Remark 3.3. Let us start by defining PIs for graph classifiers.
Note that tasks based on the recognition of a topological motif (like the existence of a star) can indeed be cast as ex- istentially quantified positive" formulas (Ezyzw. E(z, v) A (a,,, =) A E(x, w)) A * * * w), qualifying MEs as ideal targets for those tasks. Motif-based tasks are in- deed useful in a large class of practically relevant scenarios (Sushko et al., 2012; Jin et al., 2020; Chen et al., 2022; Wong et al., 2024), and have been a central assumption in many works on GNN explainability (Ying et al., 2019; Miao et al., 2022a; Wu et al., 2022). Theorem 4.2 theoretically supports using SE-GNNs for these tasks, and shows they optimize for minimally sufficient explanations (Pls). However, global properties such as long-range dependencies (Gravina et al., 2022) or classifiers like VzžyE((, y). cannot be expressed by purely existential statements. In such scenarios, PIs can be more informative than MEs, as we show next.
Definition 4.1 (PI explanation). Let be classifier and G be an instance with predicted label g(G), then I is a Prime Implicant explanation for gGG) if:
1. RCG.
2. For all R', such that R C R' C G, we have that
g(G) = g())
'Note that the positive fragment of FOL admits inequalities like (ar # y) as positive atoms (Kuperberg, 2023).
3. No other R' c R satisfies both (1) and (2).
4

---

Beyond Topological Self- Belf-Explainable GNNs
4.2. MES are Not More Informative than Pls
(Agarwal al., 2024). This section reviews a general notion of faithfulness (Azzolin et al., 2025) in Definition 5.1 and shows that faithfulness, MEs (Section 3), and PIs (Section 4) can overlap in some restricted cases but are generally misaligned.
Although Section 4.1 shows that MEs match Pls for positive existential tasks, real-world properties like counting cannot be expressed by cxistential formulas. Here, we show that be- yond positive existential tasks, MEs can be less informative than Pis (Remark 3.3).
Intuitively, faithfulness metrics assess how much the pre- diction changes when perturbing either the complement referred as sufficiency of the explanation - or the expla- nation itself referred to as necessity of the explanation. Perturbations are sampled from distribution of allowed modifications, which typically include edge and node re- movals. Then, an explanation is said to be faithful when it is both sufficient and necessary.
Let g be a classifier and y given label. Let sig" be the set of all the finite graphs (potentially with given bounded size) with predicted label y. Then,
Proposition 4.3.
USEN ME( S Ucenno Pl(((G))
(4)
This result shows that when considering the union of all finite graphs, Pls subsume MFs. Hence, if two classifiers share all PIs then they necessarily share all MEs as well, meaning that MEs do not provide more information about the underlying classifier than Pls. Conversely, we show that there exist cases where Pls provide strictly more information about the underlying classifier than MES.
Definition 5.1 (Faithfulness). Let R C G be an explana- tion for g(G) and C G R its complement. Let pa be distribution over perturbations to C, and pC be dis- tribution over perturbations to R. Also, let AGG 1 [g((G) + g(G')} indicate a change in the predicted label. Then, Suf and Nec compute respectively the degree of suf- ficiency and degree of necessity of an explanation R for a decision g(G) as:
Theorem 4.4. There exist two distinct classifiers g and g' and a label y such that:
Suf (R) = exp( Seap(-Ee'-pa Ep' (GG G')),
(7)
Nec (R) = -
e exp(- ('))
(8)
1. For all graphs G S.t. g(G) = gG) = y, we have
The degree of faithfulness Faith R) is then the harmonic mean of Suf and Nec.
ME(g(G)) MF)gg(G))-
(5)
The (negated) exponential normalization ensures that Suf (resp. Nec) increases for more sufficient (resp. necessary) explanations. Note that both Suf and Nec need to be non- zero for a Faith score above zero. According to this def- inition, the degree of necessity will be high when many perturbations of R lead to prediction change and is thus 1 when all of them do so. Suf analogous.
2. There exists at least one graph G with g(G*)
(C") = y such that
PI(g(G")) * PI'))
(6)
Theorem 4.4 shows that PIs can overcome MEs' limits in certain tasks. For example, Theorem 3.4's classifiers yield identical MES but differing PIs (see Fig. 1).
As the next theorem shows, MEs can surprisingly fail in being faithful even for trivial tasks. Theorem 5.2. There exist tasks where Minimal Explana- tions achieve a zero degree of faithfulnes.
To summarize, Theorem 4.2 justifies SE-GNNs' perfor- mance on many benchmarks, as their explanations can in- herit desirable properties of PIs. However, Theorem 3.4 and Theorem 4.4 show that MEs may not be informative for certain tasks, motivating extension of SE--NNs that preserves their performance on positive existential tasks but adaptively aids them in other tasks. We will exploit this observation for our proposed method in Section 6.
Proof. Let = Br..B.B.EEa y) and G be a positive instance
with more than one edge. Then, a Minimal Explanation R
consisting of single edge (see Fig. 1) achieves a Nec(R) RR) value of zero, as any perturbations to R will leave G' R unchanged. Hence, 9 remains satisfied, meaning that Nec = 0 and thus Faith(R) = 0.
5. Minimal Explanations can be Unfaithful
A widespread approach to estimating the trustworthiness of explanation is faithfulness (Yuan et al., 2022; Amara et al., 2022; Agarwal et al., 2023; Longa et al., 2024), which consists in checking whether the explanation contains all and only the elements responsible for the prediction. Clearly, unfaithful explanations fail to convey actionable informa- tion about what the model doing to build its predictions
Note that Er3y.E(x,)) achieves non-zero Nec(R) iff R contains every edge, whereas Suf R)) = 1 is guaranteed by the presence of single edge. These observations indeed generalize, as shown next.
Proposition 5.3, An explanation R C G for g(G) has a maximal Suf (R) score if and only if there exists a PI explanation M C R for g()).
5

---

Beyond Topological Self- Beff-Explainable GNNs
Proposition 5.4. An explanation R C G for g(G) can have a non-zero Nec( R) score only if intersects every Pl explanation for g(G).
jointly train the two channels and let DC-GNNs adaptively learn how exploit them.
Definition 6.1. (DC-GNN) Let 91 : H [o, 1 be a SE-
GNN, 92 : G + [0, 1 an interpretable model of choice, and aggr [0, _| + Y an aggregation function. A
Note that Proposition 5.3 (along with Theorem 4.2) show that MEs are indeed maximally sufficient for existentially quantified positive FOL formulas. However, this might not be enough to ensure non-zero Faith score, shown in Proposition 5.4. In general, MEs highlight minimal daas-discriminative subgraph, whereas faithful explanations highlight all possible causes for the prediction, and the two notions are fundamentally misaligned.
DC-GNN is defined as:
g(G) aggr (g) (G). 92 (G)).
(9)
While the second channel g2 can be any interpretable model of choice, we will experimentally show that even a simple sparse linear model can bring advantages over a standard SE-GNN, leaving the investigation of a more complex ar- chitecture to future work. Therefore, in practice, we will experiment with
6. Beyond (Purely) Topological SE-GNNs
Our analysis highlights that explanations extracted by SE- GNNs can be, in general, both ambiguous (Theorem 3.4) and unfaithful (Theorem 5.2), potentially limiting their use- fulness for debugging (Teso et al., 2023; Bhattacharjee & von Luxburg. 2024; Fontanesi et al., 2024), scientific discov- ery (Wong et al., 2024), and Out-of-Distribttion (OOD) gen- eralization (Chen et al., 2022; Gui et al., 2023). Nonetheless, we also showed that for a specific class of tasks, preciscly those based on the presence of motifs, MEs are actually an optimal target, in that they match PIs and are the minimal explanations that are also provably sufficient (Theorem 4.2 and Proposition 5.3).
92 ( o Enegg
(10)
where Tu E Rd is the node feature vector of u, W E 22d the weights of the linear model, and a is an element-wise sigmoid activation function. Also, we will fix n1 = n2 equal to the number of classes of Y. In the experiments, we will promote a sparse W via weight decay.
A key component of DC-GNNs is the aggr function joining the two channels. To preserve the interpretability of the overall model. aggr should act as a gateway for making the final predictions based on a simple combination of the two channels. To achieve this while ensuring differentiability, we considered an extension of Logic Explained Networks (LENs) (Barbiero et al., 2022), described below.
As PI and faithful explanations can generally be more infor- mative than MEs (Proposition 4.3 and Theorem 4.4), one might consider devising SE-GNNs that always optimize for them. We argue, however, that aiming for PI or faithful explanations can be suboptimal, as they can be large and complex in the general case. For example, a PI explanation for a positive instance of Vely.E Exx, y) is an edge cover (Weisstein, 2025). which grows with the size of the instance. Similarly, the explanation with an optimal faithfulness score for E(x, v) is the whole graph. Furthermore, finding and checking such explanations is inherently intractable, as both involve checking the model's output on all possible subgraphs (Yuan et al., 2021). These observations embody the widely observed phenomenon that explanations can get as complex as the model itself (Rudin, 2019).
Implementing aggr. LENs are small Multi-layer Percep- trons (MIP) taking as input vector of activations in [0, 1] (Barbiero et al., 2022). The first layer of the MLP is regu- larized to identify the most relevant inputs while penalizing irrelevant ones via an attention mechanism. To promote the network to achieve discrete activations scores without resorting to high-variance reparametrization tricks (Azzolin et al., 2022: Giannini et al., 2024), we propose augmenting LENs with a progressive temperature annealing of the input vector. We validate the effectiveness of this extension in preserving the semantics of each channel, together with a comparison to other baselines, in Appendix C.4.
6.1. Dual-Channel GNNS
7. Empirical Analysis
This motivates us to investigate Dual-Channel GNNs (DC- GNNs), a new family of SE-GNNs aiming to preserve the perks of MES for bosif-based tasks while freeing them from learning non-motif-basee based patterns, which would be inef- ficiently represented as a subgraph. To achieve this, DC- GNNs pair an SE-GNN-basce topological channel - named Topo- with an interpretable channel- - named Rule- pro- viding succinct non-lopol rules. To achieve optimal separation of concerns while striving for simplicity, we
We empirically address the following research questions:
Q1 Can DC-GNNs match or surpass plain SE-GNNs?
Q2 Can DC-GNNs adaptively select the best channel for each task?
Q3 Can DC-GNNs extract more focused explanations?
6

---

Beyond Topological Self- Sell-xxxlai GNNs
Input Graph
SE SE-GNN
DC.GNN w/ linear channel
98
rule (#red 2 2)
Illustration of our Dual-Channel architecture for a positive instance of TopoFeature, where positive instances contain cycle and at least two red nodes. Numbers indicate edge relevance scores. SE-GNNs may fail to highlight precisely the elements relevant to the prediction, as the task involves non-topological patterns. DC-GNNs, instead, provide more focused topological explanations by offloading part of the prediction to interpretable rules (ef. Fig. 7 and Fig. 10).
Figure 2:
Full details about the empirical analysis are in Appendix B. Our code is publicly available on GitHub
testing topology-based explainable models (Azzolin et al., 2025), and that graph-based architectures can overfit the topology to their detriment (Bechler-Speicher et al., 2023). We present further experiments in Appendix C.2 and Ap- pendix C.3, where we show the sensitivity of DC-GNNs to different hyper-parameter choices, and that DC-GNNs are also applicable to SE-GNNs beyond Table 1, respectively.
Architectures. We test two representative SE-GNNs back- bones from Table 1, namely GISST (Lin et al., 2020) and GSAT (Miao et al., 2022a), showing how adding an inter- pretable side channel can enhance them. We also propose a new SE-GNN named SMGNN, which replaces the graph- agnostic GTSST's explanation extractor with that of GSAT. More details are available in Appendix B.
We further analyze their generalization abilities by re- porting their performance on OOD splits in Table 4. Surprisingly DC-GNNs significantly outperformed base- lines on OOD, of GOODMot f but underperformed on OOD2, likely due to the intrinsic instability of OOD per- formance in models trained without OOD regularization (Chen et al., 2022; Gui et al., 2023). For RedBlueNodes and TopoFeature Fure instead, DC-GNNs exhibit substantial gains in seven cases out of eight, achieving perfect extrapo- lation on RedRl LedRles
Datasets. We consider three synthetic and five real- world graph classification tasks. Synthetic datasets include GOCDMotif f (Gui et al., 2022), and two novel datasets. MedBlueNodes contains random graphs where each node is either red or blue, and the task is to predict which color is more frequent. Similarly, TopoFeat ure contains random graphs where each node either red or uncolored, and the task is to predict whether the graph contains at least two red nodes and cycle, which is randomly attached to the base graph. Both datasets contain two OOD splits where the number of total nodes is increased or the distribution of the base graph is changed. For GOODMoti$ if we will use the original OOD splits (Gui et al., 2022). Real-world datasets include MUTAG (Debnath et al., 1991), BBBP (Morris et al., 2020), MNIST75sp (Knyazev et al., 2019), AIDS (Riesen & Bunke, 2008), and Graph-SSTT (Yuan et al., 2022).
A2: DC-GNNs can dependably select the appropriate channel(s) for the task. Results in Table 2 clearly show that both DC-GNNs correctly identify the appropriate channel(s) for all tasks. In particular, they focus on the interpretable model for RedB 1 ueNoees as the label can be predicted via a simple comparison of node features. For GOODMot i f, they rely on the underlying SE-GNN only, as the label de- pends on a topological motif. For TopoFeature, instead, they combine both channels as the task can be decomposed into motif-based sub-task and comparison of node fea- tures, as expected from the dataset design. While the chan- nel importance scores predicted by the aggr are continuous, we report a discretized version indicating only the channel(s) achieving a non-negligible (2 0.1) score to avoid clutter. Raw scores are reported in Table 8.
A1: DC-GNNs performs on par better than plain SE- GNNs. We list in Table 2 the results for synthetic datasets and in Table 3 those for real-world benchmarks. In the for- mer, DC-GNNs always match or surpass the performance of plain SE-GNNs, and similarly, in the latter DC-GNNs per- form competitively with SE-GNNs baselines, and in some cases can even surpass them all while keeping a comparable running time SE-GNNs as shown in Appendix C. For example, DC-GNNs consistently surpass the baseline on AIDS and Graph-SST2 by relying on the non non-relational interpretable model. These results are in line with previous literature highlighting that some tasks can be unsuitable for
To measure the dependability of the channel selection mech- anism of DC-GNNs, we perform an ablation study by setting to zero both channels independently. We report the resulting accuracy in the last two columns for every dataset in Table 2. Results show that when the model focuses on just a single channel, removing the other does not affect performance. Conversely, when the model finds it useful to mix informa- tion from both channels, removing either of them prevents
'tttps: //gi thub. steveazzor in/ beyond tepo--ttpp-ooee -ep--segno-sssssss
7

---

Beyond Topological Self-Explainable GNNS
Table 2: DC-GNNs can reliably select the most appropriate channel based on the task. The table shows the test accuracy, the selected channel, and the test accuracy when removing one of the two channels. GISST is excluded from this analysis as it cannot extract meaningful explanations for TopoFeatune ture and GOODMot.1..
Model
RedBess
TopoFeature
GOODMotåf
Acc
Channel
Ace w/o Topo
Acc w/o Rule
Acc
Channel
Acc w/o Topo
Acc w/o Rule
Acc
Channel
Acc w/ Topo
Acc w/o Rule
GTN
99 m:
96 o0
93 0:
GSAT
99 0:
99 01
93 6:00
DC-GSAT
100 + 00
Rule
100 0
50 02
100 + co
Both
50 + co
60 20
93 0:
Topo
34 01
93 +
SMGNN
99 2:00
95 +:00
93 1:
DC-5MGNN
100 + 00
Rule
+ 01
50 02
100 + 00
Both
50 + 00
50 0000
93 0:00
Topo
34 0:
93 0000
Table DC-GNNs performs on par or better than a plain SE-GNN. The table shows the test accuracy and the selected channel for real-world experiments. Channel relevance with "*" means that DC-GNNs select the indicated channel in nine seeds over ten: For AIDS, that single seed uses the topological channel, as it can easily fit the task without incurring performance loss; For BBBP, instead, the DC-GNN tries to use both channels but incurs performance loss. "Mix" instead indicates that different seeds rely on different channels without incurring performance loss.
Model
AIDS Channel
MUTAG
BBBP Channel
Graph-SST2 Channel
MNIST75ep
F1
Acc
Channel
AUC
Acc
Acc
Channel
GIN
96 02
0:
68 a
88 0
GISST
97 0:
78 12
66 0
85 01
91 01
DC-GISST
99 4:
Mix
79 +
Topo
65 0z
Topo
87 02
Mix
91 +
Topo
GSAT
97 0:
79 1
66 m
86 02
94 ::00
DC-GSAT
99 1:00
Rule
79 1:00 02
Topo
65 m
Topo
87 02
Rule
94 1 02
Topo
SMGNN
79
66
86
92
D0-SMGNN
=:
Rule*
80 02
Topo
05
Topo
87 01
Rule
m
Topo
Table 4: DC-GNNs can generalize better to OOD than plain SE-GNN. GISST is excluded from this analysis as it cannot extract meaningful explanations for I TopoFee eature and GOODMot f. Numbers indicate OOD accuracy.
Table 2), confirms that the two channels are cooperating as expected: the interpretable model fires when least two red nodes are present, and the SE-GNN is left to recognize when the motif is present, achieving more focused and com- pact explanations as depicted in Fig. 2. The alignment of those formulas to the ground truth annotation process is also reflected in better extrapolation performance, as shown in Table 4. We further discuss in Appendix C.5 an additional experiment on AIDS where we match the result of Pluska et al. (2024), showing that a GNN can achieve perfect score by learning a simple rule the number of nodes. Those results highlight that better and more intuitive expla- nations can be obtained without relying on subgraph of the input. We further provide a quantitative (Appendix C.6) and qualitative (Appendix C.7) analysis showing how DC-GNN can yield explanations that better reflect what the underlying SE-G ENN using for predictions.
Model
RedBlueNodes
TopoFeature
Motif
0OD;
0OD;
0OD;
0OD,
OOD;
OOD₂
GTN
94 mm
87 m
61 1:0
61 1:
63 13
64 0:
GSAT
98 ot
98 0l
81 0:08
87 +:
67 1:
57 0:
DC-GSAT
mb
100 0
1:13
1:
72 11
49 10
SMGNN
97 1:
85 m
75 1:01
65 1:05
62 os
DC-SMGNN
99 +1
100 0:
93 0:06
98 4:01
82 0:03
43 0:04
the model from making the correct prediction, as expected.
A3: DC-GNNs can uncover high-quality rules and MEs. When the linear model 92 is sparse, it is possible to interpret the weights as inequality rules enabling a full understanding of the predictions, ef. Appendix B.3. In fact, by focusing on model weights with nog-neglig magnitude, we can extract the expected ground truth rule for RedB 1 lueNodes, whilst subgraph-basd based explanations fail to convey such simple rule as shown in Appendix C.7. At the same time, for TopoFeature the interpretable model fires when the number of red nodes is at least two. This result, together with the fact that the DC-GNN is using both channels (see
8. Related Work
Explaining GNNs SE-GNNs are a physiological response to the inherent limitations of post-hoc GNN explainers (Longa et al., 2024; Li et al., 2024). SE-GNNs usually rely on regularization terms and architectural biases- - such as attention (Miao al., 2022a;b; Lin et al., 2020; Serra &
8

---

Beyond Topological Self-Explainable GNNs
Niepert, 2022; Wu al., 2022: Chen et al., 2024), proto-
rules, or their combination. We empirically validate DC- GNNs, confirming their promise.
types (Zhang al., 2022; Ragno al., 2022; Dai & Wang. 2021; 2022), or other techniques (Yu et al., 2020; 2022;
Limitations: Our theoretical analysis is focused on Sparsity- and IB- SE-GNNs, which are popular choices due to their effectiveness and ease of training. Alternative formu- lations optimize explanations for different objectives than minimality (Wu et al., 2022; Deng & Shen, 2024), and more work needed to provide unified formalization of this broader class of subgraph-basee explanations. Nonetheless, we expect our theoretical findings to also hold for many post-hoc explainers, as they also optimize for the minimal subgraph explaining the prediction (Ying et al., 2019; Luo et al., 2020). Furthermore, despite showing that DC-GNNs with a simple linear model have several benefits, we believe that more advanced interpretable channels should be investi- gated. On this line, our baseline serve as a yardstick for future developments of DC-GNNs.
Giunchiglia et al., 2022; Spinelli et al., 2023; Ferrini et al., 2024) - to encourage the explanation to be human inter- pretable. Our work aims at understanding the formal proper- ties of their explanations, which have so far been neglected.
Beyond subgraph explanations. Pluska et al. (2024) and Köhler & Heindorf (2024) proposed to distill trained GNN into an interpretable logic classifier. Their approach is how- ever limited to post-hoc settings, and the extracted expla- nations are numan-understandabhe only for simple datasets. Nonetheless, this represents a promising future direction for integrating a logic-hased rule extractor as a side channel in our DC-GNNs framework. Müller et al. (2023) and Bechler- Speicher et al. (2024) introduced two novel interpretable-by- design GNNs that avoid extracting a subgraph explanation altogether, by distilling the GNN into Decision Tree, or by modeling each feature independently via learnable shape functions, respectively. However, we claim that subgraph- based explanations are desirable for existential motif- based tasks, and thus, we strike for a middle ground between subgraph and non-subgraph-baased explanations.
Impact Statement
Our analysis highlights the intrinsic limitations of expla- nations produced by a wide class of explainable- bee-igg GNNs, and in this sense serves as a warning for stakehold- ers from blindly trusting explanations produced by these models.
Formal explainability. While GNN explanations are com- monly evaluated in terms of faithfulness (Agarwal et al., 2023; Christiansen et al., 2023; Azzolin et al., 2025), for- mal explainability has predominantly been studied for non- relational data, where it primarily focuses on PI explanations (Marques-Silvaa 2023; Darwiche & Hirth, 2023; Wang et al., 2021). Important properties of Pl explanations include suffi- ciency, minimality, and their connection to counterfactuals (Marques-See Silva & Ignatiev, 2022). Simultaneously, PI expla- nations can be exponentially many (but can be summarized (Yu et al., 2023) for understanding) and are intractable to find and enumerate for general classifiers (Marques-Sill Silla, 2023). Our work the first to systematically investigate for- mal explainability for GNNs and elucidate the link between PI explanations and SE-GNNs.
A Acknowledgments
Funded by the European Union Views and opinions ex- pressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the Euro- pean Health and Digital Executive Agency (HaDEA). Nei- ther the European Union nor the granting authority can be held responsible for them. Grant Agreement no. 101 120763 TANGO. SM acknowledges the support of FWF and ANR project NanOX-MI. (6728).
The authors are grateful to Manfred Jaeger for useful discus- sions and feedback on earlier version of this manuscript.
9. Conclusion and Limitations
References
We have formally characterized the explanations given by sparsity- and Information Bottleneck- based Self- Explainable Graph Neural Networks (SE-GNNs) as Mini- mal Explanations (MEs). We identified and analyzed MEs' relation to established notions of explanations, like Prime Implicant (PI) and faithful explanations. Our analysis re- vealed that MES match PIs and achieve maximal sufficiency score for motif- tasks. However, in general MEs can be uninformative, whereas faithful and PI explanations can be large and intractable to find. Motivated by this, we in- troduced
Agarwal, C., Queen, O.,, Lakkaraju, H.,, and Zitnik, M. Eval- uating explainability for graph neural networks. Scientific Data, 10(1):144, 2023.
Agarwal, C., Tanneru, S. H., and Lakkaraju, H. Faithfulness vs. plausibility: On the (un)reliability of explanations from large language models, 2024.
Amara, K., Ying, Z., Zhang. Z., Han, Z., Zhao, Y., Shan, Y., Brandes, U., Schemm, S., and Zhang, C. Graphframex: Towards systematic evaluation of explainability methods for graph neural networks. In Learning on Graphs Con- ference, pp. 44-1. PMLR, 2022.
GNNs (DC-GNNss, new class of SE-GNNs that adaptively provide either MEs, interpretable

---

Beyond Topological Self- Eelf--xplainable GNNs
Azzolin, S., Longa, A., Barbiero, P., Lio, P., and Passerini, A. Global explainability of gnns via logic combination of learned concepts. In The Eleventh International Con- ference on Learning Representations, 2022.
Dai, E. and Wang, S. Towards prototype-based self- explainable graph neural network. arXiv preprint arXiv:2210.01974, 2022.
Darwiche, A. and Hirth, A. On the (complete) reasons behind decisions. Journal of Logic, Language and Infor- mation, 32(1):63-88, 2023.
Azzolin, S., Longa, A., Teso, S., and Passerini, A. Re- considering faithfulness in regular, self self--xplainable and domain invariant GNNs. The Thirteenth International Conference on Learning Representations, 2025.
Debnath, A. K., Lopez de Compadre, R. L.., Debnath, G., Shusterman, A. J., and Hansch, C. Structure Structure-activit rela- tionship of mutagenic aromatic and heteroaromatic nitro compounds. correlation with molecular orbital energies and hydrophobicity. Journal of medicinal chemistry, 34 (2)786-7977, 1991.
Barabási, A.-L., and Albert, R. Emergence of scaling in random networks. science, 286(5439) 1999.
Barbiero, P., Ciravegna, G., Giannini, F., Lió, P., Gori, M., and Melacci, S. Entropy-based logic explanations of neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pp. 6046-6054, 2022.
Deng, J. and Shen, Y. Self-interpretable graph learning with sufficient and necessary explanations. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 11749-11756, 2024.
Вarceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., and Silva, J.-P. The logical expressiveness of graph neural networks. In ICLR, 2020.
Erdos, P., Rényi, A., et al. On random graphs i. Publ. math. debrecen, 6(290-297):18, 1959.
Ferrini, F., Longa, A., Passerini, A., and Jaeger, M. A self-explainable heterogeneous gnn for relational deep learning. arXiv preprint arXiv:24/2.005)/ 2024.
Bechler-Speicher, M., Amos, I., Globerson, A. Graph neural networks use graphs when they shouldn't. arXiv preprint arXiv:2309.04332, 2023.
R., and
Fey, M. and Lenssen, J. E. Fast graph represetttto learning with pytorch geometric. arXiv preprint arKiv: 0903:v//90000222 02428, 2019.
Bechler-Speicher, M., Globerson, A., and Gilad-Bachradd Bachrach, R. The intelligible and effective graph neural additive net- work. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: www.inreeiwwwweeeeeeeeme net. www.:eerffooommmomo forum? (d==KY1sUUTAA //openreview
Fontanesi, M., Micheli, A., and Podda, M. Xai and bias of deep graph networks. ESANN, 2024.
Giannini, F., Fioravanti, S., Keskin, O., Lupidi, A., Magister, L. C., Lió, P., and Barbiero, P. Interpretable graph net- works formulate universal algebra conjectures. Advances in Neural Information Processing Systems, 36, 2024.
Beckers, S. Causal Explanations and XAI. In Conference on Causal Learning and Reasoning, pp. 90-109, 2022.
Bhattacharjee, R. and von Luxburg, U. Auditing local expla- nations is hard, arXiv preprint arXiv:2407. 11.40011322// 13281, 2024.
Giunchiglia, V., Shukla, C. V., Gonzalez, G., and Agarwal, C. Towards training GNNs using explanation directed message passing. In The First Learning on Graphs Con- ference, 2022. URL https: / oppprevveeeeeeeeeeeeeee nnt// forum? 1o bbNbawXD..
Chen, Y., Zhang, Y., Bian, Y., Yang. H., Kaili, M., Xie, B., Liu, T., Han, B., and Cheng, J. Learning causally invari- generalization
ant representations for on graphs. Advances in Neural Information Processing Systems, 35:22131-22148, 2022.
Gravina, A., Bacciu, D., and Galliechio, C. Anti-symmetric dgn: a stable architecture for deep graph networks. In The Eleventh International Conference on Learning Rep- resentations, 2022.
Chen, Y., Bian, Y., Han, B., and Cheng, J. How interpretable are interpretable graph neural networks? Forty-first International Conference on Machine Learning, 2024.
Grohe, M. The logic of graph neural networks. In 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), pp. 1-17, 2021.
Christiansen, M., Villadsen, L., Zhong, Z., Teso, S., and Mottin, D. How faithful are self-explainable gnns? arXiv preprint ar 230vv 15096, 2023.
Gui, S., Li, X., Wang, L.,, and Ji, S. GOOD: A graph out-of-distribution benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2022. URL https: openrevien ew. net/ forum? ? d-wh-g-2h22-- zs 2a_p-h.
Dai, E. and Wang, S. Towards self-expla graph neural network. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pp. 301-311, 2021.
10

---

Beyond Topological Self- Explaixplee GNNs
Gui, S., Liu, M., Li, X., Luo, Y., and Ji, S. Joint learn- ing of label and environment causal independence for graph out-of-distribttion generalization. arXiv preprint arXiv:2306.01 103, 2023.
Li, Z.., Geisler, S., Wang, Y., Günnemann, S., and van Leeuwen, M. Explainable graph neural networks under fire, 2024. URL https: /arxiv..vvvv.////a org/ haag//ab//aa 2406. 06417.
Havasi, M., Parbhoo, S., and Doshi-Velez. F. Address- ing leakage in concept bottleneck models. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https::///// http//ppereeeeeeeeeeeeeeeeeeeeee wttpeeiiwwwwwwweeeeeee net/forumt id=tglniD_ft fn9.
Lin, C., Sun, G. J.J. Bulusu, K. C., Dry. J. R., and Hernandez, M. Graph neural networks including sparse interpretabil- ity. arXiv preprint 20Xi:2007.001110 2020.
Longa, A., Azzolin, S., Santin, G., Cencetti, G., Liò, P., Lepri, B., and Passerini, A. Explaining the explainers in graph neural networks: comparative study. ACM Computing Surveys, 2024.
Ignatiev, A., Previti, A., and Marques-Sivvas J. Sat-based formula simplification. In Theory and Applications of Satisfiability Testing SAT 2015, pp. 287-298. Springer International Publishing, 2015.
Luo, D., Cheng, W., Xu, D., Yu, W., Zong, B., Chen, H., and Zhang, X. Parameterized explainer for graph neural network. Advances in neural information processing systems, 33:19620-19990 19631, 2020.
Ignatiev, A., Narodytska, N., and Marques-Silvae J. On relating explanations and adversarial examples. NeurIPS, 2019.
Margeloiu, A., Ashman, M., Bhatt, U., Chen, Y., Jamnik, M., and Weller, A. concept bottleneck models learn intended? arXiv preprint arXiv:2105.0422 04289, 2021.
loffe. S. Batch normalization: Accelerating deep net- work training by reducing internal covariate shift. arXiv preprint arXiv:1502.03111 2015.
Marques-Silva, J. Logic-based explainability in machine learning. In Reasoning Web. Causality, Explanations and Declarative Knowledge: 18th International Summer School 2022, Berlin, Germany, September 27-30, 2022, Tutorial Lectures, pp. 2041 Springer, 2023.
Jang, E., Gu, S., and Poole, B. Categorical repa- rameterization with gumbel-softmax. arXiv preprint 1611.00 2016.
Marques-Silva, J. and Ignatiev, A. Delivering trustworthy ai through formal xai. In Proceedings of the AAAI Con- ference on Artificial Intelligence, volume 36, pp. 12342- 12350, 2022.
Jin, W., Barzilay, R., and Jaakkola, T. Multi-objective molecule generation using interpretable substructures. In International conference on machine learning, pp. 4849- 4859. PMLR, 2020.
Marques-Site -Silva, J., Gerspacher, T., Cooper, M. C., Ignatiev, A., and Narodytska, N. Explaining naive bayes and other linear classifiers with polynomial time and delay. In Pro- ceedings of the 34th International Conference on Neural Information Processing Systems, NIPS '20, 2020. ISBN 9781713829546.
Kingma, D. P. and Ba, J. Adam: A method for stochastic optimization. In International Conference on Learning Representations, 2015.
Klement, E. P., Mesiar, R., and Pap. E. Triangular norms, volume 8. Springer Science Business Media, 2013.
Martins, I. F., Teixeira, A. L., Pinheiro, L., and Falcao, A. O. A bayesian approach to in silico blood-brain barrier penetration modeling- Journal of chemical information and modeling, 1686) 2012.
Knyazev, B., Taylor, G. W., and Amer, M. Understanding attention and generalization in graph neural networks. Advances in neural information processing systems, 32, 2019.
McAllester, D. and Stratos, K. Formal limitations on the measurement of mutual information. In International Conference on Artificial Intelligence and Statistics, pp. $75. PMLR, 2020.
Köhler, D. and Heindorf, S. Utilizing description logics for global explanations of heterogeneous graph neural networks. arXiv preprint arXiv:2405. 2024.
Miao, S., Liu, M., and Li, P. Interpretable and generaliz- able graph learning via stochastic attention mechanism. In International Conference on Machine Learning, pp. 15524-15543 PMLR, 2022a.
Kraskov, A., Stögbauer, H., and Grassberger, Estimat- ing mutual information. Physical Review Statisistial Nonlinear, and Soft Matter Physics, 69(6)3661 2004.
Kuperberg, D. Positive first-order logic on words and graphs. Logical Methods Computer Science, 19, 2023.
Miao, S., Luo, Y., Liu, M., and Li, P. Interpretable geo- metric deep learning via learnable randomness injection.

---

Beyond Topological Self- Belf-Explainabbe GNNs
In The Eleventh International Conference Learning Representations, 2022b.
In ESANN 2023-Praceedings, European Symposium on Artificial Neural Networks, Computational Intelligence and Machine Learning, 2023.
Morris, C., Kriege, N. M., Bause, F., Kersting, K., Mutzel, P., and Neumann, M. Tudataset: collection bench- mark datasets for learning with graphs. arXiv preprint WrXiv:2007.08663 2020.
Sundararajan, M., Taly, A., and Yan, Q. Axiomatic attribu- tion for deep networks. In International conference machine learning, pp. 3319-33-00 -328. PMLR, 2017.
Müller, P.. Faber, L.. Martinkus, K., and Wattenhofer, R. Graphchef: Learning the recipe of your dataset. In ICML 3rd Workshop on Interpretable Machine Learn- ing Healthcare (IMLH), 2023. URL https:// openreview met/fooumm wtwfoooummniiddyydao.. 2gY2H55P.....
Sushko, I,, Salmina, E., Potemkin, V. A., Poda, G., and Tetko, I. V. Toxalerts: A web server of structural alerts for toxic chemicals and compounds with potential adverse reactions. Journal of Chemical Information and Model- ing, 52(8):230--2366 2012. doi: 10. 1.100//ci300244
Paszke, A., Gross, S., Chintala, S., Chanan, G.. Yang, E., DeVito, Z., Lin, Z., Desmaison, A., Antiga, L., and Lerer, A. Automatic differentiation in pytorch. In NIPS-W. W, 2017.
Tan, J., Geng, S., Fu, Z.., Ge, Y., Xu, S., Li, Y., and Zhang, Y. Learning and evaluating graph neural network expla- nations based on counterfactual and factual reasoning. In Proceedings of the ACM Web Conference 2022, WWW 222 pp. 1018-1027, New York, NY, USA, 2022. Associa- tion for Computing Machinery. ISBN 9781 9781450390965. doi: 10.1145/3485444:35111428 URL ht htts://dooi. org 10. 01..0.1145/44880
Pluska, A., Welke, P., Gärtner, T., and Malhotra, S. Logical distillation of graph neural networks. In ICML 2024 Workshop on Mechanistic Interpretability. 2024.
/doi.
3511
Ragno, A., La Rosa, B., and Capobianco, R. Prototype- based interpretable graph neural networks. IEEE Trans- actions Artificial Intelligence, 2022.
Teso, S., Alkan, Ö., Stammer, W., and Daly, E. Lever- aging explanations in interactive machine learning: An overview. Frontiers Artificial Intelligence, 2023.
Riesen, K. and Bunke, H. lam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, SSPR & SPR 2008, Orlando, USA, December 4-6, 2008. Proceedings, pp. 287-297, Springer, 2008
Tishby, N., Pereira, F. C., and Bialek, W. The infor- mation bottleneck method. ArXiv, physics/0004057, 2000. URL https: //tas://app /appi semant escholar. org/CorpusID:8836449
Wang, E., Khosravi, P., and Van den Broeck, G. Probabilistic sufficient explanations. 2021.
Rudin, C. Stop explaining black box machine learning models for high stakes decisions and use interpretable models instead. Nature Machine Intelligence, 1(5):206 215, 2019.
Weisstein, E. W. Edge cover, 2025. URL https:
mathworld, froffrmm... wwwe hee///dggeeverre html.
Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., and Monfardini, The graph neural network model. JEEE transactions on neural networks, 20(1):61-80, 2008.
Wong, F., Zheng, E. J., Valeri, J. A., Donghia, N. M., Anahtar, M. N., Omori, S.. Li. A., Cubillos-Ruiz, A.. Krishnan, A., Jin, W., et al. Discovery of structural class of antibiotics with explainable deep learning. Na- ture, (7777997) 2024.
Serra. G. and Niepert, M. Learning to explain graph neural networks. arXiv preprint arXiv:2209. /4402, 2022.
Wu, T., Ren, H., Li, P., and Leskovec, J. Graph information bottleneck. Advances in Neural Information Processing Systems, 33:20437-20448, 2020a.
Setzu, M., Guidotti, R., Monreale, A., Turini, F., Pedreschi, D., and Giannotti, F. Glocalx-from local to global expla- nations of black box ai models. Artificial Intelligence, 194:103457, 2021.
Wu, Y.-X., Wang, X., Zhang. A., He, X., and Chua, T-- S. Discovering invariant rationales for graph neural net- works. arXiv preprint arXiv:2201. 12872, 2022.
Shih, A., Choi, A., and Darwiche, A. A symbolic approach to explaining bayesian network classifiers. arXiv preprint arXiv:1805.033 033600 2018
Wu, Z., Ramsundar, B., Feinberg, E. N., Gomes, J., Ge- niesse, C., Pappu, A. S., Leswing, K., and Pande, V. Moleculenet: a benchmark for molecular machine learn- ing. Chemical science, 9(2::113-530 2018.
Spinelli, I., Guerra, M., Bianchi, F. M., Scardapane, S., et al. Combining stochastic explainers and subgraph neural networks can increase expressivity and interpretability.
12

---

Beyond Topological Self-Explainable GNNs
Wu, Z., Pan, S., Chen, E., Long, G., Zhang, C., and Philip,
S. Y. A comprehensive survey graph neural networks. IEEE transactions neural networks and learning sys- tems, 2020b.
Xu, K., Hu, W. Leskovec, J. and Jegelka, S. How powerful graph neural networks? arXiv preprint (rXiv:1810000822 2018.
Ying, Z.., Bourgeois, D., You, J., Zitnik, M., and Leskovec, Gnnexplainer: Generating explanations for graph neural networks. Advances in neural information processing systems, 32, 2019.
Yu, J., Xu, T., Rong, Y., Bian, Y., Huang, J., and He, R. Graph information bottleneck for subgraph recognition. In International Conference on Learning Reprexentations, 2020.
Yu, J., Cao, J., and He, R. Improving subgraph recogni- tion with variational graph information bottleneck. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 1999-1 2022.
Yu, J., Ignatiev, A., and Stuckey, P. J. On formal fea- ture attribution and its approximation. arXiv preprint arXiv:2307. 033.003300,0 2023.
Yuan, H., Yu, H., Wang, J., Li, K., and Ji, S. On explainabil- ity of graph neural networks via subgraph explorations. In International conference on machine learning, pp. 12241- 12252. PMLR, 2021.
Yuan, H., Yu, H., Gui, S., and Ji, S. Explainability in graph neural networks: A taxonomic survey. IEEE transactions on pattern analysis and machine intelligence, 45(5):5782- 5799, 2022.
Zhang, Z., Liu, Q. Wang, H., Lu, C., and Lee, C. Prot- gun: Towards self-explaining graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelli- gence, volume 36, pp. 9127-9135, 2022.
13

---

Beyond Topological Self-Explainable GNNs
A. Proofs
A.1. Proof of Theorem 3.2
Preliminaries and Assumptions. Recall that an SE-GNN is composed a GNN-based classifier f and an explanation extractor q. Given an instance G, the explanation extractor q returns subgraph g(G) R C G, and the classifier provides label ((C) ((((G)).
Note that analyzing the losses presented in Table 1 is challenging due to the potentially misleading minima induced by undesirable choices of λι and Xz. For example, choosing the explanation regularization weight λι and X2 in Table to be zero can trivially lead to correct predictions but with uninformative explanations. Equivalently, setting λι and x too high yields models with very compact yet useless explanations, as the model may not converge to a satisfactory accuracy. Since our goal is to analyze the nature of explanations extracted by q. we assume that f expresses the ground truth function. Also, we assume the SE-GNN to have perfect predictive accuracy, meaning that f((()) always outputs the ground truth label for any imput. Those two assumptions together allow us focus only on the nature of the explanations extracted by q.
We also consider SE-GNN with a hard explanation extractor. For sparsity-based losses (Eq. (11)), this amounts to assigning score equal to 1 for edges in the explanation R, and equal to 0 for edges in the complement G' \ R. For Information Bottleneck-bras based losses (Eg. (14)), instead, the explanation extractor assigns a score of 1 for edges in the explanation R, and equal to r for edges in the complement G' R, where r is the hyper-parameter chosen as the uninformative baseline for training the model (Miao et al., 2022a). Therefore, an explanation R is identified as the edge-induced subgraph where edges have score Puv
Theorem 3.2. Let be an SE-GNN with a ground truth classifier f (i.e., f(G) always returns the true label for G), a hard explanation extractor g, and perfect predictive accuracy. Then, g achieves minimal true risk (as indicated in Table 1) if and only if for any instance G, g(G) provides Minimal Explanations for the predicted label g(G).
Proof. We proceed to prove the Theorem by analyzing two cases separately:
Sparsity-based losses Let us consider the following training objective of a prototypical sparsity- based SE-GNN, namely GISST (Lin et al., 2020). Here we focus just on the sparsification of edge-wise importance scores, and we discuss at the end how this applies to node feature- wiiue scores:
min ((f(a(G))
+
Σ
Puo
A2
Σ (u,D)E
Puo log(Puv) + (1 Puv.) log(1 Puo)
(11)
E
(u.)EE
Given that the importance scores Puu can only take values in f0, 1}, the last term in Eq. (11) equals to 0. Also, given that every edge outside of q(G)) has Puo = 0 and every edge in g(G) has Puv 1, we have that
Σ (u.))E
Puo = lg())
(12)
Hence, the final minimization reduces to:
Ig() E
min C(f((()))) +
(13)
Minimal True Risk for SE-GNN = Minimal Explanations
Given that f is the ground truth classifier, then due to perfect predictive accuracy for f(g(G)) we have that f(g(G) f(G) = y² where y" is the ground truth label for G. This implies that L(f(g())), Y) is minimal. Now, for the true risk to be minimal we must additionally have that X₁ (GG))/ E) in Eq. (13) is minimized well. Note that g(G) returns the explanation R. Hence, minimizing \1lg(G)1/1E1 in Eq. (13) requires that we find the smallest R C G such that [(f(g(G)) Y) is also minimal, hence f({(G) = f(R) = y". Also, note that fRR = f(((R) by perfect predictive accuracy of (R((R) and f being the ground truth classifier. Hence, we have that for an instance G, C G is the smallest subgraph such that (q(()) (R)).. Hence, a Minimal Explanation for (q(
14

---

Beyond Topological Self-Explainable GNNs
Minimal True Risk for SE-GNN <= Minimal Explanations
We now show the other direction of the statement, i.e., if (()) provides Minimal Explanations then an SE-GNN g (with ground truth graph classifier f and perfect predictive accuracy) achieves minimal true risk. Since, 9 achieves perfect predictive accuracy, we have that (g)())))) Y) is minimal. Furthermore, by definition of Minimal Explanations and assumption of perfect predictive accuracy, we have that R is the smallest subgraph such that f(q(G)) = (()(R) = y²" Hence, A1 (l)g)))
can not be further minimized in Eq. (13).
The same argument applies verbatim when adding the sparsification of (discrete) node feature explanations Eq. (11), as prescribed in Lin al. (2020).
Information Bottleneck-base based losses Let us consider the following training objective of prototypical stochasticity
injection-based SE-GNN, namely GSAT (Miao et al., 2022a). The same holds for other models like LRI (Miao et al., 2022b), GMT (Chen et al., 2024), and GIB (Wu et al., 2020a):
min (f(a(G)) A
Σ
Puv log( Puv (1 Puv) log( - Puv
(14)
1
(O,))EE
By the hard explanation extractor assumption, Par when (u, v) E R and r otherwise. Then, we can differentiate the contribution of each edge to the second term separately, depending on its importance score: For edges where Puv = 1:
Puv log( Pun + (1 Puv) log( 1 - Puv = [g(()) log(
Σ (2
(15)
For edges where Puv- r:
Σ (u.D)ER
Pun log( Puy + (1 - (P- log(
1 - Pur 0
(16)
1
We can then rewrite the minimization as follows:
min ((f((G)), + [og( 5
(17)
which optimizes the same objective as Eq. (13), as the terms not in common are constants. Thus, similar argument to that of sparsity-based losses follows.
A.2. Proof of Theorem 4.2
Theorem 4.2. Given classifier g expressible as a purely existentially quantified positive first-order logic formula and a positive instance G of any size, then Minimal Explanation for g(G) is also Prime Implicant explanation for g(G).
Proof. Let g be classifier that can be expressed boolean FOL formula of the form
Ar Arg ... Ark (111, 22, Rk),
(18)
where & is positive and quantifier-free. A positive instance G for g is an instance such that G g. Now, let R C G be Minimal Explanation for 9G)), i.e, for G = Φ. We must show that R is also Pl explanation.
We now show that R satisfies conditions (1), (2) and (3) for PI Explanation as given in Definition 4.1
1. By definition of Minimal Explanation, we already have R S G. Hence, condition (1) satisfied.
2. Since a Minimal Explanation, we have that R + g. Also, g is purely existential and positive, hence there are specific elements ......, a E R witnessing gi that is, R } ( aq). Now if is a subgraph of G such that R I, then all a, and relations containing 0; remain in T. Hence I also satisfies g and therefore I ド g. This shows that every superset I of R inside G satisfies g, satisfying the condition (2) in the PI explanation definition.
'Even though it not designed for interpretability, as it predicts importance scores every layer making the resulting explanatory subgraph not intelligible, here we also include GT B as reference as shares the same training objective.
15

---

Beyond Topological Self-Explainable GNNS
3. Finally, we now show that R minimal. Note that since R is Minimal Explanation, there exists no R2| < that R' F g. In particular, if there R' R such that R' }= g. that would contradict the minimality condition for Minimal Explanation. Consequently, no such It can serve smaller PI explanation. This ensures condition (3).
[ such
There exist classifiers that are existentially quantified but Minimal Explanations still equal PI explanations. For instance, 3 Red(( not be expressed as a purely existentially quantified first-order logic formula for which Minimal Explanations still equal Pl explanations.
Remark:
A.3. Proof of Proposition 4.3
Proposition 4.3. Let g be a classifier and a given label. Let 5212) be the set of all the finite graphs (potentially with a given bounded size) with predicted label y. Then,
Vaenio MF( S UGEngo PT(g(G))
(4)
Proof. Any Minimal Explanation R for g(G) is also an instance with a label g( = g(G) = y. We now show that Minimal Explanation for g(R) is also Pl explanation for (R), and hence it is contained in UGENJ0) PI(g(G)). For any R' R, we have that ((It' + gGG (as R is a Minimal Explanation for (G)), and hence g(tt) # g(t). Furthermore, any extension of R (within R) does not lead to prediction change, vacuously, Hence, R is a Pl explanation for g(R) = g(G) = y.
A.4. Proof of Theorem 4.4
Theorem 4.4. There exist two distinct classifiers g and g' and a label y such that:
1. For all graphs G s.t. g(G) = (G') = y. we have
ME(g(G)) (E))
(5)
2. There exists at least one graph G with g(G*) = (G") y such that
PI(g(G")) + (I(g'(G*)).
(6)
Proof. We continue with g and g' given in the proof of Theorem 3.4, i.e., 9 = Fy y) and g' = F. y). As shown in Theorem 3.4, condition 1 is true for g and g'. Now, for any positively labeled graph G*, PI(g(G))) is the set of edges in G*, whereas PI(g' (G")) is the set of edge covers. As shown in Fig. 1, there exists a graph (say a triangle) such that the set of edge covers is different from the set of edges.
A.5. Proof of Proposition 5.3
Proposition 5.3. An explanation R C f.ror g(G) has a maximal Suf(R) score if and only if there exists a PI explanation M C for (G).
Proof. An explanation R is maximally sufficient if all possible edge deletions in G Rt leave the predicted label g(G)) equal to gG), where G' are the possible graphs obtained after perturbing G \ R. Equivalently, every possible extension G" of R in G preserves the label. This is true and only if R is explanation or there exists a subgraph M C. R, which is PI.
A.6. Proof of Proposition 5.4
Proposition 5.4. An explanation R C G gG) can have a non-zero Nec(R) score only if intersects every PI explanation for (G).
Proof. An explanation has zero necessity score all possible edge deletions in R leave the predicted label (G") equal to g(G), where G C are the possible subgraphs obtained after perturbations in Assume the contrary that R does not
16

---

Beyond Topological Self-Explainable GNNS
intersect a Pl explanation M, and has non-zero necessity score. Then, there exists graph G' obtained by perturbing R such that ((G) * g(G'). But note that M _ G' and M is PI by assumption, hence g(G) must be equal to g(G", leading to contradiction. Therefore, Rt must intersect all prime implicants to have non-zero necessity score.
B. Implementation Details
B.1. Datasets
In this study, we experimented on nine graph classification datasets commonly used for evaluating SE-GNNs. Among those, we also proposed two novel synthetic datasets to show some limitations of existing SE-GNNs. More details regarding each dataset follow:
MedBlueNode (ours). Nodes are colored with a one-hot encoding of either red or blue. The task to predict whether the number of red nodes is larger or equal to the number of blue ones. The topology is randomly generated from Barabási-Albert distribution (Barabási & Albert, 1999). Each graph contains number of total nodes in the range [10, 100). We also generate two OOD splits, where respectively either the number of total nodes is increased to 250 (OOD,). or where the distribution of the base graph is switched to an Erdos-Rénn distribution (OOD2) (Erdos et al., 1959).
TepoFea ru (ours). Nodes are either uncolored or marked with a red color represented one-hot encoding. The task is to predict whether the graph contains a certain motif together with at least two nodes. The base graph is randomly generated from a Barabási-Alber distribution (Barabási & Albert, 1999). Each graph contains a number of total nodes in the range [8, 80]. We also generate two OOD splits, where respectively either the number of total nodes is increased to 250 (OOD1), or where the distribution of the base graph switched to an Erdos-Rényí distribution (OOD2) (Erdos et al., 1959)
GOODMotis if E (Gui et al., 2022) is a three-classes synthetic dataset for graph classification where each graph consists of a basis and a special motif, randomly connected. The basis can be a ladder, tree (or a path), or a wheel. The motifs are a house (class 0), a five-node cycle (class 1), crane (class 2). The dataset also comes with two OOD splits, where the distribution of the basis changes, whereas the motif remains fixed (Gui et al., 2022). In our work, we refer the OOD validation split of Gui et al. (2022) as OOD,, while to the OOD test split as OOD2.
MUTAG (Debnath et al., 1991) is molecular property prediction dataset, where each molecule is annotated based on its mutagenic effect. The nodes represent atoms and the edges represent chemical bonds.
BBBP (Wu al., 2018) is a dataset derived from a study on modeling and predicting barrier permeability (Martins et al., 2012).
AIDS (Riesen & Bunke, 2008) contains chemical compounds annotated with binary labels based on their activity against HIV. Node feature vectors are one-hot encodings of the atom type.
AIDSC1 (ours) is an extension of AIDS where we concatenate the value 1.0 to the feature vector of each node.
MNIST75sp (Knyazev et al., 2019) converts the image-based digits inside graph by applying super pixelation algorithm. Nodes are then composed of superpixels, while edges follow the spatial connectivity of those superpixels
Graph SST2 is sentiment analysis dataset based on the NLP task of sentiment analysis, adapted from the work of Yuan et al. (2022). The primary task is binary classification to predict the sentiment of each sentence.
B.2, Architectures
SE-GNNS
The SE-GNNs considered in this study are composed of an explanation extractor g and a classifier f. The explanation extractor is responsible for predicting edge (or equivalently node) relevance scores Pae E [0, 1), which indicate the relative importance of that edge. Scores are trained to saturate either to or to predetermined value that is considered as the uninformative baseline. For IB-based losses, this value corresponds to the parameter r (Miao et al., 2022a;b), whereas for Sparsity based it equals (Lin et al., 2020; Yu et al., 2020). The classifier then takes as input the explanation and predicts the final label. Generally, both the explanation extractor and the classifier are implemented as GNNs, and relevance scores are predicted by a small neural network over an aggregated representation of the edge, usually represented
17

---

Beyond Topological Self-Explainable GNNs
as the concatenation of the node representations of the incident nodes. A notable exception is GISST, using shallow explanation extractor directly on raw features. Both explanation extractors and classifiers can then be augmented with other components to enhance their expressivity their training stability like virtual nodes (Wu et al., 2022; Azzolin et al., 2025) and normalization layers (loffe, 2015). Then, SE-GNNs may also differ in their training objectives, as shown in Table 1, or the type of data they are applied to (Miao et al., 2022b).
We resorted to the codebase of Gui et al. (2022) for implementing GSAT, which contains the original implementation tuned with the recommended hyperparameters. GISST is implemented following the codebase of Christiansen et al. (2023). When reproducing the original results was not possible, we manually tuned the parameters achieve the best downstream accuracies. We use the same explanation extractor for every model, implemented as a GIN (Xu et al., 2018), and adopt Batch Normalization (loffe, 2015) when the model does not achieve satisfactory results otherwise. Following Azzolin et al. (2025), we adopt the explanation readout mitigation in the final global readout of the classifier, so to push the final prediction to better adhere to the edge relevance scores. This is implemented as a simple weighted sum of final node embeddings, where the weights are the average importance score for each incident edge to that node. The only exceptions are GOODMot i f, BBBP, and Graph-SST2, where we use a simple mean aggregator as the final readout to match the results of original papers.
Model hyper-parameter. We set the weight of the explanation regularization follows: For GISST, we weight all regularization by 0.01 in the final loss; For SMGNN, we set 1.0 and 0.8 the L1 and entropy regularization respectively; For GSAT, we set the value of r to 0.7 for GOODMot if f. MNIST75sp, Sraph-SSTT and BBBP, to 0.5 for TopoF eatturetre AIDS, AIDSCI, and MUTAG, and to 0.3 for for every dataset, except for Graph-SSt S812 and GOODMot if where it is set to 20. Then, the parameter À regulating the weight of the regularization is set to 0.001 for all experiments with SMGNN, while to 1 for GSAT on every dataset except for RedBlued .eddes.
Also, for GSAT we set the decay of r is set every 10 step
For each model, we set the hidden dimension of GNN layers to be 64 for MUTAG, 300 for GOODMotif, BBBP, and Graph-SST2, and 100 otherwise. Similarly, we use dropout value of 0.5 for GOODMot i and Graph-SST2, of 0.3 for MNIST75spp MUTAG, and BBBP, and of 0.0 otherwise.
SMGNN. The explanation extractor q of GISST is implemented as a simple MLP over input features, meaning the explanation does not depend on topological information. To overcome this limitation, we propose simple augmentation named Simple Modular GNN (SMGNN). SMGNN adopts the same explanation extractor as GSAT, which is however trained with the GISST's sparsification loss after an initial warmup of 10 epochs. Therefore, SMGNN adopts specular architecture GSAT, but with the sparsification loss of GISST. Similarly to GSAT, unless otherwise specified, the classifier backbone is shared with that of the explanation extractor, and composed of 5 layers for BBBP, and 3 layers for all the other datasets.
Dual-Channel GNNs are implemented as a reference SE-GNN of choice, whose architecture remains unchanged, and a linear classifier taking as input global sum readout of node input features. Both models have an output cardinality equal to the number of output classes, with a sigmoid activation function. Then, the outputs of the two models are concatenated and fed to our (B) LENs, described in Appendix C.4. Following Barbiero et al. (2022), we use an additional fixed temperature parameter with a value of 0.6 to promote sharp attention scores of the underlying LENs Also, the number of layers of (B) LENs and LENS are fixed to 3 including input and output layer, and the hidden size is set to 350 for SNIST75sp. 64 for MUTAG and BBBP, 30 for GOODMot i f. and 20 otherwise. The input layer of (B) LENs and LENs does not use the bias parameter. We adopt weight decay regularization to promote the sparsity of the linear model. For the additional experiment on AIDSC1 (see Appendix C.5), a more stringent L1 sparsification is applied.
Dual-Channel GNNs
B.3. Extracting rules from linear classifiers
Although linear classifiers do not explicitly generate rules, their weights can be interpreted as inequality based rules. For this interpretation to be meaningful, the model should remain simple, with sparse weights that promote clarity. In this section, we review how this can be achieved.
A (binary) linear classifier makes predictions based on a linear combination of input features, follows:
y = - x b
(19)
where x E Rd is a d-dimensional input vector, and w E Rd and b E R the learned parameters. The decision boundary of the classifier corresponds to the hyperplane nn x + 0, and the classification then based on the sign of y. We will
18

---

Beyond Topological Self-Explainable GNNs
50
y=1
y
Dec. Bound.
Dec. Bound.
40
num red nodes
num red nodes
30
30
20
20
10
10
0-
50
num blue nodes
num blue nodes
Figure 3: Decision boundary of the linear classifier of DC-SMGNN for RedBluce ueNdes over the validation split (random seed and 2). The plot is in 2D since RedBl ueNodes contains only red or blue nodes.
consider a classifier predicting the positive class when
w x + 0.
(20)
By unpacking the dot product, Eq. (20) corresponds to a weighted summation of input features, where weights correspond the model's weights wt
W/ F +
WgFe + 2
(21)
For ease of understanding, let us commit the specific example of RedBl There, the linear classifier in the side channel of DC-GNNs takes input the of node features for each graph. Therefore, input vector will be [xr,, Tb, Nu], where Tu indicates the number of red, blue, and uncolored nodes, and positive prediction is made when
Wy + Wh2t W. b 2 0.
(22)
If the model is trained correctly, and the training regime promotes enough sparsity e.g. via weight decay LA sparsification we can expect to have 0 as there are no uncolored nodes and thus feature T., carries no information, and b ~ 0. Then, we can rewrite Eq. (22) as
W. 2
(23)
Then, w, = - Wi a configuration of parameters that allows to perfectly solve the task, yielding the formula
2r 2 Xb
(24)
We show in Fig. that indeed our DC-GNNs learned such configuration of parameters by illustrating the decision boundary for the first two random seeds over the validation set. The figure confirms that the decision boundary is separating graphs based on the prevalence of red or blue nodes.
We plot in Fig. 4 a similar figure for TopoFeature, where the decision boundary intersects the y-axis, on average over 10 seeds, at the value of 1.23. By inspecting the model's weights, non-red nodes are assigned a sensibly lower importance magnitude (at least 102 lower). Therefore, to convey a compact formula, we keep only the contribution of øy, resulting on average in the final formula x, 2 1.23, which fires when least two red nodes are present.
19

---

Beyond Topological Self-Explainable GNNs
3.5
3.5
num red nodes
3.0
num red nodes
3.0
2.5
2.5
2.0
2.0
1.5
1.0
1.0
y=0
y=0
0.5
y=1
0.5
y=1
Dec. Bound.
Dec. Bound.
0.0
@0XID 00000DOO
0.0
@0MID 48 0000000
20
40
60
80
num uncolored nodes
num uncolored nodes
(b)
Figure 4: Decision boundary of the linear classifier of DC-SMCNN for TopoFeature over the validation split (random seed 1 and 2). For seed 1, Wr 0.89, wy - t0, -0.001, and -1.3. For seed 2, w, 0.92, wh -1e-33 drop its visualization
w, = 00.002 and b 1.09.. Since 25 equals 0 there no blue nodes in the dataset, collapsing the plot to 2D. When providing the final interpretable formula, we drop 25 and 2u. due to their sensible lower magnitude. More aggressive sparsification can be applied to the training of the linear model to promote an even lower w...
B.4. Training and evaluation.
Every model is trained for the same 10 random splits, and the optimization protocol is fixed across all experiments following previous work (Miao et al., 2022a) and using the Adam optimizer (Kingma & Ba, 2015). Also, for experiments with Dual-Channel GNN, we fix an initial warmup of 20 epochs where the two channels are trained independently to output the ground truth label. After this warmup, only the overall model is trained altogether. The total number of epochs is fixed to 100 for every dataset except for Graph- SST2 where is set 200.
For experiments Graph-SSTI layer mapping the graph embedding to the output. The parameters of the classifier are then different from those of the explanation extractor and trained jointly.
forced the classifier of any SE-GNNs to have single GNN layer and final linear
When training SMGNN, to avoid gradient cancellation due to relevance scores approaching exact zero, we use a simple heuristic to push the scores higher when their average value in the batch is below 2e -9, This is implemented by adding back the loss of the batch the negated mean scaled by 0.1. This is similar value clapping used by GISST, but found yield better empirical performances.
B.5. Software and hardware
Our implementation is done using PyTorch 2.4.1 (Paszke al., 2017) and PyG 2.4.0 (Fey & Lenssen, 2019). Experiments two different Linux machines, with CUDA 12.6 and single NVIDIA GeForce RTX 4090, with CUDA 12.0 and single NVIDIA TITAN V.
C. Additional Experiments
C.1. Running time analysis
Table 5 presents the running time for two instances of SE-GNNs and DC-GNNs on real-world datasets, showing that the proposed architecture is not adding any significant computational overhead to the base architecture.
20

---

Beyond Topological Self-Explainable GNNs
Table 5: Average running time in seconds of SE-GNNs and DC-GNNs for two real-world datasets.
Model
Graph-SST2
BBBP
GSAT
4.78 + 0.23
0.55 0.18
DC-GSAT
4.50 0.32
0.58 + 0.18
SMGNN
6.51 + 0.37
0.53 0.18
DC-SMGNN
6.32 0.50
0.71 = 0.22
C.2. Hyper- pper-parmeeter ablation study
Table 6 presents ablation study the GOODMotif f dataset investigate the robustness of our results the choice of hyper-parameter. Overall, results are stable across the hyper-parameter choice, except for a small fluctuation when choosing r 0.5 as the parameter of GSAT. However, for r 2 0.7, performance stabilizes.
Table 6: Ablation study on the hyper-parameter choice for the GOODMot if dataset. The values underlined represent chosen
values for the main experiments. Results indicate test accuracy.
Hyper-parameter
Value
DC-GSAT
DC-SMGNN
92 + 01
93 + 01
(B) LENs hidden size
+
9
64
92 01
03
01
93
(B) LENS num layers
91
91
4
93 +
93
0.1
93 01
91
(B) LENs sigmoid temperature
0.3
93 01
93
0.5
93 01
91
0.5
90 + 02
GSAT's r
0.7
93 01
0.9
93 +1
C.3. Testing DC-GNNs on DIR (Wu et al., 2022)
Following the recommendation of an anonymous reviewer, we performed an additional experiment with DIR (Wu et al., 2022), which is a SE-GNNs not fitting the taxonomy of Table 1. While DIR may not output Minimal Explanations, our proposed Dual-Channel GNNs general framework that can be applied to any SE-GNNs. We report the results for augmenting DIR with our DC-SMGNN framework in Table 7. In running those experiments, we did not perform hyper-parameterr tuning, thus final model accuracies and stability might be further improved by more careful selection.
Table 7: Augmenting DIR with proposed Dual-Channel GNNs framework.
Model
AIDS
MUTAG
BEBP
Graph-SSTP
MNIST75ep
Fl
Channel
Acc
Channel
AUC
Channel
Acc
Channel
Acc
Channel
DIR
96 + 03
78 0
64 + 02
83 01
83 4:00
DC-DIR
96 0:03
Rule
78 1.04
Mix
65 1.02
Topo*
83 1.01
Mix
82 1.00
Topo
C.4. Ablation study how to choose aggr
Our implementation of aggr relies LENs to combine the two channels in interpretable manner. LENs however found to be susceptible to leakage (Azzolin et al., 2022), that is they can exploit information beyond those encoded in the activated class. Leakage hinders the semantics of input activations, thus comprising the interpretability of the prediction (Margeloiu et al., 2021; Havasi et al., 2022). Popular remedies include binarizing the input activations (Margeloiu et al., 2021; Azzolin et al., 2022; Giannini et al., 2024) so as to force the hidden layers of LENs to focus on the activations themselves, rather than their confidence.
21

---

Beyond Topological Self-Explainable GNNS
Table 8: Raw channel relevance scores for the experiments in Table 2. The "Channel" column reports, the relative importance computed for each channel, For binary classification tasks, the first entry corresponds to the SE-GNN channel, whereas the last is to the interpretable model. For multi-class tasks, the first [Y] entries correspond to the importance for each of the [Y] SE-GNNs outputs, whereas the last [ to that of the linear model. For GOODMot in particular, YY] =3
Model
RedBlueNoos
TopoFeature
GOODMotiE Channel
Ace
Channel
Acc
Channel
Acc
[0.33,, U.36, 0.30, 4e _2 1e=1
DC-GBXI
100 +:00
[0.02,, 0.98) 0.05
100
[0.47. 0.53 + 0.27
93
= 0.30, 0.29, le 2 2.2e
le
[0.27, 0.19, 0.53, 1e 30
le 10-
DC-SMSNN
100 0:
[0.05, 0.95]
0.10
100 (0,31, 69)
0.11 93
+ 0.29, 0.0,,000,000 0.0,
Table 9: Ablation study for the choice of aggr. The reference architecture in use is SMGNN and the dataset used for the evaluation is TepoFeature. The "Channel" column reports, when aggr supports it, the relative importance computed for each channel, where the first entry corresponds to the SE-GNN channel, whereas the last to the interpretable model.
aggr
TopoFeature Channel
Acc
Num red nodes 2
agg Gödel Producr
96 =
Not supported
96 1
Not supported
a Linear
79 +9
[-1.22, 1.77] + [1.65, 0.92]
0.24 +: 1.01
a MLP
+
Not supported
a ggT ST gggrins Fimess
95 1:05
[0.62, 0.38 = 0.42
0.17 + 1.47
65 0:
00.01, 0.99 + 0.01
0.70 + 0.96
a ggr (BYLEXS (ours)
100
0..9 + 0.11
1.23 1 0.17
In our work, we adopt a different strategy to avoid leakage in LENs and propose to anneal the temperature of the input activations so as to gradually approach binary activation during training, while ensuring smooth differentiation. Input activations are generally assumed to be continuous in [0, 1), and usually generated by a sigmoid activation function (Barbiero temperature annealing simply scales the raw activation before the sigmoid activation by
et al., 2022). Therefore, temperature parameter T, where is linearly annealed from value of 1 to 0.3. The resulting model is indicated with the name of (Eisary)LENs- (B) LENs in short.
In the following ablation study, we investigate different approaches for implementing aggr, showing that only (B) LENs reliably achieve satisfactory performances while preserving the semantics of each channel. The baselines for implementing aggr considered in our study are as follows:
Logic combination hased on T-norm fuzzy logics, like Gödel aggr G B) = -mim (A, B) and Product logic aggTrroduec (A, B) = A B (Klement et al., 2013).
Linear combination Linerr (A, B) = W [B) where concatenaMEss the two inputs.
Multi-Layer Perceptron MLM (A, B) W3 WW(o(W((oW((A\11))
Logic Explained Network (LENs) aggr LEKS (A, B) = LEN B).
Logic Explained Network (LENs) with discrete input aggr T (A, B) (ENA(S(()) The discreteness of the input activations is obtained using the Fruiigh-TTruuge (ST) reparametrizztion (Jang et al., 2016; Azzolin et al., 2022; Giannini et al., 2024), which uses the hard discrete scores in the forward step of the network, while relying on their soft continuous version for backpropagation.
We provide in Table 9 the results for DC-SMGNN using different aggr choices TopoFeature. In this dataset, the expected rule to be learned by the interpretable channel is number of red nodes 2 2. Among the alternatives, Gode- aggrrhouect and aggT MLP do not allow to understand how the channels are combined, resulting in unsuitable aggr functions for our purpose. eggglinen and ag. accuracy and an interpretable combination of channels. Nonetheless, the presence of leakage hinders full understanding of the interpretable rule, as the hidden layers of the LENS are allowed to exploit the confidence of the interpretable channel's
T instead, fail in solving the task. aggr however, achieve both a satisfactory
22

---

Beyond Topological Self-Explainable GNNS
predictions in building an alternative rule, that it is now longer intelligible. Overall, (B) LENs is the only choice that allows the combination of both accuracy and an interpretable combination of the two channels, all while preserving the semantics of the channels as testified by the rule number of red nodes 2 1.23 matching the expectations".
C.5. More experiments AIDS
In Table 3 we showed that simple linear classifier on sum-aggregated node features can suffice for achieving the same, or better, performances than plain SE-GNN. Even if the linear classifier is promoted for sparsity via weight decay regularization, the resulting model is still difficult to be interpreted, as it assigns non-negligible scores to a multiple of input features, making it difficult to extract simple rule. For this reason, we extend the original set of node features by concatenating the value 1.0 for each node. The role of this additional feature is to allow the linear classifier to easily access the graph-level feature number of nodes. We name the resulting updated dataset AIDSC1.
Then, train the same models Table where we increase the sparsity regularization both the SE-GNN and the linear model, to heavily promote sparsity. This is achieved by setting to 0.1 the weight decay regularization for the SE-GNN, and to 0.01 L1 sparsification to the linear classifier. The results are shown in Table 10, and show that under this strong regularization, SE-GNN struggles to solve the task. Conversely, the Dual-Channel GNN augmentation still solves the task, while providing intelligible predictions. In fact, by inspecting the weights of the linear classifier when picked by the Dual-Channel GNN, the resulting model weights reveal that the model is mainly relying on the count nodes in the graph, as pointed out Pluska et al. (2024). For completeness, we report in Table 12 the full weight matrix for DC-SMGNN.
Table 10:
Dual-Channel GNNs solve AIDSC1 even when prompted for strong sparsification, whereas plain SE-GNN achieves suboptimal predictions. Results are averaged only over seeds where the Dual-Chaman GNN selects the linear classifier as the main channel. We indicate with superscript numbers the seeds left out from the analysis. The rule extracted from the last column of Table 12 and averaged across nine seeds.
Model
AIDSC1
Fl
Channel
Rule
GIN
85
GISST
68
DC-GISST
02
Rule
num nodes S 12.66 + 0.18
GSAT
70 06
DC-G5AT 4,10
99 02
Rule
num nodes < 13.64 + 1.41
SMGNN
06
DC-SMONN
10
99 02
Rule
num nodes < 113.9 + 3.07
C.6. Tual-Channe GNN can improve the faithfulness of SE-GNNS
To measure the impact of the Dual-Channel GNN augmentation to plain SE-GNNs on the faithfulness of explanations, we compute Faith (Definition 5.1) for SMGNN and GSAT with their respective augmentations on TopoFeat eatuur and GOCDMot f. Following Christiansen et al. (2023), we compute Faith for both the actual explanation and randomized explanation obtained by randomly shuffling the explanation scores before feeding them to the classifier, and computing their ratio.
Faith(E) (aith(
Faith ratio
(25)
where R is the original explanation, and & a randomly shuffled explanation. The metric achieves score of 1 when the two values match, meaning the model is as faithful to the original explanation as a random explanation, whilst achieves a score of when the faithfulness of the original explanation considerably higher than that of a random one.
We compute the metric over the entire validation splits, and extract hard explanations by applying a topK strategy as indicated in previous studies (Amara et al., 2022; Longa et al., 2024), where & E [0.3, 0.6, 0.9] for GOODMot i f, and
7 Since the number of nodes is discrete, any threshold value in [1 + e, corresponds to the rule
23

---

Beyond Topological Self-Explainable GNNs
Table 11: Faithfulness of SE-GNNs and their augmentations for TopoF eet and GOODMot ff. Following (Christiansen et al., 2023), we report the ratio between Faith computed over randomly shuffled explanations and original ones. Therefore, scores close to zero indicate better values.
Model
TopoFeature Faith ratio (L)
GOODMotif
Faith ratio (L)
GSAT
0.42 1 0.10
0.78 i 0.08
DC-GSAT
0.39 # 0.43
0.69 + 0.11
SMGNN
0.65 0.28
1.00 + 0.00
DC-SMGNN
0.04 # 0.04
1.00 + 0.00
E [0.05, 0.1, 0.2, 0.4, 0.8] for TopoFeature. Perturbations are limited edge removals, and we force isolated nodes to be removed from the explanation. To compute Suf and Nec, we refer to the implementation of Azzolin et al. (2025) which requires hyperparameter b encoding the number of removals to apply at each perturbation. To obtain more robust results, we vary b E [0.01, 0.05, 0.1], corresponding to number of perturbations equal to a b percentage of the graph size. Then, the final Faith score is taken as the best Faith across k and averaged across the values of b.
The final results are reported in Table 11 and highlight that for TopoF where both DC-GNNs can exploit the interpretable channel (see Table 2), Dual- mual-Channel GNNs can achieve considerable gains in faithfulness. DC-GSAT, in particular, achieves better score but with considerably higher standard deviation. By inspecting the raw scores, however, we see that across the values 6, DC-GSAT scores [1.00, 0.05, 0.12] whereas GSAT achieves [0.50, 0.27, 0.48], indicating that b = 0.01 can be an unfortunate choice for this model as it may not bring enough perturbations to let the model change prediction. On the other values of b, however, the model achieves a significant gain in faithfulness ratio of almost an order of magnitude. On GOODMot if, f, instead, as the Dual-Channel GNNs does not have any advantage in using an interpretable model, we do not expect significant changes in the faithfulness scores as indicated in Table 11, where the only gain is due to higher variance.
We argue that the substantial gains in faithfulness mainly come from the ability of Dual-Channel GNNs to delegate each sub-task to the channel that can best handle it, i.e. learning the motif for the SE-GNN and the "2" rule to the linear classifier. In doing so, the underlying SE-GNN can better focus on highlighting the topological explanation, resulting in a more faithful explanation. This insight is supported by the analysis of the compactness of explanations provided in Appendix C.7, showing that indeed those SE-GNNs can better focus on the topological sub-task.
C.7. Plotting Explanations
In this section, we aim to provide examples of explanations of SE-GNNs and DC-GNNs. For visualization purposes, we rely on an importance threshold to plot the hard explanatory subgraph over the entire graph. Such threshold is picked by plotting the histogram of importance scores and chosen in such a way as to separate regions of higher scores from regions of lower scores. We will analyze the following datasets:
TopoFeature. Fig. and Fig. 6 present the histograms of explanation relevance scores for GSAT and SMGNN respec- tively. Overall, SMGNN achieves a better separation between higher and lower explanation scores, making it easier to select a proper threshold to plot explanations. Therefore, we will proceed to show explanation examples in Fig. 7 only for SMGNN for seed 1, picking as threshold the value 0.8. Overall, the model succeeded in giving considerably higher relevance to edges in the motif, but failed in highlighting red nodes as relevant for predictions of class 1, hindering a full understanding of the model's s decision process.
We proceed now analyze the explanations extracted for the same samples for DC- SMGNN. First, we plot the histogram of explanation scores in Fig. 8, showing better sparsification than a plain SMGNN. For reference, we also plot the histogram for DC-GSAT scores in Fig. 9, where the same sparsification effect can be observed. Then, we report in Fig. 10 the explanations for the same graphs as in Fig. 7, showing that CC-SMGNN achieves better sparsification than a plain SMGNN. In fact, since the rule at least two red nodes is learned by the interpretable model, the underlying SMCNN now just looks at the topological motif, and indeed the substantially more sparse edge score reflects this behavior. Overall, DCGSMGNN explanations reflect more closely the actual predictive behavior of the underlying SE-GNN.
24

---

Beyond Topological Self- Exll-xxxlie GNNS
GSAT
500d
seed
0.3
0.
seed 3
seed 4
5.0
0.2
66
10 0.0
0.4
0
066
1.0
density
6.4
100 0.
0.4
05
seed
Seed
seed
seed
5.0
62
24
0.3
10 0.0
0.2
0.4
0.6
0.
1.0
explanation relevance
Figure 5: Histograms of explanation relevance scores for GSAT TopoFeature (validation set). The model fails to reliably separate between relevant and non-relevant edges, making it difficult to select proper relevance threshold.
25

---

Beyond Topological Self- Eell-axxlainable GNNS
SMGNN
seed
seed
0.3
0'6
seed
seed
5.0
0.2
56
3.0 0.0
0.4
06
1.0
density
0.4
10 0.
0.4
0.
seed
Seed
seed
seed
5.0
62
24
0.3
10 0.
0.2
0.4
0.6
05
1.0
explanation relevance
Figure 6: Histograms of explanation relevance scores for SMGNN TopoFeature (validation set). The sparsification mechanism of SMGNN better separaMEs edges with higher importance than the rest of the graph.
26

---

Beyond Topological Self- Exff-Explaie GNNS
Idx: a Class 1
ldd: 1 Class
(b)
Idx: 2 Class 0
ldk: 8 Class
(c)
(d)
Figure 7: Examples of explanations for SMGNN (seed 1) over TopoFeature. Relevant edges are those with Par 2 0.8 and are highlighted in red. Edges are annotated with their respective score. Samples of class must have both cycle and at least red nodes.
27

---

Beyond Topological Self- Cell-Explainable GNNS
SMGNN
seed
seed
seed
0.0
0.2
344
56
0.8
10. 0.0
0.2
04
0.6
0.8
1.0
dencity
6.6
0.
10 0.9
06
seed 7
seed
0.2
0.0
seed
0.0
02 24 26 0.3
3. 0.
0.2
04
0.6 0. 1.0
explanation scores
Figure 8: Histograms of explanation relevance scores for DC-SMGNN TopoFeature (validation set). Since the underlying SMCNN is only looking for the topological motif (as the rule at least two red nodes is learned by the interpretable model), the Dual-Channel GNN is allowed to sparsify all the other edges better, achieving more compact explanations. For seed 1, non-zero scores are clutter around 0.38.
28

---

Beyond Topological Self- Expl-xxplaee GNNS
GSAT
seed
0.3
0.5
soed 3
seed 4
62
54
0.0
density
0.4
5/
0.5
1.0 0.
0.2
0.6
0.6
seed
Seed
seed
seed
62
30 0.0
0.4
06
explanation relevance
Figure 9: Histograms of explanation relevance scores for DC-GSA TopoFeature (validation set).
29

---

Beyond Topological Self- Eeff-xxplai GNNS
Idx: a Class 1
ldd: 1 Class
(b)
Idx: 2 Class 0
ldk: 8 Class
(d)
Figure 10: Examples of explanations for DC-SMGNN (seed 1) over TopoFeature, Relevant edges are those with
Pav 2 0.2 and are highlighted in red. The threshold is picked by looking at the histogram in Fig. 8. Edges are annotated with their respective Pwv score. Overall, DC-DDCCCCCMC SMGNN achieves better sparsification than SMGNN (Fig. 7).
30

---

Beyond Topological Self-Explainable GNNs
GSAT
64
0.
10
0.
0.
0.6
seed
seed
density
5.0
6.
2.4
0.2
10 0.
0.2
0.4
0.6
0.6
1.0
0.
seed
seed 10
explanation relevance scores
Figure 11: Histograms of explanation relevance scores for GSAT on RedBlueNoder (validation set). The model fails to reliably separate between relevant and non-relevant edges, making it difficult to select proper relevance threshold. Specifically, most edges are assigned an importance close to 0.3, which matches the uninformative prior r selected during training.
RedBlueNodes. Fig. 11 and Fig. show the edge relevance scores for GSAT and SMGNN respectively. Overall, the histograms show that both models fail reliably identify relevant subgraph with consistently higher importance than irrelevant ones. Examples of explanations for both models, plotted in Fig. 13 and Fig. 14. confirm that subgraph- based explanations fail to convey actionable insights into what the model is predicting, as no clear pattern emerges from explanations. Conversely, both DC-GSAT and DC-SMGNI provide intelligible prediction by relying on simple linear classifier encoding the ground truth rule number of red nodes 2 blue nodes (see Table and Fig. 3).
AIDS. Among each random seed, seed 8 achieves test Fl score of 1.0, highlighting that the model likely to have learned to just count the number of nodes each graph, and to make the prediction based on such count (Pluska al., 2024). This strategy is proven to be effective in this dataset, as highlighted in Appendix C.5 and Pluska al. (2024). By plotting the histogram of explanatory scores in Fig. 15, and some examples of explanations in Fig. 16, cannot unambiguously assess which rule the model is using for making predictions. Conversely, shown in Appendix C.5, DC-GSAT can achieve the same performances while declaring that only node count statistics are being used for prediction.
31

---

Beyond Topological Self- Eell-Explainable GNNS
SMGNN
soed
seed
seed
5.0
0.2
2.4
56
10 0.0
0.4
0
06
1.0
density
5.6
0.
10 0.
0.
0.6
seed
seed
seed
0.0
0.2
244
0.5
0.3
30 0.0
0.4
0.6
05
1.0
explanation
Figure 12: Histograms of explanation relevance scores for SMGNN on RedBlueNodes ((validation set)). The model assigns very cluttered scores almost all edges, failing highlight subset that is reliably more relevant than the others, making it difficult to select an appropriate threshold for showing the explanations to consumers.
32

---

Beyond Topological Self- Eell-Explainable GNNs
(a)
Figure 13: Examples of explanations for GSAT (seed 1) over RedBlueNodes. Relevant edges are those with Puv 2 0.7 and are highlighted in red. Edges are not annotated with their respective Pus score avoid excessive clutter.
Figure 14: Examples explanations for SMGNN (seed 1) over RedBlueNodes. Relevant edges are those with Puv 2 0.2 and are highlighted in red. Edges are annotated with their respective Puv score avoid excessive clutter.
33

---

Beyond Topological Self- Expl-xxplaee GNNS
GSAT
seed
0.5
seed
seed
0.
density
0.4
1.0 0.0
0.2
0.6
0.
seed
seed
seed
Seed
02
10 0.
0.4
08
explanation relevance
Figure 15: Histograms of explanation relevance scores for GSAT AIDS (validation set).
34

---

Beyond Topological Self- Beff-Explainable GNNs
(b)
Figure 16: Examples of explanations for GSAT (seed 8) over AIDS. Relevant edges are those with Pav 0.8 and highlighted in red. Edges are not annotated with their respective Puv score to avoid excessive clutter.
35

---

Beyond Topological Self-Explainable GNNS
Table 12: Dual-Chrn Channel GNN's s linear classifier weights for the DC-SMGNN experiment in Table 10. The Lı sparsification effectively promotes the model to give considerably higher importance to the last input feature, corresponding to the number of nodes the graph. Seed 10 omitted as the linear classifier is not in use.
Model DC-SMGNN's seed
AIDSC1
Weights
Bias bb [[W]
-6.le-03
-3.2c-02
-9.5c-03
-1.8c-02
-3.8c-04
7.8c-33
-2.4e-04
7.0c-04
5.9c-04
1.4c-03
3.9e-04
1.6e-02
-1.4c-04
1.4-03
-6.9c-04
4.1c-05
-2.6e-02
-7.0c-04
3.1c-04
-9.6c-04
-38c-04
-2.2e-04
3.3e
-3.3e-04
9.7e-04
4.3e-04
1.4e-03
-.6c-05
3.4--04
4.1c-04
3.6c-04
1.16-3
-1.7e.03
1.7e-03
3.4c-04
-2.9-01
-2.c-002
-3.0c402
7.3c-03
-7.3c-04
2.7c-02
-6.5c-04
2.0e-02
4 4.9--0
-9.4c-04
1.2c-02
4.0c.04
.1.4e.04
-2
-3.4e-04
seed
33.e.00
1.1e-03
3.0e-04
9.3e-04
8.4e-06
1e.1e:04
-1.4e
1.3e44
-9.4-004
6.3e-004
3.63
12:57
34
4.5c-04
3.8c-05
8.0c-05
1.6-04
-3,3e-04
1.30004
5.9c-04
-1.2e402
-3.le-02
3.2e-IM
24c-04
3.6e-04
2.4c-03
-1.4c:04
4.4c.04
1.5-06
1.8c-05
0.
2.4e-04
6.5e-04
1.2e.04
-2.ee.04
6.4c404
-3.1e-04
1,0e-03
-38c-03
-1,2e-03
-3.9-00
1.10-33
-5,20044
-600004
-1.1-00
-4.ee405
2.0e044
-3.c-004
-9.2-004
-7.6e-04
-34c-05
5.4e044
6.6e-04
-3.3c-04
-277-011
9.7c-03
8.0e004
48c-03
-3.9c-04
6.0c-05
3.9c-04
-1.1c-03
3.6--04
6.3e-04
-1.7c-03
3.2c-44
-1.0e-03
44c-04
-344-22
7,9c-04
-8.50-04
-60c-04
seed
4.7e044
-2.8-044
99.c-044
-5.90004
-1.0--03
3.42
12.04
1.3e.3
1.5-04
.13e-04
449--0
5.1e
7.9.044
2.5e-05
4.0c444
4.4c.04
-2.8--11
-17e.01
.2.0-01
-1.3e-01
1.2e-04
-..e-114
-1.2c-03
-1,4c-08
-5,7c-04
1.3e.04
-5.2e-04
.3.5e.04
.9.
4.6e-04
6.7e404
3.6e-04
1.0e033
0.
4.0e-044
22.18
4.7e-04
-92e-44
8.1-44
-5.2-004
-19c-06
04
5.2e-04
2.0e.04
4.5e-04
-1.3e-03
5.5c-04
4.2o-04
2.1c-04
8.9c-04
-2.0-011
-.0e.02
1.5e-22
-L1e-43
5.1e-04
8:4e-M
7.4c-04
-822-444
-1.30-03
-8.1c-07
seed 6
-8.c-05
1.3e-03
-L.e-02
3.1c-04
-3.1c-04
6.9c-04
-5.3c-04
27e-44
-9.0c-04
8.7e-04
3.90
15.07
4.1c-04
4.2-04
1.6c-08
-..ee04
9.4e-04
4.4e-04
8.4e-04
6.4e-05
2.4-044
-1.76-04
- -18e-02
-2.7e-02
-5.5c-03
-1.6e-02
4 49c-04
-.3c-003
-5.e-04
-1.1c-03
-6.8-004
-1.6e-04
-1,4-033
9.0e-04
-3.5e-02
2.6e-04
1.3e-03
3.0e-04
053e
.1.0e03
1..0e003
0.5e.04
7.9.004
6.3e-04
1.3e-03
15.1e-04
8.9e-04
.4.e--04
4.6c-04
1.0e033
-6.5e-04
2.9c-01
-1.0e-02
5.0e 04
.12e-003
.3.9-00
7.8c-04
5.8c-D4
9.9c-05
1.2c 04
-233-00
0.3e.04
4.5e.04
7.0e.04
seed 8
5.9-004
-L.e-44
6.5e-04
4.3e-04
7.9--06
3.47
12.18
-388-04
-3.3e-04
-5.5c-04
-1.2c-03
-9,8c005
-70e-05
3.1c-04
-3.4--04
-2.0-00
7.8c-05
-3.5c-M
1 -1.4e.02
.3.1e-02
5.7e-03
221e.222
.2.2e-14
0.5c-03
1.2-044
-2.5c-03
-1,3c-03
-1,8c-04
1.7c-03
2.50-04
-2.7c-02
6.9c-04
2.5c-04
1.10-03
seed
-.1e-04
-9.9-04
1.5e-004
Lle-44
2.4.004
13.73
-9.c-044
-8.2--04
1.6c-04
-3,c-044
-6,3c-04
-1.le-f4
6.4e-04
0.
.1.9e.04
445e-00
2.6e.
36


Reviews:
[{"review_id": "A16QOvXNCW", "reviewer": "Reviewer_oqKU", "summary": "This paper investigates Self-Explainable Graph Neural Networks (SE-GNNs) and their limitations in explanation quality. It formalizes the Trivial Explanations (TEs) generated by SE-GNNs and compares them with Prime Implicant (PI) and faithful explanations. The analysis shows that TEs align with PI explanations in some cases but are generally less informative and misaligned with faithfulness. To address this, the authors propose Dual-Channel GNNs, combining a white-box rule extractor with a standard SE-GNN. Experiments demonstrate that Dual-Channel GNNs can extract concise rules and perform better or on par with existing SE-GNNs.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for taking the time to review our work.  We are glad that you found it well supported by evidence and theoretically sound. We applied the following changes.\n\n**W1: Clarify TEs are a contribution** We revised the Introduction line 16 as follows:\n\n> Focusing on graph classification, we introduce the notion of Trivial Explanations (TEs) as the minimal subgraphs of the input that locally ensure the classifier outputs the target prediction. We then show that some popular SE-GNNs are implicitly optimized for generating TEs.\n\n**W1: TEs and PIs need examples** As an example,  Fig. 1 illustrates the different nuances between TEs, PIs, and faithfulness with a simple example of two different classifiers. We will make this connection clearer in the revised manuscript and bring this example to the forefront of the discussion in the Introduction. We also updated Fig 1’s description to ensure the figure is properly discussed and contextualized. This change could not be reported here due to space constraints.\n\n**W2:** We added a description of the formulas in Table 1. This change could not be reported here due to space constraints\n\n**W3: logical classifiers** In Section 2, different topics are introduced separately since they serve as background material for the main content. We updated the Logical classifiers paragraph as follows to make the context clearer:\n\n> To prove our theoretical results, we will use basic concepts from First Order Logic (FOL) as described in Barcelo and Grohe. [...] For ease of discussion, we fix two FOL classifiers that will be used to provide examples and intuition in the remainder of the paper: [...] \n\n**W3: Sections 3 lack context** We improved the contextualization of our results as follows:\n\nWe added this in line 134 of Section 3:\n\n> Having established a link between SE-GNNs and TEs, we proceed to analyze the formal properties of TEs, starting from the following remark formalizing the notion of *informative explanation*.\n\nWe revised line 142 of Section 3:\n\n> The following theorem, however, shows that TEs can fail to satisfy this desideratum for certain prediction tasks, indicating potential limits in the informativeness of TEs.\n\nWe added this after Thm 3.4:\n\n> Intuitively, this result indicates that there exist two distinct graph classifiers for which TEs are the same for any input, meaning that by inspecting explanations alone, it is not possible to distinguish the two classifiers. Hence, TEs can fail to be informative wrt Remark 3.3\n\n**W4:** We list our modifications below, reporting only the cases where little intuition was provided and omitting the rest due to space constraints.\n\nAfter Thm 3.4:\n\n> This theorem shows cases in which, for two distinct classifiers, TEs match for any input graph, meaning that TEs are not informative for those classifiers wrt Remark 3.3.\n\nLine 132, column 2\n\n> Intuitively, Eq. 3 shows that the insight of Thm 3.4 applies even when aggregating TEs across all instances where the two classifiers yield the same prediction. Hence [...]\n\nAfter Thm 4.4\n\n> Thm 4.4 shows that PIs can overcome TEs' limits in certain tasks. For example, Thm 3.4's classifiers yield identical TEs but differing PIs (see Fig. 1)\n\n**W5: Technical Aspects of SE-GNNs** We added a deeper technical discussion in the Preliminaries and expanded Appx B.2 with more background on SE-GNN and a diagram akin to Fig. 1 in (Miao et al. 2022) showing a prototypical SE-GNN. Sections 4 and 5 remain independent of SE-GNN details, focusing on a theoretical analysis of TEs, PIs, and faithful explanations.\n\n**W5: Improve link between sections** We added the following sentences:\n\nLine 144 Section 4:\n\n> Having established the link between SE-GNNs and TEs in Section 3, in this section, we provide a comparative analysis between TEs and PIs for graph classifiers. [...]\n\nLine 193 in Section 4.1:\n\n> We now show that our previous observation that TEs equal PIs for $\\exists x,y. E(x,y)$ generalizes all existential tasks. This reinforces the use of SE-GNNs in various practical applications and our proposed method (Section 6).\n\nLine 172 Section 4.2:\n\n> Although Section 4.1 shows TEs match PIs for existential tasks, real-world properties like counting cannot be expressed by existential formulas. Here, we show that beyond existential tasks, TEs can be less informative than PIs (Remark 3.3).\n\nLine 202 Section 4.2:\n\n> Thm 4.2  justifies SE-GNNs' performance on many benchmark datasets. However, Thm 3.4 and Thm 4.4 show that SEGNNs may not be informative for certain tasks, motivating an extension of SE-GNNs that preserves their performance on existential tasks but adaptively aids them in other tasks. We will exploit this observation in Section 6.\n\nReplace line 216 of Section 5 with:\n\n> This section reviews a general notion of faithfulness (Azzolin et al., 2024) in Definition 5.1 and shows that faithfulness, TEs (Section 3), and PIs (Section 4) can overlap – in some restricted cases – but are generally misaligned.", "claims_and_evidence": "The authors' claims are mainly threefold:  \n1. In Section 4, they formalize the trivial explanations (TEs) generated by SE-GNNs and compare them with Prime Implicant (PI) and faithful explanations.  \n2. In Section 5, they explore how Trivial Explanations can be unfaithful.  \n3. Based on the analysis and findings, in Section 6, they propose Dual-Channel GNNs, which combine a white-box rule extractor with a standard SE-GNN.\n\nBoth claims 1 and 2 are well-supported with theoretical evidence, while claim 3 is validated through extensive experiments demonstrating its effectiveness.", "methods_and_evaluation_criteria": "This paper focuses on Self-Explainable Graph Neural Networks (SE-GNNs) and aims to better understand the properties and limitations of their explanations. \n\nFirst, in Section 4, the authors formalize the trivial explanations (TEs) generated by SE-GNNs and compare them with Prime Implicant (PI) and faithful explanations. Further, in Section 5, they explore how Trivial Explanations can be unfaithful. These discussions are accompanied by extensive theoretical evidence that addresses the problems described by the authors.\n\nBased on their analysis and findings, in Section 6, the authors propose Dual-Channel GNNs, combining a white-box rule extractor with a standard SE-GNN. A large body of experiments demonstrates the effectiveness of the proposed method.", "theoretical_claims": "This paper is well-supported by theoretical evidence. I have checked all the proofs and did not find any explicit errors.", "experimental_designs_or_analyses": "I believe that both qualitative and quantitative experiments can demonstrate the performance and interpretability of the proposed method in this paper.", "relation_to_broader_scientific_literature": "I believe this paper could advance the interpretability of GNNs, but it is hard to say whether it will have a significant impact. In my view, the author's theory is solid, but the practicality of the proposed Dual-Channel GNNs will require time to be tested.", "essential_references_not_discussed": "It seems that the relevant literature is sufficient.\n\nNote: I am not familiar with this field.", "other_strengths_and_weaknesses": "**Weaknesses or Suggestions:**\n\nI believe the expression of this paper needs further improvement. Although the author's theory and techniques are sufficient, the paper lacks examples and a clear explanation of the domain background, making it difficult for readers unfamiliar with the self-explainable field or newcomers to the field to comprehend. This is particularly evident in the following points:\n\n1. In the second paragraph of the introduction, the author does not clearly express that TEs (Trivial Explanations) are the key concept introduced in this paper. It is only later in the text that we realize this. This confusing logic may leave readers unsure of the relationship between TEs and existing PIs (Prime Implicants) and faithful explanations, leading them to believe that these are parallel categories of methods (perhaps with overlap). Furthermore, these concepts need to be illustrated with examples.\n\n2. The author needs to explain the formulas in Table 1. While most readers are likely familiar with their meanings, there are unknown symbols in the table, and it is hard for us to understand what these symbols represent without further clarification.\n\n3. The logic in Sections 2 and 3 needs improvement, especially in clarifying the motivation behind each concept and theory. For example, in Section 2, the introduction of logical classifiers is abrupt, lacking context and further explanation. Readers may struggle to understand its role and its connection to the paper, leading to confusion. Similar issues appear in Theorems 3.2, 3.4, and Remark 3.3. The author should note that this is not a technical report, and the content should not be simply listed but should follow a logical structure.\n\n4. In the main text, each theory should be clearly explained with non-mathematical descriptions so that readers can understand its purpose and the motivation behind the author's derivations.\n\n5. The author should provide an overview of the technical aspects of self-explainable GNNs, particularly in Sections 4, 5, and 6. This would help tie together the goals of each section. Currently, each section contains a lot of content, but without an overview, it is easy for readers to forget the purpose of each section and how they relate to the overall paper. It might seem like three unrelated technical modules are presented.\n\nI will adjust my score based on the author's response.", "other_comments_or_suggestions": "Please see \"Other Strengths and Weaknesses\".", "questions_for_authors": "Please see \"Other Strengths and Weaknesses\".", "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": "Vyxr7HgD1p", "reviewer": "Reviewer_Mh3n", "summary": "This paper discusses several definitions of Graph explanations and there internal connections. They provide analytical results on the connections between TEs, PIs, sufficient and necessary subgraphs explanations. Because they show that TEs are always less informative than other explanations & directly learning other explanations is not optimal, they construct DC-GNN that finds a middle ground of these two issues.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We are glad they enjoyed reading it and found it well motivated. Below, we address their remarks.\n\n**Computational resources for running DC-GNNs:** We would like to clarify a slight misunderstanding regarding our discussion of computational costs. Our argument mostly pertains to PIs being intractable to extract (Marques-Silva, 2023). In contrast, SE-GNNs aim to extract explanations with a single forward pass of the neural network, resulting in fast and tractable explanations. DC-GNNs, on their side, combine a standard SE-GNNs with a side channel implemented as a linear layer. The resulting complexity is primarily dominated by the SE-GNN-based channel, and the side channel adds negligible computational overhead. Below, we report an analysis of the run time for DC-GNNs compared to existing baselines, which will be integrated into the revised manuscript.\n\n|Graph-SST2|Time per epoch (seconds)|\n|-|-|\n|GSAT| 4.78 +- 0.23 |\n|DC-GSAT| 4.50 +- 0.32 |\n|SMGNN| 6.51 +- 0.37 |\n|DC-SMGNN| 6.32 +- 0.50 |\n\n|BBBP|Time per epoch (seconds)|\n|-|-|\n|GSAT| 0.55 +- 0.18 |\n|DC-GSAT| 0.58 +- 0.18 |\n|SMGNN| 0.53 +- 0.18 |\n|DC-SMGNN| 0.71 +- 0.22 |\n\n**More details about hyper-parameter tuning:**\n\nHyper-parameters were optimized for the performance of the validation split. For datasets with OOD splits, only the ID validation split was used for tuning. We’ll clarify this in Appx. B.2. \n\nWhen choosing the values to test, we followed the standard practice of choosing values within a reasonable range, e.g., powers of $10$ (0.001, 0.01, 0.1, …), or other reasonable choices like $r \\in \\\\{0.3, 0.5, 0.7, 0.9\\\\}$ for GSAT. When performance was satisfactory, we kept the default hyper-parameters of SE-GNN.\n\nWe report below an additional analysis on the robustness to hyper-parameter selection. Given the time constraint in running those experiments, we focus only on representative hyper-parameters for DC-GSAT for the Motif dataset by aggregating values across 5 seeds. We plan to complement those results with the full experimental setting in the final revision of our manuscript.\n\n\n\n\n|(B)LEN hidden size|15|*30*|64|\n|-|-|-|-|\n|DC-GSAT| 92 +- 01 | 93 +- 01 | 93 +- 01 |\n\n|(B)LEN num layers|*2*|3|4|\n|-|-|-|-|\n|DC-GSAT| 93 +- 01 | 93 +- 01 | 93 +- 01 |\n\n|(B)LEN sigmoid temperature|0.1|*0.3*|0.5|\n|-|-|-|-|\n|DC-GSAT| 93 +- 01 | 93 +- 01 | 93 +- 01 |\n\n|GSAT’s $r$ parameter|0.5|*0.7*|0.9|\n|-|-|-|-|\n|DC-GSAT| 90 +- 02 | 93 +- 01 | 93 +- 01 |\n\n\nFor comparison, we report in italic font the original value reported in the paper. The SE-GNN channel was the one selected by the training routine for all the experiments. Overall, results are stable across hyper-parameter choice, except for a small fluctuation when choosing $0.5$ as the parameter $r$ of GSAT. However, for $r \\ge 0.7$, performance stabilizes.", "claims_and_evidence": "The paper draws connections between different subgraph explanations with rigorous proofs. I did not read the proofs fully but have examined the statement and proof sketch, which all look good to me. The second part of the paper focuses on the construction of DC-GNN and they have provided empirical results over 8 datasets.", "methods_and_evaluation_criteria": "This paper is well-motivated and I enjoy reading it much. Their analysis reveals that TEs align with PI explanations for a restricted but significant family of tasks.  However, in general, TEs can be less informative than PI explanations and are misaligned with accepted notions of faithfulness. Although synthetic datasets are easier to control (and we have groundtruth for subgraphs), it would be great to have more discussions and analysis on real-world datasets.", "theoretical_claims": "I have only checked proof sketch and they all look correct and sound to me.", "experimental_designs_or_analyses": "I have checked the setup and they are using widely-used datasets in other literature, and the evaluation metrics are related. A few questions / comments. \n\nThe paper mentions that GNNs, including DC-GNNs, can be computationally expensive. However, it does not provide a detailed analysis of the computational complexity or scalability of their approach. It would be beneficial to have a more thorough evaluation of the computational resources required by DC-GNNs, so we have a better sense if this can scale.", "relation_to_broader_scientific_literature": "The analytical parts has bridged several different metrics in generating subgraph explanations. This paper provides a clear answer to what subgraph explanations are important and in what sense.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "One significant contribution is to analyze the information gain from using a simple TE subgraph, or more complicated PI and faithful subgraphs. The authors show that TE significantly contains less information despite of its simplicity and sometimes it is very unfaithful.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Could you provide more details on the hyperparameter tuning process for DC-GNNs? How sensitive is the model's performance to different hyperparameter settings, and what steps have you taken to ensure the robustness of your results across a reasonable range of parameter values?", "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": "MoSgw6LoFq", "reviewer": "Reviewer_3Jwx", "summary": "This paper investigates the properties and limitations of explanations generated by Self-Explainable Graph Neural Networks (SE-GNNs). The authors formalize SE-GNN explanations as Trivial Explanations (TEs) and compare them to Prime Implicant (PI) and faithful explanations. They find that TEs, while effective for motif-based tasks, can be less informative and misaligned with a common definition of faithfulness in general graph classification. The paper highlights that TEs match PI explanations in motif-based prediction tasks when the presence or absence of one particular motif has a causal relationship with the class label. The authors proceed to propose Dual-Channel GNNs (DC-GNNs), which combine SE-GNNs with non-relational predictors, to improve explanation compactness and performance. DC-GNNs adaptively employ both channels, allowing the SE-GNN to focus on topological motifs. Experiments on synthetic and real-world datasets show that DC-GNNs perform competitively with SE-GNNs, often with more succinct rules. The study reveals that TEs can be ambiguous and unfaithful, limiting their utility in certain applications. Overall, the research formally analyzes SE-GNN explanations and introduces a novel architecture to address their shortcomings. The findings suggest that integrating non-topological information enhances the quality and interpretability of GNN explanations.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their feedback. We are glad they found our analysis of interest to the community. Below, we address their remarks.\n\n**Not all SE-GNNs are restricted to TEs:** We highlighted multiple times that our focus is on SE-GNNs with the losses of Table 1 (Line 57 in Preliminaries, Statement of Thm 3.2, Limitations). Overall, the losses in Table 1 capture the notion of  “small, label-preserving explanations” in a relatively general fashion, offering insights into a wide SE-GNN family. Nonetheless, we appreciate the reviewers’ feedback, and we will clarify that our results pertain to a subset of all SE-GNNs also in the Abstract, Introduction, and Conclusions. \n\n**Rethink the term Trivial Explanation:** This paper aims to formalize SE-GNN explanation semantics, and the term 'Trivial Explanation' was meant to highlight simplicity, not negativity. On further reflection, we agree that “Trivial” may imply a bias. Therefore, we will rephrase it as 'Minimum Explanations' in the manuscript.\n\n**DC-GNN may overfit node features:** Note that SE-GNNs are considerably more expressive than our sparse side channel, therefore, it is much more likely that a standard SE-GNN will overfit to (potentially harmful) topological patterns rather than the side channel overfitting to node features [1]. Nonetheless, in DC-GNNs, both channels are jointly trained to maximize accuracy, and experiments show they balance well for generalization.\n\n[1] Graph Neural Networks Use Graphs When They Shouldn't\n\n**Add baselines beyond Table 1:** Following also the suggestion of rev. rjdA, we opted to include as a new baseline beyond Table 1, the model of Wu et al. 2020. Given the time and space constraints, we report the results for a subset of the datasets, leaving the full set of results to the revised manuscript.\n\n|BAColor|Accuracy|Channel|\n|-|-|-|\n|DIR| 98 +- 01 ||\n|DC-DIR| 98 +- 01 |Rule|\n\n|AIDS|Accuracy|Channel|\n|-|-|-|\n|DIR| 96 +- 03 ||\n|DC-DIR| 96 +- 03 |Rule|\n\n|BBBP|AUC|Channel|\n|-|-|-|\n|DIR| 64 +- 02 ||\n|DC-DIR| 65 +- 02 |Topo*|\n\n|MUTAG_0|Accuracy|Channel|\n|-|-|-|\n|see below|||\n\nWhere “*” has the same meaning as is Table 3. Overall, these results are in line with those of other SE-GNNs, showing the generality of our proposal.\n\n**Add existing benchmarks:** We performed new experiments on MUTAG_0. The results are as follows:\n\n|MUTAG_0|Accuracy|Channel|\n|-|-|-|\n|GIN| 99 +- 1 ||\n|GSAT| 99 +- 1 ||\n|DC-GSAT| 99 +- 1 |Topo|\n|SMGNN| 99 +- 3 ||\n|DC-SMGNN| 98 +- 4 |Topo*|\n|GiSST| 99 +- 1 ||\n|DC-GiSST| 99 +- 1 |Topo|\n|DIR| 98 +- 2 ||\n|DC-DIR| 98 +- 2 |Topo|\n\nModel accuracy increases wrt the original MUTAG dataset, as expected (Serra & Niepert, 2022). Also, DC-GNNs prefer the topological channel as in MUTAG, and they match the performances of SE-GNNs. For BA-2MOTIFS, see **Q1**.\n\n**Show more critical distance to faithfulness:** Indeed, we show that explanations extracted by SE-GNNs can be misaligned wrt faithfulness metrics (Thm 5.2).  Whether those metrics are problematic in general is an interesting question beyond the scope of our work. We’ll add a sentence in Section 5 pointing to this issue.\n\n**Q1:** We opted for the Motif dataset in our experiments as, despite being designed with the same goal as BA-2MOTIFS, it is more challenging: it has three classes with three distinct motifs instead of two; it has more samples; and it comes with OOD splits.\n\n**Q2:** Our DC-GNNs are different from feature attribution methods in the form of the explanation they highlight. Feature attribution methods simply highlight the node features more relevant for prediction, whereas our DC-GNN can provide rules. In this sense, feature attribution methods cannot go “beyond” topological explanations, as the explanation would remain a subgraph with refined node features.\n\nLet us consider as an example RedBlueNodes, where graphs are of class 0 when they contain more red than blue nodes, encoded as one-hot vectors. There, a TE for an instance of class 0 contains a single red node, as it is the minimal subgraph allowing the SE-GNN to make the correct prediction. Then, running a feature attribution method can only highlight that the only relevant feature is the one related to the red color and that other features are irrelevant. However, this cannot give insight into the multiplicity of red vs blue nodes. Conversely, our DC-GNNs provide the rule *Red$\\ge$Blue* as the explanation, which is more aligned with human expectations.\n\n\n**Q3:** Our theoretical analysis delineates tasks that are suitable and unsuitable for SE-GNNs and shows that simply aiming for alternative notions of explanations (like PI and faithfulness) can lead to large explanations and high computational complexity. \nGiven these observations, a natural choice is to augment SE-GNNs with alternative modalities of explanations taking care of SE-GNNs’ limitations — and we believe DC-GNNs are a well-motivated step in this direction. We will clarify this link in the revised Abstract and Introduction.", "claims_and_evidence": "The paper makes the following claims:\n\n(1) Formal characterization of the class of explanations SEGNNs optimize for, namely \"trivial explanations\" (TEs). \nEvidence: the evidence is not convincing, and this is an overclaim. The above claim only holds for the loss functions given in Table 1. Several SE-GNNs do not use these losses. Or they use these losses but with more sophisticated subgraph extraction methods. \n\n(2) Formal comparison of TEs, PIs, and faithful explanations. \nEvidence: this is done well and relates these different classes of explanations to each other. In my opinion, this is the main contribution of the paper. \n\n(3) DC-GNNs are proposed as an alternative to existing SE-GNNs. They are claimed to be better empirically. \nEvidence: The evidence here is empirical and weak, also because specific benchmarks are not used in the paper.", "methods_and_evaluation_criteria": "The paper proposes a new class of models (DC-GNN) compared empirically to some existing SE-GNNs. The authors also investigate some properties of the new class, such as how well the model can indicate which type of features it uses (topological or feature-based).", "theoretical_claims": "The paper provides theoretical results—one theorem connecting SE-GNNs with specific loss functions to TEs. \nMoreover, several theorems compare TEs, PIs, and faithfulness measures. The theoretical results are correct. However, some parts of the paper overclaim the implications of some of these theorems. The theory does not support the claim that all SE-GNNs are restricted to TEs.", "experimental_designs_or_analyses": "The experimental design seems sound. However, comparing the models using common topological benchmarks such as BA-2MOTIFS and MUTAG_0 would be better. A worry about the proposed DC-GNN model is that it will overfit or latch on to node features (through the second channel) and, therefore, have more difficulty finding the topological features.", "relation_to_broader_scientific_literature": "A substantial contribution of the paper is the theoretical comparison of TEs, PIs, and faithfulness measures. This has not been done before and brings interesting insights into the otherwise mostly empirically driven research direction of explainable GNNs. The paper is therefore of interest to a XAI for GNN  subcommunity and well integrated into the literature.", "essential_references_not_discussed": "None.", "other_strengths_and_weaknesses": "The paper consists of three parts, each with its own contribution. \n\nFirst, the connection between SE-GNNs and TEs. This is an interesting result but it should be clarified that Theorem 3.2 does not generally hold for all SE-GNNs. Even in the statement of the theorem, this can be easily overlooked. Other than the imprecise claims made in the paper‘s language, the theoretical results are  a strength of the paper. \n\nI have a bit of a problem with the term \"trivial explanation,\" as it might lead people to associate these explanations with \"useless\" or \"uninteresting\" explanations. This is, of course, not the case. In general, the paper has a negative tone about what they call TEs throughout the first part of the paper, showing that TEs have undesirable properties (from their point of view) compared to PIs and faithfulness measures. However, before introducing their own method, they completely change course, saying that TEs are often the preferable topological explanations (because faithful and PIs might grow very large and unhelpful for many graph problems) and then introducing a model that augments TEs with feature-based explanations.  Therefore, the first (theoretical) and the second (empirical) parts are somewhat disconnected. \n\nThe empirical evaluation is sound but misses several benchmark datasets, such as BA-2MOTIFS. It is strange since their proposed method is a SE-GNN with an additional feature-based explanation channel. It would also be good to compare to existing methods such as https://link.springer.com/article/10.1007/s10994-024-06576-1. Here, I assume that the method (which also incorporates features) would extract the topological motif and connect nodes whose features are important via edges to this topology. The method is also not one that falls into Table 1.", "other_comments_or_suggestions": "Please rethink the term \"trivial explanation.\" As you wrote in the paper, they are often preferable, and indeed, your proposed method also attempts to extract them. They can be very complex. Indeed, in some cases finding a specific topological motif is an NP-hard problem. \n\nYou also contrast TEs with the \"measures\" of faithfulness which have their own problems.\n\nSo, the authors might want to show more critical distance to these (rather arbitrary) notions of faithfulness and what a good explanation is when writing the paper. \n\nPlease also consider, as written before, running experiments on existing benchmarks and using methods that do not follow the loss functions given in Table 1.", "questions_for_authors": "- Why did you not use datasets such as BA-2MOTIFS?\n- How is your method better than a SE-GNN that extracts a subgraph, and on top of which, you can run a feature attribution method?\n- How does your theoretical analysis (part 1 of the paper) fit to your proposed method? Why are these two parts in the same paper?", "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": "qlkUEMGw42", "reviewer": "Reviewer_rjdA", "summary": "In this paper, the authors argue that existing SE-GNNs generate Trivial Explanations and advocate for designing GNN explanation methods capable of producing Prime Implicant and faithful explanations. After conducting theoretical analysis, they propose DC-GNNs, a dual-channel model that incorporates a non-topological rule extractor. They evaluate their method on several datasets and conclude that DC-GNNs perform on par with or better than standard SE-GNNs.\n\n## update after rebuttal\n\nThe rebuttal clarified key concepts I had misunderstood in my initial review. Therefore, I have raised my score from weak reject (2) to accept (4).", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the feedback. See our comments below.\n\n**Summary clarification:** We are *not* advocating for extracting PI explanations from SE-GNNs. As per the Abstract and Sec 6 (line 244), PIs can be intractable to compute and as large as the input. Our analysis is not meant as criticism. In fact, we advocate for enhancing SE-GNNs rather than replacing them.\n\nWe renamed “Trivial Explanation” to “Minimum Explanations”, which sounds less negative.\n\n**Theory-practice gap:** Thm 3.2 does not guarantee that SE-GNNs always achieve TEs in practice, but it shows TEs are necessary and sufficient for minimal true risk *assuming perfect predictive accuracy* for any $\\lambda>0$. Optimization may not reach this solution, as also discussed in 666-673 Appx A.1. Still, the result remains impactful: even if Thm 3.2’s conditions are not met, SE-GNNs in Table 1 optimize for small (ideally the smallest) label-preserving subgraphs and our theoretical analysis applies identically, as such explanations are still neither PI nor faithful in general. Figure 3 of GSAT supports the analysis above: TEs for that task would comprise 3 houses, and GSAT indeed highlights 3 houses with only a few additional edges.\n\n**Method-theory gap:** Our analysis provides a formal argument for using (and enhancing) subgraph-based explanations, and it directly informs the design of DC-GNNs.\n\n**DC-GNNs & PI:** DC-GNNs are not designed to output PIs but to leverage SE-GNN strengths in existential tasks, combined with an interpretable model for non-existential properties\n\n**Datasets not related to FOL:** Synthetic datasets are tightly linked to FOL. TopoFeature matches the formula $\\exists a,b,c,d. Cycle(a,b,c,d) \\land \\exists^{\\ge 2}x.Red(x)$. Motif follows a similar structure, while RedBlueNodes is an instance of FOL to counting quantifiers. \n\nFigure 1 is an illustration to provide intuition.\n\n**Why a single edge is a TE for $g′$?** $g′(G)$ checks for the existence of an edge for each node. Thus, a subgraph consisting of only one edge (seen alone) indeed satisfies this constraint. We will clarify.\n\n**Mostly assess accuracy:** We also evaluate DC-GNNs by measuring faithfulness and rule quality by testing how well they generalize OOD (Table 4), their dependability (Table 2), and their conciseness (C.4). Plausibility is unsuitable, as the ground-truth explanation is either unknown or not a pure subgraph, a problem for all models beyond subgraph explanations (Bechler-Speicher et al. 2024; Pluska et al. 2024).\n\n**Datasets are biased for colors:** The synthetic datasets are explicitly designed to test DC-GNN's ability to decompose the task between the two channels. To showcase its generality, we also test it on standard benchmarks where color information is not present.\n\n**Hyperparams choice:** We verified that using $r \\in \\\\{0.5,0.7\\\\}$ for GSAT doesn’t change our results, which will be added in the revision. GIN performs better with a hidden size of 300, aligning with Gui et al. 2022. Keeping this value fixed ensures fair comparison across our experiments.\n\n**Limited baselines:** We added Wu et al. (2020) as a new baseline. Please refer to the answer to 3Jwx for the results.\n\n**Prior works also consider node features:** Including node feature relevance in topological explanations is not the same as extending them with rules:\n\n*Example*: for a model trained on RedBlueNodes, GNNExplainer and CAL will highlight individual nodes' color features. DC-GNNs, instead, will return the formula *Red $\\ge$ Blue*, which is far more compact and intelligible.\n\n**Misleading experiments:** In real-world tasks, performance drops only 1% AUC for BBBP, which is within std dev. Elsewhere, DC-GNNs match or exceed baselines.\n\nFor OOD2 in Motif, the drop likely stems from OOD performance instability in models without OOD regularization (Section 7, A1) and not the unused side channel (Table 2), as shown by the higher std dev.\n\n**Fig. 1:** It shows a positive instance G composed of a 3-clique for both formulas. Solid (resp. dashed) edges belong (resp. do not belong) to the explanation depicted in each column. We will clarify the caption.\n\n**Faithfulness is inappropriate:** We follow previous work computing SUF and NEC by feeding G and G’ into the full model, including the explanation extractor. Thus, the classifier evaluates $R'=q(G’)$, not $G’$, alleviating the OOD issue. Whether those metrics are suboptimal for SE-GNNs is beyond the scope of our contribution.\n\n**Q1:** SE-GNNs are bound to explain non-topological patterns by subgraphs, which can be ambiguous.. E.g., in Figure 2 the SE-GNN highlights the red nodes by marking their incident edges, and it’s unclear if what matters are the edges, the nodes, their multiplicity, etc.\n\n**Q2:** One can understand which (few) features are most responsible for a prediction and extract rules from them (see Appx B.3) without resorting to post-hoc methods.\n\n**Q3:** It’s the integer value of standard dev.\n\n**Q4:** Accuracy. We will clarify this.", "claims_and_evidence": "Theorem 3.2 suggests that existing SE-GNNs provide only Trivial Explanations. While this is theoretically correct, it does not always hold in practice: (1) As shown in Figure 3 of GSAT, existing SE-GNNs identify all important edges rather than strictly minimal explanations. (2) In multi-loss optimization, the hyperparameter $\\lambda$ used to constrain $R$ is typically small (to maintain stable training and ensure predictive accuracy). Consequently, the model may retain more edges to preserve predictive performance, even at the cost of some conciseness (cf. Figure 10 of GSAT). Considering that the critique of existing SE-GNNs throughout this work is primarily based on Theorem 3.2, a significant discrepancy between theory and practice would undermine the impact of this paper.", "methods_and_evaluation_criteria": "- Gap between method and theoretical analysis: From my perspective, the proposed method does not appear to have a strong connection to its theoretical analysis. While building on existing work, DC-GNNs incorporate a non-topological perspective by analyzing node features. In other words, DC-GNNs perform better on certain types of datasets, but there is no evidence that they can generate PI explanations.\n- Gap between benchmark datasets and theoretical analysis: The dataset used by the authors seems unrelated to the theoretical analysis. None of the datasets have a strong connection to FOL and Figure 1, creating a significant gap between the theoretical analysis and the experimental evaluation.", "theoretical_claims": "Based on the provided proof sketch, Theorem 3.2 is correct. However, starting from Theorem 3.4, I can't understand why a single $e \\in E$ can be a Trivial Explanation for $g^{\\prime}(G)$, which prevents me from checking the correctness of the subsequent proofs.", "experimental_designs_or_analyses": "- Limited metrics: This paper focuses on GNN explanation, yet the primary evaluation metrics only assess predictive accuracy. A more comprehensive comparison between DC-GNNs and SE-GNNs appears only in Appendix C.3, and even there, it is limited to just two synthetic datasets. \n\n- Unfair experimental settings: The authors introduce two new datasets, RedBlueNodes and TopoFeature, where labels are constructed using additional color information. However, the design of DC-GNNs inherently biases the model towards discovering color information, leading to an unfair comparison.\n\n- Inappropriate parameter choices: According to the GSAT authors’ recommendations, the parameter r should be set to $r \\geq 0.5$. However, the authors set  $r=0.3$ for RedBlueNodes (line 910), deviating from the guideline. Additionally, in GSAT, the hidden size of GIN for the Graph-SST2 dataset is 64, whereas the authors set it to 300, which may introduce inconsistencies in comparison. \n\n- Limited baselines: The baseline selection is quite limited, as the authors include only two baselines, one of which is a 2020 ArXiv paper with just 15 citations. Given that the paper extensively discusses sufficiency and necessity, it would be more appropriate to include causal-based baselines for comparison. For instance, Wu et al. (2020) is cited (line 300), so it would be reasonable to compare against it. Furthermore, DC-GNNs incorporate node features, yet multiple prior works also consider this aspect, such as GNNExplainer [1] and CAL [2]. So, comparing DC-GNNs with these methods might be a good way to verify the effectiveness of DC-GNNs.\n\n- Misleading experimental analysis: On real-world datasets, the advantage of DC-GNNs is limited and can sometimes even lead to a decline in performance. However, the authors claim that DC-GNNs perform on par with or better than plain SE-GNNs. Additionally, in Table 4, the authors state that DC-GNNs generalize better to OOD than plain SE-GNNs. However, on Motif OOD_2, DC-GNNs exhibit significantly worse performance compared to plain SE-GNNs.\n\n[1] GNNExplainer: Generating Explanations for Graph Neural Networks, NeurIPS 2019\n\n[2] Causal Attention for Interpretable and Generalizable Graph Classification, KDD 2022", "relation_to_broader_scientific_literature": "Investigating GNN explanations is crucial for expanding the applicability of GNNs in high-stakes scenarios.", "essential_references_not_discussed": "I think the paper is original as I have not seen anything like it before.", "other_strengths_and_weaknesses": "I appreciate the authors’ effort in writing such a comprehensive paper -- it is the longest paper in my batch and the one I spent the most time reviewing. I am worried that I misunderstood some parts. If the authors can address my concerns during the rebuttal phase, I would be open to reconsidering and potentially increasing my score.", "other_comments_or_suggestions": "- I suggest that the authors provide more details about Figure 1, as it is crucial for readers to fully understand the paper. I would appreciate it if the authors could clarify the meanings of the solid and dashed lines in Figure 1, illustrate what the raw graphs $G$ looks like, and specify whether the two cases presented in the figure correspond to positive or negative samples.\n- I see that the authors use faithfulness to evaluate the effectiveness of self-interpretable GNNs (e.g., GSAT). However, I think this is inappropriate because, according to Eqs. 7 and 8, Suf(R) and Nec(R) are computed based on $\\Delta(G, G^{\\prime})$ . These metrics are suitable for post-hoc GNN explanation methods, which are trained to align with the predictive results of the original graph $G$. However, self-interpretable GNNs are trained to make accurate predictions when $R$ is provided as input and do not need to align with the predictions of $G$. As a result, using Eqs. 7 and 8 to assess the effectiveness of self-interpretable GNNs suffers from a distribution shift problem. That said, I remain open-minded on this issue, as I am aware that none of the recent works have identified this problem.", "questions_for_authors": "- In Figure 2, why do SE-GNNs fail to capture non-topological patterns? Some SE-GNNs use node features to determine edge weights, which suggests that they might have the potential to discover non-topological patterns.\n- If the white-box rule extractor (line 30) is a sparse linear model, why can it be described as white-box? \n- What does ± mean in all tables? Is the number after ± at the decimal level or the integer level? \n- Which metrics did you use in Table 4?", "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": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: This paper offers a formal and insightful investigation into the explanatory capacity of Self-Explainable Graph Neural Networks (SE-GNNs), introducing the notion of Minimum Explanations and analyzing their relationship with Prime Implicant and faithful explanations. It further proposes Dual-Channel GNNs (DC-GNNs) as a practical solution to some of the theoretical limitations identified. The theoretical contributions are rigorous and well-motivated, and the empirical evaluation, while focused, provides evidence of the method’s effectiveness. The final scores reflect consensus toward acceptance, with three reviewers recommending acceptance and one leaning toward acceptance. I recommend acceptance.
Decision: Accept (poster)