Statistical Guarantees for Link Prediction using Graph Neural Networks

2024-02-05 · Alan Chung, Amin Saberi, Morgane Austern

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.

📄 PDF Abstract BibTeX arXiv:2402.02692

Code (0)

등록된 구현이 없습니다.

Tasks

Link Prediction Prediction

Methods 이 논문이 사용한 방법론

GCN A Graph Convolutional Network, or GCN, is an approach for semi-supervised learning on graph-structured data. It is based on an efficient variant of [convolutional neural…

Conformalized Link Prediction on Graph Neural Networks

2024-06-26 · Tianyi Zhao, Jian Kang, Lu Cheng

Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications in high-stakes domains are often hampered by unreliable predictions. Although numerous uncertainty quantification methods have been proposed to …

Conformal Prediction Link Prediction Prediction Uncertainty Quantification

Compact Conformal Subgraphs

2026-02-07 · Sreenivas Gollapudi, Kostas Kollias, Kamesh Munagala, Aravindan Vijayaraghavan arxiv

Conformal prediction provides rigorous, distribution-free uncertainty guarantees, but often yields prohibitively large prediction sets in structured domains such as routing, planning, or sequential recommendation. We int…

Sequential Recommendation

The Consistency of Common Neighbors for Link Prediction in Stochastic Blockmodels

2015-12-01 · NeurIPS 2015 12 · Purnamrita Sarkar, Deepayan Chakrabarti, Peter J. Bickel

Link prediction and clustering are key problems for network-structureddata. While spectral clustering has strong theoretical guaranteesunder the popular stochastic blockmodel formulation of networks, itcan be expensive f…

Clustering Link Prediction

A General Theory for Structured Prediction with Smooth Convex Surrogates

2019-02-05 · Alex Nowak-Vila, Francis Bach, Alessandro Rudi

In this work we provide a theoretical framework for structured prediction that generalizes the existing theory of surrogate methods for binary and multiclass classification based on estimating conditional probabilities w…

General Classification Graph Matching regression Structured Prediction

Improving global awareness of linkset predictions using Cross-Attentive Modulation tokens

2024-05-28 · Félix Marcoccia, Cédric Adjih, Paul Mühlethaler

This work introduces Cross-Attentive Modulation (CAM) tokens, which are tokens whose initial value is learned, gather information through cross-attention, and modulate the nodes and edges accordingly. These tokens are me…

Denoising Graph Generation Link Prediction