GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

• URL: http://arxiv.org/abs/2605.08074v1
• Date: Fri, 08 May 2026 17:56:09 GMT
• Title: GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs
• Abstract summary: Conformal prediction (CP) provides a distribution-free approach to uncertainty with finite-sample guarantees.<n>Applying CP to graph neural networks (GNNs) remains challenging as the nature of graphs often leads to insufficiently certain predictions.<n>We propose GRAPHLCP, a proximity-based localized CP framework that explicitly incorporates graph topology and inter-node dependencies into localization and weighting.
• Score: 19.650673179097407
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Conformal prediction (CP) provides a distribution-free approach to uncertainty quantification with finite-sample guarantees. However, applying CP to graph neural networks (GNNs) remains challenging as the combinatorial nature of graphs often leads to insufficiently certain predictions and indiscriminative embeddings. Existing methods primarily rely on embedding-space proximity for localization, which can be unreliable for graphs and yield inefficient prediction sets. We propose GRAPHLCP, a proximity-based localized CP framework that explicitly incorporates graph topology and inter-node dependencies into localization and weighting. Our approach introduces a feature-aware densification step to mitigate locality bias in sparse graphs, followed by a Personalized PageRank-based kernel computation to model structural proximity. This enables topology-dependent anchor sampling and calibration weighting that captures both local and long-range dependencies. Extensive experiments on several regression and classification datasets demonstrate that GRAPHLCP guarantees marginal coverage with finite samples while efficiently attaining favorable test conditional coverage across various conditioning scenarios.

Related papers

• CuBAS: Information Geometric Curvature-Based Adaptive Sampling for Supervised Classification [52.452902154360565]
  CuBAS is an information-geometric framework for adaptive data selection in supervised classification.<n>A labeled dataset can be viewed as a statistical manifold, on which local curvature, estimated via the ratio of second to first-order observed Fisher information, faithfully encodes the geometric complexity of the data distribution.
  arXiv  Detail & Related papers  (2026-07-03T09:36:02Z)
• FedCIGAR: A Personalized Reconstruction Approach for Federated Graph-level Anomaly Detection [51.473064583839296]
  We propose a novel Federated graph-level anomaly detection approach with Cluster-adaptIve GAted Reconstruction (FedCIGAR)<n>Specifically, we design a reconstruction-based paradigm trained on normal graphs to avoid synthetic data. Furthermore, we introduce a client-side node contribution gating mechanism and a server-side sliding window-based clustering strategy to tackle data heterogeneity.
  arXiv  Detail & Related papers  (2026-05-10T09:03:54Z)
• Conformal Graph Prediction with Z-Gromov Wasserstein Distances [6.575089845815419]
  Supervised graph prediction addresses regression problems where the outputs are structured graphs.<n>We propose a conformal prediction framework for graph-valued outputs, providing distribution-free coverage guarantees in structured output spaces.
  arXiv  Detail & Related papers  (2026-03-02T23:02:43Z)
• Conformal Inference for Time Series over Graphs [29.748266176856973]
  We develop a sequential prediction framework tailored for graph time series.<n>A key technical innovation is to leverage the graph structure and thus capture pairwise dependencies across nodes.<n>Our scheme yields an exponential shrinkage in the volume of the ellipsoidal prediction set relative to its graph-agnostic counterpart.
  arXiv  Detail & Related papers  (2025-10-13T06:32:09Z)
• Conformalized Gaussian processes for online uncertainty quantification over graphs [27.90282886573793]
  Uncertainty quantification (UQ) over graphs arises in a number of safety-critical applications in network science.<n>We devise a novel graph-aware parametric GP model by leveraging the random feature (RF)-based kernel approximation.<n>To ensure valid coverage with robustness to model mis-specification, we we wed the GP-based set predictors with the online conformal prediction framework.
  arXiv  Detail & Related papers  (2025-10-07T17:44:13Z)
• ReDiSC: A Reparameterized Masked Diffusion Model for Scalable Node Classification with Structured Predictions [64.17845687013434]
  We propose ReDiSC, a structured diffusion model for structured node classification.<n>We show that ReDiSC achieves superior or highly competitive performance compared to state-of-the-art GNN, label propagation, and diffusion-based baselines.<n> Notably, ReDiSC scales effectively to large-scale datasets on which previous structured diffusion methods fail due to computational constraints.
  arXiv  Detail & Related papers  (2025-07-19T04:46:53Z)
• Residual Reweighted Conformal Prediction for Graph Neural Networks [14.329186221388087]
  Graph Neural Networks (GNNs) excel at modeling data but face significant challenges in high-stakes domains due to unquantified uncertainty.<n>We propose Residual Reweighted GNN (RR-GNN), a framework designed to generate minimal prediction sets with provable marginal coverage guarantees.<n>RR-GNN achieves improved efficiency over state-of-the-art methods, with no loss of coverage.
  arXiv  Detail & Related papers  (2025-06-09T15:19:17Z)
• Conformalized Link Prediction on Graph Neural Networks [8.807684750444626]
  Graph Neural Networks (GNNs) excel in diverse tasks, yet their applications in high-stakes domains are often hampered by unreliable predictions. We introduce a distribution-free and model-agnostic uncertainty quantification approach to construct a predictive interval with a statistical guarantee for GNN-based link prediction.
  arXiv  Detail & Related papers  (2024-06-26T21:17:37Z)
• Uncertainty Quantification over Graph with Conformalized Graph Neural Networks [52.20904874696597]
  Graph Neural Networks (GNNs) are powerful machine learning prediction models on graph-structured data. GNNs lack rigorous uncertainty estimates, limiting their reliable deployment in settings where the cost of errors is significant. We propose conformalized GNN (CF-GNN), extending conformal prediction (CP) to graph-based models for guaranteed uncertainty estimates.
  arXiv  Detail & Related papers  (2023-05-23T21:38:23Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  We propose a bi-level optimization approach for learning the optimal graph structure. We also explore a low-rank approximation model for further reducing the time complexity.
  arXiv  Detail & Related papers  (2022-05-06T03:37:00Z)
• Evaluating probabilistic classifiers: Reliability diagrams and score decompositions revisited [68.8204255655161]
  We introduce the CORP approach, which generates provably statistically Consistent, Optimally binned, and Reproducible reliability diagrams in an automated way. Corpor is based on non-parametric isotonic regression and implemented via the Pool-adjacent-violators (PAV) algorithm.
  arXiv  Detail & Related papers  (2020-08-07T08:22:26Z)
• Log-Likelihood Ratio Minimizing Flows: Towards Robust and Quantifiable Neural Distribution Alignment [52.02794488304448]
  We propose a new distribution alignment method based on a log-likelihood ratio statistic and normalizing flows. We experimentally verify that minimizing the resulting objective results in domain alignment that preserves the local structure of input domains.
  arXiv  Detail & Related papers  (2020-03-26T22:10:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.