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

Bryan Lima Cavalcante; Thiago Alves Rocha

cs.LGAug 17, 2026

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

Authors: Bryan Lima Cavalcante, Thiago Alves Rocha

Organizations: Instituto Federal do Cear´a (IFCE) Brazil

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.

Figures & tables

		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

Table 1: Test accuracy of the SGC classifier and fidelity / rule count of the two global rule-based explainers under identical tree depth

12

Dataset	$n$	mean $\|\mathcal{S}_{v}\|$	median $\|\mathcal{S}_{v}\|$	max $\|\mathcal{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

Table 2: Distribution of the NF-AXp size

|\mathcal{S}_{v}|

across all nodes of each dataset.

Dataset	AXSGC	LogicXGNN
BAShapes	2.50	1.75
Cora	8.05	9.41
Citeseer	9.49	9.64
PubMed	4.21	7.62

Table 3: Mean rule length (number of conditions per rule) of the two global rule-based explainers under identical tree depth

12

		AXSGC		LogicXGNN
Dataset	$n$	top- $1$	top- $10$	top- $1$	top- $10$
BAShapes	700	280	700 ( $100.0\%$ )	300	700 ( $100.0\%$ )
Cora	2708	374	2162 ( $79.8\%$ )	232	936 ( $34.6\%$ )
Citeseer	3327	740	2846 ( $85.5\%$ )	125	679 ( $20.4\%$ )
PubMed	19717	6783	19477 ( $98.8\%$ )	2045	10528 ( $53.4\%$ )

Table 4: Top-1 and top-10 coverage of AXSGC and LogicXGNN rules per dataset.

GNN Explainability

Graph neural network explainability studies how to identify and communicate the features, nodes, edges, and subgraphs behind graph-model predictions.

See all 82 papers

GRAFT: Auditing Graph Neural Networks via Global Feature Attribution
May 5, 2026Rishi Raj Sahoo, Subhankar MishraFeature Attribution Graph Neural Networks
National Institute of Science Education and Research (NISER), Bhubaneswar, India · Homi Bhabha National Institute, Mumbai, India
Revealing Combinatorial Reasoning of GNNs via Graph Concept Bottleneck Layer
Mar 2, 2026Yue Niu, Zhaokai Sun, Jiayi Yang +5GNN Explainability Graph Neural Networks
Tongji University, Shanghai, China · City University of Macau, Macau, China
Declarative Explanations for Graph Neural Networks: A Demonstration
Oct 19, 2026Cibo Yu, Haitong Tang, Yinghui Wu +4GNN Explainability Graph Neural Networks
Zhejiang University, Hangzhou, China · Case Western Reserve University, Cleveland, USA · Bowling Green State University, Bowling Green, USA

May 5, 2026J/K move · Enter open · S save

GRAFT: Auditing Graph Neural Networks via Global Feature Attribution

Rishi Raj Sahoo, Subhankar Mishra

National Institute of Science Education and Research (NISER), Bhubaneswar, India · Homi Bhabha National Institute, Mumbai, India

Feature Attribution Graph Neural Networks Explainability Evaluation GNN Explainability

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) achieve strong performance on node classification tasks but remain difficult to interpret, particularly with respect to which input features drive their predictions. Existing global GNN explainers operate at the structural level identifying recurring subgraph motifs, but none explain model behaviour globally at the level of input node attributes. We propose GRAFT, a posthoc global explanation framework that identifies class-level feature importance profiles for GNNs. The method combines diversity-guided exemplar selection, Integrated Gradients-based attribution, and aggregation to construct a global view of feature influence for each class, which can be further expressed as concise natural language rules using a large language model with self-refinement. We evaluate GRAFT across multiple datasets, architectures, and experimental settings, demonstrating its effectiveness in capturing model-relevant features, supporting bias analysis, and enabling feature-efficient transfer learning. In addition, we introduce a structured human evaluation protocol to assess the interpretability of generated rules along dimensions such as accuracy and usefulness. Our results suggest that GRAFT provides a practical and interpretable approach for analysing feature-level behaviour in GNNs, bridging quantitative attribution with human-understandable explanations.

Abstract

GNN Explainability

Explore similar work

GRAFT: Auditing Graph Neural Networks via Global Feature Attribution

Revealing Combinatorial Reasoning of GNNs via Graph Concept Bottleneck Layer

Declarative Explanations for Graph Neural Networks: A Demonstration