Recurrent Temporal Revision Graph Networks

Summary

Temporal graphs are more accurate for modeling real-world scenarios compared to static graphs, but the current approach of extending neighbor aggregation from static graphs to temporal graphs is computationally expensive when considering all historical neighbors. To address this, the authors propose a novel framework that uses recurrent neural networks with node-wise hidden states to integrate information from all historical neighbors for each node, ensuring complete neighbor information without subsampling biases.

Strengths

1. The model proposed by the authors looks reasonable, at least their experiments suggest so. 2. The authors do a good job in describing the model. They propose two measures of expressiveness for temporal graph models, specifically in the context of temporal link prediction and temporal graph isomorphism tests. They establish a theoretical connection between these measures and demonstrate the superior expressiveness of their framework, while also presenting new findings on the expressiveness of other baseline methods. 3. The ablation studies display the positive effect of each mechanism.

Weaknesses

Some concerns in this paper should be discussed precisely. 1. In introduction, the heterogeneity in temporal revision is not explained. 2. Figure 1 lacks a specific description. The other baselines and the framework in this paper can be specified in the legend. 3. This paper lacks a description of Table 1. The authors can add a description of Table 1.

Questions

1. Eq.3, 4 and 5 all refer to arbitrary learnable function, could you please specify what function is used in this paper? 2. In the experiment shown in Table 3, is it possible to display the results of all datasets?

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

2 fair

Presentation

3 good

Contribution

3 good

Limitations

The authors adequately addressed the limitations.

Summary

The paper studies the problem of temporal graph learning. The authors propose the recurrent temporal revision (RTR) layer, which involves learning a hidden state for each node and utilizing recursive neural networks to integrate information from all neighbors. Additionally, the authors introduce heterogeneity in RTR and theoretically demonstrate that this heterogeneous revision enhances expressiveness beyond Temporal-1WL.

Strengths

S1. The majority of the paper is easy to follow. S2. Experimental results show that RTR outperforms state-of-the-art methods.

Weaknesses

W1. My main concern is with the motivation of paper. Why do we need to make each node embrace complete neighbor information? In real-world recommendation system data, the browsing/purchasing tendencies of users are often more closely related to their short-term interests. The inclusion of excessive and outdated information may introduce more noise to the model instead. W2. The proposed RTR can be understood as weight learning and important neighbor selection based on complete historical information. Could changing the sampling strategy from selecting k nearest neighbors to selecting k most important historical neighbors for methods like TGN also result in similar performance improvements? W3. The paper lacks an analysis of time complexity as well as a comparison of the model's parameter count. Minor comments M1. Page 1, Line 16: social network, recommender system -> social networks, recommender systems M2. Page 4, Line 160: an learnable function -> a learnable function M3. Page 8, Figure 4 caption: TGN and GRU-GCN fails to -> TGN and GRU-GCN fail to

Questions

Please refer to W1-W3.

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.

Confidence

5: You are absolutely certain about your assessment. You are very familiar with the related work and checked the math/other details carefully.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

I have some concerns about the scalability of the proposed method.

Summary

In this paper, the authors propose a novel aggregation layer based on a recurrent neural network dubbed recurrent temporal revision (RTR) for temporal graph networks to solve the dynamic temporal graph embedding problem. Specifically, a new aggregation function is proposed, which encodes neighbor state information and event information. This paper also proposes two expressive measures and uses them to demonstrate theoretically the difference from previous work. Empirical results on several well-known datasets show the effectiveness of the proposed method.

Strengths

1． The explanations of the components of the approach are clear and detailed. 2． This work uses the proposed two measurements, and theoretically, fully justifies the difference from the previous methods. It also includes algorithm time complexity and running time analysis 3． Ablation settings are very detailed.

Weaknesses

1. It is unclear which part of the ablation experiment corresponds to which of the two proposed measurements. It would be good to clarify that. 2. It’s better to have an Algorithm line by line to clearly correspond to specific formulae and modules for Figure 1b.

Questions

1. Some symbols and formulations need to be clarified: a) Eq. (4) should be accurately formulated. b) r_t^0(t) in Line 148 should be a vector. 2. Which variance or function in Eq3 and Eq4 can reflect the two proposed measurements? 3. The organization of Section 3 should be improved. Each subsection ends abruptly without a clear takeaway message. 4. Table 1 is hard to read. 5. The differentiation between the current work and previous works (especially TGAT, and TGS) need to be explained more clearly. 6. Why do the 2-layer experiments only run in selected datasets? What’s the selection criterion?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

N/A

Summary

The paper introduces a novel framework called Recurrent Temporal Revision (RTR) to address the challenge of neighbor subsampling in temporal graphs, an issue commonly encountered in real-world applications like social networking, recommender systems, traffic forecasting, and crime analysis. RTR serves as a standard building block for any temporal graph network, utilizing a recurrent neural network to integrate all neighbor information through a hidden node state. This hidden state mitigates the problem caused by neighbor subsampling and aims to capture complete neighbor information. The paper also introduces a new concept of "temporal revision" to update the hidden state by capturing the state changes of neighbors. To further boost the theoretical expressiveness of this technique, the authors propose incorporating heterogeneity into temporal revision by recursively identifying and marking certain nodes as specialties in the revision calculation process. The authors suggest that this new approach offers superior expressiveness in terms of temporal link prediction and temporal graph isomorphism test, a claim that is backed by theoretical proofs and experimental results. Additionally, they provide a new Ecommerce dataset for evaluating temporal graph models in real-world settings. Their experimental results indicate the proposed framework's significant improvement over state-of-the-art methods, particularly as the number of aggregation layers increases.

Strengths

- The authors introduce innovative ways of evaluating the expressiveness of graph algorithms by defining two novel metrics: the temporal graph isomorphism test and the temporal graph link prediction. They apply these new measures to several state-of-the-art models, successfully establishing an equivalence between Temporal-1WL and these baseline models which implies the shared drawbacks of these models. - The paper presents a unique temporal learning model grounded on two inventive ideas: 1) Utilizing hidden states to retain aggregated information which is subsequently updated through a temporal revision layer, and 2) Embedding heterogeneity by giving special treatment to the central node during the recursive revisioning process. The authors compellingly argue that their proposed method outperforms state-of-the-art models in terms of expressiveness, as defined within the context of this paper. - The proposed method demonstrates promising performance in real-world temporal graph tasks, particularly in the temporal link prediction task. Additionally, it excels in the graph isomorphism test examples, reinforcing its potential for practical applications in various fields.

Weaknesses

- The rationale behind the new definition of expressiveness isn't effectively conveyed in the paper. While it's true that there isn't a universally accepted definition for the expressiveness of a temporal graph model at present, the paper falls short in clarifying why its proposed isomorphism test improves upon existing ones. The lack of a clear explanation leaves a gap in understanding the superiority of the proposed metrics.

Questions

From the proof of proposition 3, the extra expressiveness of the proposed model comes from the heterogenous revision which could be in principle added to other IMP-TGN representation model. Can we conclude that heterogeneity help improve expressiveness of temporal graph model?

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

4 excellent

Limitations

N/A

Thanks a lot!

Thanks for your response and the additional experiments. I would like to keep my score.