MERIT: Learning Multi-level Representations on Temporal Graphs

1 Introduction

Graph representation learning, which is devoted to embedding graph into low dimensional space, has drawn increasing attention in recent years. Following this line, several efforts have been made for graph structural feature extraction and attained considerable success, most notably proximitypreserving methods [Grover and Leskovec, 2016; Wang et al., 2016; Zhang et al., 2018] and recently emerging graph neural network (GNN) based methods [Kipf and Welling, 2017; Velickovic et al., 2018; Hamilton et al., 2017]. Despite excellent performance, these methods only consider static or nontemporal graphs, while real-world graphs are dynamic and continuously evolving, such as social graphs and user-item interaction graphs derived from recommender systems. Ignoring such temporal information may achieve unpromising performance for dynamic graph learning. Taking Fig. 1 as an example, the target user clicks different items over a period of time, indicating his/her intent or interest changes over time. This phenomenon drives us to learn the dynamic representation for the target user to adapt for the evolution of the graph structure.

∗Equal contributions.

†Corresponding author.

To leverage temporal information, a series of recent research has shifted increasing attention towards representation learning on temporal graphs based on temporal random walk [Du et al., 2018; Singer et al., 2019], snapshots [Yu et al., 2018; Guo et al., 2019; Yang et al., 2020] and temporal kernels over continuous time [Zuo et al., 2018; Lu et al., 2019; Huang et al., 2020; Xu et al., 2020]. Although considerable success has been attained, current studies commonly ignore the fact that different types of interactions (e.g., user-item) on temporal graphs show temporal patterns in multi-level, which potentially implies users' underlying preferences 1 , as shown in Fig. 1. Additionally, most of them overlook rich attributes on nodes and edges, and usually are designed for specific tasks (e.g., traffic flow forecasting and financial risk analysis). We believe it is critically important to develop an inductive architecture for temporal graph representation in a more principled way, which hinges on jointly characterizing individual- and combinatorial-level patterns:

1 Multi-level context also arises in other general graphs, e.g., temporal financial graphs and social graphs.

• Individual level. Due to evolving nature on temporal graphs, we are interested in patterns related to timespans between each individual node involved, where different time intervals may imply different correlations between adjacent interactions. Taking Fig. 1 as an example, the target user at t6 is willing to interact with "Dessert" when |t4 - t3| is small (e.g., related necessities) while "Milky tea" is preferred when |t4 - t3| and |t5 - t4| are large (e.g., daily / weekly intents).
• Combinatorial level. Current graph attention based methods [Velickovic et al., 2018; Xu et al., 2020] independently model each neighbor's effect on the target node, but ignore the effect from the combinatorial context, which aims at capturing high-level semantic among neighbors in continuous time. Specifically, given ⟨Milky tea, t1⟩ and ⟨Hot pot, t2⟩ in Fig. 1 (Assuming that |t2 - t1| < 12h, and |t3 - t2|, |t4 - t3|, |t5 - t4| > 12h), we consider their effects towards the target node from following two aspects. If we consider them independently, "Dessert" or "Milky tea" will be recommended based on the consumption habit in daily life, since the target user shows similar preferences at t3, t4, t5. On the comparison, if we jointly consider them as the combinatorial-level context, we could abstract that the target user maybe in shopping mall, a high-level semantic hard to be captured in the first way. Therefore, "Barbecue" is more proper to be recommended. In sum, such context, as high-level semantic among neighbors, is of crucial importance for temporal graph representation learning.

In this paper, by integrating above properties together, we propose MERIT, a novel Multi-lEvel gRaph attentIon neTwork for inductive representation learning on temporal graphs. In particular, we take the inspiration from the recently emerging graph neural networks, which have the potential of capturing high-order structural information in an inductive manner [Cai et al., 2018; Velickovic et al., 2018; Hamilton et al., 2017], but have not been explored much for temporal graphs in continuous time. Benefiting from Mercer's Theorem [Minh et al., 2006; Xu et al., 2019], we propose a Personalized Time Encoding (PTE) module for transforming the original timespans into a higher, continuous space in a personalized manner, targeting for effectively preserving individual-level periodicity on temporal graphs. Subsequently, a novel Continuous time and context aware Attention (Coco-Attention) mechanism is developed to chronologically emphasize core local structure by jointly considering individual- and combinatorial-level context. At last, MERIT performs multiple aggregations and propagations to comprehensively explore high-order structural information in continuous time, followed by the end-to-end training for various downstream tasks. In sum, we make the following contributions:

• We highlight the crucial importance of explicitly exploring
• individual- and combinatorial-level patterns for representation learning on temporal graphs, and make the first step to characterize these properties together with an unified model in a principled way.
• We propose a novel model MERIT that is equipped with PTE module for depicting individual-level periodicity in a personalized manner and Coco-Attention mechanism where multi-level context is jointly captured.
• We perform extensive experiments on four public datasets in both transductive and inductive settings. Results demonstrate that MERIT consistently and significantly outperforms various state-of-the-art methods.

2 RelatedWork

Graph representation learning has shown its potential in structure feature extraction and has been widely applied in many data mining tasks [Cai et al., 2018]. Conventional graph representation learning methods have been developed to preserve graph topology [Grover and Leskovec, 2016; Wang et al., 2016; Zhang et al., 2018]. With the advent of deep learning methods, significant efforts have been devoted to developing neural network-based representation learning methods [Kipf and Welling, 2017; Hamilton et al., 2017; Velickovic et al., 2018; Liu et al., 2022; Bo et al., 2022]. Unfortunately, they are only designed for static graphs, which cannot capture dynamic natures on temporal graphs.

Recently, attention is increasingly shifted towards representation learning on temporal graphs [Kazemi et al., 2020]. Early methods [Du et al., 2018; Singer et al., 2019; Nguyen et al., 2018] attempt to learn dynamic representations with temporal random walk and extended skip-gram model, and subsequently achieve superior performance on transductive tasks. Taking advantages of information propagation, a series of spatial-temporal graph neural networks [Seo et al., 2018; Yang et al., 2020; Guo et al., 2019] are proposed for temporal graphs, which utilize the temporal aggregator for integrating representations learned from each graph snapshot. As a major weakness, these methods ignore the dynamic nature in each graph snapshot, resulting in sub-optimal performance. In order to capture the evolving patterns of graph representation over time, a series of works are proposed to embed temporal graph in continuous time [Kumar et al., 2019; Lu et al., 2019; Zuo et al., 2018; Xu et al., 2020; Huang et al., 2020; Wang et al., 2021].

Nevertheless, all the above-mentioned methods deal with temporal graphs by independently modeling each dynamic interaction, failing to explore the effectiveness of multi-level patterns. In this paper, we jointly incorporate individual- and combinatorial-level context into an unified graph neural network framework for powerful inductive representation learning on temporal graphs.

3 The ProposedMethod

In this section, we propose MERIT, a Multi-lEvel gRaph attentIon neTwork for representation learning on temporal graphs. The overall architecture of the proposed MERIT is shown in Fig. 2. Let's begin with some notations and definitions.

3.1 Notations and Definitions

Our study focuses on temporal graphs, which can be defined as follows,

Definition 1. Temporal Graph. A temporal graph G = {V, E, T } is a form of graph with timestamps, where V and E are sets of nodes and edges, and T is the sequence of timestamps. Each edge (u, v) ∈ E is associated with a timestamp t ∈ T , referring to an interaction involving node u and node v at time t.

Now, we formally define the problem studied in this paper as follows,

Definition 2. Temporal Graph Representation Learning. Given a temporal graph G = {V, E, T }, we aim to learn a mapping function f : V × T → Rd , where d is the number of embedding dimensions and d ≪ |V|. The mapping function f is expected to produce representation for each target node v ∈ V at target timestamp t ∈ T with corresponding sub-graph before timestamp t.

3.2 Personalized Time Encoding

Time encoding is at the heart of the representation learning on temporal graphs, which refers to capturing dynamic nature over a period of time. Most importantly, we should notice that temporal modeling is highly time-sensitive and each node plays a different role and shows different pattern towards neighbors. Hence, we introduce a Personalized Time Encoding (PTE) module that can adaptively learn individuallevel periodicity for each target node.

Formally, the goal of time encoding is to find a mapping Φ : T → Rd from time domain T to d-dimensional vector space. Considering arbitrary timestamp t ∈ T , suggested by Mercer's Theorem [Minh et al., 2006; Xu et al., 2019], we define the mapping as follows:

where {ci}∞i=1 and {ϕi(·)}∞i=1 is an associated set of nonnegative eigenvalues and a sequence of eigenfunctions, respectively [Minh et al., 2006]. Intuitively, temporal patterns can be detected from a finite set of periodic kernels. Following the proposition introduced in [Xu et al., 2019], we further formulate the mapping function Φ with frequency parameter ω as below:

Fortunately, such a Fourier series-like form has nice truncation properties, which drive us to truncate above mapping function Φω(t) as Φω,d(t) . Subsequently, by concatenating multiple truncated periodic mapping functions, parameterized by the frequency set {ω1, ..., ωk}, we encode the functional time as:

It is worthwhile to note that the Fourier coefficients in Eq. 2 (i.e., ci, i = 1, 2, ...) are not personalized. That is, the above time encoding is irrelevant to the corresponding node representations on temporal graphs. Specifically, Eq. 3 tends to obtain the same time encoding for two different nodes with same timestamps. Such a paradigm for time encoding is improper to be directly incorporated into following attention mechanism. Therefore, giving a target node u, we further formulate our personalized periodic kernel for u as follows,

Here, ci(u) : Rd → R, i = 1, 2, , ... are personalized mapping functions for Fourier coefficients w.r.t. node u. Empirically, we implement ci(·) as a multi-layer perceptron (MLP) due to its strong ability in modeling complex interaction. Moreover, we enforce the outputs of MLPs to be non-negative (i.e., Softplus activation function is adopted in the output layer.), in order to satisfy the intrinsic properties of the Mercer's Theorem. The input of the mapping function is the representation of node u, denoted as hu. In sum, we redefine the time encoding via our proposed PTE module as:

3.3 Continuous Time and Context aware Attention Mechanism

With the help of the PTE module, we encode the timestamps into a continuous, higher dimensional space for preserving the temporal patterns for each node in a personalized manner. Next, we introduce the Continuous time and Context aware Attention (Coco-Attention) mechanism that can chronologically tell the difference of local neighbors by jointly capturing multi-level context on temporal graphs.

Continuous time aware. Now, we start with the continuous time aware attention for effectively capturing local structure while preserving individual-level dynamic in temporal graphs, as well as the overall pipeline of Coco-Attention calculation for MERIT. We build upon the architecture of the recently emerging graph attention mechanism [Velickovic et al., 2018] to weigh various underlying preferences for interactions between connected nodes. Specifically, given a target node u at time t, we aim to produce the attention distribution of u towards its neighbors Nu(t) = {v|tv<t}, followed by a weighted combination for the final representations. Due to the translation-invariant property for the temporal kernel, we can alternatively use {t-tv}v∈Nu(t) as interaction times. Formally, we first calculate the Coco-Attention weight involving target node u and one of its neighbor v ∈ Nu(t) at time t as follows:

where "||" denotes the concatenation operation, d is the dimension of the node representation, 0 is the all-zero vector, WQ andWK is the projection matrice to obtain the "query" and "key" matrix, respectively [Vaswani et al., 2017], and eu,v(t) is the feature vector for the edge connecting u and v at time t. F (l-1) (v, t, tv) is the context modeling part, which will be introduced in next subsection. Obviously, we can easily extend it to multi-head attention for the stable training process. Due to page limitation, we omit it here.

Next, we produce the continuous time aware representation for target node u at time t through l-th layer in MERIT 2 as follows,

where WV is the projection matrix to generate the "value" matrix [Vaswani et al., 2017].

Context aware. As mentioned above, current CocoAttention mechanism is sufficient to capture individuallevel patterns in temporal graphs by incorporating multiscale (small / large) time interval into attention calculation in continuous space. As another major component of Coco-Attention mechanism, we further introduce the combinatorial-level context modeling, i.e., F (l-1) (v, t, tv). Formally, with the contextual neighbors Su,v(tv) = {v′ ∈ Nu(t)|tv′ ≤ tv} for neighbor node v at time tv, we implement F(·) using two types of aggregators:

• Recursive aggregator applies complex LSTM architecture on the sequential context to endow MERIT layer with excellent expressive capability.

• Convolutional aggregator applies convolution-like operator for more scalable implementation.

whereW∈ R|Su,v(tv)|×d×d is the convolution kernel.

2 MERIT follows the classical architectures of graph neural networks with multiple layers.

3.4 Model Learning

Naturally, MERIT performs multiple aggregations and propagations to explore high-order structural information in a broader and deeper way. With the initial representations {h(0) v (t)}v∈V for nodes set V at time t, we rewrite the final temporal representations after L layers of MERIT as {hfv (t) = h(L) v (t)}v∈V. Following previous studies, we could learn parameters of MERIT through various downstream applications with specific loss functions [Xu et al., 2020; Lu et al., 2019], e.g., link prediction and node classification.

Complexity. To speed up the training process, we randomly collect L-hop neighbors set for each node in mini-batch if we aim to stack L layers in MERIT. Since the masked selfattention operation is parallelizable [Velickovic et al., 2018], the time complexity of each layer in MERIT with K heads and L layers for each batch is approximately O((K · ˜N)L), where ˜N is the number of neighbors sampled for each node. Clearly, the time complexity of MERIT is comparable with GAT, which is verified in the Fig. 3. In addition, Fig. 3 shows that MERIT achieves faster convergence speed and better performance. Actually, MERIT has been deployed in industrial recommender systems to support very large-scale temporal graphs, consisting of hundreds of millions of nodes and edges.

4 Experiments

In this section, we perform a series of experiments on four datasets to demonstrate the effectiveness of MERIT.

4.1 Experimental Setup

Evaluation Datasets and Metrics. We conduct extensive experiments on four widely used datasets [Kumar et al., 2019] from different domains, namly Reddit, Wikipedia, MOOC and LastFM. In particular, we calculate the Average Repetitive Rate (ARR) of user behaviors for the four datasets adopted in [Bai et al., 2019] to reveal the periodicity. We summarize the statistics of the four datasets in Table 1.

In our experiments, we adopt commonly used average precision (AP) and Accuracy for the link prediction evaluation and area under the ROC curve (AUC) for the node classification evaluation.

Baselines We compare MERIT with ten state-of-art methods, falling into three main groups: i) deep recurrent neural network based methods (i.e., Time-LSTM [Zhu et al., 2017] and Jodie [Kumar et al., 2019]) learning dynamic embeddings from a sequence of temporal interactions, static graph neural network based methods (i.e., GraphSAGE [Hamilton et al., 2017] and GAT [Velickovic et al., 2018]) capturing high-order structure with information propagation and temporal graph representation learning methods (i.e., CTDNE [Nguyen et al., 2018], M2DNE [Lu et al., 2019], GCRN [Seo et al., 2018], GraphSAGE-T, GAT-T and TGAT [Xu et al., 2020]) well designed for temporal graphs.

For our model, we report its performance with different context aggregators, i.e., MERITR with recursive aggregator and MERITC with convolutional aggregator.

Significance Test For results in Tables 2 and 3, we use ** (or *) to indicate that the improvement of MERIT over the best performance from the best baseline is significant based on paired t-test at the significance level of 0.01 (or 0.05).

4.2 Experimental Results and Analysis

Overall Performance Comparison

From the experimental results in Table 2 and Table 3, firstly, we observe that our proposed MERIT model consistently outperforms all the baselines on both link prediction and node classification tasks, demonstrating the effectiveness of MERIT. Not surprisingly, MERITR slightly outperforms MERITC due to excellent expressive capability of LSTM architecture. Secondly, compared to traditional graph neural networks, the performance gains of temporal graph representation learning methods are attributed to the functional time encoding on temporal graphs. Particularly, we also observe that the performance margin in Reddit is relatively small, on account of the weak periodicity in this dataset (i.e., small ARR in Table 1). Thirdly, graph neural network based methods achieve better performance than deep recurrent neural network based methods in most cases, which indicates the usefulness of high-order structural information and the rich attributes on edges.

Ablation Study

We perform a series of ablation studies to better understand the traits of MERIT. Noting that MERIT will use the Recursive aggregator, i.e.,MERITR by default in what follows since it performs best. Due to the page limitation, we only present results of parameter studies and attention analysis on Wikipedia dataset with link prediction task, and similar trends can be observed on other datasets.

Impact of Personalization and Context Modeling. We prepare two variants of MERIT for comparison, namely MERIT-P (MERIT without personalization modeling in PTE module) and MERIT-C (MERIT without context modeling in Coco-Attention mechanism). Moreover, we select the TAGT as the reference baseline and report the comparison results in Fig. 4. Not surprisingly, we find that the overall performance order is as follows: MERIT > MERIT-P , MERIT-C > TGAT. The results show that it is necessary to adaptively learn proper Fourier coefficients in periodic kernels for enhancing temporal representations, while related combinatorial-level context information is also of crucial importance to be captured.

Impact of the Number of Periodic Kernels. Here, we analyze the impact of the number of periodic kernels (i.e., k in Eq. 5) by varying it in the set of {1, 3, 5, 7, 9}. In Fig 5 (a), it is clear that the optimal performance is achieved with k = 5, demonstrating a proper number of periodic kernels is beneficial to effectively capture temporal patterns. However, a larger k may lead to overfitting issue.

Impact of the Truncated Dimension. Similarly, we investigate into the impact of the truncated dimension d (See Eq. 3) by varying it in the set of {8, 16, 32, 64, 128, 256}. As shown in Fig 5 (b), MERIT achieves the best performance when d = 32 or d = 64. Overall, our model is not sensitive to this parameter due to the nice truncation properties of Fourier series-like form.

Attention Weight Analysis

We first present the macro-level analysis of the attention distributions on three datasets (i.e., Reddit, Wikipedia and Mooc), which aims at analyzing how the attention weights change w.r.t. the timespans of previous interactions. Specifically, for each node pair ⟨u, v, t⟩, we plot the attention weights {αu,v′ (t)|v′ ∈ Nu(t)} ⋃{αu′ ,v(t)|u′ ∈ Nv(t)}

against {t - tu,v′} ⋃{t - tu′ ,v}. we report the results in Fig. 6 (a), where a smaller timespan means a more recent interaction. It is clear that timespans and the corresponding attention weights are negatively correlated, which means that MERIT captures the temporal patterns of putting less attention on more distant interactions.

From micro-level view, we select a certain user fromWikepedia dataset and plot his/her attention weight against timespans of historical interactions as an illustrative example. In Fig. 6 (b), we observe that the attention weight decreases periodically with the increase of timespans. This finding is consistent with our intuition that user's intention or interest will periodically change over time.

5 Conclusion and FutureWork

In this paper, we proposed the novel MERIT model, which consists of PTE module for characterizing individual-level periodicity in an personalized manner and Coco-Attention mechanism for jointly capturing multi-level context. Extensive experiments demonstrate the superior performance of MERIT in both node classification and link prediction tasks. As future work, we will keep on investigating into the functional time encoding for automatically learning the parameters (i.e., {ω1, ..., ωk}) of periodic kernels. Moreover, we will also consider incorporating temporal point process to replace current MLP component as a decoder for dynamics modeling.

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (No.72192823 and No.62172362).