Conformal Graph Prediction with Z-Gromov Wasserstein Distances

• URL: http://arxiv.org/abs/2603.02460v3
• Date: Thu, 05 Mar 2026 07:56:44 GMT
• Title: Conformal Graph Prediction with Z-Gromov Wasserstein Distances
• Abstract summary: 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.
• Score: 6.575089845815419
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Supervised graph prediction addresses regression problems where the outputs are structured graphs. Although several approaches exist for graph-valued prediction, principled uncertainty quantification remains limited. We propose a conformal prediction framework for graph-valued outputs, providing distribution-free coverage guarantees in structured output spaces. Our method defines nonconformity via the Z-Gromov-Wasserstein distance, instantiated in practice through Fused Gromov-Wasserstein (FGW), enabling permutation invariant comparison between predicted and candidate graphs. To obtain adaptive prediction sets, we introduce Score Conformalized Quantile Regression (SCQR), an extension of Conformalized Quantile Regression (CQR) to handle complex output spaces such as graph-valued outputs. We evaluate the proposed approach on a synthetic task and a real problem of molecule identification.

Related papers

• Graph Matching Relaxations and Amortization for Supervised Graph Prediction [11.692215143424976]
  End-to-end Supervised Graph Prediction (SGP) requires a permutation-invariant loss to compare predicted and target graphs with arbitrary node orderings.<n>We first study three Optimal Transport relaxations of this problem and show, theoretically and empirically, that the Gromov-Wasserstein (GW) objective is the most suitable for SGP.<n>To avoid solving the resulting inner optimization for every training example, we propose to amortize the graph matching (node alignment) problem.
  arXiv  Detail & Related papers  (2026-09-14T12:00:52Z)
• Generative Diffusion Models of Stochastic Graph Signals [74.4097723209053]
  This paper tackles problems of conditional graph signal generative modeling and tackles them with a single denoising diffusion framework.<n>We learn a reverse diffusion process, parametrized by graph neural networks (GNNs), that draws graph signals conditioned directly on the graph topology and on node-feature side information.<n>We demonstrate our method on two generative tasks: stock price forecasting and optimal wireless resource allocation, with extensive numerical results in both domains.
  arXiv  Detail & Related papers  (2026-07-07T22:02:13Z)
• Directed Graph Topology Inference via Graph Filter Identification [54.541275287889164]
  We address the problem of inferring a directed network from nodal measurements generated by a graph convolutional filter.<n>A joint graph filter and topology identification algorithm is also proposed, which alternates between the aforementioned steps to offer improved sample complexity.
  arXiv  Detail & Related papers  (2026-06-25T18:25:57Z)
• When Do Graph Foundation Models Transfer? A Data-Centric Theory [68.54337055801571]
  Graph foundation models (GFMs) aim to reuse a single backbone across diverse graph domains, yet their transfer is often uneven and can exhibit negative transfer.<n>We show that for both set-based and message-passing tokenizations, any Lipschitz backbone admits an explicit decomposition of cross-domain output shift.<n>A key ingredient is positional-encoding (PE) stability: we establish stability guarantees for spectral PEs and highlight contrasting behaviors of eigenvector- versus subspace-based PEs.
  arXiv  Detail & Related papers  (2026-05-28T12:07:27Z)
• GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs [19.650673179097407]
  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.
  arXiv  Detail & Related papers  (2026-05-08T17:56:09Z)
• GCCM: Enhancing Generative Graph Prediction via Contrastive Consistency Model [10.481950161450948]
  Conditional generative models have been applied to graph prediction by modeling the target as a conditional distribution given the input graph.<n>We propose GCCM, a graph contrastive consistency model that goes beyond isolated pairwise matching between the same target at different noise levels.<n>We show that GCCM mitigates the shortcut solution and yields consistent performance improvements in graph prediction compared to deterministic predictors.
  arXiv  Detail & Related papers  (2026-05-07T05:29:57Z)
• 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)
• Uncertainty Estimation on Graphs with Structure Informed Stochastic Partial Differential Equations [1.2584276673531931]
  Graph Neural Networks have achieved impressive results across diverse network modeling tasks, but accurately estimating uncertainty on graphs remains difficult.<n>We present a principled way to design a novel message passing scheme that incorporates spatial-temporal noises motivated by the Gaussian Process approach to SPDE.<n>Our method simultaneously captures uncertainty across space and time and allows explicit control over the covariance kernel smoothness, thereby enhancing uncertainty estimates on graphs with both low and high label informativeness.
  arXiv  Detail & Related papers  (2025-06-07T19:58:38Z)
• Graph Counterfactual Explainable AI via Latent Space Traversal [4.337339380445765]
  Counterfactual explanations aim to explain predictions by finding the ''nearest'' in-distribution alternative input.<n>We propose a method to generate counterfactual explanations for any differentiable black-box graph classifier.<n>We empirically validate the approach on three graph datasets, showing that our model is consistently high-performing and more robust than the baselines.
  arXiv  Detail & Related papers  (2025-01-15T15:04:10Z)
• Semiparametric conformal prediction [79.6147286161434]
  We construct a conformal prediction set accounting for the joint correlation structure of the vector-valued non-conformity scores.<n>We flexibly estimate the joint cumulative distribution function (CDF) of the scores.<n>Our method yields desired coverage and competitive efficiency on a range of real-world regression problems.
  arXiv  Detail & Related papers  (2024-11-04T14:29:02Z)
• Fine-grained Graph Rationalization [51.293401030058085]
  We propose fine-grained graph rationalization (FIG) for graph machine learning.<n>Our idea is driven by the self-attention mechanism, which provides rich interactions between input nodes.<n>Our experiments involve 7 real-world datasets, and the proposed FIG shows significant performance advantages compared to 13 baseline methods.
  arXiv  Detail & Related papers  (2023-12-13T02:56:26Z)
• Discrete Graph Auto-Encoder [52.50288418639075]
  We introduce a new framework named Discrete Graph Auto-Encoder (DGAE) We first use a permutation-equivariant auto-encoder to convert graphs into sets of discrete latent node representations. In the second step, we sort the sets of discrete latent representations and learn their distribution with a specifically designed auto-regressive model.
  arXiv  Detail & Related papers  (2023-06-13T12:40:39Z)
• 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)
• Graph Signal Sampling for Inductive One-Bit Matrix Completion: a Closed-form Solution [112.3443939502313]
  We propose a unified graph signal sampling framework which enjoys the benefits of graph signal analysis and processing. The key idea is to transform each user's ratings on the items to a function (signal) on the vertices of an item-item graph. For the online setting, we develop a Bayesian extension, i.e., BGS-IMC which considers continuous random Gaussian noise in the graph Fourier domain.
  arXiv  Detail & Related papers  (2023-02-08T08:17:43Z)
• GraphGDP: Generative Diffusion Processes for Permutation Invariant Graph Generation [43.196067037856515]
  Graph generative models have broad applications in biology, chemistry and social science. Current leading autoregressive models fail to capture the permutation invariance nature of graphs. We propose a continuous-time generative diffusion process for permutation invariant graph generation.
  arXiv  Detail & Related papers  (2022-12-04T15:12:44Z)
• FORESEE: Prediction with Expansion-Compression Unscented Transform for Online Policy Optimization [8.97438370260135]
  We introduce a method for state prediction, called the Expansion-Compression Unscented Transform, to solve a class of online policy optimization problems. Our proposed algorithm propagates a finite number of sigma points through a state-dependent distribution, which dictates an increase in the number of sigma points at each time step. Its performance is empirically shown to be comparable to Monte Carlo but at a much lower computational cost.
  arXiv  Detail & Related papers  (2022-09-26T12:47:08Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Neuro-Symbolic Entropy Regularization [78.16196949641079]
  In structured prediction, the goal is to jointly predict many output variables that together encode a structured object. One approach -- entropy regularization -- posits that decision boundaries should lie in low-probability regions. We propose a loss, neuro-symbolic entropy regularization, that encourages the model to confidently predict a valid object.
  arXiv  Detail & Related papers  (2022-01-25T06:23:10Z)

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.