Statistical Guarantees for Link Prediction using Graph Neural Networks
It addresses the need for theoretical foundations in GNN-based link prediction, offering guarantees for both sparse and dense graphs, though it is incremental in extending existing statistical methods to this domain.
This paper tackles the problem of providing statistical guarantees for Graph Neural Networks (GNNs) in link prediction on graphon-generated graphs, resulting in a linear GNN architecture that yields consistent estimators and error bounds for edge probabilities.
This paper derives statistical guarantees for the performance of Graph Neural Networks (GNNs) in link prediction tasks on graphs generated by a graphon. We propose a linear GNN architecture (LG-GNN) that produces consistent estimators for the underlying edge probabilities. We establish a bound on the mean squared error and give guarantees on the ability of LG-GNN to detect high-probability edges. Our guarantees hold for both sparse and dense graphs. Finally, we demonstrate some of the shortcomings of the classical GCN architecture, as well as verify our results on real and synthetic datasets.