# Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data

arXiv: https://arxiv.org/abs/2606.11946 · HTML: https://mlsanity.com/paper/2606.11946/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 35 of its 62 references that are in the map.
- First posted on arXiv 10 Jun 2026.

## Builds on (most cited first, 30 of 35)

- [Retrieval-Augmented Generation for Knowledge-Intensive NLP Tasks](https://mlsanity.com/paper/2005.11401/) (2020)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Heterogeneous Graph Attention Network](https://mlsanity.com/paper/1903.07293/) (2019)
- [A Generalization of Transformer Networks to Graphs](https://mlsanity.com/paper/2012.09699/) (2020)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [Deep Graph Library: A Graph-Centric, Highly-Performant Package for Graph Neural Networks](https://mlsanity.com/paper/1909.01315/) (2019)
- [Zero-shot Recognition via Semantic Embeddings and Knowledge Graphs](https://mlsanity.com/paper/1803.08035/) (2018)
- [RelBench: A Benchmark for Deep Learning on Relational Databases](https://mlsanity.com/paper/2407.20060/) (2024)
- [CARTE: Pretraining and Transfer for Tabular Learning](https://mlsanity.com/paper/2402.16785/) (2024)
- [Scallop: A Language for Neurosymbolic Programming](https://mlsanity.com/paper/2304.04812/) (2023)
- [Graph Neural Networks with Local Graph Parameters](https://mlsanity.com/paper/2106.06707/) (2021)
- [Efficient Probabilistic Logic Reasoning with Graph Neural Networks](https://mlsanity.com/paper/2001.11850/) (2020)
- [Griffin: Towards a Graph-Centric Relational Database Foundation Model](https://mlsanity.com/paper/2505.05568/) (2025)
- [A Survey on Neural-symbolic Learning Systems](https://mlsanity.com/paper/2111.08164/) (2021)
- [Learning Differentiable Programs with Admissible Neural Heuristics](https://mlsanity.com/paper/2007.12101/) (2020)
- [Neuro-Symbolic AI: Explainability, Challenges, and Future Trends](https://mlsanity.com/paper/2411.04383/) (2024)
- [First-Order Logic with Counting: At Least, Weak Hanf Normal Forms Always Exist and Can Be Computed!](https://mlsanity.com/paper/1703.01122/) (2017)
- [Scikit-network: Graph Analysis in Python](https://mlsanity.com/paper/2009.07660/) (2020)
- [Stable Tuple Embeddings for Dynamic Databases](https://mlsanity.com/paper/2103.06766/) (2021)
- [A Logical View of GNN-Style Computation and the Role of Activation Functions](https://mlsanity.com/paper/2512.19332/) (2025)
- [On Algorithms Based on Finitely Many Homomorphism Counts](https://mlsanity.com/paper/2111.13269/) (2021)
- [Selecting Walk Schemes for Database Embedding](https://mlsanity.com/paper/2401.11215/) (2024)
- [Recursive querying of neural networks via weighted structures](https://mlsanity.com/paper/2601.03201/) (2026)
- [Generative Datalog with Continuous Distributions](https://mlsanity.com/paper/2001.06358/) (2020)
- [When do homomorphism counts help in query algorithms?](https://mlsanity.com/paper/2304.06294/) (2023)

## Abstract (arXiv)

The conventional approach to deep learning over relational databases applies neural models, such as Graph Neural Networks (GNNs), to a graph representation of the database. Recent approaches instead operate on databases directly, associating tuples with embeddings and extending query mechanisms to jointly process embeddings and relational content. Inspired by these developments, we introduce Neuro-Relational Programs (NRPs), a declarative query language for relational databases whose facts carry numeric vector embeddings. NRPs extend Datalog-style rules with operations that combine, aggregate, and transform embeddings, thereby interleaving relational reasoning and learnable neural components within a single formalism. This yields a general approach to neural computation over relational data: an NRP can be read both as a query plan with trainable components and as a neural architecture with relational structure built in. Natural syntactic fragments of NRPs recover existing architectures and query formalisms. Zero-ary NRPs correspond to non-adaptive query algorithms; monadic NRPs generalize GNN-style message passing and precisely capture Deep Homomorphism Networks, a connection that we extend to frontier-guarded NRPs over databases with row-ids. We characterize the expressive power of unrestricted NRPs with ReLU-FFN transformations by FOCQ, an extension of first-order logic with counting interpreted over real-weighted structures, yielding a precise connection with uniform TC0 over ordered databases. Together, these results establish NRPs as a broad declarative framework for querying and neural computation over relational data.