Deep Interaction Processes for Time-Evolving Graphs
Authors: xiaofu chang
jianfeng wen
xuqin liu
yanming fang
le song
yuan qi
Venue:  (2020)
Keywords: deep temporal point process
multiple time resolutions
dynamic continuous time-evolving graph
anti-fraud detection

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 time-evolving 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-$hop 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. Based on the temporal point process framework, our approach can naturally handle growth (and shrinkage) of graph nodes and interactions, making it inductive. Experimental results on interaction prediction and classification tasks -- including a  real-world financial application --  illustrate the effectiveness of the time gate, the selection and attention mechanisms of our approach, as well as its 
superior performance over the alternative approaches.

Under review as a conference paper at ICLR 2020
DEEP INTERACTION PROCESSES FOR TIME-EVOLVING GRAPHS
Anonymous authors Paper under double-blind review
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 principled deep neural approach that models continuous time- evolving 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 s neural representation depends not only this node's 's previous representations but also the previous representations of related nodes that have interacted with this node. We generalize LSTM 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 res-uuesosusions 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 real-world financial application illustrate the effectiveness of the time gate, the selection and fusion mechanisms of our approach, as well its superior performance over the alternative approaches.
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) [016)] Wang et al.] 2016)] Kipt & Welling 2017 (017//effiee Defferrard et al.] 2016 Scarselli et al. 2in9))iigg et al. [218)] 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 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 !
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 user-specified discrete-time interval, as shown in (Goyal et al.) 20188 Leskovec et al. 2007 Zhou et al., 2018 Sankar et al. (001)). This treatment reduces time resolution and is tricky to specify the appropriate aggregation granularity. To avoid these problems, Nguyen et al. (0118) proposed continuous-timg dynamic networks (CTDNE) that generalize deep walk methods learn dime-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. [rivedi ct al. (2019) extended this approach by modeling two-time scale and adopting temporal-atten a-ttention mechanism.

---

Under review as a conference paper at ICLR 2020
13:08.99
User
$36.5
$550
M4
23:48.39
Uiker
5775.5
5923
MR
01:56:37
User
5550
5300
M3
15:11:09
User $36.5
5537
M1
C
07:56:28
12:56.01
07:56:12
User
M2
08:19:12
User
MB
$1150
07:55:37
User
5500
MB
M4
ML
07:56:35
07:03:11
User
$374.5
M2
M4
MI
(a) An illegal cash-out event
(b) Legal transactions
Figure 1: An illustrative example. Figure (a) shows illegal cash-out event. It can be revealed by high-frequency transactions with multiple merchants. However, if we merge the transaction data into 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 powerful deep neural approach that models continuous time-evolving graphs at multiple time resolutions based on temporal point process framework. We name the new approach deep interaction processes (DIPs). To model the dependency between latent dynamic representations of each node, define mixture of temporal cascades in which node's ' neural representation depends on not only this node's 's previous representations but also the previous representations of related nodes that have interacted with this node. We generalize LSTM this temporal cascade mixture and introduce novel time gates to model time intervals between interactions. Furthermore, We introduce 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 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 inductive.
The rest of the paper is organized as follows. In Section 2 we give background on temporal point processes and in Section we present the new DIP approach. In Section 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 based on. Specifically, a temporal point process a stochastic process that generates a sequence of discrete events localized at times {t,) 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 À Ht) -the stochastic model for the next event time f given all historical events before time i, denoted as H, = (4: 44 < <(). Formally, within small time window [1, I + di), À (4 ( di is the probability for the occurrence for a new event given the H,: (t H2) dt P event in [t, t + dt) H... From the survival analysis
(alen et al. 2008).
the conditional density that an event occurs at f IS given as follows:p (le+1 H.:..) = A (4,+|H,,,..) exp {- f.h (t) di where the exponential
given the times of the past events {t1, 22................... .......,). t.),
part the above equation means the conditional probability that no event happens during (4s 4++ 1). The functional forms of the conditional intensity function À (t HH) can represent certain forms of dependencies 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 processes(Hawkes 1971). the intensity function 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 LSTT to learn À from data.
A is often set to be
DEEP INTERACTION PROCESSES
In this section, present new neural non-parametric Bayesian approach over continuous -im 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 latent node representations).
2

---

Under review as a conference paper at ICLR 2020
Then present 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-struetured LSTM equipped with time gates 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 Figure to introduce the corresponding concepts and the whole procedure of computing enhanced dynamic representation is given Figure
JuNs
((
((6)
<David, The Skull, See movic>
<Lucy, The Skull, fs, See movie>
v(t)
2
David, Captain America, 4, See movie>
((.))
((L)
Skull
6
Lucy, Captain America, fi, See movie
4
David, The Witch, I, See movie>
Waa Lay Capaia Anotio
subgraph(u(t)... 3)
David, Daybreakers, Sce movie>
Dasid
Dayteaaees
(a)
A sequence of time-evolving interactions
(b) Temporal dependeney graph
Cu²t)
Cu(
(fog)
(fog) mM
Ci((0
(tanh.
Lasin
Sun
Ovis
O
O
tanh
c
Au.
(fog)
(rog)
Ru (1)
(Fog)
Frgh
ha(
h
hitto
h
(c) DIP unit
(d) Dynamic embedding computation of u(ts) using DIP unit on its 3-depth subgraph
Figure 2: A toy example of interactions, the corresponding temporal dependency graph and computa- tion of nodes' dynamic embedding using DIP unit its 3-depth temporal dependency subgraph.
3.1 TEMPORAL DEPENDENCY GRAPH
Consider collection of people-movit interactions different time points (e.g., David the movie The Skull at (a-) as shown in figure aaa). The people and movies form temporal dependency graph which each person movie is node and interactions happen over time (in figure (())). After one interaction occurs, we update the neural representation of the two nodes linked to this interaction; egg., right after time fe, 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 result, depending on the representations of the two nodes associated with the previous interaction. This naturally forms dependency cascade. Similarly we can obtain dependency cascade for Lucy's representations. Because the common movies David and Lucy saw, their dependency cascades overlap and form cascade mixture. Formally, denote dynamic interaction link at time by lu,,, where and v are two nodes associated with this interaction. We denote the node u at time by u(t) and the two nodes associated with u's precedent interaction time t- n (t) and u² (t). For later usage,

---

Under review as a conference paper at ICLR 2020
denote the k- dedeeph temporal dependency subgraph for u(t) subgraph(u(t)) (u(t), k) shown in figure 2).
3.2 DIP NEURAL UNIT AND DYNAMIC REPRESENTATION
Now present novel neural unit to update dynamic latent representations of nodes the temporal dependency graph which is illustrated in figure and di
First, let denote node u's features embedding (i.e., static representation jointly learned from data) at time /. by Xx()) and denote features of interaction / by x,. The interaction feature can be empty the interaction contains only the temporal information. The concatenation of Xu(() and x t be the time interval between two consecutive interactions involving u at time t and t Our neural unit, i.e, DIP unit, generalizes chain-strie structured LSTM unit to depict the temporal dependency on graph data. The DIP umit has an update gate s. an imput gate an output gate o and two forget gates f over &u(t). dynamic representation of u'(t,, i.e, (1)(t) and cell states (t) (i 2) as shown in figure 2(c). Additionally, introduce time gates g to capture the impacts of irregular time interval A (may) Specifically, hu(e) and Cu(t) are updated as follows:
denoted by Xu(e). Let (u.t)
N
Zu(e) = (W:
+
Rs, (o) + bz
Ou(() =a W WoRu())
+
Ro, har(e) + bo.
1=1
Bu(l) = tanh
W W) +
Rs, bui()) + b,
lu(0) a (W (u(()) -RRR bo + bby))
i=1
(a(t).a"(1) (W gi xu())
+ Rg hw) + Mg. (ux) + bg:)
Cu(t) Zu(t) ① Su(t) + Σ i= (u(t),a(()) 2 Cui(t) O (a(t),
N
ba(() Oa()) @ tanh (Cutt))
(1)
where σ, (anh 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 Ro,, Re,, R,, and Ry,, the projection matrices W 2. W W., W f, and W.. the bias vectors b. b,, b.. by, and bg. and the time weight matrix Mg. are learned from data. For convenience, use DIP-UNIT (-) summarize the above equations, then the dynamic representation of node u(t) is given as follows:
bu(l); Cu(t) = DIP-UNIT (Ru(o), Cul(t)) Cua()) (e) hua(e) (a,e), θ)
(2)
where ④ represent all the parameters.
Considering the computational cost practice, when obtaining nodes' dynamic representation given an happened interaction, only utilize history information in the subgraph( (u(t), k) as illustrated in figure ((d), which is similar to a chain-structured LSTM training unfolded with the max k steps. The k is haper-parameter.
3.3
ENHANCED DYNAMIC REPRESENTATION
3.3. 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:
(h u(t): (y = DIP-UNIT (N e Satoo Sato baa hisco) A(u.)), 0,,
(3)
were (((()) &x()) =, L. To train deeper dynamic neural networks easily, we employ the residual connection as the following form: skip(h (()) h ((ee))= W (())
hi] h b where Wakip 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 weighted summation of all layers defined as follows: hu(!)) = 7 Ef ay h' where a, are
weights
and ry is scaling parameter. They both are learned parameters.
4

---

Under review as a conference paper at ICLR 2020
Layer
Lager
Fasina
ha
Sdection
Pooling
Representation
DIP Layer
Sal oellatiaaee
ham
DIP Loyer
Figure 3: An illustrative example. Enhanced dynamic representation with Fusion and Selection.
3.3.2 SELECTION
Given interaction lu,,,t, it is reasonable assume that not all the historical interactive nodes have the equal importance for formalizing this interaction. Thus we use two-phase gating mechanism to select relevant nodes 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),
Q' tanh (H. W WoH
where H = h h hi E (ab))aah(u(t)...... k), H. h
h e
subgraph(u(t)) k),, m and n are the numbers nodes in the two corresponding subgraphts W gexd are the weight parameters. The Q' is co-attention affinity matrix which captures the relevance information in subgraph(u()) (k).k) and subgraph(u(t).h) The co-dependent global embedding P P are obtained by the following equations.
P = SoftMax
Max ColW
Q')
P = SoftMMaxx
Max Row W
(Q'IT)
(5)
where Max means max-pooling operation which is used to choose the most relevant information 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(()).) respectively.
gu. (p... h = o ow,p' + wrhh))
Iu (p', = ow,p'' w,)h))
(6)
where the weights Wp, and Wn are shared by all the stacked layers. Using these gates, we enhance the dynamic node representations follows:
(he) (ny (u))) DIP-UNIT (hiT) o 9n (P ( bur)): (o darco be h baa (m,)), 1₂)
Similarly, we can compute (h2 (he (e())) for v(() based the selection mechanism.
3.4 CONDITIONAL INTENSITY FUNCTION
We model the dynamic interactions
nulti-diimnsional temporal point process. Specifically, de- fine the conditional intensity function of the temporal point process at the dimension indexed by (u, v). given its graph-structured history H.S. where H. subgraph(ut (t), k)) U subgraphi (u (1),
subgraph( u (v)(t), k) U subgraph( u (t), k)., as follows:
n [t] n. SoftPlus (h, u.r WA + W. + bx)
(8)
where h. = bT (oy h ( h 1T (c..), (v.o)) the scalar by 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 -egaativvv of the intensity. A key step for obtaining H. is to get the k- depth subgraphs of u and v's direct dependants. Please see Appendix[A]oon more details about fast obtaining k-depth subgraphs.

---

Under review as a conference paper at ICLR 2020
3.5 MAXIMUM LIKELIHOOD PARAMETER ESTIMATION
3.5.1
INTERACTION PREDICTION
Given set of interactions as / {(u, Us 4 observed in time window [0, TJ, we can learn the model by minimizing the negative joint ligeliieihoodd of I as follows: L = "2,og : (t. where p".. (t, (......) represents the probability of formalizing an interaction between u, and 2; at time t; given the dependant history of non-chain structures H H,
Based on the intensity defimition, we have L = E; log A"i." (t.l + So A(t)dt, where A(t) = En, u1, (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 al. (2019) to accelerate the survival term calculation.
3.5.2 INTERACTION CLASSIFICATION
An interaction sequence with markers is denoted as /' = {(u4, U4 14, Wi where y, is a marker at time f; 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, marker can be used to label whether transaction is a fraudulent trading or not. The joint conditional density an interaction(u, U, with marker yi is given as Puc.
By applying the Bayesian rule, the joint conditional density can be written as: [s: Vil Ht, H pu.. (ta P P (Belt, ) Hu: where pu.. (G, has the same meaning as given in subsection 3.5.1 while P(yslt,, H.l..)) means the distribution of y: given the interaction happened at t, with interaction history H. should be noted that the history H. u, contains the information of history markers and one can design marker-specift intensity function like Mei & Eisner (2017b). For simplicity, in our marked temporal point processes, we assume that eunee
La Mil
(s: Vil yi " is independent of historical markers. We model P yillt,, fru..
exp (Vy, Nunseit Ey. exp (Vy ha.w,,)))
P (ur
where "t is the concatenation of (u().) and hy(c.) which can be regarded dynamic repre- sentation for an interaction between and v at t;, V2, is the weight parameters for the yith class. Then the overall cost function is C2 L1 Leross-entropy. where Leross-entropy a cross-entropy loss over marks:
Leross-entropy
Σ y/ log (Hr) g:
(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 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.
Hamilton et al.) 2017a Kipf & Welling 2017) are 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 8 Zhou al., 2018 [So et al. 2018.) Yu et al. 2018). but can be difficult to specify the appropriate aggregation granularity. Nguyen et al, 2018)) adds temporal constraint on random walk sampling, but it can't model the rich temporal information explicitly, Temporal point processes (TPPs) are an another alternative to model dynamics (Daley & Vere-Jones 2007). Several dynamic graph modeling methods based on the TPPs (Dai et al. 2016) Trivedi et al. 2019) have been proposed. Our method DIP differs from these TaP-based methods by the extension of the LSTM model over temporal dependency graphs, the multiple time resolution modeling via stacking, fusing and the selection mechanism. A recently proposed method Kumar al. (2019)
2013

---

Under review as a conference paper at ICLR 2020
models interactions directly by predicting the next interaction embedding. More detailed related work are included in Appendix
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 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 Graphsage". What's more, for comparing with VeelVvli et al., 2017) we also implement a graph attention aggregator based on GraphSage. CTDNEINguyen et al. 2018) is newly-proposed temporal network embedding method and also tranductive method like PPeeeoziierrozzi et al. 2014). It incorporates temporal order constraint when sampling walks from coneicontiuuuus 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 al.) 2016) models dynamic interaction sequences with two co-evolution recurrent neural networks. Hidden embeddings are learned for interactive nodes after each interaction. DyREP (Trveddi et al. (2199 uses a two-time scale deep temporal point process model capture dynamics of graphs. JODIE (Kumar et al., 2019) models interaction processes in 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 and hi As for interaction classification, we employ KS (Kolmogorov 1933) score as well AUC(Area under the ROC Curve) score.
5.2 EXPERIMENTAL SETTING
We conduct all the experiments with 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 l and 21, 3) for L. For Graphsage, the maximum number of 1 l-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 the performance does not improve for 5 epochs. For Graphsage, DynGEM DDeepCoevolve 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 INTERACTION PREDICTION
5.3.1 DATASETS
CollegeMsgl Leskeovee Leskovec & Krevl 2014) 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. interaction between two users means one answered another's 's questions or replied to his/her posts. Amazon(McAuley et al.) 2015) is composed of commodity rating data from amazon users. We use the Clothing subset of this dataset. MathhOverloow@(eskkor an existing answer on the Math Overflow website. Table I shows the detailed dataset statistics. In this table. Repetition is the rate of repeated interaction in datasets. For each dataset, we first sort these interactions by occurrence time and split them to be craining/validationn participants which only exist in validation set or test set removed.
& Krevi 2014) is comprised of interactions of commenting
sets. The cold-start
7

---

Under review as a conference paper at ICLR 2020
Table 1: Dataset Statistics for interaction prediction
CollegeMsg
Ubuntu
Amazon-Clothing
Math Overflow
Train/ # Valid/ # Test
55902/7814/5055
204846/39913/5527
50209/9195/7598
58596/24045/32705
Repetition in Valid(S)
72.55
56.60
0.00
67.42
Repetition in Test(%) (6)
75.67
67.57
0.00
79.92
Duration(days)
193.63
2587.96
3657.00
2350.12
5.3.2 RESULTS AND ANALYSIS
Figure summarizes the Mean Rank performances of all methods. On the whole, DIP method consistently beats all baselines by 65. 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 '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 CollegeMssg, Ubuntu and MathOverflo 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 Msg. Ubuntu and MathOverflow have lots of repetitive interactions (at least 75% for CollegeMsg and MathOverflow test data, 68% for ubuntu on test data shown in Table I 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 repetitive information can be reused and nodes representation can't 't be updated across validation and test like CTDNE. As for comparison with dynamic methods, 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 55 are given in Appendix[B] The effects of k and L are also investigated in Appendix
Crazzon-Clothing
5.4 INTERACTION CLASSIFICATION
5.4.1 DATASETS
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 validation set, the rest as test set. Note that, in this scenario, there are users who only appear validation/testing dataset. Thus, the transductive method CTDNE is not applicable this task. Meanwhile, since the dynamic baseline methods all unsupervised, we only report GCN and our marked DIP methods Alternatively, we employ the Boost (Chen & Guestrin 2016) as additional baseline which is popular baseline method in the cash-out detection task Hu et al. 2019). The detailed data statistics are given in Appendix[E]
5.4.2 RESULTS AND ANALYSIS
Table 2 compares the results. Obviously, our model outperforms all the baseline methods with large margins. The Xgboost method which only utilize interaction context feature can't model any co-evolution information in anne-evoliing interactions, thus it performs worst. The GCN-related methods perform worse than our DIP since the static construction of interaction graph can blur temporal structural information and miss time-interval information. A toy example in figure. 1 can explain why static graph methods fail in this task.
8

---

Under review as a conference paper at ICLR 2020
DIP
GAT
DIP
GAT
DyREP
Graphdagu CTDNE
DyREP
GrapiSagu
DeepConvohv
DeeyCoevobe
CTONE
Mean Rank
Mean Rank
201
310-42 312.77
1500
1000
CollegeMsg
Ubuntu
9000
DyREP
DIP
GAT
GrophSage*
700
DyREP
DIP
GAT
Grophšage*
DeepCoevotve
CTDNE
DeepCoevohre
CTONE
DynGEM
Mean Rank
Mean Rank
500
721.7%
6000
06-1.
300
5000
200
272.22
2033
MathOverllow 100
Clothing
Figure 4: Mean rank results. As low mean rank indicates that the ground-truth item is ranked accurately, we can observe that DIP always outperforms baselines.
Table Interaction classification results
Xgboost
GraphSage*
GAT
DIP
AUC
0.6818 +0.0023
0.8603 +0.0005
0.8597 +0.0004
0.9017 +0.004
KS
0.2536 +0.0015
0.5934 10.0012
0.6018 +0.0005
0.6703 +0.0060
5.5 ABLATION STUDY
As we described 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 extract high level feature. We investigate the contribution of each component by disabling each of them one by one, and compare and the corresponding result the full model. figure 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 DIP-UNIT is disabled. This leads significant drop of the Mean Rank performance. It provides 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, directly use the hidden state vector of the last layer. Again, the per- formance degrades significantly. This demonstrates that a fusion of different layers' representations gives richer information than the last layer only.
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

---

Under review as a conference paper at ICLR 2020
FullModel No-TimeGate
Selection
FullMode
Selection No-Fusion
140
No-Fusion
No-TimeGate
850
Mean Rank
120
129.36
130.92
Mean Rank
825
120.48
800
101.81
775
814.62
816.3
806.09
796.09
750
725
700
CollegeMsg
Ubuntu
8000
FullModel
No SolSelect No-Fusion
FullModel
Selection No-Fusion
No-TimeGate
No-TimeGate
Mean Rank
7127.69
Mean Rank
115.67
115.9
6000
6602.65
6602.68
100
106.71
5552.41
92.87
5000
3000
Clothing
MathOverflow
Figure 5: Ablation study results of the interaction prediction task. Disabling any of the three component leads to a performance drop.
No-Selection
FullMMdel No-TimeGate
No-Selection No-Fusion
2.95
No-TimeGate
No-Fusion
0.6703
AUC
0.9017
0.8381
0.8509
0.8459
0.5703
0.5948
0.5654
AUC
KS
Figure 6: Ablation study results of the interaction classification task. All of the three component contributes lot to improve the final classification precision.
multiple time resolutions via stacking, selection and fusion. Experimental results show the effective- ness of the components of our neural unit and the superior performance on several datasets.
REFERENCES
Odd Aalen, Ornulf Borgan, and Hakon Gjessing. Survival and event history analysis: a process point of view. Springer Science & Business Media, 2008
Amr Ahmed, Nino Shervashidze, Shravan Narayanamurthy, Vanja Josifovski, and Alexander Smola. Distributed large-scale natural graph factorization. In Proceedings of the 22nd international conference on World Wide Web, pp. 48. ACM, 2013.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. In Advances in neural information processing systems, pp. 585-591, 2002.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. arXiv preprint 13/..623/2.6200 2013.
10

---

Under review as a conference paper at ICLR 2020
Tianqi Chen and Carlos Guestrin. Xgboost: A scalable tree boosting system. In Proceedings the 22nd acm sigkdd international conference on knowledge discovery and data mining, pp. 785-794.
ACM, 2016.
Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. Deep coevolutionary network: Embedding and item features for recommendation. arXiv preprint arXiv: (60p:::0073337 2016.
Daryl Daley and David Vere-Jones. An introduction to the theory of point processes: volume II: general theory and structure. Springer Science & Business Media, 2007.
Michael Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. neural information processing systems, pp. 3844-3852. 2016.
Rianne Van Den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. arXiv: Machine Learning, 2017.
Nan Du, Hanjun Dai, Rakshit Trivedi, Utkarsh Upadhyay, Manuel Gomez-Rodriguee and Le Song. Recurrent marked temporal point processes: Embedding event history to vector. In Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1555 1564. ACM, 2016.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. arXiv preprint urXiv:1805.11275. 2018.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017a.
William L. Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data(base) Engineering Bulletin, 40:52-74, 74, 2017b.
Alan G Hawkes. Spectra of some self-exciting and mutually exciting point processes. Biometrika, 58 (1):83-90, 1971.
Binbin Hu, Zhiqiang Zhang, Chuan Shi, Jun Zhou, Xiaolong Li, and Yuan Qi. Cash-out user detection based on attributed heterogeneous information network with hierarchical attention mechanism. 2019.
John Frank Charles Kingman. P oisson processes. Encyclopedia of biostatistics, 6, 2005.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. international conference on learning representations, 2017.
Andrey Kolmogorov. Sulla determinazione empirica di una Igge di distribuzione. Inst. Ital, Attuari, Giom., 41, 1933.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1269-1278. ACM, 2019.
Jure Leskovec and Andrej Krevl. SNAP Datasets: Stanford large network dataset collection. http /snap. edu data June 2014.
Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. ACM Transactions on Knowledge Discovery from Data (TKDD), 1(1):2, 2007.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image-based based recommendations on styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference Research and Development in Information Retrieval, pp. 43-52. ACM, 2015.

---

Under review as a conference paper at ICLR 2020
Hongyuan Mei and Jason M Eisner. The neural hawkes process: A neurally self-modulating multivariate point process. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan. and R. Gameet Advances in Neural Information Processing Systems 30,
pp. 6754-6764. Curran Associates, Inc., 2017a.
Hongyuan Mei and Jason M Eisner. The neural hawkes process: A neurally self-modulating multivariate point process. In Advances in Neural Information Processing Systems, pp. 6754-6764, 2017b.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances neural information processing systems, pp. 3111-3119, 2013.
Federico Monti, Michael M Bronstein, and Xavier Bresson. Geometric matrix completion with recurrent multi-graph neural networks. neural information processing systems, pp. 3697-3707,
2017.
Giang Hoang Nguyen, John Boaz Lee, Ryan A. Rossi, Nesreen K. Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-time dynamic network embeddings. In Companion of the The Web Conference 2018 The Web Conference 2018, WWW 2018, Lyon, , France, April 23-27, 2018, pp. 969-976, 2018.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710. ACM, 2014.
Matthew E. Peters, Mark Neumann, Mohit lyyer, Matt Gardner, Christopher Clark, Kenton Lee, and Luke Zettlemoyer. Deep contextualized word representations. In Proc. of NAACL, 2018.
Sam T Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2333-2555 2326, 2000.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dynamic graph representation learning via self-attention networks. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80, 2009.
Youngjoo Sco, Michaël Defferrard, Pierre Vandergheynst, and Xavier Bresson. Structured sequence modeling with graph convolutional recurrent networks. In International Conference on Neural Information Processing, pp. 362-373. Springer, 2018
Sucheta Soundarajan, Acar Tamersoy, Elias B Khalil, Tina Eliassi-Rad, Duen Horng Chau, Brian Gal- lagher, and Kevin Roundy. Generating graph snapshots from streaming edge data. In Proceedings of the 25th International Conference Companion on World Wide Web, pp. 109-110. International World Wide Web Conferences Steering Committee, 2016.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scate scale information network embedding. In Proceedings of the 24th International Conference on World Wide Web, pp. 1067-1077. International World Wide Web Conferences Steering Committee, 2015.
Joshua Tenenbaum, Vin De Silva, and John C Langford. global geometric framework for nonlinear dimensionality reduction. science, 290(5500):2319-2222 2000.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning
representations over dynamic graphs. In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, 2019. URL https:/:: http:////pneeeeeee.eoe/e net/ /
Forum?id=HHyePzhR5k
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1710 2017.
Daixin Wang, Peng Cui, and Wenwu Zhu. Structural deep network embedding. pp. 1225-1234, 2016.
12

---

Under review as a conference paper at ICLR 2020
Xiao Wang, Peng Cui, Jing Wang, Jian Pei, Wenwu Zhu, and Shiqiang Yang. Community preserving network embedding. Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Shuai Xiao, Mehrdad Farajtabar, Xiaojing Ye, Junchi Yan, Le Song, and Hongyuan Zha. Wasserstein learning of deep generative point process models. In Advances in Neural Information Processing
Systems, pp. 3247-3257, 2017.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. knowledge discovery and data mining, pp. 983,983, 2018.
Wenchao Yu, Wei Cheng, Charu C Aggarwal, Kai Zhang, Haifeng Chen, and Wei Wang. Netwalk: A flexible deep embedding approach for anomaly detection in dynamic networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp- 2672-2681. ACM, 2018.
Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yucting Zhuang. Dynamic network embedding by modeling triadic closure process. Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Linhong Zhu, Dong Guo, Junming Yin, Greg Ver Steeg, and Aram Galstyan. Scalable temporal latent space inference for link prediction dynamic social networks. IEEE Transactions on Knowledge and Data Engineering. (3(10):2765-7777) 2016.
13

---

Under review as a conference paper at ICLR 2020
A TEMPORAL DEPENDENCY GRAPH
The key step for efficient training or inference is to fast obtain subgraph(u(t), k) or subgraph(u(t). k) for interaction (u, v, t). Obviously, our definition of temporal dependency graph(TDG) in Subsec- tion provides provides recursive and incremental way for its construction. As illustrated in figure 2 we can easily find that subgraph(u()).. k) is the union of subgraph(u(I), k), subgraph(w(( (t_, k)) and newly added dependency edges. Based on this feature, to fast obtain k- depth subgraph, we design two algorithms, TDG- DOG-COLORING and CONSTRUCTION OF K E-DEPTH TDG orderly.
A.1 TDG-COLORING
The TDG-COLORING algorithm shown in Algorithm which the pre-step of Algorithm 2 This algorithm takes = {u, v; +)) as input and generate a new sorted sequence of interactions ordered by color numbers in an ascending way. The TDG-COLORING algorithm ensures that, interactions in the same color group are independent and interactions from groups with smaller color numbers are precedents of the larger ones.
Algorithm 1 TDG-COLORING
Require: I: A sequence of interaction with chronological order. Ensure: ColorGpSeq: sequence sorted interactions by color no.
1: Initialize ColorGroupArye for all nodes
represents nodes in and assign an initial color
2: Initialize Last.N Last.NdeTiimepp interaction and initialize with
Record the latest time when node x was involved in an
3: for event do
4: cur _t, cur_u, cur sur_tmme = event.u, event.v, event.
5: if cur time cur_time's LastNodeTiime iodeerieeuurr... then
6:
Color Groooprrorrreeeeee
7:
Last.NoeeTine imme/cur cur cur_time end if if cur simttime? > LastNodeTimmepppe then
8:
9:
10:
11:
(cur cur cur__ime
12:
end if
13: event.gn = mmo CaaaCoCCCrrruuurrrarrroioooCCoor ColorGroupArrayycrr
>> is short
for group
14:
end for
ColorGpSeq SIrt(I)
sort I by an ascending order with assigned group color no.
16: return GolorGpSey
A.2 CONSTRUCTION OF K-HOP TDG
The details of CONSTRUCTION OF K-DEPTH TDG are given in Algorithm 2 In Algorithm based on the definition of TDG and ColorGpSeq output by Algorithm we can incrementall construct the k-depth subgraphs for any two nodes in a new interaction. Specifically, we first call PREVIOUS function to get each node's is adjacent interaction in which it was involved before current interaction. Then incrementally construct Ht subgrah hw__peennteraceeeeeeeeeeoo ranks ahead of current event in ColorGpSeq. Likely, we can get
graph(ugraph) rooted cur our_u(lnes 6 to 10). Here stores the subgraph of ugraph which was obtained before ugraph
because u d_ppeennteraction ugraph incrementally. At last, call the Breadth- Fetth-FFisttStttt Strst-Search algorithm with the traverse depth K to obtain the k-depth subgraphs for cur cur_eeerrr event and then store it into Hę subgraph _eeent)
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 Algorithm 2 for interaction | from the
14

---

Under review as a conference paper at ICLR 2020
Algorithm 2 CONSTRUCTION OF K-DEPTII TDG
Require: Coler A seq of sorted interaction by group color no.
Ensure: HashTable HІ subgraph: Map an interaction to its corresponding k_subgruph.
1: Initialize empty HashTable Hk ruggghhh
2: for cur cur_event in ColorGpSeq do
3: cur_u, cur _ event.u, cur_ _er_evett.r
4:
p.reenteeaaction Previous(curs involved U "_preInneraactinn
Previous Function returns last interaction which
5:
crviousscur_...
6:
if uru_prennteeaaiion exits then
7:
cur_u) definition of dependency graph
edge)
b. The edge is defined according to the
8:
edgez (u prrppeel oreenntraction. cur_
9:
ugraph- = edge; edgez
10:
ugraph = Hx subgraph hattg/ppptpppee/eeeeeeeeeeeeeee
pre Interaction) U uggaphh
Incremental Update
else
12:
ugraph cur
13: end
14: if
preInteraction exits then
15:
edges (v wt__peennteractoon cur_
edges (v re_pre//nlerracion.r cur_v)
17:
vgraph = edges U edges
ugraph Hubgoph preInteraction] ugraph
Incremental Update
19:
else
ugraph cur
21:
end if
GK-depth B(S(uggaph U ugraph, depth K) Call Breadth-Fiig First-Searce with max depth K
23:
H2 Sh.sugmpp
deppthth
end for 25: return subgrooh
24:
collected training interaction data, we can obtain its corresponding k-depth subgraphs directly using subgrapi [2] with time complexity (11) For new incoming interaction 1 with two nodes cur _u and cur we can easily reuse Algorithm 2 code from line 3 to 22 to find ugraph and egraph, respectively. Then we merge them to get k-depth subgraph for doing inference online. the same time, we can incrementally update TDG by HA subgrophl([). The time complexity here for updating TDG mainly depends on union between ugraph and ugruph line of Algorithm and O(n+e) where and the total number of nodes and edges for ugraph and ugraph.
B ADDITIONAL DATA STATISTICS AND EXPERIMENT RESULTS
B. HUABEI TRADE DATASET
Table 3: Huabei Dataset Statistics
Interaction
Seller
# Buyer
Repetition (%)
Train
60705
19453
22916
Valid
53609
16669
23517
25.21
Test
34471
9929
17549
23.55
15

---

Under review as a conference paper at ICLR 2020
45
DIP
GAT
DIP
GAT GraphSSaee
DyREP
Sage CTDNE
DyREP
DeepConvolve
DeepConvolve
CTONE
HIT@S
20
6.37
22:18
10
12.
CollegeMsg
Ubuntu
0.5
DIP
GAT
DIP
GAT
DyREP
GraphSage*
DyREP
GraphSage"
DeepCoeevlvv
CTDNE
50
Drepooee
CTONE
0.4
DynGEM
DynGEM
HIT@8
0.2
3.27
2:23
10
0.21
0.0
Clothing
MathOverllow
Figure 7: Hit@5 Results
DIP
GAT
DIP
GAT
DyREP
GraphSage*
DyREP
GraphSage*
CTONE
17.5
CTONE
DynGEM
DynGEM
15.0
HIT@1
30.0
1375
7.5-
13.03
1:14
1/15
5.0
0.0
CollegeMsg
Ubuntu
0.30
DyREP
DIP
Graph-Sag"*
GAT
DyREP
DIP
GAT
Graph-Sage*
DeepCoovoiive
CTDNE
25
DeepConvoive
CTONE
HIT@1
57123
+.03
Clothing
MathOverflow
Figure 8: HIT@ Results
B.2 HIT PERFORMANCE
Figure and Figure provide HIT@5 and Hit@] results in addition to the Mean Rank results in E
Section 5.3.2 of the main paper. HIT@n is defined H HIT@n #of Test Interaction where 1
if rank; else O, which measures the ability of top rank prediction.
16

---

Under review as a conference paper at ICLR 2020
150
0.70
L=1
L=2
L=3
145
0.65
0.60
140
135
0.50
0.40
120
115
0.30
(a) CollegeMsg
(b) Huabei Trade data
Figure 9: Sensitivity to k and L.
800
DIP
Graphdiage
CTONE JODIE
0.75
DIP
GAT
GraphSage
700
DeepCoevoive
DyREP
0.70
600
Rank
500
400
0.55
0.50
200
0.45
100
0.40
32
128
16
32
64
128
Dimension
Dimension
(a) CollegeMsg
(b) Huabei Trade data
Figure 10: Sensitivity to dynamic representation dimension.
B.3 EFFECT THE DEPTH AND THE NUMBER OF LAYERS
For given node u(t). only the history information in k-depth temporal subgraph, i.e. subgraph(u((), k), is considered to calculate the dynamic representation, so the number of depth k could affect the final representation. Meanwhile, our proposed fusion mechanism based deep model which can capture different information at different layers. So, in this subsection, we investigate the effects of l 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 it 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 similar) for interaction classification on Huabei Trade Data in figure I0 figure I0 (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.
17

---

Under review as a conference paper at ICLR 2020
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, (200) or matrix factorization AAmmed 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 Skip- gram(Mikolov et al,] (013) 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: Peroozi et al. (2014) proposed the DeepWalk model utilizing random walks on graph to generate sequences of nodes, and feed them into the Skip-gram gram model to learn nodes' low dimensional representation vector. Then, Tang 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 & Leskoved (2016) designed biased random-war walk sampling method to capture more flexible neighborhood information which is helpful 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 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 trunsductivve, 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-traine 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 (2016) uses an non- negaatee 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 stable embedding over time. Seo et al. 2018)) combines CNN module and a RNN module to capture spatial characteristics and temporal characteristics. NetWalk 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 't explicitly models the rich temporal information.
sequence of graph snapshot(Soundarajan et al.) (0066) /hhu al.
Temporal Point Process: Temporal Point Process is powerful statistical tool for modeling se- quences of events with unequal interval. It has been wildly used in recent research with different intensity function: from parametric(Du Du al. 2016) to recurrent neural networks Dai et al., 2016 Mei & Eisner 20177)) event reinforcement learning based et al., 2017). DeepCoevolve Dai et al. 2016) designs recurrent neural network 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 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.
18


Reviews:
[{"review_id": "SyeMN893cr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper is concerned with modeling continuous time-evolving graphs, for which it proposes to combine temporal point processes with a recurrent architecture to learn dynamic node representations. In addition, the paper proposes to stack multiple recurrent layers (to obtain node representations over multiple time scales) and use a temporal attention mechanism (to select relevant past interactions).\n\nModeling temporal and dynamic graphs is an important problem with many applications in ML and AI. The focus of the paper, i.e., to develop improved models by combining TPPs and representation learning, is a promising approach to this task and fits well into ICLR. Furthermore, the presented experimental results are promising.\n\nHowever, I'm concerned about different aspects of the current version: The main contributions of the paper are a recurrent (LSTM-based) architecture to model the intensity function of a TPP, stacking multiple LSTM to form a deep architecture, and a temporal attention mechanism. However, none of these contributions on its own are particularly novel. For instance, prior work that introduces similar approaches include \n- Recurrent networks to parameterize intensity functions: (Dai, 2017), (Mei & Eisner, 2017), (Trivedi, 2019), ... \n- Temporal attention: (Trivedi, 2019) \n\nHence, the main novelty seems to lie in the stacked architecture and the particular combination of modules (which is of limited novelty). The experimental results are certainly interesting, but it would be important to provide a more detailed analysis of the model to get insights into the causes for these improvements.\n\nWith regard to the model: The Log-likelihood function in Section 3.6.1 seems to be incorrect as the LL for a TPP would be L = \\sum_{i:t_i \\leq T} \\log\\lambda(t_i) - \\int_0^T \\lambda(s)ds, which is quite different from the equations in the paper. Is the LL in Section 3.6.1 the actual objective that has been optimized?\n\nRegarding the experimental results: All models are trained on the same grid of embedding dimensions, but the proposed method is the only deep model. Hence, its maximum number of parameters can be up to 4x compared to the shallow models. How do the results look if all for models with comparable number of parameters (i.e., can the improvements be explained due to this difference)? It would also be good to get results on commonly used benchmarks (e.g. data used in DyRep or NeuralHawkes) to make the results of the new model comparable to prior experiments and datasets.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "HkxlmTgAqS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nThe 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].\n\n\nMain Comments:\n--------------\n- 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.\n \n- 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?\nSimilarly, 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?\n\n- 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?\n\n- 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?\n\n- 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? \n\n- 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?\n\n- 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?\n\n- 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\n\n- 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\n\n- 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.\n\nMinor:\n-------\n\n- 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 $\\hat{x}_{u(t)}$ a vector?\n\n- Please provide numbers to equations for better referencing\n\n[1] Predicting Dynamic Embedding Trajectory in Temporal Interaction Networks, Kumar et. al. KDD 2019", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "N/A", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "HkgAT1el5S", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper considers modeling continuous time-evolving graphs using a temporal point process framework. It introduces a time gate in the LSTM to handle the temporal dependency and uses an attention mechanism to select relevant nodes to learn the underlying dynamics. \n\nOverall, this paper is not easy to understand in detail. Firstly, it is unclear how and why the temporal point process can deal with growing/shrinking graph nodes and changing interactions. Secondly, how does the DIP-UNIT handle the continuous graph changing? What if the graph changes with an uneven speed? Thirdly, how do all the small pieces work together to achieve the goal of the paper? An overview diagram or a toy example would greatly improve the readability of the paper. \n\nBesides, what is the computational cost of the proposed network? How large a graph could be and how fast its changes could be captured? ", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I did not assess the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers rated this paper as a weak reject.
The author response was just not enough to sway any of the reviewers to revise their assessment.
The AC recommends rejection.
Decision: Reject