Timezone: »

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

@
in New Frontiers in Graph Learning »
Event URL: https://openreview.net/forum?id=2neXknZg9ej »

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 introduce 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.Our experiments demonstrate that PINT significantly outperforms existing TGNs on several real-world benchmarks.

Keywords: link prediction · Graph Representation Learning · temporal graph learning

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