Provably expressive temporal graph networks

Vikas Garg; Samuel Kaski; Diego Parente Paiva Mesquita; Amauri Holanda De Souza Junior

Provably expressive temporal graph networks

Vikas Garg, Samuel Kaski, Diego Parente Paiva Mesquita, Amauri Holanda De Souza Junior

Machine Learning and Robotics

Aalto University

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

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. Import

Original language	English
Title of host publication	Advances in Neural Information Processing Systems 35
Subtitle of host publication	36th Conference on Neural Information Processing Systems (NeurIPS 2022)
Editors	S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, A. Oh
Place of Publication	Red Hook, NY
Publisher	Curran Associates, Inc.
Pages	32257-32269
Number of pages	13
Volume	42
ISBN (Electronic)	9781713873129
ISBN (Print)	9781713871088
Publication status	Published - Apr 2023
Event	Conference on Neural Information Processing Systems - Duration: 28 Nov 2022 → 9 Dec 2022

Conference

Conference	Conference on Neural Information Processing Systems
Period	28/11/22 → 9/12/22

Research Beacons, Institutes and Platforms

Institute for Data Science and AI
Digital Futures
Sustainable Futures

Access to Document

MCAIF: Centre for AI Fundamentals
Kaski, S. (PI), Alvarez, M. (Researcher), Pan, W. (Researcher), Mu, T. (Researcher), Rivasplata, O. (PI), Sun, M. (PI), Mukherjee, A. (PI), Caprio, M. (PI), Sonee, A. (Researcher), Leroy, A. (Researcher), Wang, J. (Researcher), Lee, J. (Researcher), Parakkal Unni, M. (Researcher), Sloman, S. (Researcher), Menary, S. (Researcher), Quilter, T. (Researcher), Hosseinzadeh, A. (PGR student), Mousa, A. (PGR student), Glover, E. (PGR student), Das, A. (PGR student), DURSUN, F. (PGR student), Zhu, H. (PGR student), Abdi, H. (PGR student), Dandago, K. (PGR student), Piriyajitakonkij, M. (PGR student), Rachman, R. (PGR student), Shi, X. (PGR student), Keany, T. (PGR student), Liu, X. (PGR student), Jiang, Y. (PGR student), Wan, Z. (PGR student), Harrison, M. (Support team), Machado, M. (Support team), Hartford, J. (PI), Kangin, D. (Researcher), Harikumar, H. (PI), Dubey, M. (PI), Parakkal Unni, M. (PI), Dash, S. P. (PGR student), Mi, X. (PGR student) & Barlas, Y. (PGR student)
1/10/21 → 30/09/26
Project: Research
Turing AI Fellowship: Human-AI Research Teams - Steering AI in Experimental Design and Decision-Making
Kaski, S. (PI), Bristow, R. (CoI), Cai, P. (CoI), Jay, C. (CoI) & Peek, N. (CoI)
1/10/21 → 30/09/26
Project: Research

Cite this

Garg, V., Kaski, S., Parente Paiva Mesquita, D., & Holanda De Souza Junior, A. (2023). 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: 36th Conference on Neural Information Processing Systems (NeurIPS 2022) (Vol. 42, pp. 32257-32269). Curran Associates, Inc.. https://arxiv.org/pdf/2209.15059.pdf

Garg, Vikas ; Kaski, Samuel ; Parente Paiva Mesquita, Diego et al. / Provably expressive temporal graph networks. Advances in Neural Information Processing Systems 35: 36th Conference on Neural Information Processing Systems (NeurIPS 2022). editor / S. Koyejo ; S. Mohamed ; A. Agarwal ; D. Belgrave ; K. Cho ; A. Oh. Vol. 42 Red Hook, NY : Curran Associates, Inc., 2023. pp. 32257-32269

@inproceedings{4f6cc34b1f9e4accbe8a488291d809ed,

title = "Provably expressive temporal graph networks",

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. Import",

author = "Vikas Garg and Samuel Kaski and {Parente Paiva Mesquita}, Diego and {Holanda De Souza Junior}, Amauri",

year = "2023",

month = apr,

language = "English",

isbn = "9781713871088",

volume = "42",

pages = "32257--32269",

editor = "S. Koyejo and S. Mohamed and A. Agarwal and D. Belgrave and K. Cho and A. Oh",

booktitle = "Advances in Neural Information Processing Systems 35",

publisher = "Curran Associates, Inc.",

address = "United States",

note = "Conference on Neural Information Processing Systems ; Conference date: 28-11-2022 Through 09-12-2022",

}

Garg, V, Kaski, S, Parente Paiva Mesquita, D & Holanda De Souza Junior, A 2023, 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: 36th Conference on Neural Information Processing Systems (NeurIPS 2022). vol. 42, Curran Associates, Inc., Red Hook, NY, pp. 32257-32269, Conference on Neural Information Processing Systems, 28/11/22. <https://arxiv.org/pdf/2209.15059.pdf>

Provably expressive temporal graph networks. / Garg, Vikas; Kaski, Samuel; Parente Paiva Mesquita, Diego et al.
Advances in Neural Information Processing Systems 35: 36th Conference on Neural Information Processing Systems (NeurIPS 2022). ed. / S. Koyejo; S. Mohamed; A. Agarwal; D. Belgrave; K. Cho; A. Oh. Vol. 42 Red Hook, NY: Curran Associates, Inc., 2023. p. 32257-32269.

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Provably expressive temporal graph networks

AU - Garg, Vikas

AU - Kaski, Samuel

AU - Parente Paiva Mesquita, Diego

AU - Holanda De Souza Junior, Amauri

PY - 2023/4

Y1 - 2023/4

N2 - 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. Import

AB - 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. Import

M3 - Conference contribution

SN - 9781713871088

VL - 42

SP - 32257

EP - 32269

BT - Advances in Neural Information Processing Systems 35

A2 - Koyejo, S.

A2 - Mohamed, S.

A2 - Agarwal, A.

A2 - Belgrave, D.

A2 - Cho, K.

A2 - Oh, A.

PB - Curran Associates, Inc.

CY - Red Hook, NY

T2 - Conference on Neural Information Processing Systems

Y2 - 28 November 2022 through 9 December 2022

ER -

Garg V, Kaski S, Parente Paiva Mesquita D, Holanda De Souza Junior A. Provably expressive temporal graph networks. In Koyejo S, Mohamed S, Agarwal A, Belgrave D, Cho K, Oh A, editors, Advances in Neural Information Processing Systems 35: 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Vol. 42. Red Hook, NY: Curran Associates, Inc. 2023. p. 32257-32269

Provably expressive temporal graph networks

Abstract

Conference

Research Beacons, Institutes and Platforms

Access to Document

Fingerprint

Projects

MCAIF: Centre for AI Fundamentals

Turing AI Fellowship: Human-AI Research Teams - Steering AI in Experimental Design and Decision-Making

Cite this