OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs. (arXiv:2205.15117v5 [cs.LG] UPDATED)

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 …

arxiv gnns graphs link prediction prediction test