Chaudhri, V. and Dinesh, N. and Heymans, S. and Wessel, M. Automatic Strengthening of Graph-Structured Knowledge Bases, in 3rd International Workshop on Graph Structures for Knowledge Representation and Reasoning, 2013.
Abstract
We address two problems in underspecified graphstructured knowledge bases (GSKBs): the coreference and the provenance problem. Both problems are important for a variety of reasons. The former asks “Which existentially quantified variables in different but related axioms of a GSKB possibly denote identical domain individuals?”, and the latter “From which axioms in a GSKB is a piece of knowledge getting derived?” To decide the former, we need to be able to prove equality between different variables – a GSKB in which this is possible is called a strengthened GSKB, and an underspecified GSKB otherwise. The latter occur naturally in many knowledge acquisition contexts, and are also easier to author. We hence present an algorithm which rewrites an underspecified GSKB into
a strengthened GSKB, by virtue of Skolemization and addition of equality atoms such that the coreference information can be drawn from it. This enlarges the logical theory (the deductive closure) of the GSKB and strengthens its inferential power, hence affecting the provenance information. Our algorithm is model-theoretic in nature and exploits a novel class of desirable, preferred models, which
capture the desired co-references. The algorithm is a logical reconstruction of an implemented algorithm that we successfully applied to a large-scale biological knowledge base, in which it identified more that 22,000 equality atoms.