Knowledge Graphs (KGs) are a prevailing data management approach and have found extensive applications in recent years. While several methods have been proposed for learning schema information for KGs in the form of logical rules, they are not suitable for KGs with constantly evolving data. This paper makes the first attempt to address the problem by presenting an approach to learning temporal rules from KG streams. The learned temporal rules can be applied in link prediction and event prediction over KG streams. Based on the proposed method, a system StreamLearner has been implemented. Our experimental results show that StreamLearner is effective and efficient in learning temporal rules on real-life datasets and significantly outperforms some state-ofthe-art systems that do not account for temporal knowledge or evolving data.
Knowledge graphs (KGs) have proven to be a flexible and
powerful data management approach that underlies a new
generation of information systems. In many approaches, a
KG is represented as a set of RDF triples and thus is also
referred to as an RDF graph. A KG is usually very large
and thus automated and scalable methods are needed for
the creation, maintenance and use of KGs. On the other
hand, it would be essential to extract schema information
from KGs. As a result, in recent years, a number of systems
have been developed for learning rules from KGs
An increasing number of KGs are emerging that model events taking places over time besides static relations among entities. However, the existing rule learning systems customarily assume KGs to be static and are not suitable for KGs with constantly evolving data. A KG containing constantly evolving data can be viewed as a stream of snapshots of the KG over a sequence of time points. Figure 1 illustrates such a KG stream, which involve four entities and some events occurred among them at various time points. Entities e0, e1, and e2 are three countries, and e3 is the missile. Three events occurred in the past: Country e0 test missile at time point 4, and then it established military cooperation with country e1 and imposed sanction on country e2 at time point 3. Besides classical link prediction questions such as “Which countries besides e0 tested missile?” or link prediction questions with temporal knowledge such as “Which counties may attack e2 at the time point ?”, there are also schema level questions that of much interest, such as “After a country x tested missile and then imposed sanction on another country y on the next day, in how many days is it most likely that x will attack y?”
This brings in some research challenges. First, this
requires temporal knowledge to be expressed in the
schema information. For example, the above question
can be expressed as a temporal rule test(x; missile; t) ^
imposeSanc(x; y; t + 1) ! attack(x; y; t + k), where k
ranges over integers. Learning a temporal rule with a
specific k and a highest confidence degree indicates a answer to
the above question. In fact, our experiments show that using
temporal rules also improves the accuracy of classical link
prediction over KG Streams (see Section ). Moreover,
existing rule learners for KGs cannot be directly used to learn
temporal rules. Finally, a framework for stream learning and
reasoning of temporal rules is still missing. Regarding the
application of such framework, in the real-world problems,
we face to this kind of dynamic data which ignoring their
time feature make the obtained model inaccurate or
incapable. For example, ICEWS
In this paper, we make the first attempt to tackle this
problem by developing a method for learning temporal rules
from KG streams. In our proposed method, an existing rule
learner for KG is used to extract static rules from an
initial data set, which is the collection of facts at the first few
time points. These static rules, referred to as structure rules,
are used to construct a space of candidate temporal rules.
Then we extract temporal rules from this rule space by
generalising major quality measures for static rules to
temporal rules. Based on this method, we have implemented a
system called StreamLearner. Experiments have been
conducted to evaluate the proposed method. Our experiments
show that StreamLearner outperforms the state-of-the-art
static KG learners including HOLE
Knowledge graphs (KGs) concerns about entities, such as persons and places, and binary relations among them. A KG consists of a set of RDF triples (e; P; e0), each of which expresses a fact that entity e is related to another entity e0 via relation P . Such a KG is static in the sense that temporal information is not taken into account. In this paper, we consider streams of KGs. A KG stream consists of a (possibly infinite) set of quadruples of the form (e; P; e0; k), each of which expresses an event that the relation P associates entity e to entity e0 at time point k. For convenience, such a fact with time stamp is also called event . Following the convention in knowledge representation, we denote such an event as P (e; e0; k), where P is a ternary predicate, e and e0 are entities, and k is a time point constant.
Consider an KG stream S and two integers i; j with 0 i j, the [i; j]-segment S[i; j] of S is the subset of S consisting of all the events with time points between and including i and j. That is, S[i; j] = fP (e; e0; k) j P (e; e0; k) 2 S; i k jg. When i = j, it can be simplified as S[i]. Note that S can be seen as a sequence of KGs S[0]; S[1]; : : :. Sometimes we want to consider the facts via omitting the time points in the events, and S denotes the static KG obtained from S by replacing each event P (e; e0; k) with the fact P (e; e0).
The class of closed path rules (or CP rules) have attracted
attention in the community of KGs as it provides a balance
between the expressive power of mined rules for KGs and
the efficiency of rule mining. Such a syntactic restriction
is now a widely adopted language bias in the literature of
rule mining for KGs. For instance, CP rules are the
underlying formalism of Path Ranking Algorithms (Gardner and
Mitchell
P1(x; z1) ^ P2(z1; z2) ^ ::: ^ Pn(zn 1; y) ! P (x; y): (1) Here x, y and zi’s are variables, each P (u; v) is an atom, and u and v are called respectively, the subject and object argument for P . Intuitively, the rule r reads that if P1(x; z1); P2(z1; z2); :::; Pn(zn 1; y) hold, then P (x; y) holds too. Atom P (x; y) is the head of r, denoted head(r), and the set of atoms P1(x; z1); P2(z1; z2); :::; Pn(zn 1; y) is the body of r, denoted body(r). It is called closed-path as the sequence of predicates in the rule body forms a path from the subject argument to the object argument of the head predicate. Note that CP rules allow recursion, i.e., the head predicate can occur in the body.
In this paper, we consider temporal CP rules (or simply temporal rules) of the following form:
P1(x; z1; t) ^ P2(z1; z2; t) ^ :::^Pn(zn 1; y; t) ! P (x; y; t + k): (2) Here t is a time point variable and k is an integer. The rule reads that if the rule body holds at time point t, then the rule head holds at time point t + k. Obviously, the class of temporal CP rules could be more general, for instance, different time points could be allowed for different atoms in the rule. Our definition of temporal CP rules is a balance of expressive power and efficiency of rule mining algorithms. Especially, in learning rules from data streams, we are interested in making predictions based on current data stream.
Existing rule learning methods generally involve two components: one is to learn the structure of the rules (e.g., through search and refinement) and the other is to filter out low quality rules through certain quality measures. Our temporal rule learning also involve such two components.
Consider a KG stream S, to learn the structure of the rules,
our method uses facts in an initial segment of the stream
S [0; n] (n 0), which consists of the facts from time
points 0 up to n, as structure training data. A static rule
learner such as RLvLR
Given rule r of the form (1), for each integer k 0, we obtain a temporal rule r(k) of the form (2):
P1(x; z1; t) ^ P2(z1; z2; t) ^ :::^Pn(zn 1; y; t) ! P (x; y; t + k):
Then to assess the quality of candidate temporal rules,
we adapt standard measures, namely support, standard
confidence, and head coverage, that are used in rule learning
literature
For a temporal rule r(k), the support degree of r(k) at time point is naturally defined as the number of entity pairs for which the head of r(k) has instantiations at time point and the body of r(k) has instantiation at time point k. Formally, a pair of entities (e; e0) satisfies the body of r at time point with 0, denoted body(r; e; e0; ), if there exist entities e1; :::; en 1 in the KG stream S such that P1(e; e1; ); P2(e1; e2; ); :::; Pn(en 1; e0; ) are events in S[ ]. And (e; e0) satisfies the head of r at time point , denoted head(r; e; e0; ), if P (e; e0; ) is an event in S[ ]. Then the support degree of r(k) at time point is defined as supp(r(k); ) = ( 0; #(e; e0) : head(r; e; e0; ) ^body(r; e; e0; k); otherwise (3) Note that, since in the static case there is only one time point 0, the standard notion of support is a special case of the above definition where = k = 0.
To normalize support degree, the notions of standard confidence and head coverage have been introduced, which correspond to the standard accuracy and recall, respectively. The standard confidence (SC) of a temporal rule r(k) at time point is the ratio between support degree at and the number of entity pairs satisfying the body at time point k: if
< k supp(r(k); ) SC(r(k); ) =
#(e; e0) : body(r; e; e0; k) Similarly, we define head coverage (HC) of a temporal rule r(k) at time point to be the ratio between support degree and the number of entity pairs satisfying the head at time point :
HC(r(k); ) =
supp(r(k); ) #(e; e0) : head(r; e; e0; )
In the following example, we illustrate the process of temporal rule generation and the quality measures defined above.
Example 1 Consider the first three time points in a KG stream S as follows: S[0] = fP1(e3; e2; 0); P1(e2; e1; 0); P1(e1; e3; 0); (4) (5)
P2(e3; e1; 0)g S[1] = fP1(e2; e2; 1); P1(e2; e1; 1); P2(e1; e3; 1); P2(e2; e1; 1); P2(e2; e3; 1); P2(e3; e3; 1);
P (e1; e1; 1); P (e1; e3; 1)g S[2] = fP1(e1; e3; 2); P2(e2; e2; 2); P2(e3; e1; 2);
P2(e2; e1; 2); P2(e3; e3; 2); P (e1; e3; 2); P (e1; e1; 2)g Let r : P1(x; z) ^ P2(z; y) ! P (x; y) be a CP rule. Consider k = 0; 1; 2 and we have the following candidate temporal rules based on r: r(0) :P1(x; z; t) ^ P2(z; y; t) ! P (x; y; t) r(1) :P1(x; z; t) ^ P2(z; y; t) ! P (x; y; t + 1) r(2) :P1(x; z; t) ^ P2(z; y; t) ! P (x; y; t + 2)
At time point = 2, the quality of the these rules can be assessed as follows: supp(r(0); 2) = 2; SC(r(0); 2) = 1; supp(r(1); 2) = 0; SC(r(1); 2) = 0; HC(r(0); 2) = 1 HC(r(1); 2) = 0 supp(r(2); 2) = 1; SC(r(2); 2) = 0:5; HC(r(2); 2) = 0:5
The SC and HC of temporal rules generalises those standard notions with a temporal flavour, yet they haven’t taken into consideration of the streaming nature of KG stream. In particular, the SC and HC of a temporal rule at one time point is independent from that at other time points. On the other hand, the quality of temporal rules at a time point in a KG stream should aggregate the corresponding (SC and HC) values at previous time points. Hence, the dynamic standard confidence (DSC) of a temporal rule at time point is defined as follows: ( SC( ; ); (1 ) DSC( ; + SC( ; ); DSC( ; ) = otherwise (6) where 0 < < 1 is the learning rate to adjust the weights of previously aggregated DSC and that of the SC of current time point. The dynamic head coverage (DHC) is defined in a similar way. if In this section, we present our algorithm that combines the learning and reasoning of temporal rules in a dynamic manner over KG streams. Our algorithm takes as input a KG stream S (i.e., a stream of quadruples), for which all the facts in an initial segment up to time point n, S [0; n] is stored, and two integers l; m 0 as minimum and maximum prediction distances. And it produces as output a stream of temporal rule sets and a stream of derived events. In particular, we use the method from the above section to obtain a set of candidate temporal rules: r(l), r(l+1), . . . , r(m) for each structure rule r. Then, at each time point, we select quality temporal rules using their DSC and DHC scores and apply the selected rules to derive events about current and future time points.
For both rule quality measure computation and rule application over KG stream S, the notion of shifting windows is required. We assume at each time point , only a segment of S of size w, S[ w + 1; ], is used for computation. Here, w 1 is an integer called the window size, which may vary over time points. The shifting windows are needed not only for memory space concerns but also due to efficiency requirement of stream processing. Note that the structure rules can be learned offline, whereas the temporal rule filtering and rule application need to be performed online.
At time point , to assess the quality of candidate temporal rule r(k), it is clear that if < k then DSC(r(k); ) = DHC(r(k); ) = 0; otherwise, we assume DSC(r(k); 1) has been obtained from the previous time point. By (3) – (7), we would need to access the events at time points and k. Yet we can only access the events in the shifting window, that is only those in S[ w + 1; ]. In this case, if k w 1 then we have required events and the quality measures can be computed as in (3) – (7); otherwise, we set DSC(r(k); ) = DSC(r(k); 1) and HC(r(k); ) = HC(r(k); 1), where 0 < < 1 is used to adjust the weights of previously aggregated DSC due to the rule’s quality not assessable at the current time point.
At time point , to derive new events at time point + k with l k m (recall that m is the maximum prediction distance), we apply selected temporal rule of the form r(k) to the events in S[ ]. To obtain the confidence degree (CD) of a derived event, we adapt the score ( ) function from (Gala´rraga et al. 2015) by aggregating the DSC of all the temporal rules that can derive the event in a Noisy-OR manner. The intuition is that events derived by more rules should have a higher confidence degree. Formally, for an event = P (e; e0; ) and the set of temporal rules that can derive from the KG stream, the CD of is defined as follows:
CD( ) = 1
DSC( ; )): Y (1 2
In Figure 2, we illustrate one snapshot of the stream where the current point is , w = 4, and m = 2. In this example, we consider one structure rule, r. In this time point, we learn the DSC from current and previous time points while we use this time point as the body of rules which get fired and predict the new events for current time point and the future ones.
Algorithm 1 shows the data flow and major components of our system for temporal rule learning and reasoning over KG streams.
In line 2, we obtain a set of structure rules R using static rule learner StaticLearner, such as RLvLR, over the structure training data S [0; n]. This is performed offline. Then, in line 3, a set of candidate temporal rules of the form r(k) is obtained with maximum k being m.
The online stream learning and reasoning starts from line 4. In line 5, current events at time point are read in, and in line 7, past events outside of the shifting window are forgotten. Thus, W consists of all the events in the current shifting window.
In line 9, candidate temporal rules are filtered based on their DSC and DHC scores at time point . As discussed
before, this involves aggregating previous DSC and DHC scores, and is restricted by W the events available in the shifting windows. After filtering, the set of selected rules can be streamed out.
The selected temporal rules can then be used for reasoning. In line 12, each rule r(k) is applied to the current events S[ ] to derive events in future time point + k. Note that events at a time point is derived incrementally from a sequence of past time points. Once all the learnt temporal rules at time point have been applied, the derived events at , , will not change and can be streamed out.
We have implemented a system, StreamLearner, based on
the above algorithm and conducted several experiments to
evaluate it. In our implementation, RLvLR
Our experiments are designed to demonstrate that
temporal rules are an effective model to capture temporal
knowledge and thus can provide more accurate link prediction than
some existing statistical models, such as TransE
In our experiments, we used the Integrated Crisis Early
Warning System (ICEWS) dataset
In the first set of experiments, we used the facts from the first 50 days (i.e., S [0; 50]) as the training data for learning structure rules. We note that the size of the data set is much smaller than the initial data sets in other approaches for learning from streams. Since static rule learner RLvLR learns static rules about specified predicates in rule heads, called target predicates, we randomly selected 20 target predicates.
We assessed the accuracy of link prediction fortnightly
after the 50th day. That is, 23 time points after the rules
structure training. For each of these time points k, we separated
the datasets into 70% training and 30% testing as in most
literature. The link prediction task is to identify for each
target predicate P and each entity e, an entity e0 such that
P (e; e0; k) is an event occurred in the KG stream; or
alternatively, to identify for each target predicate P and each entity
e, an entity e0 such that P (e0; e; k) is an event in the stream.
The prediction accuracy was measured by filtered Mean
Reciprocal Rank (MRR) and Hits@10 as in the literature
In this experiment, the size of shifting window was fixed to 10 days and the maximal prediction distance was also 10 days. For each time point k, SteamLearner applied the learnt temporal rules to the training data in S[k], as well as S[k 10; k 1], to derive missing events at k, whereas StreamLearner-S applied all the structure rules to the training data in S[k]. TransE and HOLE obtained their respective statistical models from the training data in S[k].
Table 2 shows the performance of StreamLearner, StreamLearner-S, TransE and HOLE. We report the numbers of temporal rules (#R), the numbers of structure rules (#SR), MRR and Hits@10 (H@10) scores, averaged over all selected time points and target predicates.
The experimental results show that StreamLearner significantly outperformed the baseline systems. In particular, StreamLearner was around 4 times more accurate than TransE and HOLE on Hits@10, and about 5 times more accurate on MRR. StreamLearner also showed superior performance to its static version, which clearly demonstrates the benefit of temporal rules over static rules on stream reasoning. Indeed, the average number of temporal rules is only around 3 times more than that of structure rules. Considering the number of candidate temporal rules (10 times of structure rules), it shows that the temporal rules can model much refined and more precise association among events.
Figure 3 shows the detailed performance of StreamLearner and the baseline systems, from which we can see that of StreamLearner showed consistently superior performance over the time.
A major benefit of temporal rules compared to statistical models is that their meanings are human understandable, and hence the learned temporal rules themselves contain valuable temporal knowledge about the domain. Although entities and predicates in the ICWEC dataset are obfuscated and thus it is difficult to assess the meaning of learnt temporal rules, it is not hard to image the temporal knowledge behind some common patterns. For illustration purpose, we present the following two temporal rules whose predicate names are replaced with meaningful terms from the ICEWS dictionary. 0:05 : rejectMaterialCooperation(y; x; t) !
threatenWithSanctions(x; y; t): 0:15 : rejectMaterialCooperation(y; x; t) !
threatenWithSanctions(x; y; t + 1): The number before each rule is the corresponding DSC. The two rules indicate that if country y rejects the material cooperation with country x, then it is unlikely that y threatens x with sanctions on the same day. But this is more likely to happen on the next day.
The quality of learnt temporal rules and their performance in link prediction are affected by several factors related to the KG streams, including the sizes of structure training data, the window sizes, and the (minimum and maximum) prediction distance. For the second set of experiments, we evaluate how these factors affect the quality and performance of temporal rules.
The size of structure training data affects the quantity and quality of the structure rules, which in turn affects the learning of temporal rules. In particular, it impacts the efficiency of StreamLearner. Table 3 shows the performance of StreamLearner with different sizes n of structure training data S [0; n], and we compare its performance with that of StreamLearner-S. We report the numbers of structure rules (#SR), stream learning and reasoning times (Time, in seconds), MRR and Hits@10 (H@10) scores, averaged over all selected time points and target predicates.
Overall, allowing larger structure learning data provides more structure rules and leads to better prediction accuracy on both StreamLearner and StreamLearner-S. Yet, there is trade-off between time efficiency and prediction accuracy, and as the size of structure learning data increases, the processing time of StreamLearner increases more significantly than that of StreamLearner-S, due to the number of candidate temporal rules. Yet the processing time of StreamLearner remains acceptable (14.1 seconds) even when a significantly large portion of the KG stream (250 out of 365) were used as structure training data. While StreamLearner again significantly outperformed StreamLearner-S in all cases, an interesting observation is when the available data for rule structure learning is smaller, the benefit of using temporal rules over static rules is more obvious. This indicates when the available structural knowledge (i.e., association among facts, represented in structure rules and temporal rules) is relatively limited, the temporal knowledge (i.e., association among events, represented in temporal rules) plays a more significant role in prediction.
The window sizes and the maximum prediction distances both determine the amount of historical data that can be utilised for learning and prediction, and thus affect the performance of our system. For simplicity, in the following experiments, we set the window sizes to be fixed over time and equivalent to the maximum prediction distances. Figure 4 shows the performance of StreamLearner over window sizes ranging from 1 to 15. Again, we used StreamLearner-S as a baseline, whose performance is not impacted by the window sizes, and MRR and Hits@10 scores are averaged over all selected time points and target predicates.
Generally speaking, the performance of StreamLearner improves as the window size increases. It also reveals some local optimal points, namely window sizes 3 and 10. Although slight improvement in Hits@10 can be observed for widow sizes larget than 10, MRR seems to be flattening. This suggests that in real-life, events occurring further way in the stream tend to be more loosely associated with the current events, and in practice it could be effective to use small window sizes (like 3 or 10).
The minimum prediction distance also impacts the learning and prediction, and probably more on prediction. In the previous experiments, we set the minimum prediction distance to be 0, which allowed events to be derived from the current data. Clearly, as the minimum prediction distance increases, the system is challenged to finalise the derived events in distance. For instance, if the minimum prediction distance is set to 3 then the learnt temporal rules are of the form r(3); r(4); : : :. That means, all derived events at time point ( ) are obtained at time point 3. This effectively requires the prediction to happen at least 3 days ahead.
In the following experiments, we evaluated the impact of minimum prediction distance on the performance of StreamLearner, using StreamLearner-S as a baseline. Note that if the maximum prediction distance stays the same, the increase of minimum prediction distance will reduce the number of candidate temporal rules. To separate this factor from the challenged post by distant prediction, we assume the difference between the maximum and minimum prediction distance remains 10. Figure 5 shows the performance of StreamLearner over minimum prediction distances ranging from 0 to 10. Again, the values are averaged.
The performance of StreamLearner drops as the prediction distances increase. An interesting observation is that the accuracy decrease was not as dramatic as one would expect. In particular, predicting one day or two days ahead had comparable accuracy as “predicting” about today. Also, 7 turns out to be a local optimal point, which may suggest weekly pattern in the event association.
The topic of our work is in the intersection of stream
reasoning and stream learning. There have been some approaches
to address these two issues but separately. Knowledge
representation and reasoning in the presence of data streams
has been investigated in
In KG community, some methods have been proposed for
learning rules from a given (static) KG. Recently, the method
of embedding from representation learning is applied in rule
learning for (static) KGs
There are numerous works on link prediction by
employing the method of embedding such as
There are also some approaches to learning logic-based
models form streams of relational data such as
In this paper, we have proposed a method for learning temporal rules from data streams in the format of Knowledge Graphs (KGs). Such rules can be used for reasoning about event over different time points. Especially, temporal rules are useful for link prediction and event prediction in the setting of KG data streams. The proposed method is essentially a framework for rule learning from KG data streams by extending existing rule learners for KGs. Based on RLvLR, a state-of-the-art rule learner for KGs, we have implemented a system StreamLearner, which can learn temporal rules from KG data streams, completing dynamic KGs and predicting events for them. Our experiments show that StreamLearner significantly outperforms the base systems. It is able to handle large KGs and a promising approach to creating, maintaining and using data streams in the format of KGs.
There are still some interesting issues for future work. We plan to develop a framework to handle more complex events such as the event with the beginning and termination time or the event with the location of the happening label.