Timezone: »
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.
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
-
2022 : Modular Flows: Differential Molecular Generation »
Yogesh Verma · Samuel Kaski · Markus Heinonen · Vikas Garg -
2022 : Locking and Quacking: Stacking Bayesian models predictions by log-pooling and superposition »
Yuling Yao · Luiz Carvalho · Diego Mesquita -
2022 : Targeted Causal Elicitation »
Nazaal Ibrahim · ST John · Zhigao Guo · Samuel Kaski -
2022 : More trustworthy Bayesian optimization of materials properties by adding human into the loop »
Armi Tiihonen · Louis Filstroff · Petrus Mikkola · Emma Lehto · Samuel Kaski · Milica Todorović · Patrick Rinke -
2022 : Provably expressive temporal graph networks »
Amauri Souza · Diego Mesquita · Samuel Kaski · Vikas Garg -
2022 : Modular Flows: Differential Molecular Generation »
Yogesh Verma · Samuel Kaski · Markus Heinonen · Vikas Garg -
2022 : Differentiable User Models »
Alex Hämäläinen · Mustafa Mert Çelikok · Samuel Kaski -
2023 Poster: Thin and deep Gaussian processes »
Daniel Augusto de Souza · Alexander Nikitin · ST John · Magnus Ross · Mauricio A Álvarez · Marc Deisenroth · João Paulo Gomes · Diego Mesquita · César Lincoln Mattos -
2023 Poster: Practical Equivariances via Relational Conditional Neural Processes »
Daolang Huang · Manuel Haussmann · Ulpu Remes · ST John · Grégoire Clarté · Kevin Sebastian Luck · Samuel Kaski · Luigi Acerbi -
2023 Poster: Compositional Sculpting of Iterative Generative Processes »
Timur Garipov · Sebastiaan De Peuter · Ge Yang · Vikas Garg · Samuel Kaski · Tommi Jaakkola -
2023 Poster: Learning Robust Statistics for Simulation-based Inference under Model Misspecification »
Daolang Huang · Ayush Bharti · Amauri Souza · Luigi Acerbi · Samuel Kaski -
2023 Poster: Going beyond persistent homology using persistent homology »
Johanna Immonen · Amauri Souza · Vikas Garg -
2023 Oral: Going beyond persistent homology using persistent homology »
Johanna Immonen · Amauri Souza · Vikas Garg -
2022 Spotlight: Are GANs overkill for NLP? »
David Alvarez-Melis · Vikas Garg · Adam Kalai -
2022 : Panel »
Vikas Garg · Pan Li · Srijan Kumar · Emanuele Rossi · Shenyang Huang -
2022 : KeyNote 3 by Vikas Garg: Provably Powerful Temporal Graph Networks »
Vikas Garg -
2022 : Panel Discussion »
Cynthia Rudin · Dan Bohus · Brenna Argall · Alison Gopnik · Igor Mordatch · Samuel Kaski -
2022 : Collaborative AI for assisting virtual laboratories »
Samuel Kaski -
2022 : Noise-Aware Statistical Inference with Differentially Private Synthetic Data »
Ossi Räisä · Joonas Jälkö · Antti Honkela · Samuel Kaski -
2022 : HAPNEST: An efficient tool for generating large-scale genetics datasets from limited training data »
Sophie Wharrie · Zhiyu Yang · Vishnu Raj · Remo Monti · Rahul Gupta · Ying Wang · Alicia Martin · Luke O'Connor · Samuel Kaski · Pekka Marttinen · Pier Palamara · Christoph Lippert · Andrea Ganna -
2022 Poster: Modular Flows: Differential Molecular Generation »
Yogesh Verma · Samuel Kaski · Markus Heinonen · Vikas Garg -
2022 Poster: Are GANs overkill for NLP? »
David Alvarez-Melis · Vikas Garg · Adam Kalai -
2022 Poster: Symmetry-induced Disentanglement on Graphs »
Giangiacomo Mercatali · Andre Freitas · Vikas Garg -
2022 Poster: Deconfounded Representation Similarity for Comparison of Neural Networks »
Tianyu Cui · Yogesh Kumar · Pekka Marttinen · Samuel Kaski -
2021 Poster: De-randomizing MCMC dynamics with the diffusion Stein operator »
Zheyang Shen · Markus Heinonen · Samuel Kaski -
2020 Poster: Rethinking pooling in graph neural networks »
Diego Mesquita · Amauri Souza · Samuel Kaski -
2019 Poster: Solving graph compression via optimal transport »
Vikas Garg · Tommi Jaakkola -
2019 Poster: Generative Models for Graph-Based Protein Design »
John Ingraham · Vikas Garg · Regina Barzilay · Tommi Jaakkola -
2019 Poster: Machine Teaching of Active Sequential Learners »
Tomi Peltola · Mustafa Mert Çelikok · Pedram Daee · Samuel Kaski -
2019 Poster: Online Markov Decoding: Lower Bounds and Near-Optimal Approximation Algorithms »
Vikas Garg · Tamar Pichkhadze -
2018 Poster: Learning SMaLL Predictors »
Vikas Garg · Ofer Dekel · Lin Xiao -
2018 Poster: Supervising Unsupervised Learning »
Vikas Garg · Adam Kalai -
2018 Spotlight: Supervising Unsupervised Learning »
Vikas Garg · Adam Kalai -
2017 Poster: Non-Stationary Spectral Kernels »
Sami Remes · Markus Heinonen · Samuel Kaski -
2017 Poster: Differentially private Bayesian learning on distributed data »
Mikko Heikkilä · Eemil Lagerspetz · Samuel Kaski · Kana Shimizu · Sasu Tarkoma · Antti Honkela -
2016 Poster: Learning Tree Structured Potential Games »
Vikas Garg · Tommi Jaakkola -
2014 Workshop: Machine Learning in Computational Biology »
Oliver Stegle · Sara Mostafavi · Anna Goldenberg · Su-In Lee · Michael Leung · Anshul Kundaje · Mark B Gerstein · Martin Renqiang Min · Hannes Bretschneider · Francesco Paolo Casale · Loïc Schwaller · Amit G Deshwar · Benjamin A Logsdon · Yuanyang Zhang · Ali Punjani · Derek C Aguiar · Samuel Kaski