Timezone: »

 
Poster
Provably expressive temporal graph networks
Amauri Souza · Diego Mesquita · Samuel Kaski · Vikas Garg

Tue Nov 29 02:00 PM -- 04:00 PM (PST) @ Hall J #834
in Poster Session 2 »

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.

Keywords: graph neural networks · link prediction · temporal graphs

Author Information

Amauri Souza (Aalto University)
Diego Mesquita (Getulio Vargas Foundation)
Samuel Kaski (Aalto University and University of Manchester)
Vikas Garg (Aalto University/YaiYai Ltd)

More from the Same Authors