Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper aims to directly model the edges in temporal networks instead of indirectly inferring edge embeddings by computations from nodes. To achieve so, the paper constructs Time-Decayed Line Graphs (TDLGs) to use each node to represent the edges, and weigh the edges between resultant nodes based on differences in time. Such modeling avoids the assumption of discretized time info. Theoretical analysis is provided to ensure the proposed edge modeling can recover original nodes based on the stochastic block model (SBM). 

strength_and_weaknesses: Strength:

Overall the paper has good clarity in the problem statement. The novelty is stated clearly.  

Weakness:

W1: The motivation of why edge embedding needs to be improved is unclear to me. It is stated that edge embedding has seen less interest, while it does not make a strong and effective motivation. 

W2: The related work and baseline approaches are papers proposed in year 2019 or before. It would be better to include more recent papers to have a better reflection on the novelty of this paper.  

clarity,_quality,_novelty_and_reproducibility: The paper introduces the problem clearly and has clear contextual structure. 

The motivation of why edge embedding needs to be improved is unclear to me. It is stated that edge embedding has seen less interest, while it does not make a strong and effective motivation. 


Is $\lambda$ in Proposition 4.1 a typo? Should be $\gamma$?

The time scale hyperparameter $\sigma_{t}$ is important and is chosen by informal tuning. Can you explain informal tuning?


The proposed approach provides a novel way of modeling edges in temporal networks. 

The related work and baseline approaches are papers proposed in year 2019 or before. It would be better to include more recent papers to have a better reflection on the novelty of this paper.  


The reproducibility of this paper is good since a code demo is provided.

summary_of_the_review: Overall, the paper is well written and the contents are self-contained. The motivation and the lack of more recent related work are the two main issues.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper discusses how to embed the edges of temporal networks. It proposes to create line graphs weighed by Gaussian weight decay and to use the row vectors of the adjacency matrix of the line graph as the embeddings of the edges. The experimental results show that the proposed method performs better in edge classification tasks and link prediction tasks than other methods that discretize the time stamps of the datasets.
strength_and_weaknesses: Strengths:

- The idea to utilize line graphs in data mining tasks has been discussed in a lot of papers such as [1], and it seems straightforward to weigh the line graph according to time decay between edges; however, to my knowledge, there has been no work that shows such simple method can surprisingly outperform other methods that discretize the time stamps.
- This paper is well-organized and clearly written. It is easy for readers to follow.

Weaknesses:

- The discussion and evaluation related to the time/space complexity are not provided enough. Because the embedding vectors have fundamentally extremely high dimensionality, the computation of the downstream tasks will be affected by the sparsity of the vectors, which depends on the size and fraction of hub nodes in the original graph. Moreover, the computation cost of eigendecomposition should be discussed more including how to update the eigendecomposition in the time-evolving graphs.

[1] Ahn, YY., Bagrow, J. & Lehmann, S. Link communities reveal multiscale complexity in networks. Nature 466, 761-764 (2010).

clarity,_quality,_novelty_and_reproducibility: Clarity:

- This paper is clearly written and easy to read.

Quality:

- This paper is well-organized.

Novelty:

- Despite the idea to utilize the row vectors of the line graphs with time-decayed weight being straightforward, there has been no work that shows such a simple method surprisingly works well.

Reproducibility:

- Readers can easily implement the proposed method.

summary_of_the_review: This paper is well-organized and clearly written. Despite the idea to utilize the row vectors of the line graphs with time-decayed weight being straightforward, there has been no work that shows such a simple method surprisingly works well. A downside is that this paper does not provide enough discussion and evaluation of time/space complexity.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: Edge embeddings and continuous time have not received as much attention as the alternatives between these two categories, and this paper takes an edge-first approach to temporal graph edge embeddings. The paper introduces a simple strategy to obtain these, justifying several useful aspects of their strategy. A demonstrative example is given to share intuition with the readers, which is followed by theoretical insights on the methodolgy. Following the related work section, empirical analysis is performend, where the proposed method beats several baseline methods. Given that this paper is focusing on a niche, I'm not sure if any method can be considered SoTA. Empirically, the proposed method ran to conlusion over all datasets, whereas some baseline methods did not. 
strength_and_weaknesses: Pros: 
+ Simple methodology that seems to make a lot of intuitive sense. I found the demonstrative example rather compelling given its simplicity and clear outcomes. I think I would have valued (for comparative purposes) examples of baselines
+ Experimental results look good, both in terms of accuracy and runtime. They seem to dominate the baselines considered. 

Cons: 
- The edge weight function, being an RBF kernel, is 'opinionated' as to the nature of the weighting function. I would imagine that a richer function class (even a NN) could allow much richer relationships to be learnt in a data driven manner. Is this a weakness? I would have liked abalation studies with other weight functions, such as those mentioned previously. 
- I didn't see a strong connection between the theoretical analysis and evaluation. In particular, the reduction of the time variance to 0 in the analysis seems to me to implicitly discretise the context of the analysis, and its conclusions have (I believe) very weak links to the continuous time problem. 
- I am curious about spectral interpretations of this construction, particularly regarding the specturm of the edge adjacency matrix. 
- In hyperparam selection section, I would value clarification on what fraction of training data was used for valudation. The authors explicitly train and test sets, but not validation. 

Additional questions: 
- Why is escorts sensitive to the time scale hyperparameter and the others aren't? 
- Why is it that normalisation hinders the classification performance? 
- The method seems so simple that I'm surprised it hasn't been elucidated before. 
- The structure of your adjacency matrix (Eq (1)) looks similar to the product of two kernels (linear kernel and an squared exponential kernel). I wonder if theory could be borrowed from the kernel and / or Gaussian processes literature to help with the understanding of the domain here? 
clarity,_quality,_novelty_and_reproducibility: - The writing was clear, easy to follow and logical. I appreciated the explicit example given after exposition of their framework since it helped me gain a fast intuition about the problem. 
- I'm not expertly familiar with the relevant citing literature, so am unsure about the novelty of the work in the context of the relevant literature. A major strength of this is the simplicity of the work, but it seems unlikely to me that it wouldn't have been considered before. 
- The results are strong and convincing. I think this is a major strength of the work. 
- The writing is very clear. 
- I think the work is reproducible. However, I didn't see mention of an implementation repository which hinders fast and easy reproduction. 
- I didn't find the theory too convincing mainly because of the strong assumptions that are associated with it. I am not certain about my position, but I didn't see the connection between the theory and the practical results either. 
summary_of_the_review: This paper introduces a straightforward approach to edge embeddings of temporal graphs. The proposed approach works very well according to the empirical results. I also find the similicity of the approach to be a strength rather than a weakness of the paper, though, not being an expert in this area, I would be surprised if this didn't exist elsewhere. I appreciated the theoretical analysis, but I am wary of some aspects, particularly that the assumptions (esp. the zero time variance) means the analysis is more suitable discrete rather than continuous contexts, which is not the focus of this paper. If other reviews, or the authors, can ratify the theory and novelty of the contribution I would be willing to increase my recommendation.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper is about edge representation learning in continuous temporal networks. The proposed method (TDLG) starts with the construction of the line graph which converts each edge to a node and connects interactions that share the same endpoint node.Then, the edge weights in the line graph are calculated based on  the time differences between interactions, with interactions that happen closer in time to have higher weights. The line graph then represents both topological proximity and temporal proximity. Efficient classical methods can then be applied to the line graph. The authors of this paper propose the temporal stochastic block model (TSBM), which naturally extends the stochastic block model for static networks to temporal networks. The results contain a comparison of six state of the art models to the proposed TDGL on five real world datasets. The focus is on two downstream tasks: the temporal edge classification task and the {inter/extra}-polative link prediction task. The TDGL in most cases outperforms all other comparison methods. There is also discussion about the runtime improvement, the hyperparameters and in the appendix a full report on the results can be found.
strength_and_weaknesses: Strengths:
- The paper is well-structured and well-written. The paper is easy to follow and the flow is great.
- The authors have done a good job with the related works; they have organized most of the state of art methods and they discuss about the limitations and the challenges of each category which also gives motivation for the proposed model and setup.
- All figures and tables are well-thought and designed. The authors make the best out of the 9 page limitation.
- The demonstrating example and the theoretical discussion give the reader the extra proofs and background needed for this methodology.
- The results are very promising and show that the proposed method outperforms the six comparison models in five datasets in both edge classification and edge prediction tasks.
- The runtime results also show that the proposed method reduces the runtime, while increases the performance, and it also highlights that a simpler method can have comparable or better performance to other more complicated methods.

Weaknesses:
- The novelty of the work is incremental.
- The fact that it is proposed to create the line graph using the continuous stream of timestamps information as weights is not fully convincing on how this is continuous and not discrete time related information. Maybe more explanation and justification is needed in that part.
- It would be interesting to see all the models that appear in Table 1, in the comparison methods in the experimental setup.
- Do the train/test split percentages refer to the number of days? Can later days appear in the train set and earlier days in the test set? How do the authors do 10 trials with 10 random splits given that the time has the concept of order in it?
clarity,_quality,_novelty_and_reproducibility: The proposed idea has some novelty. The paper is well-structured and well-written. The figures and the tables support the text and are well done. The authors provide a demo python notebook ready to use in the supplementary material for reproducibility. All datasets used are publicly available.
summary_of_the_review: Overall, this is a well-written paper, the quality of the work and the presentation is high. The proposed method is simple with incremental novelty, but it outperforms all other comparison state of the art models in five datasets and has a shorter runtime. The authors have done a great job describing the proposed method, and also in the experimental design and implementation.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper proposes to directly model feature embeddings from a line graph. The line graph is comprised of nodes as the original temporal edges, and new set of edges between the line graph nodes are captured by interactions between the original temporal edges.

The paper addresses critical ML application in the context of dynamic graph structures that is changing as time evolves, and how to conduct representation learning for such dynamic structures. The limitation of discretization of the time dimension is addressed and a great reduction in runtime compared to other state of the art methods are also demonstrated. The resultant method is simple yet effective, and resembles classical methods in recommendation systems which also adopts the weight adjacency matrix to derive embeddings.
strength_and_weaknesses: Strength:
- Well written paper. The paper states its core contributions clearly and directly aims to address related works limitations. As a result, the readers would have a relatively easy time to understand the concepts and proposals written in the article.
- Extensive experimental studies. The author supported their work with a large set of experiments centering around node classification on a variety of datasets. I appreciate the effort.
- Ablation study. I appreciate the model study conducted on synthetic dataset, and showcasing TDLG's ability to learn the global structure of the graph.
- Very fast runtime of this method compared to the related works.

Weakness:

- Graph structure's enormous scale. The original graph with O(NT) nodes, where N is number of nodes and T is number of time steps, would be constructed as O(N^2 T) nodes, which is a quadratic scale. As is shown in table 2, the #edges are typically much larger than the #nodes, thus rendering heavy memory pressure of the model runtime. However, this weakness is partially offset by its fast runtime. But this limitation makes the model hard to deploy on edge devices.

- Reliance of global graph structure. Based on section 2's experimental setup explanation (Temporal edge embedding and classification, Temporal link prediction), the model proposed in this paper relies on adjacency matrix A's row as its input feature to predict the edge class. This creates a limitation that the training and inference has to be operated on the same graph. Whereas, the test data coming from a different graph structure will make this method infeasible. My main concern is that the neural net training/testing on the same graph is not actually learning signatures of edges, and that how those edges are interacting with its important neighbors, but rather implicitly learning the training graph’s full topological information, thus making the inference on test set much easier, at the cost of poor generalizability on unseen graphs. Note, the models ability on learning the global graph structure is supported by the author's model study experiment in section 3,4, see figure 2.

- Reliance of global graph structure cond. However, I understand certain applications may actually favors this setup, i.e. recommender systems. As such, let us relax my argument by a little bit and assume we always operate on the same global graph. Then, if we have an unseen edge during test time, and we have no such row in the matrix A. In order to compute its feature, we have to rely on the set of training edges to acquire a relationship row vector between the test edge to all train edges. Our feature set is then limited/bounded by those training edges. However, the test edges can formulate interactions with edges that are not found in the training set, and we will not be able to acquire those features. This is a critical limitation, and this is also the core reason why cold start is always a tricky and heated topic in recommender systems.

- Reliance of global graph structure cond. That being said, I would be interested to see if the authors could compute localized embedding computation based on neural functions between nodes, and use them for edge classification tasks. For example, one could use graph attention networks [1], or spectral graph convolution kernels [2][3] to compute node embeddings on the line graph, thus constituting a valid representation of the temporal edge in the original graph. When this method is equipped with localized embeddings, we can train on a set of graphs and eval on unseen graph structures without issues. 

- Experimental results are not completely fair. Most of the related work, for example evolve GCN is not depending on the global graph structure, thus being able to generalize to unseen graphs. When comparing to those kind of more generalizable work, this paper intrinsically has an advantage: it leverages the global graph structure and will not work if it is tested on an unseen graph. This is probably a good reason why this method is performing on 90% level across the board while the related works only performs at 70% level. In addition, figure 4 hints that when the access to global graph structure is impaired (when we only use 128 eigenvector's projections), the model's performance is severely hindered.


[1] Graph attention networks. https://arxiv.org/abs/1710.10903
[2] Spectral graph convnets. https://arxiv.org/abs/1606.09375
[3] Spectral localized kernels on point clouds. https://arxiv.org/abs/1803.05827

clarity,_quality,_novelty_and_reproducibility: See strength and weakness.

summary_of_the_review: At the present form of the paper, I am discouraged to recommended it with high ratings due to the limitation of its reliance on the full graph structure being consistent for training and inference time. Granted, there are applications scenarios that favors this setup, but it is indeed a limitation for generalizable representation learning.

The experiments and evaluation process are also compared against more generalizable methods which could operate on unseen graphs during test time, thus creating an unfair comparison. I would be more convinced if the compared methods are also operating on the same graph throughout and leveraging the global graph structure during its learning process.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper provides an interesting approach for generating link embeddings in temporal graphs, which is converting the graph into a line graph and connecting edges (now nodes), based on the temporal difference they have in the initial graph. They show that with this representation, the adjacency matrix representation is enough to achieve very strong performance in edge prediction and classification. The method is simple and seems to outperform the state of the art representation learning models by a significant margin.  
strength_and_weaknesses: The performance gain is impressive and the proposed model is simple and intuitive.

However, key related works are missing, e.g. TGN: TEMPORAL GRAPH NETWORKS FOR DEEP LEARNING ON DYNAMIC GRAPHS

There are also not much discussion on DTDGs and how this method performs on them.  
Some of the claims might also not be correct [although said differently in different parts of the paper]. For example, there is a statement in the abstract that "First, time is assumed to be discretized, so if the time data is continuous, the user must determine the discretization and discard precise time information", while there are many methods for continues times graphs and some recent work explicitly discuss the relation CTDG and DTDG models (this is recent so of course not listing it as a missing reference but more as a reference to see https://arxiv.org/pdf/2209.15059.pdf). This is later expanded and corrected in text, but the sentence in abstract can be rephrased. 

The argument that node to edge embedding is suboptimal seems weak given the proposed method needs a vector of length m, m being the number of edges. There is an attempt to make it smaller with SVD but performance drops. 

The only parameter the model has is a hyper parameter tuned informally, so the although performance is good, this is not much a representation learning. 
clarity,_quality,_novelty_and_reproducibility: It is well written paper and easy to follow. However some parts could be explained better, e.g., explain the class imbalance of datasets in the edge classification task.


summary_of_the_review: Simple way for edge representation in temporal graph, with no learning, that performs significantly better than the baselines. It seems not practical given the size of representation is number of edges in the graph.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors present a simple framework to address two issues with learning on temporal networks: (1) manual discretization of time disregards precise time information, and (2) in general, representations of nodes are returned instead of edges, making it suboptimal for edge-classification tasks. They propose a method that constructs the line graph of the network and set the edge weights based on the differences in time between the edge-interactions. This new graph represents topological proximity (existence of the edges) and temporal proximity (weights of the edges). This appears to be the first method that directly constructs embeddings for continuous-time temporal edges without aggregating node embeddings. The method is simple and intuitive. For theoretical analysis, the authors introduce a data model, called the temporal stochastic block model (TSBM), a temporal variant of the popularly studied SBM. The method is also easy to implement and is shown to perform better than prior methods in experiments on five benchmark real-world temporal networks.
strength_and_weaknesses: ### Strengths
1. The paper is easy to follow and well-written.
2. The proposed method is easy to implement and simple to understand, yet, is shown to perform better than prior methods via an extensive set of experiments.
3. Theoretical discussion is apt and provides the relevant intuition behind the method very cleanly.

### Weaknesses
1. The theoretical discussion is limited to a very bare-bones TSBM. The requirement of zero time variance in the results is not well-justified.
2. I believe there is a missing discussion on spectral methods for multi-graph community detection where multiple graphs are given, and one is supposed to figure out the community structure. From a theoretical standpoint, I don't see a difference between the temporal problem and the multi-graph problem. A brief discussion with references would be nice. In particular, the survey "Abbe, E., 2017. Community detection and stochastic block models: recent developments. JMLR, 18(1), pp.6446-6531" is a good reference.

### Questions and Feedback
1. [Def 3] Could you justify taking the time values in the two periods to be Gaussian? It seems that a primary motivation was to not have to discretize time. However, saying "two" periods but taking the values to be Gaussian still in some sense makes me think that the time values are discretized. I'm thinking that: Gaussians have nice tails, so they are essentially their mean (concentration), then in this regime how is the model different from one where time is discretized?
2. [Fig 1] The toy example of TSBM is very intuitive. However, it might be good to add why spectral methods are not applicable to this problem. In the setup of the figure, looking at, for example, the second eigenvector of the adjacency matrix of the graphs in both time periods separately might also work (will give community labels, where one can combine the two sets of labels in a clever way to obtain more confidence). Does the sparsity of the graph play a role here? I'm thinking that if the graph is very sparse, then spectral methods won't work.
3. [Proposition 4.1] Do $\lambda$ and $\gamma$ denote the same thing?
4. [**Important**] Why do we need time variance $0$ for the theoretical results, i.e., both Prop 4.1 and 4.2? Can you provide a brief sketch for how the proof will go for non-zero variance? I believe something can be done since it's Gaussian, otherwise, why take Gaussian to begin with? Shouldn't the definition simply say that you are taking two discrete times $\mu_1,\mu_2$ for the two periods instead of Gaussian?
clarity,_quality,_novelty_and_reproducibility: The problem is well-motivated and the empirical part of the paper is substantial. The results look promising. I believe the results are original, clearly stated, and described well along with the intuition behind the method.
summary_of_the_review: Solid empirical results. Slightly lacking theoretical arguments with very strong assumptions (zero time-variance). I believe this could be a good contribution.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: The authors propose an approach for computing edge embeddings in temporal networks evolving in continuous time. By considering direct embeddings of edges rather than nodes, the authors claim that they can achieve better accuracy on downstream tasks such as edge classification. The proposed edge embedding uses a time-decayed line graph (TDLG) constructed from the original temporal network. The authors demonstrate impressive gains over other temporal network embedding methods for edge classification and link prediction on several real networks. They also present some theoretical analysis on their proposed embedding approach.
strength_and_weaknesses: Strengths:
- Highly creative and simple approach. While line graphs have previously been used in various network science applications, the proposed time-decayed line graph (TDLG) representation appears to be novel. The edge embedding is simply a row of the TDLG adjacency matrix.
- The authors prove that their proposed embedding can separate nodes in different communities in a simplified temporal stochastic block model (TSBM).
- Strong performance in experiments compared to recent temporal network embedding methods, with better accuracy while maintaining low runtime due to the simplicity.
- Top-notch presentation--very well written and a joy to read. Thank you!

Weaknesses:
- Theoretical analysis applies only to the expected adjacency matrix and also assumes no variance in the edge timestamps. While this is a good start, it is too simplistic to be of practical use. As the authors suggest, the results could likely be extended to the sampled setting using concentration inequalities for matrices. This type of analysis was conducted on the Community Hawkes Independent Pairs (CHIP) model--another type of temporal SBM model involving Hawkes processes. See Arastuie et al. (NeurIPS, 2020) for more details.
- Naming the demonstrative example in Section 3 a "temporal SBM" is somewhat misleading. There are lots of different probabilistic generative models for temporal networks in the literature that can be considered temporal SBMs, including the CHIP model and even older work such as the Hawkes IRM (Blundell et al., NeurIPS 2012). I suggest the authors to pick a more specific name for their proposed simple model and add references to other work on temporal SBMs.

References:
- Arastuie, M., Paul, S., & Xu, K. S. (2020). CHIP: A Hawkes process model for continuous-time networks with scalable and consistent estimation. In Advances in Neural Information Processing Systems 33 (pp. 16983-16996).
- Blundell, C., Heller, K. A., & Beck, J. (2012). Modelling reciprocating relationships with Hawkes processes. In Advances in Neural Information Processing Systems 25 (pp. 2600-2608).

Questions:
1. In the specification of the temporal SBM, it appears that the number of temporal edges is fixed to $\Delta \cdot n/2$. This does not match with the usual definition of the SBM, where the number of edges is not fixed but the probability of forming an edge between any two communities are fixed. This is analogous to the difference between a $G(n,m)$ and $G(n,p)$ random graph model. How are you fixing the number of edges while maintaining community structure?
2. One disadvantage of using line graphs is the large size of the adjacency matrix they generate, which requires lots of memory to store even using sparse matrices. It appears that your TDLG also has this disadvantage. How much main memory is required to conduct your experiments, especially on the large Epinions data? Do you further sparsify your TDLG in any way, e.g., by removing edges with weights below a certain threshold?

Typos and minor issues:
- A figure showing the time-decayed line graph for a toy example would be helpful to illustrate the construction of a time-decayed line graph. I was already familiar with line graphs before reading this paper, so I had no problem understanding the definition, but I suspect many readers may not have previously seen line graphs. To create some room, I suggest moving the proof of Proposition 4.1 also to the appendix.
- The use of $\sigma_1, \sigma_2$ in the temporal SBM is potentially confusing given the use of $\sigma_t$ for the Gaussian decay. I would suggest changing $\sigma_t$ to a different symbol.
- I think there is some notation inconsistency in Proposition 4.1. $\gamma$ is defined but never used, and $\lambda$ is used in the Kronecker product but not defined.

clarity,_quality,_novelty_and_reproducibility: - Clarity: Very High. An absolute joy to read! I have only a few suggestions to improve the presentation above.
- Quality: High. I noticed only some minor issues with notation. The experiments are sound. The theoretical analysis is a bit simplistic.
- Novelty: Very High. This is the first approach I have seen for edge embeddings in temporal networks, and it involves the creation of a time-decayed line graph, which is also a novel concept.
- Reproducibility: Very High. Between the attached Jupyter notebook in the supplementary material and the descriptions in the paper, I am confident that I could reproduce the results. The simplicity of the proposed approach helps further here--there is no dependency on tons of additional libraries.

summary_of_the_review: The authors have proposed a highly novel and simple approach for temporal network embedding. The simplicity enables theoretical analysis of the model. It also has very strong empirical performance. I could see this paper having tremendous impact on the ever-growing community interested in graph embeddings. It could also inspire more useful rigorous analysis of the proposed model. I strongly support this paper for acceptance!
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The authors propose a new model for temporal network. The key idea behind the paper is to design a linearization of the evolution of the graph. In this way they can avoid standard shortcoming of previous techniques. In particular, they introduce a Time-Decayed Line Graphs (TDLGs) representation that can be used to weigh the edges between nodes based on differences in time.

The proposed model is simple but it has good experimental performances. In addition, the authors also provide theoretical results showing some nice properties of their technique.

Overall, the paper would be an interesting contribution to the ICLR program.
justification_for_why_not_higher_score: The problem studied is a bit niche and it may not be of interest for a wider audience. The theoretical results are nice but not particularly strong or surprising.
justification_for_why_not_lower_score: The paper study a natural problem and introduce a novel idea. The paper contains both nice theoretical and empirical results.
Decision: Accept: poster