Paper deep dive
From Abductive Explanations to Global Logical Rules for Node Classification in SGCs
Bryan Lima Cavalcante, Thiago Alves Rocha
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/19/2026, 4:15:22 AM
Summary
The paper proposes AXSGC, a logic-based framework for explaining node classification in Simple Graph Convolution (SGC) networks. It utilizes minimal abductive explanations (NF-AXps) at the node-feature level to ensure sufficiency and irredundancy. These local explanations are aggregated into distance-indexed predicates and used to train decision trees, which extract compact global logical rules. Experiments demonstrate that AXSGC achieves higher fidelity to the SGC model and produces fewer rules compared to existing methods like LogicXGNN.
Entities (7)
Relation Signals (6)
AXSGC → uses → Simple Graph Convolution
confidence 98% · we propose AXSGC... a logic-based method for node classification in SGCs.
AXSGC → utilizes → Node-Feature AXp
confidence 97% · For each node, we extract an AXp at the node-feature level from the SGC classifier and use these AXps as the intermediate representation
Simple Graph Convolution → hasproperty → Linearity
confidence 95% · The logits of an SGC are therefore a linear function of node features.
Node-Feature AXp → isinputto → decision tree
confidence 95% · These explanations are then used to train decision trees from which global logical rules are extracted.
decision tree → produces → Global Logical Rules
confidence 95% · global logical rules are read directly from the root-to-leaf paths of the trees
AXSGC → outperforms → LogicXGNN
confidence 90% · our method achieves fidelity to the SGC up to 30.2% over LogicXGNN and extracting up to 83.8% fewer rules.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2608.17103v1
- Canonical: https://arxiv.org/abs/2608.17103v1
Trouble viewing inline? Open PDF directly →
Full Text
42,870 characters extracted from source content.
Expand or collapse full text
From Abductive Explanations to Global Logical Rules for Node Classification in SGCs Bryan Lima Cavalcante Thiago Alves Rocha 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. 1 Introduction 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, 4]. 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]. A recent line of work approaches this problem through symbolic logic. Methods such as LogicXGNN [3] 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, 1] 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] 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, 11]; 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, 9]. 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]. 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] 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. 2 Preliminaries 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.1 Simple Graph Convolution Let G=(V,E)G=(V,E) be an undirected graph with n=|V|n=|V| nodes, adjacency matrix A∈0,1n×nA∈\0,1\^n× n, and node-feature matrix ∈ℝn×dX ^n× d, where d is the number of node features and Xu,jX_u,j is the value of feature j at node u. In most datasets considered in this work, node attributes are represented as binary bag-of-words vectors. Hence, Xu,j∈0,1X_u,j∈\0,1\, where Xu,j=1X_u,j=1 indicates that term j occurs in the document associated with node u, and Xu,j=0X_u,j=0 indicates its absence. Then, throughout the paper, we assume Boolean node features. Let I∈ℝn×nI ^n× n be the identity matrix. The augmented adjacency A+IA+I adds a self-loop to every node, so each node aggregates its own features alongside those of its neighbours. Let D~ D be the diagonal degree matrix of A+IA+I, with D~ii=∑k=1n(A+I)ik D_i= _k=1^n(A+I)_ik, where D~ii D_i is the degree of node i in the augmented graph. The symmetric normalisation by D~−1/2 D^-1/2 on both sides bounds the spectrum of the propagation operator, defined as A^=D~−1/2(A+I)D~−1/2. A\;=\; D^-1/2\,(A+I)\, D^-1/2. (1) The entry A^v,u A_v,u encodes the one-step weighted influence of node u on node v after self-loop augmentation and symmetric normalisation. Let Θ∈ℝd×C ^d× C be the learned weight matrix, where C is the number of classes and each column Θ:,c∈ℝd _:,c ^d is the linear classifier for class c, with Θj,c _j,c the weight assigned to feature j when scoring class c. Let K∈ℕK be the number of times feature propagation is applied; K plays 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Θ), Y\;=\;softmax ( A^K\,X\, ), (2) with row-wise softmax, where row v of Y Y is the predicted class distribution at node v. The predicted class of node v is c∗(v)=argmaxc∈1,…,C(A^KΘ)v,c,c^*(v)\;=\; _c∈\1,…,C\ ( A^K\,X\, )_v,c, (3) where c∗(v)c^*(v) is the class SGC assigns to node v. 2.2 Abductive Explanations An abductive explanation (AXp) [5, 9] is a minimal set of input assignments whose values determine the model’s prediction. Definition 1 (Abductive explanation). Let ϕ:→φ:X be a classifier whose feature space factors as =∏i∈FiX= _i∈ FX_i, where F is a finite index set of features and iX_i is the domain of feature i, and let x∈x be an input with prediction y=ϕ(x)y=φ(x). A subset H⊆FH F is an abductive explanation (AXp) for ϕ(x)=yφ(x)=y if (a) ϕ(x′)=yφ(x )=y for every x′∈x with xi′=xix _i=x_i for all i∈Hi∈ H, and (b) no proper subset of H satisfies (a). In Definition 1, ϕφ is the classifier whose prediction is being explained, F is the set of explainable inputs, iX_i is the domain of input i, x is the observed input, y=ϕ(x)y=φ(x) is the prediction at x, H is the subset of inputs the explanation holds fixed, and x′x ranges over all alternative inputs that agree with x on H. Clause (a) says that as long as the values on H are pinned, no perturbation of the remaining inputs F∖HF H can 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=F would trivially satisfy (a). 3 AXps for Selecting Node-Feature Pairs The construction developed in this section turns the sufficiency and minimality conditions of Definition 1 into a concrete procedure for explaining SGC node predictions. We proceed in two steps. Subsection 3.1 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 adepts Definition 1 to a node v of 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.1 Linear inequalities for SGC predictions Fix A A and Θ . The entry (A^K)v,u( A^K)_v,u is the total weight with which the feature vector of u enters the score at v after K propagation steps; it is nonzero exactly when u is reachable from v in at most K hops on the augmented graph. This entry depends on u only through structural quantities of the augmented graph (degrees and the number of walks of length up to K from v to u), and in particular it is zero whenever the shortest-path distance from v to u exceeds K. We write K(v):=u∈V:(A^K)v,u≠0N_K(v):=\u∈ V:( A^K)_v,u≠ 0\ for the K-hop receptive field of v and note that v∈K(v)v _K(v). Only feature values at nodes in K(v)N_K(v) can change the score at v, so they are the only candidates for an explanation of c∗(v)c^*(v). Expanding A^K A^K\,X entrywise as (A^K)v,j=∑u∈V(A^K)v,uXu,j( A^K\,X)_v,j= _u∈ V( A^K)_v,u\,X_u,j and contracting with Θ , the unnormalised score at v for class c decomposes as a linear combination over node-feature pairs: (A^KΘ)v,c=∑(u,j)∈K(v)×1,…,dαu,jv,cXu,j,αu,jv,c:=(A^K)v,uΘj,c.( A^K\,X\, )_v,c\;=\; _(u,j) _K(v)×\1,…,d\α^v,c_u,j\,X_u,j, α^v,c_u,j:=( A^K)_v,u\, _j,c. (4) The coefficient αu,jv,cα^v,c_u,j is the fixed weight with which the Boolean input Xu,jX_u,j enters the unnormalised score of class c at v. It factors into a structural term (A^K)v,u( A^K)_v,u, recording how strongly u reaches v, and a semantic term Θj,c _j,c, recording how strongly feature j votes for class c. The coefficients depend only on A A and Θ , not on the input features, so they can be precomputed once per node and reused for every explanation query each v. Softmax is strictly monotone, so the predicted class is determined by the argmax of the unnormalised scores. The prediction c∗(v)=c^*(v)=c therefore holds iff, for every competing class c′≠c ≠ c, the linear score induced by column Θ:,c _:,c exceeds the linear score induced by column Θ:,c′ _:,c evaluated on the same feature values Xu,jX_u,j over the receptive field. The classification rule at v is thus a system of C−1C-1 linear inequalities in the Boolean inputs Xu,j(u,j)∈K(v)×1,…,d\X_u,j\_(u,j) _K(v)×\1,…,d\: ∑(u,j)∈K(v)×1,…,d(αu,jv,c−αu,jv,c′)Xu,j> 0,∀c′≠c, _(u,j) _K(v)×\1,…,d\(α^v,c_u,j-α^v,c _u,j)\,X_u,j\;>\;0, ∀\,c ≠ c, (5) with margin coefficients αu,jv,c−αu,jv,c′α^v,c_u,j-α^v,c _u,j fixed by the model. We take c∗(v)c^*(v) throughout the paper as the prediction to be explained. 3.2 NF-AXps for SGC Adapting Definition 1 for SGC, the components correspond as follows: ϕφ is the SGC argmax classifier of Eq. (3), F=K(v)×1,…,dF=N_K(v)×\1,…,d\ is the set of node-feature pairs inside the receptive field of v, =0,1FX=\0,1\^F is the Boolean cube indexed by these node-feature pairs, and =1,…,CY=\1,…,C\ is the set of class labels. The observed input x is the current Boolean configuration on F, and y=c∗(v)y=c^*(v) is the predicted class. A subset H⊆FH F is an AXp at node-feature level for c∗(v)=c^*(v)=c iff fixing Xu,j=xu,jX_u,j=x_u,j on H preserves, for every c′≠c ≠ c, the column-c-vs-column-c′c inequality derived from (4), for all 0,1\0,1\-assignments of the remaining entries in F∖HF H. AXp sufficiency is thus a single linear inequality universally quantified over Boolean completions of F∖HF H, with coefficients αu,jv,cα^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, most datasets considered in our experiments represent node attributes as binary bag-of-words vectors, where Xu,j=1X_u,j=1 indicates the presence of term j at node u. 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]. 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 at v are therefore exactly those whose pair (u,j)(u,j) is both reachable and with Xu,j=1X_u,j=1. We collect these into the candidate set v=(u,j):u∈K(v),Xu,j=1,C_v\;=\; \(u,j)\,:\,u _K(v),\;X_u,j=1 \, (6) which serves as the search space for the NF-AXp of v. We assume: only pairs that are currently switched on Xu,j=1X_u,j=1 can be “removed” by setting the corresponding entry to zero, and pairs that are switched off Xu,j=0X_u,j=0 already contribute zero to the score under that baseline. Let c∗=c∗(v)c^*=c^*(v) denote the SGC prediction at v. We want a subset v⊆vS_v _v such that no Boolean completion of the remaining entries of X on the receptive field, restricted to 0,1\0,1\ on the indices outside vS_v and inside vC_v, can flip the predicted class. Because the SGC score is linear in X, the worst-case completion is computable explicitly. For every rival class c′≠c∗c ≠ c^*, define the contribution of a single pair to the margin of c∗c^* over c′c , δu,j,c′=(A^K)v,u(Θj,c∗−Θj,c′), _u,j,c \;=\;( A^K)_v,u\, ( _j,c^*- _j,c ), and the worst-case margin attainable under a fixed ⊆vS _v as margin(c′,)=∑(u,j)∈δu,j,c′+∑(u,j)∈v∖min0,δu,j,c′. (c ,S)\;=\; _(u,j) _u,j,c \;+\; _(u,j) _v \0,\, _u,j,c \. (7) The two sums admit a direct worst-case reading. Pairs in S are held at their observed value Xu,j=1X_u,j=1 by the explanation and therefore contribute exactly δu,j,c′ _u,j,c . Pairs outside S can take either Boolean value; the completion that minimises the margin sets Xu,j=0X_u,j=0 when δu,j,c′>0 _u,j,c >0, removing a contribution that would otherwise favour c∗c^*, and keeps Xu,j=1X_u,j=1 when δu,j,c′<0 _u,j,c <0, adding a contribution that reduces c∗c^*. The minimum operator records exactly this worst-case assignment. Specialising Definition 1 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) _v rather than single feature indices. Definition 2 (NF-AXp for SGC at v). A set v⊆vS_v _v is a (node-feature) abductive explanation for c∗(v)c^*(v) if margin(c′,v)≥0 (c ,S_v)≥ 0 for every c′≠c∗c ≠ c^*. More over, no proper subset of vS_v satisfies the same condition. A NF-AXp vS_v is the analogue, for SGC node classification, of the AXp of Definition 1: a irredundant collection of present node-feature pairs whose value alone, regardless of how every other entry of X is set within 0,1\0,1\, already pins the prediction to c∗c^*. Equivalently, vS_v is a robustness certificate against Boolean erasures on its complement. The full candidate set vC_v is trivially sufficient: substituting v=vS_v=C_v into Eq. (7) 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 of c∗c^*. So vC_v is sufficient but not subset-minimal, and the question is how to compress it. We obtain a NF-AXp vS_v by greedy deletion [5]. The procedure starts from v←vS_v _v and processes the elements of vC_v in a fixed deterministic order. For each pair (u,j)(u,j) in turn, it tentatively removes the pair from vS_v and recomputes the worst-case margin in Eq. (7); if margin(c′,v∖(u,j))≥0 (c ,S_v \(u,j)\)≥ 0 holds for every rival class, the pair is dropped permanently, otherwise it is restored. Because the dependence of margin on 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||C_v| margin checks per node, each of which is itself a sum over |v||C_v| contributions and so runs in time linear in the candidate set. The total cost of an explanation at v is therefore ((C−1)|v|2)O ((C-1)\,|C_v|^2 ) arithmetic operations. By construction, the returned vS_v inherits the two formal properties of Definition 2. Sufficiency holds because the last accepted state of vS_v passes the margin test against every rival; subset-minimality holds because every pair in the final vS_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. 4 Extracting global rules from AXps We now lift the per-node NF-AXps produced in Section 3 into a small set of global logical rules. We proceed in two steps. Subsection 4.1 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 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.1 Distance-indexed predicates and the explanation matrix The NF-AXps vv∈V\S_v\_v∈ 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 neighbours u are 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 index j∈1,…,dj∈\1,…,d\ and every hop distance k∈0,1,…,Kk∈\0,1,…,K\ we define a Boolean predicate over nodes: Pk,j(v)= 1⇔∃u∈V:distG(v,u)=kand(u,j)∈vP_k,j(v)\;=\;1\; \;∃\,u∈ V:dist_G(v,u)=k\;and\;(u,j) _v (8) where distGdist_G is the unweighted shortest-path distance in G. In words, Pk,j(v)P_k,j(v) asserts that ”feature j appears in the NF-AXp of v through at least one node located exactly k hops away from v”. The hop truncation k≤Kk≤ K is consistent with the SGC receptive field: pairs at greater distance have (A^K)v,u=0( A^K)_v,u=0 and therefore cannot appear in any vS_v. Two design choices in Eq. (8) 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 vS_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. 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,1n×(K+1)d,Mv,(k,j)=Pk,j(v).M∈\0,1\^n×(K+1)\,d, M_v,\,(k,j)\;=\;P_k,j(v). (9) Each row of M summarises the NF-AXp of a single node in the predicate vocabulary; columns correspond to elementary structural-semantic events of the form ”feature j in a node at hop k”. The width (K+1)d(K+1)\,d is 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 vS_v are small relative to d, and it is the only object the global stage of AXSGC needs to consult. 4.2 Global rule extraction The matrix M from Subsection 4.1 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 tree T on M with the multi-class target c∗(v)∈1,…,Cc^*(v)∈\1,…,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 between T and c∗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 of T is fixed a priori. The tree T partitions the node set according to short conjunctions of predicate tests. Every internal node of T branches on a single column of M, so each root-to-leaf path corresponds to a conjunction of literals of the form Pk,j(v)=0P_k,j(v)=0 or Pk,j(v)=1P_k,j(v)=1, and the leaf at the end of the path carries a single class label c∈1,…,Cc∈\1,…,C\. Reading the literals along a path that terminates at a leaf labelled with class c yields a rule of the form ⋀(k,j)∈S+Pk,j(v)∧⋀(k,j)∈S−¬Pk,j(v)⟹c∗(v)=c, _(k,j)∈ S^+P_k,j(v)\; \; _(k,j)∈ S^- \,P_k,j(v)\; \;c^*(v)=c, (10) where S+S^+ and S−S^- collect the (hop, feature) tests asserted respectively true and false along the path. Grouping the leaves of T by 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 of T is 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 literal Pk,j(v)=1P_k,j(v)=1 asserts that some node at distance k from v contributed feature j to the explanation, while a negative literal asserts the absence of any such contribution at distance exactly k from v. The agreement between the resulting rule set and the SGC model is measured directly. Writing T(Mv,⋅)T(M_v,·) for the class label predicted by T when applied to the row of M indexed by v, we define the fidelity of the rule set on a test split Vtest⊆V_test V as Fidelity=Prv∈Vtest[T(Mv,⋅)=c∗(v)],Fidelity\;=\; _v∈ V_test\! [\,T(M_v,·)=c^*(v)\, ], (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 and c∗c^* is attributable to the abstraction introduced by the predicates and to the capacity limits imposed on the trees. 5 Experiments The empirical evaluation is organised around three questions raised by the construction of Section 3. (Q1) Does the global rule set extracted from the explanation matrix M reproduce the predictions of the underlying SGC, and at what cost in description length? (Q2) How large are the NF-AXps vS_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 fixes the protocol; Sections 5.2, 5.3 and 5.4 address the three questions in turn. 5.1 Setup Four standard node-classification benchmarks are used, spanning the range of regimes AXSGC is intended to cover. BAShapes is a synthetic graph of 700700 nodes built from a Barabási–Albert base augmented with house motifs, with 3232 one-hot degree features and 44 classes; it serves as a controlled sanity check where ground-truth motifs are known. Cora (27082708 nodes, 14331433 binary bag-of-words features, 77 classes) and Citeseer (33273327 nodes, 37033703 binary bag-of-words features, 66 classes) are citation networks with natively binary inputs. PubMed (1971719717 nodes, 500500 TF-IDF features, 33 classes) is an order of magnitude larger and is binarised at zero so that the feature matrix ∈0,1n×dX∈\0,1\^n× d matches the Boolean signature on which the predicates Pk,jP_k,j. The base classifier is the SGC of [12] with propagation depth K=2K=2, trained with learning rate 10−210^-2, weight decay 5⋅10−45· 10^-4, 200200 epochs and seed 4242. Once A A and the learned weights are fixed, NF-AXps vS_v are obtained from the propagated representation A^K A^KX by the procedure of Section 3.2. The predicates Pk,jP_k,j of Section 4.1 then populate the explanation matrix M, and the global stage of Section 4.2 fits a single multi-class decision tree T on M with target c∗(v)c^*(v), using the Gini criterion and maximum depth 1212. Each root-to-leaf path of T yields one rule of the form prescribed by Eq. (10). The reference baseline is LogicXGNN [3], 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 depth 1212 so 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), namely the fraction of test nodes on which the class-conditioned DNF rules reproduce c∗(v)c^*(v). Parsimony is measured by the total number of extracted rules. Our implementation is publicly available.11 1 Anonymous link. 5.2 Fidelity 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, 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 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 depth 1212. AXSGC LogicXGNN Dataset SGC acc. (%) Fidelity (%) rules Fidelity (%) rules BAShapes 100.00 100.00 6 100.00 4 Cora 74.40 90.70 77 78.60 318 Citeseer 61.70 83.50 72 76.60 445 PubMed 99.90 99.90 31 69.70 153 On 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 reaches 90.7%90.7\% fidelity with 7777 rules, against 78.6%78.6\% with 318318 rules for LogicXGNN. Citeseer shows the same qualitative pattern at lower absolute fidelity for both methods, with AXSGC reaching 83.5%83.5\% fidelity against 76.6%76.6\% for LogicXGNN, a gain of 6.96.9 percentage points while using 83.8%83.8\% fewer rules (7272 vs 445445). On PubMed the gap is the largest of the four benchmarks: 99.9%99.9\% fidelity with 3131 rules against 69.7%69.7\% with 153153. 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.3 NF-AXp sizes (Q2) The global rule set is the externally visible artefact, but it is built by aggregating the NF-AXps vS_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 reports the mean, median and maximum of |v||S_v| over the whole node set of each dataset. Table 2: Distribution of the NF-AXp size |v||S_v| across all nodes of each dataset. Dataset n mean |v||S_v| median |v||S_v| max |v||S_v| BAShapes 700 4.0 2 31 Cora 2708 67.4 32 2426 Citeseer 3327 61.7 35 1238 PubMed 19717 629.2 292 45288 The mean NF-AXp size scales jointly with the receptive-field density induced by A^K A^K and with the feature dimension. BAShapes, whose 3232-dimensional one-hot vector. Because this encoding is extremely sparse after propagation, yields NF-AXps of median size 22. 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 of A^K A^KX, produces the largest NF-AXps. In all three non-synthetic datasets the median of |v||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 vS_v through the matrix M is 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 depth 1212. Dataset AXSGC LogicXGNN BAShapes 2.50 1.75 Cora 8.05 9.41 Citeseer 9.49 9.64 PubMed 4.21 7.62 Beyond the size of the intermediate NF-AXps, we also compare the size of the global rules between AXSGC and LogicXGNN. Table 3 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.75 vs 2.502.50). On the citation networks (Cora and Citeseer), the two methods produce rules of comparable length, in the range of 88–1010 conditions. On PubMed, AXSGC produces noticeably shorter rules (4.214.21 vs 7.627.62), which is consistent with the smaller number of rules it requires (Table 1) 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.4 A 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, denoted R0R_0 and assigned to class 00 (the Barabási–Albert base nodes). It fires on 280280 of the 700700 nodes (40%40\% of the dataset). R0:P0,31(v)=1∧P1,2(v)=0⇒c∗(v)=0.R_0: P_0,31(v)=1\ \ P_1,2(v)=0\ \ c^*(v)=0. On BAShapes feature 3131 is the highest-degree bin of the one-hot degree encoding and feature 22 is 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. AXSGC LogicXGNN Dataset n top-11 top-1010 top-11 top-1010 BAShapes 700 280 700 (100.0%100.0\%) 300 700 (100.0%100.0\%) Cora 2708 374 2162 (79.8%79.8\%) 232 936 (34.6%34.6\%) Citeseer 3327 740 2846 (85.5%85.5\%) 125 679 (20.4%20.4\%) PubMed 19717 6783 19477 (98.8%98.8\%) 2045 10528 (53.4%53.4\%) Coverage is also informative on the citation networks, where exhaustive inspection of the rule list is not realistic. Table 4 reports the top-11 and top-1010 coverage for both methods. On BAShapes both reach 100%100\% with their ten top rules. On the larger benchmarks, AXSGC rule sets are markedly more concentrated: the top 1010 rules cover 79.8%79.8\% of Cora, 85.5%85.5\% of Citeseer and 98.8%98.8\% of PubMed, against 34.6%34.6\%, 20.4%20.4\% and 53.4%53.4\% for LogicXGNN — gaps of 2.3×2.3×, 4.2×4.2× and 1.85×1.85× respectively. 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). 6 Conclusion 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]. 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. In Advances in Neural Information Processing Systems 38 (NeurIPS 2024), External Links: Link Cited by: §1. [2] S. Azzolin, A. Longa, P. Barbiero, P. Lio, and A. Passerini (2023) Global explainability of GNNs via logic combination of learned concepts. In The Eleventh International Conference on Learning Representations (ICLR), External Links: Link Cited by: §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. In International Conference on Learning Representations (ICLR), External Links: 2503.19476, Link Cited by: §1, §1, §5.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. In Advances in Neural Information Processing Systems (NeurIPS), Vol. 33, p. 22118–22133. External Links: Link Cited by: §1. [5] A. Ignatiev, N. Narodytska, and J. Marques-Silva (2019) Abduction-Based Explanations for Machine Learning Models. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 33, p. 1511–1519. External Links: Document, Link Cited by: §1, §2.2, §3.2. [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 Networks 173, p. 106207. External Links: Document, Link Cited by: §1. [7] E. La Malfa, R. Michelmore, A. M. Zbrzezny, N. Paoletti, and M. Kwiatkowska (2021) On guaranteed optimal robust explanations for nlp models. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, Z. Zhou (Ed.), p. 2658–2665. Note: Main Track External Links: Document, Link Cited by: §3.2. [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. In Advances in Neural Information Processing Systems 33 (NeurIPS 2020), External Links: Link, 2008.05803 Cited by: §1. [9] J. Marques-Silva and A. Ignatiev (2022) Delivering trustworthy AI through formal XAI. Proceedings of the AAAI Conference on Artificial Intelligence 36 (11), p. 12342–12350. Note: Senior Member Presentation Track External Links: Document, Link Cited by: §1, §2.2. [10] T. A. Pereira, E. J. F. Nascimento, D. Mesquita, and A. H. Souza (2022) ConveXplainer for Graph Neural Networks. In Brazilian Conference on Intelligent Systems (BRACIS), Lecture Notes in Computer Science. Cited by: §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. In Proceedings of The 26th International Conference on Artificial Intelligence and Statistics (AISTATS), Proceedings of Machine Learning Research, Vol. 206, p. 6199–6214. External Links: 2303.10139, Link Cited by: §1, §6. [12] F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Q. Weinberger (2019) Simplifying graph convolutional networks. In Proceedings of the 36th International Conference on Machine Learning (ICML), K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 6861–6871. External Links: Link Cited by: §1, §5.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 Intelligence 45 (5), p. 5782–5799. External Links: Document, 2012.15445, Link Cited by: §1.