Towards Better Dynamic Graph Learning: New Architecture and Unified Library

Summary

This paper studies the problem of continuous-time dynamic graph learning. The authors proposed a Transformer-based architecture DyGFormer to learn the dynamic edge representation, which mainly consists of a neighbor co-occurrence encoding scheme to count the co-occurrence of nodes, a patching technique to split the node’s sequence into multiple patches, and a Transformer as the backbone. The authors also propose a dynamic graph learning library DyGLib, and re-report the important baselines’ performance based on DyGLib. Experimental results conducted on 13 benchmark datasets verify the effectiveness of the proposed method.

Strengths

1. The authors propose a co-occurrence encoding scheme and a patching technique to capture the correlation between sequences and the long histories of sequences respectively. As far as I know, it is less studied than learning the dynamic link representations direct from the sequences of nodes’ first-hop interactions under the dynamic graph learning problem, especially how to model the long histories of the interaction sequence. 2. The authors conduct extensive experiments on 13 benchmark datasets to verify the effectiveness of the proposed two-component. Besides the proposed method, the authors also re-implemented the important baselines in the area, and point out that some findings of baselines are not in line with previous reports because of their varied pipelines and problematic implementations, which may benefit future research in the continuous-time dynamic graph learning community. 3. The authors propose a continuous-time dynamic graph learning problem. This library provides a unified pipeline to train and evaluate different baselines. I think this library can provide a tool for researchers in the community to conveniently evaluate different methods in a unified setting.

Weaknesses

1. In the problem formalization of section 3, the authors define the target of the dynamic graph learning problem as learning the time-aware representations for each node. But the DyGFormer actually learns the dynamic link representations but not the node representations. Or more accurately, the DyGFormer learns the contextual node representation $h^t_{u|(u,v)}$ but not $h^t_u$, where the node representation $h^t_{u|(u,v)}$ relies on the other node v. It will be better to add some discussion for this in the paper. 2. In section 5.2, the authors say that “some of our findings of baselines differ from previous reports”, but the authors do not point out which baselines’ performance improves. I suggest the authors explicitly list which baselines’ performance improves.

Questions

Please refer to the weaknesses part.

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.

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

4 excellent

Contribution

3 good

Limitations

N/A

Summary

In this paper, the authors considered the dynamic graph representation learning (a.k.a. dynamic network embedding) problem and proposed a novel transformer-based architecture - DyGFormer, with several original designs (e.g., a neighbor co-occurrence encoding scheme, a patching technique, etc.) Moreover, the authors also implemented a unified continuous-time dynamic graph learning library, which include several baselines, widely-used datasets, and a common evaluation pipeline. Exhaustive experiments with various settings of dynamic link prediction and dynamic node classification were also conducted to validate the effectiveness of the proposed method.

Strengths

(S1) The overall presentation of this paper is clear, which makes it easy to grasp the key ideas. (S2) There are some original designs (e.g., neighbor co-occurrence encoding scheme and patching of historical neighbor sequence) in the proposed method. (S3) The authors conducted many experiments on 13 datasets for both dynamic link prediction and dynamic node classification with various settings. (S4) The authors also implemented a unified library including some typical baselines and a common evaluation pipeline for various task settings (e.g., transductive and inductive dynamic link prediction and node classification), with the code provided for review.

Weaknesses

(W1) Some statements are with too many citations (e.g., 'continuous-time methods [27, 53, 62, 44, 35, 9, 55, 58, 57, 24, 34, 12]', 'graph convolutions [53, 62, 44, 35, 9, 57]', etc,) which are hard to check their sources. Some references are also repeated in successive sentences (e.g., 'only a few libraries are specifically designed for dynamic graphs [18, 45, 71]. DynamicGEM [18] is a library for dynamic graph embedding methods'). It is better to ensure that there are at most 5 references for each statement. Some of the references can also be replaced with concrete examples or methods introduced in this paper. Furthermore, references of some important statements are also missing, e.g., 'unlike most previous methods that need to retrieve nodes' historical interactions from multiple hops' but what do 'previous methods' refer to? (W2) Some problem statements regarding model optimization are unclear. Concretely, the formal definition of training loss is not given. In general, we can divided existing dynamic graph representation techniques into the task-dependent and task-independent methods, which are respectively trained via (i) supervised losses related to and (ii) unsupervised losses regardless of the downstream task. It is unclear that the proposed method is task-dependent or task-independent. In the baselines, DyRep and TGAT are task-independent while CAW is task-dependent (with a loss designed for dynamic link prediction), as I can check. From my perspective, it is unfair to compare both types of method in a common experiment setting, where task-dependent methods are expected to have better performance than task-independent approaches, due to the incorporation of supervised information related to the downstream task. For task-independent methods, the authors should also clarify the downstream module (e.g., logistic regression, SVM, MLP, etc.) to support a concrete task. More importantly, the evaluation pipeline of a unified library should also cover both the settings. (W3) Although the authors gave toy examples for some procedures of the proposed method (e.g., the computation of neighbor co-occurrence encoding), several details still need further clarification (e.g., how to pad a derived patch, etc.) It is recommended summarizing the overall procedure to derive all the encoding and patches in terms of pseudo-code (even in supplementary material). (W4) In related research, inductive dynamic link prediction includes the prediction of links between (i) one old (i.e., previously observed) node and one new (i.e., previously unobserved) node as well as between (ii) two new nodes. It is unclear that the inductive setting in this paper refers to both cases or just the latter case. (W5) Although the authors included 7 baselines in experiments, most of them are based on time-encoded deep sequential models (e.g., with RNN and attention). In addition, there are some other related approaches based on temporal point process (e.g., HTNE [1] and TREND [2]) and neural ordinary differential equation (e.g., GSNOP [3]) that are not considered in experiments. A unified library should cover various types of method. - [1] Zuo, Yuan, et al. Embedding temporal network via neighborhood formation. KDD 2018. - [2] Wen, Zhihao, and Yuan Fang. Trend: Temporal event and node dynamics for graph representation learning. Web Conference 2022. - [3] Luo, Linhao, Gholamreza Haffari, and Shirui Pan. Graph sequential neural ode process for link prediction on dynamic and sparse graphs. WSDM 2023. (W6) In supplementary material, although the authors gave some details regarding the datasets, the source information (i.e., where can we download these datasets) is missing. In Table 4 of supplementary material, what does 'duration' means? Does it means the time granularity? Consistent with the statistics of 'duration', what is the total number of time steps for each dataset? From my perspective, the scale of a dynamic graph is related to the (i) number of nodes $N$ and (ii) number of time steps $T$. As I can check, all the datasets are with $N<20,000$, which cannot be considered as large datasets. Can the proposed method be scaled up to larger datasets? Or are there any possible solutions to addressing the scalability issue (perhaps as one future research direction)? (W7) It seems that the authors upload the paper to ArXiv before the formal submission to NeurIPS. Several month ago, google scholar and github recommended the ArXiv version of this paper to me. As a result, I have already known the names and institutions of the anonymous authors, which breaks the double-blind policy.

Questions

See W1-W7. As claimed before Eq. (3)-(7), the row dimensionality of ${\bf{Z}}^t$ (i.e., the input of transformer encoder) is $(l_u^t + l_v^t)$, which is related to the length of $S_u^t$ and $S_v^t$. Since different nodes $u$ may have $S_u^t$ with different length, it seems that one can only feed the input ${\bf{Z}}^t$ w.r.t. one link $(u, v, t)$ to the transformer encoder every time due to the non-fixed dimensionality of input. Can we simultaneously feed ${\bf{Z}}^t$ w.r.t. multiple (i.e., more than one) links $(u, v, t)$ into the transformer encoder and derive multiple embedding pairs $({\bf{h}}_u^t, {\bf{h}}_v^t)$? If yes, how to derive these embedding paris $({\bf{h}}_u^t, {\bf{h}}_v^t)$? If not, there seems to be an efficiency issue for the proposed method. Consider an extreme case. For some new (i.e., previously unobserved) nodes without any available attributes and historical neighbors, can the proposed method still be able to support the inductive inference (e.g., dynamic link prediction and node classification) w.r.t. these nodes?

Rating

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

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

See W1-W7.

Summary

This paper proposes a new dynamic graph learning architecture and implemented it as part of a new unified graph library with extensive experiment results to verify the effectiveness of the proposed algorithms. The author proposes a new Transformer-based architecture DyGFormer for dynamic graph learning. The architecture is designed to overcome some of the limitations of previous methods by: - Leveraging a neighbor co-occurrence encoding scheme, which captures the frequency of appearances of each neighbor in the sequences of source and destination nodes. This explicitly explores the correlations between nodes. - Utilizing a patching technique, which allows splitting each source/destination node’s sequence into multiple patches, enabling the capture of long-term temporal dependencies and reducing the computational complexity to a level that doesn't depend on the input sequence length. The author also developed a library called DyGLib as a unified library specifically tailored to continuous-time dynamic graph learning. Its key features include: - Standardized training pipelines to facilitate reproducibility and consistency across different methods. - Extensible coding interfaces for better adaptability and scalability and integrates with 13 graph datasets and 9 graph algorithms

Strengths

The paper presents an extensive and technically rigorous evaluation. The authors benchmark their model on 13 dynamic graph datasets against nine state-of-the-art dynamic graph learning models, providing thorough evidence for their conclusions. The comprehensive ablation study further supports the effectiveness of the proposed components. The proposed DyGFormer architecture performs favorably in comparison to other dynamic graph learning models, with only a few exceptions. DyGFormer handles long-term node interactions efficiently, thanks to the novel integration of neighborhood co-occurrence encoding and the patching technique.

Weaknesses

The paper lacks a comprehensive technical discussion motivating the design of the proposed model. The co-occurrence matrix is said to model node correlations better than other models, but it's not entirely clear why explicit modeling of correlations leads to superior performance. Node proximity and similar neighbors are features that even basic models like the Graph Convolutional Network (GCN) can capture without explicit modeling. The paper's presentation could be improved. The title, for instance, may overpromise what the paper actually delivers - I was expecting a unified learning algorithm along with a software tool. However, on closer reading, it appears that the main contribution is from DyGFormer, while DyGLib, though useful, doesn't seem to bring much novelty or be absolutely essential to the paper's contributions. The preliminaries section seems unfinished, and the section on DyGLib includes several unsupported claims and lacks novelty.

Questions

1) Why does explicitly modeling the neighbor co-occurrence encoding help? What does the model eventually learn in the encoding module? What is the motivation of this function design which computes f(count_in_Su) + f(count_in_Sv) for each neighbor node? 2) The dynamic graph models consider the depth of graph searching but the proposed only considered first-layer interaction. Does it imply that high-level interaction modeling is not needed for dynamic graphs?

Rating

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

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

1 poor

Contribution

2 fair

Limitations

NA

Summary

This paper propose DyGFormer, a new Transformer-based architecture for dynamic graph learning, whose novelty mainly includes a neighbor co-occurrence encoding scheme and a patching technique. Moreover, it introduce DyGLib, a unified library to promote reproducible, scalable, and credible dynamic graph learning research. In experiments ,the DyGFormer achieves sota performance on most of the datasets.

Strengths

1. The paper is clearly written and easy to follow. 2. I think this unified library is high-quality, meaningful and urgently needed, which can well promote the development of dynamic graphs

Weaknesses

1. In DyGFormer , I think the introduction of transformer is not so novel. which has similarity with the attention mechanism of TGAT and TGN. 2. PINT[1], a work in NeurIPS 2022, is a new and sota model in the area of dynamic graph. Why this paper has not mention it? [1] Souza A, Mesquita D, Kaski S, et al. Provably expressive temporal graph networks[J]. Advances in Neural Information Processing Systems, 2022, 35: 32257-32269.

Questions

1. Can you add the introduction and experiment of PINT in this paper?

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

The authors adequately addressed the limitations. I have no ethical concerns with this paper.

Summary

This paper presents a transformer-based architecture (DyGFormer) for dynamic graph learning, based on a node co-occurrence encoding scheme and patching. Further, they present DyGLib a library for uniform evaluation of dynamic graph learning techniques. Extensive experimental evaluations over diverse datasets show that DyGFormer performs well.

Strengths

**Originality.** While the transformer architecture is well-known, it's application to dynamic graph learning, and the proposed co-occurrence encoding and patching schemes are novel. Various libraries / frameworks (as discussed in 108) exist for dynamic graph learning, so DyGLib is not novel in that regard, but a fresh rigorous and extensible evaluation is appreciated. **Quality / Clarity.** The paper is well-written and easy to follow. The DyGLib codebase is high-quality and well-documented. At a glance, it looks easy to use. Also, the appendix is thorough and well-put-together. **Significance.** Dynamic graph learning is an important research problem. This work not only presents a good solution but also paves the way for rigorous future work.

Weaknesses

While DyGFormer outperforms the baselines in avg. rank, there is a problematic trend that on some datasets DyGFormer can be much worse than the best or second best baseline in terms of absolute performance points (Table 1). This needs some analysis. What characteristics of these datasets make DyGFormer a bad choice against the baselines? What aspects of DyGFormer and the baselines could be causing their poor and better performance respectively? Why does DyGFormer's superiority falter when going from "rnd" to "hist" to "ind"?

Questions

Is it possible to integrate DyGLib / DyGFormer into TGL ([71] in paper)? If so, that would prevent a fragmentation of frameworks, and also allow dynamic graph learning research on billion-scale graphs. Also, see the weaknesses section.

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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

Limitations are discussed but in the appendix.

Thanks for your response

Thanks for your efforts to improve the paper, which have solved most of my concerns. I would like to keep the score as is.