Timezone: »

 
Spotlight
OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
Yangze Zhou · Gitta Kutyniok · Bruno Ribeiro

Tue Dec 06 09:00 AM -- 11:00 AM (PST) @
in Lightning Talks 1B-1 »

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.

Keywords: graphon · link prediction · OOD · Message Passing GNNs · random graphs · GNNs

Author Information

Yangze Zhou (Purdue University)
Gitta Kutyniok (LMU München)
Bruno Ribeiro (Purdue)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors