Efficient and Effective Implicit Dynamic Graph Neural Network

Yongjian Zhong; Hieu Vu; Tianbao Yang; Bijaya Adhikari

doi:10.1145/3637528.3672026

Back

Efficient and Effective Implicit Dynamic Graph Neural Network

Conference proceeding

Open access

Efficient and Effective Implicit Dynamic Graph Neural Network

Yongjian Zhong, Hieu Vu, Tianbao Yang and Bijaya Adhikari

Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.4595-4606

ACM Conferences

KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining

08/25/2024

DOI: 10.1145/3637528.3672026

Appears in UI Libraries Support Open Access

Files and links (1)

url

https://doi.org/10.1145/3637528.3672026View

Published (Version of record) Open Access

Abstract

Implicit graph neural networks have gained popularity in recent years as they capture long-range dependencies while improving predictive performance in static graphs. Despite the tussle between performance degradation due to the oversmoothing of learned embeddings and long-range dependency being more pronounced in dynamic graphs, as features are aggregated both across neighborhood and time, no prior work has proposed an implicit graph neural model in a dynamic setting. In this paper, we present Implicit Dynamic Graph Neural Network (IDGNN) a novel implicit neural network for dynamic graphs which is the first of its kind. A key characteristic of IDGNN is that it demonstrably is well-posed, i.e., it is theoretically guaranteed to have a fixed-point representation. We then demonstrate that the standard iterative algorithm often used to train implicit models is computationally expensive in our dynamic setting as it involves computing gradients, which themselves have to be estimated in an iterative manner. To overcome this, we pose an equivalent bilevel optimization problem and propose an efficient single-loop training algorithm that avoids iterative computation by maintaining moving averages of key components of the gradients. We conduct extensive experiments on real-world datasets on both classification and regression tasks to demonstrate the superiority of our approach over state-of-the-art baselines. We also demonstrate that our bi-level optimization framework maintains the performance of the expensive iterative algorithm while obtaining up to 1600x speed-up.

Computing methodologies -- Artificial intelligence -- Knowledge representation and reasoning -- Temporal reasoning

Computing methodologies -- Machine learning -- Machine learning approaches -- Neural networks

UIOWA OA Agreement

Details

Title: Subtitle: Efficient and Effective Implicit Dynamic Graph Neural Network
Creators: Yongjian Zhong - University of Iowa
Hieu Vu - University of Iowa
Tianbao Yang - Texas A&M University
Bijaya Adhikari - University of Iowa
Resource Type: Conference proceeding
Publication Details: Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pp.4595-4606
Conference: KDD '24: The 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining
Publisher: Association for Computing Machinery (ACM)
Series: ACM Conferences
DOI: 10.1145/3637528.3672026
Language: English
Date published: 08/25/2024
Academic Unit: Computer Science
Record Identifier: 9984699517402771

Metrics

3 Record Views