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

• URL: http://arxiv.org/abs/2602.16947v2
• Date: Mon, 23 Feb 2026 21:44:17 GMT
• Title: 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,
• Abstract summary: We propose SymGraph, a symbolic framework for self-explainable Graph Neural Networks (GNNs)<n>By replacing continuous message passing with discrete structural hashing and topological role-based aggregation, our architecture theoretically surpasses the 1-WL barrier.<n>We show that SymGraph achieves state-of-the-art performance, outperforming existing self-explainable GNNs.
• Score: 12.70345169123999
• License: http://creativecommons.org/licenses/by/4.0/
• 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.

Related papers

• A Boolean Function-Theoretic Framework for Expressivity in GNNs with Applications to Fair Graph Mining [0.0]
  We propose a novel expressivity framework for Graph Neural Networks (GNNs) grounded in Boolean function theory.<n>We show that SBI subsumes existing expressivity measures such as Weisfeiler-Lehman (WL), biconnectivity-based, and homomorphism-based frameworks.<n>We design a circuit-traversal-based fairness algorithm capable of handling subpopulations defined by high-complexity Boolean functions, such as parity.
  arXiv  Detail & Related papers  (2026-01-19T06:15:25Z)
• LGAN: An Efficient High-Order Graph Neural Network via the Line Graph Aggregation [12.813630209382426]
  We propose a novel Graph Aggregation Network (LGAN) that constructs a line graph from the induced subgraph centered at each node to perform the higher-order aggregation.<n>We theoretically prove that the LGAN possesses the greater expressive power than the 2-WL under injective aggregation assumptions.<n> Empirical evaluations on benchmarks demonstrate that the LGAN outperforms state-of-the-art k-WL-based GNNs, while offering better interpretability.
  arXiv  Detail & Related papers  (2025-12-11T15:23:46Z)
• GILT: An LLM-Free, Tuning-Free Graph Foundational Model for In-Context Learning [50.40400074353263]
  Graph Neural Networks (GNNs) are powerful tools for precessing relational data but often struggle to generalize to unseen graphs.<n>We introduce textbfGraph textbfIn-context textbfL textbfTransformer (GILT), a framework built on an LLM-free and tuning-free architecture.
  arXiv  Detail & Related papers  (2025-10-06T08:09:15Z)
• What Expressivity Theory Misses: Message Passing Complexity for GNNs [51.20749443004513]
  We argue that higher expressivity is not necessary for most real-world tasks as they rarely require expressivity beyond the basic WL test.<n>We propose Message Passing Complexity (MPC), a measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing.<n>MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory.
  arXiv  Detail & Related papers  (2025-09-01T08:44:49Z)
• Beyond Message Passing: Neural Graph Pattern Machine [50.78679002846741]
  We introduce the Neural Graph Pattern Machine (GPM), a novel framework that bypasses message passing by learning directly from graph substructures.<n>GPM efficiently extracts, encodes, and prioritizes task-relevant graph patterns, offering greater expressivity and improved ability to capture long-range dependencies.
  arXiv  Detail & Related papers  (2025-01-30T20:37:47Z)
• Boosting Graph Neural Network Expressivity with Learnable Lanczos Constraints [7.605749412696919]
  Graph Neural Networks (GNNs) excel in handling graph-structured data but often underperform in link prediction tasks.<n>We present a novel method to enhance the expressivity of GNNs by embedding induced subgraphs into the graph Laplacian matrix's eigenbasis.<n>We demonstrate the ability to distinguish graphs that are indistinguishable by 2-WL, while maintaining efficient time complexity.
  arXiv  Detail & Related papers  (2024-08-22T12:22:00Z)
• Two Heads Are Better Than One: Boosting Graph Sparse Training via Semantic and Topological Awareness [80.87683145376305]
  Graph Neural Networks (GNNs) excel in various graph learning tasks but face computational challenges when applied to large-scale graphs. We propose Graph Sparse Training ( GST), which dynamically manipulates sparsity at the data level. GST produces a sparse graph with maximum topological integrity and no performance degradation.
  arXiv  Detail & Related papers  (2024-02-02T09:10:35Z)
• Improving Expressivity of GNNs with Subgraph-specific Factor Embedded Normalization [30.86182962089487]
  Graph Neural Networks (GNNs) have emerged as a powerful category of learning architecture for handling graph-structured data. We propose a dedicated plug-and-play normalization scheme, termed as SUbgraph-sPEcific FactoR Embedded Normalization (SuperNorm)
  arXiv  Detail & Related papers  (2023-05-31T14:37:31Z)
• Representation Power of Graph Neural Networks: Improved Expressivity via Algebraic Analysis [124.97061497512804]
  We show that standard Graph Neural Networks (GNNs) produce more discriminative representations than the Weisfeiler-Lehman (WL) algorithm. We also show that simple convolutional architectures with white inputs, produce equivariant features that count the closed paths in the graph.
  arXiv  Detail & Related papers  (2022-05-19T18:40:25Z)
• Improving Graph Neural Network Expressivity via Subgraph Isomorphism Counting [63.04999833264299]
  "Graph Substructure Networks" (GSN) is a topologically-aware message passing scheme based on substructure encoding. We show that it is strictly more expressive than the Weisfeiler-Leman (WL) graph isomorphism test. We perform an extensive evaluation on graph classification and regression tasks and obtain state-of-the-art results in diverse real-world settings.
  arXiv  Detail & Related papers  (2020-06-16T15:30:31Z)
• Towards an Efficient and General Framework of Robust Training for Graph Neural Networks [96.93500886136532]
  Graph Neural Networks (GNNs) have made significant advances on several fundamental inference tasks. Despite GNNs' impressive performance, it has been observed that carefully crafted perturbations on graph structures lead them to make wrong predictions. We propose a general framework which leverages the greedy search algorithms and zeroth-order methods to obtain robust GNNs.
  arXiv  Detail & Related papers  (2020-02-25T15:17:58Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.