PaperlayerView exact revision on arXiv

Source-linked AI summary

Know-Evolve: Deep Temporal Reasoning for Dynamic Knowledge Graphs

Rakshit Trivedi, Hanjun Dai, Yichen Wang, Le Song

arXiv:1705.05742v3cs.AIcs.CLcs.LG

TL;DR

Large-scale timestamped event data has created dynamic knowledge graphs whose temporal reasoning remains insufficiently understood. Know-Evolve addresses this gap with evolving entity representations and a temporal point-process model, achieving improved link prediction and predicting fact occurrence times on two real-world datasets.

  • Problem

    Temporal knowledge graphs contain timestamped, evolving interactions, but prior relational learning approaches do not capture their temporal dynamics.

  • Method

    Know-Evolve uses a deep evolutionary network with dynamically evolving entity embeddings and models fact occurrences as a multivariate temporal point process.

  • Results

    Know-Evolve consistently and significantly outperforms state-of-the-art methods on link prediction across two real-world temporal knowledge graphs and predicts fact occurrence or recurrence times.

  • Takeaways & Limitations

    Temporal point processes provide a framework for temporal reasoning over dynamically evolving knowledge graphs.

  • Takeaways & Limitations

    The paper contrasts Know-Evolve with relational learning approaches that treat knowledge graphs as static and lack temporal modeling.

Abstract

from arXiv · show

The availability of large scale event data with time stamps has given rise to dynamically evolving knowledge graphs that contain temporal information for each edge. Reasoning over time in such dynamic knowledge graphs is not yet well understood. To this end, we present Know-Evolve, a novel deep evolutionary knowledge network that learns non-linearly evolving entity representations over time. The occurrence of a fact (edge) is modeled as a multivariate point process whose intensity function is modulated by the score for that fact computed based on the learned entity embeddings. We demonstrate significantly improved performance over various relational learning approaches on two large scale real-world datasets. Further, our method effectively predicts occurrence or recurrence time of a fact which is novel compared to prior reasoning approaches in multi-relational setting.

1. Introduction

Temporal knowledge graphs extend static multi-relational graphs with timestamped, recurring facts, enabling reasoning about evolving entity relationships. Know-Evolve models this evolution with dynamically updated embeddings and temporal point processes to predict facts and their occurrence times.

  • Temporal knowledge graphs add timestamps to edges, allowing facts to occur, recur, or evolve over time.
  • Static relational methods infer missing facts but cannot use the rich temporal dynamics in event-based interaction data.
  • Temporal reasoning supports object, subject, and time prediction questions about future entity interactions.
  • Know-Evolve models knowledge evolution through non-linear interactions between entities in a multi-relational setting.
  • Its architecture updates involved entity embeddings from incoming facts, recent relationships, and temporal behavior.
  • The model predicts both fact occurrence and potential occurrence time, while supporting open-world reasoning and unseen-entity prediction.

2. Preliminaries

Temporal point processes model events localized in time and characterize the next event through a conditional intensity and survival probability. Temporal knowledge graphs represent timestamped relational events as structured graph edges or quadruplets.

  • 2.1. Temporal Point Process: A temporal point process represents events as a time-ordered list or counting process that records event counts before time t.
  • 2.1. Temporal Point Process: The conditional intensity λ(t) gives the probability of observing the next event in a small interval given prior history.
  • 2.1. Temporal Point Process: The survival function gives the probability that no event occurs during an interval, while f(t) = λ(t) S(t) gives event-time density.
  • 2.1. Temporal Point Process: Common intensity designs include Poisson, Hawkes, self-correcting, power-law, and Rayleigh processes.
  • 2.2. Temporal Knowledge Graph representation: A temporal knowledge graph is a directed multi-relational graph whose timestamped edges represent real-world events and may recur at different times.
  • 2.2. Temporal Knowledge Graph representation: Each temporal fact is represented as a quadruplet (es, r, eo, t), encoding a relationship created between subject and object entities at time t.

3. Evolutionary Knowledge Network

Know-Evolve combines a temporal point process, bilinear relational scoring, and a deep recurrent network to reason over evolving temporal knowledge graphs. Its entity representations update through temporal drift and relation-specific mutual evolution as events occur.

  • 3.2. Relational Score: A bilinear relationship score captures compatibility between subject and object embeddings and modulates the point-process intensity for each relation.Each relation has a learned relation-specific weight matrix, while entity embeddings summarize knowledge accumulated from prior events.
  • 3.3. Dynamically Evolving Entity Representations: A deep recurrent network updates entity embeddings after events, allowing latent representations to evolve non-linearly and mutually across relational interactions.The update uses hidden-layer information from prior relationships and applies analogous updates to subject and object entities.
  • 3.1. Temporal Process: Know-Evolve models fact occurrences with a relationship-modulated multidimensional point process whose intensity depends on dynamically evolving entity representations.The intensity is conditioned on the most recent activity of either entity, supporting non-periodic and previously unseen events.
  • 3.3. Dynamically Evolving Entity Representations: The architecture tracks previous events along the timeline and propagates their effects into the embeddings used for the current event.The illustrated computation allows the previous subject and object events to occur at non-consecutive time points.
  • 3.3. Dynamically Evolving Entity Representations: The recurrent formulations use simple RNN units, although the architecture can be replaced with more expressive units such as LSTM or GRU.The paper notes that the temporal-drift and recurrent-participation parameters are learned during training.
  • 3.3. Dynamically Evolving Entity Representations: Temporal drift captures changes between consecutive events, while relation-specific mutual evolution models how interacting entities influence one another in a particular relationship space.The drift term reflects external influences between events; the mutual-evolution term incorporates the other entity and the relationship formed.

4. Efficient Training Procedure

Training uses maximum likelihood for the temporal point process, with a survival term that is expensive to compute over all entity pairs. Know-Evolve addresses this cost through global timeline mini-batches and stochastic survival-loss approximation.

  • 4. Efficient Training Procedure: Despite the expressive deep architecture, Know-Evolve has a memory footprint comparable to simpler relational models.The comparison is reported in Table 4 in Appendix D.
  • 4. Efficient Training Procedure: The model is trained by minimizing the joint negative log likelihood of its intensity function over facts observed in a temporal window.The objective combines a term for observed events with a survival term penalizing absent event types across entity pairs.
  • 4. Efficient Training Procedure: Global BPTT forms sliding-window mini-batches over the global event timeline, capturing dependencies across batches while retaining efficiency.This differs from approaches that decompose data into independent sequences before training on mini-batches.
  • 4. Efficient Training Procedure: The survival term requires O(n^2r) computations over entity pairs and relations, making exact calculation computationally intractable.The cost arises because relation-specific intensity requires survival probabilities for all entity pairs.
  • 4. Efficient Training Procedure: Algorithm 1 computes subject and object survival contributions over the batch entity list and adds them to the loss for each event.The procedure uses the current event time and the latest prior activity time to evaluate the survival contributions.
  • 4. Efficient Training Procedure: Know-Evolve approximates survival loss stochastically by sampling entities within each mini-batch and computing dyadic survival terms for each relation.This random strategy is motivated by the inherent sparsity of knowledge tensors, though it may randomly avoid penalizing some relationship dimensions.

5. Experiments

Experiments evaluate Know-Evolve on GDELT and ICEWS using link-prediction and time-prediction tasks. It consistently outperforms competing relational and point-process methods, while maintaining stable performance over time.

  • Datasets: Experiments use GDELT and ICEWS, which contain dyadic events with timestamps and different temporal granularities and relation hierarchies.GDELT spans 15-minute intervals with 20 top-level relations, whereas ICEWS uses 24-hour intervals with 260 last-level relations.
  • Evaluation: The study compares Know-Evolve with RESCAL, Neural Tensor Network, ER-MLP, TransE, TransR, MHP, and RTPP across link and time prediction.The reported tasks are link prediction and time prediction.
  • Evaluation: Link prediction reports MAR, MAR standard deviation, and HITS@10 for raw and filtered rankings, using conditional-density rankings of candidate entities.The evaluation also partitions each test set into 12 two-week sliding windows.
  • Link Prediction Results: Know-Evolve significantly and consistently outperforms all competitors in prediction rank without deterioration over time.Neural Tensor Network is the second-best baseline but its performance decreases in later test windows.
  • Link Prediction Results: Know-Evolve achieves significantly lower MAR deviation error and high HITS@10, indicating stable and discriminative entity prediction.The result is especially notable on GDELT, which contains 32M events involving entities in multiple relationships.
  • Time Prediction Results: Know-Evolve performs significantly better than other point-process methods for predicting the occurrence time of facts.The authors attribute this to modeling non-linear relational and temporal dynamics, unlike MHP’s restricted intensity and RTPP’s global event view.

6. Related Work

Related work spans relational learning with neural entity and relation embeddings and temporal point processes for evolving network behavior. Existing relational learning methods generally treat knowledge graphs as static and therefore do not capture temporal evolution.

  • Relational Learning: Relational learning models represent entities and relations in low-dimensional spaces and score facts using operations on latent representations.The surveyed models include compositional and translation-based variants.
  • Compositional Models: Compositional models include RESCAL, Neural Tensor Network, and projection-based methods that combine latent features through matrices, tensors, or projections.These models differ in expressive structure while remaining relational embedding approaches.
  • Translation Based Models: Translation-based models score facts through relation-specific translations or projections of entity embeddings, including TransE and TransR.TransR uses separate semantic spaces for entities and relations.
  • Limitation: These relational learning methods consider knowledge graphs as static models and lack the ability to capture temporally evolving dynamics.This limitation motivates methods that incorporate temporal modeling.
  • Temporal Modeling: Temporal point processes model intricate temporal behaviors in networks, while co-evolutionary embedding work captures self-evolution and co-evolution in interacting users and items.The related literature connects temporal event modeling with evolving representations.

7. Conclusion

The conclusion presents Know-Evolve as a deep evolutionary knowledge network for non-linear entity evolution and temporal reasoning in multi-relational graphs. It also describes Global BPTT as an efficient training procedure for coupled temporal and relational dependencies.

  • Conclusion: Know-Evolve learns non-linearly evolving entity representations in multi-relational settings using a deep evolutionary knowledge network.Its recurrent architecture captures subject and object evolution in relationship-specific spaces.
  • Conclusion: The model represents fact occurrence with a multivariate temporal point process whose intensity depends on dynamically evolving entity embeddings.This links relational compatibility with temporal dependencies across facts.
  • Training: Global BPTT trains on consecutive events within fixed-size sliding windows to handle coupled relational and temporal dependencies.Each window builds a computational graph, computes total loss and survival loss, and backpropagates through its time steps.
  • Training: The training procedure moves the sliding window through the global event sequence until reaching the stopping condition.The algorithm tracks the current index and window start time while iterating over event mini-batches.

B. Data Statistics and Sparsity of Knowledge Tensor

Table 1 provides statistics for each dataset.

  • Data Statistics: Table 1 reports dataset statistics for the temporal knowledge-graph experiments.The supplied passage contains the table caption but no individual statistics.

C. Implementation Details

The implementation uses graph-embedding methods to train over dynamic computational graphs and uniformly tuned TensorFlow baselines.

  • Data representation: Table 2 reports the sparsity of the knowledge tensor.
  • Dynamic training: Know-Evolve has a different computational graph for each mini-batch because interactions vary across time windows.The implementation uses a graph embedding framework designed for objectives whose computational graphs can differ by batch.
  • Baseline evaluation: All reported baseline methods were implemented in TensorFlow and evaluated uniformly with grid-searched hyperparameters and embedding sizes.Baselines use a contrastive max-margin objective and TensorFlow Adagrad optimization.

D. Parameter Complexity Analysis

The analysis compares parameter efficiency with relational baselines and illustrates reasoning behavior through a Cairo–Croatia temporal case study.

  • Parameter complexity: Know-Evolve uses significantly fewer parameters than Neural Tensor Network while remaining expressive according to its prediction performance.Across dataset configurations, its parameter count is comparable in order of magnitude to simpler relational models.
  • Case study setup: The Cairo–Croatia case study evaluates a test quadruplet involving an assault event on July 5, 2015.The relationship graph depicts the predicted edge from subject to object.
  • Prediction result: Rank-1: Know-Evolve predicted Croatia as the object, whereas baselines assigned ranks greater than 250.The event concerns an assault on a Croatian prisoner in Cairo.
  • Temporal and dynamic effects: Cairo’s recent training history contained increased assault activity, which the model captured as increased recent event intensity.The dataset also shows changing relationship patterns over time for Cairo and, to a lesser extent, Croatia.

CASE STUDY II: COMMON ENEMY FORGES FRIENDSHIP

The Colombia–Ottawa case study examines a previously unseen cooperation event and relates its prediction to temporal and mutual evolution across neighboring and third-party relationships.

  • Prediction result: Rank-1: Know-Evolve predicted Ottawa for a new Colombia–Ottawa material-cooperation event, while baselines ranked it greater than 250.The event was never observed during training and occurred on July 2, 2015.
  • Case study setup: The case study describes Colombia and Ottawa’s relationship histories using counts of involved nodes, events, and cooperation relations.Colombia participated in 1,604 events with 165 nodes, while Ottawa participated in 733 events with those nodes.
  • Temporal effect: Colombia’s more recent positive relationships with Venezuela and Venezuela’s cooperation with Ottawa provide temporal context for the predicted Canada relationship.The authors infer that Colombia was affected by recent interactions with its neighbors when forming the relationship with Canada.
  • Dynamic knowledge evolution: Colombia’s relationships evolved toward more positive interactions, while Ottawa’s features continued evolving positively because it had few negative relationships.
  • Mutual evolution: Mutual-evolution examples pair Colombia’s negative relationship with a third entity with that entity’s later positive relationship with Ottawa.The authors infer that cooperation with Ottawa could serve Colombia’s strategic interest against the third entity.

E.2. Sliding Window Training Experiment

The experiment addresses a fairness concern caused by Know-Evolve updating entity embeddings during testing by giving baselines a sliding-window training setup, then compares recurrent and new facts.

  • Sliding-window design: Know-Evolve updates entity embeddings after every test event, while model parameters remain fixed after training.Baselines were additionally evaluated with sliding-window training to reduce this potential advantage.
  • Sliding-window design: The sliding-window baseline protocol trains on six months, evaluates the first test window, then incorporates test data after discarding an equivalent two-week span.
  • Evaluation measure: Figure 10 compares sliding-window and non-sliding-window training using link-prediction rank.
  • Recurrent versus new facts: On GDELT-500, Know-Evolve performed consistently and significantly better than NTN on both recurrent-fact and new-fact test setups.New facts comprised 40%–60% of events in a specific test window and increased over time.
Loading 1705.05742v3…