{'fraction_non_alphanumeric': 0.03536754507628294, 'fraction_numerical': 0.012383594214384784, 'mean_word_length': 4.775568588184809, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 3, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
TIE: A Framework for Embedding-based Incremental Temporal Knowledge Graph Completion

Reasoning in a temporal knowledge graph (TKG) is a critical task for information retrieval and semantic search. It is particularly challenging when the TKG is updated frequently. The model has to adapt to changes in the TKG for efficient training and inference while preserving its performance on historical knowledge. Recent work approaches TKG completion (TKGC) by augmenting the encoder-decoder framework with a time-aware encoding function. However, naively fine-tuning the model at every time step using these methods does not address the problems of 1) catastrophic forgetting, 2) the model's inability to identify the change of facts (e.g., the change of the political affiliation and end of a marriage), and 3) the lack of training efficiency. To address these challenges, we present the Time-aware Incremental Embedding (TIE) framework, which combines TKG representation learning, experience replay, and temporal regularization. We introduce a set of metrics that characterizes the intransigence of the model and propose a constraint that associates the deleted facts with negative labels. Experimental results on Wikidata12k and YAGO11k datasets demonstrate that the proposed TIE framework reduces training time by about ten times and improves on the proposed metrics compared to vanilla full-batch training. It comes without a significant loss in performance for any traditional measures. Extensive ablation studies reveal performance trade-offs among different evaluation metrics, which is essential for decision-making around real-world TKG applications.


INTRODUCTION
Knowledge graphs (KGs), consisting of triples in the form of (head entity, relationship, tail entity), are effective data structures for representing factual knowledge and lie at the core of many downstream tasks; e.g." question answering [14,22,40] and web search [25]. Although KGs enable powerful relational reasoning, they are usually incomplete. As such, inferring new facts based on existing ones in the KG, known as KG completion, is one of the most important tasks in KG research.
Typical KGs represent knowledge facts without incorporating temporal information, which is sufficient under some circumstances [2,32,37]. By additionally associating each triple with a timestamp, such as (Obama, visit, China, 2014), temporal knowledge graphs (TKGs) are able to consider the temporal dynamics. Usually, TKGs are assumed to consist of discrete timestamps [16]. They can be represented as a sequence of static KG snapshots. The task of inferring missing facts across these snapshots is referred to as temporal knowledge graph completion (TKGC).
To tackle the TKGC task, two avenues of work have been explored. The first line of models induces time-dependent representation with time-agnostic decoding functions to extend static KGC methods for capturing the temporal dynamics [7,11]. The second category of methods adopts spatial-temporal models, which leverage graph neural networks (GNNs) to capture the intra-graph structural information and inter-graph temporal dependencies [34]. We argue that there are still several areas for improvement.
First, previous methods do not explicitly formulate the incremental learning problem, where the change (addition and deletion) of historical information is incrementally available, and the model is expected to adapt to the changes while maintaining its knowledge about the historical facts. Naively, one might fine-tune the TKGC model with all available data at each new time step using gradient descent optimization. This, however, causes the model performance on the historical task to degrade quickly, a phenomenon known as catastrophic forgetting [24,36], which usually occurs because the model loses track of the key static features derived from earlier data. Second, previous methods usually only assess overall link prediction metrics such as Hits@10 and Mean Reciprocal Rank (MRR) while omitting the dynamic aspects of the TKG performance. There is an absence of metrics that can evaluate how well a model forgets deleted facts. For example, the quadruple (Trump, presidentOf, US, 2020) is no longer true in 2021. Hence we would like the model to rank Biden higher than Trump given the query (?, presidentOf, US, 2021). We argue that this is an essential measure of a model's effectiveness in modeling the temporal dynamics of TKGs. Third, as discussed in Section 3.1, previous TKGC methods [7,11] conduct training and evaluation once across all the time steps. This does not satisfy the scalability and training efficiency requirements in real-world KG applications, where millions of entities and relations frequently update [1,33].
Present Work. We introduce a new task, incremental TKGC, and propose TIE, a training and evaluation framework that integrates incremental learning with TKGC. TIE combines TKG representation learning, experience replay, temporal regularization to improve model performance and alleviate catastrophic forgetting.
To measure TKGC models' ability to discern facts that were true in the past but false at present, we propose new evaluation metrics dubbed Deleted Facts Hits@10 (DF) and Reciprocal Rank Difference Measure (RRD). To this end, we explicitly associate deleted quadruples with negative labels and integrate them into the training process, which shows improvement upon the two metrics compared to baseline methods.
Finally, we show that training using added facts significantly improves the training speed and reduces dataset size by around ten times while maintaining a similar ranking performance level compared to vanilla fine-tuning methods.
We adapt HyTE [7] and DE [11], two existing TKGC models, to the incremental learning task on wikidata12k and YAGO11k datasets. Experiments results demonstrate that the proposed TIE framework reduces training time by about ten times and improves some of the proposed metrics compared to the full-batch training. It comes without a significant loss in any traditional measures. Extensive ablation studies reveal the performance trade-offs among different evaluation metrics, providing insights for choosing among model variations.

RELATED WORK 2.1 Temporal KG Completion
Existing TKGC methods can be broadly categorized into two lines of work. The first line uses shallow encoders with time-sensitive decoding functions to extend static KGC methods [7,11,17,35].
For example, [7] constrains entity and relation embeddings. The decoded scores of triples lie in different hyperplanes for each timestamp. The second line of methods uses spatiotemporal models, which leverage graph neural networks (GNNs) to capture intragraph neighborhood information and temporal recurrence or attention mechanisms to capture temporal information [18,28,34]. The third line of methods leverages temporal point processes to deal with continuous prediction in TKGs [12,30,31]. However, this line of work is orthogonal to ours as their focus is the extrapolation task in the TKG, which aims at predicting the future interactions among entities and relations.
In our work, we aim to provide an efficient incremental learning framework for TKGC. Hence we focus on the shallow embedding methods.

Incremental Learning
As knowledge graphs evolve, more graph snapshots become available. However, deep learning models suffer from catastrophic forgetting when existing models are incrementally fine-tuned according to the newly available data [3,19]. Various incremental learning techniques have been introduced to combat this issue for deep learning models. Our work is closely related to the experience replay and regularization-based methods. Experience replay, also referred to as reservoir sampling, retains an additional set of the most representative historical data. Rehearsal methods [6,15,26,27] explicitly maintain a pool of historical data when training the model on new tasks. One of the earliest methods, iCarLR [27], sets the fixed number of samples for each task and selects samples that best approximate the feature mean of each class. Constrained optimization methods also belong to this category. Previous work [5,21] exploits the stored samples to project the gradient of the current task's loss to a desired region. The objective is to ensure that the loss on the historical samples will decrease after training on the current task. This is equivalent to projecting the gradients of the current data to a direction that aligns with the gradients of the previous data. Regularization-based approaches consolidate previous knowledge by introducing regularization terms in the loss when learning on new data [3,19,38,39].
More recent work has explored applying incremental learning techniques for training deep graph neural networks. Graph-SAIL [36] tackles the GNN-based recommendation system's forgetting issue using knowledge distillation at both node and graph levels. ER-GNN [41] proposes node importance metrics and selects the most influential nodes in the graph as reservoir data. The model is fine tuned on the new data as well as the selected nodes during the training. A more relevant work [29] applies the regularizationbased method to enrich embeddings in knowledge graphs. However, the method in [29] focuses on data synthesized by subdividing a static knowledge graph into multiple snapshots.
In our work, we propose an end-to-end framework combining experience replay and regularization-based methods that are specifically tailored for incrementally training TKGC tasks.

PROBLEM SETUP AND FORMULATION
In this section, we introduce notations, specify assumptions, and describe the encoder-decoder framework for the standard TKGC [34]. This is the foundation of our TIE framework for incremental TKGC.

Problem Formulation
A TKG is a sequence of KG snapshots: G = { 1 , 2 , ..., }, where denotes the total number of time steps in the TKG and is the KG snapshot at time step . Each graph is represented as a triple, i.e., = ( , , ). Here, denotes the set of all observed quadruples ( , , , ) occurring at time ; and denote the sets of entities and relations that are involved in at least one fact in . Each quadruple contains the subject , the relation , the object and the time . Let denote the set of true quadruples at time such that ⊆ , ∀ . The set of missing facts can therefore be written as = \ . For a quadruple ( , , , ) ∈ and its related object query ( , , ?, ), the goal of TKGC is ranking as high as possible. The goal of answering a subject query (?, , , ) is similarly defined.
Standard TKGC and incremental TKGC differ in terms of 1) the scope of the input, 2) the scope of the time steps targeted for evaluation, and 3) the set of candidate entities on which the score function is applied to produce the final ranking. Incremental TKGC. Under this setting, both training and evaluation are conducted at each time step upon the available new data . Hence, the input is the sequence 1 , 2 , . . . , and the goal is to answer queries in 1 , 2 , . . . , . As opposed to standard TKGC, the model only has access to entities present from the beginning to the current time step , i.e., = =1

Encoder-Decoder Framework
TeMP [34] proposes a TKGC framework with a temporal multirelational message passing encoder and static KG decoders. However, their main focus is the encoder's design, which combines multi-relational message passing and commonly used temporal models (RNN and transformer). In TIE, we instead emphasize the time-aware embedding, which is composed of single-layer embedding matrices coupled with a time-agnostic decoding function designed for static KGC.
Encoder. Let ∈ R | |× and ∈ R | |× denote the entity and relation embedding matrices ( is the embedding dimension for both entities and relations), The static entity representations for entity and relation are defined as = [ ] and = [ ].
Temporal KG embedding models derive time-aware representations for entities and relations, so their temporal representations at time are denoted as and . For example, the Diachronic Embedding (DE) proposed in [11] applies a time-dependent function on static entity embeddings but does not differentiate between relation embeddings in different time steps: Here and are entity-specific vectors with learnable parameters. The first elements of the vector capture temporal features while the last (1 − ) elements capture static features. The function is used as the activation function enabling the model.
In the temporal KG representation learning methods, time-dependent representations are taken as input to the time-agnostic decoding function. Let denote the model with the parameters at time step . The score for a quadruple ( , , , ) is defined as follows: Connection to incremental TKGC. The encoder-decoder framework can be naturally adapted to incremental learning with simple fine-tuning using or full-batch training using 1 , . . . , at each time step. In the following sections, we define key metrics and propose a set of incremental learning techniques based on the encoder-decoder framework.

METRICS
We start by introducing commonly used evaluation metrics in standard TKGC, followed by the notions of current, historical average, and intransigence measures in the context of TKGC to quantify the different aspects of model capacity.

Standard TKGC Metrics
For each quadruple ( , , , ) ∈ , we evaluate an object query ( , , ?, ) and a subject query (?, , , ). Regarding the object query, we calculate the scores for all known entities, i.e., ( , , ′ , ), ∀ ′ ∈ . The ranks are obtained by sorting the scores in descending order. Thereafter this is used to compute commonly used metrics such as Mean Reciprocal Rank (MRR) and Hits@k (k is usually 1, 3, and 10). The Hits@k is the percentage of test facts for which the correct entity's rank is at most . For = 10, we have the Hits@10 metrics, defined for object queries as: where is the indicator function.

Incremental TKGC Metrics
Since the objective of incremental TKGC is to incorporate facts from new time steps while preserving knowledge derived from the previous ones, an incremental learning approach should be evaluated based on its performance on both the current and historical quadruples. Additionally, we would like them to measure a model's ability to discern changes in the validity of facts at a different point in time, e.g., change of political affiliation or end of a marriage.
Current and Historical Average Measure. Let , be the Hits@10 value specified in Equation (3) evaluated on , ( ≤ ), using the model incrementally trained after time step . The current performance measure ( ) is written as = , .
We adapt the Average Accuracy Measure proposed in [4] to the TKGC setting, replacing the accuracy with the Hits@10 measure. The Average Hits@10 ( ) at time step is defined as = 1 =1 , . The higher the value of , the better the model in terms of historical average performance, which is an important aspect for TKGC evaluation. This, to some degree, also measures whether a model is prone to catastrophic forgetting. A model that cannot retain past knowledge would yield a much lower than a model trained using all the historical data.
Intransigence Measure. In the context of TKGC, we define intransigence as the inability of an algorithm to identify knowledge that was true in the past but false at present. For example, after graduating from a college, a student is no longer associated with the college.
We categorize the measure into the model's ability to 1) assign a low rank to the deleted facts and 2) rank the currently valid facts above the deleted facts. We propose Deleted Facts Hits@10 (DF) and Reciprocal Rank Difference (RRD) to measure the two aspects. The DF is analogous to the false positive rate in the classification setting, measuring the rank of the deleted triples' current time step as their time attributes. A lower DF value suggests that a model has a better capability to exclude deleted facts from the top 10 results.
The RRD is defined as the pairwise difference of reciprocal ranks between each positive quadruple in the test set and each deleted fact in the previous data. RRD implicitly focuses on the cases where the rank value of either the positive object or the negative object ′ is low, e.g., 1 1 − 1 10 = 0.9, while discounting the cases where both rank values are high, e.g. 1 1000 − 1 1010 ≈ 9.9 × 10 −6 . We define a time window ranging from − to −1 to limit the scope of evaluation. For every quadruple ( , , , ), we aim to find and then evaluate the related deleted facts from this time window. We define the DF and RRD metrics for object queries at time step : where ′ , , is the collection of negative objects and is the normalizing constant: In practice, the RRD values are very close to zero. Hence we multiply the RRD by a factor of 100 for better presentation. The intransigence metrics for subject queries can be defined analogously.

PROPOSED FRAMEWORK: TIE
We provide an overview of TIE before describing the proposed methods in detail in the following sections.

Overview
We establish the TIE framework that augments the TKGC encoderdecoder framework (Section 3.2) with incremental learning techniques, a method to overcome intransigence, and an efficient training strategy. The overall architecture of TIE model is depicted in Figure 1. Algorithm 2 outlines the representation learning procedure of TIE.
A key insight of our framework is that we adapt experience replay and temporal regularization techniques (Sections 5.2 and 5.3) to address the catastrophic forgetting issues of fine-tuning methods using TKG representation learning models. Additionally, we propose to use the deleted facts from the recent time steps as a subset of negative training examples to address the intransigence issue of the state-of-the-art TKGC methods. Finally, we propose to use newly added facts only for fine-tuning at each time step. This is based on the finding that the particular type of TKGs of most interest is composed primarily of persistent facts, i.e., the average duration of facts is typically long enough that no drastic changes occur between adjacent time steps.

Experience Replay
Inspired by iCaRL [27], we propose adapting the principle of experience replay -to update the model parameters for the current task, we use not only the training data for the current time step but also the quadruples from earlier time steps. The data in the recent time steps can be made available with a replay buffer confined by a sliding window.
We denote the current time as and the time window length for experience replay as . At time step , we define a time window spanning from max( − , 1) to −1. The historical facts in the most recent time steps are stored in memory, which also satisfies the resource constraints in a large-scale knowledge graph application, as it is too costly to store and load data from all time steps. Line 3 of Algorithm 2 constructs the replay buffer . We first introduce two strategies for replay fact sampling, then specify the loss function, which combines a standard cross-entropy loss and a knowledge distillation loss.

Replay Fact Sampling.
We extract , a set of replay samples with positive labels, from , using the following sampling strategies: Uniform Sampling. A simple yet powerful sampling strategy is to uniformly sample triples from the replay buffer .
Frequency-based Sampling. We extend the notion of pattern frequency introduced in [34] to gauge the sampling probability of each quadruple in the time window and develop two approaches dubbed frequency-based sampling and inverse frequency-based sampling. A pattern of the triple ( , , ) refers to a regular expression with some of the elements replaced with the wildcard symbol ' * '. We use historical pattern frequency (HPF) and current pattern frequency (CPF) to represent the number of quadruples matching a pattern occurring before (within ) and at (within ) respectively. The set of patterns is defined as:  Taking ( , * , ) for example, the HPF ℎ , * , and CPF , * , are calculated as: , The HPF and CPF for the rest of the patterns are analogously defined. The process for calculating the pattern frequencies over all quadruples and defining their sampling probabilities is highlighted in Algorithm 1.
The sampling probability for each quadruple ( , , , ′ ) in involves two separate terms: a frequency-dependent probability ( , , ) and a time-dependent probability ( ′ ). We define ( , , ) as the weighted sum of pattern frequencies in the log scale: where the scalar value denotes the weight associated with the frequency of pattern . Recall that is the window length. We additionally introduce as a discount factor controlling the ratio of ℎ and . We take pattern frequencies in their log forms (after adding 1 to avoid zero-values) to downscale the patterns with particularly large frequency, in order to avoid repeatedly sampling quadruples with a few very frequent patterns (examples are presented later).
The term ( ′ ) is formulated as an exponential decay function on the temporal distance to the current time step, aiming at downweighting the quadruples from the older time steps relative to the more recent ones. It is defined as where is a scalar parameter controlling the smoothness of the function. The resulting unnormalized sampling rate ( , , , ′ ) is written as ( , , ) ( ′ ) (line 10, Algorithm 1). This design encourages the sampling of quadruples with higher pattern frequencies and discourages the sampling of quadruples with lower pattern frequencies. For example, in the Wikidata12k dataset, (La Chapelle-sur-Oudon, instance of, commune of France, 76) would get a high sampling probability because the pattern (*, instance of, commune of France) has a large number of matches from time steps 62 to 77. Moreover, every quadruple with this pattern is assigned a higher sampling probability, resulting in a non-representative subset sampled by the algorithm, leading to higher intransigence.
We thus propose a simple alternative that instead encourages the sampling of quadruples with lower pattern frequencies. We name this inverse frequency-based sampling, and define the sampling rate as ( ′ ) ( , , ) (line 8, Algorithm 1). This design results in a more diverse set of replay samples, with the quadruples with high pattern frequencies discarded.
After computing the sampling rates for all the quadruples, we normalize the sampling probability for each quadruple and use them to sample (lines 13 -17, Algorithm 1).

Representation
Learning. For each quadruple in , we use time-dependent negative sampling [7] to collect a negative set of entities to approximate the cross-entropy loss. Each negative entity is collected from the set of known entities up to time step ′ . For each triple ( , , , ′ ) ∈ , the negative entities set is written as As in iCarRL, we additionally use the knowledge distillation loss [13] to ensure that the previously learned discriminative information is not lost during the new current learning step. Before training the parameters at time step , we store the output of the model with the network parameters after training at time step −1 as: After each training iteration, we cache the output logits , , , ′ using the current decoding function : We use to denote the Kullback-Leibler divergence. The replay knowledge distillation (RKD) loss and replay cross-entropy (RCE) at each iteration are defined as follows: the corresponding entry in −1 , or with Glorot Initialization [10] if an entity appears for the first time. The initialization for the entity embedding matrix is as follows: The initialization for other parameters are defined similarly. Inspired by previous work [29], we propose temporal regularization on the parameter space to alleviate catastrophic forgetting. We impose an 2 regularization constraint in the context of TKGC to smooth drastic change in the current representations compared to the previous task's parameters.
Taking the entity embedding matrix for example, we only regularize the representation for those entities that are also present in

Learning with Deleted Facts
To reduce the intransigence of the model as defined in Equations (4) and (5), we propose training the model using a set of deleted quadruples from the perspective of time step : We associate each quadruple in with a negative label and calculate the binary cross entropy loss as: where denotes the sigmoid function. We do not include knowledge distillation since the labels of ( , , , −1) and ( , , , ) are not necessarily identical. It is optional to add a positive example ( , , , ′ ) associated with each negative example ( , , , ) to . However, we do not find it helpful experimentally in terms of alleviating intransigence.

Learning with Added Facts
We observe via statistics of Wikidata12k and YAGP11k (Figure 2) that most facts are common between time steps −1 and , besides the time attributes. This suggests that fine-tuning using all the quadruples within essentially re-emphasizes the majority of the facts that the model has previously seen.
We propose a novel training strategy that uses only the added facts at each time step, i.e., facts that just become true at despite being false at −1. This can significantly reduce the size of training data, thus accelerating training by orders of magnitude. It also allows us to incorporate other complementary techniques introduced in Sections 5.
where the 's are weight parameters controlling the relative emphasis placed on each loss term.

EXPERIMENTS
We evaluate the performance of our models on two standard TKGC benchmark datasets using our proposed evaluation protocol. We also conduct various ablation studies investigating the effectiveness of individual and combined components of the proposed methods.

Datasets
Common TKGs such as YAGO3 [20] and Wikidata [8] have valid time intervals associated with a subset of the facts. We use the two instances in these datasets, i.e., YAGO11k and Wikidata12k released in [7] for the experiments. The statistics of the two datasets are summarized in Table 1.
YAGO11k. This is a subset of YAGO3 [23]. In the YAGO3 dataset, the valid time of a fact is represented as a time interval, e.g., (Pétala  Monteiro, isAffiliatedTo, Democratic Labour Party (Brazil), [1999-##-##, 2014-##-##]). We follow the same preprocessing procedures described in [7] including subgraph extraction and conversion from time interval to discrete time steps. We also follow the practice of merging multiple adjacent time steps to balance the number of triples in different time steps, resulting in 61 different time steps in total. However, an issue with the merging is that redundant facts occur within both training and validation sets. We fix the problem by retaining only one occurrence for each quadruple in the dataset.
For a time interval with a missing start or end date, e.g., (Ann Shoemaker, isMarriedTo, Henry Stephenson, [1956-##-##, ####-##-##]), we use the first and the last time step in the entire dataset to represent the missing start time or end time.
Wikidata12k. This is a subset of Wikidata [8]. Similar to YAGO11k, Wikidata12k associates each fact with a time interval. We create a TKG with 77 time-steps by applying the same processing as YAGO11k. 6.2.1 Training and Evaluation Protocol. Each set of quadruples is partitioned into , and . Motivated by the experiment setting in [36], we pretrain a base model using the quadruples from the first 70% of the time steps following standard TKGC training and evaluation protocols. We then perform incremental training and evaluation on the last 30% of the time steps. Figure 3 illustrates the training and evaluation procedure for Wikidata12k.

Experiment Setting
At each time step , we use the current performance measure as the criterion for early-stopping on the with patience set to 20. We use the best model at the current time step to compute all metrics defined in Section 4 on the test set to obtain the final performance. For evaluation, the time window length for calculating and is set to 10. We report results averaged across 4 randomized runs, along with standard deviation.

Evaluation Metrics.
We report the following metrics defined in section 4: • C@10, or C-Hits@10 (↑): Current Hits@10. The symbol ↑ suggests the higher the metric value, the better the performance. The opposite is true for ↓.
For each evaluation metric, we calculate the average across the incremental learning time steps. For example, the reported current Hits@10 on Wikidata12k is 1 22 77 =55 , as shown in figure 3, time step 55 is the beginning of the incremental learning.
We also report the average training time per epoch, and the size of training data at each time step. Note that the training time includes only the GPU computation time and omits any sampling conducted on the CPU to ensure a fair comparison. Dataset size represents the total number of quadruples involved in the training, including both current facts, experience replay facts, and the sampled negative quadruples.

Representation Learning Base Models.
We directly adapt DE [11] and HyTE [7] to the incremental learning setting. The exact formulations are introduced in Section 3.2. We use ComplEx [32] and TransE [2] as the decoding functions for DE and HyTE, respectively.

Baselines and Skylines Algorithms.
To demonstrate the effectiveness of our incremental training framework, we compare three incremental training strategies, including Fine-tune (FT), Temporal regularization (TR), and the complete proposed model TIE.
(1) Fine-tune (FT): this is a naive baseline that only utilizes added facts and corresponding cross-entropy loss to fine-tune the model at each time step. (1) Full-batch (FB): In this setting, we use all the quadruples in and to fine-tune the model. Negative sampling is based on facts at different time steps. No regularization or distillation is involved.
(2) Full-batch with future data (FB_future): This setting acts as an oracle with access to all data in 1 , ..., . The training and evaluation protocol is described in Section 3.1.

Implementation and Hyperparameters
Our models are implemented using PyTorch with the support of the PyTorch-lightning library [9]. We set the learning rate to 10 −3 and embedding sizes to 128 for all experiments. We use 2048 as the batch size. When training using both current quadruples, experience replay, and deleted facts, we ensure that the total number of these samples in each batch is at most 2048. For the training data at the current time step, we use 500 as a negative sampling rate, meaning that we sample 500 negative entities for each query. Because we corrupt subjects and objects separately, there are in total 1000 negative samples collected to estimate the probability of a factual triple. For the replay samples, we set the negative sampling rate to 50, i.e., sampling 100 negative entities for each replay fact. We find that this ratio achieves an appropriate trade-off between task performance and training time. The above hyperparameters are selected based on the validation set performances. For experience replay experiments, the training time window length is set to 10, and we sample 1,000 historical samples per time step.  Table 2 reports the performances of the proposed methods and baselines. We make the following observations:

Comparative Study
(1) Our proposed method TIE achieves better C-Hits@10 and A-Hits@10 than both the FT and TR baselines (besides Wiki-data12K + DE combination). It also performs better in terms of intransigence measures in DE experiments. (2) Although two full-batch skylines achieve better C-Hits@10 and A-Hits@10 than our proposed methods, they perform poorly on intransigence measures. This indicates the full-batch methods fail to identify obsolete facts promptly. Moreover, FB_future is impractical in our setting because the model does not have access to future data. The practical skyline FB yields a relatively small advantage compared to the proposed methods on C-Hits@10 but performs dramatically worse on the intransigence measures. Despite the improvement, the RRD results of all methods are negative, meaning that on average, the deleted facts rank higher than the currently valid facts. Further research is required to develop better strategies to reverse this. (3) Comparing the different base models, HyTe outperforms DE in terms of C-Hits@10 and A-Hits@10 but under-performs for DF@10 and RRD. Moreover, augmenting the HyTE fine-tuning baseline with either TR or TIE does not result in an improvement. Both TR and experience replay emphasize remembering the previously valid facts and hence improve the A-Hits@10 metric significantly. However, due to the limited representation capacity of HyTE's time-embedding approaches, the model is unable further to distinguish the deleted facts from the previously true facts. This is partly because all the entity and relation embeddings are projected using the same time embedding at each time step. (4) TIE significantly improves both the time efficiency and data efficiency compared to full-batch training settings. The proposed TIE sacrifices time efficiency compared to the TR method as the loss computation of the experience replay component is costly.
Nevertheless, TIE and the TR methods reduce the training time by about 10 and 100 times, respectively comparing to FB.

Ablation Study
To better understand the effectiveness of the proposed methods, we conduct the following four ablation experiments. We use DE as the base model on the Wikidata12k and YAGO11k datasets for ablation analysis. The test results are averaged over four randomized runs. Standard deviations are sometimes omitted due to space constraints. We use "Wiki" and "YAGO" as abbreviates of the two datasets.
6.5.1 Experience Replay Sampling Methods (5.2.1). As described in Sec 5.2.1, we proposed multiple sampling strategies for sampling positive facts from the replay buffer. Table 3 shows the results of applying each sampling strategy, as well as no experience replay. We first observe that using positive facts leads to a better performance in almost all measures compared to not using experience replay, irrespective of the specific sampling strategy. Comparing among the different sampling strategies, the frequencybased sampling performs statistically better on C-Hits@10 and the intransigence measure than other alternatives for the Wikidata12k dataset. The inverse frequency-based sampling performs better on the C-Hits@10 and A-Hits@10 on average, while worse on the DF and RRD measures by average. However, the results for the YAGO11k data set are inconclusive. Considering the standard deviation, no method achieves a significant outperformance.
As the best sampling strategy in each combination of the base model and dataset varies, we treat the sampling strategy as a categorical hyperparameter and choose the one that yields the best validation performance for each experiment setting to apply on the test set.   Table 3: Ablation analysis on different experience replay strategies. All experiments use added facts, deleted facts and temporal regularization. Uniform, Freq, and Inv-Freq stand for uniform sampling, frequency-based sampling, and inverse frequency based sampling respectively. 6.5.2 Learning with Deleted Facts (5.4). To evaluate the effectiveness of the deleted fact sampling component, we compare the performance of adding the deleted facts (Del) to the following baseline models: 1) temporal regularization (TR); 2) the combination of temporal regularization and experience replay (TR + Replay). All models use added facts by default. As shown in Table 4, adding sampled deleted facts consistently improves the model's intransigence measure in DF-Hits@10 and RRD. Meanwhile, it slightly impedes the model's performance in terms of C-Hits@10 and A-Hits@10 for most cases. This demonstrates that the deleted fact sampling helps the model differentiate triples with low ranks from triples with high ranks with a limited sacrifice in the model's ranking performance. Practitioners should be mindful of this trade-off when deciding whether to use deleted facts.
6.5.3 Learning with Added Facts (5.5). To evaluate the impact of only using newly added facts for incremental training, we conduct experiments to compare 1) only using added facts and 2) using all the new facts for training at each time step.    Table 6, we fix the window length = 10 and vary the replay sampling size for each step. For Table 7, we vary and the sample size jointly. Table 6 shows all measures tend to improve as the sampling size increases while keeping fixed. On the contrary, Table 7 shows that larger replay data size does not always lead to better performance as the model's performance is sensitive to the value of , which is the window length of the old data. Among experiments from

CONCLUSION
We present a novel incremental learning framework named TIE for TKGC tasks. TIE combines TKG representation learning, frequencybased experience replay, and temporal regularization to improve the model's performance on both current and past time steps. TIE leverages pattern frequencies to select among reservoir samples and uses only the deleted and added facts at the current time step for training, which significantly reduces training time and the size of training data. Moreover, we propose DF and RRD metrics to measure the intransigence of the model. Extensive ablation studies shows each proposed component's effectiveness. They also provide insights for deciding among model variations by revealing performance trade-offs among various evaluation metrics. This work serves as a first attempt and exploration to apply incremental learning to TKGC tasks. Future work might involve exploring other incremental learning techniques, such as constrained optimization, to achieve more robust performance across datasets and metrics.
A.2.1 Experience replay buffer size (5.2). To examine the effectiveness of the experience replay component, we conduct experiments by altering the maximum number of the positive replay facts sampled from the replay buffer. We alter the replay sample sizes in two separate experiments. First, in Table 6, we fix the window length = 10 and vary the replay sampling size. Second, in Table 7, we vary both and the sample size, where the sample size grows linearly with the .
As observed from Table 6, all measures tend to improve as the sampling size increases. The largest sampling size of 40,000 achieves the best result for all measures except DF-Hits@10. At the same time, we notice that each time step's training time also increases as the replay sample size grows. There exists a trade-off between performance and training time.
Interestingly, unlike the result from table 6, we observe in table 7 that larger data size does not lead to a better performance in terms of neither Hits@10 measure nor intransigence measure. The best C-Hits@10, A-Hits@10, and DF-Hits@10 are reached when sampling 15,000 positive replay facts with the time window size of 15. Further increasing the sampling size beyond 20,000 and time window size beyond 20 leads to a decrease in all measures. Combining with the previous observation, we conclude that a larger sampling size generally leads to better performance. Meanwhile, replaying the historical facts within a certain time range benefits the model, and the effectiveness of the experience replay component is sensitive to the time window size.

A.3 A-GEM optimization
We report the comparative study between the original TIE model and the A-GEM variation of TIE model in Table 8. The difference between the model performance with and without A-GEM are not statistically significant. This echos the finding in [6] that simple experience replay methods are empirically better than A-GEM on incremental image classification tasks. Our result can be seen an extended piece of evidence in the domain of incremental knowledge graph completion.   Table 8: Ablation analysis of A-GEM under using sampling methods. Replay stands for the type of replay sampling method and A-GEM column indicates whether A-GEM is used or not. All experiments use added facts, deleted facts and temporal regularization bu default.