NeoMaPy: A Framework for Computing MAP Inference on Temporal Knowledge Graphs

1 Introduction

Markov Logic Networks (MLNs) [Richardson and Domingos, 2006; Domingos and Lowd, 2019] are a very useful conceptual tool for reasoning over uncertain facts. They combine Markov networks and First Order Logic, by attaching weights to logic formulae. Several MLNs extensions have been devised to work on different types of data [Snidaro et al., 2015; Chekol et al., 2016; Rinc´e et al., 2018]. Those uncertain temporal facts generate conflicts. Reasoning on those facts often requires to resolve those conflicts, i.e., to find consistent sets of facts useful for multi-agent tasks, production of hypotheses in history, global analysis, etc.

MLNs help find the most probable state of the world, gathering a set of facts whose weights have maximal probabilities with a process called Maximum A-Posteriori inference (MAP) [Niu et al., 2011; Riedel, 2012; Noessner et al., 2013; Sarkhel et al., 2014]. However, the state of the art integrating temporal information into MLN is insufficient, and computing the MAP inference usually relies on a heavy data mining process which checks rules application on possible facts [Chekol et al., 2017b]. It may be optimized by aggregating some formulae and by parallelizing the mining, but the complexity of those pessimistic approaches remains highly dependent on the number of possibilities.

We have recently introduced an extension of MLNs called Temporal Markov Logic Networks (TMLN) [David et al., 2022], along with a temporal semantics which may be configured through 3 categories of functions. We have devised key principles on the semantics for MAP inference, to reach desirable properties, and examined total and partial

(in)consistency relations between temporal formulae. Our completely different approach to MAP inference relies on building compatible worlds instead of mining valid worlds.

In this paper, we now introduce the NeoMaPy framework, a complete implementation of our approach for TMLN reasoning 1 . To achieve this, we extract a conflict graph between facts [Bertossi, 2011; Hipel et al., 2020], based on the rules and the nodes weights. Thus, the MAP inference now searches combinations of non-conflict graphs. This optimistic approach allows to parameterize MAP inferences with various semantics, computing efficiently with a heuristic and interacting with results for explaining choices of facts.

2 Background Concepts

2.1 Temporal Markov Logic Networks

Temporal Markov Logic Networks are based on a Temporal Many-Sorted First-Order Logic TF-FOL which combines formulae and temporal predicates from a temporal domain, to represent temporal facts and rules (more details are presented in [David et al., 2022]). Temporal Markov Logic Networks associate a degree of certainty to each formula.

A TMLNM= (F,R) is a set of weighted temporal facts F and R are sets of pairs such that:

• F = {(ϕ1, w1),. . . , (ϕn, wn)} with ∀i ∈ {1,. . . , n}, ϕi ∈ TF-FOL such that it is a ground formula (i.e., without variable, see Table 1) and wi ∈ [0,∞[,
• R = {(ϕ′1 , w′1 ),. . . , (ϕ′k , w′k )} with ∀i ∈ {1,. . . , k}, ϕ′i ∈ TF-FOL such that it is not a ground formula and in the form (premises, conclusion), i.e., (ψ1∧. . .∧ψl) → ψl+1 where ∀j ∈ {1,. . . , l + 1}, ψj ∈ TF-FOL, and wi ∈ [0,∞[.

The universe of all TMLNs is denoted by TMLN.

2.2 MAP Inference

After obtaining the representation of facts and rules in a TMLN, to select the most probable and consistent set of ground formulae with a MAP inference, we proceed to an instantiation of the TMLN, to obtain the ground rules (when possible) by replacing variables in rules by constants.

A TMLN instantiation I ⊆ MI(M) is a TMLN only composed of ground formulae, I is also called a state of the TMLN M, and MI(M) is its maximal instantiation, i.e., the set of all ground formulae from M. An instantiation can be inconsistent. The universe of all TMLN instantiations is denoted by TMLN∗ . To compute the strength of a TMLN state, we resort to a semantics. We denote the universe of all semantics by Sem, such that for any S ∈ Sem, S : TMLN∗ → [0,+∞[. It computes a strength above 0 (not a probability between 0 and 1). One semantics may maximize the amount of information and quality for another one. States computed by MAP inference are relative to a given semantics. Given a TMLN M ∈ TMLN and a semantics S ∈ Sem, a method solving a MAP problem is denoted by: map : TMLN × Sem → P(TMLN∗ ), where P(X) denotes the powerset of X, such that: map(M, S) = {I | I ∈ argmax I ⊆ MI(M) S(I) and ∄I ′ ∈ argmax I ′ ⊆ MI(M) S(I ′ ) s.t. I ⊂ I ′ }.

1 A companion video for this paper is available at https://www. youtube.com/watch?v=c8AzFQMs1I4

Our approach introduces a semantics decomposed in three functions: a validation of instantiations function ∆ integrating various consistency relations, ii) a selecting function σ that modifies formulae's weights in instantiations and iii) an aggregate function Θ returning the final strength. A temporal parametric semantics is a tuple TPS = ⟨∆,σ,Θ⟩ ∈ Sem, st.: ∆ : TMLN∗ → {0, 1}, σ : TMLN∗ → ⋃+∞ k=0 [0, 1]k ,Θ : ⋃+∞ k=0 [0, 1]k → [0, +∞[. And for M ∈ TMLN, I ⊆ MI(M), the strength of a temporal parametric semantics TPS = ⟨∆, σ, Θ⟩ is computed by: TPS(I) = ∆(I) · Θ(σ(I)).

An example of a selection function is a threshold function, an aggregation function may be different types of sums, and for validation functions we have defined the notions of partial and total temporal in/consistencies, which depend on the temporal intersection of conflicting information (Figure 1).

2.3 Reasoning Example

In Table 1, we present some facts about the Brazilian football player Pel´e, formalized with a TMLN. It is certain that he was a football player between 1956 and 1977 (F1). Other facts state some information about teams he may have played with, or not. Then, we introduce a rule indicating that, in general, a player can only play for one team at a time (R1). Variables are typed into two sorts, α and β, respectively indicating a general concept or a temporal point. Table 2 shows examples of rule R1 instantiated with some facts from Table 1. For instance, GR11 is instantiated from facts F1, F2 and F4.

GR11 ((Diff (NY C, Santos) ∧ ¬Disjoint(1975, 1977, 1973, 1976)∧ P layF or(P ele, NY C, 1975, 1977) ∧ F ootballer(P ele, 1956, 1977))

→ ¬P layF or(P ele, Santos, 1973, 1976), 0.6) GR12 ((Diff (Santos, NY C) ∧ ¬Disjoint(1973, 1976, 1975, 1977)∧ P layF or(P ele, Santos, 1973, 1976) ∧ F ootballer(P ele, 1956, 1977)) → ¬P layF or(P ele, NY C, 1975, 1977), 0.7) GR13 ((Diff(Brazil, Santos) ∧ ¬Disjoint(1958, 1970, 1956, 1974)∧ P layF or(P ele, Brazil, 1958, 1970) ∧ F ootballer(P ele, 1956, 1977)) → ¬P layF or(P ele, Santos, 1956, 1974), 0.7)

3 The NeoMaPy Approach

The NeoMaPy framework consists of a two-step MAP inference extraction based on a graph database, and a conflict resolution heuristic. This major contribution introduces a parametric, efficient and interactive process.

Graph of conflicts. This first step transforms a TMLN instantiation into a property graph where constants and predicates become Concept nodes. Ground formulae combining those concept nodes are represented as TF nodes (Temporal Formula) with temporal predicates and weights as properties. Rules are expressed as queries on the graph of interactions between TF nodes based on their properties, constants and predicates. They produce conflict relationships between TF nodes, labelled with a conflict type. TF and Concept nodes and relationships are stored in a graph database.

Thanks to this conflict graph, applying semantics corresponds to a pattern query on the graph, searching for conflicts between TF nodes. It reduces the MAP inference to the computation of the maximal subset of consistent TF nodes.

Infering the MAP. Once the set of conflictual nodes has been obtained, the MAP inference is computed in two steps: 1) we conduct a pre-processing that structures our data into a set of connected components (i.e., if there is no path between two nodes, they are not connected). 2) for each connected component (i.e., a dictionary) we apply in parallel the MAP inference algorithm MaPy which creates a list of solutions by iteratively trying to add each node to the current solutions. We optimize this process by using a heuristic to eliminate the worst solutions and by restricting the size of this solution list, i.e., by keeping the k best solutions.

4 Implementation

Figure 2 illustrates the architecture of the NeoMaPy framework. The first step extracts the knowledge graph by instantiating facts and ground facts with the Neo4j 2 graph database (nodes' size depends on weights). By applying rules, the graph of conflicts is extracted from facts (green and purple links). The second step exploits the list of conflicts with a parameterized semantics and processes it with the MaPy algorithm implemented in Python (red circles are removed nodes). The source code and datasets are available on GitHub 3 .

2 https://neo4j.com

4.1 MAP Inference Computation

Conflicts extraction from TF nodes has been implemented in Neo4j. Facts are imported from CSV files. The graph is composed of Concept and TF nodes. Rules are applied to instantiate ground rules as Cypher queries. Conflicts are then instantiated as "conflict" relationships on the graph, by searching for TF with corresponding patterns (rules).

The Cypher query below illustrates the generation of conflicts for the pCon rule (partial temporal consistency). If two TF tf1 and tf2 share the same concepts (s,o,p) with opposite polarities (positive or negative information) and a timeframe intersection, it produces a pCon conflict between tf1 and tf2. For optimization purposes, concept IDs are repeated in TF nodes (e.g., tf1.p = tf2.p). Conflict and inference relationships are typed.

MATCH (tf1:TF) -[:s]-> (:Concept) <-[:s]- (tf2:TF) WHERE tf1.p=tf2.p and tf1.o=tf2.o and tf1.polarity <> tf2.polarity AND ( (tf1.date_start <= tf2.date_start and tf2.date_start <= tf1.date_end) AND (tf1.date_start <= tf2.date_end and tf2.date_end <= tf1.date_end) ) MERGE (tf1)-[c:conflict]-(tf2) SET c.pCon=true;

The resulting graph eases the tracability of the MAP inference. Moreover, MaPy processes the inference with a parametric semantics extracted with a Cypher query of corresponding conflicts, and inference rules (inferred TF are ignored along with their premises), thresholds on weights, etc.

4.2 Scenarios

A Graphical User Interface was developed using GraphStream 4 [Dutot et al., 2007], to improve the reasoning process on uncertain temporal knowledge graphs. The dataset we use contain football facts and rules from [Chekol et al., 2017a]. The demonstration will show all NeoMaPy steps:

Graph import and conflict extraction. Concept and TF nodes are imported from CSV files into the Neo4j database and inference rules are applied. Then, a set of rules expressed as Cypher queries are applied on the graph.

3 https://github.com/cedric-cnam/NeoMaPy Daphne

4 A Java library for graphs: https://graphstream-project.org/.

Conflict-graph visualization. The produced conflict graph is visualized as shown in Figure 3. Several interactions are offered to users to explore the knowledge graph, such as node search, clusters of conflict nodes, zooming features. Moreover, graph statistics are computed (graph weights and conflict statistics in Figure 3).

ParametricMAP inferences. Eventually, several MAP inference computations are applied to show the impact on the graph. Simple strategies are compared with different Parametric Temporal Semantics showing the maximization of the argmax S(I) defined in Section 2.2 (e.g., the tInc total inconsistency semantics in Figure 4).

5 Conclusion

Our framework NeoMaPy demonstrates the computation of a MAP inference on TMLNs with formalized uncertain temporal facts and rules. The two-step extraction of the graph of conflicts and their resolution with a MAP inference heuristic provides a parametric, interactive and efficient process.

Acknowledgments

This work was funded by French ANR project DAPHNE and by Project GIUSTIZIA AGILE, CUP J89J22000900005. An author is a member of the INdAM Research group GNCS.