# An epistemic approach to model uncertainty in data-graphs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 54 references that are in the map.
- First posted on arXiv 29 Sep 2021.

## Builds on (most cited first, 11 of 11)

- [Knowledge Graphs](https://mlsanity.com/paper/2003.02320/) (2020)
- [HoloClean: Holistic Data Repairs with Probabilistic Inference](https://mlsanity.com/paper/1702.00820/) (2017)
- [A Survey of Community Search Over Big Graphs](https://mlsanity.com/paper/1904.12539/) (2019)
- [Skolemization for Weighted First-Order Model Counting](https://mlsanity.com/paper/1312.5378/) (2013)
- [Symbolic Querying of Vector Spaces: Probabilistic Databases Meets Relational Embeddings](https://mlsanity.com/paper/2002.10029/) (2020)
- [A Formal Framework For Probabilistic Unclean Databases](https://mlsanity.com/paper/1801.06750/) (2018)
- [Model Counting of Query Expressions: Limitations of Propositional Methods](https://mlsanity.com/paper/1312.4125/) (2013)
- [Understanding the Complexity of Lifted Inference and Asymmetric Weighted Model Counting](https://mlsanity.com/paper/1405.3250/) (2014)
- [Querying in the Age of Graph Databases and Knowledge Graphs](https://mlsanity.com/paper/2106.11456/) (2021)
- [Conjunctive Queries on Probabilistic Graphs: Combined Complexity](https://mlsanity.com/paper/1703.03201/) (2017)
- [Counting Problems over Incomplete Databases](https://mlsanity.com/paper/1912.11064/) (2019)

## Abstract (arXiv)

Graph databases are becoming widely successful as data models that allow to effectively represent and process complex relationships among various types of data. As with any other type of data repository, graph databases may suffer from errors and discrepancies with respect to the real-world data they intend to represent. In this work we explore the notion of probabilistic unclean graph databases, previously proposed for relational databases, in order to capture the idea that the observed (unclean) graph database is actually the noisy version of a clean one that correctly models the world but that we know partially. As the factors that may be involved in the observation can be many, e.g, all different types of clerical errors or unintended transformations of the data, we assume a probabilistic model that describes the distribution over all possible ways in which the clean (uncertain) database could have been polluted. Based on this model we define two computational problems: data cleaning and probabilistic query answering and study for both of them their corresponding complexity when considering that the transformation of the database can be caused by either removing (subset) or adding (superset) nodes and edges.