Pricing Symbolic Rules by What GNNs Leave Unlearned
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 can give a model family is given what the family computes; every realised gain splits exactly into this term plus repaid neural debt; and for a trained network with representation the value is , 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 of the target in three independent runs () 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
| Dataset | task | graphs | classes | splits used |
| MUTAG, PTC | binary classification | 188, 344 | 2 | CV |
| PROTEINS | binary classification | 1113 | 2 | CV, 80/10/10, random/size |
| NCI1 | binary classification | 4110 | 2 | CV, random/size |
| IMDB-BINARY | binary classification | 1000 | 2 | CV, 80/10/10, random/size |
| IMDB-MULTI | 3-class classification | 1500 | 3 | CV |
| COLLAB | 3-class classification | 5000 | 3 | CV, 80/10/10 |
| Experiment | model | hidden | lr | schedule | dropout | epochs | batch |
|---|---|---|---|---|---|---|---|
| WL/absorption/ledger (TU, 10-fold) | GIN, DeepSets | 64 | patience 100 | 0.5 | 350 | – | |
| Classical rules on ZINC/NCI1/PROTEINS | GIN, GINE | 128 | cosine | 0 | 200 | 128 | |
| Discovery, ZINC | GINE | 128 | cosine | 0 | 200 | 128 | |
| Discovery, molhiv | GINE (OGB feat.) | 256 | cosine | 0.5 | 80 | 128 | |
| Discovery, molbace/molbbbp | GINE (OGB feat.) | 256 | cosine | 0.5 | 100 | 32 | |
| Discovery, COLLAB/TU | GIN (degree tags) | 64 | cosine | 0 | 150 | 32 |
| MUTAG | PTC | PROTEINS | NCI1 | IMDB-B | IMDB-M | COLLAB | |
| 13.3 | 3.2 | 46.4 | 33.5 | 0 | 0 | 0 | |
| / | 0 / 0 | 0 / 0 | 0 / 0 | 0.12 / 0 | 0 / 0 | 0 / 0 | 0 / 0 |
| gain, DeepSets | |||||||
| gain, GIN |
| Dataset | observed gain | readout part | coordinate part | residual |
|---|---|---|---|---|
| COLLAB | [ ] | [ ] | ||
| NCI1 | [ ] | [ ] | ||
| PROTEINS | [ ] | [ ] |
| log-loss | accuracy | |||||
|---|---|---|---|---|---|---|
| Dataset | linear | MLP | log-MLP | linear | MLP | log-MLP |
| COLLAB | 0.518 | 0.468 | 0.470 | 0.751 | 0.790 | 0.792 |
| NCI1 | 0.484 | 0.479 | 0.474 | 0.783 | 0.788 | 0.783 |
| PROTEINS | 0.574 | 0.550 | 0.575 | 0.735 | 0.731 | 0.704 |
| IMDB-B | 0.516 | 0.533 | 0.529 | 0.726 | 0.724 | 0.721 |
| GIN | GINE | |||
| Rule | gain [95% CI] | gain [95% CI] | ||
| cycles (3–8) | 0.49 | [ ] | 0.59 | [ ] |
| triangles | 0.40 | [ ] | 0.64 | [ ] |
| spectrum | 0.85 | [ ] | 0.86 | [ ] |
| bond histogram | 0.86 | [ ] | 0.98 | [ ] |
| ring atoms | 0.94 | [ ] | 0.95 | [ ] |
| Dataset (metric) | seeds | plain | expert | discovered | gain vs. plain | gain vs. expert | first block ( ) |
| development | |||||||
| ZINC (MAE ) | 3 | 0.1911 | 0.1306 | 0.1196 | [.065, .077] | [.009, .012] | ring term (.001) |
| molhiv (AUC) | 8 | 0.7588 | 0.7871 | 0.7796 | [.010, .031] | [ .023, .010] | 12-ring, arom. (.001) |
| COLLAB (acc) | 5 | 0.7996 | 0.8072 | 0.8064 | [.000, .016] | [ .008, .006] | clustering (.001) |
| held out, frozen method | |||||||
| molbbbp (AUC) | 10 | 0.6421 | 0.6610 | 0.6768 | [.025, .045] | [.002, .030] | C 5 O 6-ring (.046) |
| ZINC (MAE, 3 seeds) | molhiv (AUC, 8 seeds) | COLLAB (acc, 5 seeds) | ||||
|---|---|---|---|---|---|---|
| Config | score | gain | score | gain | score | gain |
| plain | 0.1911 | – | 0.7588 | – | 0.7996 | – |
| expert rule | 0.1306 | [.056, .065] | 0.7871 | [.013, .042] | 0.8072 | [.001, .014] |
| blk 1 | 0.1181 | [.066, .079] | 0.7741 | [.007, .025] | 0.8064 | [.000, .016] |
| blk 2 | 0.1196 | [.065, .077] | 0.7796 | [.010, .031] | 0.8092 | [.002, .024] |
| blk 3 | 0.1215 | [.066, .076] | 0.7783 | [.005, .033] | 0.8052 | [ .003, .015] |
| Config | molbace (AUC) | molbbbp (AUC) | PROTEINS (acc) | IMDB-B (acc) | REDDIT-B (acc) |
|---|---|---|---|---|---|
| plain | 0.8084 | 0.6421 | 0.7786 | 0.7590 | 0.9175 |
| expert rule | [ .019, .018] | [.011, .027] | [ .023, .005] | [ .016, .009] | [ .011, .011] |
| blk 1 | [ .039, .002] | [.010, .031] | [ .015, .008] | [ .034, .005] | [ .006, .022] |
| blk 2 | [ .027, .014] | [.016, .046] | [ .030, .001] | [ .041, .002] | [ .014, .012] |
| blk 3 | [ .029, .008] | [.025, .044] | [ .016, .011] | [ .023, .010] | [ .017, .006] |
| random (size-matched) | [ .047, .001] | [.011, .033] | [ .015, .013] | [ .012, .015] | [ .009, .013] |
| Dataset | plain (random) | plain (shifted) | mean rule gain, random | mean rule gain, shifted |
|---|---|---|---|---|
| ogbg-molhiv | 0.828 | 0.756 | ||
| ogbg-molbace | 0.862 | 0.810 | ||
| ogbg-molbbbp | 0.954 | 0.664 | ||
| NCI1 | 0.813 | 0.564 | ||
| PROTEINS | 0.771 | 0.593 | ||
| IMDB-B | 0.716 | 0.744 |
Graph Neural Networks
Graph Neural Networks learn from graph-structured data by combining information across connected nodes, edges, and larger structures.
See all 782 papers