论文标题
OOD链路链接预测通用能力在较大的测试图中通过消息传播的GNN
OOD Link Prediction Generalization Capabilities of Message-Passing GNNs in Larger Test Graphs
论文作者
论文摘要
这项工作提供了关于图形消息传递神经网络（GMPNN）的能力的首次理论研究（例如图形神经网络（GNNS）），可以执行归纳性脱离分布（OOD）链接预测任务，其中部署（测试）图形大小比训练图更大。我们首先证明了非反应界限，表明基于GMPNN获得的基于置换量等均值（结构）节点嵌入的链接预测变量可以随着测试图变大，可以收敛到随机猜测。然后，我们提出了一个理论上的GMPNN，该GMPNN输出结构性成对（2节点）嵌入，并证明非扰动界限，表明随着测试图的增长，这些嵌入式会收敛到连续函数的嵌入，以保留其预测链接的能力。随机图的经验结果表明与我们的理论结果一致。
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.
