Temporal Attribute Prediction via Joint Modeling of Multi-Relational Structure Evolution

1 Introduction

Many real-world scenarios exist where the time series can effectively be complemented with external knowledge. One such scenario represents information about the trade between countries in the form of a temporally evolving knowledge graph. The information about trade between the countries affects the corresponding currency exchange rate. Using information about trade, we want to better predict the currency exchange rate with high accuracy.

∗Equal Contribution

†Work done while at USC

1 https://github.com/INK-USC/DArtNet

Time Series forecasting deals with the prediction of the data points of the sequence at a future timestamp based on the data available up till the current timestamp. Methods such as Auto-Regressive Integrated Moving Average (ARIMA) model and Kalman filtering [Liu et al., 2011; Lippi et al., 2013] are popular for predicting time series. Representational learning on graph-structured data [Hamilton et al., 2017; Wu et al., 2019; Kipf and Welling, 2016; You et al., 2018] is a widely researched field with considerable focus on temporally-evolving graphs [Trivedi et al., 2018; Pareja et al., 2019; Kumar et al., 2018; Goyal et al., 2018]. The increasing amount of complex data that can be effectively represented using dynamic multi-relational graphs [Neil et al., 2018] has led to this increased focus on dynamic graph modeling. Several methods such as ConvE [Dettmers et al., 2017], RGCN [Schlichtkrull et al., 2018], and DistMult [Yang et al., 2014] have shown admirable results on modeling static, multi-relational graph data for link prediction. There are other approaches that attempt to model dynamic knowledge graphs by incorporating temporal information, and these include Know-Evolve [Trivedi et al., 2017], HyTE [Dasgupta et al., 2018], and TA-DistMult [Garc´ıaDur´an et al., 2018], among others.

The two aforementioned fields of time series prediction and representation learning on graphs have mainly been separated in the machine learning community. Recently some work has been done in integrating the two fields [Li et al., 2017], which describes a method to incorporate a static, unirelational graph for traffic flow prediction. However, this method is only limited to static graphs with a single relation. To date, no method has been proposed for integrating temporally evolving graphs and time series prediction. In this paper, we propose a new method for exploiting the information from the dynamic graphs for time series prediction. We propose the use of static learnable embedding to capture the spatial information from knowledge graphs and a dynamic embedding to capture the dynamics of the time series and the evolving graph.

We present the first-ever solution to the problem of timeseries prediction with temporal knowledge graphs (TKG). Since, to the best of our knowledge, currently no datasets exist which align with the problem statement, we prepared five suitable datasets through web scraping and evaluate our model. We show that our approach beats the current stateof-the-art methods for time series forecasting on all the five datasets. Our approach also predicts the time series by any number of time steps and does not require a test time graph structure for evaluation.

2 RelatedWork

We review work using static graphs for time series prediction and work on temporal knowledge graphs.

Time-series Prediction. In addition to the general timeseries prediction task, there have been some recent studies on the spatial-temporal forecasting problem. Diffusion Convolutional Recurrent Neural Network (DCRNN) [Li et al., 2017] is a method which incorporates a static, uni-relational graph for time series (traffic flow) forecasting. Traffic flow is modeled as a diffusion process on a directed graph. The method makes use of bidirectional random walks on the graph to capture the spatial dependency and uses an encoderdecoder framework with scheduled sampling for incorporating the temporal dependence. However, this method cannot be extended to temporally evolving graphs as well as multirelational graphs. Another paper on Relational Time Series Forecasting [Rossi, 2018], also formulates the problem of using dynamic graphs for time series prediction though it is not formulated for multi relational data. Neural relational inference [Kipf et al., 2018] also looks at the inverse problem of predicting dynamics of graph with attribute information.

Temporal Knowledge Graph Reasoning and Link Prediction. There have been several attempts on reasoning on dynamically evolving graphs. HyTE [Dasgupta et al., 2018] is a method for embedding knowledge graphs which views each timestamp in the graph data as a hyperplane. Each head, relation, tail triple at a particular timestamp is projected into the corresponding hyperplane. The translational distance, as defined by the TransE model [Bordes et al., 2013], of the projected embedding vectors, is minimized. TA-Distmult is a temporal-aware version of Distmult. For a quadruple h, r, t, τ, a predicate p is constructed using r, τ which is passed into an GRU. The last hidden state of the GRU is taken as the representation of the predicate sequence (ep). KnowEvolve [Trivedi et al., 2017] models a relationship between two nodes as a multivariate point process. Learned entity embeddings are used to calculate the score for that relation, which is used to modulate the intensity function of the point process. ReNet [Jin et al., 2019] uses the neighborhood aggregation and RNN to capture the spatial and temporal information in the graph.

3 ProblemFormulation

A Knowledge Graph is a multi-relational graph that can be represented in the form of triples (h, r, t) where h denotes the head, t denotes the tail, and r is the relation between the nodes h and t. A TKG has a time dimension as well, and the graph can be represented as quadruples in the form (h, r, t, τ ) where τ denotes the timestamp at which the relation r exists between the nodes h and t. We now introduce Dynamic Attributed Graphs, formalize our problem statement, and in later sections, present our model for making predictions on Dynamic Attributed Graphs.

Problem Definition. A Dynamic Attributed Graph (DAG) is a directed graph, where the edges are multi-relational with time stamp associated with each edge known as an event, and attributes associated with the nodes for that particular time. An event in dynamic graph is represented as a quadruple (h, r, t, τ) where h is the head entity, r is the relation, t is the tail entity and τ is the time stamp of the event. In a dynamic attributed graph, an event (Eτ) is represented as a hextuple (h, r, t, aτh , aτt , τ) where aτh and aτt are the attribute associated with head and tail at time τ. The collection of all the events at a time constitutes a dynamic graph Gτ where Gτ = {Eτi = (hi, ri, ti, aτhi , aτti , τi)|τi = τ, ∀i}. The goal of the DAG Prediction problem is to learn a representation of the dynamic graph events and predict the attributes at each node at future timestamps by learning a set of functions to predict the events for the next time step. Link is predicted jointly, to aid the attribute prediction task. Formally, we want to learn a set of functions {F(.)} such that:

We divide the dynamic graph at any time τ in two sets, one consisting of only (h, r, t, τ) and other consisting of only the attribute values. Formally, Gτ = GIτ ∪ GAτ , where GIτ = {EI τi = (hi, ri, ti, τi)|τi = τ, ∀i} and GAτ = {aτhi |τi = τ, ∀i}. We propose to predict GI and GA using these set of functions as follows:

We jointly predict the graph structure GIτ ′ and the attribute values GAτ ′ and show that the attribute values are being predicted with greater accuracy than can be done using any existing method.

4 Proposed Framework : DARTNET

We now present our framework for learning the set of functions for predicting the events for the next timestamp, given the history. We name our framework DARTNET which stands for Dynamic Attributed Network.

We model the changing graph structure and attribute values by learning an entity-specific representation. We define the representation of an entity in the graph as a combination of a static learnable embedding which does not change with time and represent static characteristics of each node, and a dynamic embedding which depends on the attribute value at that time and represent dynamically evolving property of each node. We then aggregate the information using the mean of neighborhood entities. For every entity in the graph, we model history encoding using a Recurrent Neural Network. Finally, we use a fully connected network for attribute prediction and link prediction tasks.

4.1 Representation Learning on Events

The main component of our framework is to learn a representation over the events which will be used for predicting future events. We learn a head-specific representation and then model its history using Recurrent Neural Network (RNN). Let Eh,τ represent the events associated with head h at time τ, i.e., Eh,τ = {(h, ri, ti, aτh , aτti , τi)|τi = τ, ∀i}. For each entity in the graph, we decompose the information in two parts, static information and dynamic information. Static information does not change over time and represents the inherent information for the entity. Dynamic information changes over time. It represents the information that is affected by all the external variables for the entity. For every entity h in the graph at time τ , we construct an embedding for the entity which consists of two components:

1. Static (Constant) learnable embedding (ch) which does not change over time.
2. Dynamic embedding (dh,τ = ah,τ ·W1) which changes over time.

where ch ∈ Rd , ah,τ ∈ Rk is the attribute of entity h at time τ andW1 ∈ Rk×d is learnable parameter. The attribute value can be a multi-dimensional vector with k ≥ 1 representing multiple time-series associated with same head. Hence the embedding of entity h becomes eh,τ = (ch; dh,τ) where ; is the concatenation operator. For every relation (link) r, we construct a learnable static embedding er ∈ Rd .

To capture the neighbourhood information of entity h at time τ from the dynamic graph, we propose two spatial embeddings: attribute embedding (Ah,τ) and interaction embedding (Ih,τ). Ah,τ captures the spatio-attribute information from the neighbourhood of the entity h and Ih,τ captures the spatio-interaction information from the neighbourhood of the entity h. Mathematically, we can define the spatial embeddings as:

(2) where |Eh,τ | is the cardinality of set Eh,τ andW2 ∈ R3d×d andW3 ∈ R2d×d are learnable parameters.

4.2 Learning Temporal Dependency

The embeddings Ih,τ , Ah,τ capture the spatial information for entity h at time τ . For predicting the information at future time, we need to capture the temporal dependence of the information. To keep track of the interactions and the attribute evolution over time, we model the history using Gated Recurrent Unit [Cho et al., 2014], an RNN. For the head s, we define the encoded attribute history at time τ as the sequence [Ah,1,Ah,2, . . . ,Ah,τ-1] and the encoded interaction history at time τ as the sequence [Ih,1, Ih,2, . . . , Ih,τ-1]. These sequence provide the full information about the evolution of the head h till time τ. To represent in sequences, we model the encoded attribute and encoded interaction history for head h as follows:

where the vector HA(h, τ) captures the spatio-temporal information for the attribute evolution i.e. captures how the attribute value of the entity evolves over time with respect to the evolving graph structure, while the vector HI(h, r, τ) captures the spatio-temporal information of how the relation r is associated with the entity h over time. We show the DARTNET, its input and output in Figure 2.

4.3 Prediction Functions

The main aim of the model is to be able to predict the future attribute values as well as the interaction events. To get the complete information of the event at next time step, we perform the prediction in two steps: (1) prediction of the attribute values for the whole graph and (2) prediction of the interaction events for the graph. We know Gτ+1 = {Eτi = (hi, ri, ti, aτhi , aτti , τi)|τi = τ + 1, ∀i}. To predict Gτ+1, we divide it into two sets GIτ+1 and GAτ+1 . The attribute values of GAτ+1 are predicted directly and modelled as follows:

The attribute value for the entity is a function of the spatioattribute history for the entity and the static information about the entity. Attribute prediction requires graph structures, so we also predict graph structures. The probability of GIτ+1 is modeled as:

At τ + 1, we can write this probability as

In this work, we consider the case that probability of (h, r) is independent of the past graphs {G1, . . . ,Gτ}, and model it using uniform distribution, leading to

For predicting the interaction at future timestamp, we model the probability of the tail as follows:

The functions fA and fI can be any function. In our experiments we use the functions as a single-layered feed-forward network.

4.4 Parameter Learning

We use multi-task learning [Ruder, 2017; Caruana, 1997] loss for optimizing the parameters. We minimize the attribute prediction loss and graph prediction loss jointly. The total loss L = LI + λLA, where LI is interaction loss, LA is attribute loss and λ is a hyperparameter deciding the weight of both the tasks. For the attribute loss, we use the mean-squared error LA = 1N ∑Ni=1 (a′ hi,τi -ahi,τi )2 , where a′hi,τi is the predicted attribute and ahi,τi is the ground truth attribute. For the interaction loss, we use the standard multi-class cross entropy loss, LI = ∑Ni=1 ∑Mc=1 yj log(Pr(t = c|hi, ri)), where the M is the number classes i.e. number of entities in our case.

4.5 Forecasting Over Time

At each inference time, DARTNET predicts future interactions and attributes based on the previous observations, i.e.,

[(GIi ,GAi )]τi=0 . To predict interactions and attributes at time τ + ∆τ , DARTNET adopts multi-step inference and predicts in a sequential manner. At each time step, we compute the probability Pr(t|h, r, G1, . . . , Gτ ) to predict GAτ+1 . We rank the tails predicted and choose the top-k tails as the predicted values. We use the predicted tails as GAτ+1 for further inference. Also, we predict attributes, which yields GIτ+1 . Now we have graph structure and attributes at time τ + 1. We repeat this process until we get (GIτ+∆τ-1 ,GAτ+∆τ-1 ). Then we can predict interactions and attributes at time τ+∆τ based on [(GIi ,GAi )]τ+∆τ-1 i=0 .

5 Experiments

In this section, we evaluate our proposed method DARTNET on a temporal attribute prediction task on five datasets.The attribute prediction task predicts future attributes for each node.

We evaluate our proposed method on two tasks: (1) predicting future attributes associated with each node on five datasets; (2) studying variations and parameter sensitivity of our proposed method. We will summarize the datasets, evaluation metrics, and baseline methods in the following sections.

5.1 Datasets

Due to the unavailability of datasets satisfying our problem statement, we curated appropriate datasets by scraping the web. We created and tested our approach on the datasets described below. Statistics of datasets are described in Table 1.

Attributed Trade graph (ATG). This dynamic graph represents the net export from one country (node) to another, where each edge belongs to an order of trade segment (in a million dollars). The month-averaged currency exchange rate of the corresponding country in SDRs per currency unit is the time series attribute value.

Co-authorship-Citation dataset (CAC). Each edge in the graph represents the collaboration between the authors (node) of the research paper. The number of citations per year for an author is the corresponding time series attribute for the node.

Multi-attributed Trade graph (MTG). This is a subset of ATG, with a multi attributed time series representing monthly Net Export Price Index and the value of International Reserves assets in millions of US dollars.

Attributed GDELT graph (AGG). Global Database of Events, Language, and Tone (GDELT) represents a different type of event in a month between entities like political leaders, organizations, and countries, etc. Here only country nodes are associated with a time-series attribute, which is taken as the Currency Exchange Rate.

5.2 EvaluationMetrics

The aim is to predict attribute values at each node at future timestamps. For this purpose, Mean Squared Error (MSE) loss is used. The lower MSE indicates better performance.

5.3 Baseline Methods

We show that the results produced by our model outperform those of the existing time series forecasting models. We compare against two kinds of attribute prediction methods.

Time series prediction without TKG. These methods do not take into account the graph data and make predictions using just the time-series history available. We compare our model to Historic Average (HA), Vector AutoRegressive (VAR) model [Hamilton, 1994], Autoregressive Integrated Moving Average (ARIMA) model, and GRU based Seq2Seq [Sutskever et al., 2014]. HA makes predictions based on the weighted average of the previous time series values, ARIMA uses lagged observations for prediction and VAR predicts multiple time series simultaneously by capturing linear interdependencies among multiple time series.

Time series prediction with TKG. Node embeddings are learned using graph representational learning methods (both static and temporal) like RE-NET, HyTE, TA-DistMult, and ConvE. For each node, the attribute value at a particular timestamp is concatenated with the corresponding node embedding, and this data is passed into an GRU network for making predictions.

Hyperparameter settings. All models are implemented in PyTorch using Adam Optimizer for training. The best hyperparameters are chosen using the validation dataset. Typically increasing value of λ gives better results, and the best results on each dataset are reported.

2 https://github.com/liyaguang/DCRNN

3 https://github.com/TimDettmers/ConvE

4 https://github.com/malllabiisc/HyTE

5.4 Main Results

The results for the attribute prediction on different datasets are reported in Table 2. We see that our method DARTNET outperforms every other baseline for the attribute prediction by a large margin. From the results it is clear, that the neural network based models outperform the other baselines on these complicated datasets proving their long term modeling capacity. We observe that the relational methods using graph information, generally outperform the non-relational methods on attribute prediction. Large increase in performance is observed for more complicated datasets like MTG and AGG. This suggests that it is the right direction for research to use relational methods for attribute prediction. DARTNET outperforms other relational methods, which does not jointly train embeddings for attribute prediction and link prediction. This suggests that joint training of embeddings for attribute prediction and link prediction improves the performance on attribute prediction rather than training embeddings separately and then using it for attribute prediction.

5.5 Performance Analysis

To study the effects of changes in model parameter sharing and hyperparameter sensitivity on prediction, we perform several ablation studies for DARTNET on four datasets as AGG does not have attribute values over all nodes.

1. Decoupling of Attribute prediction and Interaction prediction tasks. We decouple the shared parameters ch andW1 for both tasks and observe the performance. More formally, we use a different embedding for both tasks, i.e cIh ,WI1 and cAh ,WA 1 as the parameters for link prediction and attribute prediction task respectively.
2. Sharing history. We study the effect of using the same history embedding for both link prediction and attribute prediction. This will help us study if similar history information is required for both the tasks. Here the HI

does not explicitly get the related information so that we can share the weights. Hence the new equations become:

where the parameters of both the RNNs are shared.

1. Study of Time-Dependent Information. We evaluate the performance of our model in the absence of any temporal information. Hence we do not encode any history for any task and directly predict the tails and the attribute values at a future timestamp. Hence equations are:

Analysis on Variants of DARTNET. Figure 3 shows the variation of Attribute Loss with different variants of DARTNET proposed in Section 5.5. From Figure 3, we observe that our model outperforms the decoupled variant by a large margin for attribute prediction. This confirms the hypothesis that joint training of attribute prediction and link prediction performs better than training separately. We also see that sharing history for attribute prediction and link prediction deteriorates the results, which indicates that the history encoding information required for link prediction and attribute prediction is quite different from each other. Lastly, the time-independent variant of our framework performs poorly. This clearly indicates that the temporal evolution information is essential for proper inference.

Sensitivity analysis of hyperparameter λ. We perform the sensitivity analysis of parameter λ, which specifies the weight given to both the tasks. We show the variation of MSE loss for attribute prediction task with λ. Figures 4 shows the variation of Attribute Loss with increasing λ. In Figure 4, we observe that Attribute value decreases with increasing λ. As expected, as increasing lambda favors the optimization of attribute loss while decreasing lambda favors the link prediction.

6 Conclusion and FutureWork

In this paper, we propose to jointly model the attribute prediction and link prediction on a temporally evolving graph. We propose a novel framework DARTNET, which uses two recurrent neural networks to encode the history for the graph. The framework shares the parameter for the two tasks and jointly trains the two tasks using multi-task learning. Through various experiments, we show that our framework is able to achieve better performance on attribute prediction than the previous methods indicating that external knowledge is useful for time series prediction. Interesting future work includes the link prediction on graph level rather than on subject and relation level in a memory-optimized way.

Acknowledgements

This research is based upon work supported in part by NSF SMA 18-29268 and United States Office Of Naval Research under Contract No. N660011924033.The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies, either expressed or implied, of the U.S. Government. We would like to thank all the collaborators in USC INK research lab for their constructive feedback on the work.