Time-varying Graph Representation Learning via Higher-Order Skip-Gram with Negative Sampling
Authors: Simone Piaggesi
André Panisson
Venue:  (2021)
Keywords: representation learning
node embeddings
temporal graphs
tensor factorization
disease spreading

Abstract: Representation learning models for graphs are a successful family of techniques that project nodes into feature spaces that can be exploited by other machine learning algorithms. Since many real-world networks are inherently dynamic, with interactions among nodes changing over time, these techniques can be defined both for static and for time-varying graphs. Here, we show how the skip-gram embedding approach can be used to perform implicit tensor factorization on different tensor representations of time-varying graphs. We show that higher-order skip-gram with negative sampling (HOSGNS) is able to disentangle the role of nodes and time, with a small fraction of the number of parameters needed by other approaches. We empirically evaluate our approach using time-resolved face-to-face proximity data, showing that the learned representations outperform state-of-the-art methods when used to solve downstream tasks such as network reconstruction. Good performance on predicting the outcome of dynamical processes such as disease spreading shows the potential of this new method to estimate contagion risk, providing early risk awareness based on contact tracing data.

Under review as a conference paper at ICLR 2021
TIME-VARYING GRAPH REPRESENTATION LEARNING VIA HIGHER-ORDER SKIP-GRAM WITH NEGATIVE SAMPLING
Anonymous authors Paper under double-blind review
ABSTRACT
Representation learning models for graphs are a successful family of techniques that project nodes into feature spaces that can be exploited by other machine learning algorithms. Since many real-world networks are inherently dynamic, with interac- tions among nodes changing over time, these techniques can be defined both for static and for time-varying graphs. Here, we show how the skip-gram embedding approach can be used to perform implicit tensor factorization representations of time-varying graphs. We show that higher-order skip-gram with negative sampling (HOSGNS) is able to disentangle the role of nodes and time, with a small fraction of the number of parameters needed by other approaches. We empirically evaluate our approach using time-resolved face-to-face proximity data, showing that the learned representations outperform state-of of-the--rr art methods when used to solve downstream tasks such as network reconstruction. Good performance on predicting the outcome of dynamical processes such as disease spreading shows the potential of this new method estimate contagion risk, providing early risk awareness based on contact tracing data. The source code and data are publicly available at [link to anonymized repository]
different tensor
INTRODUCTION
A great variety of natural and artificial systems can be represented networks of elementary structural entities coupled by relations between them. The abstraction of such systems as networks helps us understand, predict and optimize their behaviour (Newman) 2003 Albert & Barabási] 2002). In this sense, node and graph embeddings have been established as standard feature representations in many learning tasks (Cai et al. 2018 Goyal & Ferrara 2018). Node embedding methods map nodes into low-dimensional vectors that can be used to solve downstream tasks such as edge prediction, network reconstruction and node classification.
Node embeddings have proven successful in achieving low liwddimnnsional encoding of static network structures, but many real-world networks inherently dynamic (Holme & Saramäki 2012). Time- resolved networks are also the support of important dynamical processes, such as epidemic or rumor spreading, cascading failures, consensus formation, etc. (Barrat al. 2008). Time-resolved node embeddings have been shown to yield improved performance for predicting the outcome of dynamical processes over networks, such information diffusion and disease spreading (Sato et al. 2019) providing estimation of infection and contagion risk when used with contact tracing data.
Since we expect having more data on proximity networks being used for contact tracing and as proxies for epidemic risk (Alsdurí et al. 2020). learning meaningful representations of time-resolved proxim- ity networks can be of extreme importance when facing events such as epidemic outbreaks (Kapoor et al. 2020 Gao et al. 2020). The manual and automatic collection of time-resolved proximity graphs for contact tracing purposes presents an opportunity for quick identification of possible infection clusters and infection chains. Even before the COVID-19 pandemic, the use of wearable proximity sensors for collecting time-resolved proximity networks has been largely discussed in the literature and many approaches have been used to deseribe patterns of activity and community structure. and to study spreading patterns of infectious diseases (Sapienza et al., 2015) Gauvin et al. 2014: Génois et al. 2015).

---

Under review as a conference paper at ICLR 2021
Here we propose representation learning model that performs implicit tensor factorization different higher-order representations of tarying graphs. The main contributions are as follows: Given that the skip-gram gap-grammm embedding approach implicitly performs factorization of the shifted pointwise mutual information matrix (PMI) (Levy & Goldberg 2014), we generalize it to perform implicit factorization of shifted PMI tensor. We then define the steps to achieve this factorization using higher-order skip-gram with negative sampling (HOSGNS) optimization. We show how to apply 3rd-order and 4th-order SGNS on different higher-order representations of time-varying graphs. Finally, we show that time-varying graph representations learned via HOSGNS outperform state- of-the-art methods when used to solve downstream tasks, even using a fraction of the number of embedding parameters.
We report the results of learning embeddings on empirical time-resolved face-to-face proximity data and using such representations as predictors for solving two different tasks: network reconstruction and predicting the outcomes of SIR spreading process over the varying graph. We compare these results with state-of-the art methods for time-varying graph representation learning.
PRELIMINARIES AND RELATED WORK
Skip-gram representation learning. The skip-gram model was designed to compute word em- beddings in WORD2VEC (Mikolov al. 2013), and afterwards extended to graph node embeddings (Perozzi et al. 2014; Tang et al.) 22015] Grover & Leskovec 2016). Levy & Goldberg (2014) es- tablished the relation between skip-gram trained with negative sampling (SGNS) and traditional low-rank approximation methods (Kolda & Bader 2009 Anandkumar et al. 2014), showing the
equivalence of SGNS optimization to factorizing shifted PMI matrix (Church & Hanks [990). This equivalence was later retrieved from diverse assumptions (Assylbekov & Takhanov 2019 Allen et al.)
2019. Melamud & Goldberger] 2017 Arora al. 20166] Li et al.] and exploited to compute closed form expressions approximated in different graph embedding models (Qiu et al.) 2018)) In this work, we refer to the shifted PMI matrix also as SPMI, = PMI - log K. where A is the number of negative samples.
Random walk based graph embeddings. Given an undirected, weighted and connected graph E) with nodes j.j E V, edges (i. E & and adjacency matrix A, graph embedding methods are unsupervised models designed to map nodes into dense d-dimensional representations (d < [VD (Hamilton et al. 2017). A well known family of approaches based on the skip-gram model consists in sampling random walks from the graph and processing node sequences as textual sentences.
In DEEPWALE AL.K (Perozzi al. 2014) and NODR2vEC (Grover & Leskovee 2016), the skip-gram model is used to obtain node embeddings from co-occurrences in random walk realizations. Although the original implementation of DEEPWALK ALK uses hicrarchical softmax to compute embeddings, we will refer to the SGNS formulation given by Qiu et al. (2018).
Since SGNS can be interpreted as a factorization of the word-context PMI matrix (Levy & Gold berg] (014)) the asymptotic form of the PMI matrix implicitly decomposed in DEEPWALK can be derived (Qiu et al., 2018). Given the 1-step transition matrix P = D-1A, where = diag( (oug(d11... .d..... ,dyi) and d, Ejev Ai is the (weighted) node degree, the expected PMI for node-context pair (i. occurring in T-sized window is:
2T ('()(P")
Ej PMI DREPWALK (i.5) T = log
(
(2.1)
d, where p² p1) = vol(o] is the unique stationary distribution for random walks (Mssuda et al. 2017 and vol(g) = Eijev Aij. We will use this expression in Section 3.2 to build PMI tensors from higher-order graph representations.
Time-varying graphs and their algebraic representations. Time-varying graphs (Holme & Saramäki 2012) are defined as triples H. = (V,ETT) i.c. collections of events ji,j,k) E E, representing undirected pairwise relations among nodes at discrete times (i.j E V, k E T). H can be as temporal sequence of static graphs (g()))kTT each of those with adjacency matrix (4) such that A (/) = j(i E R is the weight of the event (i,j. E E. We can concatenate the list of time-stamped snapshots (1)1) ....,, (TT) obtain single 3rd-order tensor
2

---

Under review as a conference paper at ICLR 2021
A (H) R which characterize the evolution of the graph over time. This representa- tion has been used to discover latent community structures of temporal graphs (Gauvin et al.) 2014) and to perform temporal link prediction (Dunlavy et al. 2011). Indeed, beyond the above stacked graph representation, more exhaustive representations are possible. In particular, the multi-layer approach (De Domenico et al., 2013) allows map the topology of time-varying graph H into a static network GN = (VH, Ex) (the supra-adiacency graph) such that vertices of GH correspond to pairs (i, k) = (()) E V x T of the original time-dependent network. This representation can be stored in a 4th-order tensor A dym (H) E R | equivalent, up to an opportune reshaping, to the adjacency matrix (9x) E ( associated to Gy. Multi-layer representations for time- aiee-varynng networks have been used to study Lume-dependens centrality measures (Taylor et al.) 2019) and properties of spreading processes (Valdano et al. 2015).
Time-varying graph representation learning. Given a time-varying graph H = (V, we define as temporal network embedding model that learns from data, implicitly or explicitly, mapping function:
f (v, 1) E V x T E Rd
(2.2)
which project time-stamped nodes into a latent low-rank vector space that encodes structural and temporal properties of the original evolving graph. Many existing methods Iearn node representations from sequences of static snapshots through incremental updates in a streaming scenario: deep autoencoders (Goyal al. 2017), SVD (Zhang al. 2018 skip-gram (Du al. 2018) and random walk sampling (Béres et al. 20199 Mahdavi et al. 20188] Yu et al. 2018). Another class of models
learn dynamic node representations by recurrent/attentioo mechanisms (Goyal al., 2020 Li et al.) 2018; Sankar et al., 2020 Xu et al. 2020) or by imposing temporal stability among adjacent time intervals (Zhou al. 2018 Zhu al. 2016). DyANE (Sato al., 2019) and wEG2VEC (Torricelli et al.) 2020) project the dynamic graph structure into a static graph. in order to compute embeddings with WORD2vEC. Closely related to these ones are Nguyen et al. (2018) and ZZan al. (2020), which learn node vectors according to time-respecting random walks or spreading trajectory paths. Moreover, Kumar (2019) proposed an embedding framework for user-item temporal interactions, and Malik et al. (2020) suggested tensor-based convolutional architecture for dynamic graphs.
Methods that perform well for predicting outcomes of spreading processes make use of time- respecting supra-adjacency representations such the one proposed by Valdano al. (2015). In this representation, random itineraries correspond to temporal paths of the original time-varying graph. The supra-adjacency representation Gz that refer in Section 3.2 also used in DyANE, with adjacency matrix A (Gx), is defined by two rules:
1. For each event (i,j, to), if also active at time f >> lg and in no other time-stamp between the two, we add cross-coupling edge between supra-adjacency nodes j(to) and j(f)) In addition, if the next interaction of j with other nodes happens at t2 > to. we add an edge between 2(1)) and j(tz), The weights of such edges are set to j...
2. For every case as described above, we also add self-coupling edges (ilte), z(t1)) and (j(tt),, (((t)),(()))) with weights set to 1.
self-coupling
cross-coupling
k
k
4
4
Figure 1: A time-varying graph H with three intervals (left) and its corresponding time-respecting aupra-adjacency graph Gx (right).
Figure I shows the differences between time-varying graph and its time-aware supra-adjacency representation, according to the formulation described above. Dy AYANE computes, given a node E V, one vector representation for each time-stamped node j(t) E viT) = ((i,t) E V VxT: (i.j. E E} of this supra-adjacency representation. Similar models that learn time-resolved node representations
3

---

Under review as a conference paper at ICLR 2021
require quantity O(IV) IT]) of embedding parameters represent the system in the latent space. Compared with these methods, our approach requires quantity O([V) + (T]) of embedding parameters for disentangled node and time representations.
PROPOSED METHOD
Given time-varying graph H. TT we propose representation learning method that Iearns disentangled representations for nodes and time slices. More formally, we learn a function:
(o,l)
v,t Rd
through a number of parameters proportional O(V) + [7])- This embedding representation can then be reconciled with the definition in Eq. (.2) by combining v and in a single v() representation using any combination function e: (v.t)= R Fd v(t) Rd.
Starting from the existing skip-gram framework for node embeddings, we propose higher-order generalization of skip-gram with negative sampling (HOSGNS) applied time-varying graphs. We show that it allows to implicitly factorize higher-order relations that characterize tensor representations of time-vare varriig graphs, the same way that the classical SGNS decomposes dyadic relations associated to static graph. Similar approaches have been applied in NLP for dynamic word embeddings (Rudolph & Blei] 2018), and higher-order extensions of the skip-gram model have been proposed to learn context-dependent (Liu et al., 2015) and syntactic-aware (Cotterell al.) 2017) word representations. Moreover tensor factorization techniques have been applied to include the temporal dimension in recommender systems (Xiong al. 2010 Wu ct 2019), knowledge graphs (Lacroix et al. 2020 Ma et al. 2019) and face-to-face contact networks (Sapienza et al. 2015 Gauvin et al. 2014). But this work the first to merge SGNS with tensor factorization, and then apply it to learn time-varying graph embeddings.
3.1 HIGHER-ORDER SKIP-GRAM WITH NEGATIVE SAMPLING AS IMPLICIT TENSOR FACTORIZATION
Here we address the problem of generalizing SGNS learn embedding representations from higher- order co-occurrences. We analyze here the 3rd-order case, giving the description of the general N-order case in the Supplementary Information. Later in this work we will focus 3rd and 4th order representations since these are the most interesting for time-varying graphs.
We consider set of training samples D (i,j.k), i W, C, & E T} obtained by collecting co-occurrences among elements from three sets W, C and T. While SGNS is limited to pairs of node- context (i, here 'D is constructed with three (or more) variables, e.g. sampling random walks higher-order data structure. We denote as (1. k) the number of times the triple (i.j. k) appears in D. Similarly we use #i Ej #(i, k), #j Eea # k) and #k Eis #(i, as the number of times each distinct element occurs in D, with relative frequencies (p(i,j,)) = #(.j.) #1 - Po(
(D(
#1 and (k) [D
# [D]
Optimization is performed as binary classification task, where the objective discern occurrences actually coming from 'D from random occurrences. We define the likelihood for single observation (i,j.k) by applying a sigmoid (a = (1 -- the higher-order inner product [-I of corresponding d d-dimensional representations:
P P( ED wi, to = o [[,,,,, txl) = [o (E W Crr
(3.1)
where embedding vectors W;, Cj, Rd are respectively rows of W R C xc
and T E ll/]xd In the 4th-order case we will also have fourth embedding matrix S E S xd related to a fourth set S. For negative sampling we fix an observed (i. k) E D and independently sample ju and ky to generate negative examples j... kxr). ). In this way, for single occurrence (i,j, k) E DD the expected contribution to the loss is:
{(i.j. k) log ([w;, Cj2 tx]) +
E ix P
[logo( ( [w,, Gjv- tRxl))
(3.2)
4

---

Under review as a conference paper at ICLR 2021
where the noise distribution is the product of independent marginal probabilities Pv)(j PD(j). Po(k). Thus the global objective is the sum all the quantities of Eq. (3.2) weighted with the corresponding relative frequency Po(i.j, k). The full loss function can be expressed as:
IW |c| IT! -=1ΣΣΣ
C
t.l) + R (x((i,,k logo( [w:, Cji te]l] (3.3)
=1
In Supplementary Information we show the formal steps to obtain Eq. 3.3 for the N-order case and that it can be optimized with respect the embedding parameters, satisfying the low-rank tensor approximation the multivariate shifted PMI tensor into factor matrices W, C, T:
Σn Wir Tur log
(D( (.(
log K SPMI, (i,
(3.4)
3.2 TIME-VARYING GRAPH EMBEDDING HOSGNS
While static graph 9 = (V, E) is uniquely represented by an adjacency matrix A()) E RIVI time-varying graph 7 TT) admits diverse possible higher-order adjaceney relations (Section Starting from these higher-order relations, we can either use them directly or use random walk realizations to build a dataset of higher-order co-occurrences. walk realizations give place to dyadic co-occurrences used to learn embeddings in SGNS, we use higher-order co-occurrences to learn embeddings via HOSGNS.
2).
the same spirit that random
As discussed in Section 3.1 the statistics of higher-order relations can be summarized in multivariate PMI tensors, which derive from proper co- co-occurrence probabilities among elements. Once such PMI tensors constructed, we again factorize them via HOSGNS. To show the versatility of this approach, we choose PMI tensors derived from two different types of higher-order relations:
1. A 3rd-order tensor (statt) (H) E R MX which gather relative frequencies of nodes occurrences in temporal edges:
wi.j,kk)
(p(otat)) )azk vol(H)
(3.5)
where vol(H) = Enj j(i,j.k is the total weight of interactions occurring in H.
These probabilities are associated to the snapshot sequence representation Atst (H)
[A (1) . A (TT)) and contain information about the topological structure of H.
2. A 4th-order tensor P (dym) (H)) |/ which gather occurrence probabilities of time-stamped nodes over random walks of the supra-adjacency graph GN (as used in DyANE), Using the numerator of Eq. (2.1) tensor entries are given by:
(P (P")(a))) + dun vol(Gn)
d vol(Gx) (P")
(pldgn) light Jigkt
(P" ())coa))))
(3.6)
27
where (ik) and (jt) are lexicographic indices of the supra-adjacency matrix A cor- responding to nodes i()) and node j()) These probabilities encode causal dependeneies among temporal nodes and are correlated with dynamical properties of spreading processes.
We also combined the two representations a single tensor that is the average p (sstaa)) and p (dyn)
(P (stat) (stat)dgn) (gn))
sykl 2 (Pl (stat) De + (P (dym) Jagkt
(3.7)
where 6gz = 1[k = ( is the Kronecker delta.
Figure 2 summarizes the differences between graph embedding via classical SGNS and varying graph embedding via HOSGNS. Here, indices (i, I) correspond to (node, context, time, context- time) in 4th-order tensor representation of H.
The above tensors gather empirical probabilities (p k...) corresponding to positive examples of observable higher-order relations. The probabilities of negative examples Py j, k...) can be
5

---

Under review as a conference paper at ICLR 2021
Classical SGNS
HOSGNS
W
Node ambaddinge matris, W
Contest ambedddinge
Node embeddings maini,
embeddingg
embeddings mabrix
Context umbeddding muaiiss 5
O0 Random Walk (V,E)
(R)
higher-order representation of H (V,ETT)
Figure Representation of SGNS and HOSGNS with embedding matrices and operations on embedding vectors. Starting from a random walk realization static graph 9 (V, SGNS takes as input nodes i and j within a context window of size T, and maximizes (W, Cy). HOSGNS starts from random walk realization
higher-order representation of time-varying graph H & T) takes input nodes ((k (node at time k) and j(() (node
time /) within a context window of size I and maximizes [[[,, Cj2 tx, st]). In both cases, for each input sample, we fix i and draw combinations of j or j, from a noise distribution, and we maximize (-w, - Cÿ) (SGNS) or o- [w: Cj. tg. s (HOSGNS) with their corresponding embedding vectors (negative sampling).
obtained as the product of marginal distributions PD(i), PD(j), PD(k) Computing exactly the objective function in Eq. (3.3) (or the 4th-order analogous) is computationally expensive, but it can be approximated by a sampling strategy: picking positive tuples according to the data distribution Po and negative ones according independent sampling Pv. HOSGNS objective can be asymptotically approximated through the optimization of the following weighted cross entropy loss:
((bee)
Σ
log Dogo[Iw Cjn t.... +
Σ
log logo(-[ws,) Cj tu Cy, C...k....))))
11] (3.8)
)xPP
(Kik... PNP
where B is the number of the samples drawn in a training step and is the negative sampling constant. We additionally apply the warm-up steps explained in Supplementary Information to speed-up the training convergence.
EXPERIMENTS
For the experiments we use time-varying graphs collected by the SocioPatterns collaboration http://wwww.occipattee oog) using wearable proximity sensors that sense the face-to-face proximity relations of individuals wearing them. After training the proposed models (HOSGNS applied to pistat) (dgn) or p ((statddgn) on each dataset, embedding matrices W, C. (and in case of p ((stat)) are mapped to embedding vectors w,, Cj, t (and s)) where i, E V and k. E T, and we them to solve different downstream tasks: node classification and temporal event reconstruction.
4.1 EXPERIMENTAL. SETUP
Datasets. We performed experiments with both empirical and synthetic datasets describing face-to- face proximity of individuals. We used publicly available empirical contact data collected by the SocioPatterns collaboration (Cattuto et al. (010)) with temporal resolution of 20 seconds, in variety of contexts: in a school ("L ""LYONSCHOO"" "), conference ("SFHH"), a hospital ("LH10"), a highschool ("THIERs13"), and in offices ("INVS15") (Génois & Barrat 2018). This is currently the largest collection open datasets sensing proximity in the same range and temporal resolution used by modern contact tracing systems. In addition, we used social interactions data generated by the agenttbbsedd-ne bww.d-asoooooooo model OpevABM-Covid19 (Hinch et al. 2020) to simulate an outbreak of COVID-19 in urban setting.

---

Under review as a conference paper at ICLR 2021
We built time-varying graph from each dataset, and for the empirical data we performed aggregation on 600 seconds time windows, neglecting those snapshots without registered interactions at that time scale. The weight of the link (.) à) is the number of events recorded between nodes (i in certain aggregated window k. For synthetic data we maintained the original temporal resolution and set links weights to 1. Table shows statistics for each dataset.
Table Summary statistics about empirical and synthetic time-varying graph data, In order: number of single nodes [V., number of steps [T], number of events [E], number of active nodes [V(T). average weight of events
[ET Eese w(e), nodes density |M(7] and links density
2|
|
VI[ 1)
Dataset
[V]
[T]
|E]
V(T)
Average Weight
Nodes Density
Links Density
LYONSCHOOL
242
104
44820
17174
2.806
0.6824
0.0148
Empirical graphs
SFHH
403
127
17223
10815
0.2113
0.0017
LH10
76
321
7435
4880
4,448
0.2000
0,0081
THIERS13
327
246
35862
32546
5.256
0.4046
0.0027
INVS15
217
691
18791
22451
4.164
0.1497
0.0012
Syntheric
OPENARM WWW.AAAMM-OOVIII----111
2000
100
1243551
198537
0.9927
0,0062
graphs
OPENABM-COVID19-1--000
5000
20
632523
99966
1.0
0.9997
0,0025
Baselines. We compare our approach with several baseline methods from the literature of time- varying graph embeddings, which learn stae-st node representations: (1) DyANE (Sato et al., 2019), which learns temporal node embeddings with DEEPWALE ALK, mapping a time-varying graph into supra-adjacency representation; (2) DysGEM (Goyal et al. 2017), deep autoencoder architecture which dynamically reconstructs each graph snapshot initializing model weights with parameters learned in previous time frames; (3) DYNAMICTRIAD (Zhou et al., 2018), which captures structural information and temporal patterns of nodes, modeling the triadic closure process. Details about hyper-parameters used in each method can be found in the Supplementary Information.
4.2 DOWNSTREAM TASKS
Node Classification. The aim this task is to classify nodes in epidemic states according to a SIR epidemic process with infection rate B and recovery rate μ. We simulated 30 realizations of the SIR process on top of each empirical graph with different combinations of parameters (3, μ)). We used similar combinations of epidemic parameters and the same dynamical process produce SIR states as described in Sato et al. (2019). Then we set a logistic regression to classify epidemic states S-I-R assigned to each active node g(4) during the unfolding of the spreading process. We combine the embedding vectors of HOSGNS using the Hadamard (element-wise product w, tg. We compared with dynamic node embeddings learned from baselines. For fair comparison, all models produce time-stamped node representations with dimension d 128 as input the logistic regression.
Temporal Event Reconstruction. In this task, we aim to determine if an event (i. k) is in H = -V, & T), i.e., if there is an edge between nodes and j time k. We create random time- varying graph H (V, E* T)) with same active nodes yTT and number of |8| events that are part of E. Embedding representations learned from H are used as features to train a logistic regression to predict if a given event (i. j, k) is in E or in E-. We combine the embedding vectors of HOSGNS as follows: for HOSGNS (stat), we use the Hadamard product w, o Cj tt; for HOSGNS (dyn) and (stat)
HOSGNS dyn), we use w, ot, OSK. For baseline methods, we aggregate vector embeddings to obtain link-level representations with binary operators (Average, Hadamard, Weighted-LL1, Weighted- 1.2 and Concat) as already used in previous works (Grover & Leskovee 2016 Tsitsulin et al., 2018). For fair comparison, all models are required produce event representations with dimension d 192.
Tasks were evaluated using train-test split. To avoid information leakage from training to test, we randomly split V and T in train and test sets (Ver, V.s) and (Ter, Tra), with proportion 70% - 30%. For node classification, only nodes in Ver at times in Ter were included in the train set, and only nodes in Vie at times in Tea were included in the test set. For temporal event reconstruction. only events with j E Ver and I E Ter were included in the train set, and only events with i, E Vz, and k E Tea were included in the test set.
7

---

Under review as a conference paper at ICLR 2021
4.3 RESULTS
In this section we first show downstream task performance results for the empirical datasets, leaving results for synthetic datasets Supplementary Information. Synthetic datasets are used here to compare the performance of the different approaches in terms of training complexity, by measuring the number of trainable parameters and the training time with fixed number of training steps.
All approaches were evaluated for both downstream tasks in terms of Macro-F] scores in all datasets. different runs of the embedding model are evaluated on 30 different train-test splits for both down- stream tasks. We report the average score with standard error over all splits. In node classification, every SIR realization is assigned to a single embedding run to compute prediction scores. In event reconstruction, a different random realization H" is assigned to each train-test subset.
Results for the classification of nodes in epidemic states are shown Table 2 We report here a subset of (B, 11) but other combinations are available the Supplementary Information. DyNGEM and DYNAMICTRIAD have low scores, since they are not devised to learn from graph dy- namics. HOSGNS (stat) is not able to capture the graph dynamics due to the static nature of p (statt). DyANE, HOSGNS' ( (stat)dym) and HOSGNS (dyn) show good performance, with these two HOSGNS variants outperforming DyANE in most of the combinations of datasets and SIR parameters.
Table 2: Ml scores for classification of nodes in epidemic states according to different SIR epidemic processes over empirical datasets. For each (3, (4) we highlight the two highest scores and underline the best one.
(9,p)
Model
Dataset LH11
LYONSCHOOL
SPHH
THIERSI3
INVS15
DYANE
78.1
67.0
64.3
DYNGEM
2.8
35.9 1.1
34.5 0.7
35.5 1..5111 1.2
58.8 1: 1.1
DYNAMICTRIAD
31.0
28.8 0.4
2.3
30.3
30.4
(0.25, 0.002)
HOSGNS!RTat
0.85
57.3
4..9
4..9
44.5
(1SGGNS(49))
1.5
1.2
(OSGNS(<rat)dda))
0.6
1.2
72.5
DYANE
75.3 0.4
71.6 + 1.9
59.0
1.3
65.8 0.6
DYNGEM
58.9
37.0 1: 4.1
41.0 1.4
32.5
59.0 1:
(0.125, 0.001)
DYNAMICTRIAD
3..2
35.0 1 3.3
30.5 0.7
27.4 0.3
29.5 0.2
56.8
61.8 1: 2.4
49.1 1.9
47.3 11331000
45.9 0.7
HOOGGNS (dyy)
76.0 1 0.4
71.5 1: 2.0
59.6 2.0
0.4 74.2
65.9 0.6
HOSGNS (
74.6
70.2 1.9
59.9 2.3
74.8 0.4
66.0 - 0.6
DYANE
72.2
64.9 1.7
59.0 1.2
68.0 0.5
60.2 2 0.5
DYNGEM
2.7
35.8
32,9
(0.0625, 0.002)
DYNAMICTRIAN TRIAD
29.5
33.1 2.5
29.6 0.4
27.4 0.3
28.4 0.2
HOSSNSS (rrat)
3..5.1.0.7
57.6 2.2
49.4 1..4..0..
45.5 1.51100 0.4
43.6 1 0.5
HOSGNS (dyn)
0.5
65.7 1.6
61. 111110 1.2
69.5 - 0.3
59.6 0.5
HOSGNS (teetddn)
72.9
66.8 + 1.9
58.2 de 1.1
68.5
0.4
59.0 0.7
Results for the temporal event reconstruction task are reported in Table Temporal event reconstruc- tion not performed well by DyNGEM. DYNAMICTRIAD has better performance with Weighted-LI and Weighted-L2 L2 operators, while DYANE has better performance using Hadamard or Weighted- L.2 Since Hadamard product explicitly used in Eq. 33.1 to optimize HOSGNS, all HOSGNS variants show best scores with this operator. HOSGNS stat) outperforms all approaches, setting
new state-of-thh-art results this task. The P (dyn) representation used as input to HOSGNS (dym) does not focus on events but dynamics, the performance for event reconstruction is slightly below DYANE, while HOSGNS (stat]dyn) is comparable to DYANE. Results for HOSGNS models using other operators are available in the Supplementary Information. We observe an overall good performance of HOSGNS (stat)dgn) in both downstream tasks, being in almost all cases the second highest score, compared to the other two variants which excel in one task but have lower performance in the other.
Training Complexity. We report in Table 4 the number of trainable parameters and training time duration for each considered algorithm, when applied to an empirical graph (LYONSCHOOL) and to the synthetic ones. The proposed HOSGNS model requires number of trainable parameters that is orders of magnitude smaller than other approaches, with a training time considerably shorter as the number of nodes increases, given a fixed number of training iterations. For this analysis, HOSGNS
8

---

Under review as a conference paper at ICLR 2021
Table Macro-Fl scores for temporal event reconstruction in empirical datasets. We highlight in bold the two best scores for each dataset. For baseline models we underline their highest score.
Model
Operator
LYGNSCHOOL
SFHI
LH11
THIERS13
INVSI5
Average
56.4 + 0.4
52.9 0.5
52.3 +:
51.0 = 0.4
52.7 + 0.4
Hadumard
89.7 1: 0.3
86.5
0.3
74.6 0.8
94.7
0.1
94.1
0.1
DYANE
Weighted-L.1
90.2 0.2
$3.3
0.7
94.7
94.4 0.2
Weighted-L2
90.6
81.5 0.5
72.0
95.0 0.1
94.8 0.2
0.4
53.8
56.2 06.2+000 0.6
Avorage
0.5
56.8 0.7
54.8 1.5
404
42.8 0.9
Hadumard
6.
55.1 1.0
52.3 1.6
40.8=12 1.5
43.7 1.0
DYNGEM
Weighted L1
0..4
52.3 0.7
50.9
41.3 1 1.6
44.8 0.9
Weighred-1.2
0.6
47.0 0.8
47.0 1.3
39.2
1.2
43.6 0.6
Concat
0.44
57.8=03
1.7
36.9
Average
51.7
56.9
00.2
U.2
38.1
Hadomard
0.3
68.9
0.5
62.2
64.7 0.3
DYNAMICTRIAD
Weightd-LL
0..1
7233 0.4
75.5
70.8 0.3
78.1 0.2
Weighted-L2
0.4
73.
4.5
72.4 0.2
78.9 0.3
Concal
5..2
53.4 0.3
55.9 1.
55.1
53.2 1 0.3
HOSGNS
Hadamard
98.5 0.1 0.1
98.8 0.1
99.8 0.1
99.6 0.1
99.1 0.1
HOSGNS (dym)
Hadamard
90.3 0.2
80.9 00.9:000 0.4
08.1
93.5
87.2 0.2
HOSGNS (etat dym)
Hadumard
91.8 1: 0.2
86.7
0.4
73.6 0.6
94.3 0.1
89.0 1: 0.2
sampling was implemented by picking positive and negative examples from a corpus of random walks sampled from a given graph. For HOSGNS(sta) random walks are sampled from the set of temporal snapshots (g(*) keT with window size T = 1, and for HOSGN5(dy) random walks sampled from the supra-adjacency graph GN with window size T = 10. With these sampling strategies, positive examples are drawn from the same probability distributions as defined in Eq. (3.5) and Eq. (3.6).
Table 4: Number of trainable parameters and training time of each time-varying graph representation learning model compared between LYONSCHOOL and synthetic datasets. The embedding dimension is fixed to 128. technical specifications of the computing system and hyper-parameters configuration are reported in Supplementary Information.
LYONSCHOOL
OPENABM COVID19
Model
|
242,
[T|
104
[V]
2000, [T]
100
[
5000, T
20
parameters
time
parameters
Tr. time
Tr. parameters
time
DYANE DYNGEM
4,396.544
62s
50,825,472
1.014s
25,591 ,296
448s
459,270
5166
1,867,42
10,765s
4,270.428
23,307s
DYNAMICTRIAD
3,221,632
1,131s
25,600,128
17.191s
12,800,228
12.625s
HOSGNS (xtue)
75,264
316s
$24,800
548s
1,282,560
724s
HOSGNS (dun)
88,576
303s
537,600
565s
1,285,120
734s
We recall that HOSGNS, by learning disentangled representations of nodes and time intervals, uses number of parameters in the order of ([[v)+17) while models that learn node-time representations (such as DYANE) need number of parameters that is at least O(V] [T[). In the Supplementary Information we include plots with two dimensional projections of these embeddings, showing that the embedding matrices of HOSGNS approaches successfully capture both the structure and the dynamics of the time-varying graph.
CONCLUSIONS
In this paper, we introduce higher-order skip-gram with negative sampling (HOSGNS) for time- varying graph representation learning. We show that this method is able to disentangle the role of nodes and time, with small fraction the number of parameters needed by other methods. The embedding representations learned by HOSGNS outperform other methods in the literature and set new ttate-of-the. results for predicting the outcome of dynamical processes and for temporal event reconstruction. We show that HOSGNS can be intuitively applied to time-varying varying graphs, but this methodology can easily adapted to solve other representation learning problems that involve multi-modal data and multi-layered graph representations.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Réka Albert and Albert-László Barabási. Statistical mechanics of complex networks. Reviews of modern physics, 74(1):47, 2002.
Carl Allen, Ivana Balazevic, and Timothy Hospedales. What the vec? towards probabilistically grounded embeddings. In Advances in Neural Information Processing Systems, pp. 7465-7475, 2019.
Hannah Alsdurf, Yoshua Bengio, Tristan Deleu, Prateek Gupta, Daphne Ippolito, Richard Janda, Max Jarvie, Tyler Kolody, Sekoul Krastev, Tegan Maharaj, et al. Covi white paper. arXiv preprint arXiv:2005.08502, 2020.
Animashree Anandkumar, Rong Ge, Daniel Hsu, Sham M Kakade, and Matus Telgarsky. Tensor decompositions for learning latent variable models. Journal of Machine Learning Research, 15: 2773-2832, 2014.
Sanjeev Arora, Yuanzhi Li, Yingyu Liang, Tengyu Ma, and Andrej Risteski. A latent variable model approach to pmi-based word embeddings. Transactions of the Association for Computational Linguistics, 4:385-399, 2016.
Zhenisbek Assylbekov and Rustem Takhanov. Context vectors reflections of word vectors in half the dimensions. Journal of Artificial Intelligence Research, 66:225-242, 2019. 2019..
Alain Barrat, Mare Barthelemy, and Alessandro Vespignani. Dynamical processes on complex nehworks. Cambridge university press, 2008
Ferenc Béres, Domokos Kelen, Róbert Pálovics, and András A Benczúr. Node embeddings in dynamic graphs. Applied Network Science, 4(1):64, 2019.
Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chhan Chang. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Figineerrigg 1069)11616 2018.
Ciro Cattuto, Wouter Van den Broeck, Alain Barrat, Vittoria Colizza, Saan-François Pinton, and Alessandro Vespignani. Dynamics of person-to persoo interactions from distributed rfid sensor networks. PloS one. 5(7), 2010.
Kenneth Ward Church and Patrick Hanks. Word association norms, mutual information, and lexicog- raphy. Computational linguistics, 16(1):22-29, 1990.
Ryan Cotterell, Adam Poliak, Benjamin Van Durme, and Jason Eisner. Explaining and generalizing skip-gram through exponential family principal component analysis. In Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume Short Papers, pp. 175-181, 2017.
Manlio De Domenico, Albert Solé-Ribalta, Emanuele Cozzo, Mikko Kivelä, Yamir Moreno, Mason A Porter, Sergio Gómez, and Alex Arenas. Mathematical formulation of multilayer networks. Physical Review X, 3(4):041022, 2013.
Lun Du, Yun Wang, Guojic Song, Zhicong Lu, and Junshan Wang. Dynamic network embedding: An extended approach for skip-gram based network embedding. In IJCAI, pp. 2086-2092, 2018.
Daniel M Dunlavy, Tamara G Kolda, and Evrim Acar. Temporal link prediction using matrix and tensor factorizations. ACM Transactions on Knowledge Discovery from Data (TKDD), 5(2):1-27, 2011.
Junyi Gao, Rakshith Sharma, Cheng Qian, Lucas M Glass, Jeffrey Spaeder, Justin Romberg, Jimeng Sun, and Cao Xiao. Stan: Spatio-temporaa attention network for pandemic prediction using real world evidence. arXiv preprint 2008.0000 2020.
Lactitia Gauvin, André Panisson, and Ciro Cattuto. Detecting the community structure and activity patterns temporal networks: a non-negative tensor factorization approach. PloS one, 9(1): e86028, 2014.
10

---

Under review as a conference paper at ICLR 2021
Mathieu Génois and Alain Barrat. Can co-location be used as a proxy for face-to-face contacts? EPJ Data Science, 7(1):11, 2018.
Mathieu Génois, Christian L Vestergaard, Julie Fournet, André Panisson, Isabelle Bonmarin, and Alain Barrat. Data on face-to- tocf-ee-eeee contacts in an office building suggest a low-cost vaccination strategy based community linkers. Network Science, 3(3):326-347, 2015.
Palash Goyal and Emilio Ferrara. Graph embedding techniques, applications, and performance: A survey. Knowledge- Based Systems, 151:78-80 94, 2018.
Palash Goyal, Nitin Kamra, Xinran He, and Yan Liu. Dyngem: Deep embedding method for dynamic graphs. In IJCAI Workshop Reprexentation Learning for Graphs (ReLiG), August 2017. URL
httpps:/eee aww.vviiivv.v//aa///ii//aaaaaaia http://.///11011111
Palash Goyal, Sujit Rokka Chhetri, and Arquimedes Canedo. dyngraph2vec: Capturing network dynamics using dynamic graph representation learning. Knowledge-Ban Based Systems, 187:1048 16, 2020.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp- 855-864, 2016.
William Hamilton, Rex Ying, and Jure Leskovec. Representation learning on graphs: Methods and applications. arXiv preprint
2017.
Robert Hinch, William JM Probert, Anel Nurtay, Michelle Kendall, Chris Wymatt, Matthew Hall, Katrina Lythgoe, Ana Bulas Cruz, Lele Zhao, Andrea Stewart, et al. Openabm-covid agent- based model for non-pharmaceutical interventions against covid-19 including contact tracing. medRxiv, 2020.
Petter Holme and Jari Saramäki. Temporal networks. Physics reports, 519(3):97-125, 2012.
Amol Kapoor, Xue Ben, Luyang Liu, Bryan Perozzi, Matt Barnes, Martin Blais, and Shawn O'Banion. Examining covid-19 forecasting using spatio-temporal graph neural networks. arXiv preprins arXiv:2007.03113, 2020.
Tamara G Kolda and Brett W Bader. Tensor decompositions and applications. SIAM review, 51(3): 455-500, 2009.
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, 2019.
Timothée Lacroix, Guillaume Obozinski, and Nicolas Usunier. Tensor decompositions for temporal knowledge base completion. In International Conference on Learning Representations, 2020.
Omer Levy and Yoav Goldberg. Neural word embedding as implicit matrix factorization, In Advances in nearal information processing systems, pp. 2177-2185, 2014.
Taisong Li, Jiawei Zhang, S Yu Philip, Yan Zhang, and Yonghong Yan. Deep dynamic network embedding for link prediction. IEEE Access, 6:29219-29230 2018.
Yitan Li, Linli Xu, Fei Tian, Liang Jiang, Xiaowei Zhong, and Enhong Chen. Word embedding revisited: A new representation learning and explicit matrix factorization perspective. In 24th Int.l Joint Conf. on Artificial Intelligence, 2015.
Pengfei Liu, Xipeng Qiu, and Xuanjing Huang. Learning context-sensitive word embeddings with neural tensor skip-gram model. In Twenty- Fourth International Joint Conference on Artificial Intelligence, 2015.
Yunpu Ma, Volker Tresp, and Erik A Daxberger. Embedding models for episodic knowledge graphs. Journal of Web Semantics, 59:100490, 2019.
11

---

Under review as a conference paper at ICLR 2021
Sedigheh Mahdavi, Shima Khoshraftar, and Aijun An. dynnode2vec: Scalable dynamic network embedding. In 2018 IEEE International Conference on Big Data (Big Data), pp. 3762-3765. IEEE, 2018.
Osman Asif Malik, Shashanka Ubaru, Lior Horesh, Misha E. Kilmer, and Haim Avron. Dynamic graph convolutional networks using the tensor m-product. arXiv preprint 11X1v:1910.07643, 2020.
Naoki Masuda, Mason A Porter, and Renaud Lambiotte. Random walks and diffusion on networks.
Physics reports, 716:1 1-118,,, 2017.
Oren Melamud and Jacob Goldberger. Information -heorry interpretation of the skip-gram negative- sampling objective function. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers), pp. 167-171, 2017. 2017.
Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed representations of words and phrases and their compositionality. In Advances in neural information processing systems, pp. 311 11-31199, 2013.
Mark EJ Newman. The structure and function of complex networks. SIAM review, 45(2):167-256, 2003.
Giang Hoang Nguyen, John Boaz Lee, Ryan Rossi, Nesreen K Ahmed, Eunyee Koh, and Sungchul Kim. Continuous- dynamic network embeddings. In Companion Proceedings of the The Web Conference 2018, pp. 969-976, 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In Proc. of the 20th ACM SIGKDD Int.l Conf. on Knowledge Discovery and Data Mining, pp. 701-710. ACM, 2014.
Jiezhong Qiu, Yuxiao Dong, Hao Ma, Jian Li, Kuansan Wang, and Jie Tang. Network embedding as matrix factorization: Unifying deepwalk, line, pte, and node2vee. In Proceedings of the Eleventh ACM International Conference on Web Search and Data Mining, pp. 459-467. ACM, 2018.
Maja Rudolph and David Blei. Dynamic embeddings for language evolution. In Proceedings of the 2018 World Wide Web Conference, pp. 1003-1011, 2018.
Aravind Sankar, Yanhong Wu, Liang Gou, Wei Zhang, and Hao Yang. Dysat: Deep neural rep- resentation learning on dynamic graphs via self-attention networks. In Proceedings of the 13th International Conference on Web Search and Data Mining, pp. 519-527, 2020.
Anna Sapienza, André Panisson, Joseph Wu, Laetitia Gauvin, and Ciro Cattuto. Detecting anomalies in time-varying networks using tensor decomposition. In 2015 IEEE International Conference on Data Mining Workshop (ICDMW), pp. 516-523, IEEE, 2015.
Koya Sato, Mizuki Oka, Alain Barrat, and Ciro Cattuto. Dyane: Dynamics-aware node embedding for temporal networks. arXiv preprint 190..5990900577, 2019.
Jian Tang, Meng Qu, Mingzhe Wang, Ming Zhang, Jun Yan, and Qiaozhu Mei. Line: Large-scale information network embedding. In Proceedings of the 24th international conference world wide web, pp. 1067-1077, 2015.
Dane Taylor, Mason A. Porter, and Peter J. Mucha. Supracentrality Analysis of Temporal Networks with Directed Interlayer Coupling, pp. 325-344. Springer International Publishing, Cham, 2019. ISBN 778-3-030-234999 9. doi: 10. 10. 030 2200--3395555 17
17. https///: org
Maddalena Torricelli, Márton Karsai, and Lactitia Gauvin. weg2vec: Event embedding for temporal networks. Scientific Reports, 10(1):1-11, 2020.
Anton Tsitsulin, Davide Mottin, Panagiotis Karras, and Emmanuel Müller. Verse: Versatile graph embeddings from similarity measures. In Proceedings of the 2018 World Wide Web Conference, pp. 539-548, 2018.
12

---

Under review as a conference paper at ICLR 2021
Eugenio Valdano, Luca Ferreri, Chiara Poletto, and Vittoria Colizza. Analytical computation of the epidemic threshold on temporal networks. Physical Review X, 5(2):021005, 2015.
Xian Wu, Baoxu Shi, Yuxiao Dong, Chao Huang, and Nitesh V Chawla. Neural tensor factorization for temporal interaction learning. In Proc. of the Twelfth ACM Int.l Conf. Web Search and Data Mining, pp. 537-545, 2019.
Liang Xiong, Xi Chen, Tzu-Kuo Huang, Jeff Schneider, and Jaime G Carbonell, Temporal collabora- tive filtering with bayesian probabilistic tensor factorization. In Proceedings of the 2010 SIAM international conference data mining, pp. 211-222. SIAM, 2010.
Da Xu, Chuanwei Ruan, Evren Korpeoglu, Sushant Kumar, and Kannan Achan. Inductive repre- sentation learning on temporal graphs. International Conference on Learning Representations, 2020.
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 2018.
Xiu-Xiu Zhan, Ziyu Li, Naoki Masuda, Petter Holme, and Huijuan Wang. Si-spreading- based network embedding in static and temporal networks. arXiv preprint arXiv:200.006750, 2020.
Ziwei Zhang, Peng Cui, Jian Pei, Xiao Wang, and Wenwu Zhu, Timers: Error-bounded svd restart on dynamic networks. In Thirty-Second AAAI Conference Artificial Intelligence, 2018.
Lekui Zhou, Yang Yang, Xiang Ren, Fei Wu, and Yueting Zhuang. Dynamic network embedding by modeling triadic closure process. In 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 in dynamic social networks. IEEE Transactions Knowledge and Data Engineering, 28(10)) -77777 2711.
13


Reviews:
[{"review_id": "sIRrOR01MZ_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "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:\n========\nThe paper proposes an implicit tensor factorization approach for learning time-varying node representations over dynamic networks.  The core method lifts the well-known skip gram based embedding approach from matrix to higher order tensors to support temporal dimensions. The authors claim that such tensor based treatment allows to disentangle the role of node and time. Negative sampling method ( similar to noise contrastive estimation) is extended the higher order tensor setting and incorporated in the cross entropy objective for training. In the experiments, the authors consider five variants of face-to-face proximity data that contains temporal interactions and focuses on tasks of node classification (predicting outcome of SIR epidemic process) and link prediction (in the form of event reconstruction). The proposed method has been compared against two discrete time graph representation learning model and a recently proposed tensor based method. The authors claim that the provided method shows comparable performance with requirement to train lesser number of parameters. Also, the authors provide qualitative analysis in terms of embedding visualizations and goodness of fit plots. \n\n\nStrengths:\n========\n- The paper focuses on an important problem of representation learning for time-varying graphs as several real-world networks consist of interactions between nodes that occur and change over time. The higher-order skip gram based method proposed by the authors promises better parameter complexity compared to other methods while retaining or exceeding previous empirical performance.\n- Both the high level tasks of predicting outcome of epidemic process and event reconstruction are useful and important realizations of basic node classification and link prediction tasks respectively in the time-dependent setting.\n- The authors show that the method provides significant empirical performance on both tasks compared to non-tensor based methods and comparable performance to recently proposed approach in [4].\n- I find the qualitative analysis provided by the authors in the appendix in terms of embedding visualization, execution time, goodness of fit and other ablations to be very insightful\n\nConcerns and Improvements:\n=========================\n- One of the major concerns I have is the novelty of the overall approach. Both skip gram embedding and negative sampling based training is well-known approach. While the authors claim that their key contribution is to use these techniques for higher order structures than a matrix. However, skip-gram type of methods with negative sampling for 3-order tensor have been well studied in relational learning literature [1] for static case. This has also been extended to 4-order tensor to consider temporal dimension and presented in previous ICLR [2]. Hence, the novelty of the technical contribution is not very clear. One of the novel part seems to be learning different representations of node and time. But I could not see how this is more helpful than previous approaches. The author needs to adequately discuss and analyze this and present the outcome in the scenario when they only learn one of the two representations. \n- In addition to comparing with the relational learning literature (static and dynamic) both in terms of empirical performance and methodological difference, the authors also miss comparison with a recently proposed tensor based representation learning method for dynamic networks [3]. The paper needs to compare with all these methods and distinguish the technical differences to exactly discern the value of the presented approach. \n- The third major concern is the author’s claim on the requirement to use lesser number of parameters. I do not find enough evidence in the paper to support this claim. The author need to exemplify the difference in the number of parameters for particular case compared to DyANE and other methods (see Table V in [1] for example). Also it is important to test how these lesser number of parameters affect the empirical performance. Finally, the execution times in Table 1 do not seem to show any speedup gained due to these less number of parameters. Can the authors discuss more on these effects of lesser number of parameters in addition to retaining performance of DyANE and also compare this with other methods I mentioned above? \n- As a follow-up, most experiments are done on graphs with few hundred nodes while real-world networks contains thousands and even more number of nodes. I am not able to see how this method would scale to such large graphs. Does the improvement in parameter complexity above help to promote scalability? Or Is this a limitation of the proposed approach?\n- From my understanding, the authors use the warm-up effect for finding a good initialization of the parameters. However, the gap shown in Figure 1 in Appendix for warm-up vs non warm-up case is concerning as it appears that majority of the performance gain (especially considering only marginal performance increase over DyANE) is achieved due to warm-up steps and less due to the effect of the training via negative sampling. \n- Overall the paper reads very dense and needs an improved presentation. Specifically, the concepts explained in Section 2 and 3 can be better presented using figures to explain the details such as cross coupling (see Fig 1 in [4] for an example)\n- While the authors present better performance for the proposed approach in the experiment section and also provide qualitative analysis in the appendix, it is also important for the authors to discuss and analyze the reasons behind the performance gain with this method in the text in addition to describing the results from the table.\n\nMinor Points not affecting the score:\n===============================\n\n- I find the overall performance increase over DyANE to be marginal and while this is not a major concern in itself that has affected my score for the paper, the authors need to provide more comparisons and distinguish their approach from DyANE with better analysis in terms of parameter complexity  to fully support their claim of better performance.\n- Minor type - below equation 3.2, should it be P_N(i,j,k)? It seems i and its corresponding term in RHS is missing.\n\nGiven the concerns above, I currently do not find this paper ready for publication. I will be happy to revisit my score based on the author’s response to the concerns raised by me above. \n\nReferences:\n==========\n[1] A Review of Relational Machine Learning for Knowledge Graphs, Nickel et. al. 2015\n\n[2] Tensor Decompositions for Temporal Knowledge Base Completion, Lacroix et. al. ICLR 2020\n\n[3] Dynamic Graph Convolutional Networks Using the Tensor M-Product, Malik et. al. 2020\n\n[4] DyANE: Dynamics-aware node embedding for temporal networks, Sato et. al. 2020\n\n\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "Q-fhXJOr3T3", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "Clarity: The motivations of learning representations for  time dependent proximity graphs generated from contact tracing are well explained. The learning of two disentangled representations to capture topological structure and temporal dynamics information is clearly demonstrated.\n\nNovelty: The paper extends a previous proof by Levy and Goldberg, about how Mikolov’s SGNS is implicitly factorizing a word-context matrix, to higher order tensors . This higher order generalisation applied to time-varying graphs is used to learn embeddings, which are shown to effectively encode graph structure and dynamics.\n\nImpact: The paper proposes an extension of a previous well known proof for higher order tensors, which leads to an embedding technique which is shown to perform well on real world datasets\nThe code and datasets have been made freely available.\n\nCorrectness: Several experiments have been conducted to demonstrate effectiveness of learned embeddings\nTheoretical groundwork for the proposed model has been well laid.", "extra_scores": {}, "extra_text": {}}, {"review_id": "4ivEj_CXxm", "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": "Main Idea\n\nIn this paper, the authors studied the problem of time-varying graph embedding problems. The authors generalized skip-gram based graph embedding method to time-varying graphs. The authors show that the method can be used to factorize time-varying graphs as high-order tensors via negative sampling. The authors carried out experiments on several time-resolved proximity networks with comparison to several state-of-art baselines.\n\nStrength\nThe paper is well written and technically sound. The authors provided theoretical analysis for the approximation of negative sampling to tensor factorization.\nThe authors carried out extensive experiments on several real-world networks with comparison to strong baselines. The application of SIR node classification task is very interesting.\n\nWeakness\nThe proposed method does not utilize the special property of time-varying graphs. In the equation (3.1), the positive instances are just single edges while the negative are just for independent marginals. It is not clear how random walk is involved in this setting.\nThe proposed method is more like an acceleration to traditional tensor factorization method for time-varying graphs. In this case, the authors should (1) include tensor factorization baselines to compare the accuracy and (2) carry out experiments on efficiency comparison with classic tensor factorization methods.\nThe scalability of the proposed method is another concern. The largest network the authors experiment with has ~200 nodes. It will be good to see scalability experiments for example on synthetic networks.\nFor the evaluation of temporal event reconstruction. It would be better to use time to separate train/test. Also, it would be better to include some simple static graph embedding baseliness to operate on the network with all time-step graphs combined.\n\nDetailed comments:\nLine below equation (2.1), please provide definition for vol(G). \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "1DKRqbqrGW3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "In this paper, the authors propose learning node embeddings of time varying graphs. They extend the ideas from Skip Gram Negative Sampling (SGNS) to time varying graphs. They extend the relationship between SGNS and Matrix Factorization to a tensor setting. The key contribution seems to be learning a static embedding for each node and an embedding for a time step. These embeddings are combined to learn a time-aware node embedding. Experiments on multiple datasets show that the proposed method outperforms related benchmarks. \n\nThe paper is well written, and easy to follow. My main concern is with the degree of novelty. I think the work is relevant, but am not convinced that the novelty is sufficient to warrant acceptance. It seems a rather straightforward extension of SGNS as well as the idea that the shifter PMI matrix can be factorized, to a tensor. The datasets the authors use are also quite small, so I'm not convinced that the method is scalable. Indeed, scalable tensor factorization is a challenging problem. It's unclear what the authors gain by casting this as tensor factorization, rather than just solving the SGNS problem like in word2vec. Infact I think that's basically what (3.8) does. \n\nadditional comments:\n- p3: what's \\omega(i, j, t_0)?\n- sec 3.1 paragraph 2: \"obtained by collecting co-occurrences...\" : Can the “jump” in T be arbitrary? How are the (i, j, k) tuples constructed specifically?\n- from Table 1: These datasets are quite small. Is there a note on scalability? How large can you go?\n- From table 3: The results from HOSGNS are significantly better (sometimes 99%) compared to the baselines. Can you provide some intuition as to why this is? what explains the large jump?\n- for the task in Table 3, it seems the (stat) version of the model works a lot better, and adding (dyn) actually makes it worse. Does that mean edge detection is hampered by taking time into account? An explanation would be good. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is concerned with learning representations for time-varying graphs which is an important problem that is relevant to the ICLR community. For this purpose the authors propose a new method to extend skip-gram with negative sampling to higher-order tensors with the goal to perform an implicit tensor factorization of time-varying graphs.The proposed approach shows promising experimental improvements compared to previous methods. Reviewers highlighted also the tasks considered in the paper as well as the theoretical and qualitative analysis as further positive aspects.

However, there exist still concerns regarding the current version of the manuscript. In particular, reviewers raised concerns regarding the novelty of the approach (SGNS, its extension to higher-order tensors, as well as the connection to PMI have been studied in the literature). As such the new technical contributions are limited. Reviewers raised also concerns regarding the scalability of the method and its applicability to large graphs. The revised version addresses this concern to some extent by showing experiments on mid-sized graphs with 2000/5000 nodes. While this clearly improves the paper, I agree with the majority of the reviewers that the manuscript requires an additional revision to iron out the points raised in this round of reviews. However, the presented results are indeed promising and I'd encourage the authors to revise and resubmit their work considering the reviewers' feedback.
Decision: Reject