Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning

Chuqin Geng; Li Zhang; Haolin Ye; Ziyu Zhao; Yuhe Jiang; Tara Saba; Xinyu Wang; Xujie Si

cs.LGFeb 18, 2026

Beyond Message Passing: A Symbolic Alternative for Expressive and Interpretable Graph Learning

Authors: Chuqin Geng, Li Zhang, Haolin Ye, Ziyu Zhao, Yuhe Jiang, Tara Saba, Xinyu Wang, Xujie Si

Organizations: School of Computer Science, McGill University, Montreal, Canada · Department of Computer Science, University of Toronto, Toronto, Canada

Abstract

Graph Neural Networks (GNNs) have become essential in high-stakes domains such as drug discovery, yet their black-box nature remains a significant barrier to trustworthiness. While self-explainable GNNs attempt to bridge this gap, they often rely on standard message-passing backbones that inherit fundamental limitations, including the 1-Weisfeiler-Lehman (1-WL) expressivity barrier and a lack of fine-grained interpretability. To address these challenges, we propose SymGraph, a symbolic framework designed to transcend these constraints. By replacing continuous message passing with discrete structural hashing and topological role-based aggregation, our architecture theoretically surpasses the 1-WL barrier, achieving superior expressiveness without the overhead of differentiable optimization. Extensive empirical evaluations demonstrate that SymGraph achieves state-of-the-art performance, outperforming existing self-explainable GNNs. Notably, SymGraph delivers 10x to 100x speedups in training time using only CPU execution. Furthermore, SymGraph generates rules with superior semantic granularity compared to existing rule-based methods, offering great potential for scientific discovery and explainable AI.

Figures & tables

Figure 1: Visualization of a Local Structural Predicate. The extracted predicate identifies specific node and edge constraints, providing superior semantic granularity compared to canonical subgraph-based explanations. See more details in Appendix H .

Figure 2: An overview of the SymGraph framework.

	Ba2Motifs		BaMultiShapes		PROTEINS		Mutagenicity		NCI1		BBBP
Model	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$
GCN	58.3 $\pm$ 2.3	0.2 $\pm$ 0.0	70.7 $\pm$ 9.7	0.5 $\pm$ 0.0	71.1 $\pm$ 1.5	2.8 $\pm$ 0.4	81.6 $\pm$ 1.0	14.4 $\pm$ 1.6	76.0 $\pm$ 1.3	12.6 $\pm$ 1.1	86.1 $\pm$ 1.0	5.3 $\pm$ 1.0
GraphSAGE	48.2 $\pm$ 0.8	0.3 $\pm$ 0.0	50.6 $\pm$ 2.1	0.3 $\pm$ 0.0	72.3 $\pm$ 2.3	2.2 $\pm$ 1.1	81.9 $\pm$ 1.6	13.9 $\pm$ 3.2	79.6 $\pm$ 0.3	12.9 $\pm$ 1.4	86.9 $\pm$ 1.0	4.6 $\pm$ 1.7
GAT	48.2 $\pm$ 0.8	0.3 $\pm$ 0.0	49.4 $\pm$ 2.1	0.3 $\pm$ 0.0	70.9 $\pm$ 1.0	1.8 $\pm$ 1.1	82.2 $\pm$ 1.2	18.2 $\pm$ 1.9	78.0 $\pm$ 2.0	16.4 $\pm$ 4.3	88.2 $\pm$ 2.0	6.9 $\pm$ 1.0
GIN	100.0 $\pm$ 0.0	0.3 $\pm$ 0.0	95.0 $\pm$ 1.5	0.4 $\pm$ 0.2	68.5 $\pm$ 2.3	3.0 $\pm$ 0.4	83.0 $\pm$ 1.6	13.1 $\pm$ 1.4	81.2 $\pm$ 1.3	11.9 $\pm$ 2.2	87.7 $\pm$ 1.0	5.5 $\pm$ 0.6
GNAN	49.5 $\pm$ 0.5	51.8 $\pm$ 1.2	51.4 $\pm$ 1.6	50.4 $\pm$ 1.2	59.6 $\pm$ 0.0	65.2 $\pm$ 1.8	55.4 $\pm$ 0.1	163.6 $\pm$ 5.7	52.1 $\pm$ 1.7	326.7 $\pm$ 13.1	23.5 $\pm$ 0.0	81.8 $\pm$ 3.4

Table 1: Performance Benchmark. Comparison of test accuracy (%) and total runtime (

10^{2}

seconds) against state-of-the-art self-explainable GNNs and standard message-passing GNN baselines. Results are averaged over five random seeds. Bold and underlined indicate the best and second-best performance, respectively. SymGraph -DT and SymGraph -RF denote the decision tree and random forest variants of our framework. Notably, our approach achieves superior accuracy on complex molecular datasets while being orders of magnitude faster than competing self-explainable methods like LogiX-GIN and PiGNN . See more results in Appendix E .

Panel of Figure 3 — Figure 3: Baselines’ explanations exhibit irrelevant rules and chemically invalid components.

Panel of Figure 4 — Figure 4: SymGraph identifies expert-validated chemical motifs that provide ground-truth explanations for molecular properties. Our predicates enforce structural constraints on node and edge attributes, which are readily mapped to SMARTS patterns, as illustrated by the red highlights on the chemical compounds. This provides a direct bridge between learned logic and established domain knowledge.

Ablation 1: Topological Role Encoding via Orbits (Orbits)
Model Variant	PROTEINS	Mutagenicity	NCI1	BBBP
DT w/o Orbits	70.0 $\pm$ 3.4	78.4 $\pm$ 0.9	73.0 $\pm$ 1.2	84.4 $\pm$ 1.4
RF w/o Orbits	75.3 $\pm$ 2.6	81.6 $\pm$ 0.7	81.5 $\pm$ 1.1	86.7 $\pm$ 1.3
Ablation 2: Structural Histograms (Counts)
DT w/o Counts	66.7 $\pm$ 4.7	80.1 $\pm$ 0.9	74.2 $\pm$ 1.0	84.6 $\pm$ 1.4
RF w/o Counts	75.2 $\pm$ 1.4	83.4 $\pm$ 1.7	82.9 $\pm$ 1.7	88.5 $\pm$ 1.2

Table 2: Ablation Study. Impact of removing key components from SymGraph . Results are reported as mean

\pm

standard deviation over 5 random seeds. The consistent performance degradation across all variants validates the design principles of SymGraph .

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

	Ba2Motifs	BAMultiShapes	Mutagenicity	BBBP	NCI1	PROTEINS
#Graphs	1,000	1,000	4,337	2,050	4,110	1,113
Avg. $\|\mathcal{V}\|$	25.0	40.0	30.3	23.9	29.9	39.1
Avg. $\|\mathcal{E}\|$	51.0	87.0	30.8	51.6	32.3	145.6

Appendix

Table 3: Statistics of standard graph classification datasets used in the main paper.

	MUTAG	BACE	HIV	IMDB-BINARY	TreeGrid	BaShapes
#Graphs	188	1,513	1,484	1,000	1	1
Avg. $\|\mathcal{V}\|$	17.9	34.1	26.1	19.8	1,231	700
Avg. $\|\mathcal{E}\|$	39.6	73.7	55.5	193.1	1,550	2,105

Appendix

Table 4: Statistics of additional graph and node classification datasets used in the supplementary material. Note that TreeGrid and BaShapes are single-graph node classification tasks, so

|\mathcal{V}|

and

|\mathcal{E}|

refer to the total size of the single graph.

Dataset	K_HOPS	TREE_MODE	MAX_LEAVES_CAP	POPULATION_SIZE	GENERATION	JUDGE_MAX_LEAVES	JUDGE_CCP_ALPHA
Ba2Motifs	1	’LEAVES’	—	—	—	—	—
BaMultiShapes	1	’LEAVES’	—	—	—	—	—
PROTEINS	1	’LEAVES’	16	100	5	48	0.001
Mutagenicity	2	’LEAVES’	16	100	5	48	0.001
NCI1	2	’LEAVES’	16	100	5	48	0.001
BBBP	2	’LEAVES’	16	100	5	32	0.001

Appendix

Table 5: Hyperparameter configuration for SymGraph models.

Panel of Figure 5 — Figure 5: Raw subgraph visualization via Node IDs. These figures display partially the raw output from the LogiX-GIN extraction process. The highlighted regions correspond to the internal node indices (IDs) identified in the DNF rules as critical for classification, prior to semantic mapping.

Panel of Figure 6 — Figure 6: Semantically interpreted visualization with atom identities. The corresponding molecular visualization of the graphs in Figure 5 . By mapping internal IDs to atomic identities and manual filtering, we collect these highlighted subgraphs that are easier to interpret.

	MUTAG		BACE		ClinTox		IMDB		TreeGrid		BaShapes
Model	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$	Acc $\uparrow$	Time $\downarrow$
GCN	74.7 $\pm$ 6.1	0.5 $\pm$ 0.2	80.7 $\pm$ 1.7	4.8 $\pm$ 1.1	92.3 $\pm$ 0.6	8.0 $\pm$ 4.6	49.4 $\pm$ 2.1	0.3 $\pm$ 0.0	71.6 $\pm$ 1.1	44.1 $\pm$ 0.8	85.5 $\pm$ 2.0	34.5 $\pm$ 1.7
GIN	88.4 $\pm$ 3.0	0.4 $\pm$ 0.0	82.4 $\pm$ 2.7	3.8 $\pm$ 1.0	92.3 $\pm$ 0.7	7.8 $\pm$ 2.4	69.5 $\pm$ 1.9	0.7 $\pm$ 0.2	82.6 $\pm$ 0.2	34.1 $\pm$ 4.1	96.9 $\pm$ 1.0	27.6 $\pm$ 1.3
GraphSAGE	75.3 $\pm$ 4.8	0.4 $\pm$ 0.1	82.6 $\pm$ 2.2	4.4 $\pm$ 0.8	92.2 $\pm$ 1.0	8.2 $\pm$ 0.5	48.6 $\pm$ 1.5	0.2 $\pm$ 0.0	41.5 $\pm$ 2.4	24.9 $\pm$ 1.6	42.9 $\pm$ 1.7	21.5 $\pm$ 0.2
GAT	75.3 $\pm$ 3.5	0.5 $\pm$ 0.2	81.7 $\pm$ 1.1	6.3 $\pm$ 1.0	92.6 $\pm$ 0.9	9.4 $\pm$ 3.8	50.6 $\pm$ 2.1	0.3 $\pm$ 0.0	41.5 $\pm$ 2.4	32.6 $\pm$ 2.0	42.9 $\pm$ 1.7	28.7 $\pm$ 1.3
KerGNN	69.0 $\pm$ 2.2	19.5 $\pm$ 0.4	57.0 $\pm$ 2.7	91.8 $\pm$ 0.1	92.4 $\pm$ 1.0	10.3 $\pm$ 1.0	51.3 $\pm$ 1.6	65.9 $\pm$ 0.2	—	—	—	—

Appendix

Table 6: Test accuracy (%) and runtime (

10^{2}

seconds) on additional benchmarks for XAI graph and node classification. Results are averaged over five random seeds. Bold indicates the best performance, and underlined indicates the second-best. SymGraph -DT and SymGraph -RF denote decision tree and random forest variants of our framework, respectively. — indicates that the method is not supported.

Figure 7: Visualization of logic rules induced by local structural predicates. The symbolic rule $(\text{Orbit 0: }\#\text{O}=1)\wedge(\text{Orbit 1: }\#(\text{C-C})\geq 2)$ is grounded to a specific molecular substructure. By decomposing the motif into Orbit 0 (node constraint) and Orbit 1 (edge constraint), SymGraph achieves a level of semantic granularity that exceeds traditional coarse-grained subgraph explanations.

Aspect	SMARTS Rules (Chemical Standard)	SymGraph ’s Rules
Structural Constraints	Atom and bond constraints at specific positions (e.g., [O] , [C]-[O] )	Orbit-wise node and edge constraints (e.g., $\#\text{O}=1$ , $\#(\text{C,C})\geq 2$ )
Topological Roles	Defined by bond positions and connectivity	Orbit indices encoding structural symmetry via hashing
Logical Flexibility	Logical OR over pattern variants	Disjunctive Normal Form (DNF) clauses
Compositionality	Recursive conjunctions of conditions	Conjunctions of structural predicates
Generalization	Matches molecules not present in training data	Covers structural families beyond observed motifs
Implementation	Hand-crafted or mined patterns	Automatically induced via RDKit-compatible predicates

Appendix

Table 7: Conceptual correspondence between chemical SMARTS patterns and SymGraph ’s rules.

Figure 8: Visualization of the structural predicates identified by SymGraph for the BAMultiShapes dataset.

Figure 9: Visualization of the structural predicates identified by SymGraph for the BA2Motifs dataset.

Explore similar work

Invariant-Stratified Propagation for Expressive Graph Neural Networks
Mar 2, 2026Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe +1Graph Neural Networks GNN Expressivity
Department of Mechanical Engineering, University of Melbourne, Melbourne, Australia · School of Computing, Australian National University, Canberra, Australia · Data61, CSIRO, Canberra, Australia
Hierarchical Attention-based Graph Neural Network with Relevance-driven Pruning
May 10, 2026Seungwoo KumGraph Attention Networks Heterogeneous GNNs
Korea Electronics Technology Institute (KETI) Seongnam, Republic of Korea
Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning
Apr 13, 2026Xiaoxue Han, Libo Zhang, Zining Zhu +1GNN Explainability Text-Attributed Graph Learning
Department of Computer Science, Stevens Institute of Technology, Hoboken, NJ, USA.

Mar 2, 2026J/K move · Enter open · S save

Invariant-Stratified Propagation for Expressive Graph Neural Networks

Asela Hevapathige, Ahad N. Zehmakan, Asiri Wijesinghe, Saman Halgamuge

Department of Mechanical Engineering, University of Melbourne, Melbourne, Australia · School of Computing, Australian National University, Canberra, Australia · Data61, CSIRO, Canberra, Australia

Graph Neural Networks GNN Expressivity

Open paper AskPDF arXiv

Graph Neural Networks (GNNs) face fundamental limitations in expressivity and capturing structural heterogeneity. Standard message-passing architectures are constrained by the 1-dimensional Weisfeiler-Leman (1-WL) test, unable to distinguish graphs beyond degree sequences, and aggregate information uniformly from neighbors, failing to capture how nodes occupy different structural positions within higher-order patterns. While methods exist to achieve higher expressivity, they incur prohibitive computational costs and lack unified frameworks for flexibly encoding diverse structural properties. To address these limitations, we introduce Invariant-Stratified Propagation (ISP), a framework comprising both a novel WL variant (ISP-WL) and its efficient neural network implementation (ISPGNN). ISP stratifies nodes according to graph invariants, processing them in hierarchical strata that reveal structural distinctions invisible to 1-WL. Through hierarchical structural heterogeneity encoding, ISP quantifies differences in nodes' structural positions within higher-order patterns, distinguishing interactions where participants occupy different roles from those with uniform participation. We provide formal theoretical analysis establishing enhanced expressivity beyond 1-WL, convergence guarantees, and inherent resistance to oversmoothing. Extensive experiments across graph classification, node classification, and influence estimation demonstrate consistent improvements over standard architectures and state-of-the-art expressive baselines.

Abstract

Explore similar work

Invariant-Stratified Propagation for Expressive Graph Neural Networks

Hierarchical Attention-based Graph Neural Network with Relevance-driven Pruning

Exploring Concept Subspace for Self-explainable Text-Attributed Graph Learning