Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: 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.

Novelty: 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.

Impact: 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
The code and datasets have been made freely available.

Correctness: Several experiments have been conducted to demonstrate effectiveness of learned embeddings
Theoretical groundwork for the proposed model has been well laid.
review_title: A good paper in terms of both theory and practice.

final_score: rating: 4: Ok but not good enough - rejection
review_content: Summary:
========
The 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. 


Strengths:
========
- 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.
- 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.
- 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].
- 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

Concerns and Improvements:
=========================
- 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. 
- 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. 
- 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? 
- 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?
- 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. 
- 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)
- 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.

Minor Points not affecting the score:
===============================

- 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.
- 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.

Given 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. 

References:
==========
[1] A Review of Relational Machine Learning for Knowledge Graphs, Nickel et. al. 2015

[2] Tensor Decompositions for Temporal Knowledge Base Completion, Lacroix et. al. ICLR 2020

[3] Dynamic Graph Convolutional Networks Using the Tensor M-Product, Malik et. al. 2020

[4] DyANE: Dynamics-aware node embedding for temporal networks, Sato et. al. 2020







review_title: Interesting topic and empirical tasks; useful qualitative evaluation but lacks novelty, adequate comparisons and requires improved presentation

final_score: rating: 5: Marginally below acceptance threshold
review_content: Main Idea

In 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.

Strength
The paper is well written and technically sound. The authors provided theoretical analysis for the approximation of negative sampling to tensor factorization.
The 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.

Weakness
The 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.
The 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.
The 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.
For 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.

Detailed comments:
Line below equation (2.1), please provide definition for vol(G). 

review_title: Official Blind Review #3

final_score: rating: 5: Marginally below acceptance threshold
review_content: 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. 

The 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. 

additional comments:
- p3: what's \omega(i, j, t_0)?
- 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?
- from Table 1: These datasets are quite small. Is there a note on scalability? How large can you go?
- 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?
- 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. 

review_title: Official Blind Review #2

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