Research map / Graph learning / Graph self-supervised learning

Similarity-Navigated Conformal Prediction for Graph Neural Networks

NeurIPS 2024 · Graph learning › Graph self-supervised learning · approach: Semi-supervised node representation learning · 1 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes SNAPS, a post-hoc conformal prediction method for GNN node classification that aggregates APS non-conformity scores over feature-similarity k-NN nodes and one-hop neighbors, yielding smaller prediction sets and higher singleton hit ratio at valid coverage.

Problem

Conformal prediction sets for semi-supervised node classification with GNNs are often large and inefficient, and singleton hit ratio is low; existing graph-aware CP (DAPS) only uses structural neighbors.

Approach

Aggregate basic non-conformity scores (APS) across nodes likely sharing the ego node's label, selected by feature-similarity k-NN and one-hop structural neighbors, with a weighted combination that preserves exchangeability and marginal coverage.

Key results

• On OGBN Products (alpha=0.05, GCN), SNAPS reduces average prediction set size from 14.92 (APS) to 7.68 while keeping coverage at 0.950.
• Average over 10 graph datasets at alpha=0.05: SNAPS size 3.17 vs APS 5.23 and DAPS 3.79; singleton hit ratio 52.31% vs DAPS 48.01%.
• On ImageNet with ResNeXt101 at alpha=0.1, SNAPS reduces set size from 19.64 to 4.08 with coverage 0.900.

Measured effects reported in the paper

Surprising findings

• Oracle experiments show that aggregating scores of randomly chosen same-label nodes sharply reduces set size, motivating label-aware aggregation.
• Feature-similarity k-NN selects same-label nodes with reasonable accuracy only when k is not very large; performance declines slightly for extremely large k.

Limitations

• Node selection via feature similarity is computationally inefficient and not highly accurate at identifying same-label nodes.
• Method is limited to transductive setting and focuses on homophilous graphs; heterophily results are preliminary.
• Hyperparameters lambda, mu, k tuned on calibration split; theoretical validity proposition assumes aggregated nodes share the ego label.

Experimental setup

Datasets: CoraML PubMed CiteSeer CoraFull* Coauthor CS Coauthor Physics Amazon Photos Amazon Computers OGBN Arxiv OGBN Products ImageNet Chameleon

Benchmarks: CoraML PubMed CiteSeer CoraFull* Coauthor CS Coauthor Physics Amazon Photos Amazon Computers OGBN Arxiv OGBN Products ImageNet Chameleon

Metrics: coverage average prediction set size singleton hit ratio size-stratified coverage violation

Baselines: APS RAPS DAPS CF-GNN

Builds on: adaptive prediction sets DAPS split conformal prediction

Closest papers by meaning

• Distribution Free Prediction Sets for Node Classification (ICML 2023 · similarity 0.90)
• GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs (NeurIPS 2026 · similarity 0.89)
• Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training (AAAI 2025 · similarity 0.87)
• Valid Conformal Prediction for Dynamic GNNs (ICLR 2025 · similarity 0.86)
• Conformal Structured Prediction (ICLR 2025 · similarity 0.86)
• Random Search Neural Networks for Efficient and Expressive Graph Learning (NeurIPS 2025 · similarity 0.85)