INFER: A Neural-symbolic Model For Extrapolation Reasoning on Temporal Knowledge Graph

Thank you for your insightful feedbacks on our paper. We appreciate your crucial suggestions. The followings are our replies to your questions and summarized weaknesses:

Reply to W#1:

We have two main motivations. Firstly, traditional rule-based models, when applying rules through path matching, do not consider the validity of historical facts and treat recent facts and ancient facts equally (lines 82-84 in our paper). Secondly, traditional rule-based models are greatly affected by missing information, leading to inference bottlenecks. To address the first issue, we propose a temporal validity function that considers the time span and frequency of historical facts, extending the truth value of facts from binary to continuous and modeling fact validity. The main experiment and ablation experiment verify this motivation. To address the second issue, we introduce a static KG embedding model, which captures structural information through pre-training. We then propose the entire INFER paradigm, which combines embedding information with improved rule application by constructing and updating the Temporal Weight Matrix and proposing Projection operator. The resulting neural-symbolic method gains the ability to reason about missing information and its performance is less affected under incomplete settings compared to traditional rule-based models (Results in Table 2). Meanwhile, the efficiency of applying rules is greatly enhanced through performing matrices operations instead of path matching. More importantly, our model provides a new paradigm to combine embedding-based methods and symbolic-based methods paving the way for future research.

As we mentioned in section 4.3.3, when answering query $(s,r,?,t)$, we first traverse the available rule’s body obtaining the relations $rl_1,rl_2$.... At the starting point we select the $s$-th row of $M_{rl_1}$ which records the truth values of each entity serving as object entity in facts with subject entity $s$ and relation $rl_1$, $(s,rl_1,e_i);e_i∈E$. If the rule length is 1, then this vector denotes the scores of all entities given by this rule. If the rule length is more than 1, as mentioned in the paper we transpose the row vector and repeat it along the row direction for $|E|$ times which results in a matrix of $|E|×|E|$. Then we calculate the Hadamard product of the obtained matrix and the corresponding temporal weights matrix, which is the results of the AND of facts along each possible paths. Finally, we take the maximal value of each column, which is to select the biggest truth value of a path starting from s and ending at each entity $e_i$. This process is tractable and can be interpreted as human-readable results. For example by performing argmax operation, we can show which specific path leads to the maximal score of $e_i$. As we repeat the above procedure, the final results is the vector records the maximal truth values of paths leading to each entity.

We are sorry about the confusing presentation. In equation 5, $Ans_i$ is a row vector which denotes the scores of all candidates at the $i$-th hop of a rule and n is the length of the rule. As for the Ans in Algorithm 1, it is also a row vector representing the scores of all candidates at each step.

Reply to W#3:

Thanks for your advice. Theoretically, the spatial complexity of INFER mainly counts on the temporal weight matrices: O(|E| * |E| *|R|). Although it seems costly, TKGs in real world are really sparse and we can use sparse matrix to store them. Also, as mentioned in line 259, we set a threshold to filter out some really small values so that the matrices can be stored on a single GPU. Here’s some statistics to illustrate the sparsity of TKGs:

For ICEWS14, the facts it contains take up only 0.00043% of the whole matrices, which means the rest entries in the Temporal Weight Matrices are zero. The proportion of ICEWS18 is 0.00020%, 0.00060% for ICEWS0515.

As for the time complexity, if the length of the rule is 1, then we just select a specific row of the corresponding Temporal Weight Matrix $M_r$. Thus, the time complexity is $O(1)$.

Intuitively, when the rule is longer than 1, the time complexity of the inference procedure of INFER is $O(|E|^2)$ due to the Hadamard Product, which seems high. However, due to the sparse property of TKGs, in fact there are many zero values in $Ans$ (the vector stores intermediate candidates list), thus we actually implement it in a more efficient way through only selecting the non-zero values in Ans and calculate the product of the values and their corresponding rows in $M_r$. In this way, the time complexity is $O(|E| * len(Ans>0))$.

Reply to W#4:

As we mentioned in Section 1, line(82-84), “previous rule-based methods consider the standing of facts as a binary 0 or 1 problem (have been true or not) for path matching, which ignores the validity as well as frequency of historical facts under temporal settings”. The reason why we have the above claim is that when applying rules, previous methods search for the stands of rule bodies through paths matching on the graphs. If we consider the knowledge graphs as weighted graphs, then normally there are only two kinds of weights: 0 and 1. 0 for the facts that have never appeared, i.e. there’s no edges between two entity nodes. 1 for the facts that have been true in history, i.e. there’s an edge of a specific relation between two entity nodes. In this paper, we argue that this setting is not suitable for TKGs. Details can be found in line 97-94 and 107-109.

So back to your question, “traditional binary truth values for historical facts” in line 426 means that we assign 1 to all historical facts as long as it appeared before, otherwise we do not update its value in the temporal weight matrices.

Reply to W#5:

Here are the results of INFER on WIKI and YAGO, as we can see INFER still outperforms existing methods and significantly improves the rule-based baselines on WIKI. As for YAGO, our model and other rule-based methods fall short compared with embedding-based methods. As mentioned in [1], some relations in YAGO can not be modeled by cyclic rules which take up to 10% of the test set. Since our model only uses cyclic rules, it is affected to a certain extent. However, INFER still gain improvements compared with TLogic.

WIKI:

YAGO:

[1] Confidence is not Timeless: Modeling Temporal Validity for Rule-based Temporal Knowledge Graph Forecasting (Huang et al., ACL 2024)

Please feel free to reach out if you have any questions or require further clarification. If you find our response satisfactory, we hope you will consider this a valid reason to consider raising your rating.

Dear Reviewer qjZA,

I hope this message finds you well. As the deadline for the reviewer-author discussion draws near, we would like to kindly request your input on our rebuttal. We understand your time is valuable, and we greatly appreciate your initial engagement with our paper. If you could spare a moment to review our responses and consider the clarification and extra experiments we've made, we would be truly grateful.

Thank you once again for your time. Please feel free to reach out if you have any questions or require further clarification. If you find our response satisfactory, we hope you will consider this a valid reason to consider raising your rating.

Thank you for your feedbacks and here are our clarifications about your questions:

Reply to W#1:

The temporal validity function we proposed is indeed an empirical result. When designing the model, we also considered that using a learnable approach might achieve better performance. However, our current framework is already divided into three stages: rule learning, pre-trained model training, and rule application. Introducing an additional learning and training process for the temporal validity function would make the overall workflow cumbersome compared to previous rule-based methods. Through experiments, we found that designing a fixed temporal validity function can also achieve good results. Therefore, we adopted the current approach. However, we fully agree with your viewpoint that a learnable approach may provide better performance, and we will attempt to explore this issue in future work.

Reply to W#2:

Since our model uses an existing algorithm (TR-Rules) to acquire rules during the rule learning stage, the performance of INFER is dependent on the quality of the learned rules. As can be seen from Table 1, compared to ICEWS14 and ICEWS18, the performance of TR-Rules on ICEWS0515 is the furthest from that of TECHS. This is because ICEWS0515 contains data spanning 10 years and is relatively sparse, which increases the difficulty of capturing stronger causal rules and assessing rule confidence during the rule learning process. Therefore, the relatively low quality of the learned rules affects the final performance of INFER. However, we can see that on ICEWS0515, INFER has significant improvements in MRR and Hits@1 compared to TR-Rules, which demonstrates the effectiveness of our proposed rule application paradigm.

As mentioned in Appendix F, INFER's current inability to effectively model the sequential order of events may, to a certain extent, limit the its current capabilities. We will also explore effective ways to address this issue in our future work. Below is a comparison of INFER's performance when applying rules of different lengths with TR-Rules on the ICEWS14 dataset:

Length 1:

Length 2:

Length 3:

It can be observed that, INFER greatly improves the effect of applying rules of length of 1 and 2 compared to TR-Rules. (Rules with length of 2 also include variable constraints sometimes) As for length of 3, INFER still performs better on MRR and Hits@1. However, the results of INFER have more bias when dealing with rules of length 2 or 3. Because, we use 40 rules during evaluation and there are less high confidence (quality) rules of length 2 or 3 compared with rules of length 1, which means when evaluating rules of length 3, we might use some low quality rules which further lead to undesirable results.

Reply to W#4:

We fully understand your concerns. We believe that, compared to traditional rule-based methods, the current interpretable process presented by INFER can provide scores for candidates, only lacks the path that leads to each candidate at each step. However, this issue can be resolved. We only need to add a step of argmax operation before line 5 in Algorithm 1, so that we can obtain the specific path indicating which entity from the previous hop leads to each candidate with the highest score. After obtaining such results, the reasoning process we provide will be completely consistent with traditional rule-based methods.

Reply to Q#1:

Yes, as we mentioned in line(295,296), it is an empirical results. We tested multiple designs of this function and corresponding results are reported in Appendix D, Table 4.

Reply to Q#2:

Currently we have $|R|$ temporal weight matrices and the size of each of them is $|E| * |E|$. If we use a temporal embedding model, then for $|T|$ timestamps, we need to build $|R|$ matrices of $|E| *|E|$ for each of them, since each fact might have a different score at different timestamp. This is the overhead issue.

However we choose to use static embedding model not only because of the overhead issue:

Temporal embedding models can only score facts at timestamps that they have seen during the training stage. However, under extrapolation settings, the timestamps in the training set do not overlap with the timestamps in the validation and test set. When we use the matched bodies appeared after the training set timestamps but before the query timestamps, the temporal model can not give a reasonable score to them. Nevertheless, static embedding models can learn the overall structural information and give fair scores based on historical facts for future usage.

Secondly, as we mentioned in line 256-258, during rule application, unlike traditional rule-based models’ path matching way, INFER does not consider the specific timestamp of facts. Thus, we do not need a score of a facts at a specific timestamp. The structural information of the whole historical facts better serves as the dependence of probabilities of potential missing facts.

Reply to Q#3:

We have observed that the improvement brought by acyclic rules in TR-Rules is not very significant, and the relatively large number of such acyclic rules may result in greater overhead. (TR-Rules report that the number of acyclic rules used is far greater than the number of cyclic rules) Therefore, we have not designed to utilize acyclic rules so far. As mentioned in Appendix F, we will explore this aspect in our future work.

Reply to Q#4:

Yes. Since the pre-trained static embedding model scores each fact ignoring the timestamps, it gives same score to the same fact at different timestamps.

Reply to Q#5:

Please see the results given in the reply#1 to W#3.

If you still have any concerns, please feel free to comment. If you find our response satisfactory, we hope you will consider this a valid reason to consider raising your rating.

Thank you for getting back to me. My concerns have been largely addressed, and I will raise my score

Thank you for your insightful feedbacks on our paper. We appreciate your crucial suggestions. The followings are our replies to your questions and summarized weaknesses:

Reply to W#1:

Thank you for pointing out the issues, and we will make the necessary modifications in the revised PDF. Regarding the number of rules, we provided an explanation for "60" on lines 406-408 of our paper, indicating that it represents the performance of INFER when using 60 rules for testing.

Reply to W#2:

Thank you very much for your constructive suggestions, which have helped us improve the expression of our paper. The reason why TLogic uses fewer candidates is due to computational cost constraints, as TLogic sets an upper limit of 20 candidates to consider. Once the number of searched candidates reaches 20, the TLogic algorithm will directly stop applying more rules to obtain more candidates, meaning that it does not consider the potential impact of additional rules on the current results. Therefore, it does not provide a superior method for selecting candidates but rather exhibits limited performance due to cost considerations. Our proposed INFER can efficiently consider a wider range of candidates to obtain more accurate results. Thus, we believe that INFER has higher efficiency, which allows it to consider more rules and candidate entities within acceptable time costs, thereby producing more accurate results.

Reply to W#3:

The similarity in the trends of these lines to some extent is due to the inevitable deterioration in model performance as the proportion of missing facts increases. We enhance the robustness of the rule-based model to this issue by introducing a pre-trained model. As can be seen in Figure 4, the slope of the blue line (INFER) is smaller than the other two lines, especially on ICEWS18, where the slope of the blue line is significantly gentler. This means that the design of our model has mitigated the impact of missing facts on the reasoning results to some extent.

Reply to W#4:

Here we provide an explanation and example regarding Variable Constraints, and we will try our best to include these explanations in the revised version of the PDF.

This is a rule with variable constraints:

$(A, support, C, T)←(A, riot, B, T_1) \bigwedge (B, make statement, A, T_2) \bigwedge (A, resort, C, T_3)$

As we can see in the body of the rule, in the second hop, the entity which B make statement to has to be the same with the entity that riot with B at T1.

If the rule is:

$(A, support, C, T)←(A, riot, B, T_1) \bigwedge (B, make statement, D, T_2) \bigwedge (D, resort, C, T_3)$

Then it is a rule without variable constraints which is different with the rule given above. Because the entity which B make statement to can be or can not be the same with the entity riot with B at T1.

In summary, variable constraints mean that in some rules, it is restricted that the same entity need to appear repetitively so that the rule body is satisfied.

Reply to Q#1:

For facts (s, r, o) that have never appeared, it is meaningless to calculate their Temporal Validity because Temporal Validity measures the validity of a historical fact at the current moment (it should not be considered as a historical fact if it has never appeared). Therefore, we will not update its value in the Temporal Weight Matrices. This means that its corresponding value will be the probability given by the pre-trained model. This process aligns with our motivation to address the bottleneck caused by incompleteness of TKGs. Because the absence of some facts may cause their premises to be invalid, which should have been matched with the bodies of rules.

Reply to Q#2:

Our reply to W#2 can partially address this question. TLogic is limited by the computational cost of path matching, which forces it to stop searching for candidates after a certain number have been found. In contrast, our proposed INFER can efficiently consider a wider range of candidates to obtain more accurate results.

If you are not satisfied with our clarification please feel free to discuss with us.

Dear Reviewer cyuQ,

I hope this message finds you well. We are grateful for your recognition of work and sincerely appreciate your valuable and comments. We eagerly anticipate receiving any additional feedback you may have for the clarification we've provided. We totally understand that your time is valuable. Thanks again for your valuable time and efforts and we are looking forward to your response.

Thanks for your thorough feedbacks which help us to polish this paper . Here's our clarification and replies to questions in weaknesses:

Reply to W#1 and Q#1:

We have two main motivations(the improvements of rule application efficiency is not one of them and it’s more like a advantage of our paradigm instead of the starting point of the design of INFER):

Firstly, traditional rule-based models, when applying rules through path matching, do not consider the validity of historical facts and treat recent facts and ancient facts equally (lines 82-84 in our paper). Secondly, traditional rule-based models are greatly affected by missing information, leading to inference bottlenecks. To address the first issue, we propose a temporal validity function that considers the time span and frequency of historical facts, extending the truth value of facts from binary to continuous and modeling fact validity. The main experiment and ablation experiment verify this motivation. To address the second issue, we introduce a static KG embedding model, which captures structural information through pre-training. We then propose the entire INFER paradigm, which combines embedding information with improved rule application by constructing and updating the Temporal Weight Matrix and proposing Projection operator. The resulting neural-symbolic method gains the ability to reason about missing information and its performance is less affected under incomplete settings compared to traditional rule-based models (Results in Table 2). Meanwhile, the efficiency of applying rules is greatly enhanced through performing matrices operations instead of path matching. More importantly, our model provides a new paradigm to combine embedding-based methods and symbolic-based methods paving the way for future research.

Back to your question, after reading these two papers, we believe that the most fundamental difference between our model and Neural-LP lies in the fact that our proposed method is not learnable and does not require a data-driven training process. Undeniably, our model and TensorLog are indeed similar in essence to a certain extent, and we apologize for neglecting this paper during our research. However, there are still some differences between them. The most significant one is that the relation matrix constructed by TensorLog is binary, with values stored as either 0 or 1. Therefore, TensorLog's computational method involves direct matrix multiplication, whose result denotes entities reachable through rules, and is the “OR” of each path. In contrast, our model extends the truth values of events from 0 and 1 to continuous numerical values. It is unreasonable to directly compute values through matrix multiplication. Hence, we introduce the Max operation in our computational method.

Reply to W#2:

Thank you for mentioning those two papers. After reading them, we found that the two models you mentioned are targeted at the task of Interpolation Reasoning on Temporal Knowledge Graphs (TKGs), while the INFER model we proposed is targeted at the task of Extrapolation Reasoning on TKGs. The difference between the two lies in that:

Given a temporal knowledge graph with timestamps varying from $t_0$ to $t_T$, extrapolation reasoning is to predict new links for future timestamps. Given a query with a previously unseen timestamp $(s, r, ?, t) (t>t_T)$, the model need to give a list of object candidates that are most likely to answer the query. （We give the formal task definition at line 168-170 in our paper）

However under interpolation settings, it does not have the future domain restriction and queries are predicted for time t such that $t_0 ≤ t ≤ t_T$.

Furthermore, as we mentioned in lines 364-366 of our paper, to satisfy the requirements of Extrapolation Reasoning, the data in the dataset is sorted by timestamps and then partitioned accordingly.

Therefore, we did not compare INFER with the two models you mentioned, as they are designed for different tasks. I believe this explanation can also answer your questions Q#3 and Q#4. More details can be found in some early Extrapolation Reasoning papers: [1], [2].

[1]Jin W, et al. Recurrent event network: Autoregressive structure inference over temporal knowledge graphs[J]. arXiv preprint arXiv:1904.05530, 2019.

[2] Li Z, Jin X, Li W, et al. Temporal knowledge graph reasoning based on evolutional representation learning[C]//Proceedings of the 44th international ACM SIGIR conference on research and development in information retrieval. 2021: 408-417.

Reply to Q#2:

As far as we know, no one has ever tried to developed models for TKG extrapolation reasoning based on Neural LP. We are the first to propose a paradigm for integrating rules with embedding methods for TKG extrapolation. There’s one paper published at ACL2024 proposed a machine learning method for rule confidence learning as we mentioned in line229. However, it focuses on improving the rule learning stage while our method mainly improves the rule application stage. As we said in line229, we believe the more accurate confidence given by their model can boost the performance of INFER.

Please feel free to reach out if you have any questions or require further clarification. If you find our response satisfactory, we hope you will consider this a valid reason to consider raising your rating.

Hi Julia,

Thank you for your interest in our work! I truly appreciate that you’ve taken the time to thoroughly inspect our code.

Regarding the issue you raised in your public comment: yes, we do use the "best" setting for evaluation. I recommend checking the public code provided by TLogic [1] (https://github.com/liu-yushan/TLogic/tree/main, particularly the evaluate.py file). TLogic was the first to leverage rule-based approaches for TKG extrapolation reasoning, and in their released code, they also report results under the "best" setting for comparison with other embedding-based methods.

For fair comparison and alignment, that's why we adopted the same "best" setting. Your concern is absolutely valid—this setting may introduce some bias. However, we believe that if all rule-based methods are evaluated under the same "best" settings, the comparison remains relatively fair. If embedding-based methods are involved then there might be some bias.

Thus if it does not convince you, you can try to reproduce the results reported by TLogic and other several rule-based methods mentioned in this paper and then carry out your further research. I think the code given by TLogic provides the calculation for other settings("average", "worse").

[1] Liu, Y., Ma, Y., Hildebrandt, M., Joblin, M., & Tresp, V. (2022, June). Tlogic: Temporal logical rules for explainable link forecasting on temporal knowledge graphs. In Proceedings of the AAAI conference on artificial intelligence (Vol. 36, No. 4, pp. 4120-4127).