cs.NENov 9, 2026

Pricing Symbolic Rules by What GNNs Leave Unlearned

Authors: Satabarto Sarkar, Prithwineel Paul

Organizations: Department of Computer Science and Engineering, University of Engineering and Management, Kolkata 700091, India

Abstract

Symbolic knowledge (motif counts, ring counts, label constraints) is routinely added to graph neural networks (GNNs) and justified by their limited expressivity. We replace this yardstick with an exact one. The largest log-loss reduction a rule SS can give a model family is I(Y;S∣σ)I(Y;S\midσ) given what the family computes; every realised gain splits exactly into this term plus repaid neural debt; and for a trained network with representation TT the value is I(Y;S∣T)I(Y;S\mid T), the label information training failed to extract. Rule design thus becomes rule discovery: we score candidates on the network's out-of-fold residual against calibrated permutation nulls with family-wise error control. On ZINC, discovery recovers the hidden ring term max⁡(0,ℓmax⁡−6)\max(0,\ell_{\max}-6) of the target in three independent runs (padj=0.001p_{\mathrm{adj}}=0.001) and beats expert cycle counts; frozen and applied to five unseen datasets it is never significantly worse than the plain network or the expert rule, and on BBBP it significantly beats both.

Figures & tables

Explore similar work

CardsList
  1. When Design Rules Break: Benchmark Composition Determines Whether Label Informativeness Predicts GNN Aggregator Choice

    Jun 8, 2026Neha Sharma, Ritesh SharmaGraph Neural NetworksNode Classification

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

    Feb 18, 2026Chuqin Geng, Li Zhang, Haolin Ye +5Graph Representation LearningGNN Explainability

  3. Neural Proposals, Symbolic Guarantees: Neuro-Symbolic Graph Generative Modeling

    Feb 18, 2026Chuqin Geng, Li Zhang, Mark Zhang +3Constrained Generative ModelingSatisfiability Modulo Theories