Title: DEEP INTERACTION PROCESSES FOR TIME-EVOLVING GRAPHS Anonymous

Abstract: Time-evolving graphs are ubiquitous such as online transactions on an e-commerce platform and user interactions on social networks. While neural approaches have been proposed for graph modeling, most of them focus on static graphs. In this paper we present a principled deep neural approach that models continuous timeevolving graphs at multiple time resolutions based on a temporal point process framework. To model the dependency between latent dynamic representations of each node, we define a mixture of temporal cascades in which a node's neural representation depends on not only this node's previous representations but also the previous representations of related nodes that have interacted with this node. We generalize LSTM on this temporal cascade mixture and introduce novel time gates to model time intervals between interactions. Furthermore, we introduce a selection mechanism that gives important nodes large influence in both k-depth subgraphs of nodes in an interaction. To capture temporal dependency at multiple time-resolutions, we stack our neural representations in several layers and fuse them based on attention. Meanwhile, our method can process unseen nodes and their interactions. Experimental results on interaction prediction and classification tasks -including a real-world financial application -illustrate the effectiveness of the time gate, the selection and fusion mechanisms of our approach, as well as its superior performance over the alternative approaches.

1. INTRODUCTION:

Representation learning over graph data has become a core machine learning task with a wide range of applications including e-commerce, finance, social networks, and bioinformatics. Various neural graph representations such as (Perozzi et al., 2014; Grover & Leskovec, 2016; Wang et al., 2016; Kipf & Welling, 2017; Defferrard et al., 2016; Scarselli et al., 2009; Ying et al., 2018; Hamilton et al., 2017b; Monti et al., 2017; Den Berg et al., 2017) have been proposed to learn from static graph data and successfully used for downstream tasks (e.g., classification). Graph data, however, are often dynamic in practice; nodes and interactions between them can grow and shrink. A straightforward approach to handle dynamic graphs is to compress them into one or several static graphs. The drawbacks of this approach are multifold; we not only blur temporal structural information but also miss time information that can be critical for real-world applications. An illustrative example is given in figure 1 .

To handle continuous time-evolving graph, we can approximate a by a sequence of snapshot graphs, each of which includes all interactions that occur during a user-specified discrete-time interval, as shown in (Goyal et al., 2018; Leskovec et al., 2007; Zhou et al., 2018; Sankar et al., 2019) . This treatment reduces time resolution and it is tricky to specify the appropriate aggregation granularity. To avoid these problems, Nguyen et al. (2018) proposed continuous-time dynamic networks (CTDNE) that generalize deep walk methods to learn time-dependent network embedding. As a transductive method, CTDNE cannot handle the growth of new nodes. Dai et al. (2016) applied temporal point processes to model time-evolving graphs and, as a nonparametric Bayesian approach, their approach can naturally cope with the growth of new nodes and interactions. They used recurrent neural networks (RNNs) to define an intensity function in temporal point processes. These RNN models are shallow and one-step unrolled, making it easy to compute but relatively limited in modeling power. Trivedi et al. (2019) extended this approach by modeling two-time scale and adopting temporal-attention mechanism. It can be revealed by high-frequency transactions with multiple merchants. However, if we merge the transaction data into a static graph, we cannot distinguish it from the static graph generated from normal online shopping activities. Thus, learning from such a static graph will fail to detect the cash-out event.

In this paper we present a powerful deep neural approach that models continuous time-evolving graphs at multiple time resolutions based on a temporal point process framework. We name the new approach deep interaction processes (DIPs). To model the dependency between latent dynamic representations of each node, we define a mixture of temporal cascades in which a node's neural representation depends on not only this node's previous representations but also the previous representations of related nodes that have interacted with this node. We generalize LSTM on this temporal cascade mixture and introduce novel time gates to model time intervals between interactions. Furthermore, We introduce a selection mechanism that gives important nodes large influence in both k-depth subgraphs of nodes in an interaction. To obtain representations from fine-to-coarse time-resolutions, we stack our neural representations in several layers and fuse them based on attention. Based on the temporal point process framework, our approach can naturally handle growth of graph nodes and interactions, making it inductive.

The rest of the paper is organized as follows. In Section 2 we give background on temporal point processes and in Section 3 we present the new DIP approach. In Section 4 we discuss related works.

In Section 5 we report experimental results on multiple interaction prediction and classification tasks including an important real-world anti-fraud financial application, demonstrating superior performance of the new approach over the alternatives.

2. TEMPORAL POINT PROCESSES:

We first describe temporal point processes (a class of nonparametric Bayesian models) that our approach is based on. Specifically, a temporal point process is a stochastic process that generates a sequence of discrete events localized at times {t i } N i=1 in any given observed time window [0, T ], where N is the number of events. An important way to characterize temporal point processes is via the conditional intensity function λ (t|H t ) -the stochastic model for the next event time t given all historical events before time t, denoted as H t = {t i |t i < t}. Formally, within a small time window [t, t + dt), λ (t|H t ) dt is the probability for the occurrence for a new event given the

H t : λ (t|H t ) dt = P { event in [t, t + dt)|H t }.

From the survival analysis theory (Aalen et al., 2008) , given the times of the past events {t 1 , t 2 , . . . , t i }, the conditional density that an event occurs at t i+1 is given as follows:p

t i+1 |H ti+1 = λ t i+1 |H ti+1 exp - ti+1 ti

λ (t|H t ) dt ,where the exponential part in the above equation means the conditional probability that no event happens during [t i , t i+1 ). The functional forms of the conditional intensity function λ (t|H t ) can represent certain forms of dependencies of the historical events. For instance, for Poisson processes (Kingman, 2005) we set λ to be constant -making the assumption that the process is stationary and the temporal events in history are independent of each other. For classical Hawkes processes (Hawkes, 1971) , the intensity function λ is often set to be a sum of multiple exponential functions, assuming that the mutual excitation among events is positive, additive over the past events, and exponentially decaying with time. Mei & Eisner (2017a) removed these limiting assumptions using LSTM to learn λ from data.

3. DEEP INTERACTION PROCESSES:

In this section, we present a new neural non-parametric Bayesian approach over continuous-time evolving graphs. First, we present a temporal dependency graph that is a mixture of the temporal cascades, to model interdependence between graph nodes (as well as latent node representations).

Then we present a novel deep model to learn dynamic node representations in the temporal dependency graph. This model naturally generalizes a chain-structured LSTM to a temporal Graph-structured LSTM equipped with time gates to handle interaction with irregular time intervals. Furthermore, we propose the FUSION and SELECTION methods to enhance the dynamic interactive nodes representation. Given the dynamic node representations, we define deep interaction processes that model potential interactions between any two nodes over time and we finally layout the maximum likelihood estimation method to optimize it. A toy example is shown in Figure 2 to introduce the corresponding concepts and the whole procedure of computing enhanced dynamic representation is given in Figure 3 .

Figure 2: A toy example of interactions, the corresponding temporal dependency graph and computation of nodes' dynamic embedding using DIP unit on its 3-depth temporal dependency subgraph.

3.1. TEMPORAL DEPENDENCY GRAPH:

Consider a collection of people-movie interactions at different time points (e.g., David saw the movie The Skull at t 6 .) as shown in figure 2(a) . The people and movies form a temporal dependency graph in which each person or movie is a node and interactions happen over time (in figure 2(b )). After one interaction occurs, we update the neural representation of the two nodes linked to this interaction; e.g., right after time t 6 , we update the representations for David and movie The Skull. The new neural representation of David depends on both his current and previous interactions -as a result, depending on the representations of the two nodes associated with the previous interaction. This naturally forms a dependency cascade. Similarly we can obtain a dependency cascade for Lucy's representations. Because of the common movies David and Lucy saw, their dependency cascades overlap and form a cascade mixture. Formally, we denote a dynamic interaction or link at time t by l u,v,t where u and v are two nodes associated with this interaction. We denote the node u at time t by u(t) and the two nodes associated with u's precedent interaction at time t -as u 1 (t) and u 2 (t). For later usage, we denote the k-depth temporal dependency subgraph for u(t) as subgraph(u(t), k) as shown in figure 2(b).

3.2. DIP NEURAL UNIT AND DYNAMIC REPRESENTATION:

Now we present a novel neural unit to update dynamic latent representations of nodes over the temporal dependency graph which is illustrated in figure 2(c ) and figure 2(d) .

First, let us denote node u's features or embedding (i.e., a static representation jointly learned from data) at time t by x u(t) and denote features of interaction l by x l . The interaction feature can be empty if the interaction contains only the temporal information. The concatenation of x u(t) and x l is denoted by xu(t) . Let ∆ (u,t) = t -t -be the time interval between two consecutive interactions involving u at time t and t -. Our neural unit, i.e, DIP unit, generalizes a chain-structured LSTM unit to depict the temporal dependency on graph data. The DIP unit has an update gate s, an input gate z, an output gate o and two forget gates f over xu(t) , dynamic representation of u i (t), i.e, h u i (t) and cell states c u i (t) (i = 1, 2) as shown in figure 2(c ). Additionally, we introduce time gates g to capture the impacts of irregular time interval ∆ (u,t) . Specifically, h u(t) and c u(t) are updated as follows:

EQUATION

where σ, tanh and represent the sigmoid function, the hyperbolic tangent function, and the Hadamard product (pointwise multiplication), respectively, and parameters in the unit including the recurrent weights R zi , R oi , R si , R fi and R gi , the projection matrices W z , W o , W s , W fi and W gi , the bias vectors b z , b o , b s , b fi and b gi and the time weight matrix M gi are learned from data. For convenience, we use DIP-UNIT (•) to summarize the above equations, then the dynamic representation of node u(t) is given as follows:

EQUATION

where Θ represent all the parameters.

Considering the computational cost in practice, when obtaining nodes' dynamic representation given an happened interaction, we only utilize history information in the subgraph(u(t), k) as illustrated in figure 2(d), which is similar to a chain-structured LSTM training unfolded with the max k steps.

The k is a hyper-parameter.

3.3. ENHANCED DYNAMIC REPRESENTATION:



3.3.1. STACKING AND FUSION:

To model nonlinear dependency relationships at different temporal resolutions, we stack L layers of DIP-UNIT together. The output of the j-th layer is computed recursively as follows:

EQUATION

were h 0 u(t) = xu(t) , j = 1, . . . , L. To train deeper dynamic neural networks easily, we employ the residual connection as the following form:

skip(h j-1 u(t) , h j u(t) ) = W skip h j-1 u(t) +h j u(t)

where W skip is a weight matrix. Motivated by ELMo (Peters et al., 2018) , we fuse all internal dynamic representations from all the layers to achieve rich dynamic representations. The fusion is a weighted summation of all layers defined as follows:

h u(t) = γ L j=0 α j h j u(t)

, where α j are softmax-normalized weights and γ is a scaling parameter. They both are learned parameters. 

3.3.2. SELECTION:

Given an interaction l u,v,t , it is reasonable to assume that not all the historical interactive nodes have the equal importance for formalizing this interaction. Thus we use a two-phase gating mechanism to select relevant nodes to learn dynamic representations and cell states of the current node. Specifically, a co-attention mechanism is first used to measure relevance of historical time-evolving patterns between subgraph(u(t), k) and subgraph(v(t), k),

Q j = tanh H j u W Q H j v (4)

where

H j u = h j 1 , . . . , h j a , . . . , h j m , a ∈ subgraph(u(t), k), H j v = h j 1 , . . . , h j e , .

. . , h j n , e ∈ subgraph(v(t), k), m and n are the numbers of nodes in the two corresponding subgraphs, W Q ∈ R d×d are the weight parameters. The Q j is a co-attention affinity matrix which captures the relevance information in subgraph(u(t),k) and subgraph(v(t),k). The co-dependent global embedding p j u , p j v are obtained by the following equations.

p j u = H j u SoftMax Max ColW ise Q j p j v = H j v SoftMax Max RowW ise (Q j ) (5)

where Max means max-pooling operation which is used to choose the most relevant information for the maximum influence (or affinities) on nodes in the corresponding subgraph. In addition, to adjust the importance of historical nodes, two adaptive gate functions are designed for nodes in subgraph(u(t),k) and subgraph(v(t),k) respectively,

EQUATION

where the weights w p , and w h are shared by all the stacked layers. Using these gates, we enhance the dynamic node representations as follows:

(h j u(t) , c j u(t) ) = DIP-UNIT j h j-1 u(t) g u (p j-1 u(t) , h j-1 u(t) ), c j u 1 (t) , c j u 2 (t) , h j u 1 (t) , h j u 2 (t) , ∆ (u,t) , Θ j (7) Similarly, we can compute (h j v(t) , c j v(t)

) for v(t) based on the selection mechanism.

3.4. CONDITIONAL INTENSITY FUNCTION:

We model the dynamic interactions as a multi-dimensional temporal point process. Specifically, we define the conditional intensity function of the temporal point process at the dimension indexed by (u, v), given its graph-structured history

H u,v t where H u,v t = subgraph(u 1 (t), k) ∪ subgraph(u 2 (t), k) ∪ subgraph(v 1 (t), k) ∪ subgraph(v 2 (t), k), as follows: λ u,v (t|H u,v t ) = SoftPlus h u,v t w λ + w t τ + b λ (8) where h u,v t = h u 1 (t) , h u 2 (t) , h v 1 (t) , h v 2 (t) , τ = ∆ (u,t) , ∆ (v,t)

, the scalar b λ can be viewed as a base intensity level for the occurrence of the next interaction, and the SoftPlus function is used to ensure the non-negativity of the intensity. A key step for obtaining H u,v t is to get the kdepth subgraphs of u and v's direct dependants. Please see Appendix.A for more details about fast obtaining k-depth subgraphs.

3.5. MAXIMUM LIKELIHOOD PARAMETER ESTIMATION:



3.5.1. INTERACTION PREDICTION:

Given a set of interactions as I = {(u i , v i , t i )} i=N i=1 observed in a time window [0, T], we can learn the model by minimizing the negative joint log-likelihood of I as follows: L 1 = i log P ui,vi t i |H ui,vi ti where P ui,vi (t i |H ui,vi ti ) represents the probability of formalizing an interaction between u i and v i at time t i given the dependant history of non-chain structures H ui,vi ti . Based on the intensity definition, we have

L 1 = -i log λ ui,vi t i |H ui,vi ti + T 0 Λ(t)dt, where Λ(t) = u,v λ u,v (t).

Since the survival part does not have an analytic solution, we apply Monte Carlo to do numerical integrations. We follow the negative sampling approaches used by Dai et al. (2016) and Trivedi et al. (2019) to accelerate the survival term calculation.

3.5.2. INTERACTION CLASSIFICATION:

An interaction sequence with markers is denoted as

I = {(u i , v i , t i , y i )} i=N i=1

, where y i is a marker at time t i and usually is a discrete variable. In practice, the markers have different meanings in distinct scenes. A marker can be treated as a magnitude in modeling earthquakes and aftershocks. For financial transactions, a marker can be used to label whether a transaction is a fraudulent trading or not. The joint conditional density of an interaction(u i , v i , t i ) with marker y i is given as P ui,vi t i , y i | Ĥui,vi ti . By applying the Bayesian rule , the joint conditional density can be written as:

P ui,vi t i , y i | Ĥui,vi ti = P ui,vi (t i | Ĥui,vi ti )P y i |t i , Ĥui,vi ti ,where P ui,vi (t i | Ĥui,vi ti

) has the same meaning as given in subsection 3.5.1, while P (y i |t i , Ĥui,vi ti ) means the distribution of y i given the interaction happened at t i with interaction history Ĥui,vi ti . It should be noted that the history Ĥui,vi ti contains the information of history markers and one can design a marker-specific intensity function like Mei & Eisner (2017b) . For simplicity, in our marked temporal point processes, we assume that P ui,vi t i , y i | Ĥui,vi ti is independent of historical markers. We model P y i |t i , Ĥui,vi ti as

EQUATION

where h ui,vi,ti is the concatenation of h u(ti) and h v(ti) which can be regarded as a dynamic representation for an interaction between u and v at t i , V yi is the weight parameters for the y i th class. Then the overall cost function is L 2 = L 1 + L cross-entropy , where L cross-entropy is a cross-entropy loss over marks:

L cross-entropy = - N i=1 yi y i • logP (y i |h ui,vi,ti ) (10)

4. RELATED WORK:

Inspired by the Skip-gram (Mikolov et al., 2013) for word embedding, a series of node embedding methods based on the random walks on graphs have been proposed (Perozzi et al., 2014; Tang et al., 2015; Grover & Leskovec, 2016; Wang et al., 2016; 2017) . GCN and its variants (Bruna et al., 2013; Hamilton et al., 2017a; Kipf & Welling, 2017) are a recent class of algorithms which extend convolutions from spatial domains to graph-structured domains. Meanwhile they can efficiently generate node embeddings for previously unseen data. All models above are designed for static graphs. The intuitive and popular approaches for modeling dynamic graphs are based on a sequence for graph snapshots (Goyal et al., 2018; Zhou et al., 2018; Seo et al., 2018; Yu et al., 2018) 

5. EXPERIMENTS:

We evaluate the proposed DIP model for interaction prediction and interaction classification on several real-world datasets.

5.1. BASELINES AND EVALUATION METRICS:

GraphSage (Hamilton et al., 2017a ) is an inductive graph neural network framework consisting of three different aggregators which are GCN, Mean and LSTM aggregators respectively. We report the best results among these three aggregators noted as Graphsage*. What's more, for comparing with GAT (Veličković et al., 2017) we also implement a graph attention aggregator based on GraphSage. CTDNE(Nguyen et al., 2018) is a newly-proposed temporal network embedding method and also a tranductive method like DeepWalk (Perozzi et al., 2014) . It incorporates temporal order constraint when sampling walks from time-continuous graphs. DynGEM (Goyal et al., 2018) takes a sequence of static graph snapshots as inputs to learn node embeddings by a deep auto-encoder network.

DeepCoevolve (Dai et al., 2016 ) models dynamic interaction sequences with two co-evolution recurrent neural networks. Hidden embeddings are learned for interactive nodes after each interaction.

DyREP (Trivedi et al., 2019) uses a two-time scale deep temporal point process model to capture dynamics of graphs. JODIE (Kumar et al., 2019) models interaction processes in a novel way by predicting the next interaction embedding directly instead of modeling the intensity function.

For interaction prediction, we report Mean Rank results. To evaluate the effectiveness of top-n, we also report performances on hit@1 and hit@5. As for interaction classification, we employ KS (Kolmogorov, 1933) score as well as AUC(Area under the ROC Curve) score.

5.2. EXPERIMENTAL SETTING:

We conduct all the experiments with a hyper-parameter grid search strategy. For all methods, we search the dimension of embedding from {16, 32, 64, 128} and the learning rate from {0.01, 0.001, 0.0005, 0.0001, 0.00001}. For our DIP model, we go through {1, 2, 3, 4} for k and {1, 2, 3} for L. For Graphsage, the maximum number of 1-hop and 2-hop neighbor nodes are set to 25 and 20 respectively. All the models are trained for at most 50 epochs with an early-stop operation if the performance does not improve for 5 epochs. For Graphsage, DynGEM ,DeepCoevolve and JODIE, we use the open source codes provided by the authors. We implement the CTNDE and GAT based on the Graphsage framework, and implement DyREP based on the pytorch implementation of DeepCoevolve. After the best configuration is found, we repeat the full experiments 5 times and report the mean results and standard deviation.



5.3.1. DATASETS:

CollegeMsg (Leskovec & Krevl, 2014) 1 ) and repetitive information makes recurring interaction predicted easily. The two static methods perform worse than the other dynamic methods(but JODIE ) on the Amazon-Clothing because no repetitive information can be reused and nodes representation can't be updated across validation and test like CTDNE. As for comparison with dynamic methods, our work performs better than the Dyrep, DeepCoevolve and JODIE which use the similar mutually-recursive RNNs to capture and update co-evolution states sequentially. We argue that the vallina RNNs can't capture long-term dependency history well and have optimization problems which may lead to worse performances than ours. Moreover they treat past history information equally while our selection mechanism can select more relevant information for updating dynamic representation. The performances of all methods on hit@1 and hit@5 are given in Appendix.B. The effects of k and L are also investigated in Appendix.B.



We conduct this task on an industrial dataset: Huabei Trade Data. This dataset consists of about 150,000 transaction records processed by Huabei during August 2018. Each transaction is initiated with three parties: the buyer, the seller and transaction details such as merchant category and transaction amount. Around 15% of the transaction are fraudulent and is labeled by a complicated Ex-Post method. For each interaction event, there are 11 context features including information about buyer types, seller types, purchased items' categories and trading platform. We use the first 10 days data as training set, the following 10 days data as validation set, the rest as test set. Note that, in this scenario, there are users who only appear in validation/testing dataset. Thus, the transductive method CTDNE is not applicable on this task. Meanwhile, since the dynamic baseline methods are all unsupervised, we only report GCN and our marked DIP methods Alternatively, we employ the XGBoost (Chen & Guestrin, 2016) as an additional baseline which is a popular baseline method in the cash-out detection task (Hu et al., 2019) . The detailed data statistics are given in Appendix.B.1. 

5.4.2. RESULTS AND ANALYSIS:



5.5. ABLATION STUDY:

As we described in Section 3, the DIP model consists of three important components: First, it uses a Time Gate in the DIP neural unit to explicitly model the temporal information. Second, the selection mechanism enables our model to select more important historical information for interactions. Third, the Fusion of multi-layer DIP-UNIT's hidden state vector helps to extract high level feature. We investigate the contribution of each component by disabling each of them one by one, and compare the corresponding result to the full model. figure 5 and figure 6 give the detailed ablation results.

FullModel in the two figures means all the three components are enabled.

• No Time Gate: In this configuration, the time gate in DIP-UNIT is disabled. This leads to a significant drop of the Mean Rank performance. It provides a strong evidence for the effectiveness of the time gate. • No Selection: In this configuration the selection mechanism is disabled. Accordingly, all the historical node representations contribute equally, thus again leading to a performance drop. • No Fusion: In this variant, we directly use the hidden state vector of the last layer. Again, the performance degrades significantly. This demonstrates that a fusion of different layers' representations gives richer information than the last layer only.

6. CONCLUSIONS:

In this paper, we have proposed a deep multidimensional point process approach, DIP, to learn dynamic graph representations. We generalize LSTM over temporal dependency graphs and model Record the latest time when node x was involved in an interaction and initialize with -1 3: for event in I do gn is short for group no 14: end for 15: ColorGpSeq = Sort(I) sort I by an ascending order with assigned group color no. 16: return ColorGpSeq

A.2 CONSTRUCTION OF K-HOP TDG:

The details of CONSTRUCTION OF K-DEPTH TDG are given in Algorithm 2. In Algorithm 2, based on the definition of TDG and ColorGpSeq output by Algorithm 1, we can incrementally construct the k-depth subgraphs for any two nodes in a new interaction. Specifically, we first call PREVIOUS function to get each node's adjacent interaction in which it was involved before current interaction. Then incrementally construct a graph(ugraph) rooted at cur_u(lines 6 to 10). Here H k_subgraph [u_preInteraction] stores the subgraph of ugraph which was obtained before ugraph because u_preInteraction ranks ahead of current event in ColorGpSeq. Likely, we can get vgraph incrementally. At last, we call the Breadth-First-Search algorithm with the traverse depth = K to obtain the k-depth subgraphs for cur_event and then store it into H k_subgraph [cur_event] .

A.3 OBTAINING AND UPDATING K-DEPTH TDG:

As for efficiency, fast obtaining k-depth subgraph of TDG for an interaction is both important for offline training and online inference. Based on Algorithm 2, for an interaction l from the Algorithm 2 CONSTRUCTION OF K-DEPTH TDG Require: ColorGpSeq: A seq of sorted interaction by group color no. Ensure: HashTable H k_subgraph : Map an interaction to its corresponding k_subgraph.

1: Initialize an empty HashTable H k_subgraph 2: for cur_event in ColorGpSeq do if u_preInteraction exits then 7:

edge 1 = (u_preInteraction.u, cur_u)

The edge is defined according to the definition of dependency graph 

B.2 HIT PERFORMANCE:

Figure 7 and Figure 8 provide HIT@5 and Hit@1 results in addition to the Mean Rank results in Section 5.3.2 of the main paper. HIT@n is defined as HIT @n = δi #of T est Interaction , where δ i = 1 if rank i <= n else 0, which measures the ability of top rank prediction. For a given node u(t), only the history information in k-depth temporal subgraph, i.e, subgraph(u(t), k), is considered to calculate the dynamic representation, so the number of depth k could affect the final representation. Meanwhile, our proposed fusion mechanism is based on deep model which can capture different information at different layers. So, in this subsection, we investigate the effects of k and L for CollegeMsg dataset on the Interaction Prediction task and Huabei Trade dataset on the Interaction Recognition, which is shown in Figure 9 . As we can see, stacking multiple layers does help improve the interaction prediction and interaction classification performances, but it doesn't mean the larger L will always give the better results. And with the k increases which means we could utilize more history information, the trend of the performances go better for both tasks.

B.4 EFFECT OF EMBEDDING SIZES:

To investigate the effect of the dynamic embedding size on the interaction prediction and interaction classification tasks, we vary the dynamic embedding dimension in {16, 32, 64, 128} and report the corresponding Mean Rank results for interaction prediction on the CollegeMsg dataset and KS results(AUC is similar) for interaction classification on Huabei Trade Data in figure 10 . In figure 10 (a), we see that the dynamic embedding size has little impact on DIP model, and it consistently outperforms all baselines. The performances of several baselines drop more or less when the embedding size is set to 128. The baseline model could overfit at this embedding size. In figure 10 (b ) we find that when all the baselines are set with the same dynamic embedding sizes, our DIP model always outperforms the competitors.

C DETAILED RELATED WORK:

Graph representation learning, which is also known as graph embedding or network embedding, is a task aiming to learn low-dimensional dense vectors for vertex and edges that preserve the original graph structural information and network properties. Before the era of deep learning, conventional graph representation learning methods usually adopts dimension reduction (Belkin & Niyogi, 2002; Tenenbaum et al., 2000; Roweis & Saul, 2000) or matrix factorization (Ahmed et al., 2013) techniques. While these methods usually suffer a heavy computational cost. After the great success of deep learning methods in the field of computer vision and natural language processing, especially Skipgram (Mikolov et al., 2013) in word representation learning, this problem has been widely investigated by neural network methods. We review the development of this research direction from the following perspectives.

Static Graph Representation Learning: Perozzi et al. (2014) proposed the DeepWalk model utilizing random walks on graph to generate sequences of nodes, and feed them into the Skip-gram model to learn nodes' low dimensional representation vector. Then, Tang et al. (2015) proposed the definition of first-order proximity and second-order proximity in the model named LINE, that jointly models this two different level structure information. Grover & Leskovec (2016) designed a biased random-walk sampling method to capture more flexible neighborhood information which is helpful to learn richer representations. And Wang et al. (2016; 2017) extended these models by considering high-order proximity and community structure. But these mentioned methods are somehow shallow.

Another type of method is the Graph Convolution Network (Bruna et al., 2013; Kipf & Welling, 2017) . They extended the convolution neural network to the graph spectral space, thus applied DEEP model on graph data. While these methods are still transductive, and can not jointly models the network structure information and the attributed on nodes or edges of graph. To overcome this problem, Hamilton et al. (2017a) proposed an inductive graph embedding framework, which divided the representation learning into two phrase: sampling and aggregation, such that it could incorporates node feature information and thus generate embedding from these features using the well-trained graph neural network for unseen nodes. Veličković et al. (2017) used self-attention to learn weights for neighborhood, then aggregated them by the self-adapted weight. While, most of these approaches can only model static graph data.

Dynamic Graph Representation Learning: A popular approach for modeling dynamic graph data is considering the dynamics as a sequence of graph snapshot (Soundarajan et al., 2016) . Zhu et al. (2016) uses an non-negative matrix factorization technique to embed social network in a temporal latent space. Zhou et al. (2018) models the specific triadics closure formation procedure over the snapshots. Goyal et al. (2018) adapts an graph autoencoder and learns a stable embedding over time. Seo et al. (2018) combines a CNN module and a RNN module to capture spatial characteristics and temporal characteristics. NetWalk (Yu et al., 2018 ) also learns vertex representations from sequences of snapshots, and it is designed specially for anomaly detection. In contrast, Nguyen et al. ( 2018) adds temporal order constraint on random walk sampling to capture evolving neighborhood. But, it can't explicitly models the rich temporal information.

Temporal Point Process: Temporal Point Process is a powerful statistical tool for modeling sequences of events with unequal interval. It has been wildly used in recent research with different intensity function: from parametric (Du et al., 2016) to recurrent neural networks (Dai et al., 2016; Mei & Eisner, 2017b) , event reinforcement learning based (Xiao et al., 2017) . DeepCoevolve (Dai et al., 2016) designs a recurrent neural network to capture the co-evolution dynamics of interaction data. But it just takes the interaction counterpart into the co-evolution module, which may loss temporal structural information. DyREP (Trivedi et al., 2019) divides the interactions between nodes into two different types as communication and association and models them separately. Although it uses the neighborhood of interaction counterpart to update node representation, the relevance between the different neighbors of counterpart and the node itself has not been modeled.

:



Figures and Tables:

Figure 1: An illustrative example. Figure (a) shows an illegal cash-out event.It can be revealed by high-frequency transactions with multiple merchants. However, if we merge the transaction data into a static graph, we cannot distinguish it from the static graph generated from normal online shopping activities. Thus, learning from such a static graph will fail to detect the cash-out event.

Figure 3: An illustrative example. Enhanced dynamic representation with Fusion and Selection.

Figure 5: Ablation study results of the interaction prediction task. Disabling any one of the three component leads to a performance drop.

, cur_time = event.u, event.v, event.t 5: if cur_time > LastN odeT ime[cur_u] then = max(ColorGroupArray[cur_u], ColorGroupArray[cur_v])

depth = BF S(ugraph ∪ vgraph, depth = K) Call Breadth-First-Search with max depth = K 23:H k_subgraph [cur_event] = G K-depth 24: end for 25: return H k_subgraph collected training interaction data, we can obtain its corresponding k-depth subgraphs directly using H k_subgraph [l] with time complexity O(1). For a new incoming interaction l with two nodes cur_u and cur_v , we can easily reuse Algorithm 2's code from line 3 to 22 to find ugraph and vgraph, respectively. Then we merge them to get k-depth subgraph for doing inference online. At the same time, we can incrementally update TDG by H k_subgraph[l]. The time complexity here for updating TDG mainly depends on union between ugraph and vgraph in line 22 of Algorithm 2 and is O(n+e) where n and e are the total number of nodes and edges for ugraph and vgraph.B ADDITIONAL DATA STATISTICS AND EXPERIMENT RESULTSB.1 HUABEI TRADE DATASET

Figure 7: Hit@5 Results

Figure 9: Sensitivity to k and L.

, but it can be difficult to specify the appropriate aggregation granularity. Nguyen et al. (2018) adds a temporal constraint on random walk sampling, but it can't model the rich temporal information explicitly. interactions directly by predicting the next interaction embedding. More detailed related work are included in Appendix.C.

Table content: <table/>

consists of sending message interactions on an online social network at the University of California, Irvine during 193 days. Ubuntu(Leskovec & Krevl, 2014) is a temporal interaction dataset extracted from the stack exchange website. An interaction between two users means one answered another's questions or replied to his/her posts. Amazon(McAuley et al.Dataset Statistics for interaction prediction Mean Rank performances of all methods. On the whole, our DIP method consistently beats all baselines by 65.84%, 41.64%, 10.69% and 43.99% over the four diverse datasets. The CTDNE method performs worst across all the datasets since the generated embedding is static and can't be updated and evolved across validation and test datasets. Meanwhile we can see that there is no consistent winner among baselines and all the methods perform relatively better on the CollegeMsg, Ubuntu and MathOverflow datasets than do on the Amazon-Clothing dataset. It is also noteworthy that the static methods GAT and GraphSage* perform competitive with dynamic baselines on these three datasets. These phenomenons above could be explained that the CollegeMsg, Ubuntu and MathOverflow have lots of repetitive interactions (at least 75% for CollegeMsg and MathOverflow on test data, 68% for ubuntu on test data as shown in Table

Table content: <table><tr><td/><td>CollegeMsg</td><td>Ubuntu</td><td>Amazon-Clothing</td><td>Math Overflow</td></tr><tr><td colspan="2"># Train/ # Valid/ # Test 35902/7814/5055</td><td>204846/39913/35271</td><td>50209/9195/7598</td><td>58596/24045/32705</td></tr><tr><td>Repetition in Valid(%)</td><td>72.55</td><td>56.60</td><td>0.00</td><td>67.42</td></tr><tr><td>Repetition in Test(%)</td><td>75.67</td><td>67.57</td><td>0.00</td><td>79.92</td></tr><tr><td>Duration(days)</td><td>193.63</td><td>2587.96</td><td>3657.00</td><td>2350.12</td></tr><tr><td colspan="2">5.3.2 RESULTS AND ANALYSIS</td><td/><td/><td/></tr><tr><td>Figure 4 summarizes the</td><td/><td/><td/><td/></tr></table>



Table content: <table><tr><td/><td/><td>600</td><td>DIP DyREP</td><td/><td colspan="2">GAT GraphSage*</td><td/><td/><td/><td colspan="2">3500</td><td>DIP DyREP</td><td/><td colspan="2">GAT GraphSage*</td></tr><tr><td/><td/><td>500</td><td colspan="2">DeepCoevolve DynGEM</td><td colspan="2">CTDNE JODIE</td><td/><td/><td/><td colspan="2">3000</td><td colspan="2">DeepCoevolve DynGEM</td><td colspan="2">CTDNE JODIE</td></tr><tr><td colspan="2">Mean Rank</td><td>300 400 200</td><td>345.56</td><td>313.28</td><td>356.58</td><td>314.42 311.57</td><td>550.71</td><td>361.23</td><td>Mean Rank</td><td colspan="2">1500 2000 2500 1000</td><td>1713.48</td><td>2055.05</td><td>2202.06</td><td>1529.8 1512.92</td><td>3406.14</td><td>1762.33</td></tr><tr><td/><td/><td>100</td><td>101.81</td><td/><td/><td/><td/><td/><td/><td/><td/><td>796.09</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td colspan="3">CollegeMsg</td><td/><td/><td/><td/><td/><td/><td/><td colspan="2">Ubuntu</td></tr><tr><td/><td colspan="2">9000</td><td>DIP DyREP</td><td/><td colspan="2">GAT GraphSage*</td><td/><td/><td/><td/><td>700</td><td>DIP DyREP</td><td/><td colspan="2">GAT GraphSage*</td></tr><tr><td/><td/><td/><td colspan="2">DeepCoevolve</td><td colspan="2">CTDNE</td><td/><td/><td/><td/><td/><td colspan="2">DeepCoevolve</td><td colspan="2">CTDNE</td></tr><tr><td>Mean Rank</td><td colspan="2">6000 7000 8000</td><td>DynGEM</td><td/><td colspan="2">JODIE</td><td>8641.16</td><td>8330.39</td><td colspan="2">Mean Rank</td><td>300 400 500 600</td><td>DynGEM</td><td/><td colspan="2">JODIE</td><td>723.23</td></tr><tr><td/><td colspan="2">5000</td><td colspan="2">6862.01 6742.4</td><td/><td>7164.38 7173.11</td><td/><td/><td/><td/><td>200</td><td/><td colspan="3">312.61 294.9 301.6 272.12</td><td>302.3</td></tr><tr><td/><td/><td/><td/><td/><td>6216.84</td><td/><td/><td/><td/><td/><td/><td>188.72</td><td/><td/><td/></tr><tr><td/><td colspan="2">4000</td><td>5552.41</td><td/><td/><td/><td/><td/><td/><td/><td>100</td><td>92.87</td><td/><td/><td/></tr><tr><td/><td/><td/><td/><td/><td colspan="2">Clothing</td><td/><td/><td/><td/><td/><td/><td colspan="3">MathOverflow</td></tr><tr><td/><td/><td/><td/><td/><td/><td colspan="8">Table 2: Interaction classification results</td><td/><td/></tr><tr><td/><td/><td/><td/><td/><td colspan="2">Xgboost</td><td colspan="3">GraphSage*</td><td/><td/><td>GAT</td><td/><td/><td colspan="2">DIP</td></tr><tr><td/><td/><td/><td colspan="14">AUC 0.6818 ±0.0023 0.8603 ±0.0005 0.8597 ±0.0004 0.9017 ±0.0004</td></tr><tr><td/><td/><td/><td>KS</td><td colspan="13">0.2536 ±0.0015 0.5934 ±0.0012 0.6018 ±0.0005 0.6703 ±0.0060</td></tr></table>

Huabei Dataset Statistics

Table content: <table><tr><td/><td colspan="4"># Interaction # Seller # Buyer Repetition(%)</td></tr><tr><td>Train</td><td>60705</td><td>19453</td><td>22916</td><td>-</td></tr><tr><td>Valid</td><td>53609</td><td>16669</td><td>23517</td><td>25.21</td></tr><tr><td>Test</td><td>34471</td><td>9929</td><td>17549</td><td>23.55</td></tr></table>

Peer review (iclr2020):
The paper focuses on the problem of modeling interaction processes over dynamically evolving graphs and perform inference tasks such future interaction prediction and interaction classification. Specifically, the paper proposes a temporal point process based formulation to model the interaction dynamics where the conditional intensity function is parameterized by a recurrent network. With an occurrence of any event, the recurrent architecture updates the embeddings of the nodes involved in that event which then affects the intensity function and hence the likelihood of future events. The paper uses intensity based likelihood to train for future interaction prediction task while cross-entropy based loss for classification task. The paper demonstrates the efficacy of the method through experiments across multiple datasets and compare against representative baselines and further provides ablation analysis for the proposed architecture. The paper demonstrates markedly improved empirical performance on multiple datasets and also performs the task of interaction classification which is not seen in recent works on evolving graphs, which are plus points. However, there are several concerns with the overall work that makes this paper weaker: (1) The main concern is with the novelty and more importantly the justification/analysis of the contributions proposed approach. (2) Further, while the ablation study provides some insights into architecture, it is not adequate (3) The paper misses comparison with a very important and recently proposed baseline, JODIE [1]. Main Comments: -------------- - The paper leverages existing techniques built for learning over evolving graphs and augments it with three modifications: explicit use LSTM with time gate, stacked LSTM approach with fusion (Aggregation) and attention mechanism to select important neighbors to contribute to embedding update. The use of LSTM with time gate and fusion mechanism is very incremental contribution. The attention mechanism proposed here is novel compared to existing works. However, there is very little justification or analysis provide or either of the contributions. This is big drawback of this contribution. - For instance, the authors mention that stacked LSTM is used to capture multiple resolution. Can they provide some analysis or empirical demonstration that this actually happens? Also, the authors mention they use K in range of {1,2,3,4} but do not provide details what was useful for each dataset and how is it useful. How does the scaling parameter and alpha affect the performance and what are their roles? Also, what does superscript *task* signify? Similarly, they propose coattention mechanism with adaptive gate functions but does not provide any analysis of why they are useful and what characteristics they capture in the data that allows it to select most relevant neighbors. Is the attention mechanism temporally dependent? - The authors perform ablation studies by switching off each component as a whole but considering the way this architecture is built, this is not a very useful exercise except knowing that each component contributes to the performance. A more detailed analysis and ablation is required. For instance, can the authors show performance with different K and how it deteriorates/improves with it? Also, for stacked LSTM case, the authors show what happens when you use last layer, but what happens if the authors use only one layer (I guess this is K=1?) or don*t use residual connections? When the time gate is switched off, does the authors also remove deltas from intensity function? what happens in this scenario? How does subgraph depth affect the quality of performance? What happens if authors don*t sue adaptive gate functions? - Figure 2 shows an example of bipartite graph, however, it seems datasets in experiments does have non-bipartite case? Is this true or the method only works for bipartite case? - The use of proposed Algorithm 2 is not well justified. Why does the author need coloring and hashing mechanism instead of simpler BFS/randomwalk routine to collect previous interactions? Also, is this subgraph created for each event or it is computed offline during training? Further, the subgraph used for selection mechanism same as subgraph used for backtracking in LSTM? - Further, is it true that the training is done in order of ColorGraphSeq or is it done in order of dataset? How does the authors capture dependencies across dataset in later case? - Do you also update cell states with selection mechanism? The DIP-UNIT equation in selection section does not show that update. Also, are the embeddings updated only during train or also during validation/evaluation? - The authors only present the results as-is without any insights on the performance of DIP model vs others and why they are able to demonstrate good performance. It is highly desired that authors add discussion section for each set of results to provide such information - The authors include support for new nodes for interaction classification task but remove them for interaction prediction task which is strange. Is there a specific reason for this? What is the effect on the performance if new nodes are allowed in test? Further, why is interaction classification not compared with temporal baselines? All baselines produce embeddings and the authors mention that classification for this paper is independent of marker history. While the temporal baselines do not train for the task, the authors can train a second stage classifier with learned embeddings to perform classification - The authors do not compare with recently proposed JODIE [1] which is a big miss. The comparison is required as it also models interaction processes in a novel way by actually predicting the next embedding directly instead of modeling the intensity. An empirical comparison and discussion of this method is required to compare with various state-of-art methods. Minor: ------- - The authors need to use better and consistent notations. Also, as the overall approach uses similar flow as previous papers such as DeepCoevolve, it is recommended that the authors make the presentation simpler to position it clearly with existing works. On page 3, section 3.2 both bold-face and normal letters are used as vectors. Is a vector? - Please provide numbers to equations for better referencing [1] Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks, Kumar et. al. KDD 2019