Computing and Maintaining Provenance of Query Result Probabilities in\n Uncertain Knowledge Graphs

Knowledge graphs (KG) that model the relationships between entities as\nlabeled edges (or facts) in a graph are mostly constructed using a suite of\nautomated extractors, thereby inherently leading to uncertainty in the\nextracted facts. Modeling the uncertainty as probabilistic confidence scores\nresults in a probabilistic knowledge graph. Graph queries over such\nprobabilistic KGs require answer computation along with the computation of\nthose result probabilities, aka, probabilistic inference. We propose a system,\nHAPPI (How Provenance of Probabilistic Inference), to handle such query\nprocessing. Complying with the standard provenance semiring model, we propose a\nnovel commutative semiring to symbolically compute the probability of the\nresult of a query. These provenance-polynomiallike symbolic expressions encode\nfine-grained information about the probability computation process. We leverage\nthis encoding to efficiently compute as well as maintain the probability of\nresults as the underlying KG changes. Focusing on a popular class of\nconjunctive basic graph pattern queries on the KG, we compare the performance\nof HAPPI against a possible-world model of computation and a knowledge\ncompilation tool over two large datasets. We also propose an adaptive system\nthat leverages the strengths of both HAPPI and compilation based techniques.\nSince existing systems for probabilistic databases mostly focus on query\ncomputation, they default to re-computation when facts in the KG are updated.\nHAPPI, on the other hand, does not just perform probabilistic inference and\nmaintain their provenance, but also provides a mechanism to incrementally\nmaintain them as the KG changes. We extend this maintainability as part of our\nproposed adaptive system.\n