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

Authors: Zhe Wang, Tianjian Zhao, Zhen Zhang, Jiawei Chen, Sheng Zhou, Yan Feng, Chun Chen, Can Wang
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Network, Dynamic Graph, Expressive power

Abstract:
Dynamic Graph Neural Networks (DyGNNs) have garnered increasing research attention for learning representations on evolving graphs. 
Despite their effectiveness, the limited expressive power of existing DyGNNs hinders them from capturing important evolving patterns of dynamic graphs. 
Although some works attempt to enhance expressive capability with heuristic features, there remains a lack of DyGNN frameworks with provable and quantifiable high-order expressive power.
To address this research gap, we firstly propose the k-dimensional Dynamic WL tests (k-DWL) as the referencing algorithms to quantify the expressive power of DyGNNs. We demonstrate that the expressive power of existing DyGNNs is bounded by the 1-DWL test. 
To enhance the expressive power, we propose Dynamic Graph Neural Network with High-order expressive power (HopeDGN), which updates the representation of central node pair by aggregating the interaction history with neighbor node pairs. 
Our theoretical results demonstrate that HopeDGN can achieve expressive power equivalent to the 2-DWL test. 
We then present a Transformer-based implementation for the local variant of \model.
Experimental results show that HopeDGN achieved  performance improvement up to 3.12\% on seven datasets, demonstrating the effectiveness of HopeDGN.

Decision: reject
Reviewer scores: 5, 5, 6, 5, 3

Reviews and discussion:
<thread>
creation date:
1730167687094

thread_type:
official_review

<thread_object>
creator: reviewer_f2fd

<content>
summary:
The authors present a new dynamic GNN model, HopeDGN, designed to exceed the expressive power limitations of current DyGNNs, which are capped by the 1-DWL test. HopeDGN aims to achieve higher-order expressive power by leveraging the 2-WL test.

strengths:
1. This paper investigates an important problem.

2. The paper thoroughly explores the expressive power of dynamic GNNs in relation to the 2-WL test.

weaknesses:
1. Similarity to Existing Models: The model structure closely resembles DyGFormer, particularly in Section 4.4, where essential component, from node encoding to the patching-based transformer encoder, are almost identical. However, the authors did not correctly cite DyGFormer, referencing only Dosovitskiy et al. (2021) instead.

2. Lack of Comprehensive 2-WL Analysis: While the paper’s primary contribution is introducing 2-WL testing for dynamic graphs, it falls short of a thorough examination of prior dynamic graph models’ failures under 2-WL. Some inaccuracies are noted; for example, in Figure 1, the claim that DyGNN cannot differentiate node pairs AC and AD is vague. With Neighbor Co-Occurrence Encoding, DyGFormer can indeed distinguish between these pairs. Additionally, the authors did not address scenarios where their model might also fail.

3. Limited Experiments: 3. According to the experimental setup in DyGFormer, there are three different negative sampling configurations. However, this paper appears to only conduct one configuration. Additionally, What’s the purpose of removing time encoding in the ablation study, as time encoding seems to be a common module in DyGNN frameworks and is not a contribution introduced by this paper.

4. Ambiguity in Notation: Certain symbols and terms are unclear, creating readability issues. For instance, the symbol S appears frequently in the complex analysis section (line 398) without definition. Similarly, i and j in Equation 3 lack clear explanations, and there are other instances of undefined notation throughout the paper.

5. Unclear Theoretical Framework: The authors state that they "establish a theoretical framework to quantify the expressive power of DyGNNs," but it is unclear how this quantification is achieved or where this analysis is elaborated upon in the paper.

questions:
Please refer to the weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730294615223

thread_type:
official_review

<thread_object>
creator: reviewer_1npk

<content>
summary:
This work aims to address the gap in dynamic graph learning research concerning the theory of expressive power. The authors first introduce the $k$-DWL test and argue that the expressive power of existing DGNN models is bounded by the 1-DWL test. To advance this, they propose a new DGNN model that works analogously to the 2-DWL test and prove that the proposed model, Global HopeDGN, is equivalent to the 2-DWL test. The experiments show the local variant of HepeDGN can achieve superior performance across several datasets.

strengths:
1. This work is the first attempt at assessing the expressive power of dynamic graph learning and introduces the concept of the $k$-WL test. It intuitively points out the limitations of existing DGNN models and proves that the 1-WL test limits their expressive power.
2. This work proposes a new DGNN model, HopeDGN, inspired by the 2-WL test. This model has greater expressive power than vanilla DGNN models, and the experiments show its superiority.

weaknesses:
1. Although no research exists on the expressive power theory of DGNN, a few studies have considered the correlations between historical neighbors of two terminal nodes, such as DyGFormer, HOT [R1], and CAWN. HopeDGN is somewhat of an incremental study compared to DyGFormer. HopeDGN exhibits higher performance in the experiments but may incur much larger training costs.
2. The discussions of the expressive power of existing DGNN models are not completely correct. 
   1. The abstraction of DyGNNs in Section 3 cannot cover existing studies. For instance, CAWN can leverage the information from high-order neighbors in a single layer if the length of the random walk is larger than 1.   
   2. DyGFormer, HOT, and CAWN are able to distinguish AC and AD in Figure 1.
3. Some notations are confusing. $l$ is used to represent the layer of AGG and UPDATE in Line 167 and the node labeling function in Line 239. And the layer of AGG and UPDATE of local HopeDGN in the experiments is not specified. In addition, the MITE of $w$ is denoted as $X_{B,w}$ in Line 369 and $X_{M,w}$ in Line 289.

[R1] HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers

questions:
1. The expressive power of the 1-WL test and the 2-WL test is the same in static graphs, as argued in [R2]. Is the 1-DWL test equivalent to the 2-DWL test? Intuitively, it is.
2. Could the authors provide the training cost of HopeDGN and the baselines?


[R2] A Short Tutorial on The Weisfeiler-Lehman Test And Its Variants.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730377410917

thread_type:
official_review

<thread_object>
creator: reviewer_aj2f

<content>
summary:
The paper introduces a novel Dynamic Graph Neural Network (DyGNN) framework called HopeDGN (Dynamic Graph Neural Network with High-order Expressive power). The primary focus of the paper is to address the limited expressive power of existing DyGNNs in capturing evolving patterns in dynamic graphs. The authors propose the k-dimensional Dynamic WL tests (k-DWL) as a theoretical framework to quantify the expressive power of DyGNNs, and introduce the Multi-Interacted Time Encoding (MITE) that captures the bi-interaction history of target node pairs with other nodes. MITE is integrated into the HopeDGN framework, and theoretical results show that HopeDGN can achieve expressive power equivalent to the 2-DWL test. Experimental results demonstrate that HopeDGN achieves superior performance on link prediction and node classification tasks compared to other baselines.

strengths:
- The Multi-Interacted Time Encoding (MITE) allows the model to capture indirect dependencies between node pairs, which is crucial for tasks like link prediction. This module is a plug-and-play component that can be integrated into various models, enhancing their expressive power.

- The paper provides proofs that HopeDGN can achieve expressive power equivalent to the 2-DWL test, which is a significant improvement over existing DyGNNs. This theoretical grounding adds credibility to the practical results.

- The authors discuss multiple model design details including Neighborhood encoding, patching and Transformer encoder. The authors conduct extensive experiments on both link prediction and node classification tasks across multiple datasets. The results consistently show that HopeDGN outperforms existing baselines, demonstrating its effectiveness.

weaknesses:
- The paper could benefit from a detailed comparison with other high-order GNNs that have been proposed for static graphs since the basic idea of encoding node pairs comes from high-order WL tests, like https://arxiv.org/abs/1810.02244.
- See questions below.

questions:
- I am confused with the example in Figure 1. Suppose the graph is static, according to symmetry 1-WL test will give identical labels to C and D, then GNN cannot distinguish node pairs (A, C) and (A, D) using only node embeddings, which has no connection to graph dynamics. And since 2-WL works on node pairs, we can easily verify that (A, C) and (A, D) will get different labels in 2-WL test so methods derived from 2-WL can distinguish them (like MITE). Therefore I don’t think that this example can well explain the expressive limitations of 1-DWL since it also works in static graphs. Can the authors provide more explanations?

- Can the proposed method work on dynamic graphs in which edge interaction can both start and end?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730581879432

thread_type:
official_review

<thread_object>
creator: reviewer_w1ok

<content>
summary:
The paper presents a novel dynamic graph neural network that is theoretically inspired by a proposed dynamic-WL test. According to this framework, they show that existing DyGNNs are bounded by 1-DWL test and by using a multi-interaction time encoding (MITE), they can increase the expressiveness to up to 2-DWL test. Then, they propose HopeDGN, which updates the representation of a node pair by aggregating not just the historical interactions but also the elapsed times. Through a transformer-based implementation, they show improved performance across seven datasets, while demonstrating plug-and-play benefits.

strengths:
- The proposed MITE matrix can be used in a plug-and-play fashion to provide gains in existing architectures. 
- Time complexity and efficiency analysis are provided.
- HopeDGN leverages the strengths of the transformer and a theoretically motivated WL-test to propose a more effective method.
- Empirical comparison is thorough in both transductive and inductive settings of link prediction against representative baselines.

weaknesses:
- 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. 
- Discussion with existing related work is casual and not carefully positioned. 
  - It is mentioned that it is not clear how relative positional features provide theoretical benefits even though it was shown theoretically in Souza et al., 2022 [1]. 
  - It is mentioned that "Souza et al. (2022) proves that adding a memory mechanism will not change the expressive power of DyGNNs. Therefore, the expressive power of DyGNNs can be fully characterized by the 1-DWL test." but this is wrong as they show that is true specifically when the architecture of the MP-GNN is deep enough. 
  - It is not clear whether what are the theoretical benefits of the proposed method as compared to [1] or [4]. It seems that the benefits are complementary but needs further discussion. Does the proposed method already provably reach the expressiveness of time-then-graph and PINT in their expressiveness tests.
- Space complexity is not provided nor computationally compared. The additional cost of storing B matrix along with the transformer architectures may be prohibitive in many cases and limit the scalability of the proposed method. 
- MITE encoding is similar to the time projection for staleness as done in JODIE [2] and TGN [3]. However, these similarities are neither acknowledged nor discussed in the paper. It seems like MITE is an extension of the time projection to the neighbors' encodings in addition to only the interacting node's embeddings. 
- 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, Equation 9 denotes that they should have considered all historical neighbors w for both graphs. This would have meant considering nodes b, h, d for graph (a) and nodes b, h, f for graph (b). In that case, d and f seem to be the difference maker and not b and h. 
- Considering the MITE interactions for all historical neighbors seem unscalable as the size of the graph increases. 
- Running time of HopeDGN is not compared against the baselines, only the training time is compared. 

[1] Souza, Amauri, et al. "Provably expressive temporal graph networks." Advances in neural information processing systems 35 (2022): 32257-32269.

[2] Kumar, Srijan, Xikun Zhang, and Jure Leskovec. "Predicting dynamic embedding trajectory in temporal interaction networks." Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining. 2019.

[3] Rossi, Emanuele, et al. "Temporal graph networks for deep learning on dynamic graphs." arXiv preprint arXiv:2006.10637 (2020).

[4] Gao, Jianfei, and Bruno Ribeiro. "On the equivalence between temporal and static graph representations for observational predictions." arXiv preprint arXiv:2103.07016 (2021).

questions:
see above weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730716350802

thread_type:
official_review

<thread_object>
creator: reviewer_hh9m

<content>
summary:
This paper introduces a k-dimensional dynamic Weisfeiler-Lehman (WL) test as a novel approach to quantify the expressiveness of dynamic graph neural networks (DyGNNs) and unifies simpler DyGNNs under the 1-Dimensional WL (1-DWL) framework. Additionally, the paper proposes HopeDGN, which employs a more granular encoding method to achieve the expressiveness of a 2-DWL test. Experimental results indicate the method’s effectiveness.

strengths:
1. The paper is the first to propose a k-dimensional dynamic WL test to evaluate the expressiveness of DyGNNs, addressing a relatively underexplored area in DyGNN expressiveness.
2. The proposed framework theoretically attains 2-DWL expressiveness by introducing a novel encoding scheme, which also shows potential for generalization to other models.
3. The model includes an optimized local version for practical applications, demonstrating strong performance.

weaknesses:
1. While prior DyGNNs may lack a unified framework, they have implemented numerous techniques to enhance expressiveness. Examples include DyGformer [1] with neighbor co-occurrence encoding, CAWN [2] with anonymous walk paths, and NAT [3] with neighborhood-aware encoding, etc. These methods are not addressed within the proposed framework, potentially making it appear somewhat isolated.
2. The theoretical time complexity of the k-DWL framework, especially over longer time spans, may be a concern, as noted by the authors. While local variants are proposed, practical usability could still be limited by these computational demands.

[1] Towards Better Dynamic Graph Learning: New Architecture and Unified Library https://arxiv.org/abs/2303.13047
[2] Inductive Representation Learning in Temporal Networks via Causal Anonymous Walks https://arxiv.org/abs/2101.05974
[3] Neighborhood-aware Scalable Temporal Network Representation Learning https://arxiv.org/abs/2209.01084

questions:
1. In Table 2, integrating MITE with other baselines shows significant improvements. How is this integration implemented, and does MITE demonstrate clear benefits compared to other encoding approaches?
2. Figure 5 highlights a notable efficiency improvement when reducing the neighbor length. What are the corresponding performance metrics associated with these efficiency gains?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732160029846

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response (Part 1/2)

comment:
We thank all reviewers for taking the time to review our paper and for providing valuable and insightful feedback. We recognize that the quality of this paper can be further improved, and we decide to withdraw this paper. 

Below are some overall clarifications for our work. 

**Motivation**. 

+ The expressive power of vanilla message-passing based DyGNNs is limited. Recently, some heuristic encodings have been designed to somewhat improve the expressive power of DyGNNs, such as DyGFormer [1], CAWN [2], PINT [3], **but the expressive power of these models is not quantified by some benchmarking criterions (such as k-WL tests in static graph).** 

**Contribution of this work**.

+ In analogy to WL tests in static graph, we propose a benchmarking hierarchy named **k-DWL test** to quantify the level of expressive power of DyGNNs. Then, we propose **HopeDGN** which is proven to be as expressive as 2-DWL test, thus its high-order expressive power can be clearly quantified.

**Ref:**  
+ [1] Yu L, Sun L, Du B, et al. Towards better dynamic graph learning: New architecture and unified library[J]. Advances in Neural Information Processing Systems, 2023, 36: 67686-67700.  
+ [2] Wang Y, Chang Y Y, Liu Y, et al. Inductive representation learning in temporal networks via causal anonymous walks[J]. arXiv preprint arXiv:2101.05974, 2021.  
+ [3] Souza A, Mesquita D, Kaski S, et al. Provably expressive temporal graph networks[J]. Advances in neural information processing systems, 2022, 35: 32257-32269.
</content>
</thread_object>

</thread>


Metareview: