Source-linked AI summary
From Abductive Explanations to Global Logical Rules for Node Classification in SGCs
Bryan Lima Cavalcante, Thiago Alves Rocha
TL;DR
Existing logic-based explanations for GNNs do not adequately address node-level rule extraction, while abductive explanations had not been directly applied to GNNs. AXSGC uses minimal node-feature explanations to induce global rules for SGCs, achieving high fidelity with substantially fewer rules across benchmark datasets.
Problem
Existing logic-based methods focus mainly on graph classification, while abductive explanations had not been directly applied to GNNs for node-level prediction.
Method
AXSGC extracts minimal node-feature abductive explanations for each SGC prediction and aggregates them through distance-indexed predicates and decision trees into global per-class rules.
Results
Up to 30.2% higher fidelity than LogicXGNN was achieved while extracting up to 83.8% fewer rules across four benchmark datasets.
Takeaways & Limitations
AXSGC provides per-node certified sufficiency and empirically faithful, model-aligned global rules for SGC node predictions.
Takeaways & Limitations
The framework assumes Boolean node features and restricts candidate explanations to node-feature pairs representing present terms.
Abstract
from arXiv · showhide
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
The paper introduces AXSGC, a logic-based framework that uses minimal node-feature abductive explanations to derive compact global rules for SGC node classification. It targets limitations of subgraph-based explanations while preserving fidelity to the original SGC model.
- Motivation: LogicXGNN derives global GNN rules from structural and embedding predicates, then grounds them through representative local subgraphs and feature-based decision trees.This grounding can retain structural information specific to individual nodes, limiting rule generality.
- Motivation: SGC is a natural explanation target because its logits are linear functions of node features while matching state-of-the-art node-classification performance despite removing intermediate nonlinearities.SGC collapses feature propagation and transformations into a single linear classifier.
- Method: AXSGC computes a minimal node-feature AXp for each node, guaranteeing that the selected feature pairs are sufficient and irredundant for the predicted class.Once fixed, the AXp preserves the model output regardless of the remaining inputs.
- Method: AXSGC encodes each AXp as distance-indexed predicates, trains decision trees on these representations, and reads global per-class rules from root-to-leaf paths.The predicates preserve hop distance while abstracting away the identity of contributing neighbors.
- Evaluation: Across benchmark datasets, AXSGC evaluates AXp size, per-class rule size, and intrinsic fidelity to the SGC model against LogicXGNN.The introduction reports fidelity to the SGC up to 30.2% over LogicXGNN.
2. Preliminaries
The preliminaries define the graph, node features, normalized propagation, and SGC classifier notation, then introduce minimal abductive explanations as the formal basis for explaining predictions.
- Graph and feature notation: The graph is G = (V, E), with n = |V | nodes, adjacency matrix A, and node-feature matrix X ∈ Rn×d; most datasets use binary bag-of-words attributes.For binary attributes, Xu,j = 1 indicates that term j occurs in node u’s document, while Xu,j = 0 indicates absence.
- SGC propagation: SGC uses symmetric normalization of the self-loop-augmented adjacency matrix, whose entry ˆAv,u represents one-step weighted influence from node u to node v.The normalization uses the degree matrix of A + I and bounds the propagation operator’s spectrum.
- SGC classifier: The learned weight matrix Θ scores C classes after K propagation steps, with K controlling how far information travels before classification.Each column Θ:,c is the linear classifier for class c, and Θj,c is the weight assigned to feature j for that class.
- Abductive explanations: An abductive explanation is a minimal set of input assignments whose fixed values determine a classifier’s prediction.It must preserve the prediction under every alternative input agreeing on the selected assignments, while no proper subset can do so.
3. AXps for Selecting Node-Feature Pairs
This section defines node-feature abductive explanations for SGC predictions by expressing classification as linear margin constraints over receptive-field pairs and computing subset-minimal sufficient sets through greedy deletion.
- Linear formulation: SGC predictions are rewritten as linear inequalities over node-feature pairs, with coefficients combining graph reachability and class-specific feature weights.The coefficients depend only on the augmented graph and model parameters, and pairs outside the K-hop receptive field have zero structural weight.
- Explanation units: The natural explanation unit is a present node-feature pair within the target node’s receptive field, under presence-based semantics for binary attributes.Currently absent pairs are already zero under the baseline and are not removable explanation elements.
- NF-AXp definition: An NF-AXp is an irredundant set of present node-feature pairs whose fixed values preserve the predicted class under every Boolean completion of the remaining receptive-field entries.Equivalently, it is a robustness certificate against Boolean erasures on the complement.
- Worst-case margins: Worst-case completions preserve positive contributions when fixed and adversarially remove favorable or retain unfavorable unfixed contributions to minimize each class margin.This yields an explicit margin test that must hold against every rival class.
- NF-AXp computation: Greedy deletion starts from the full candidate set and permanently removes a pair only when all worst-case rival margins remain nonnegative.The deterministic procedure returns sets that are exactly sufficient and subset-minimal for the original SGC decision function.
4. Extracting global rules from AXps
AXSGC converts per-node NF-AXps into a distance-indexed Boolean representation that abstracts away concrete node identities while retaining explanation-specific feature occurrences. A shallow decision tree trained to reproduce SGC predictions then yields compact per-class global logical rules, whose fidelity measures agreement with the SGC model.
- 4.1 Predicate abstraction: Distance-indexed predicates abstract away concrete node identities, allowing structurally similar receptive fields to share representations across the graph.Each predicate records whether feature j appears in an NF-AXp through a node exactly k hops away.
- 4.1 Predicate abstraction: Predicates fire only for feature occurrences included in the abductive explanation, rather than encoding a generic bag of features at each hop.Existential aggregation supports isomorphic-but-not-identical neighbourhoods, while explanation membership preserves the NF-AXp condition.
- 4.1 Explanation matrix: The resulting explanation matrix has Boolean rows for nodes and columns for hop-feature events, with width bounded by (K + 1) d.Its columns are indexed by (k, j), and the matrix is sparse in practice because most NF-AXps are small.
- 4.2 Global rule extraction: A shallow decision tree is trained on the matrix using SGC predictions, so disagreement between the tree and SGC predictions reflects rule-extraction deficiency.Splits use Gini impurity, and the tree depth is fixed a priori.
- 4.2 Global rule extraction: Root-to-leaf conjunctions become class-specific rules, and grouping leaves by class produces one DNF formula per class.The bounded tree depth keeps rules short and limits memorisation of rare predicate combinations.
- 4.2 Fidelity: Fidelity is the fraction of test nodes for which the extracted rule set reproduces the SGC prediction.It isolates the rule extractor’s contribution from the underlying classifier’s dataset-label accuracy.
5. Experiments
Experiments on four benchmark datasets evaluate AXSGC against LogicXGNN in fidelity, compactness, NF-AXp size, rule readability, and coverage. AXSGC generally achieves higher fidelity with fewer and more concentrated rules, while its explanations expose structurally meaningful conditions.
- Experimental setup: Evaluation uses BAShapes, Cora, Citeseer, and PubMed, covering synthetic motifs, citation networks, and differing feature regimes.BAShapes has 700 nodes and known motifs; Cora and Citeseer use binary bag-of-words features, while PubMed represents a denser regime.
- Intermediate explanations: NF-AXp sizes are typically short but long-tailed, with larger means associated with denser receptive fields and higher feature activation.BAShapes has median size 2, while PubMed produces the largest NF-AXps; in non-synthetic datasets, hubs account for exceptionally large maxima.
- Rule readability: AXSGC produces noticeably shorter PubMed rules than LogicXGNN, averaging 4.21 versus 7.62 conditions per rule.On BAShapes, LogicXGNN is slightly shorter at 1.75 versus 2.50, while Cora and Citeseer have comparable rule lengths in the range of 8–10 conditions.
- Structural interpretation: The highest-coverage BAShapes rule fires on 40% of nodes and identifies base nodes through degree-based structural conditions.It activates the high-degree bin at zero hops while excluding degree-two activation at one hop, matching the graph’s synthetic construction.
- Rule coverage: AXSGC’s top 10 rules cover 79.8% of Cora, 85.5% of Citeseer, and 98.8% of PubMed, versus 34.6%, 20.4%, and 53.4% for LogicXGNN.The corresponding concentration gaps are 2.3×, 4.2×, and 1.85×, respectively; both methods reach 100% top-10 coverage on BAShapes.
6. Conclusion
AXSGC explains SGC node predictions using minimal, margin-certified abductive explanations and aggregates them into global per-class logical rules. Across four benchmarks, it improves fidelity over LogicXGNN while extracting substantially fewer rules.
- Framework: AXSGC derives per-node AXps with an explicit sufficiency margin from the closed form of Simple Graph Convolution.These explanations provide per-node certified sufficiency.
- Framework: Per-node AXps are aggregated into a global per-class ruleset through a decision tree over distance-indexed predicates.The decision-tree representation converts local explanations into global logical rules.
- Results: 30.2% higher fidelity than LogicXGNN is achieved across four benchmarks, while extracting 83.8% fewer rules.Both figures are reported as improvements over LogicXGNN across the benchmark suite.
Referˆencias
The references span explainability for graph neural networks, logical-rule extraction, abductive explanations, and simplified graph convolutional networks. They also include surveys and benchmark-dataset resources relevant to graph representation learning.
- Logical GNN explanations: Prior work addresses translating GNN predictions into logical rules and combining learned concepts for global explainability.The cited works include GraphTrail and global explainability through logic combinations of learned concepts.
- Logical GNN explanations: The bibliography includes LogicXGNN, which grounds logical rules for explaining graph neural networks.The reference identifies LogicXGNN as a work on grounded logical rules for GNN explanations.
- GNN foundations and resources: Other cited work covers GNN explanation surveys, surrogate explainers, graph representation learning, benchmark datasets, and simplified graph convolutional networks.These references include taxonomic and comprehensive surveys, Distill n’Explain, ConvExplainer, the Open Graph Benchmark, and Simplifying Graph Convolutional Networks.
- Abductive and formal explanations: Abduction-based explanations and formal trustworthy-XAI methods provide foundations for explanation construction and reliability.Related references cover abduction-based explanations for machine-learning models, optimal robust explanations, polynomial-time explanations, and trustworthy AI through formal XAI.