Automatic Strengthening of Graph-Structured Knowledge Bases

We consider the problem of identifying inherited content in knowledge representation structures called concept graphs (CGraphs). A CGraph is a visual representation of a concept; in the following, CGraphs and concepts are used synonymously. A CGraph is a node- and edge-labeled directed graph. Labeled (binary) edges represent relations between nodes, which are considered instances of the concepts in their node labels. CGraphs are arranged in a taxonomy (is-a hierarchy). The taxonomy is a directed acyclic graph, as multiple inheritance is allowed. A taxonomy and set of CGraphs is called a graph-structured knowledge base (GSKB). A CGraph can inherit content from other CGraphs — intuitively, if C and D are CGraphs, then C may contain content inherited from D, i.e. labeled nodes and edges \"from D\" can appear in C, if D is a direct or indirect superconcept of C, or if C contains a node being labeled with either D or some subclass of D. In both cases, C is said to refer to D. This paper contains three contributions. First, we describe and formalize the problem from a logical point of view and give a first-order semantics for CGraphs. We show that the identification of inherited content in CGraphs depends on some form of hypothetical reasoning and is thus not a purely deductive inference task, as it requires unsound reasoning. Hence, this inference is different from the standard subsumption checking problem, as known from description logics (DLs) [1]. We show that the provenance problem (from where does a logical atom in a CGraph get inherited?) strongly depends on the solution to the co-reference problem (which existentials in the first-order axiomatization of concepts as formulas denote identical domain individuals?) We demonstrate that the desired inferences can be obtained from a so-called strengthened GSKB, which is an augmented variant of the input GSKB. We present an algorithm which augments and strengthens an input GSKB, using model-theoretic notions. Secondly, we are addressing the problem from a graph-theoretic point of view, as this perspective is closer to the actual implementation. We show that we can identify inherited content by computing so-called concept coverings, which induce inherited content from superconcepts by means of graph morphisms. We argue that the algorithm solves a challenging (NP-hard) problem. Thirdly, we apply the algorithm to the large-scale biological knowledge base from the AURA project [2], and present a preliminary evaluation of its performance.