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

arXiv: https://arxiv.org/abs/2602.16947 · HTML: https://mlsanity.com/paper/2602.16947/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 30 references that are in the map.
- First posted on arXiv 18 Feb 2026.

## Builds on (most cited first, 15 of 15)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [GNNExplainer: Generating Explanations for Graph Neural Networks](https://mlsanity.com/paper/1903.03894/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Parameterized Explainer for Graph Neural Network](https://mlsanity.com/paper/2011.04573/) (2020)
- [XGNN: Towards Model-Level Explanations of Graph Neural Networks](https://mlsanity.com/paper/2006.02587/) (2020)
- [Graph Information Bottleneck for Subgraph Recognition](https://mlsanity.com/paper/2010.05563/) (2020)
- [Global Explainability of GNNs via Logic Combination of Learned Concepts](https://mlsanity.com/paper/2210.07147/) (2022)
- [KerGNNs: Interpretable Graph Neural Networks with Graph Kernels](https://mlsanity.com/paper/2201.00491/) (2022)
- [Global Concept-Based Interpretability for Graph Neural Networks via Neuron Analysis](https://mlsanity.com/paper/2208.10609/) (2022)
- [The Interpretable and Effective Graph Neural Additive Networks](https://mlsanity.com/paper/2406.01317/) (2024)
- [Towards Symbolic XAI -- Explanation Through Human Understandable Logical Relationships Between Features](https://mlsanity.com/paper/2408.17198/) (2024)

## Built on by (most cited first, 1 of 1)

- [Concept Graph Convolutions: Message Passing in the Concept Space](https://mlsanity.com/paper/2604.20082/) (2026)

## Abstract (arXiv)

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.