Preserving spatial-temporal relationship with adaptive node sampling in hierarchical dynamic graph transformers

Dynamic Graph Transformers (DGTs) have demonstrated remarkable performance in various applications, such as social networks, traffic forecasting, and recommendation systems. Despite their effectiveness in capturing long-range dependencies, training DGTs for large graphs remains a challenge. Mini-batch training is usually used to alleviate this challenge but this approach often fails to capture complex dependencies or sacrifice performance. To deal with the above problems, we propose the Adaptive Node Sampling in Hierarchical Dynamic Graph Transformers (ASH-DGT) architecture that focuses on sampling the set of suitable nodes preserving spatial-temporal relationships in the dynamic graph for training DGTs. Unlike previous methods that use random sampling or structural sampling, our motivation is that the contribution of nodes to learning performance can be time-sensitive, while we still care about spatial correlation in the dynamic graph with consideration to the global and local structure of the graph. Through extensive evaluations on popular real-world datasets for node classification and link prediction, ASH-DGT consistently outperforms multiple state-of-the-art methods, achieving both higher accuracy and significant improvements in training efficiency.