Introduction to knowledge graphs (section 4.3): Deductive knowledge – Reasoning

This article is section 4.3 of part 4 of the Introduction to knowledge graphs series of articles. Recent research has identified the development of knowledge graphs as an important aspect of artificial intelligence (AI) in knowledge management (KM).

Hogan and colleagues’ comprehensive tutorial article¹ now describes practical reasoning algorithms using rules and description logics.

Given two graphs, deciding if the first entails the second—per all of the features in Tables 1–3—is undecidable: No (finite) algorithm for such entailment can exist that halts on all inputs with the correct true/false answer. However, we can provide practical reasoning algorithms for ontologies that (1) halt on any input ontology but may miss entailments, returning false instead of true, (2) always halt with the correct answer but only accept input ontologies with restricted features, or (3) only return correct answers for any input ontology but may never halt on certain inputs. Though option (3) has been explored using, e.g., theorem provers for first order logic, options (1) and (2) are more commonly pursued using rules and/or description logics. Option (1) often allows for more efficient and scalable reasoning algorithms and is useful where data are incomplete and having some entailments is valuable. Option (2) may be a better choice in domains—such as medical ontologies—where missing entailments may have undesirable outcomes.

Rules

A straightforward way to implement reasoning is through inference rules (or simply rules), composed of a body (IF) and a head (THEN). Both the body and head are given as graph patterns. A rule indicates that if we can replace the variables of the body with terms from the data graph and form a subgraph of a given data graph, then using the same replacement of variables in the head will yield a valid entailment. The head must typically use a subset of the variables appearing in the body to ensure that the conclusion leaves no variables unreplaced. Rules of this form correspond to (positive) Datalog in databases, Horn clauses in logic programming, and so on.

Rules can be used to capture entailments under ontological conditions. Here, we provide an example of two rules for capturing some of the entailments valid for SUBCLASS:

A comprehensive set of rules for OWL have been standardised as OWL 2 RL/RDF. These rules are, however, incomplete, as such rules cannot fully capture negation (e.g., COMPLEMENT), existentials (e.g., SOME VALUES), universals (e.g., ALL VALUES), or counting (e.g., CARDINALITY and QUALIFIED CARDINALITY). Other rule languages can, however, support additional such features, including existentials (see, e.g., Datalog^±), disjunction (see, e.g., Disjunctive Datalog), and so on.

Rules can be used for reasoning in a number of ways. Materialisation applies rules recursively to a graph, adding entailments back to the graph until nothing new can be added. The materialised graph can then be treated as any other graph; however, the materialised graph may become unfeasibly large to manage. Another strategy is to use rules for query rewriting, which extends an input query to find entailed solutions. Figure 13 provides an example ontology whose rules are used to rewrite the query of Figure 12; if evaluated over the graph of Figure 1, then will be returned as a solution. While not all ontological features can be supported in this manner, query rewriting is sufficient to support complete reasoning over lightweight ontology languages.

While rules can be used to (partially) capture ontological entailments, they can also be defined independently of an ontology, capturing entailments for a given domain. In fact, some rules—such as the following—cannot be emulated with the ontology features previously seen, as they do not support ways to infer binary relations from cyclical graph patterns (for computability reasons):

Various languages allow for expressing rules over graphs (possibly alongside ontological definitions) including: Rule Interchange Format (RIF), Semantic Web Rule Language, and so on.

Description Logic

Description logics (DLs) hold an important place in the logical formalisation of knowledge graphs: They were initially introduced as a way to formalise the meaning of frames and semantic networks (which can be seen as predecessors of knowledge graphs) and also heavily influenced OWL. DLs are a family of logics rather than a particular logic. Initially, DLs were restricted fragments of first order logic (FOL) that permit decidable reasoning tasks, such as entailment checking. DLs would later be extended with useful features for modelling graph data that go beyond FOL, such as transitive closure, datatypes, and so on. Different DLs strike different balances between expressive power and the computational complexity of reasoning.

DLs are based on three types of elements: individuals, such as Santiago; classes (a.k.a. concepts) such as City; and properties (a.k.a. roles) such as flight. DLs then allow for making claims, known as axioms, about these elements. Assertional axioms can be either unary class relations on individuals, such as City(Santiago), or binary property relations on individuals, such as flight(Santiago,Arica). Such axioms form the Assertional Box (A-Box). DLs further introduce logical symbols to allow for defining class axioms (forming the Terminology Box, or T-Box for short) and property axioms (forming the Role Box, or R-Box); for example, the class axiom City ⊑ Place states that the former class is a subclass of the latter one, while the property axiom flight ⊑ connectsTo states that the former property is a subproperty of the latter one. DLs also allow for defining classes based on existing terms; for example, we can define a class ∃nearby.Airport as the class of individuals that have some airport(s) nearby. Noting that the symbol ⊤ is used in DLs to denote the class of all individuals, we can then add a class axiom ∃flight.⊤ ⊑ ∃nearby.Airport to state that individuals with an outgoing flight must have some airport nearby. Noting that the symbol ⊔ can be used in DL to define that a class is the union of other classes, we can further define that Airport ⊑ DomesticAirport⊔InternationalAirport, i.e., that an airport is either a domestic airport or an international airport (or both).

The similarities between DLs and OWL are not coincidental: The OWL standard was heavily influenced by DLs, where the OWL 2 DL language is a restricted fragment of OWL with decidable entailment. To exemplify one such restriction, with DomesticAirport ⊑ =1 destination ◦ country.⊤, we can define in DL syntax that domestic airports have flights destined to precisely one country (where p ◦ q denotes a chain of properties). However, counting chains is often disallowed in DLs to ensure decidability.

Expressive DLs support complex entailments involving existentials, universals, counting, and so on. A common strategy for deciding such entailments is to reduce entailment to satisfiability, which decides if an ontology is consistent or not. Thereafter methods such as tableau can be used to check satisfiability, cautiously constructing models by completing them along similar lines to the materialisation strategy previously described, but additionally branching models in the case of disjunction, introducing new elements to represent existentials, and so on. If any model is successfully “completed,” then the process concludes that the original definitions are satisfiable. Due to their prohibitive computational complexity, such reasoning strategies are not typically applied to large-scale data, but may be useful when modelling complex domains.

Next part (part 5): Inductive knowledge.

Header image source: Crow Intelligence, CC BY-NC-SA 4.0.

References: