Warded Datalog+/- is a Datalog-based KRR language that guarantees decidability and tractability of the ontological reasoning task, thanks to its favourable theoretical properties. The Vadalog reasoning system exploits Warded Datalog+/- to provide a practical implementation of diferent reasoning tasks via basic isomorphism checks. However, these can be prohibitive in space and time complexity especially in the economic and financial context which is characterised by extreme-scale data stores and complex societal network dynamics. Recently, Knowledge Graph Embeddings (KGEs) have gained great interest in the scientific community and have extensively improved learning and knowledge discovery techniques. In this paper, we present and provide an experimental evaluation of Vada-ER, a framework that jointly uses logic-based reasoning and KGEs to provide a scalable alternative to basic isomorphism checks in ontological reasoning. With our work, we aim to improve the synergy between the reasoning and the embedding technologies and communities.
Isomorphism Check. The key for guaranteeing
termination of a chase-based procedure in reasoners is, in fact,
2. Preliminaries
defining points at which the chase may be terminated
prematurely, by dynamically pruning derivation branches,
while at the same time upholding correctness of the rea- In this section, we lay out the preliminary concepts of this
soning task. For instance, in Warded Datalog± the chase work including: chase, chase graph, query answering,
is restricted by isomorphism check, in the sense that and knowledge graph embeddings.
when two facts have the same predicate name, same con- Chase. The chase is considered among the fundamental
stants in the same positions and there exists a bijection algorithmic tools for a variety of database problems [13,
between the labelled nulls—i.e., they are isomorphic—just 14, 15, 16]. We consider a set Σ of tuple-generating
omnaetioofnthfoemrqiusecrryeaatneds winerthinegp.rYoecte,ssst,awnidtahroduitsloomssoorfpihnifsomr- d∃e¯pe(n¯d, e¯)n)ciweshTerGeDsa[n1d6] oafrethceonfojurnmct∀io¯n∀s¯(ofa(to¯m,¯)s. L→et
check could be ineficient, due to the impractical mem- us have a database = {ℰ , ℛ, ℱ }, where ℰ = {} is
orisation of all the produced facts, in many situations a set of entities, ℛ = {} is a set of -ary relations, and
tporolhimibiittitvheeinsesapracche sapnadcetimaned.Insofaocpt,titmheisree amree matotermyputss- oℱffac=ts.{The=c has(e1is, .a.p.r,oce)d|ure ∈(ℛΣ,,)∈thℰat}tiaskaessient
age, for instance, with Warded Datalog± it is possible to input a database and a set Σ of constraints and applies
restrict the search of isomorphic copies to specific por- the TGDs until all of them are satisfied (if terminating)
tions of the chase derivation graph, individuated by the and possibly generates nulls (labelled/marked nulls) to
fragment characteristics, namely the connected compo- satisfy existential quantification [
procedure in the form of a graph. The nodes of the graph represent the facts ℧ = (1, . . . , ), while the links represent the application of the rule, the dependency of the generated facts.
Query answering. Ontological query answering is
one of the fundamental tasks in databases and
knowledge representation. Given a set of existential rules Σ
and an n-ary predicate Ans, the evaluation of a query
= (Σ , Ans) over a database is defined as () =
{¯ ∈ dom() | Ans(¯) ∈ Σ( )}. Therefore, it is the
problem of answering queries with respect to both
and all the facts entailed from via Σ [
Knowledge graph embeddings. Embedding-based approaches obtain low dimensional representation for symbolic data (e.g., vector representation of nodes and edges in a graph) and aim at preserving the characteristics of original representation. A Knowledge Graph (KG) is deifned as = {ℰ , ℛ, ℱ }, where ℰ , ℛ are a set of entities (e.g. Bob, Apple) and (2-ary) relations (e.g. InvestorIn) respectively, and ℱ = {2(ℎ, ) = (ℎ, , )} ⊂ ℰ × ℛ × ℰ is a set of triples/facts.
Graph Embedding models (KGEs) have gained great interest in the scientific community. Achieving state-ofthe-art performance and accuracy, they are used for AI tasks such as link prediction, question answering, and recommendation systems. However, despite their potential, they are mainly employed for knowledge preparation learning rather than actual logic-based reasoning tasks.
Although there still is a perceived disconnect between the
two areas, injecting logical rules into embedding-oriented
approaches seems promising [
Contribution. In this paper we aim to bridge logic and embeddings to enable faster reasoning over large scale datasets and provide the following contributions: • We present Vada-ER, a framework which jointly uses logic-based reasoning and KGEs to achieve faster and more eficient query answering. • We introduce the distance termination strategy which Embeddings: For a given graph, ≿ is a mapping that employs embeddings for chase termination purposes. represents nodes as vectors in a -dimensional space We provide an experimental evaluation and show im- such that ≿ : ℰ → , where can be real R, complex provements in performance. C etc. The embedding of an entity ∈ ℰ is noted in boldface form i.e. = ≿() where ℎ denotes the head • We propose a chase graph generator methodology cap- and the tail entities. Depending on the formulation of turing both semantic and pattern features. a KGE model, each relation ∈ ℛ can be represented • We introduce chase graph embeddings to improve as a vector : ℛ → , matrix : ℛ → (1× 2), the traditional logic-based approach and enable n-ary tensor : ℛ → 1× 2× ...× , (where can be embedding-based reasoning for a novel hybrid solu- real R, complex C, etc), or a function (e.g the weights of tion for query answering. a neural network) : ℛ → . We use = { , } (initially randomized) to represent the embeddings of all entities ( ) and relations ( ) in a KG. In case a relation is represented as a function, denotes the parameters of the function.
edge, very little related work in the concrete area of using
embeddings to improve performance of the chase. One
example is [
produced during the chase procedure, instead of isoAs discussed in the introduction, termination strategies morphism check, Vada-ER computes the embedding are a key technique to ensure chase termination in distance from every existing fact and sets = Datalog± languages, such as Warded Datalog± , when min∈ℱ ( , ) (where ℱ is the set of all facts the chase starts producing isomorphic copies. We pro- in the th iteration of the chase) as the shortest dispose an alternative and novel termination strategy based tance. If is larger than a certain threshold , on embedding distance instead of isomorphism check. is generated and added to the chase graph. We observe that the first two rules lead to the generation Distance Termination Strategy. Our embedding-based of Funding(Apple, Sequoia, 1). At this point in the chase termination approach relies on the distance be- chase, Vada-ER checks if a similar fact was already tween fact embeddings (i.e. (, ), , ∈ generated by calculating the distance from the fact emR, , ∈ ℱ , where ℱ is the set of all facts obtained bedding of Company(Apple), InvestorFrom(Bob, Sequoia) during the chase) rather than basic isomorphism checks and InvestmentOfFrom(Apple, Bob, Sequoia). The shortin ontological reasoning. Given a Vadalog program, our est distance from the already generated facts is still larger Vada-ER framework builds the full chase graph and than the threshold and hence the fact can be added to learns fact embeddings = { | ∈ ℱ }. These are the chase. However, Funding(Apple, Sequoia, 2) is protrained to represent semantic and reasoning similarities. duced in the connected component resulting from rules Let us explain the procedure with an example. 3, 4, 5. Its embedding results are very close to the one Example 1. (isomorphic copies in chase) Program P con- produced in rule 2 as they have same predicate name and constants in the same positions and there is a bijection Σtaiannsdseat oqfueenrtyities., relations, facts = {ℰ , ℛ, ℱ }, rules of the labelled nulls. Therefore, Vada-ER stops to avoid generating the duplicate. ℰ = {Apple, Bob, Sequoia}, ℛ = {Company, InvestorFrom, InvestorIn}, HasPitched, SuccesfulPitch}, ℱ = {Company(Apple), InvestorFrom(Bob, Sequoia), InvestorIn(Bob, Apple), HasPitched(Apple), SuccesfulPitch(Apple)} Σ = { 1 : Company(), InvestorFrom(, ), InvestorIn(, ) → InvestmentOfFrom(, , ). 2 : InvestmentOfFrom(, , ) → ∃ Funding(, , ). 3 : Company() → ∃ MeetingWith(, ).
for termination purposes, Vada-ER employs the so called Distance Threshold which is defined below.
Definition 1. (Distance Threshold) Given a Vadalog program = {, Σ } and fact embeddings = { ∈ R| ∈ ℱ } and given a fact to be generated in the current chase step (ℎ step), we define the distance threshold as the minimal distance at which the closest fact to in the embedding space must be so that is generated. Then is generated when (, ) > and dropped when (, ) ≤ . 4 : MeetingWith(, ), HasPitched() → PitchedTo(, ).
5 : PitchedTo(, ), SuccesfulPitch() → ∃ Funding(, , ).} probability of generating duplicates with the number = {Funding(, , ) → ?.} of chase steps in our methodology, we propose to use a cumulative distance threshold which increases by ∆ In order to answer the query in this example, Vada- (the distance threshold step) in each iteration (), i.e. = ER generates the query chase graph, sketched on the − 1 + ∆ . This technique allows us to decrease, at each left-hand side of Figure 1. For each new fact chase step, the probability of producing new facts and obtain a homogeneous approximation of each chase tree. the latter representing an isomorphism class with all In order to update the distance threshold at each step, we of its instantiations in the semantic chase graph. That is, propose the equation = 0 +∑︀=1 − * 0 where 0 = ∪ ∪ with is the initial distance threshold, chosen as a parameter.
= {(, ) | (, _) ∈ ∨ (_, ) ∈ }
all facts in the same connected component in the warded We call those additional edges (as in connecting
forest [
Vada-ER can position facts in a multidimensional space that, if properly indexed, enables an eficient full check beyond the mere single connected component and guaranteeing low computational complexity, e.g. logarithmic in case of kd-trees.
phase is performed by the Embedding Layer which takes
in input the hybrid chase graph and returns a
vector for each fact = { | (, _) ∈ ∨ (_, ) ∈
} produced during the chase so that similar facts in
Preprocessing Phase. Vada-ER carries out two pre- terms of semantic and pattern features are closer in the
processing steps to generate the embeddings used in the embedding space. This is the prerequisite to successfully
distance termination strategy. These are the Chase Graph use embeddings for reasoning purposes. We obtain an
Generator and Embedding Layer. The Chase Graph Gen- embedding space in which nodes belonging to the same
erator layer generates the chase graph for the execution chase tree are close to each other, grouped in what we
of a given Vadalog program and a set of facts represent- call reasoning clusters. For this purpose various suitable
ing the underlying knowledge. This step itself includes state-of-the-art embedding models are DeepWalk [
advantages compared to the usual termination strategies. It wins at run time, as the learning procedure is carried on during the preprocessing steps and the model used at run time. Moreover, our approach is not only capable of recognising two isomorphic facts but even finding semantic and pattern similarity between facts that may lead to isomorphism in following steps.
Semantic chase graph. The first step of the preprocessing phase is the Chase Graph Generator which constructs what we call the hybrid chase graph. In a first step, we take the standard chase graph (i.e., where facts are nodes and rule applications are edges) and enhance it with the following additional edges: for each rule application, all atoms in the body are also connected via edges. We call this the semantic chase graph , given that it improves the semantic understanding of the reasoning process for the later embedding step.
and recall using both real-world and complex synthetic
Vadalog programs [
This work has taken one foundational step towards bridging logic-based and embedding-based reasoning, by answering the question: can embedding-based reasoning