mlsanityData to 7 Oct 2026

Statistical Guarantees for Link Prediction using Graph Neural Networks

arXiv 2402.02692 ↗First posted 5 Feb 2024cs.LG cs.SI math.STcited by 2

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 15 of its 49 references that are in the map. First posted on arXiv 5 Feb 2024.

Builds on

15 of 49 references.

References · 15

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2018How Powerful are Graph Neural Networks?cited by 4,355
  3. 2018Link Prediction Based on Graph Neural Networkscited by 829
  4. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  5. 2020Building powerful and equivariant graph neural networks with structural message-passingcited by 95
  6. 2020Convergence and Stability of Graph Convolutional Networks on Large Random Graphscited by 75
  7. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  8. 2022Generalization Analysis of Message Passing Neural Networks on Large Random Graphscited by 58
  9. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  10. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  11. 2020Strong Consistency, Graph Laplacians, and the Stochastic Block Modelcited by 20
  12. 2021Asymptotics of Network Embeddings Learned via Subsamplingcited by 10
3 more
  1. 2021Community detection using low-dimensional network embedding algorithmscited by 4
  2. 2021Exact Recovery of Community Structures Using DeepWalk and Node2veccited by 2
  3. 2023A Local Graph Limits Perspective on Sampling-Based GNNscited by 2

Built on by

Cited by year

Citing papers per year: 2024: 2.

2 papers.

  1. 2024On provable privacy vulnerabilities of graph representationscited by 1
  2. 2024Perfect Recovery for Random Geometric Graph Matching with Shallow Graph Neural Networkscited by 0