Research map / Graph learning / Knowledge and temporal graphs
Understanding Expressivity of GNN in Rule Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Unifies tail-entity-scoring KG GNNs (NBFNet, RED-GNN) as QL-GNN, characterizes the rule structures they can learn via graded modal logic, and proposes EL-GNN, an entity-labeling trick that expands learnable rules.
Problem
Theoretical understanding of which rule structures state-of-the-art tail-entity-scoring GNNs for knowledge graph reasoning can learn is lacking or limited to single-relational graphs.
Approach
Unify NBFNet/RED-GNN into a query-labeling GNN (QL-GNN), analyze logical expressivity using graded modal logic extended with constants for the query entity, and add unique initial labels to high out-degree entities (EL-GNN) so that more rule structures become learnable.
Key results
- On synthetic dataset U, EL-NBFNet reaches 0.838 accuracy versus 0.541 for NBFNet and 0.405 for RED-GNN, while QL-GNN models reach 1.0 on C3, C4, I1, I2, T.
- EL-NBFNet achieves 0.332 on FB15k-237 and 0.842 on Kinship, improving over NBFNet's 0.320 and 0.819.
- CompGCN and R-GCN score near chance (about 0.01 to 0.07) on all synthetic datasets, consistent with theory that they cannot learn connected rule structures.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| apply entity labeling to RED-GNN | RED-GNN · Family | accuracy: 0.988±0.002 -> 0.990±0.002 | Helped |
| apply entity labeling to NBFNet | NBFNet · Family | accuracy: 0.977±0.001 -> 0.985±0.001 | Helped |
| apply entity labeling to RED-GNN | RED-GNN · Kinship | accuracy: 0.820±0.003 -> 0.839±0.001 | Helped |
| apply entity labeling to NBFNet | NBFNet · Kinship | accuracy: 0.819±0.002 -> 0.842±0.003 | Helped |
| apply entity labeling to RED-GNN | RED-GNN · UMLS | accuracy: 0.946±0.001 -> 0.952±0.003 | Helped |
| apply entity labeling to NBFNet | NBFNet · UMLS | accuracy: 0.946±0.002 -> 0.953±0.002 | Helped |
| apply entity labeling to RED-GNN | RED-GNN · WN18RR | accuracy: 0.502±0.001 -> 0.504±0.001 | Helped |
| apply entity labeling to NBFNet | NBFNet · WN18RR | accuracy: 0.496±0.002 -> 0.501±0.003 | Helped |
| apply entity labeling to RED-GNN | RED-GNN · FB15k-237 | accuracy: 0.284±0.002 -> 0.322±0.002 | Helped |
| apply entity labeling to NBFNet | NBFNet · FB15k-237 | accuracy: 0.320±0.001 -> 0.332±0.001 | Helped |
| apply entity labeling to RED-GNN | RED-GNN · Synthetic U | accuracy: 0.405 -> 0.797 | Helped |
| apply entity labeling to NBFNet | NBFNet · Synthetic U | accuracy: 0.541 -> 0.838 | Helped |
Surprising findings
- Classical methods such as CompGCN learn only non-structural rules, so they fail even on simple chain-like synthetic structures.
Limitations
- Theory does not directly cover learning multiple rule structures simultaneously.
- Degree threshold d must be tuned; too small or large values hurt performance.
Experimental setup
Datasets: Family Kinship UMLS WN18RR FB15k-237 synthetic rule-structure KGs (C3, C4, I1, I2, T, U)
Benchmarks: Family Kinship UMLS WN18RR FB15k-237 synthetic datasets C3, C4, I1, I2, T, U
Metrics: accuracy standard deviation
Baselines: R-GCN CompGCN RotatE QuatE Neural LP DRUM RED-GNN NBFNet
Builds on: NBFNet RED-GNN CompGCN graded modal logic labeling trick
Closest papers by meaning
- Rule-Guided Graph Neural Networks for Explainable Knowledge Graph Reasoning (AAAI 2025 · similarity 0.90)
- GraphTrail: Translating GNN Predictions into Human-Interpretable Logical Rules (NeurIPS 2024 · similarity 0.87)
- Systematic Relational Reasoning With Epistemic Graph Neural Networks (ICLR 2025 · similarity 0.87)
- Sound Logical Explanations for Mean Aggregation Graph Neural Networks (NeurIPS 2025 · similarity 0.86)
- Self-Interpretable Graph Learning with Sufficient and Necessary Explanations (AAAI 2024 · similarity 0.86)
- Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.