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

2026-02-18 · Chuqin Geng, Li Zhang, Haolin Ye, Ziyu Zhao, Yuhe Jiang, Tara Saba, Xinyu Wang, Xujie Si 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.

📄 PDF Abstract BibTeX arXiv:2602.16947

Code (0)

등록된 구현이 없습니다.

Tasks

Graph Learning Drug Discovery

VS-Graph: Scalable and Efficient Graph Classification Using Hyperdimensional Computing

2025-12-03 · Hamed Poursiami, Shay Snyder, Guojing Cong, Thomas Potok 외 arxiv

Graph classification is a fundamental task in domains ranging from molecular property prediction to materials design. While graph neural networks (GNNs) achieve strong performance by learning expressive representations v…

Molecular Property Prediction Graph Classification Graph Learning

Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification

2022-03-22 · Zhaohui Wang, Qi Cao, HuaWei Shen, Bingbing Xu 외

The expressive power of message passing GNNs is upper-bounded by Weisfeiler-Lehman (WL) test. To achieve high expressive GNNs beyond WL test, we propose a novel graph isomorphism test method, namely Twin-WL, which simult…

Classification Graph Classification Vocal Bursts Intensity Prediction

How Powerful are K-hop Message Passing Graph Neural Networks

2022-05-26 · Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar 외

The most popular design paradigm for Graph Neural Networks (GNNs) is 1-hop message passing -- aggregating information from 1-hop neighbors repeatedly. However, the expressive power of 1-hop message passing is bounded by …

EDEN: A Plug-in Equivariant Distance Encoding to Beyond the 1-WL Test

2022-11-19 · Chang Liu, Yuwen Yang, Yue Ding, Hongtao Lu

The message-passing scheme is the core of graph representation learning. While most existing message-passing graph neural networks (MPNNs) are permutation-invariant in graph-level representation learning and permutation-…

Graph Representation Learning Representation Learning

Expressive Power of Temporal Message Passing

2024-08-19 · Przemysław Andrzej Wałęga, Michael Rawson

Graph neural networks (GNNs) have recently been adapted to temporal settings, often employing temporal versions of the message-passing mechanism known from GNNs. We divide temporal message passing mechanisms from literat…