OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
MCML Authors
Gitta Kutyniok
Prof. Dr.
Core PI
Abstract
Gitta Kutyniok
Prof. Dr.
Core PI
Abstract
This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) ---such as Graph Neural Networks (GNNs)--- to perform inductive out-of-distribution (OOD) link prediction tasks, where deployment (test) graph sizes are larger than training graphs. We first prove non-asymptotic bounds showing that link predictors based on permutation-equivariant (structural) node embeddings obtained by gMPNNs can converge to a random guess as test graphs get larger. We then propose a theoretically-sound gMPNN that outputs structural pairwise (2-node) embeddings and prove non-asymptotic bounds showing that, as test graphs grow, these embeddings converge to embeddings of a continuous function that retains its ability to predict links OOD. Empirical results on random graphs show agreement with our theoretical results.
inproceedings ZKR22
NeurIPS 2022
36th Conference on Neural Information Processing Systems. New Orleans, LA, USA, Nov 28-Dec 09, 2022.
Authors
Y. Zhou • G. Kutyniok • B. RibeiroLinks
DOIResearch Area
BibTeXKey: ZKR22