Towards Dynamic Graph Neural Networks with Provably High-Order Expressive Power

W1: Similarity to Existing Models.

Response: We believe there exists misunderstandings. The proposed HopeDGN is clearly different from DyGFormer in following aspects. Firstly, HopeDGN is a general framework which can be implemented by many forms, while the model structure of DyGFormer is fixed. Secondly, HopeDGN adopts the proposed MITE as the correlation encoding while DyGFormer adopts Neighbor Co-Occurrence Encoding (NCOE). The advantage of MITE over NCOE is discussed in Section 4.2. Thirdly, the output of HopeDGN is the embeddings of a node pair, while the output of DyGFormer is node embedding.

W2: Some inaccuracies in Fig.1.

Response: Thanks for your comments. We apologize for making you confusion. Figure 1 illustrates the limited expressive power of defined DyGNNs (Section 4.3), but not for DyGNNs with heuristic encodings such as DyGFormer. We will clarify this point in the revised paper. Although the heuristic encodings in DyGFormer have improve the expressive power to some extent, its expressive power is not quantifiable from a theoretical perspective. We will add DyGFormer for discussion in the revised paper.

W3: Limited Experiments

Response: Thanks for your suggestion. We will consider to add the experiments of different negative sampling configurations in the revised paper.

W4: Ambiguity in Notation

Response: Thanks for your suggestion. We will revise these symbols in the revised paper.

W5: Unclear Theoretical Framework

Response: Thanks for your suggestion. To quantify the expressive power of DyGNNs, we propose the k-DWL for dynamic graphs, which is an extension of WL test to dynamic graphs. We have demonstrated in Proposition 1 that the expressive power of (k+1)-DWL is strictly stronger than k-DWL. This demonstrate that the proposed DWL test is a valid quantification of expressive power, similar to WL test in static graph used to quantify the expressive power of static graphs.

W1: HopeDGN is somewhat of an incremental study compared to DyGFormer. HopeDGN exhibits higher performance in the experiments but may incur much larger training costs.

Response: We believe there exists misunderstandings. Here we clarify the difference between the proposed HopeDGN and other baselines (DyGFormer, HOT and CAWN) as follows. Firstly, the expressive power of HopeDGN is proven to be equivalent to 2-DWL test, while other baselines (DyGFormer, HOT, CAWN) only leverage heuristic encodings without theoretical derivations. Secondly, the proposed HopeDGN is a general framework which can be implemented by many forms. The specific implementation of HopeDGN in section 4.4 is just one form of it. Thus, HopeDGN is not an incremental study to DyGFormer.

In terms of training costs, we have evaluated the training efficiency of HopeDGN in experiments and the results are presented in Figure 5. In Figure 5, we observe that HopeDGN with neighbor length 16 is faster than DyGFormer.

W2: The discussions of the expressive power of existing DGNN models are not completely correct.

Response: Thanks for your suggestion. Our abstraction of DyGNNs in Section 3 closely follows existing works [1]. Our discussion about the expressive power (including Fig 1 and Proposition 1) is for this definition of DyGNN, but not for DyGNNs with heuristic encodings (such as DyGFormer, HOT, CAWN). We will clarify this point in the revised paper.

W3: Some notations are confusing.

Response: Thanks for your suggestion. We will specify these notations in the revised paper.

Q1: Is the expressive power of 1-DWL test equivalent to the 2-DWL test?.

Response: Thanks for your question. The answer is no. Our proposed 2-DWL test is an extension of Folklore variant of 2-WL test, whose expressive power is proven stronger than 1-WL test [2].

Q2: Could the authors provide the training cost of HopeDGN and the baselines?.

Response: Thanks for your question. We have provided the training cost in Fig.5 of Appendix.

Ref:
[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.
[2] Morris C, Lipman Y, Maron H, et al. Weisfeiler and leman go machine learning: The story so far[J]. The Journal of Machine Learning Research, 2023, 24(1): 15865-15923.

W1: The paper could benefit from a detailed comparison with other high-order GNNs for static graphs.

Response: Thanks for your suggestion. We will compare some papers you mentioned in the revised paper in detail.

W2: Confusion about Fig.1.

Response: Thanks for your suggestion. The proposed DWL test is inspired by the WL test in static graphs, which additionally hashes the timestamps arrays. We acknowledge that the failure case of 1-DWL test may be somewhat similar to 1-WL test. However, the dynamic graph has clear difference with static graphs since each interaction (edge) is associated with timestamps array. Since the focus of this study is on dynamic graphs, and Figure 1 indeed presents a failure case of vanilla DyGNN (or 1-DWL test), we think this is appropriate for illustrating the limited expressive power of DyGNN, regardless whether it can be work on static graphs.

W3: Can the proposed method work on dynamic graphs in which edge interaction can both start and end?

Response: Thanks for your suggestion. To address the edge deletion event, we need to make some modification on the current model. In specific, we can add an 0-1 indicator on mite to signify whether each event is an edge addition or deletion event. Through this technique, the model can capture whether the event is an addition or deletion event.

W1: The DWL test is almost identical to the temporal WL test in PINT [1]. This is not acknowledged in the main paper and thus, can be flagged as plagiarism.

Response: We believe there exists serious misunderstandings. There are some clear difference between temporal WL and PINT. Firstly, the proposed DWL test is $k$-order which colors the $k$-node set on dynamic graphs, while temporal WL test is only applicable for coloring single node. Secondly, temporal WL test hashes the single time interval while DWL test hashes the complete interaction timestamps array (a vector). Therefore, we think the proposed DWL should definitely not be recognized as plagiarism.

W2: Discussion with existing related work is casual and not carefully positioned.

Response: We believe there exists misunderstandings. We respectively respond to your concerns as follows.

• Our claim in Paragraph 2 of Introduction is “it remains unclear how the relative positional features (RPF) quantitatively affect DyGNNs' expressive power” but not your paraphrase. Our original claim is true because the Proposition 9 of PINT only shows that combining RPF with DyGNN is strictly more expressive than DyGNNs, but the exact expressive power of DyGNN with RPF is not quantified by some benchmarking criterion such as DWL test.

• As you have stated, the expressive power of “sufficiently deep DyGNN” will not be be improved with memory. In addition, the expressive power of “sufficiently deep DyGNN” is bounded by 1-DWL test as shown in proposition 1. This means that the expressive power of “sufficiently deep DyGNN with memory” is bounded by 1-DWL test. Thus, we can easily conclude that the expressive power of “normal DyGNN with memory” is bounded by 1-DWL test. Thus, our claim is true.

• The goal of our work is not to prove that HopeDGN is more expressive than [1] and [4]. Instead, our goal is to propose a model (HopeDGN) whose high-order expressive power can be quantified by benchmarking criterion such as DWL test, while both [1] and [4] cannot address.

W3: The additional cost of storing B matrix may be prohibitive.

Response: In implementations, we do not use the original $B$ tensor in Eq. (6) but cut down the last $K$ non-infinite timestamps when computing MITE (as we have stated in Section 4.2). The MITE is computed in the current batch of data and discarded when moving into the next batch, thus the memory burden is light.

W4: MITE encoding is similar to the time projection for staleness as done in JODIE [2] and TGN [3].

Response: We believe there exists misunderstandings. MITE is completely different from time projection in JODIE and TGN. Specifically, time projection aims to project the time interval between the last interaction and current time for central node (a single scalar) to make prediction, while MITE encodes the complete history between the neighbors to central node pair (a matrix). The computation procedures of these two techniques are completely different, and there is no evidence that our MITE is the extension of time projection.

W5: The proof of the main proposition 3 that shows the theoretical disadvantage of existing dyGNNs seems wrong. In particular, they only consider node b for graph (a) and node h in graph (b). On the other hand, ...

Response: We believe there exists misunderstandings. The proposition 3 only aims to show that there exists an non-isomorphic node pair that DyGNN with MITE can distinguish while vanilla DyGNN cannot. We prove this by showing the case of (a,c) in Fig.3 (a) and (a,g) in Fig.3 (b). For your comment of “on the other hand …”, we are discussing DyGNN and DyGNN with MITE in Proposition 3, and HopeDGN (Eq. 9) is irrelevant to Proposition 3.

W1: Some baselines are not addressed.

Response: Thanks for your comments. We acknowledge that some heuristic encodings have been designed to somewhat improve the expressive power of DyGNNs, such as those in CAWN, NAT, DyGFormer and PINT. However, the expressive power of these models is not quantified (such as k-WL test in static graph).

To bridge this research gap, we propose a benchmarking hierarchy named k-DWL test to quantify the level of expressive power of DyGNNs, which has been highlighted in the second paragraph of introduction. Then, we propose HopeDGN which is proven to be as expressive as 2-DWL test, thus its expressive power can be clearly quantified.

We will revise the introduction section and include these works for discussion.

W2: The time complexity of HopeDGN.

Response: We argue that the time complexity of HopeDGN is controllable when the time spans is large. As analyzed in Section 4.4, the time complexity of HopeDGN is linear with $S$ where $S$ is the length of concatenated historical neighbors. Fig.5 also demonstrate that training time is linear with $S$ by experiments. This linear complexity is similar to other DyGNNs such as DyGFormer and be scalable to the case of long time span.

Q1: How is the integration of MITE implemented, and does MITE demonstrate clear benefits compared to other encoding approaches?

Response: The integration process is as follows: Given a DyGNN model A, suppose the target link to be predicted is $(u,v,t)$, where u and v are nodes and t is the timestamp. A processes by sampling the historical neighbors of $u$ and $v$, denoted as $\mathcal{N}(u,t)$ and $\mathcal{N}(v,t)$ respectively, For any $w \in \mathcal{N}(v,t) \cup \mathcal{N}(v,t)$, we can compute its MITE with respect to $(u,v)$ at time $t$ (eq. 7). Then, MITE is integrated with the node feature.

To demonstrate the benefits of MITE over other encodings, we will also integrate Neighbor CoOccurrence Encoding (NCOE) with various baselines on various datasets in the revised paper.

Q2: The performance metrics in Fig 5.

Response: The inductive AP metrics of CorDGT with various neighbor length on MOOC (in Fig. 5) is summarized as follows.

Although we have decided to withdraw this paper, we still provide detailed responses below to address the concerns of reviewers. We hope these clarifications and responses will help the reviewers and future readers to better understand this paper.

Again, we thank the reviewers for providing valuable comments.