From Abductive Explanations to Global Logical Rules for Node Classification in SGCs

# From Abductive Explanations to Global Logical Rules for Node Classification in SGCs
Source: [https://arxiv.org/html/2608.17103](https://arxiv.org/html/2608.17103)
###### Abstract

Graph Neural Networks \(GNNs\) have achieved remarkable performance in node classification tasks, motivating growing interest in methods capable of explaining their predictions\. Recent logic\-based approaches, such as LogicXGNN, derive global logical rules for Graph Neural Networks \(GNNs\) from collections of explanatory subgraphs\. While informative, these subgraphs may contain redundant structural information that is specific to individual nodes, potentially limiting the generality of the extracted rules\. In this work, we propose a logic\-based framework for node classification in Simple Graph Convolution \(SGC\) networks that uses minimal abductive explanations as an intermediate representation for rule extraction\. For each node, we compute a minimal set of node\-feature pairs sufficient to preserve the predicted class\. These explanations are then used to train decision trees from which global logical rules are extracted\. Experiments on benchmark datasets show that the proposed framework produces compact global rules while maintaining high fidelity to the original SGC model\.

## 1Introduction

Graph Neural Networks \(GNNs\) have become the standard tool for node classification on attributed graphs, with applications ranging from document categorization in citation networks to entity classification in knowledge graphs\[[6](https://arxiv.org/html/2608.17103#bib.bib2),[4](https://arxiv.org/html/2608.17103#bib.bib10)\]\. As these models inform decisions in scientific and operational pipelines, explaining individual node predictions and characterising overall model behaviour has become a central concern\. Recent surveys organise this literature along two axes: instance\-level methods, which explain individual predictions, and model\-level methods, which characterise global behaviour\[[13](https://arxiv.org/html/2608.17103#bib.bib6)\]\.

A recent line of work approaches this problem through symbolic logic\. Methods such as LogicXGNN\[[3](https://arxiv.org/html/2608.17103#bib.bib1)\]derive global logical rules for GNNs by characterizing each node through two complementary predicates\. The first is a structural component, obtained from a Weisfeiler–Lehman hash of the node’s local multi\-hop receptive field\. The second is an embedding component, obtained by binarizing a small set of informative dimensions of the learned node representation against thresholds; the dimensions and thresholds are selected by a decision tree fit on the graph\-level mean\-pooled embeddings against the model’s predictions\. Correctly classified instances are then encoded as binary vectors over these predicates, and a decision tree trained against the model’s prediction distills a per\-class set of logical rules, each a disjunction of conjunctions of predicates\. A follow\-up grounding step links each predicate back to the input by collecting representative subgraphs, namely the local neighborhoods of nodes that activate it; a per\-predicate decision tree is then fitted over a canonical, structure\-aware concatenation of the node features within those subgraphs, yielding grounding rules that connect predicates to input features\. However, the main exposition and experiments of this line target graph classification, with reported baselines such as GLGExplainer and GraphTrail\[[2](https://arxiv.org/html/2608.17103#bib.bib5),[1](https://arxiv.org/html/2608.17103#bib.bib4)\]evaluated in the same setting\. LogicXGNN sketches an extension to node\-level tasks but does not develop or evaluate it\. As a consequence, rule\-based global explanation for node classification remains comparatively underexplored, and the predicates used by this family carry no formal sufficiency guarantee at the node level\.

Simple Graph Convolution \(SGC\)\[[12](https://arxiv.org/html/2608.17103#bib.bib12)\]is a natural target for rule\-based explanation in this setting\. SGC matches the performance of GCN and other state\-of\-the\-art graph neural networks on standard node classification benchmarks despite removing the nonlinearities between message\-passing layers and collapsing the resulting transformations into a single linear classifier applied to a fixed feature propagation\. The logits of an SGC are therefore a linear function of node features\. This property has been used by recent work that distils a nonlinear GNN into an SGC and extracts node\-level explanations from it rather than from the original model\[[10](https://arxiv.org/html/2608.17103#bib.bib9),[11](https://arxiv.org/html/2608.17103#bib.bib7)\]; by analogy, explanation pipelines built around SGC can in principle be applied to other node\-classification GNNs by first composing with a distillation step, at the cost of an additional approximation\.

A parallel line of work uses abductive explanations \(AXps\)\[[5](https://arxiv.org/html/2608.17103#bib.bib13),[9](https://arxiv.org/html/2608.17103#bib.bib8)\]\. An AXp is a minimal subset of input feature assignments that, together with the model, entails the predicted class: once this subset is fixed, the model’s output does not change regardless of the remaining inputs\. AXps therefore provide a formal sufficiency and irredundancy guarantee for the prediction, and, for classifiers that are linear in the inputs being explained, an AXp can be computed in polynomial time rather than via combinatorial search\[[8](https://arxiv.org/html/2608.17103#bib.bib11)\]\. However, these methods have not been directly applied to GNNs\.

To address the limitations of these previous lines of work, we propose AXSGC\(Abduction\-based Explanations for SGC\), a logic\-based method for node classification in SGCs\. For each node, we extract an AXp at the node\-feature level from the SGC classifier and use these AXps as the intermediate representation from which global rules are derived\. Rule extraction is applied to the set of node\-feature pairs that determine each node’s prediction, whose irredundancy is guaranteed by the AXp formulation\. We compute these AXps in polynomial time by exploiting the linearity of the SGC score\.

Overall, our method operates in three stages\. First, for each node, we compute a subset of node\-feature pairs that by itself is sufficient to fix the SGC prediction\. Second, the resulting sets are encoded as vectors over distance\-indexed predicates of the form ”feature of a node at a given hop distance from the target node”, which abstract away the identity of the contributing neighbor while preserving its distance from the target node\. These vectors, paired with the SGC prediction as a label, are used to train a decision tree from whose paths the per\-class rules are read off\. Third, global logical rules are read directly from the root\-to\-leaf paths of the trees, with each leaf labelled by the class it predicts and each path read as a conjunction of distance\-indexed predicates\.

Each AXp therefore acts as a bridge between the local and global stages: it is the Node\-feature AXp \(NF\-AXp\) returned for an individual node, and at the same time the input from which the global per\-class rules are induced\.

We evaluate AXSGC on benchmark node classification datasets and report intrinsic fidelity to the SGC model alongside LogicXGNN\[[3](https://arxiv.org/html/2608.17103#bib.bib1)\]as a representative recent rule\-based global explanation method for GNNs\. Our experiments report the size of AXps, the size of the resulting per\-class rules, and the intrinsic fidelity of the rules to the SGC model across the benchmarks considered\. Across these benchmarks, our method achieves fidelity to the SGC up to 30\.2% over LogicXGNN and extracting up to 83\.8% fewer rules\.

## 2Preliminaries

This section fixes the notation used in the remainder of the paper\. We first recall the SGC classifier and isolate the property that makes it amenable to formal explanation\. We then recall the abstract notion of abductive explanation from formal explainability, which serves as the conceptual foundation for the method developed in the next section\.

### 2\.1Simple Graph Convolution

LetG=\(V,E\)G=\(V,E\)be an undirected graph withn=\|V\|n=\|V\|nodes, adjacency matrixA∈\{0,1\}n×nA\\in\\\{0,1\\\}^\{n\\times n\}, and node\-feature matrix𝐗∈ℝn×d\\mathbf\{X\}\\in\\mathbb\{R\}^\{n\\times d\}, whereddis the number of node features andXu,jX\_\{u,j\}is the value of featurejjat nodeuu\. In most datasets considered in this work, node attributes are represented as binary bag\-of\-words vectors\. Hence,Xu,j∈\{0,1\}X\_\{u,j\}\\in\\\{0,1\\\}, whereXu,j=1X\_\{u,j\}=1indicates that termjjoccurs in the document associated with nodeuu, andXu,j=0X\_\{u,j\}=0indicates its absence\. Then, throughout the paper, we assume Boolean node features\. LetI∈ℝn×nI\\in\\mathbb\{R\}^\{n\\times n\}be the identity matrix\. The augmented adjacencyA\+IA\+Iadds a self\-loop to every node, so each node aggregates its own features alongside those of its neighbours\. LetD~\\tilde\{D\}be the diagonal degree matrix ofA\+IA\+I, withD~i​i=∑k=1n\(A\+I\)i​k\\tilde\{D\}\_\{ii\}=\\sum\_\{k=1\}^\{n\}\(A\+I\)\_\{ik\}, whereD~i​i\\tilde\{D\}\_\{ii\}is the degree of nodeiiin the augmented graph\. The symmetric normalisation byD~−1/2\\tilde\{D\}^\{\-1/2\}on both sides bounds the spectrum of the propagation operator, defined as

A^=D~−1/2\(A\+I\)D~−1/2\.\\hat\{A\}\\;=\\;\\tilde\{D\}^\{\-1/2\}\\,\(A\+I\)\\,\\tilde\{D\}^\{\-1/2\}\.\(1\)The entryA^v,u\\hat\{A\}\_\{v,u\}encodes the one\-step weighted influence of nodeuuon nodevvafter self\-loop augmentation and symmetric normalisation\.

LetΘ∈ℝd×C\\Theta\\in\\mathbb\{R\}^\{d\\times C\}be the learned weight matrix, whereCCis the number of classes and each columnΘ:,c∈ℝd\\Theta\_\{:,c\}\\in\\mathbb\{R\}^\{d\}is the linear classifier for classcc, withΘj,c\\Theta\_\{j,c\}the weight assigned to featurejjwhen scoring classcc\. LetK∈ℕK\\in\\mathbb\{N\}be the number of times feature propagation is applied;KKplays the same role as the number of message\-passing layers in a GCN, controlling how far information can travel before classification\. The score matrix is given by

Y^=softmax⁡\(A^K​𝐗​Θ\),\\hat\{Y\}\\;=\\;\\mathrm\{softmax\}\\bigl\(\\hat\{A\}^\{K\}\\,\\mathbf\{X\}\\,\\Theta\\bigr\),\(2\)with row\-wise softmax, where rowvvofY^\\hat\{Y\}is the predicted class distribution at nodevv\. The predicted class of nodevvis

c∗​\(v\)=arg⁡maxc∈\{1,…,C\}⁡\(A^K​𝐗​Θ\)v,c,c^\{\*\}\(v\)\\;=\\;\\arg\\max\_\{c\\in\\\{1,\\dots,C\\\}\}\\bigl\(\\hat\{A\}^\{K\}\\,\\mathbf\{X\}\\,\\Theta\\bigr\)\_\{v,c\},\(3\)wherec∗​\(v\)c^\{\*\}\(v\)is the class SGC assigns to nodevv\.

### 2\.2Abductive Explanations

An abductive explanation \(AXp\)\[[5](https://arxiv.org/html/2608.17103#bib.bib13),[9](https://arxiv.org/html/2608.17103#bib.bib8)\]is a minimal set of input assignments whose values determine the model’s prediction\.

###### Definition 1\(Abductive explanation\)\.

Letϕ:𝒳→𝒴\\phi:\\mathcal\{X\}\\to\\mathcal\{Y\}be a classifier whose feature space factors as𝒳=∏i∈F𝒳i\\mathcal\{X\}=\\prod\_\{i\\in F\}\\mathcal\{X\}\_\{i\}, whereFFis a finite index set of features and𝒳i\\mathcal\{X\}\_\{i\}is the domain of featureii, and letx∈𝒳x\\in\\mathcal\{X\}be an input with predictiony=ϕ⁡\(x\)y=\\phi\(x\)\. A subsetH⊆FH\\subseteq Fis an*abductive explanation*\(AXp\) forϕ⁡\(x\)=y\\phi\(x\)=yif \(a\)ϕ⁡\(x′\)=y\\phi\(x^\{\\prime\}\)=yfor everyx′∈𝒳x^\{\\prime\}\\in\\mathcal\{X\}withxi′=xix^\{\\prime\}\_\{i\}=x\_\{i\}for alli∈Hi\\in H, and \(b\) no proper subset ofHHsatisfies \(a\)\.

In Definition[1](https://arxiv.org/html/2608.17103#Thmdefinition1),ϕ\\phiis the classifier whose prediction is being explained,FFis the set of explainable inputs,𝒳i\\mathcal\{X\}\_\{i\}is the domain of inputii,xxis the observed input,y=ϕ⁡\(x\)y=\\phi\(x\)is the prediction atxx,HHis the subset of inputs the explanation holds fixed, andx′x^\{\\prime\}ranges over all alternative inputs that agree withxxonHH\. Clause \(a\) says that as long as the values onHHare pinned, no perturbation of the remaining inputsF∖HF\\setminus Hcan change the prediction\. Clause \(b\) identifies the inputs the model actually relies on rather than a superset that also happens to be sufficient: without \(b\),H=FH=Fwould trivially satisfy \(a\)\.

## 3AXps for Selecting Node\-Feature Pairs

The construction developed in this section turns the sufficiency and minimality conditions of Definition[1](https://arxiv.org/html/2608.17103#Thmdefinition1)into a concrete procedure for explaining SGC node predictions\. We proceed in two steps\. Subsection[3\.1](https://arxiv.org/html/2608.17103#S3.SS1)reformulates the SGC classification rule as a system of linear inequalities over node\-feature pairs, exposing the structure that the AXp computation exploits\. Subsection[3\.2](https://arxiv.org/html/2608.17103#S3.SS2)adepts Definition[1](https://arxiv.org/html/2608.17103#Thmdefinition1)to a nodevvof an SGC classifier and gives a greedy deletion procedure that returns an AXp at node\-feature using a number of model queries linear in the size of the candidate set\.

### 3\.1Linear inequalities for SGC predictions

FixA^\\hat\{A\}andΘ\\Theta\. The entry\(A^K\)v,u\(\\hat\{A\}^\{K\}\)\_\{v,u\}is the total weight with which the feature vector ofuuenters the score atvvafterKKpropagation steps; it is nonzero exactly whenuuis reachable fromvvin at mostKKhops on the augmented graph\. This entry depends onuuonly through structural quantities of the augmented graph \(degrees and the number of walks of length up toKKfromvvtouu\), and in particular it is zero whenever the shortest\-path distance fromvvtouuexceedsKK\. We write𝒩K​\(v\):=\{u∈V:\(A^K\)v,u≠0\}\\mathcal\{N\}\_\{K\}\(v\):=\\\{u\\in V:\(\\hat\{A\}^\{K\}\)\_\{v,u\}\\neq 0\\\}for theKK\-hop receptive field ofvvand note thatv∈𝒩K​\(v\)v\\in\\mathcal\{N\}\_\{K\}\(v\)\. Only feature values at nodes in𝒩K​\(v\)\\mathcal\{N\}\_\{K\}\(v\)can change the score atvv, so they are the only candidates for an explanation ofc∗​\(v\)c^\{\*\}\(v\)\.

ExpandingA^K​𝐗\\hat\{A\}^\{K\}\\,\\mathbf\{X\}entrywise as\(A^K​𝐗\)v,j=∑u∈V\(A^K\)v,u​Xu,j\(\\hat\{A\}^\{K\}\\,\\mathbf\{X\}\)\_\{v,j\}=\\sum\_\{u\\in V\}\(\\hat\{A\}^\{K\}\)\_\{v,u\}\\,X\_\{u,j\}and contracting withΘ\\Theta, the unnormalised score atvvfor classccdecomposes as a linear combination over node\-feature pairs:

\(A^K​𝐗​Θ\)v,c=∑\(u,j\)∈𝒩K​\(v\)×\{1,…,d\}αu,jv,c​Xu,j,αu,jv,c:=\(A^K\)v,u​Θj,c\.\(\\hat\{A\}^\{K\}\\,\\mathbf\{X\}\\,\\Theta\)\_\{v,c\}\\;=\\;\\sum\_\{\(u,j\)\\in\\mathcal\{N\}\_\{K\}\(v\)\\times\\\{1,\\dots,d\\\}\}\\alpha^\{v,c\}\_\{u,j\}\\,X\_\{u,j\},\\qquad\\alpha^\{v,c\}\_\{u,j\}:=\(\\hat\{A\}^\{K\}\)\_\{v,u\}\\,\\Theta\_\{j,c\}\.\(4\)The coefficientαu,jv,c\\alpha^\{v,c\}\_\{u,j\}is the fixed weight with which the Boolean inputXu,jX\_\{u,j\}enters the unnormalised score of classccatvv\. It factors into a structural term\(A^K\)v,u\(\\hat\{A\}^\{K\}\)\_\{v,u\}, recording how stronglyuureachesvv, and a semantic termΘj,c\\Theta\_\{j,c\}, recording how strongly featurejjvotes for classcc\. The coefficients depend only onA^\\hat\{A\}andΘ\\Theta, not on the input features, so they can be precomputed once per node and reused for every explanation query eachvv\. Softmax is strictly monotone, so the predicted class is determined by the argmax of the unnormalised scores\. The predictionc∗​\(v\)=cc^\{\*\}\(v\)=ctherefore holds iff, for every competing classc′≠cc^\{\\prime\}\\neq c, the linear score induced by columnΘ:,c\\Theta\_\{:,c\}exceeds the linear score induced by columnΘ:,c′\\Theta\_\{:,c^\{\\prime\}\}evaluated on the same feature valuesXu,jX\_\{u,j\}over the receptive field\. The classification rule atvvis thus a system ofC−1C\-1linear inequalities in the Boolean inputs\{Xu,j\}\(u,j\)∈𝒩K​\(v\)×\{1,…,d\}\\\{X\_\{u,j\}\\\}\_\{\(u,j\)\\in\\mathcal\{N\}\_\{K\}\(v\)\\times\\\{1,\\dots,d\\\}\}:

∑\(u,j\)∈𝒩K​\(v\)×\{1,…,d\}\(αu,jv,c−αu,jv,c′\)​Xu,j\>0,∀c′≠c,\\sum\_\{\(u,j\)\\in\\mathcal\{N\}\_\{K\}\(v\)\\times\\\{1,\\dots,d\\\}\}\(\\alpha^\{v,c\}\_\{u,j\}\-\\alpha^\{v,c^\{\\prime\}\}\_\{u,j\}\)\\,X\_\{u,j\}\\;\>\\;0,\\qquad\\forall\\,c^\{\\prime\}\\neq c,\(5\)with margin coefficientsαu,jv,c−αu,jv,c′\\alpha^\{v,c\}\_\{u,j\}\-\\alpha^\{v,c^\{\\prime\}\}\_\{u,j\}fixed by the model\. We takec∗​\(v\)c^\{\*\}\(v\)throughout the paper as the prediction to be explained\.

### 3\.2NF\-AXps for SGC

Adapting Definition[1](https://arxiv.org/html/2608.17103#Thmdefinition1)for SGC, the components correspond as follows:ϕ\\phiis the SGC argmax classifier of Eq\. \([3](https://arxiv.org/html/2608.17103#S2.E3)\),F=𝒩K​\(v\)×\{1,…,d\}F=\\mathcal\{N\}\_\{K\}\(v\)\\times\\\{1,\\dots,d\\\}is the set of node\-feature pairs inside the receptive field ofvv,𝒳=\{0,1\}F\\mathcal\{X\}=\\\{0,1\\\}^\{F\}is the Boolean cube indexed by these node\-feature pairs, and𝒴=\{1,…,C\}\\mathcal\{Y\}=\\\{1,\\dots,C\\\}is the set of class labels\. The observed inputxxis the current Boolean configuration onFF, andy=c∗​\(v\)y=c^\{\*\}\(v\)is the predicted class\. A subsetH⊆FH\\subseteq Fis an AXp at node\-feature level forc∗​\(v\)=cc^\{\*\}\(v\)=ciff fixingXu,j=xu,jX\_\{u,j\}=x\_\{u,j\}onHHpreserves, for everyc′≠cc^\{\\prime\}\\neq c, the column\-cc\-vs\-column\-c′c^\{\\prime\}inequality derived from \([4](https://arxiv.org/html/2608.17103#S3.E4)\), for all\{0,1\}\\\{0,1\\\}\-assignments of the remaining entries inF∖HF\\setminus H\. AXp sufficiency is thus a single linear inequality universally quantified over Boolean completions ofF∖HF\\setminus H, with coefficientsαu,jv,c\\alpha^\{v,c\}\_\{u,j\}fixed by the model\.

The natural unit of explanation is therefore a node\-feature pair, rather than a whole node or a whole feature\. As mentioned in Section[2\.1](https://arxiv.org/html/2608.17103#S2.SS1), most datasets considered in our experiments represent node attributes as binary bag\-of\-words vectors, whereXu,j=1X\_\{u,j\}=1indicates the presence of termjjat nodeuu\. We therefore adopt a presence\-based explanation semantics\. Following robust explanation approaches for text classification, explanations are defined in terms of subsets of the words present in the input\[[7](https://arxiv.org/html/2608.17103#bib.bib3)\]\. Accordingly, we consider as explanatory candidates only node\-feature pairs\(u,j\)\(u,j\)for which the corresponding term is present, i\.e\.,Xu,j=1X\_\{u,j\}=1\. The features that can possibly matter for the prediction atvvare therefore exactly those whose pair\(u,j\)\(u,j\)is both reachable and withXu,j=1X\_\{u,j\}=1\. We collect these into the candidate set

𝒞v=\{\(u,j\):u∈𝒩K\(v\),Xu,j=1\},\\mathcal\{C\}\_\{v\}\\;=\\;\\bigl\\\{\(u,j\)\\,:\\,u\\in\\mathcal\{N\}\_\{K\}\(v\),\\;X\_\{u,j\}=1\\bigr\\\},\(6\)which serves as the search space for the NF\-AXp ofvv\. We assume: only pairs that are currently switched onXu,j=1X\_\{u,j\}=1can be “removed” by setting the corresponding entry to zero, and pairs that are switched offXu,j=0X\_\{u,j\}=0already contribute zero to the score under that baseline\.

Letc∗=c∗​\(v\)c^\{\*\}=c^\{\*\}\(v\)denote the SGC prediction atvv\. We want a subset𝒮v⊆𝒞v\\mathcal\{S\}\_\{v\}\\subseteq\\mathcal\{C\}\_\{v\}such that no Boolean completion of the remaining entries of𝐗\\mathbf\{X\}on the receptive field, restricted to\{0,1\}\\\{0,1\\\}on the indices outside𝒮v\\mathcal\{S\}\_\{v\}and inside𝒞v\\mathcal\{C\}\_\{v\}, can flip the predicted class\. Because the SGC score is linear in𝐗\\mathbf\{X\}, the worst\-case completion is computable explicitly\. For every rival classc′≠c∗c^\{\\prime\}\\neq c^\{\*\}, define the contribution of a single pair to the margin ofc∗c^\{\*\}overc′c^\{\\prime\},

δu,j,c′=\(A^K\)v,u​\(Θj,c∗−Θj,c′\),\\delta\_\{u,j,c^\{\\prime\}\}\\;=\\;\(\\hat\{A\}^\{K\}\)\_\{v,u\}\\,\\bigl\(\\Theta\_\{j,c^\{\*\}\}\-\\Theta\_\{j,c^\{\\prime\}\}\\bigr\),and the worst\-case margin attainable under a fixed𝒮⊆𝒞v\\mathcal\{S\}\\subseteq\\mathcal\{C\}\_\{v\}as

margin⁡\(c′,𝒮\)=∑\(u,j\)∈𝒮δu,j,c′\+∑\(u,j\)∈𝒞v∖𝒮min⁡\{0,δu,j,c′\}\.\\margin\(c^\{\\prime\},\\mathcal\{S\}\)\\;=\\;\\sum\_\{\(u,j\)\\in\\mathcal\{S\}\}\\delta\_\{u,j,c^\{\\prime\}\}\\;\+\\;\\sum\_\{\(u,j\)\\in\\mathcal\{C\}\_\{v\}\\setminus\\mathcal\{S\}\}\\min\\\{0,\\,\\delta\_\{u,j,c^\{\\prime\}\}\\\}\.\(7\)The two sums admit a direct worst\-case reading\. Pairs in𝒮\\mathcal\{S\}are held at their observed valueXu,j=1X\_\{u,j\}=1by the explanation and therefore contribute exactlyδu,j,c′\\delta\_\{u,j,c^\{\\prime\}\}\. Pairs outside𝒮\\mathcal\{S\}can take either Boolean value; the completion that minimises the margin setsXu,j=0X\_\{u,j\}=0whenδu,j,c′\>0\\delta\_\{u,j,c^\{\\prime\}\}\>0, removing a contribution that would otherwise favourc∗c^\{\*\}, and keepsXu,j=1X\_\{u,j\}=1whenδu,j,c′<0\\delta\_\{u,j,c^\{\\prime\}\}<0, adding a contribution that reducesc∗c^\{\*\}\. The minimum operator records exactly this worst\-case assignment\. Specialising Definition[1](https://arxiv.org/html/2608.17103#Thmdefinition1)to the SGC then yields an explicit sufficiency condition\.

We call the AXp for SGC a node\-feature AXp \(NF\-AXp\), since it ranges over node\-feature pairs\(u,j\)∈𝒞v\(u,j\)\\in\\mathcal\{C\}\_\{v\}rather than single feature indices\.

###### Definition 2\(NF\-AXp for SGC atvv\)\.

A set𝒮v⊆𝒞v\\mathcal\{S\}\_\{v\}\\subseteq\\mathcal\{C\}\_\{v\}is a \(node\-feature\) abductive explanation forc∗​\(v\)c^\{\*\}\(v\)ifmargin⁡\(c′,𝒮v\)≥0\\margin\(c^\{\\prime\},\\mathcal\{S\}\_\{v\}\)\\geq 0for everyc′≠c∗c^\{\\prime\}\\neq c^\{\*\}\. More over, no proper subset of𝒮v\\mathcal\{S\}\_\{v\}satisfies the same condition\.

A NF\-AXp𝒮v\\mathcal\{S\}\_\{v\}is the analogue, for SGC node classification, of the AXp of Definition[1](https://arxiv.org/html/2608.17103#Thmdefinition1): a irredundant collection of present node\-feature pairs whose value alone, regardless of how every other entry of𝐗\\mathbf\{X\}is set within\{0,1\}\\\{0,1\\\}, already pins the prediction toc∗c^\{\*\}\. Equivalently,𝒮v\\mathcal\{S\}\_\{v\}is a robustness certificate against Boolean erasures on its complement\. The full candidate set𝒞v\\mathcal\{C\}\_\{v\}is trivially sufficient: substituting𝒮v=𝒞v\\mathcal\{S\}\_\{v\}=\\mathcal\{C\}\_\{v\}into Eq\. \([7](https://arxiv.org/html/2608.17103#S3.E7)\) reduces the second sum to zero and recovers the actual margin computed by the model on the observed input, which is non\-negative by the definition ofc∗c^\{\*\}\. So𝒞v\\mathcal\{C\}\_\{v\}is sufficient but not subset\-minimal, and the question is how to compress it\.

We obtain a NF\-AXp𝒮v\\mathcal\{S\}\_\{v\}by greedy deletion\[[5](https://arxiv.org/html/2608.17103#bib.bib13)\]\. The procedure starts from𝒮v←𝒞v\\mathcal\{S\}\_\{v\}\\leftarrow\\mathcal\{C\}\_\{v\}and processes the elements of𝒞v\\mathcal\{C\}\_\{v\}in a fixed deterministic order\. For each pair\(u,j\)\(u,j\)in turn, it tentatively removes the pair from𝒮v\\mathcal\{S\}\_\{v\}and recomputes the worst\-case margin in Eq\. \([7](https://arxiv.org/html/2608.17103#S3.E7)\); ifmargin⁡\(c′,𝒮v∖\{\(u,j\)\}\)≥0\\margin\(c^\{\\prime\},\\mathcal\{S\}\_\{v\}\\setminus\\\{\(u,j\)\\\}\)\\geq 0holds for every rival class, the pair is dropped permanently, otherwise it is restored\. Because the dependence ofmargin\\marginon𝒮\\mathcal\{S\}is monotone, in the sense that removing a pair can only weaken the margin, a pair that fails the test once cannot become removable later, so a single linear pass suffices\. The result is a NF\-AXp at a cost of\|𝒞v\|\|\\mathcal\{C\}\_\{v\}\|margin checks per node, each of which is itself a sum over\|𝒞v\|\|\\mathcal\{C\}\_\{v\}\|contributions and so runs in time linear in the candidate set\. The total cost of an explanation atvvis therefore𝒪⁡\(\(C−1\)​\|𝒞v\|2\)\\mathcal\{O\}\\bigl\(\(C\-1\)\\,\|\\mathcal\{C\}\_\{v\}\|^\{2\}\\bigr\)arithmetic operations\.

By construction, the returned𝒮v\\mathcal\{S\}\_\{v\}inherits the two formal properties of Definition[2](https://arxiv.org/html/2608.17103#Thmdefinition2)\. Sufficiency holds because the last accepted state of𝒮v\\mathcal\{S\}\_\{v\}passes the margin test against every rival; subset\-minimality holds because every pair in the final𝒮v\\mathcal\{S\}\_\{v\}was tested and could not be removed\. Both properties are exact, in the strong sense that they hold for the original SGC decision function\. These per\-node sets are the NF\-AXps of AXSGC, and they are the raw material for the global step\.

## 4Extracting global rules from AXps

We now lift the per\-node NF\-AXps produced in Section[3](https://arxiv.org/html/2608.17103#S3)into a small set of global logical rules\. We proceed in two steps\. Subsection[4\.1](https://arxiv.org/html/2608.17103#S4.SS1)aggregates the per\-node sets into a single propositional representation by replacing concrete node identities with distance\-indexed predicates over features, producing a Boolean matrix that summarises the entire dataset\. Subsection[4\.2](https://arxiv.org/html/2608.17103#S4.SS2)reads global per\-class rules out of this matrix by fitting one shallow decision tree per class against the SGC prediction and converting its root\-to\-leaf paths into DNF rules whose agreement with the model is measured by fidelity\.

### 4\.1Distance\-indexed predicates and the explanation matrix

The NF\-AXps\{𝒮v\}v∈V\\\{\\mathcal\{S\}\_\{v\}\\\}\_\{v\\in V\}are detailed certificates but they are written in terms of concrete neighbour identities\. Two nodes with structurally similar receptive fields can produce explanations that share no pair\(u,j\)\(u,j\)at all, simply because their neighboursuuare different nodes\. To generalise across the graph we abstract over node identity while keeping the hop distance at which a contribution arrives\. Concretely, for every feature indexj∈\{1,…,d\}j\\in\\\{1,\\dots,d\\\}and every hop distancek∈\{0,1,…,K\}k\\in\\\{0,1,\\dots,K\\\}we define a Boolean predicate over nodes:

Pk,j​\(v\)=1⇔∃u∈V:distG​\(v,u\)=k​and​\(u,j\)∈𝒮v\\mathrm\{P\}\_\{k,j\}\(v\)\\;=\\;1\\;\\iff\\;\\exists\\,u\\in V:\\mathrm\{dist\}\_\{G\}\(v,u\)=k\\;\\text\{and\}\\;\(u,j\)\\in\\mathcal\{S\}\_\{v\}\(8\)wheredistG\\mathrm\{dist\}\_\{G\}is the unweighted shortest\-path distance inGG\. In words,Pk,j​\(v\)\\mathrm\{P\}\_\{k,j\}\(v\)asserts that ”featurejjappears in the NF\-AXp ofvvthrough at least one node located exactlykkhops away fromvv”\. The hop truncationk≤Kk\\leq Kis consistent with the SGC receptive field: pairs at greater distance have\(A^K\)v,u=0\(\\hat\{A\}^\{K\}\)\_\{v,u\}=0and therefore cannot appear in any𝒮v\\mathcal\{S\}\_\{v\}\.

Two design choices in Eq\. \([8](https://arxiv.org/html/2608.17103#S4.E8)\) deserve explicit comment\. First, the predicate aggregates over neighbours by existential quantification, which is what allows nodes with isomorphic\-but\-not\-identical neighbourhoods to share predicates\. Second, the predicate is gated by membership in𝒮v\\mathcal\{S\}\_\{v\}, it fires only when the active occurrence was actually used by the abductive explanation\. This second condition is what differentiates the construction from a generic “bag of features per hop” encoding, since the predicate selects exactly the contributions that survived the procedure in Subsection[3\.2](https://arxiv.org/html/2608.17103#S3.SS2)\.

Collecting the predicates yields a global representation of the dataset\. We index columns by pairs\(k,j\)\(k,j\)in lexicographic order and define the explanation matrix

M∈\{0,1\}n×\(K\+1\)​d,Mv,\(k,j\)=Pk,j​\(v\)\.M\\in\\\{0,1\\\}^\{n\\times\(K\+1\)\\,d\},\\qquad M\_\{v,\\,\(k,j\)\}\\;=\\;\\mathrm\{P\}\_\{k,j\}\(v\)\.\(9\)Each row ofMMsummarises the NF\-AXp of a single node in the predicate vocabulary; columns correspond to elementary structural\-semantic events of the form ”featurejjin a node at hopkk”\. The width\(K\+1\)​d\(K\+1\)\\,dis bounded a priori by the model and is independent of how the receptive fields of different nodes overlap\. The matrix is sparse in practice, since most𝒮v\\mathcal\{S\}\_\{v\}are small relative todd, and it is the only object the global stage of AXSGC needs to consult\.

### 4\.2Global rule extraction

The matrixMMfrom Subsection[4\.1](https://arxiv.org/html/2608.17103#S4.SS1)reduces global explanation to a tabular learning problem on Boolean inputs, where each input is a node and the target is the SGC prediction at that node\. We train a single shallow decision treeTTonMMwith the multi\-class targetc∗​\(v\)∈\{1,…,C\}c^\{\*\}\(v\)\\in\\\{1,\\dots,C\\\}\. Crucially, the supervision signal is the SGC prediction and not the dataset label: the tree models the behaviour of the SGC classifier on the predicate vocabulary, so any disagreement betweenTTandc∗c^\{\*\}is a deficiency of the rules and not of the model, and the corresponding gap is what we will later quantify as fidelity\. Splits are scored by Gini impurity and the depth ofTTis fixed a priori\.

The treeTTpartitions the node set according to short conjunctions of predicate tests\. Every internal node ofTTbranches on a single column ofMM, so each root\-to\-leaf path corresponds to a conjunction of literals of the formPk,j​\(v\)=0\\mathrm\{P\}\_\{k,j\}\(v\)=0orPk,j​\(v\)=1\\mathrm\{P\}\_\{k,j\}\(v\)=1, and the leaf at the end of the path carries a single class labelc∈\{1,…,C\}c\\in\\\{1,\\dots,C\\\}\. Reading the literals along a path that terminates at a leaf labelled with classccyields a rule of the form

⋀\(k,j\)∈S\+Pk,j​\(v\)∧⋀\(k,j\)∈S−¬Pk,j​\(v\)⟹c∗​\(v\)=c,\\bigwedge\_\{\(k,j\)\\in S^\{\+\}\}\\mathrm\{P\}\_\{k,j\}\(v\)\\;\\wedge\\;\\bigwedge\_\{\(k,j\)\\in S^\{\-\}\}\\neg\\,\\mathrm\{P\}\_\{k,j\}\(v\)\\;\\Longrightarrow\\;c^\{\*\}\(v\)=c,\(10\)whereS\+S^\{\+\}andS−S^\{\-\}collect the \(hop, feature\) tests asserted respectively true and false along the path\. Grouping the leaves ofTTby their class label and taking the disjunction within each group yields one DNF formula per class; the collection of these formulae forms the global rule set returned by AXSGC\. The depth ofTTis bounded by a small constant so that every rule remains short enough to inspect; this also acts as an implicit regulariser against memorising rare predicate combinations\. Each literal carries a structural reading: a positive literalPk,j​\(v\)=1\\mathrm\{P\}\_\{k,j\}\(v\)=1asserts that some node at distancekkfromvvcontributed featurejjto the explanation, while a negative literal asserts the absence of any such contribution at distance exactlykkfromvv\.

The agreement between the resulting rule set and the SGC model is measured directly\. WritingT⁡\(Mv,⋅\)T\(M\_\{v,\\cdot\}\)for the class label predicted byTTwhen applied to the row ofMMindexed byvv, we define the fidelity of the rule set on a test splitVtest⊆VV\_\{\\mathrm\{test\}\}\\subseteq Vas

Fidelity=Prv∈Vtest\[T\(Mv,⋅\)=c∗\(v\)\],\\mathrm\{Fidelity\}\\;=\\;\\Pr\_\{v\\in V\_\{\\mathrm\{test\}\}\}\\\!\\bigl\[\\,T\(M\_\{v,\\cdot\}\)=c^\{\*\}\(v\)\\,\\bigr\],\(11\)i\.e\. the fraction of test nodes on which the rule set reproduces the SGC prediction\. Fidelity is the central quantity of the global stage because it isolates the contribution of the rule extractor from the contribution of the underlying classifier: the SGC accuracy with respect to the dataset labels is unaffected by the extraction step, while any disagreement between the rules andc∗c^\{\*\}is attributable to the abstraction introduced by the predicates and to the capacity limits imposed on the trees\.

## 5Experiments

The empirical evaluation is organised around three questions raised by the construction of Section[3](https://arxiv.org/html/2608.17103#S3)\. \(Q1\) Does the global rule set extracted from the explanation matrixMMreproduce the predictions of the underlying SGC, and at what cost in description length? \(Q2\) How large are the NF\-AXps𝒮v\\mathcal\{S\}\_\{v\}that AXSGC manipulates internally, and how does this scale with dataset properties? \(Q3\) Are individual rules informative enough to admit a structural reading, and how much of the data does a handful of them cover? Section[5\.1](https://arxiv.org/html/2608.17103#S5.SS1)fixes the protocol; Sections[5\.2](https://arxiv.org/html/2608.17103#S5.SS2),[5\.3](https://arxiv.org/html/2608.17103#S5.SS3)and[5\.4](https://arxiv.org/html/2608.17103#S5.SS4)address the three questions in turn\.

### 5\.1Setup

Four standard node\-classification benchmarks are used, spanning the range of regimes AXSGC is intended to cover\. BAShapes is a synthetic graph of700700nodes built from a Barabási–Albert base augmented with house motifs, with3232one\-hot degree features and44classes; it serves as a controlled sanity check where ground\-truth motifs are known\. Cora \(27082708nodes,14331433binary bag\-of\-words features,77classes\) and Citeseer \(33273327nodes,37033703binary bag\-of\-words features,66classes\) are citation networks with natively binary inputs\. PubMed \(1971719717nodes,500500TF\-IDF features,33classes\) is an order of magnitude larger and is binarised at zero so that the feature matrix𝐗∈\{0,1\}n×d\\mathbf\{X\}\\in\\\{0,1\\\}^\{n\\times d\}matches the Boolean signature on which the predicatesPk,j\\mathrm\{P\}\_\{k,j\}\.

The base classifier is the SGC of\[[12](https://arxiv.org/html/2608.17103#bib.bib12)\]with propagation depthK=2K=2, trained with learning rate10−210^\{\-2\}, weight decay5⋅10−45\\cdot 10^\{\-4\},200200epochs and seed4242\. OnceA^\\hat\{A\}and the learned weights are fixed, NF\-AXps𝒮v\\mathcal\{S\}\_\{v\}are obtained from the propagated representationA^K​𝐗\\hat\{A\}^\{K\}\\mathbf\{X\}by the procedure of Section[3\.2](https://arxiv.org/html/2608.17103#S3.SS2)\. The predicatesPk,j\\mathrm\{P\}\_\{k,j\}of Section[4\.1](https://arxiv.org/html/2608.17103#S4.SS1)then populate the explanation matrixMM, and the global stage of Section[4\.2](https://arxiv.org/html/2608.17103#S4.SS2)fits a single multi\-class decision treeTTonMMwith targetc∗​\(v\)c^\{\*\}\(v\), using the Gini criterion and maximum depth1212\. Each root\-to\-leaf path ofTTyields one rule of the form prescribed by Eq\. \([10](https://arxiv.org/html/2608.17103#S4.E10)\)\.

The reference baseline is LogicXGNN\[[3](https://arxiv.org/html/2608.17103#bib.bib1)\], the closest existing rule\-based global method for graph neural networks\. It is run on the same SGC predictor and the same propagated features, and configured with maximum tree depth1212so that the two decision trees have identical capacity\. The primary metric is the fidelity of the rule set with respect to the SGC, as defined in Eq\. \([11](https://arxiv.org/html/2608.17103#S4.E11)\), namely the fraction of test nodes on which the class\-conditioned DNF rules reproducec∗​\(v\)c^\{\*\}\(v\)\. Parsimony is measured by the total number of extracted rules\. Our implementation is publicly available\.111Anonymous link\.

### 5\.2Fidelity and parsimony \(Q1\)

In addition to fidelity, we report descriptive statistics of the extracted rules: their number, the average length of the antecedents, and their coverage \(the fraction of test nodes on which each rule fires\)\. Together, these characterise how compact and how informative the global rules are\. Unlike the per\-node guarantees of Subsection[3\.2](https://arxiv.org/html/2608.17103#S3.SS2), the global rules carry no explicit sufficiency certificate\. A high fidelity is empirical evidence that the abductive vocabulary captures the SGC decision boundary\.

A rule\-based explainer is only useful insofar as it faithfully tracks the model it claims to describe, and that faithfulness should be obtained with a rule set small enough to inspect\. Table[1](https://arxiv.org/html/2608.17103#S5.T1)reports, for each dataset, the SGC test accuracy together with the fidelity and rule count of the two global explainers\. The SGC accuracy is included as a reference point so that fidelity is read against the predictive quality of the model being explained, not against ground\-truth labels\.

Table 1:Test accuracy of the SGC classifier and fidelity / rule count of the two global rule\-based explainers under identical tree depth1212\.AXSGCLogicXGNNDatasetSGC acc\. \(%\)Fidelity \(%\)rulesFidelity \(%\)rulesBAShapes100\.00100\.006100\.004Cora74\.4090\.707778\.60318Citeseer61\.7083\.507276\.60445PubMed99\.9099\.903169\.70153On BAShapes both methods reach perfect fidelity, with rule counts of the same order as the number of latent motif classes: both methods simply rediscover those motifs, and AXSGC does so with six rules against four\. On Cora, AXSGC reaches90\.7%90\.7\\%fidelity with7777rules, against78\.6%78\.6\\%with318318rules for LogicXGNN\. Citeseer shows the same qualitative pattern at lower absolute fidelity for both methods, with AXSGC reaching83\.5%83\.5\\%fidelity against76\.6%76\.6\\%for LogicXGNN, a gain of6\.96\.9percentage points while using83\.8%83\.8\\%fewer rules \(7272vs445445\)\. On PubMed the gap is the largest of the four benchmarks:99\.9%99\.9\\%fidelity with3131rules against69\.7%69\.7\\%with153153\. A plausible reading is that the NF\-AXp step produces candidate node\-feature pairs tailored to each node before aggregation\. A single rule can then subsume many NF\-AXps once they share a common minimal core\. Decision\-tree path enumeration on the raw propagated features, in contrast, does not exploit this redundancy\.

### 5\.3NF\-AXp sizes \(Q2\)

The global rule set is the externally visible artefact, but it is built by aggregating the NF\-AXps𝒮v\\mathcal\{S\}\_\{v\}produced by greedy deletion\. Their size controls both the cost of AXSGC and the readability of the intermediate evidence that an inspector might want to query for individual nodes\. Table[2](https://arxiv.org/html/2608.17103#S5.T2)reports the mean, median and maximum of\|𝒮v\|\|\\mathcal\{S\}\_\{v\}\|over the whole node set of each dataset\.

Table 2:Distribution of the NF\-AXp size\|𝒮v\|\|\\mathcal\{S\}\_\{v\}\|across all nodes of each dataset\.The mean NF\-AXp size scales jointly with the receptive\-field density induced byA^K\\hat\{A\}^\{K\}and with the feature dimension\. BAShapes, whose3232\-dimensional one\-hot vector\. Because this encoding is extremely sparse after propagation, yields NF\-AXps of median size22\. Cora and Citeseer, which share the bag\-of\-words regime, lie in the same range despite Citeseer’s larger feature dimension\. PubMed, whose denser TF\-IDF signature activates many coordinates per node after two hops ofA^K​𝐗\\hat\{A\}^\{K\}\\mathbf\{X\}, produces the largest NF\-AXps\.

In all three non\-synthetic datasets the median of\|𝒮v\|\|\\mathcal\{S\}\_\{v\}\|is markedly smaller than the mean, and both are orders of magnitude smaller than the maximum\. This long\-tailed shape indicates that a small number of high\-degree hubs concentrate the cost of explanation, while the typical node admits a substantially shorter sufficient condition than the mean alone would suggest\. This is precisely the regime in which the aggregation of the𝒮v\\mathcal\{S\}\_\{v\}through the matrixMMis most beneficial: many short, overlapping NF\-AXps collapse into a few global rules, while the rare long ones are absorbed by the same aggregation step\.

Table 3:Mean rule length \(number of conditions per rule\) of the two global rule\-based explainers under identical tree depth1212\.Beyond the size of the intermediate NF\-AXps, we also compare the size of the global rules between AXSGC and LogicXGNN\. Table[3](https://arxiv.org/html/2608.17103#S5.T3)reports the mean number of conditions per rule for both methods on each dataset\. On BAShapes, both methods produce very short rules, with LogicXGNN slightly shorter \(1\.751\.75vs2\.502\.50\)\. On the citation networks \(Cora and Citeseer\), the two methods produce rules of comparable length, in the range of88–1010conditions\. On PubMed, AXSGC produces noticeably shorter rules \(4\.214\.21vs7\.627\.62\), which is consistent with the smaller number of rules it requires \(Table[1](https://arxiv.org/html/2608.17103#S5.T1)\) and with the long\-tailed shape of the NF\-AXp sizes: a large fraction of nodes admits a short sufficient condition that the global tree can absorb into a compact disjunction\.

### 5\.4A qualitative example and coverage \(Q3\)

Fidelity numbers and average sizes do not by themselves indicate whether individual rules carry semantic content\. As a concrete illustration, consider the highest\-coverage rule extracted on BAShapes, denotedR0R\_\{0\}and assigned to class00\(the Barabási–Albert base nodes\)\. It fires on280280of the700700nodes \(40%40\\%of the dataset\)\.

R0:P0,31​\(v\)=1∧P1,2​\(v\)=0⇒c∗​\(v\)=0\.R\_\{0\}:\\quad P\_\{0,31\}\(v\)=1\\ \\wedge\\ P\_\{1,2\}\(v\)=0\\ \\Rightarrow\\ c^\{\*\}\(v\)=0\.On BAShapes feature3131is the highest\-degree bin of the one\-hot degree encoding and feature22is the degree\-two bin, so the rule asserts that a node belongs to the BA base whenever its own zero\-hop representation activates the high\-degree bin and no node at one hop activates the degree\-two bin\. The condition is structural rather than feature\-driven and matches the way the synthetic graph is generated, which is the kind of correspondence one would hope to recover from a transparent model\.

Table 4:Top\-1 and top\-10 coverage of AXSGC and LogicXGNN rules per dataset\.Coverage is also informative on the citation networks, where exhaustive inspection of the rule list is not realistic\. Table[4](https://arxiv.org/html/2608.17103#S5.T4)reports the top\-11and top\-1010coverage for both methods\. On BAShapes both reach100%100\\%with their ten top rules\. On the larger benchmarks, AXSGC rule sets are markedly more concentrated: the top1010rules cover79\.8%79\.8\\%of Cora,85\.5%85\.5\\%of Citeseer and98\.8%98\.8\\%of PubMed, against34\.6%34\.6\\%,20\.4%20\.4\\%and53\.4%53\.4\\%for LogicXGNN — gaps of2\.3×2\.3\\times,4\.2×4\.2\\timesand1\.85×1\.85\\timesrespectively\. AXSGC therefore concentrates coverage in a small subset of high\-coverage rules, whereas LogicXGNN spreads it more thinly across its larger pool, consistent with its higher rule counts and lower fidelity \(Table[1](https://arxiv.org/html/2608.17103#S5.T1)\)\.

## 6Conclusion

We presented AXSGC, a logic\-based framework for explaining SGC node predictions\. For each node, AXSGC derives an AXp with an explicit sufficiency margin from the closed form of Simple Graph Convolution\. These per\-node AXps are then aggregated into a global per\-class ruleset via a decision tree over distance\-indexed predicates\. Across four benchmarks, our method improves fidelity by up to 30\.2% over LogicXGNN while extracting up to 83\.8% fewer rules\. AXSGC delivers per\-node certified sufficiency and empirically faithful, model\-aligned global rules\. We plan to extend AXSGC in two directions\. First, we will apply it to other GNN architectures by composing it with a distillation step to SGC\[[11](https://arxiv.org/html/2608.17103#bib.bib7)\]\. Second, we will extend our method and the NF\-AXps directly to other GNN architectures\.

## References

- \[1\]B\. Armgaan, M\. Dalmia, S\. Medya, and S\. Ranu\(2024\)GraphTrail: translating GNN predictions into human\-interpretable logical rules\.InAdvances in Neural Information Processing Systems 38 \(NeurIPS 2024\),External Links:[Link](https://openreview.net/forum?id=fzlMza6dRZ)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p2.1)\.
- \[2\]S\. Azzolin, A\. Longa, P\. Barbiero, P\. Lio, and A\. Passerini\(2023\)Global explainability of GNNs via logic combination of learned concepts\.InThe Eleventh International Conference on Learning Representations \(ICLR\),External Links:[Link](https://openreview.net/forum?id=OTbRTIY4YS)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p2.1)\.
- \[3\]C\. Geng, Z\. Zhao, Z\. Wang, H\. Ye, Y\. Jiang, and X\. Si\(2026\)LogicXGNN: grounded logical rules for explaining graph neural networks\.InInternational Conference on Learning Representations \(ICLR\),External Links:2503\.19476,[Link](https://arxiv.org/abs/2503.19476)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p2.1),[§1](https://arxiv.org/html/2608.17103#S1.p8.1),[§5\.1](https://arxiv.org/html/2608.17103#S5.SS1.p3.1)\.
- \[4\]W\. Hu, M\. Fey, M\. Zitnik, Y\. Dong, H\. Ren, B\. Liu, M\. Catasta, and J\. Leskovec\(2020\)Open graph benchmark: datasets for machine learning on graphs\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Vol\.33,pp\. 22118–22133\.External Links:[Link](https://proceedings.neurips.cc/paper/2020/hash/fb60d411a5c5b72b2e7d3527cfc84fd0-Abstract.html)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p1.1)\.
- \[5\]A\. Ignatiev, N\. Narodytska, and J\. Marques\-Silva\(2019\)Abduction\-Based Explanations for Machine Learning Models\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.33,pp\. 1511–1519\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v33i01.33011511),[Link](https://doi.org/10.1609/aaai.v33i01.33011511)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p4.1),[§2\.2](https://arxiv.org/html/2608.17103#S2.SS2.p1.1),[§3\.2](https://arxiv.org/html/2608.17103#S3.SS2.p6.1)\.
- \[6\]W\. Ju, Z\. Fang, Y\. Gu, Z\. Liu, Q\. Long, Z\. Qiao, Y\. Qin, J\. Shen, F\. Sun, Z\. Xiao, J\. Yang, J\. Yuan, Y\. Zhao, Y\. Wang, X\. Luo, and M\. Zhang\(2024\)A comprehensive survey on deep graph representation learning\.Neural Networks173,pp\. 106207\.External Links:[Document](https://dx.doi.org/10.1016/j.neunet.2024.106207),[Link](https://doi.org/10.1016/j.neunet.2024.106207)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p1.1)\.
- \[7\]E\. La Malfa, R\. Michelmore, A\. M\. Zbrzezny, N\. Paoletti, and M\. Kwiatkowska\(2021\)On guaranteed optimal robust explanations for nlp models\.InProceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI\-21,Z\. Zhou \(Ed\.\),pp\. 2658–2665\.Note:Main TrackExternal Links:[Document](https://dx.doi.org/10.24963/ijcai.2021/366),[Link](https://doi.org/10.24963/ijcai.2021/366)Cited by:[§3\.2](https://arxiv.org/html/2608.17103#S3.SS2.p2.1)\.
- \[8\]J\. Marques\-Silva, T\. Gerspacher, M\. C\. Cooper, A\. Ignatiev, and N\. Narodytska\(2020\)Explaining naive Bayes and other linear classifiers with polynomial time and delay\.InAdvances in Neural Information Processing Systems 33 \(NeurIPS 2020\),External Links:[Link](https://proceedings.neurips.cc/paper/2020/hash/eccd2a86bae4728b38627162ba297828-Abstract.html),2008\.05803Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p4.1)\.
- \[9\]J\. Marques\-Silva and A\. Ignatiev\(2022\)Delivering trustworthy AI through formal XAI\.Proceedings of the AAAI Conference on Artificial Intelligence36\(11\),pp\. 12342–12350\.Note:Senior Member Presentation TrackExternal Links:[Document](https://dx.doi.org/10.1609/aaai.v36i11.21499),[Link](https://doi.org/10.1609/aaai.v36i11.21499)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p4.1),[§2\.2](https://arxiv.org/html/2608.17103#S2.SS2.p1.1)\.
- \[10\]T\. A\. Pereira, E\. J\. F\. Nascimento, D\. Mesquita, and A\. H\. Souza\(2022\)ConveXplainer for Graph Neural Networks\.InBrazilian Conference on Intelligent Systems \(BRACIS\),Lecture Notes in Computer Science\.Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p3.1)\.
- \[11\]T\. Pereira, E\. Nascimento, L\. E\. Resck, D\. Mesquita, and A\. Souza\(2023\)Distill n’ explain: explaining graph neural networks using simple surrogates\.InProceedings of The 26th International Conference on Artificial Intelligence and Statistics \(AISTATS\),Proceedings of Machine Learning Research, Vol\.206,pp\. 6199–6214\.External Links:2303\.10139,[Link](https://proceedings.mlr.press/v206/pereira23a.html)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p3.1),[§6](https://arxiv.org/html/2608.17103#S6.p1.1)\.
- \[12\]F\. Wu, A\. Souza, T\. Zhang, C\. Fifty, T\. Yu, and K\. Q\. Weinberger\(2019\)Simplifying graph convolutional networks\.InProceedings of the 36th International Conference on Machine Learning \(ICML\),K\. Chaudhuri and R\. Salakhutdinov \(Eds\.\),Proceedings of Machine Learning Research, Vol\.97,pp\. 6861–6871\.External Links:[Link](https://proceedings.mlr.press/v97/wu19e.html)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p3.1),[§5\.1](https://arxiv.org/html/2608.17103#S5.SS1.p2.1)\.
- \[13\]H\. Yuan, H\. Yu, S\. Gui, and S\. Ji\(2023\)Explainability in graph neural networks: a taxonomic survey\.IEEE Transactions on Pattern Analysis and Machine Intelligence45\(5\),pp\. 5782–5799\.External Links:[Document](https://dx.doi.org/10.1109/TPAMI.2022.3204236),2012\.15445,[Link](https://doi.org/10.1109/TPAMI.2022.3204236)Cited by:[§1](https://arxiv.org/html/2608.17103#S1.p1.1)\.