Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks
Authors: Yanbang Wang
Yen-Yu Chang
Yunyu Liu
Jure Leskovec
Pan Li
Venue: ICLR 2021 Poster (2021)
Keywords: temporal networks
inductive representation learning
anonymous walk
network motif

Abstract: Temporal networks serve as abstractions of many real-world dynamic systems. These networks typically evolve according to certain laws, such as the law of triadic closure, which is universal in social networks. Inductive representation learning of temporal networks should be able to capture such laws and further be applied to systems that follow the same laws but have not been unseen during the training stage. Previous works in this area depend on either network node identities or rich edge attributes and typically fail to extract these laws. Here, we propose {\em Causal Anonymous Walks (CAWs)} to inductively represent a temporal network. CAWs are extracted by temporal random walks and work as automatic retrieval of temporal network motifs to represent network dynamics while avoiding the time-consuming selection and counting of those motifs. CAWs adopt a novel anonymization strategy that replaces node identities with the hitting counts of the nodes based on a set of sampled walks to keep the method inductive, and simultaneously establish the correlation between motifs. We further propose a neural-network model CAW-N to encode CAWs, and pair it with a CAW sampling strategy with constant memory and time cost to support online training and inference. CAW-N is evaluated to predict links over 6 real temporal networks and uniformly outperforms previous SOTA methods by averaged 15\% AUC gain in the inductive setting. CAW-N also outperforms previous methods in 5 out of the 6 networks in the transductive setting.

Published as a conference paper at ICLR 2021
INDUCTIVE REPRESENTATION LEARNING IN TEMPO- RAL NETWORKS VIA CAUSAL ANONYMOUS WALKS
Yanbang Wang'; Yun-Yu Chang?; Yunyu Liu Jure Leskovec', Pan Li Department of Computer Science, Flectrical Engineering, Stanford University Department of Computer Science, Purdue University
(ywangår, jure) ) êcs. stanford edu, yww.u@ttanoord.eed {1iu3154, 4, panli Y @purdue. edu
ABSTRACT
Temporal networks serve as abstractions of many real-world dynamic systems. These networks typically evolve according to certain laws, such as the law of triadic closure, which is universal in social networks. Inductive representation learning of temporal networks should be able to capture such laws and further be applied systems that follow the same laws but have not been unseen during the training stage. Previous works in this area depend on either network node identities or rich edge attributes and typically fail extract these laws. Here, we propose Causal Anonymous Walks (CAWs) to inductively represent a temporal network. CAWs are extracted by temporal random walks and work as automatic retrieval of temporal network motifs to represent network dynamics while avoiding the time-consuming selection and counting of those motifs. CAWs adopt a novel anonymization strategy that replaces node identities with the hitting counts of the nodes based on set of sampled walks to keep the method inductive, and simultaneously establish the correlation between motifs. We further propose neural-network model CAW-N to encode CAWs, and pair it with a CAW sampling strategy with constant memory and time cost to support online training and inference. CAW-N is evaluated to predict links over 6 real temporal networks and uniformly outperforms previous SOTA methods by averaged 15% AUC gain in the inductive setting. CAW-N also outperforms previous methods in 5 out of the 6 networks in the transductive setting.
INTRODUCTION
Temporal networks consider dynamically interacting elements as nodes, interactions as temporal links, with labels of when those interactions happen. Such temporal networks provide abstractions to study many real-world dynamic systems (Holme & Saramäki 2012). Researchers have investigated temporal networks in recent several decades and concluded many insightful laws that essentially reflect how these real-world systems evolve over time (Kovanen et al. 2011 Benson et al.] [2116] [Paranjape] et al. 2017 Zitnik et al. 2019). For example, the law of triadic closure in social networks, describing that two nodes with common neighbors tend to have a mutual interaction later, reflects how people establish social connections (Simmel 1950). Later, more elaborate law on the correlation between the interaction frequency between two individuals and the degree that they share social connections, further got demonstrated (Granovetter) 1973. Toivonen et al.. 2007). Feedforward control loops that consist of direct interaction (from node w to node v)) and an indirect interaction (from w through another node e to u), also work as law in the modulation of gene regulatory systems (Mangan & Alon, 2003) and also the control principles of many engineering systems (Gorochowski al. 2018). Although research on temporal networks has achieved the above success, it can hardly be generalized to study more complicated laws: Researchers have to investigate exponentially increasing number of patterns when incorporating more interacting elements let alone their time-evolving aspects.
Recently, representation learning, via learning vector representations of data based on neural net- works, has offered unprecedented possibilities to extract, albeit implicitly, more complex structural patterns (Hamilton et al. [017b] [Battaglia et al.] (208).. However, as opposed to the study on static networks, representation learning of temporal networks is far from mature. Two challenges on temporal networks have been frequently discussed. First, the entanglement of structural and temporal
Project website with code and data:

---

Published as a conference paper at ICLR 2021
eaWsextracted:
CAWsestrated
w
51
2
22
21
C3
Law explanatione Two nodes that share common node directly connected them lend to be connected.
Law explanation One node activates another node first (ul and then aclivates a third node (v). Mostly third node will inhibit the second node later.
Triadic closure E2 < (g)
Feed forward control (4, 12 1z)
Figure 1: Triadic closure and feed-forward loops: Causal anonymous walks (CAW) capture the laws.
temporal graph with timestapped links and
Example: three 3-step walks (t,. the default timestamp and the default node when historical links can be found)
queried link at certain time:
d
3,9
u
0
3,6
10
3,77
Syy
O
Spa
5
7,9
8
4,8
h
u
7
h
Backtrack m- step random walks over time before t=10:
Count number of b's different positions:
(0.
1.
0)"
(0.
0.
1)²
M walks starting at IcAw (b; Syn Sa). s, (Relative node identity)
Anonymize
6
3
M walks starting at v Causality Extraction
- leaw (a) 1 loaw (c)
3
(un leaw (b)
Set- Set--ased nonymization
Figure 2: Causal anonymous walks (CAW): causality extraction and set-based anonymization.
patterns required an elegant model to digest the two-side information. Second, the model scalability becomes more crucial over temporal networks as new arriving links need to be processed timely while a huge link set due to the repetitive links between two nodes needs to be digested simultancously.
In contrast to the above two challenges, another challenge, the inductive capability of the temporal- network representation, is often ignored. However, it is equally important if not more, as the inductive capability indicates whether the models indeed capture the dynamic laws of the systems and can be further generalized to the system that share the same laws but have not been used to train these models. These laws may only depend on structures such as the triadic closure or feed-forward control loops as aforementioned. These laws may also correlate with node attributes, such as interactions between people affected by their gender and age (Kovanen et al. 2013). But in both cases, the laws should be independent from network node identities. Although previous works tend to learn inductive models by removing node identities (Trivedi et al.) 2019 Xu et al., 2020), they run into other issues to inductively represent the dynamic laws, for which leave more detailed discussion in Sec. e
Here we propose Causal Anonymous Walks (CAW) for modeling temporal networks. Our idea for inductive learning is inspired by the recent investigation on temporal network motifs that correspond to connected subgraphs with links that appear within a restricted time range (Kovanen et al.. 2011 Paranjape et al., (0177). Temporal network motifs essentially reflect network dynamics: Both triadic closure and feed-forward control can be viewed as temporal network motifs evolving (Fig. I] An inductive model should predict the 3rd link in both cases when it captures the correlation of these two links as they share common node, while the model is agnostic to the node identities of these motifs.
Our CAW model has two important properties (Fig. 2): (1) Causality extraction from link of interest and backtracks several adjacent links over time to encode the underlying causality of network dynamics. Each walk essentially gives a temporal network motif; (2) bet-based anonymization CAWs remove the node identities over the walks to guarantee inductive learning while encoding relative node identities based on the counts that they appear at a certain position according to a set of sampled walks. Relative node identities guarantee that the structures of motifs and their correlations are still kept after removing node identities. To predict temporal links between two nodes of interest, we propose a model CAW-Network (CAW-N) that samples a few CAWs related to the two nodes of interest, encodes and aggregates these CAWs via RNNs (Rumelhart et al. 1986) and set-pooling respectively to make the prediction.
CAW starts
2

---

Published as a conference paper at ICLR 2021
Experiments show that CAW-N is extremely effective. CAW-N does not need to enumerate the types of motifs and count their numbers that have been used as features to predict network dynamics (Lahini
& Berger- Wolf 2007:
Rahman & Al Hasan 2016; Rossi et al., 2019; AbuOda et al.) 2019 Li
& Milenkovic 2017). which significantly saves feature-engineering effort. CAW-N also keeps
all fine-grained temporal information along the walks that may be removed by directly counting motif's (Ahmed et al. 2015 Paranjape et al. 2017). CAWs share a similar idea as anonymous walks (AW) (Micali & Zhu 2016) to remove node identities. However, AWs have only been used for entire static graph embedding (Ivanov & Burnaev 2018) and are not directedly applied to represent temporal networks: AWs cannot capture causality: AWs get anonymized based on each single walk and hence lose the correlation between network motifs. In contrast, CAWs capture all the information, temporal, structural, motif-correlation that are needed, to represent temporal networks.
We conclude our contributions in three-folds: (1) A novel approach to represent temporal network CAW-N is proposed, which leverages CAWs to encode temporal network motifs to capture network dynamics while keeping fully inductive. CAW-N is evaluated to predict links over 6 real-world tem- poral networks. CAW-N outperforms all SOTA methods by about 15% averaged over 6 networks in the inductive setting and also significantly beat all SOTA methods over 5 networks in the transductive setting: (2) CAW-N significantly decreases the feature-engineering effort in traditional motif selection and counting approaches and keeps fine- -na-grai temporal information; (3) CAW-N is paired with CAW sampling method with constant memory and time cost, which conduces to online learning.
2 RELATED WORK
Prior work on representation learning of temporal networks preprocesses the networks by simply aggregating the sequence of links within consecutive time windows into network snapshots, and use graph neural networks (GNN) (Scarselli et al.] 2008 Kipf & Welling 2017) and RNNs or transformer networks (Vaswani et 2017) to encode structural patterns and temporal patterns respectively (Pareja et al. 20200 Manessi et al. 2020 Goyal et al., 2020, Hajiraezanalii et al. 2019) Sankar et al.) 2020). The main trawback of these approaches that they need to predetermine time granularity for link aggregation, which is hard to learn structural dynamics in different time scales, Therefore, approaches that work on link streams directly have been recently proposed (Trivedi et al. 2017 2019 Kumar et al. 2019 Xu et al. 2020). Know-E (Trivedi et al.) 2017). DyRep (Trivedi) al. 2019) and JODIE ( (Kumar al. 2019) use RNNS to propagate messages across interactions to update node representations. Know-E, JODIE consider message exchanges between two directly interacted nodes while DeRep considers an additional hop of interactions. Therefore, DyRep gives a more expressive model at a cost of high complexity. TGAT (Xu et al. (020) in contrast mimics GraphSAGE (Hamilton et al. 2017a) and GAT (Veličković et al.] to propagate messages in a GNN-like way from sampled historical neighbors of node of interest. TGAT's s sampling strategy requires to store all historical neighbors, which is unscalable for online learning. Our CAW-N directly works on link streams and only requires to memorize constant many most recent links for each node.
Most of the above models are not inductive be- cause they associate each node with an one- hot identity (or the corresponding row of the adjacency matrix, or free-trained vector) (Li jet al.
L, b
History: (a. 6, t.). (a', t. t. (a, t2). (a', 82))): The order of timestamps: < by < (g-
Question Which is more likely to happen, (a, b,1) or (af, b,tg)?
2018 [Cen et al.)
2019
Kumar et al.
Figure 3: Ambiguity due to removing node identi- ties in TGAT (Xu et al., 2020) (4 < l2 < 1z).
2019
Hajiramezanali et al.
2019 Sankar et al.
2020
Manessi et al. 2020 Goyal et al. 2020).
TGAT
(Xu et al. (020)) claimed to be inductive by removing node identities and just encoding link timestamps and attributes. However, TGAT was only evaluated over networks with rich link attributes,
where the structural dynamics not captured essentially: If we focus on structural dynamics only, it is easy to show a case when TGAT confuses node representations and will fail: Suppose in the history, two node pairs {a, b) and {a', 8/} only interact within each pair but share the timestamps (Fig. Intuitively, a proper model should predict that future links still appear within each pair. However, TGAT cannot distinguish a v.s. a', and b v.s. b', which leads to incorrect prediction. Note that GraphSAGE (Hamilton et al.) 2017a) and GAT (Veličković et al. 2018) also share the similar issue when representing static networks for link prediction (Zhang et al. 2020 Srinivasan & Ribeiro 2019). DyRep (Trivedi et al. 2019) is able to relieve such ambiguity by merging node representations with their neighbors' via RNNs However, when DyRep runs over a new network, it frequently encounters node representations unseen during its training and will fail to make correct prediction.
3

---

Published as a conference paper at ICLR 2021
Algorithm 1: Temporal Walk Extraction (E, a, M, m. wo. to)
Therule: "one node (eg u) interacts with other nodes only another node interacts with node lesast twice."
Initialize M walks: W; < ((wb, fo)). S Sis M;
for j from 1 to do
for i from 1 to M do
(wp: v the last (node, time) pair in W;;
Sample one (e, t) E Exp,,, with prob. oc exp(a(t- tp)) Denote e = {w', w and then W; + W2 @ (w', t);
takes action u. NOT takes action Figure 4: The correlation be- tween walks needs to be captured to learn this law.
Return {Wil1 S SiSM):
Our CAW-N removes node identities and leverages relative node identities to avoid the issue in Fig. Detailed explanations are given in Sec 4.2
approaches may also be applied to temporal networks (Zhou et al., 2018 Du jet al., 2018; Mahdavi et al. 2018: Singer et al. 2209)) Nguyen et al. 2018). However, they directly assign each node with learnable vector. Therefore, they are not inductive and cannot digest attributes.
PROBLEM FORMULATION AND NOTATIONS
Problem Formulation. A temporal network can be represented as a sequence of links that come in over time, i.e. 3 = {e1 f1), (e2, t..) where e; is a link and & is the timestamp showing when e, arrives. Each link e; corresponds we first assume those links to be undirected and without attributes while later we discuss how to generalized our method to directed attributed networks. The sequence of links encodes network dynamics. Therefore, the capability of model for representation learning of temporal networks is typically evaluated by how accurately it may predict future links based on the historical links (Sarkar et al. 2012). In this work, we also use link prediction as the metric. Note that we care not only the link prediction between the nodes that have been seen during the training. We also expect the models to predict links between the nodes that has never been seen the inductive evaluation.
dyadic event between two nodes {u,, uz For simplicity,
Notations. We define E = {(e, t') E Elt < t, V E e} to include the links attached to a node v before certain time A walk W (reverse over time) temporal networks can be represented as
W = ((wo, ta), (w1,11),-. (Wm: fmn)); to > 1 >
(1) lmn (fw;-1, w/ (,4)) 4) for all
We use [[]]] to denote the ith node-time pair, and W [i][ and W[i][1] to denote the corresponding node and time in Wii] correspondingly, Later, we also use as vector concatenation.
Temporal network molifs are defined as connected subgraphs that consist of links appearing within restricted time range (Kovanen et al., 2011]. Based this definition, each walk defined in Eq. naturally corresponds to a temporal network motif as long as (t1 tm) is in the time range.
PROPOSED METHOD: CAUSAL ANONYMOUS WALK-NETWORK
4.1 PRELIMINARIES: ANONYMOUS WALK AND TEMPORAL NETWORK MOTIF
Anonymous walks were first considered by Micali & Zhu (016) to study the reconstruction of Markov process from the records without sharing a common "name space". AWs can be directly rephrased in the network context. Specifically, an AW starts from node, performs random walks over the graph to collect a walk of nodes, e.g. (11, D2 ..., Um). AW has an important anonymization step to replace the node identities by the orders of their appearance in each walk, which term relative node identities in AW and define it as
Law (w; W) A [vo, Fi, vi...., vk- } where ks the smallest index s.t. Ug- = w.
Note that the set operation above removes duplicated elements. Although AW removes node identities, those nodes are still distinguishable within this walk. Therefore, an AW can be viewed network motif while the information on which specific nodes form this motif is removed. Examples of AWs are shown as follows. While these are two different walks, they may be mapped the same AW when node identities get removed.
Anonymous Wolks
Network Motifs
2 Each walk gets anomymized independently
4

---

Published as a conference paper at ICLR 2021
4.2 CAUSAL ANONYMOUS WALK
We propose CAW that shares the high-level concept with AW remove the original node identities. However, CAW has a different causal sampling strategy and a novel set- btsed approach for node anonymization, which are specifically designed encode temporal network dynamics (Fig. 2
Causality Extraction, Alg.
- shows our causal sampling: We sample connected links by backtracking time extract the underlying causality of network dynamics. More recent links may be more informative and thus we introduce a non-negative hyper-
a to sample a link with probability proportional to exp(a(t - fp) where L, 4p are the timestamps of this link and the link previously sampled respectively. A large a can emphasize more on recent links while zero a leads to uniform sampling. In Sec44.4 we will discuss an efficient sampling strategy for the step 5 in Alg which avoids computing those probabilities by visiting the entire historical links.
Then, given link {uo: Fot and a time to. we use Alg. to collect M many m-step walks starting from both Me and No. and record them in S., and S. respectively. For convenience, a walk W from a starting node Wh E {u, v} can be represented as [
Set-based Anonymization. Based on S. and S,, we may anonymize each node identity w that appears on at least one walk in S., S, and design relative node identity IcAw(wu (w; (S., S.)) for w. Our design has the following consideration. Law (Eq only depends on a single path, which results from the original assumption that any two AWs do not even share the name space (i.e. node identities) (Micali & Zhu 2016 However, in our case, node identities are actually accessible, though an inductive model is not allowed to use them directly. Instead, correlation across different walks could be key to reflect laws of network dynamics: Consider the case when the link (u. v) happens only if there is another node appearing in multiple links connected to u (Fig. 4 Therefore, we propose use node identities to first establish such correlation and then remove the original identities.
Specifically, we define Tcaw(w; {Su, 5 as follows: For wo E {u, w}. let g(w, Swo) E z=+1 count the times in Se,, node w appears at certain positions, i.e., g(w, Sw,, ]b] KWIW E Swo w W[]0 for E {0, 1,.,, m). Further, define
Icaw (w; {Su, S.)) & (o(w, Sw), o(w,S.)}
(3)
Essentially, g(w, S.) and ((w, Sy) encode the correlation between walks within S. and S, respec- tively and the set operation in Eq establishes the correlation across S, and S... For the case in Fig 3 suppose Sa, Sb, Say, Sn include all historical one-step walks (before (2) starting from a, b, a' respectively. Then, it is easy to show that Acw (a; {Sa,, S,D) + lw (a'; (Sar, St that allows differentiating a and a', while TGAT (Xu et al., 2020) as discussed in See fails. From the network- motif point of view, lw not only encodes each network motif that corresponds to one single walk as Law does but also establish the correlation among these network motifs. Law cannot establish the correlation between motifs and will also fail to distinguish and a' in Fig We it as significant breakthrough as such correlation often gets neglected in previous works that directly count motifs or adopt AW-type anonymization Law.
Later, we use Icaw(w) for simplicity when the reference set (S.., S.b can be inferred from the context. Then, each walk W [Eq[] can be anonymized as
W ((Jcaw (wo)), to), (JeAw (a1).ww1,,)..) tz), ..... (Ja (Wm), fm))
(4)
The following theorem indicates that ICAw does not depend on node identities to guarantee the inductive property of the models, which can be easily justified.
For two pairs of walk sets {Su, S.) and (Sur, S.r if there exists bijective mapping क between node identities such that each walk W in S., U S. can be bijectively mapped to one walk W' in Sw U Sur according to x (W [[]][0)) [i] for all i [0, m). Then Ic (S., S.)) TCAw ( (m(w) (Sa,, 3,r for all nodes w that appear in at least one walk in S, U.S.
Theorem 4.1.
4.3 NEURAL ENCODING FOR CAUSAL ANONYMOUS WALKS
After we collect CAWs, neural networks can be conveniently leveraged to extract their structural (in (-))(:)) and fine- temporal information by encoding CAWs: We will propose the model CAW-N to first encode each walk W. (Fq and then aggregate all encoded walks in S, U.S..
5

---

Published as a conference paper at ICLR 2021
Measurement
Reddit
Wikipedia
MOOC
Social Evo.
Enron
UCI
nodes temporal links attributes for nodes & links
672,417
157474
& 411.49
18 1252335
2,099.200
1,89 59,835
172 & 172.
172 & 172.
0&
0
0&
&&
aeg. link stream intensity
x 10
1.27 10
4448
10-
6.50
10
4.98 10
10-
Table 1:
Summary of dataset statistics. Average link stream intensity is calculated by 2|E1/(V (T). where T is the total time range of all edges in unit of seconds, [V] and [B] are number of nodes and temporal links.
Encode W. Note that each walk is sequence of node-time pairs. If we encode each node-time pair and plug those pairs in sequence encoder, e.g., RNNs, obtain the encoding of W:
enc (W) = RNN(Lf1(///ww
@ f2(4-1 1,)) (,)==o.......)) where (-1 lu-
(5)
where f1, are two encoding function on ICAw( and f;-1 t respectively. One may use transformer networks instead of RNNs to encode the sequences but as the sequences in our case are not long (1 ~ 5). RNNs have achieved good enough performance. Now, we specify the two encoding functions S1 aw (w,)) and fe(4-11 - 4,) as follows. Recall the definition of ICAw (w;) (Eq
(WFCAw(w))) = (L w. Sw)) + (W,()) where two MLPs share parameters. (6)
Here the encoding of (cAw(w), adopts the sum- sum-pooling as the order of u. v is not relevant. For fe(t), we adopt random Fourier features to encode time (Xu et al. 2019 Kazemi al. 2019)) which may approach any positive definite kernels according to the Bochner's s theorem (Bochner 1992).
[2( [cos(wi))) sin(wn)), cos(wal), sin(wal)), where wj's are learnable parameters.
Encode S, U.S. After encoding each walk in S. U S.,, we aggregate all these walks to obtain the final representation enc(S, U.) for prediction. We suggest to use either mean-pon mean-pooling for algorithmic efficiency or eeff-attentoon (Vaswani al. (017) followed by mean-pooling further capture subtle interactions between different walks. Specifically, suppose (Winses2M are the 2M CAWs in S., S, and each ene(W;) E IRdx1, We set enc(S, S.)) as
Mean-AGG(S, U U.):::: 2M E enc(W..
Self-Att-AGGSS, U Sp):: 1 2M softmax (alimax(fenc(Wi (fene(W.)) (Qeeee/ where Q1, Q2 E Raxd are two learnable parameter matrices.
2M
We add 2-layer perceptron over enc(S, U S.)) to make the final link prediction.
4.4 EXTENSION AND DISCUSSION
Attributed nodes/links and directed links. In some real networks, nodes or links may have at- tributes available, e.g., the message content in the case of SMS networks. In this case, the walk in Eq can be associated with node/link attributes Xo, X1, ..., Xmm where X; refers to the attributes on link ((w;-1, w:)
44) or on the node w; concatenation of these two parts. Note that the direction of a link can also be viewed as binary link attribute, where 2-dimensional one-hot encoding can be used. To incorporate such information, we only need to change enc(W) (Eq 5 as
enc(W RNN( (Laww (w;) o fa(t-1 t,) @ Xe)i=o,,.....)) where t- to-
(8)
Since (I (w:)) is a strong signal, in practice is optional to use another RNN to encode its own dynamics. The derived encoding is then concatenated with enc to obtain the enhanced final encoding of W.
Efficient link sampling. compute and normalize the sampling probabilities of all links in Eup,t, which requires memorize all historical links and costs much time and memory. To solve this problem. we propose a sampling strategy (Appendix A) with expected time and memory complexity minf 2z + 1. Eu |} if links in Eng.,, come in by following a Poisson process with intensity r (Last & Penrose 2017 This means that our sampling strategy with a positive a allows the model only recording O ( recent links for each node instead of the entire history. Our experiments in S.c that that achieves the best prediction performance makes #5 in different datasets. Since the time and memory complexity do not increase with respect to the number of links, our model can be used for online training and inference. Note that the a = O case reduces to uniform sampling, mostly adopted by previous methods (Xu et al. 2020), which requires to record the entire history and thus not scalable.
naive implementation of the link sampling step 5 Alg to

---

Published as a conference paper at ICLR 2021
5 EXPERIMENTS
5.1 EXPERIMENTAL SETUP
CAW-N Variants. We test CAW-N-mean and CAW-N-attn which uses mean and attention pooling respectively to encode S. U U. (Sec. 4.3). Their code is provided in the supplement.
Baselines. Our method is compared with six previous state-of-the-ar baselines representation learning of temporal networks. They can be grouped into two categories based on their input data structure: (1) Snapshot-based methods, including DynAERNN (Goyal et al. 2020), VGRNN (Haji- 2019) and EvolveGCN (Pareja et al. 2020); (2) Stream- methods, including TGAT (Xu et al., 2020 JODIE (Kumar et al.) 2019 and DyRep (Trivedi al., 2019). We give
ramezanali et al.
For the snapshot- -baee methods, we view the link aggregation way to preprocess historical links. We adopt the aggregation ways suggested in their papers. These models are trained and evaluated over the same link sets as the stream- stream-based methods.
their detailed introduction in Appendix|C.22
Dataset. We use six real-world public datasets: Wikipedia is a network between wiki pages and human editors. Reddit is a network between posts and users on subreddits. MOOC is a network of students and online course content units. Social Evolution is a network recording the physical proximity between students. Enron is a email communication network. UCI is network between online posts made by students. We summarize their statistics in Tab and give their detailed description and access in Appendix C.I
Evaluation Tasks. Two types of tasks are for evaluation: transductive and inductive link prediction.
Transductive link prediction task allows temporal links between all nodes to be observed up to time point during the training phase, and uses all the remaining links after that time point for testing. In our implementation, we split the total time range [0, T] into three intervals: [0, Tirain), [T trains T Twat). (Tea,, 77. links occurring within each interval are dedicated to training, validation, and testing set, respectively. For all datasets, we fix =00.7, and T0..5/==0.85.
Inductive link prediction task predicts links associated with nodes that are not observed in the training set. There are two types of such links: 1) "old vs. new" links, which are links between an observed node and an unobserved node; 2) "new vs. new" links, which are links between two unobserved nodes. Since these two types of links suggest different types of inductiveness, we distinguish them by reporting their performance metrics separately. In practice, we follow two steps to split the data: 1) we use the same setting of the transductive task to first split the links chronologically into training/ validation / testing sets; 2) we randomly select 10% nodes, remove any links associated with them from the training set, and remove any links not associated with them in the validation and testing sets.
Following most baselines, we randomly sample an equal amount of negative links and consider link prediction as a binary classification problem. For fair comparison, we use the same evaluation procedures for all baselines, including the snapshot-based methods.
Training configuration. We use binary cross entropy loss and Adam optimizer to train all the models, and early stopping strategy to select the best epoch stop training. For hyperparameters, we primarily tune those that control the CAW sampling scheme including the number M, the length m of CAW's and the time decay a. We will investigate their sensitivity in Sec Sec5.3 For all baselines, we adapt their implemented models into our evaluation pipeline and extensively tune them. Detailed description of all models' tuning can be found in Appendix C Finally, we adopt two metrics to evaluate the models' performance: Area Under the ROC curve (AUC) and Average Precision (AP),
5.2 RESULTS AND DISCUSSION
We report AUC scores in Tab and report AP scores in Tab of Appendix D.I In the inductive setting and especially with "new vs new" links, our models significantly outperform all baselines on all datasets. On average, our best method improves over the strongest baseline by 14.46% (new vs. new) and 3.49% (old vs. new) in relative, or reduces the error (= 1 - AUC) by 69. 73% (new vs. new) and 58.63% (old new). Noticeably, out method achieves almost perfect AUCs on UCI's "new vs. new" edges, when all basclines' performance is below 0.8.
Even in transductive setting where the baselines claim their primary contribution, our approaches still significantly outperform them on five out of six datasets. Note that our models achieve almost perfect scores on Reddit and Wikpedia when the baselines are far from perfect. Meanwhile, the strongest baseline on these two attributed datasets, TGAT (Xu et al. 2020)) suffers a lot on all the other datasets where informative node / link attributes become unavailable.
7

---

one-hot encoding Published as a conference paper at ICLR 2021
Task
Methods
Reddit
Wikapedia
MOOC
Social Evo.
Enron
UCI
DynÄERNN
37,31 + 2.54
2.54
55.16 1.15
60.35 = 1.61
52.00 = 0.16
51.37 = 2.63
50.20
2.78
new new
JODIE
72.49 0.38
70.78
+ 0.25
80.04 = 0.28
87.66 - 0.121
73.99 = 2.54
64.77 0.75
DyRep
62.37 1.49
67.07 + 1.26
74.07
1.88
83.92 0.02
69.74 + 0.44
63.76
VGRNN
61.93 + 0.72
60.64 1: 0.68
63.01
+ 0.29
66,30 + 0.84
61.35 = 1.10
61.35
1.35+11.10 1.10
EvolveGCN
63.31 + 0.53
58.01 + 0.16
52.31
4.14
46.95 + 0.85
42.53 + 2.12
76.65 + 0.63
TGAT
94.96 0.881
93.53 + 0.841
70.10
0.35
53.27 + 1.16
63.34 +: 2.95
76.36 1.48
Inductive
CAW-N-mean
98.30 0
96.36 1: 0.48
90.29
0.82
93.81 + 0.69*
94.26 = 0.62"
99.62 +: 0.34"
CAW-N-attn
98.11 0.58
97.83 + 0.67
90.40 0.75
94.55 + 0.811
93.53
0.63
100.00 0.00
DyBÄERNN
58.79 3.01
57.97 2.38
80,99
1.35
$2.31
54.36
$2.26 1.36
JODIE
76.33 + 0.03
74.65 + 0.06
87.40
1.71
91.80 + 0.01
85.24 + 0.08
69.95 + 0.11
new old
DyRep
66,13 + 1.07
76.72 + 0.19
88.23
1.20'
87.98 + 0.45
94.39 + 0.32!
93.28 + 0.96
VGRNN
54.11
62.93 1: 0.69
60.10
0.88
64.66 + 0.41
68.71 +: 0.92
62.39 +: 1.08
EvolveGCN
65.61 0.37
56.29 +: 2.17
50,20
1.22
50.73 + 1.36
42.53 = 2.13
70.78 0.22
TGAT
97.25 +: 0.18
95.47 +: 0.17'
69.30 + 0.08
54.22 + 1.28
58.76 + 1.18
74.19 + 0.88
CAW-N-mean
99.88 + 0.04
98.94 + 0.05'
90.88 = 0.54
95.15 + 0.40
94.76 = 1.05"
99.04 + 0.34'
CAW-N-attn
99.93 0.03
+ 0.25
90.89
95.74 0.68
93.43
98.99 0.44
DynÄERNN
83,37 1.48
71.00 1 1.10
89.34
0.24
67.78 + 0.80
63.11 = 1.13
83,72 1: 1.79
JODIE
87.71 + 0.02
88.43 + 0.02
90.50 + 0.011
89.78 + 0.04
89.36 + 0.06
74.63 + 0.11
Transhifivve
DyRep
67.36 + 1.23
77.40 +: 0.13
90.49 0.03
90.85 + 0.011
96.71 + 0.041
95.23 + 0.25
VGRNN
51.89 0.92
71.20 +:
78.28 -:
89.43 0.27
EvolvveGCN
58.42 + 0.55
60.48 + 0.47
50.36 + 0.85
60.36 + 0.65
74.02 + 0.31
78.30 + 0.22
TGAT
96.65 + 0.06'
96,36 + 0.051
72.09 1 0.29
56.63 + 0.55
60.88 : 0.37
77.67 + 0.27
CAW-N-mean
99.97
0
0.04
94.12 0.15*
93.53
95.90 0.71
CAW-N-attn
99.98 0.01
99.89 + 0.03
92.38
0.58
94.79 + 0.16'
95.93 = 0.39
98.45 0.49
Table 2: Performance in AUC (mean in percentage + 95% confidence level.) t highlights the best baselines. ", bold font, bold font" respectively highlights the case where our models" performance exceeds the best baseline on average, by 70% confidence, by 95% confidence.
No.
Ablation
Wikipedia
UCI
Social Evo.
I.
original method (CAW-N-mean)
98.49 + 0.38
99.12 0.33
94.54 0.69
2.
remove (Il
96.28 + 0.66
79.45 0.71
$3.69 + 0.21
3.
remove fa(t)
97.99 + 0.13
95.00
0.42
71.93 2.32
4. remove (Ic ). f2(e)
88.94 + 0.85
50.01
0.02
50.00 + 0.00
5. replace fo Aw by one-hot([Aw)
96.55 + 0.21
85.59
+ 0.34
68.47 + 0.86
6. fix a
75.10 1 3.12
87.13
1: 0.49
78.01 1: 0.69
Table 3: Ablation study with CAW-N-mean. AUC scores all inductive test links are reported.
Comparing the two training settings, we observe that the performance of four baselines (JODIE, VGRNN, DynAERNN,DyRey. drop significantly when transiting from the transductive setting the inductive one, as they mostly record node identities either explicitly (JODIE, VGRNN, DynAERNN or implicitly (DyRep). TGAT and EvolveGCN do not use node identities and thus their performance gaps between the two settings are small, while they sometimes do not perform well in the transductive setting, as they encounter the ambiguity issue in Fig. 3 contrast, our methods perform well in both the transductive and inductive settings. We attribute this superiority to the anonymization procedure: the set-based relative node identities well capture the correlation between walks to make good prediction while removing the original node identities to keep entirely inductive. Even when the network structures greatly change and new nodes come in as long as the network evolves according to the same law as the network used for training. CAW-N will always work. Comparing CAW-N-mert mean and CAW-N-attn, we see that our attention- variant outperforms the mean-pooling variant, albeit at the cost of high computation complexity. Also note that the strongest baselines all datasets are stream- based methods, which indicates that the aggregation of links into network snapshots may remove some useful time information (see more discussion in Appendix D.2).
We further conduct ablation studies on Wikipedia (attributed), UCI (non- aot--tttrib,,ed), and Social Evolution (non-attributed), to validate effectiveness of critical components of our model. Tab. 3 shows the results. By comparing Ab. 1 with Ab.2, 3 and respectively, we observe that our proposed node anonymization and encoding, (i ). contributes most to the performance, though the time encoding ft( also helps. Comparing performance across different datasets, we see that the impact of ablation is more prominent when informative node/link attributes are unavailable such with UCI and Social Evolution. Therefore, in such scenarios our CAWs are highly crucial. In Ab.5, we replace our proposed ICAW with Law (Eq[), which is used in standard AWs, and of node new identities I Law- We see by comparing Ab. 1, 2, and 5 that such anonymization process is significantly less effective than our ICAW, though it helps to some extent. Finally, Ab.6 suggests that entirely uniform sampling of the history may hurt performance.
8

---

Published as a conference paper at ICLR 2021
UCT
Wikkipddn
(a)
(b)
(c)
1.00
1.00
0.55
0.99
0.98
0.90
0.94
0.02
0.85
0.85
0.86
0.75
10"
1/s
CAW sampling number
CAW sampling time blas
CAW sampling length
Figure 5: Hyperparameter sensitivity in CAW sampling. AUC on all inductive test links are reported.
(b)
660)
500
500
210
100
8 [4]
18
12
14
16
6
10
12
14
16
X30
14
Figure 6: Complexity evaluation: The accumulated runtime of (a) temporal random walk extraction (Alg) | and (b) the entire CAW-N training, timed over one epuch on Wikipedia (using different [E] for training).
5.3 HYPERPARAMETER INVESTIGATION OF CAW SAMPLING
We systematically analyze the effect of hyperparameters used in CAW sampling schemes, including sampling number M, temporal decay coefficient and walk length m. The experiments are conducted on UCI and Wikipedia datasets using CAW-N-mean When investigating each hyperparameter, we set the rest two to an optimal value found by grid search, and report the mean AUC performance on all inductive test links (i.e. old vs. new, new vs. new) and their 95% confidence intervals.
The results are summarized in Fig From (a), we observe that only small number of sampled CAWs are needed to achieve a competitive performance. Meanwhile, the performance gain is saturated as the sampling number increases. We analyze the temporal decay a (b): a usually has an optimal interval, whose values and length also vary with different datasets to capture the different levels of temporal dynamics; a small a suggests an almost uniform sampling
interaction history, which hurts the performance; an overly large a also damages the model, since it makes the model only sample the most recent few interactions for computation and blind to the rest. Based on our efficient sampling strategy 4,4, may combine the optimal with the average link intensity (Tab[]. and concludes that CAW-N only needs to online record and sample from about a constant times about 5 (z 2) most recent links for each node. Plot (c) suggests that the performance may peak at certain CAW length, while the exact value may vary with datasets. Longer CAWs indicate that the corresponding networks evolve according to more complicated laws encoded in higher-order motif'.
5.4 COMPLEXITY EVALUATION
We examine how the runtime of CAW-N depends on the number of edges |8| used for training. We record the rumtimes of CAW-N for training one epoch on the Wikipedia datasets using M = 32, m =
with 3atch-size=32. Specifics of the computing infrastructure are given in Appendix C.5 Fig.
(a) shows the accumulated runtime of executing the random walk extraction iee. Alg I Tonly. It well aligns with our theoretical analysis (Thm. A.2) that each step of the random walk extraction has constant complexity (i.e. accumulated runtime linear with El). Plot (b) shows the entire runtime for one-epoch training, which is also linear with (g). Note that O((E)) is the time complexity that one at least needs to pay. The study demonstrates our method is scalable to long edge streams.
CONCLUSION
We proposed CAW-N to inductively represent the dynamics of temporal networks. CAW-N uses CAWs to implicitly extract network motifs via temporal random walks and adopts novel set- bat-based anonymization to establish the correlation between network motifs. The success of CAW-N points out many promising future research directions on temporal networks: Pairing CAW-N with neural network interpretation techniques (Montavon et al. 2018)) may give a chance to automatically discover larger and meaningful motifs/patterns of temporal networks; CAW-N may also be generalized to predict high-order structures (e.g., triangles) that correspond to some function units of temporal networks from different domains (Benson al. 2016 2018 Zitnik et al. 2019).

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGMENTS
We thank Jiaxuan You and Rex Ying for their helpful discussion on the idea of Causal Anonymous Walks. We also thank Rok Sosič, Camilo Andres Ruiz and Maria Brbić for providing insightful feedback on the abstract. We also gratefully acknowledge the support of DARPA under Nos. (4865018C7880 (ASED), N660011924033 (MCS); ARO under Nos. W91 19911N1-1-1-11 16-14----332 (MURI), 1911NNF16-1-017 (DURIP); NSF under Nos. OAC-1835599 (CINES), OAC-1934578 (HDR), CCF-1918940 (Expeditions), IIS-2030477 (RAPID); Stanford Data Science Initiative, Wu Tsai Neurosciences Institute, Chan Zuckerberg Biohub, Amazon, Bocing, JPMorgan Chase, Docomo, Hitachi, JD.com, KDDI, NVIDIA, Dell. J. L. is Chan Zuckerberg Biohub investigator.
REFERENCES
Ghadeer AbuOda, Gianmarco De Francisci Morales, and Ashraf Aboulnaga. Link prediction via higher-order motif features. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2019.
Nesreen K Ahmed, Jennifer Neville, Ryan Rossi, and Nick Duffield. Efficient graphlet counting for large networks. In International Conference on Data Mining. IEEE, 2015.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-Gonzalez. Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01223 2018.
Austin Benson, David Gleich, and Jure Leskovec. Higher-order organizztion of complex networks. Science, 353(6295), 2016.
Austin R Benson, Rediet Abebe, Michael Schaub, Ali Jadbabaie, and Jon Kleinberg. Simplicial closure and higher-order link prediction. Proceedings of the National Academy of Sciences, 115 (48):E11221-P))) 1230, 2018.
Salomon Bochner. A theorem on Fourier-Stieltjes integrals. Collected Papers of Salomon Bochner, 2, 1992.
Jinyin Chen, Jian Zhang, Xuanheng Xu, Chenbo Fu, Dan Zhang, Qingpeng Zhang, and Qi Xuan. E-Istm-d: A deep learning framework for dynamic network link prediction. IEEE Transactions on Systems, Man, and Cyberneties: Systems, 2019.
Lun Du, Yun Wang, Guojie Song. Zhicong Lu, and Junshan Wang. Dynamic network embedding: An extended approach for skip-gram based network embedding. In International Joint Conference on Artificial Intelligence, 2018
Thomas E Gorochowski, Claire Grierson, and Mario di Bernardo. Organization of feed-forward loop motifs reveals architectural principles in natural and engineered networks. Science advances, 4(3), 2018.
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Bonl Based Systems, 187, 2020.
Mark S Granovetter. The strength of weak ties. American journal of sociology, 78(6), 1973.
Ehsan Hajiramezanali, Arman Hasanzadeh, Krishna Narayanan, Nick Duffield, Mingyuan Zhou, and Xiaoning Qian. Variational graph recurrent neural networks. In Advances in Neural Information Processing Systems, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, 2017a.
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. IEEE Data Engineering Bulletin, 40(3), 2017b.
Petter Holme and Jari Saramäki. Temporal networks. Physics reports, 519(3), 2012.
10

---

Published as a conference paper at ICLR 2021
Sergey Ivanov and Evgeny Burnaev. Anonymous walk embeddings. In International Conference Machine Learning, 2018.
Seyed Mehran Kazemi, Rishab Goel, Sepehr Eghbali, Janahan Ramanan, Jaspreet Sahota, Sanjay Thakur, Stella Wu, Cathal Smyth, Pascal Poupart, and Marcus Brubaker. Time2vec: Learning a vector representation of time. arXiv preprint arXiv: 2019.
Thomas Kipf and Max Welling. Variational graph auto-encoders. arXiv preprint arXiv: 2016.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017.
Lauri Kovanen, Márton Karsai, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motif's in dime-dependent networks. Journal of Statistical Mechanics: Theory and Experiment, 201 1(11), 2011.
Lauri Kovanen, Kimmo Kaski, János Kertész, and Jari Saramäki. Temporal motifs reveal homophily, gender-specific patterns, and group talk in call sequences. Proceedings of the National Academy of Sciences, 110(45), 2013.
Srijan Kumar, Xikun Zhang, and Jure Leskovec. Predicting dynamic embedding trajectory in temporal interaction networks. In International Conference on Knowledge Discovery Data Mining, 2019.
Mayank Lahiri and Tanya Y Berger- Wolf. Structure prediction in temporal networks using frequent subgraphs. In IEEE Symposium on Computational Intelligence and Data Mining, 2007.
Günter Last and Mathew Penrose. Lectures on the Poisson process, volume 7. Cambridge University Press, 2017.
Stephen Lavenberg. Computer performance modeling handbook. Elsevier, 1983.
Pan Li and Olgica Milenkovic. Inhomogeneous hypergraph clustering with applications. In Advances in Neural Information Processing Systems, 2017.
Taisong Li, Jiawei Zhang, S Yu Philip, Yan Zhang, and Yonghong Yan. Deep dynamic network embedding for link prediction. IEEE Access, 6, 2018.
Sedigheh Mahdavi, Shima Khoshraftar, and Aijun An. dynnode2vec: Scalable dynamic network embedding. In International Conference on Big Data (Big Data). IEEE, 2018.
Franco Manessi, Alessandro Rozza, and Mario Manzo. Dynamic graph convolutional networks. Pattern Recognition, 97, 2020.
Shmoolik Mangan and Uri Alon. Structure and function of the ford-forward loop network motif. Proceedings of the National Academy of Sciences, 100(21), 2003.
Silvio Micali and Zeyuan Allen Zhu. Reconstructing markov processes from independent and anonymous experiments. Discrete Applied Mathematics, 200, 2016.
Grégoire Montavon, Wojeiech Samek, and Klaus-Robert Müller. Methods for interpreting and understanding deep neural networks. Digital Signal Processing. 73:1-15, 2018
Giang Hoang Nguyen, John Boaz Lee, Ryan A Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous-tine dynamic network embeddings. In Companion Proceedings of the The Web Conference, 2018
Ashwin Paranjape, Austin R Benson, and Jure Leskovee. Motifs in temporal networks. In Interna- fional Conference on Web Search and Data Mining, 2017.
Aldo Pareja, Giacomo Domeniconi, Jie Chen, Tengfei Ma, Toyotaro Suzumura, Hiroki Kanezashi, Tim Kaler, Tao B Schardl, and Charles E Leiserson. EvolveGCN: Evolving graph convolutional networks for dynamic graphs. In AAAI Conference Artificial Intelligence, 2020.

---

Published as a conference paper at ICLR 2021
Mahmudur Rahman and Mohammad Al Hasan. Link prediction in dynamic networks using graphlet. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases. Springer, 2016.
Ryan A Rossi, Anup Rao, Sungchul Kim, Eunyee Koh, Nesreen K Ahmed, and Gang Wu. Higher- order ranking and link prediction: From closing triangles to closing higher-order motifs. arXiv preprint 14Kv::9906000555 2019.
David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. Learning representations by back-propagating errors. nature, 323(6088), 1986.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. DySAT: Deep neural representation learning on dynamic graphs via self-attention networks. International Conference Web Search and Data Mining, 2020.
Pumnarrita Sarkar, Deepayan Chakrabarti, and Michael I Jordan. Nonparametric link prediction in dynamic networks. In International Conference on Machine Learning. 2012.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 2008
Georg Simmel. The sociology of georg simmel, volume 92892. Simon and Schuster, 1950.
Uriel Singer, Ido Guy, and Kira Radinsky. Node embedding over temporal graphs. In International Joint Conference on Artificial Intelligence, 2019.
Balasubramaniam Srinivasan and Bruno Ribeiro. On the equivalence between positional node embeddings and structural graph representations. In International Conference on Learning Repre- sentations, 2019.
Ritta Toivonen, Jussi Kumpula, Jari Saramäki. lukka-Pekka Onnela, János Kertész, and Kimmo Kaski. The role of edge weights in social networks: modelling structure and dynamics. In Noise and Stochastics in Complex Systems and Finance, volume 6601. International Society for Optics and Photonics, 2007.
Rakshit Trivedi, Hanjun Dai, Yichen Wang, and Le Song. Know-evolve: deep temporal reasoning for dynamic knowledge graphs. In International Conference on Machine Learning, 2017.
Rakshit Trivedi, Mehrdad Farajtabar, Prasenjeet Biswal, and Hongyuan Zha. Dyrep: Learning representations over dynamic graphs. In International Conference on Learning Representation, 2019.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in Neural Information Processing Systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Yanbang Wang, Pan Li, Chongyang Bai, VS Subrahmanian, and Jure Leskovec. Generic representa- tion learning for dynamic social interaction. International Conference on Knowledge Discovery Data Mining, MLG workshop, 2020.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Self-attention with functional time representation learning. In Advances in Neural Information Processing Systems, 2019.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive repre- sentation learning temporal graphs. In International Conference Learning Representation. 2020.
Muhan Zhang, Pan Li, Yinglong Xia. Kai Wang, and Long Jin. Revisiting graph neural networks for link prediction. arXiv preprint arXiv:2010. 16103, 2020.
12

---

Published as a conference paper at ICLR 2021
Le-kui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In AAAI Conference on Artificial Intelligence, 2018
Marinka Zitnik, Marcus W Feldman, Jure Leskovec, et al. Evolution of resilience in protein interactomes across the of life. Proceedings of the National Academy of Sciences, 116(10), 2019.
13

---

Published as a conference paper at ICLR 2021
A EFFICIENT LINK SAMPLING
Our efficient link sampling strategy contains two subroutines - Online probability computation (Alg and Iterative sampling (). The Online probability computation subroutine Alg essentially works online to assign each new incoming link (fu,v), v}, with a pair of probabilities {a Po,s) such that
2
exp(al)
exp(al)
Pu,t (e. exp(ot"))
Pu,t Le, exp(ot')
These probabilities will be used later in sampling (Alg 3 and do not need to be updated any more.
Algorithm 2: Online probability computation (G, a))
Initialize V 5-0, Q 0: for (fu, vu, t) & do
for w E {u, /) do
if V then
+ V fww: P.. exp(al);
else
Find P E Ω2 P t Pw exp(at);
Pw,t + exp(at),
10
P Ω - Ω U P
11
Assign two probability scores: ([(u, Pu.e, Po,)))tt. + (fu, t)
12
The Iterative sampling subroutine Alg is an efficient implementation of step 5 in Alg 1 We may first show that the sampling probability of a link (e, t) in Eup,,, is proportional to exp(a(t - tp)) in Prople A.1
Algorithm 3: Iterative Sampling (E, a, ap. Up:
Initialize V <- Q 0:
for te, E Ewy.t, with an decreasing order of do
Sample a ~ Unif(U. 1]:
Pup. is the score of this link related up obtained from Alg
a < Pu,.t then
L Return (e, L);
Return (Ltop X},x)):
Proposition A.1. Based on the probabilities (Eq 9 pre-computed by Alg 2 Alg will sample a link (e, t) in Ewg,,, with probability proportional exp(a(t tp)).
Proof. To show this, first order the timestamps of links in Eng, between (t,tp) as < I/2 <... lp where there exists an link (e', (()) Empit, for G. Then, the probability sample link (e, t) E Eug, satisfies
II Pupptt)
p = Pu,,
Elernee exp(al!)
exp(at)
Σ Eie, (1)EE)) exp (att)
Eie exp(at))
exp(at)
exp(alt - tp))
Eiereeeeeep exp (all)
Elet (e) exp (a(l' (7))
14

---

Published as a conference paper at ICLR 2021
which is exactly the probability that we need.
We have the following Thm A.2 with a weak assumption that evaluates the complexity of Alg We assume that links come in by following a Poisson point process with intensity т, which a frequently used assumption to model communication networks (Lavenberg 1983). This result indicates that if a 0, for each node, we only need to record the most recent O links to sample. This result is important as it means our method can do online training and inference with time and memory complexity that are not related to the total number of links.
Theorem A.2. If the links that are connected to wp appear by following Poisson point process with intensity Then, the expected number of iterations of Alg.3 is bounded by min ( + 1, ( (.)
Proof. The number of iterations of Alg is always bounded by [Ew,,tyl: So we only need to prove that the expected number of interactions of Alg 3 is bounded by 2r
a + 1.
To show this, we order the timestamps of links in Empity between (0,tp) as 0 = to < < t2 < < t& < tp where there exists an link (e,t4) E Eup.t, for ty. Further define we define Z, = exp(a(t; - 14=1)) for i [1.
Due to the definition of Poisson process, we know that each time difference in {t: f hsisk follows i.i.d. exponential distribution with parameter т. Therefore, (Zi)isiss are also i.i.d.. Let a = B(2 ) a+r
The probability that Alg 3 = gets sampled. That is
runs j iterations is equal to the probability that the link with timestamp
h+1-$ Zi k+1
P(iter 5)
2,
i=
Therefore, the expected number of iterations is
k E(iter) = j=
Σ
1-3 Z,
jE
(10)
h=
h Z
j=1
Z
where 2/= = ==ZZ+ 2-1-- and IT Z = 1. Next we will prove that each item in righh-hhnd-side of Eg
10
satisfies
z
jTE
1 - 1)(1 +3)-
(11)
プ 2
If this is true, then
k
k
k
E(iter)
1 (j 1)(1 -10
Σ j=1
2o
+ > (j 1)(1 - +-
j=1
j=1
1b
2T
+1.
1
1
Now, let us prove Eq
11
For j = 1, Eq
is trivial. For j > 1,
Z
Z
B(Z)
2o
E
< E
1+
Z
1+ 1+ -4=
E(Z))
Σ
(12)
where the second inequality is due to the Jensen's inequality and the fact that for any positive C1 C2. x is concave with respect to r.. Moreover, we also have
[ + (j - 1)(1
(j 1) 2 j.
(13)
Combining Eq 12 and Eq
13 we prove Eq 11 which concludes the proof.
15

---

Published as a conference paper at ICLR 2021
B TREE-STRUCTURED SAMPLING
We may further decrease the sampling complexity by revising Alg. intt tree-structured sampling. Alg. [ originally requires to sample link M m times because we need search M links that connected to wi in the first step and then sample one link for each of the M nodes in each following step. A tree-structured sampling strategy may reduce this number: Specifically,
sample k; links for each node in step i but we make sure I k = M, which does not change the total number of walks. In this way, the times of link search decrease to Di= by kg. Suppose M = 64, m = 3, and A1 4, l2 4, 43 4, then the times of link search decrease about 0.44M m Though empirical results below show that tree-structured sampling achieves slightly worse performance, it provides an opportunity tradeoff between prediction performance and time complexity.
1.00
0.95
0.90
0.85
0.80
UCI
0.75
Wikipedia
2
2
2
2
K1
Figure 7: Effect of sampling of different tree structures inductive performance.
We conduct experiment to investigate this topic with Wikipedia and UCI datasets. The setup is as follows: first, we fix CAW sampling number M = 64 = 2 and length m = 2, so that we always have k 62 = M 26; next, we assign different values to k1, that the shape of the accordingly; controlling other hyperparameters to be the optimal combination found by grid search, we plot the corresponding inductive AUC scores of CAW-N-meat on all testing edges in Fig. 7 is observed that while tree-structured sampling may affect the performance to some extent, its negative impact is less prominent when the first-step sampling number ki relatively large, and our model still achieves state-of-the-ar performance compared to our baselines. That makes the tree-structured sampling a reasonable strategy that can further reduce time complexity.
changes
C ADDITIONAL EXPERIMENTAL SETUP DETAILS
C.I DATASET INTRODUCTION AND ACCESS
We list the introduction of the six datasets as follows.
Reddi is dataset of posts made by users on subredditts over month. Its nodes are users and posts, and its links are the timestamped posting requests.
Wikipedid is a dataset of edits over wiki pages over month, whose nodes represent human editors and wiki pages and whose links represent timestamped edits.
Social Evolutior is a dataset recording the detailed evolving physical proximity between students in dormitory devices.
year, deterimined from wireless signals of their mobile
Enror is a communication network whose links are email communication between core employees of a cooperation over several years.
UcT] is a dataset recording online posts made by university students on forum, but is non-attributed.
MOOdS is a dataset online courses where nodes represent students and course content units such videos and problem sets, and links represent student's access behavior to particular unit.
http:
/
htte://mmg.ssarforreeee////////p
16

---

Published as a conference paper at ICLR 2021
C.2 BASELINES, IMPLEMENTATION AND TRAINING DETAILS
C.2.1 CAW-N-MEAN AND CAW-N-ATTN
We first report the general training hyperparameters of our models in addition to those mentioned in the main text: on all datasets, we train both variants with mini-batch size 32 and set learning rate 1.0 X 10TH 10; the maximum training epoch number is 50 though in practice we observe that with early stopping we usually find the optimal epoch in fewer than 10 epochs: our early stopping strategy is that if the validation performance does not increase for more than 3 epoch then we stop and use the third previous epoch for testing: dropout layers with dropout probability = 0.1 are added to the RNN module, the MLP modules, and the self-attention pooling layer. Please refer to our code for more details.
In terms of the three hyperparameters controlling CAW sampling, discussed them in Sec 5.3 For all datasets, they are systematically tuned with grid search, whose ranges are reported in Tab
Dataset
Sampling number M
Time decay a
Walk length m
Reddit
32, 64, 128
(0.25, 0.5, 1.0, 2.0, x.0]x100* x100
1, 3, 3, 4 2,3,4
Wikipedia
32, 64, 128
(0.25, 0.5, 1.0, 2.0, 4.0) x000=
MOOC
32, 64, 128
(0.25, 0.5, 1.0, 2.0, 4.0) x10
2,3.4.
Social Evo.
32, 64, 128
[0.25, 0.5, 1.0, 2.0, 4.0, 8.0)x10 (0.25, 0.5, 1.0, 2.0, 4.00 [0.6, 0.8, 1.0, 1.2, 114)
1,2,3
Enron
32, 64, 128
1,2,3,4
UCT
32, 64, 128
1,2,3
Table 4: Hyperparameter search range of CAW sampling.
Apart from the hyperparameters controlling CAW sampling, hidden dimensions of CAW-N mentioned in Sec 4.3 including that of the various encodings, MI.Ps, RNN, and attention projection matrices, are relatively less tuned. We select them based on two principles: 1) when node & link attributes are available, dimension of all these modules are set to have the same dimensions as baselines; 2) when node & link attributes are unavailable, the dimensions are picked from 32, 64, 128, whichever leads to better performance.
C.2.2 BASELINES
We list the introduction of the six baselines as follows:
2020 uses fully connected encoder to acquire network repre- sentations, passes them into LSTM and uses a fully connected network to decode the future network structures.
DynAERNN (Goyal al.
2019) applies RNNs to estimate the future embedding of nodes. The model was proposed for bipartite graphs while we properly modify it for standard graphs the input graphs non-bipartite.
JODIE (umarr et al.
DyRep (Trivedi et al., 2019) also uses RNNs to learn node embedding while its loss function is built upon temporal point process.
VGRNN (Hajiramezanalii et al.) 2019) generalizes the variational GAE (Kipf & Welling (2016) to temporal graphs, which makes the prior depend on the historical dynamics and captures those dynamics with RNNs.
EvolveGCN (Pareja al. 2020 uses RNN estimate the GCN parameters for the future snapshots.
TGAT (Xu et al. 2020) leverages GAT to extract node representations where the nodes" neighbors sampled from the history and encodes temporal information via Eq 7
We introduce how we tune these baselines as follows.
DynAERNN. The model with code provided here is adapted into our evaluation pipeline. We follow most of the settings in the code. We tune the embedding size in (32, 64) and lookback in (2, 3, 5 to report the best performance.
17

---

Published as a conference paper at ICLR 2021
JODIE, The model with code provided here adapted into evaluation pipeline. JODIE calculates the Ly distances between the predicted item embedding to other items and uses the rankings to evaluate their performance. Here, consider the negative distances the prediction score. Based on the prediction score, we calculate mAP and AUC. We split the data according to the setting in section [.1] The model is trained for 50 epoches. The dimensions of the dynamic embedding is searched in,4,, 128) ) and the best performance is reported.
DyRep. The model with code provided here is adapted into our evaluation pipeline. We follow most of the settings in the paper. That is, we set the number of samples for survival to 5, gradient clipping to 100. And we tune the hidden unit size and embedding size in [32, 64) to report the best performance. The model uses likelihood based on point process to predict links and therefore we use these likelihood scores compute AUC and AP.
VGRNN, The model with code provided here is adapted into our evaluation pipeline. We use several of its default settings: one-hot node features input when node attributes are unavailable as suggested by the original paper (Hajiramezanali et al. 2019), one layer of GRU network as the history tracking backbone, a learning rate of 1e-2, and training for 1000 epochs. Its hidden dimension is searched in (32, 64) and the best performance is reported.
The model with code provided here is adapted into evaluation pipeline. We utilize EvolveGCN-O version since it can capture more graph structural information. For most hyperparameters, we follow the default values. According to setting, we sample an equal amount of negative links, which means we set negative mult training and negative mult test to I. One central hyperparameter needs to be further tuned is number of previous snapshots used for training and testing. We search its optimal value in (3, 4, 6, 8, 10) when tuning the model for most datasets. Since Enron only contains 11 snapshots, search its optimal value in (3,4,5.6).
EvolveGCN.
TGAT.
The model with code provided here adapted into our evaluation pipeline. We use several of their default settings. That is, we use product attention, set the number of attention heads to 2, set the number of graph attention layers to 2, and use 100 as their default hidden dimension. One central hyperparameter that needs to be further tuned is the degree of their neighbor sampling. We search its optimal value in { [10, 20, 30) when tuning the model.
C.3 EVALUATION OF SNAPSHOT-BASED BASELINES
Reddit
Wikipedia
MOOC
Social Evo.
Enron
UCI
total snapshots
174
20
20
27
11
88
cxact split
122 26 /
14/3/3
14/3/3
1
7/2/2 VGRNN
62 / EvolveGCN
referenced bascline
EvolveGCN
VGRNN
Table Snapshot split for evaluating snapshot- based baselines.
We make the following decisions to evaluate snapshot-based baselines a fair manner, so that their performances are comparable to those derived from the stream-based evaluation procedure. The first step we do is to evenly split the whole dataset chronologically into a number of snapshots. We determine the exact number of snapshots by referring the three snapshot-based baselines we use. For Wikipedia and MOOC dataset which are not used by any snapshot-bas based baseline, we split them into a total of 20 snapshots. Next, we need to determine the proportions of these snapshots assigned each to training, validation, and testing set. In doing this, our principle is that the proportions of these three sets should be close to 70: 15:15 as much as possible, since that ratio what we use for evaluating stream-based baselines and our proposed method. These decisions lead to our final splitting scheme summarized in Tab.
Extra care should also be taken when testing snapshot-based methods. For queried link in snapshot, usually snapshot- baase methods only make a binary prediction whether or not that link may exist at any time in that snapshot. They do not, however, take care of the case that the link may appear multiple times at different time points within that snapshot's 's time range. This lead to different evaluation scheme than stream-based methods, which do consider the multiplicity of links. Therefore,
18

---

Published as a conference paper at ICLR 2021
when testing snapshot-based methods, if link appear in certain snapshot for multiple times, record the model's prediction the same number of times before computing its performance metrics.
C.4 CHOICE OF EVALUATION METRIC
When considering link prediction as a binary classification problem, the existing literature usually choose metrics from the following: Area Under the ROC Curve (AUC), Average Precision (AP), and Accuracy (ACC). The reason we do not use ACC is that a proper confidence threshold of decision is ill-defined in literature, which leads to unfair comparison across different works.
C.5 COMPUTING INFRASTRUCTURE
All the experiments were carried out Ubuntu 16.04 server with Xeon Gold 6148 2.4 GHz 40-core CPU, Nvidia 2080 RTX 11GB GPU, and 768 GB memory.
D ADDITIONAL EXPERIMENTAL RESULTS
D.1 PERFORMANCE IN AVERAGE PRECISION
Wikipedia
DynÄERNN
58.63 5.42
54,94 + 2.29
59.84 1,26
54.76 1.33
54.89
3.79
3.92
Dew V.S. new
JODIE
80.03 0.13
76.90 + 0.49
82.27 0.46
87.96
0.12
79.80 = 1.48
71.64
DyRep
61.28 - 1.89
57.57 +: 2.56
62.29 2.09
75.42
0.32
69.97 = 0.92
63.08 -
VGRNN
5 0.66
0.82
67.83 0.53
0
0.950
EvolveGCN
0.19
55.64 1.03
S2.28 1.80
52.26 + 1.16
47.36
1.24
80.98 + 1.09
TGAT
95.17
93.18 + 0.73
72.91
2..1
52.17 1.94
63.83 + 3.70
75.27 2.34
Inductive
CAW-N-mean
98.05 0.87
96.01 + 0.25'
0.80 90.36
92.16 + 1.03
93,93
0.66'
99.63 - 0.34
CAW-N-attn
98.08 0.66
97.86 + 0.63
90.35
0.81
93.29
1.90
92.73
0.76
100.00 0.00
DynÄERNN
66.59 1 2.90
63.76 1: 2.82
82.02 1.59
52.54 1 0.22
55.50 2 2.07
$7.29 1 2.52
JODIE
83.15 + 0.03
80.54 + 0.06
87.95 0.08
91.40 + 0.041
89.57
0.30
76.34 + 0.17
v.S. old
DyRep
66.73
89,41
0.281
93.60 1.47
VGRNN
52.84 0.66
60.99 1: 0.55
62,95 0.58
69.20 + 0.52
67.93 = 0.88
67.50 +: 0.92
EvolveGCN
66.29 + 0.52
53.82 + 1.64
51.53
0.92
$2.01 + 0.67
46.56
1.89
76.30 + 0.33
TGAT
97.09 - 0.18
95.17 + 0.151
71.77
0.23
$2.48 + 0.52
59.70 =
75.01 0.72
CAW-N-mean
98.89 0.04
99.04 1: 0.14"
0.96 90.99
93.71 + 0.75*
92.93
0.94
98.86 0.95*
CAW-N-attn
99.90 + 0.05
99.55 : 0,30
0.93 91.24
94.17 + 0.86'
92.38 = 1.36
98,53 + 0.64
DynÄERNN
85,58 2.12
76.38
0.49 89.29
66.38 = 1.84
60.90 = 2.70
84,95 2.13
Transfuctive
80.27
DyRep
67.54 + 2.02
77.36 0.25
90.49 0.03
94.48 0.01
97.14 0.071
95.29 0.13
VGRNN
50.87 0.81
67.66 0.89
83.70 0.56
78.66 - 0.67
94.02 0.52
82.23 - 0.56
EvolveGiCN
0.46
56,90
81.63 0.23
TGAT
98.38
0.01
96.65 + 0.061
69.75
0.23
57.37
1.18
57.37 0.18
60.25 0.31
CAW-N-mean
99.96 + 0.01
99.91
+: 0
92.05
0.88
95.90 + 0.09*
94.93 #: 0.39
95.89 0.87
CAW-N-attn
99.99
0.01
99.89 + 0.03'
92.23
0.76
96.37
+ 0.09
96.13 + 0.37
98.86 0.38
Table 6: Performance in Average Precision (AP) (mean in percentage + 95% confidence level.) t highlights the best baselines. * bold font, bold font" respectively highlights the case where our models' performance exceeds the best baseline on average, by 70% confidence, by 95% confidence.
D.2 MORE DISCUSSION ON STREAM-BASER VS. SNAPSHOT-BASER METHODS
Stream-based methods usually treat each temporal link as individual training instance. In contrast, snapshot-based methods stack all the temporal links within a time slice into one static graph snapshot and do not further distinguish temporal order of links within that snapshot. In Tab. 2 and wee saw that stream- based methods generally exhibit better performance than inaphoot-basee methods. An important reason that stream-based methods are able to access the few most recent interactions previous to the target link to predict. This makes them especially advantageous when used to model many common temporal networks whose dynamics are governed by some short-term laws. In contrast, snapshot-based methods are less able to access such immediate history, because they make prediction on all links within one future snapshot all at once. In principle they could alleviate this problem by making very ine-grained snapshots that less immediate history is missed. However, this is not practical with real-word large temporal graphs whose temporal links come in millions, which leads to snapshot sequences of extreme length intractable to their recurrent neural structure. This issue was
19

---

Published as a conference paper at ICLR 2021
occurence ratio with posttive links occurence ratio with negaiive links
1.0
0.8
0.6
Scaw (W)
Top 3 highest-scored CAWs
Top 3 lowest-scored CAWs
(0, c0) - (1,2) - (2.3) (1,2)
(0,00 - (1, - (2) - (3,00)
(0, (1,2) - (2.1) (1,
(0,00 (1, - (2) (0)
(0, - (1,2) - (2.3) (3.2)
(0, - (1, - 12 - (3,
Figure 8: Visualizing most discriminatory CAWs, and their occurrence ratios with positive / negative samples.
also observed by the recent work to model social interacting behaviors (Wang al. 2020), although temporal convolutional networks may alleviate this issue to some extent. That said, snapshot- based methods usually has the advantage that they usually consume less memory and computation time. strcam-based methods on the other hand need to manage how they sample history very carefully to balance the efficiency and effectiveness. Our proposed algorithm on CAW sampling comes into the place in light of this to solve the problem.
E VISUALIZING CAWS AND AWS
Here, we introduce one way to visualize and interpret CAWs. Our interpretation can also illustrate the importance to capture the correlation between walks to represent the dynamics of temporal networks, where the set-based anonymization of CAWs can work while AWs will fail. The basic idea of our intrepretation is to identify different shapes of CAWs via their patterns encoded in ICAW, and compare their contributions to the link naneprrdiction confidence. The idea will be also used interpret AWs so that we can compare CAWs with AWs.
First, we define the shapes of walks based on ICAw. Recall from Eq. 3 that g(w, S.)) encodes the number of times node w that appears in different walk positions w.r.t source node u. This encoding induces a temporal shortest-path distance d between node w and u: duw- & min S0,,,,,,, S,) 0}. Note that temporal networks, there is not a canonical way to define shortest-path distance between two nodes as there is no static structures. So our definition duo can be viewed the shortest- path distance between u and w over the subgraph that consists of walks in Su. Based on the way to define (duw, ),w), we introduce the mapping from ICAw of the node the subgraph that consists of walks in S. n,S (g(w, gWn, S.)) -> coor(w; (w; u, v) = (duar d ) This cooredinate can be viewed as relative coordinate of node w.r.t. the source nodes walk W E S, U S. can then represented as a sequence of such coordinates by mapping each node's IaAW to coordinate. The obtained sequence can be viewed obtained shape as sc Aw (W). For instance, in the toy example shown by Fig. 2 right, the first CAW in Su, + a + c is mapped a new coordinate sequence (0, + (1, 2) - (2, + o0). The Do marks the setting that node a, c do not appear in S..
coordinate of this node in
Each
shape of W and we denote the
Next, we score the contributions of CAWs with different shapes. We use CAW-N-Mean as enc(S, S.) is simply mean over the encodings of sampled CAWs and further use linear pro- jection ST enc(S, U...) to compute the final scalar logit for prediction. As the two operations mean and projection are commutative, the above setting allows each CAW W, contributing a scalar score lo, = enc(W,) to the final logit.
Fig. lists the 3 highest-scored and 3 lowest-scored shapes of CAW, which are extracted from the Wikipedia dataset with M = 32 and m = 3. A law of general motif closure can be observed from the highest-scored CAWs: two nodes that commonly appear in some types of motif
more inclined to
have a link in between. For example, the highest-scores shape of CAW, (0, oc) + (1,2) + (2,3) - (1, 2), implies that the nodes except the first in this CAW appear in the sampled common 3-hop
20

---

Published as a conference paper at ICLR 2021
1.0
occurence ratio positive links
occurence ratio with negative links
0.8
0.6
0.4
0.0
SAw (W)(W)
0-1-2-1 0-1-0-1 0-1-0-
0 -+1 0-1+2
Figure Visualizing all AWs, and their occurrence ratios with positive / negattvee samples.
neighborhood around the nodes between which the link is be predicted. Therefore, CAW-N essentially adaptively samples a temporal motif closure pattern that is very informative to predict this link. CAW-N does not explicitly enumerating or counting these motif patterns. In contrast, when CAWs do not bridge the two nodes, as shown in top-2 lowest-scored CAWs, very unlikely there will exist link. Fig. also displays each of the CAW's occurrence ratio with positive and negative links. The difference within each pair of ratios is an indicator of the corresponding CAW's discriminatory power. We also see that the discriminatory power of CAWs is very strong: highest-scored CAWs almost never occur with negative links, and lowest-scored CAWs also seldom occur with positive links.
We further apply the similar procedure to analyze the AWs introduced in Sec. 4. and the model Ab.5 of Tab. Jused for ablation study, Note that AW cannot establish the correlation between walks, each single AW itself, say W (Cu, U1,..., U, decides its shape sAw (W). We directly set SAw (W)= = Law (Dy: W) - Law (12; W) - ... - Law (Umi W) with Law (w: W) defined Eq. 2 As the Wikipedia dataset is bipartite graph, there are in total four different shapes when m as listed align with the x-axis of Fig. 9 For illustration, we explain one shape of AW as an example, say -
- 1: The corresponding walks have the second and the fourth nodes correspond to the same node, which the first, second and third nodes are different. As shown in Fig.
we can see that AW's occurrence with positive versus negative links are highly mixed-up. compared CAW's. That suggests that AWs possess significantly less discriminatory power than CAWs. The main reason that AWs do not have set-based anonymization, so they cannot capture the correlation between walks/motif's but CAWs can do that. This observation further gives reason on why the model Ab.5 of Tab. only achieves some performance on-par with the model Ab.2 where we totally remove anonymization procedure: the anonymization adopted by AWs loses too much information of the structure and cannot benefit the prediction much. However, the original CAW-N well captures such information via the set-based anonymization.
g
21


Reviews:
[{"review_id": "ztOQW8_Aa-E", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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 proposed causal anonymous walks (CAW) is the key contribution of the paper where the set-based anonymization is adopted to allow temporal and structure information in a temporal network can be retained in the CAWs. The sampled CAWs are then used to learn RNN for the link prediction.\n\nPros:\n- The proposed design of CAW (set-based anonymization in particular) is a simple and reasonable one. The empirical results show that it is a good input representation to be fed to the RNN for training.\n- The consideration of the underlying motifs is captured by the RNN so that the scalability issue caused by identifying the motifs can be alleviated.\n- The empirical results based on six different datasets show that it outperforms a number of existing methods.\n- The experiments were well designed with ablation study to figure out the effectiveness of different components introduced in the proposed methods.\n\nCons: \n- In terms of methodology, it is an improved method upon some previously proposed anonymous walk for handling temporal networks. There is some novelty but it is hard to be considered as a breakthrough as claimed by the authors.\n- Figures 1 and 2 are included to help explain the concepts. They are good in general but a bit compact with a lot of details packed making the presentation not hard to comprehend.\n- Readability could be improved. My impression is that it requires the readers to have some background on temporal motifs and anonymous walks or it could be hard for the reader to follow.\n- Entanglement of structural and temporal information is mentioned as one of the challenges. It is not clear how this is addressed in the proposed method.\n\nQns\n- Is the structural and temporal information being addressed disentangled in some way? It seems that it just replies on the use of RNN to take care of all the information as a black box.\n- Can the optimality of the adopted encoding steps be discussed? It seems that they are determined by making references to different existing works.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "uEKobAY-kxh", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "Summary:\nThe paper provides an interesting way to inductively represent a temporal network with the proposed Causal Anonymous Walks (CAWs) which work as temporal motifs to represent the network dynamics. The CAWs can be further encoded by the proposed CAW-N which supports online training. \n\nPros:\nOverall, I like the idea to represent the temporal network with the proposed causal anonymous walks. Experimental results also show significant improvements over the existing baselines.\n- Representation learning for dynamic graphs is very practical and important. This paper proposed an effective solution to this problem.\n- The proposed CAW is novel for capturing the temporal dynamics in temporal networks. The description of the method is easy to follow.\n- This paper provides sufficient experimental results which show the effectiveness of the proposed CAW-N model on the link prediction task, including a wide variety of baselines and datasets.\n\nCons: \n- This paper has been listed on the author's homepage (https://scholar.google.com/citations?user=Ch3YUgsAAAAJ&hl=en), potentially violate the double blind review rules.\n- Some figures, e.g. figure 4, are not very useful in explaining the corner cases. Simple sentences are enough for clarification.\n- It would be better to include the training/inference time comparisons as the introduction claims \"the model scalability\". \n- It would be more convincing if the authors can provide representation visualization comparisons in the rebuttal period. \n \nMinors: \n- missing conclusion section\n- Eq.2, I_AW(w; P), definition of P\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "e0o0JmzPBnW", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "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 authors provide in-depth analysis on the critical topic of capturing dynamic laws for the inductive representation learning of temporal graphs. The authors leverage the causal anonymous walk to capture the topological laws of the dynamic graph, while not requiring to memorize node identities such that inductive learning is still feasible. Compared with the previous work, the paper emphasizes on scenarios where node/edge attributes are less informative of the inductive reasoning. Some workaround methods are also proposed to deal with the edge features and to enable the efficient computation and sampling procedure. \n\nThe paper is overall well-written, and the motivations are justified clearly. The most relevant work of TGAT from Xu, et al. 2020 does not explicitly account for the dynamic laws of evolving graphs, and the way they construct and sample the local neighborhood is infeasible when processing large graphs in a streaming fashion. The authors leverage the causal anonymous walks to:\n\n1. capture the signals of topological structures which \"reflect\" the identities of the nodes;\n\n2. avoid the costly computations to recover the network structural features during both the training and inference.\n\nThe contribution is solid as it complements the TGAT when the node/edges features are less important. It also solves the computation issues of the TGAT. The numerical results also compare favorably to the baselines. \n\nMy concerns with the paper include:\n\n1. Using random walks and local aggregation methods (such as GCN, GAT, TGAT) have their different emphasis on the network topological laws & node/edge features. The authors should discuss and make it more clear regarding the pros and cons. \n\n2. It appears TGAT adopts the same inductive representation learning setting from GraphSAGE and GAT, which are widely accepted in this domain. The claim and key arguments made by the authors raise a major confusion about being inductive in graph representation learning, and I believe the criticisms here are equally applicable to GraphSAGE and GAT that leverage node features as well. Therefore, I think the notion of inductiveness studied by the authors is at most in parallel to that of TGAT (and GraphSAGE & GAT). If the authors believe their notion of inductiveness is more proper, they should discuss the similar issues for GraphSAGE and GAT since they are more well-known to the readers and will raise less confusion.\n\n3. the link sampling strategy that ensures the overall efficiency of the computation lacks support and is not principled. To some extent, neighborhood/walk construction in dynamic graphs are still open challenges in this domain, so I think using heuristics is fine, but the consequence should be made more clear.\n\nThe authors make the novel contribution of combining the causal anonymous walk with inductive representation on temporal graphs. However, their arguments on the notion of inductiveness can raise a major confusion if not directly discussed for GraphSAGE and GAT. Therefore, I vote for a weak acceptance of this version of the paper.\n\n============================================\nThe authors address most of my questions and concerns in the response, and update the manuscript. I decide to increase my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "8oL77rt82e9", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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 proposes Causal Anonymous Walks (CAWs) that are extracted by temporal random walks and work as automatic retrieval of temporal network motifs to represent network dynamics while avoiding the time-consuming selection and counting of those motifs. CAWs adopt an anonymization strategy that replaces node identities with the hitting counts of the nodes based on a set of sampled walks to keep the method inductive, and simultaneously establish the correlation between motifs. CAW-N to encode CAWs with a neural network model. CAW-N was evaluated to predict links over 6 real temporal showed better AUC gain compared to baselines. \nPros: \n-\tPromising evaluation results which shows average 15% AUC gain compared to 6 baselines over 6 real world datasets. \n-\tNovel idea of avoiding the selection and counting of network motifs instead leveraging anonymization and encoding.  \nCons:\n-\tNo conclusion or future work that discusses about next steps for research community. \n-\tHyperparameter study shows the AUC is very sensitive to sampling strategy (time bias or sampling length). \n-\tSet-based anonymization seems to require a computational complexity of counting the number of nodes in different positions. For example in Figure 2, it counts the number of “b” in different positions. There is no computational complexity comparison between counting this vs. motif counting. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper introduces a new method for encoding dynamics of temporal networks.  The approach, while not ground-breaking, is interesting and the results are fairly convincing.

The submission raised a number of concerns from the reviewers. They questioned the complexity of the proposed approach (R3 and R4), the clarity/readability (R2 and R1), and appropriateness of the link sampling strategy (R2), as well as raised several more minor (from my perspective) issues. I believe that the authors adequately addressed most of these concerns in their rebuttal and the revision.  R2 has confirmed that they read the rebuttal and raised their score to strong accept. Unfortunately, the other reviewers have not engaged during the discussion period, and it is unclear if they are satisfied with the clarifications and changes. Nevertheless, after reading the authors' responses and skimming through the manuscript, I believe that most concerns have been addressed, and this is a good paper that deserves to be accepted. That being said, the issue of readability has been raised by the reviewers, and, while I do not think the paper is unreadable, I do agree that there is much room for improvement. I would encourage the authors to polish the manuscript for the camera-ready version, as well as try to address the remaining concerns raised by the reviewers. 


Decision: Accept (Poster)