OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
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.