Conformal Graph Prediction with Z-Gromov-Wasserstein Distances

Gabriel Melo; Thibaut de Saivre; Anna Calissano; Florence d'Alché-Buc

stat.MLMar 2, 2026

Conformal Graph Prediction with Z-Gromov-Wasserstein Distances

Authors: Gabriel Melo, Thibaut de Saivre, Anna Calissano, Florence d'Alché-Buc

Organizations: LTCI, Télécom Paris, Intistut Polytechnique de Paris, Palaiseau, France · Department of Statistical Science, University College London, London, UK

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.

Figures & tables

Figure 1: Conformal metabolite prediction set at $90\%$ marginal coverage for molecule identification. The green check-mark denotes the ground-truth.

Figure 2: Z-GW distance

Figure 3: Example of the retrieval on the Coloring dataset. The green check-mark denotes the ground-truth.

				Conformal Set Size $\downarrow$		Candidate Set Size		Reduction % $\uparrow$
Dataset	Model $f_{\theta}$	Method	Emp. Cov. (%)	Mean	Median	Mean	Median	Mean	Median	Empty rate (%) $\downarrow$
Coverage $1-\alpha=90\%$
Colors	Any2Graph Acc: 82%	CP	$90.2$	$4$	$1$	$205$	$223$	$95.8\%$	$98.9\%$	$8.9\%$
Colors	Any2Graph Acc: 82%	SCQR $\|\mathcal{L}(x)\|$	$90.3$	$4$	$1$	$201$	$223$	$95.6\%$	$98.9\%$	$8.8\%$
		SCQR $\operatorname{ResNet}(x)$	$93.0$	$4$	$1$	$205$	$218$	$96.2\%$	$98.9\%$	$5.7\%$
Spectraverse Adduct: $[\text{M+CH}_{3}\text{COOH-H}]^{-}$	MSAlign Acc: 71.8%	CP	$90.0$	$59$	$56$	$152$	$159$	$60.4\%$	$61.0\%$	$0.0\%$

Table 1: Comparison of conformal prediction (CP) and score conformalized quantile regression (SCQR) on graph-valued outputs with finite candidate sets. Acc denotes the base predictor retrieval accuracy. We report the metrics on non-empty predicted conformal sets, hence the changes in candidate set sizes.

Method	Marginal Coverage	Worst-Slab Coverage
CP	$90.2\%$	$64.7\%$
SCQR $\|\mathcal{L}(x)\|$	$90.3\%$	$67.6\%$
SCQR $\operatorname{ResNet}(x)$	$90.2\%$	$73.5\%$

Table 2: Marginal and worst-slab coverage for different SCQR conditioning attributes on the Coloring dataset. Slabs group inputs by number of candidates.

Figure 4: Empirical coverage as a function of the probability of ground-truth absence from the candidate library

\mathbb{P}(Y_{n+1}\notin\mathcal{L}(X_{n+1}))

, evaluated on the Coloring dataset.

Panel of Figure 5 — Figure 5: Empirical coverage versus candidate set size, for CP (left) and SCQR (right). For SCQR, the attribute function $\omega(x)$ is task-dependent: $\omega(x)=|\mathcal{L}(x)|$ (candidate set size) for Coloring, and $\omega(x)=\textsc{DreaMS}(x)$ (mass-spectrum embedding) for Molecule Retrieval.

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 6: Coloring dataset examples using Any2Graph as graph predictor.

Parameter	Value
Optimizer	Adam
Learning rate	0.001
Batch size	32
Early stopping patience	3
Early stopping minimum loss improvement	0.0001

Appendix

Table 3: embedding-based SCQR neural network training parameters

Figure 7: Time taken to compute a FGW distance between a pair of Coloring dataset graphs with various amounts of nodes. Notice how the performance of uniform initialization is offset from the others, given that it is the default initialization of the FGW algorithm, not requiring prior computations. The adjacency cost matrix scales very badly with the amount of nodes. At 10 nodes per graph, it is already 20 times slower than the other options.

Figure 8: Computation time of the FGW distance between a pair of coloring dataset graphs with the FD prior. Although the adjacency cost matrix yields good conformal performance, it is not recommended when working with large graphs.

				Conformal Set Size $\downarrow$		Candidate Set Size		Reduction % $\uparrow$
Dataset	Model $f_{\theta}$	Method	Emp. Cov. (%)	Mean	Median	Mean	Median	Mean	Median	Empty rate (%) $\downarrow$
Coverage $1-\alpha=90\%$
Colors	Any2Graph Acc: 82%	CP	$90.2$	$4$	$1$	$205$	$223$	$95.8\%$	$98.9\%$	$8.9\%$
Colors	Any2Graph Acc: 82%	SCQR $\|\mathcal{L}(x)\|$	$90.3$	$4$	$1$	$201$	$223$	$95.6\%$	$98.9\%$	$8.8\%$
		SCQR $\operatorname{ResNet}(x)$	$93.0$	$4$	$1$	$205$	$218$	$96.2\%$	$98.9\%$	$5.7\%$
Spectraverse Adduct: $[\text{M+CH}_{3}\text{COOH-H}]^{-}$	MSAlign Acc: 71.8%	CP	$90.0$	$59$	$56$	$152$	$159$	$60.4\%$	$61.0\%$	$0.0\%$

Appendix

Table 4: Comparison of conformal prediction (CP) and score conformalized quantile regression (SCQR) on graph-valued outputs with finite candidate sets. Acc denotes the base predictor retrieval accuracy.

Category	Acronym	Description
Cost Matrix $C$	$A$	Adjacency
	$L$	Laplacian
	$L^{sym}$	Laplacian (symmetrically normalized)
	$SP$	Shortest Paths
Initial Transport Plan $G_{0}$	FD	Feature Diffusion: Solution to the Earth Mover’s Distance problem for given nodes of feature augmented vector $(F,AF)$
	LFD	Laplacian Feature Diffusion: Same as Feature Diffusion but with features $(F,LF)$

Appendix

Table 5: Summary of acronyms used in the experiments.

Task	Cost Matrix	Empirical Coverage	Mean set size $\downarrow$	Median set size $\downarrow$	Mean reduction (%) $\uparrow$	Median reduction (%) $\uparrow$	Empty rate (%) $\downarrow$
Colors	$A$	$90.2\%$	$4$	$1$	$95.8\%$	$98.9\%$	$9.0\%$
	$L^{sym}$	$90.4\%$	$4$	$1$	$95.8\%$	$98.9\%$	$8.5\%$
	$L$	$90.8\%$	$4$	$1$	$95.5\%$	$98.7\%$	$8.3\%$
	$SP$	$90.1\%$	$205$	$223$	$2.2\%$	$0.0\%$	$2.6\%$

Appendix

Table 6: Cost matrix impact on different tasks. The colors task uses the feature diffusion

G_{0}

prior.

Task	$G_{0}$	Empirical Coverage	Mean set size $\downarrow$	Median set size $\downarrow$	Mean reduction (%) $\uparrow$	Median reduction (%) $\uparrow$	Empty rate (%) $\downarrow$
Colors	LFD	$90.4\%$	$4$	$1$	$95.8\%$	$98.9\%$	$8.7\%$
	FD	$90.2\%$	$4$	$1$	$95.8\%$	$98.9\%$	$9.0\%$
	Uniform	$90.1\%$	$4$	$1$	$95.8\%$	$98.9\%$	$8.7\%$
	LFD-sym	$90.0\%$	$4$	$1$	$95.8\%$	$98.9\%$	$8.8\%$
	Id	$90.4\%$	$6$	$2$	$94.4\%$	$97.9\%$	$5.1\%$

Appendix

Table 7:

G_{0}

prior impact on different tasks. The colors task uses the adjacency cost matrix. Note that uniform

G_{0}

prior often converges very slowly.

Explore similar work

GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs
May 8, 2026Peyman Baghershahi, Fangxin Wang, Debmalya Mandal +1Graph Neural Networks Conformal Prediction
Department of Computer Science, University of Illinois Chicago · Department of Computer Science, University of Warwick
Graph Matching Relaxations and Amortization for Supervised Graph Prediction
Sep 14, 2026Federico Méndez, Paul Krzakala, Gabriel Melo +3Learning to Optimize Graph Matching
LTCI, Télécom Paris · Institut Polytechnique de Paris · CMAP, École Polytechnique
Delving into Non-Exchangeability for Conformal Prediction in Graph-Structured Multivariate Time Series
May 6, 2026Ruichao Guo, Xingyao Han, Luo Wenshui +3Multivariate Time Series Forecasting Conformal Prediction
School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai, China

May 8, 2026J/K move · Enter open · S save

GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

Peyman Baghershahi, Fangxin Wang, Debmalya Mandal, Sourav Medya

Department of Computer Science, University of Illinois Chicago · Department of Computer Science, University of Warwick

Graph Neural Networks Conformal Prediction

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

GRAPHLCP: Structure-Aware Localized Conformal Prediction on Graphs

Graph Matching Relaxations and Amortization for Supervised Graph Prediction

Delving into Non-Exchangeability for Conformal Prediction in Graph-Structured Multivariate Time Series