Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspective

Thank you for the feedback. See our comments below.

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.

We renamed “Trivial Explanation” to “Minimum Explanations”, which sounds less negative.

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.

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.

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

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.

Figure 1 is an illustration to provide intuition.

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.

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).

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.

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.

Limited baselines: We added Wu et al. (2020) as a new baseline. Please refer to the answer to 3Jwx for the results.

Prior works also consider node features: Including node feature relevance in topological explanations is not the same as extending them with rules:

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.

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.

For 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.

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.

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.

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.

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.

Q3: It’s the integer value of standard dev.

Q4: Accuracy. We will clarify this.

We thank the reviewer for their feedback. We are glad they found our analysis of interest to the community. Below, we address their remarks.

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.

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.

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.

[1] Graph Neural Networks Use Graphs When They Shouldn't

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.

Where “*” 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.

Add existing benchmarks: We performed new experiments on MUTAG_0. The results are as follows:

Model 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.

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.

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.

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.

Let 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.

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. Given 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.

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.

W1: Clarify TEs are a contribution We revised the Introduction line 16 as follows:

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.

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.

W2: We added a description of the formulas in Table 1. This change could not be reported here due to space constraints

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:

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: [...]

W3: Sections 3 lack context We improved the contextualization of our results as follows:

We added this in line 134 of Section 3:

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.

We revised line 142 of Section 3:

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.

We added this after Thm 3.4:

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

W4: We list our modifications below, reporting only the cases where little intuition was provided and omitting the rest due to space constraints.

After Thm 3.4:

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.

Line 132, column 2

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 [...]

After Thm 4.4

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)

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.

W5: Improve link between sections We added the following sentences:

Line 144 Section 4:

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. [...]

Line 193 in Section 4.1:

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).

Line 172 Section 4.2:

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).

Line 202 Section 4.2:

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.

Replace line 216 of Section 5 with:

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.

We thank the reviewer for their feedback. We are glad they enjoyed reading it and found it well motivated. Below, we address their remarks.

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.

More details about hyper-parameter tuning:

Hyper-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.

When 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.

We 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.

For 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.