This work provides the first theoretical study on the ability of graph Message Passing Neural Networks (gMPNNs) -- such as Graph Neural Networks (GNNs) -- to achieve counterfactually-invariant representations for 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.

翻译：这项工作首次对图形消息传递神经网络(gMPNNs) -- -- 如图形神经网络(GNNS) -- -- 的能力进行了理论研究,以便实现反实际的反变量表达式,用于感性流出(OOOD)链接预测任务,因为部署(测试)图形的大小大于培训图形。我们首先证明非非无源界限,显示GMPNS获得的基于静态(结构性)节点嵌入的链接预测器能够随着测试图形的扩大而随机组合为随机猜测。我们然后提议一个理论上健全的GMPNN,输出成结构对齐(2-诺德)嵌入并证明非自动边框显示,随着测试图的增长,这些嵌入会嵌入到持续功能的嵌入中,从而保留着预测链接 OODD(结构性)的功能。随机图形的亲切结果显示我们理论结果的一致。