A New Approach to Pricing GNN Rules: Precisely Quantifying the Value of Symbolic Rules with Mutual Information

New research uses mutual information to precisely quantify symbolic rule value, turning rule design into statistical discovery, finding hidden cycle terms on ZINC that beat expert rules.
This paper proposes a mutual-information-based rule pricing framework, arguing that the value of a symbolic rule should be quantified as the label information the model fails to learn from data, i.e., conditional mutual information I(Y;S|T), rather than the theoretical upper bound of GNN expressiveness. Accordingly, the researchers turn rule design into rule discovery: scoring candidate rules on out-of-fold residuals, with permutation tests and family-wise error control for statistical significance. On the ZINC molecular dataset, the method automatically discovers the hidden cycle term max(0,ℓ_max-6), outperforming expert rules; when frozen and applied to five unseen datasets, it generalizes well, and on BBBP it significantly outperforms plain networks and expert rules. This work provides a theoretically rigorous and computable method for pricing and discovering symbolic knowledge for GNN integration.
Graph neural networks (GNNs) have limited expressive power, which is often cited as the reason for incorporating symbolic knowledge (e.g., motif counts, cycle counts, label constraints). But a new study proposes a more precise metric: the value of a rule should depend on the amount of label information the model fails to learn from data. This method turns rule design into rule discovery and successfully uncovers hidden cycle terms in experiments, outperforming expert-designed rules.

Limitations of Traditional Methods and the Mutual Information Perspective
Previous studies often use the theoretical upper bound of GNN expressive power as the basis for introducing symbolic rules, but this "ruler" is not precise enough. The new study points out that the maximum log-loss reduction a rule $S$ can bring to a model family is $I(Y;S|\sigma)$, i.e., the mutual information between the rule and the label given the model's computational capacity. The actual gain obtained can be precisely decomposed into this mutual information term plus the "repaid neural debt"—the information gap the model originally owed due to insufficient expressive power. For a trained network, the value of a rule under its representation $T$ is $I(Y;S|T)$, i.e., the label information that training failed to extract. This perspective directly links the value of a rule to the model's actual learning state, rather than relying on generalization upper bounds.
Mutual information is a measure in information theory of the statistical dependence between two random variables, defined as $I(X;Y)=H(Y)-H(Y|X)$, where $H$ is entropy. In this context, $I(Y;S|\sigma)$ represents the amount of information about the label $Y$ contained in rule $S$, given the model's computational capacity $\sigma$—i.e., the label uncertainty the rule can help reduce. The conditional mutual information $I(Y;S|T)$ further conditions on the model's learned representation $T$, characterizing the label information in the rule that the model has not yet captured. Mutual information is non-negative and zero if and only if the two variables are conditionally independent, making it naturally suitable as a measure of rule value: if the rule and label remain statistically correlated given the model representation, it indicates that the model has failed to extract this information and the rule has incremental value.
Rule Discovery: Residual-Based Statistical Testing
Based on the above theory, the researchers transform rule design into rule discovery: scoring candidate rules on the out-of-fold residuals of the network output and using a calibrated permutation null distribution to control the family-wise error rate. Specifically, they use a trained GNN to compute residuals for each sample, then evaluate whether candidate rules (e.g., cycle counts, motif counts) can significantly explain the label information in the residuals. A permutation test generates the null distribution to ensure the discovered rules are statistically significant. This approach does not rely on expert priors but lets the data "speak."
Out-of-fold residuals are the prediction errors of a model on samples not used in its training, obtained through cross-validation. Specifically, the data is divided into several folds; the model is trained on the remaining folds and used to predict the current fold in turn, ensuring that each sample's residual comes from a model that has not seen that sample. This avoids residuals being artificially small due to overfitting, making the residuals more faithfully reflect the label variation the model fails to explain. In rule discovery, analyzing the association between out-of-fold residuals and candidate rules more reliably identifies whether a rule carries information missed by the model.
Permutation test is a non-parametric statistical test method that generates a null distribution of the test statistic by randomly shuffling the sample labels (or rule values), thereby computing p-values without relying on distributional assumptions. In this paper, for each candidate rule, the researchers repeatedly permute labels and recompute the association statistic between residuals and the rule to build a null distribution, then compare the actual statistic to determine significance. To control false positives from testing multiple rules simultaneously, they adopt family-wise error rate control, such as Bonferroni correction or the max-T permutation method, ensuring the overall error rate does not exceed a preset level.
Experimental Validation: Discovery of Cycle Terms on the ZINC Dataset
On the ZINC molecular dataset, the method discovered the hidden cycle term $\max(0,\ell_{\max}-6)$ in the target in three independent runs (adjusted p-value = 0.001), and outperformed expert-designed cycle-counting rules. This shows that the method can automatically identify symbolic features truly useful for the prediction task. More subtly, when the rule was frozen and applied to five unseen datasets, its performance was never significantly worse than a plain network or expert rules, and on the BBBP dataset it was even significantly better than both. This demonstrates that the discovered rule has good generalization ability.
The ZINC dataset is a commonly used benchmark for molecular property prediction in the graph neural network field, containing about 250,000 drug-like molecules, with the task typically being to predict aqueous solubility (logP or logD). Molecules in this dataset are represented as graphs, with atoms as nodes and chemical bonds as edges. Ring structures are important topological features of molecular graphs, and ring size and count are often correlated with physicochemical properties. The rule discovered in this paper, $\max(0,\ell_{\max}-6)$, means: when the size of the largest ring in the molecule $\ell_{\max}$ exceeds 6, take the excess as the feature value; otherwise zero. This rule encodes "the nonlinear effect of large rings on properties," a hidden term not explicitly included in expert rules.
The BBBP dataset (Blood-Brain Barrier Penetration) is another molecular graph dataset, used to predict whether a compound can cross the blood-brain barrier, a binary classification task. This dataset has a smaller sample size and class imbalance, placing higher demands on model generalization. The rule discovered in this paper significantly outperforms plain GNNs and expert rules on BBBP, indicating that it captures general chemical patterns across datasets.
Significance and Outlook
This study provides a theoretically rigorous pricing framework for the integration of symbolic rules and GNNs. Through mutual information decomposition, the value of rules becomes computable and comparable, and the rule discovery process gains statistical rigor. In the future, this method may be extended to more complex types of symbolic knowledge, advancing the development of interpretable and efficient graph learning systems.
According to the research team, they plan to further explore the applicability of this framework to graph data in more domains and open-source the relevant code to facilitate community validation.
One-line Summary
A new study uses mutual information to precisely quantify the value of symbolic rules, turning rule design into statistical discovery, and discovers hidden cycle terms on ZINC that outperform expert rules.
Paragraph Summary
This paper proposes a mutual-information-based rule pricing framework, arguing that the value of a symbolic rule should be quantified as the amount of label information the model fails to learn from data, i.e., the conditional mutual information I(Y;S|T), rather than relying on the theoretical upper bound of GNN expressive power. Based on this, the researchers transform rule design into rule discovery: scoring candidate rules on out-of-fold residuals and using permutation tests and family-wise error control to ensure statistical significance. On the ZINC molecular dataset, the method automatically discovers the hidden cycle term max(0,ℓ_max-6), outperforming expert rules; when frozen and applied to five unseen datasets, the rule generalizes well, and on BBBP it significantly outperforms plain networks and expert rules. This work provides a theoretically rigorous and computable method for pricing and discovering symbolic knowledge for integration with GNNs.
Related articles

Why You Shouldn't Run the Hermes Agent on Your Personal Computer
Why shouldn't you run autonomous AI agents like Hermes on your personal computer? This article analyzes why agents should be deployed to a dedicated VPS instead of your primary device, from four angles: security risks, resource consumption, credential leakage, and autonomy requirements—plus the practical logic of isolated deployment.

Ignite Keynote: Building a Frontier Ecosystem to Bring AI to Life
Microsoft CEO Nadella's Ignite keynote proposes a frontier ecosystem to turn AI advances into real-world impact. This article unpacks the strategy's ecosystem layers and deployment signals.
C++26 Standard Finalized: Key Takeaway…
C++26 Standard Finalized: Key Takeaways from the ISO C++ Meeting
C++26 wraps up at the ISO C++ meeting. This article explains the trip report's implications, the standardization process, and impact on developers and compiler ecosystems.