Provably expressive temporal graph networks

No Thumbnail Available
Journal Title
Journal ISSN
Volume Title
Conference article in proceedings
This publication is imported from Aalto University research portal.
View publication in the Research portal

Other link related to publication
Date
2022
Major/Subject
Mcode
Degree programme
Language
en
Pages
13
Series
Advances in Neural Information Processing Systems 35 (NeurIPS 2022), Advances in Neural Information Processing Systems, Volume 35
Abstract
Temporal graph networks (TGNs) have gained prominence as models for embedding dynamic interactions, but little is known about their theoretical underpinnings. We establish fundamental results about the representational power and limits of the two main categories of TGNs: those that aggregate temporal walks (WA-TGNs), and those that augment local message passing with recurrent memory modules (MP-TGNs). Specifically, novel constructions reveal the inadequacy of MP-TGNs and WA-TGNs, proving that neither category subsumes the other. We extend the 1-WL (Weisfeiler-Leman) test to temporal graphs, and show that the most powerful MP-TGNs should use injective updates, as in this case they become as expressive as the temporal WL. Also, we show that sufficiently deep MP-TGNs cannot benefit from memory, and MP/WA-TGNs fail to compute graph properties such as girth. These theoretical insights lead us to PINT --- a novel architecture that leverages injective temporal message passing and relative positional features. Importantly, PINT is provably more expressive than both MP-TGNs and WA-TGNs. PINT significantly outperforms existing TGNs on several real-world benchmarks.
Description
| openaire: EC/H2020/951847/EU//ELISE
Keywords
Other note
Citation
Souza, A H, Mesquita, D, Kaski, S & Garg, V 2022, Provably expressive temporal graph networks . in S Koyejo, S Mohamed, A Agarwal, D Belgrave, K Cho & A Oh (eds), Advances in Neural Information Processing Systems 35 (NeurIPS 2022) . Advances in Neural Information Processing Systems, vol. 35, Morgan Kaufmann Publishers, Conference on Neural Information Processing Systems, New Orleans, Louisiana, United States, 28/11/2022 . < https://proceedings.neurips.cc/paper_files/paper/2022/hash/d029c97ee0db162c60f2ebc9cb93387e-Abstract-Conference.html >