DyFormer: A Scalable Dynamic Graph Transformer with Provable Benefits on Generalization Ability

Weilin Cong, Yanhong Wu, Yuandong Tian, Mengting Gu, Yinglong Xia, Chun Cheng Jason Chen, Mehrdad Mahdavi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

Transformers have achieved great success in several domains, including Natural Language Processing and Computer Vision. However, their application to real-world graphs is less explored, mainly due to its high computation cost and its poor generalizability caused by the lack of enough training data in the graph domain. To fill in this gap, we propose a scalable Transformer-like dynamic graph learning method named Dynamic Graph Transformer (DyFormer) with spatial-temporal encoding to effectively learn graph topology and capture implicit links. To achieve efficient and scalable training, we propose temporal-union graph structure and its associated subgraph-based node sampling strategy. To improve the generalization ability, we introduce two complementary self-supervised pre-training tasks and show that jointly optimizing the two pre-training tasks results in a smaller Bayesian error rate via an information-theoretic analysis. Extensive experiments on the real-world datasets illustrate that DyFormer achieves a consistent 1% ~ 3% AUC gain (averaged over all time steps) compared with baselines on all benchmarks.

Original languageEnglish (US)
Title of host publication2023 SIAM International Conference on Data Mining, SDM 2023
PublisherSociety for Industrial and Applied Mathematics Publications
Pages442-450
Number of pages9
ISBN (Electronic)9781611977653
StatePublished - 2023
Event2023 SIAM International Conference on Data Mining, SDM 2023 - Minneapolis, United States
Duration: Apr 27 2023Apr 29 2023

Publication series

Name2023 SIAM International Conference on Data Mining, SDM 2023

Conference

Conference2023 SIAM International Conference on Data Mining, SDM 2023
Country/TerritoryUnited States
CityMinneapolis
Period4/27/234/29/23

All Science Journal Classification (ASJC) codes

  • Education
  • Information Systems

Cite this