Research map / Graph learning / GNN architectures

GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

NeurIPS 2026 · Graph learning › GNN architectures · approach: Physics-inspired GNNs · 0 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 GRAPHLCP, a localized conformal prediction method for GNNs that uses a PPR-based structural kernel on a feature-densified graph to weight calibration nodes and sample anchors, achieving marginal coverage with tighter, more conditionally valid sets.

Problem

Conformal prediction for GNNs struggles to obtain informative localization: embedding-space proximity becomes indiscriminative due to over-smoothing and poor separability, and sparse graphs cause locality bias, yielding inefficient or poorly localized prediction sets.

Approach

Replace embedding-based kernels in randomized localized CP (RLCP) with a Personalized PageRank kernel computed on a graph densified by thresholded Gaussian similarities over PCA-reduced embeddings with adaptive bandwidth, so anchors and calibration weights reflect structural proximity.

Key results

• On WSC, GRAPHLCP achieves second-best coverage on most datasets, e.g., 0.67 on ANH vs 0.68 for SNAPS and 0.61 for SCP.
• Ablation on WKB shows PPR kernel improves coverage over Gaussian kernel (0.63 vs 0.68 reported in table is mixed; e.g., on TWT 0.71 vs 0.71), with PPR giving shorter prediction length on most regression datasets such as ANH (1.61 vs 1.66).
• Marginal coverage stays near the 0.9 target for all methods (e.g., 0.905 on ANH) while CalLCP over-covers (~0.94).

Surprising findings

• Standard CalLCP over-covers (~0.94 marginal) and produces larger sets than necessary, while SCP yields the smallest prediction lengths.
• Gaussian-kernel RLCP weights collapse to Dirac or uniform distributions on GNN embeddings, reducing it to SCP or isolating test points.

Limitations

• Substantially slower than SCP and RLCP on larger graphs, e.g., 508.8 s on DBLP.
• Conditional coverage evaluated only via WSC and group-based diagnostics; exact conditional coverage is infeasible and the guarantee is relaxed.
• Does not incorporate node attributes into the PPR kernel directly; relies on GNN embeddings for densification.

Experimental setup

Datasets: Cora_ML DBLP PubMed Computers Education Election Income Unemployment Anaheim Chicago Twitch GOOD-WebKB

Benchmarks: Cora_ML DBLP PubMed Computers Education Election Income Unemployment Anaheim Chicago Twitch GOOD-WebKB

Metrics: marginal coverage worst-slab coverage (WSC) prediction length group-conditional minimum coverage

Baselines: SCP RLCP CalLCP NAPS CF-GNN SNAPS

Builds on: RLCP weighted conformal prediction personalized pagerank CalLCP SNAPS

Closest papers by meaning

• Similarity-Navigated Conformal Prediction for Graph Neural Networks (NeurIPS 2024 · similarity 0.89)
• Enhancing Trustworthiness of Graph Neural Networks with Rank-Based Conformal Training (AAAI 2025 · similarity 0.87)
• Conformal Structured Prediction (ICLR 2025 · similarity 0.87)
• Valid Conformal Prediction for Dynamic GNNs (ICLR 2025 · similarity 0.87)
• Positional Encoding meets Persistent Homology on Graphs (ICML 2025 · similarity 0.86)
• Topology-Aware Conformal Prediction for Stream Networks (NeurIPS 2025 · similarity 0.86)