# A Neuro-Symbolic Approach for Probabilistic Reasoning on Graph Data

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 45 references that are in the map.
- First posted on arXiv 29 Jul 2025.

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

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (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)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Neural Probabilistic Logic Programming in DeepProbLog](https://mlsanity.com/paper/1907.08194/) (2019)
- [GraphVAE: Towards Generation of Small Graphs Using Variational Autoencoders](https://mlsanity.com/paper/1802.03480/) (2018)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)
- [Logic Tensor Networks](https://mlsanity.com/paper/2012.13635/) (2020)
- [Neural-Symbolic Learning and Reasoning: A Survey and Interpretation](https://mlsanity.com/paper/1711.03902/) (2017)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Graph Normalizing Flows](https://mlsanity.com/paper/1905.13177/) (2019)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [Graph Neural Networks Meet Neural-Symbolic Computing: A Survey and Perspective](https://mlsanity.com/paper/2003.00330/) (2020)
- [NeurASP: Embracing Neural Networks into Answer Set Programming](https://mlsanity.com/paper/2307.07700/) (2023)
- [GMNN: Graph Markov Neural Networks](https://mlsanity.com/paper/1905.06214/) (2019)
- [From Statistical Relational to Neuro-Symbolic Artificial Intelligence](https://mlsanity.com/paper/2003.08316/) (2020)
- [Efficient Probabilistic Logic Reasoning with Graph Neural Networks](https://mlsanity.com/paper/2001.11850/) (2020)
- [A-NeSI: A Scalable Approximate Method for Probabilistic Neurosymbolic Inference](https://mlsanity.com/paper/2212.12393/) (2022)
- [A Survey on Neural-symbolic Learning Systems](https://mlsanity.com/paper/2111.08164/) (2021)
- [NeuPSL: Neural Probabilistic Soft Logic](https://mlsanity.com/paper/2205.14268/) (2022)
- [VAEL: Bridging Variational Autoencoders and Probabilistic Logic Programming](https://mlsanity.com/paper/2202.04178/) (2022)
- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [Neural Markov Logic Networks](https://mlsanity.com/paper/1905.13462/) (2019)
- [Efficient Generation of Structured Objects with Constrained Adversarial Networks](https://mlsanity.com/paper/2007.13197/) (2020)
- [Controllable Neural Symbolic Regression](https://mlsanity.com/paper/2304.10336/) (2023)
- [Scalable Neural-Probabilistic Answer Set Programming](https://mlsanity.com/paper/2306.08397/) (2023)
- [On Performance Discrepancies Across Local Homophily Levels in Graph Neural Networks](https://mlsanity.com/paper/2306.05557/) (2023)
- [Beyond Graph Neural Networks with Lifted Relational Neural Networks](https://mlsanity.com/paper/2007.06286/) (2020)
- [Relational Bayesian Networks](https://mlsanity.com/paper/1302.1550/) (2013)

## Built on by (most cited first, 2 of 2)

- [Panning for Gold: Expanding Domain-Specific Knowledge Graphs with General Knowledge](https://mlsanity.com/paper/2601.10485/) (2026)
- [Auto-Formalizing Neuro-Symbolic Predictors](https://mlsanity.com/paper/2610.01519/) (2026)

## Abstract (arXiv)

Graph neural networks (GNNs) excel at predictive tasks on graph-structured data but often lack the ability to incorporate symbolic domain knowledge and perform general reasoning. Relational Bayesian Networks (RBNs), in contrast, enable fully generative probabilistic modeling over graph-like structures and support rich symbolic knowledge and probabilistic inference. This paper presents a neuro-symbolic framework that seamlessly integrates GNNs into RBNs, combining the learning strength of GNNs with the flexible reasoning capabilities of RBNs. We develop two implementations of this integration: one compiles GNNs directly into the native RBN language, while the other maintains the GNN as an external component. Both approaches preserve the semantics and computational properties of GNNs while fully aligning with the RBN modeling paradigm. We also propose a maximum a posteriori (MAP) inference method for these neuro-symbolic models. To demonstrate the framework's versatility, we apply it to two distinct problems. First, we transform a GNN for node classification into a collective classification model that explicitly models homo- and heterophilic label patterns, substantially improving accuracy on both synthetic and real-world datasets. Second, we introduce a multi-objective network optimization problem in environmental planning, where MAP inference and continuous numeric relaxation support a complex decision-making task. Both applications include new publicly available benchmark datasets. This work introduces a powerful and coherent neuro-symbolic approach to graph data, bridging learning and reasoning in ways that enable novel applications and improved performance across diverse tasks.