Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: The paper attempts to address the limitations of message-passing TGNs (MP-TGNs) and walk-aggregating TGNs (WA-TGNs). To be specific, a so-called position-encoding injective temporal graph net (PINT) is proposed, which not only defines injective message passing and update steps, but augments memory states with novel relative positional features. Note that, the time complexity of computing and communicating positional features in PINT is less than CAW. Experimental results show that PINT outperforms existing TGNs on several real-world benchmarks in both transductive and Inductive settings.
strengths_and_weaknesses: Strengths:
1. The paper is clearly written and easy to follow. The Introduction and Related Works (Preliminaries) parts are well written.
2. Visualizations and plots are intuitive.
3. Building injective aggregation and update functions in the temporal setting is interesting and somewhat novel.
4. Experiments are extensive and promissing, considering both transductive and Inductive settings.

Weaknesses:
Although the authors have already show that PINT can be trained faster than CAW (which is the main competitor shown in Table 1). I wonder will the large-scale temporal networks limit the behavior of PINT?
questions: Questions: 
1. Can the proposed PINT deal with long-term dependencies?
2. For edge and node embeddings, why the authors consider 10/20-hop neighbors? Will the small number of neighbors will impact the performance? 
3. I am curious whether the proposed PINT model can be used for node classification/forecasting?
4. The standard deviations of PINT on Reddit and Twitter (for both transductive and Inductive settings) are very small. I wonder is there any reasons/ways to interpret this scenario?
5. For Eqs. 9 and 10. Why the authors only do multiplication between $P$ and $r^{t^-}_{i \rightarrow u}$ (e.g., in Eq. 9)?
limitations: I have no ethical concerns with this paper.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper studies the topic of graph neural networks in temporal settings, which is a very significant avenue of graph learning applications. In doing so, a number of recent prominent works in this sub-topic is converged in this paper through solid theoretical analyses. Particularly, theoretical foundations have been developed (summarized in Fig 1 with references to relevant statements) which improves the understanding of temporal GNNs and provides a basis for further improvement targeting this research domain. Standing on such theoretical studies, the paper proposes a position-encoding temporal graph network (PINT) which is provably powerful than existing GNNs for temporal graph learning, which is empirically powerful than existing methods on the benchmarks used.
strengths_and_weaknesses: =>Strengths:   
-This work is an excellent convergence of the recent advances in extending GNNs on temporal graphs. It includes several studies in terms of theoretical property of existing temporal GNNs, what are their limitations, extending WL test analysis on temporal graphs, and ways to improve TGNs beyond MP-TGNs.    
-In terms of originality, I feel the paper is greatly motivated from existing theoretical advancements of GNNs applied to static graphs (in terms of 1-WL like quantification, limitations and positional encodings). Nevertheless, this extension and presentation of the theoretical insights to temporal graph settings is novel.    
-In terms of significance, the results and insights from this paper would definitely be used in further developments.    
-The paper writing is clear, the related literature and existing concerns are discussed.    
-Overall this paper does a fundamental contribution for the topic of developing machine learning foundations on temporal and time dynamic graphs.   

=>Weaknesses:   
While there seems no significant weakness in the contribution of this work, below are some minor observations:
-Are the experimental results significant looking at the score differences of PINT with best model of the literature. For instance the differences are in the ranges ~0.5 scores of AP for many results in Table 1?    
-Whether positional encoding (pe) is main contributor of good performance of PINT? Would incorporating the 'pe' in existing TGNs would be at par performance of PINT+pe?   
questions: -What would be the effect of directly adopting positional encodings that have been developed for static GNNs (which the paper reviews in the supplementary sections), say for different static graph snapshots at different timestamps?   
-In line 347-349, it is claimed that MP-TGNs are outperformed by PINT w/o pos. feat. However, from Table 1, it is observed that in 7/12 results (12 = 6 transductive + 6 inductive), it is not the case.   
-With respect to the time complexity analysis, the Figure 6 has an interesting mark at epoch 25, after which PINT's runtime is faster than CAW. To this end, will it possible to show some sample evaluations of PINT at only 25 epochs (or lesser) of training? This could provide a useful insight on comparison of PINT with CAW at a situation where PINT's runtime is not better than CAW.   
limitations: Yes, the limitations are clearly discussed as well as societal impact mentioned.
review_title: null

final_score: 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.
review_content: summary: The paper provides a theoretical framework to analyse the expressive power of temporal graph networks (TGNs), and designs a novel model, PINT, which is provably more expressive than existing ones. Specifically, the paper proves the role of memory, benefits of injective message passing, limits of existing TGN models, temporal extension of the 1-WL test and its implications, impossibility results about temporal graph properties, and the relationship between main classes of TGNs. Then, PINT is introduced, with the elaborately design of injective temporal aggregation and relative positional features. Empirical investigations show that PINT is competitive or better than existing models on several real benchmarks for dynamic link prediction in different settings.
strengths_and_weaknesses: Strengths:
1. The paper puts forward an interesting research direction of theoretically analysing the expressive power of temporal graph networks, which is of great importance yet long be ignored.
2. The theoretical results in the paper are solid. The authors extend the analysis framework in static GNNs to TGNs. The lemmas and propositions are closely linked to each other. The proofs seem logically rigorous, covering both special and general cases.
3. The design of PINT is concise yet with firm theoretical foundation.
4. Impossibility results of PINT are also introduced.

Weakness:
1. Discussion on the experimental results are not sufficient. Notice that the model does not outperform certain baselines on Enron in the transductive setting, and is relatively worse in the inductive setting. However, the authors do not provide a plausible explanation on these phenomena.
2. Several important experiments are missing. For example, the results on node classification is more straighforward to show the models' power of distinguishing nodes than dynamic link prediction.
questions: 1. The model does not outperform certain baselines on Enron in the transductive setting, and is relatively worse in the inductive setting. However, the authors do not provide a plausible explanation on these phenomena.

2. Several experiments are missing. For example, the results on node classification is more straighforward to show the models' power of distinguishing nodes than dynamic link prediction. Also, parameter sensitivity can be analysed on \alpha and \beta, because it may be important for controling the learned injective function.

3. Does PINT still fail in differing properties mentioned in Proposition 7, even the relative positional features are added?

4. There are some places that can be improved to make the discussion clearer. For example, I am a bit confused when reading line 45-50, because I fail to recognize the concept "injective MP-TGN", as it is referred to as "MP-TGNs equipped with injective functions" and "these most powerful MP-TGNs", and is contained in "MP-TGN" mentioned in the last sentence of this paragraph. Besides, there is no clear definition of the concept "anonymous TGNs", which comes up for several times in the paper.

5. A minor flaw: the term "discrete-time dynamic graph" in line 83 should be in italic type, aligning with line 85.
limitations: This work do not show any potential negative societal impact. The authors illustrate cases when the model fails, which is possibly related to temporal 1-WL test. Future works can be focused on going beyond this.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This work studies the expressivity limitation of temporal graph neural networks, mainly on two state-of-the-art (SOTA) methods, TGNs (MP-TGN in paper) and CAWs, then proposes a more expressive framework, PINE.
strengths_and_weaknesses: The strength of this paper is:
1. Propose a concrete failure case of SOTA methods, e.g., CAW, which can be used as a benchmark for temporal graphs.
2. Studying temporal graph neural networks expressivity by temporal computation tree (TCT) and proposed temporal WL test variant.
3. Design more expressive PINE which achieve empirically better performance in 5/6 widely used datasets.




questions: 1. Around CTDG definition (line 85), it will be better to use different symbols for G since it will have two meanings before and after line 85. Before the line, G refers to simple graph (no dup edges, static or happening in specific time range); but after the line, G refers to multi-graph (have multi edges linking same nodes) whose edges are additionally distinguished by extra timestamps. It is important to highlight this shifting to avoid confusion in later content.
2. I am not sure the correctness of uniformly spaced countable set in Proposition 1 (line 93), please clarify: To transform CTDG to DTDG, we only need to put all timestamps as a real value feature on nodes or edges, and let different timestamp generate different snapshot, thus just countable will be enough. And I think this requirement may even be meaningless since even for CTDG, you can not store infinite timestamps, and with finite timestamps, CTDG and DTDG are same.
3. Need clarification of memory aggregation for equation (3) (line 114) and experiments. Equation (3) shows that you are using most recent memory aggregation in the paper, but in appendix, you investigate mean aggregation of TGN, which one are you really using? Besides, if you are using mean memory aggregation, shouldn't you decrease MP-TGN by 1 layer for fairness? Since it is a kind of graph convolution.
4. The TGN limitation example (figure 2) is unfair since TGN-Att is just a specific hyperparameter setting of original TGN paper, and I think that another setting TGN-sum can solve this counterexample, thus this is not a real counterexample for TGN.
5. TCT node symbol i_u is bad and causes confusion. In line 142, i_u should not have u as subscript since it implies a unique TCT node is assigned with u but we can have multi nodes in the same TCT layer corresponding to the same u (but different times). A better notation is required to make it clear that a real node u can appear multiple times in both the same and different layers in TCT.
6. Besides, should mapping #v also have t as an argument since it is reverse mapping in a sub tree of root (v, t)?
7. Is line 155 of definition 1 indeed s_u = s'_{f(u)}? I don't think current statement makes any sense. Omitting root node makes the notation confusing.
8. Can proposition 6 and 7 extend to random walk methods, e.g. CAW? Since without such extensions, it looks same as conclusion of reference [49] that with proper injective mappings, we can always distinguish temporal graph isomorphism like a static graph, and even the most power methods are not good for learning relations? If so, you can move this part to appendix and clarify other parts better or put other parts there, e.g., how can your method deal with deletion.
9. What is the square root term in equation (4)? It is different from proposition 8, and no explanation or intuition is provided for such modification in the paper.
10. It will be better to add more space between P and r in equation (9) and (10) since it looks like Pr on the first sight.
11. There is a highly related work CAW-TGN [1] that use CAW to get positional info for TGN which is similar to your paper, and you should add this into your comparison baseline and do ablation study.
12. Why some datasets do not have static method performance?

Minor typos:
- Figure 2: (v, z, t3) to (u, z, t3)

[1] Makarov, I., et al. (2021). Temporal graph network embedding with causal anonymous walks representations.
limitations: This paper provides the limitation of PINE which reveals the direction for future efforts and reports societal impact in appendix.
review_title: null

Meta-review: metareview: This paper considered temporal graph networks (TGNs). It first analyzed the representational power and limits of the two main categories of TGNs (WA-TGN and MP-TGN), proving neither category subsumes the other. It extended the 1-WL (Weisfeiler-Leman) test to TGNs and showed when TGNs become as expressive as the temporal WL. It also showed that sufficiently deep MP-TGNs cannot benefit from memory, and MP-TGNs fail to compute graph properties such as girth. Based on the theoretical results, it proposed a provably more expressive TGN called PINT and showed that it outperforms existing methods on several real-world benchmarks.

The work has made solid and novel contributions, including theoretical studies of the expressive power of TGNs, a new framework, and strong empirical performance of the proposed framework. The authors also addressed well the comments from the reviewers and further strengthened the work during the response period.
confidence: Certain
Decision: Accept