Conformal Graph Prediction with Z-Gromov Wasserstein Distances

Gabriel Melo, Thibaut de Saivre, Anna Calissano, Florence d’Alché-Buc
Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, PMLR 337:4479-4496, 2026.

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v337-melo26a, title = {Conformal Graph Prediction with {Z-Gromov} {Wasserstein} Distances}, author = {Melo, Gabriel and de Saivre, Thibaut and Calissano, Anna and {d'Alch\'{e}-Buc}, Florence}, booktitle = {Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence}, pages = {4479--4496}, year = {2026}, editor = {Perković, Emilija and Malinsky, Daniel}, volume = {337}, series = {Proceedings of Machine Learning Research}, month = {17--21 Aug}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v337/main/assets/melo26a/melo26a.pdf}, url = {https://proceedings.mlr.press/v337/melo26a.html}, 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.} }
Endnote
%0 Conference Paper %T Conformal Graph Prediction with Z-Gromov Wasserstein Distances %A Gabriel Melo %A Thibaut de Saivre %A Anna Calissano %A Florence d’Alché-Buc %B Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2026 %E Emilija Perković %E Daniel Malinsky %F pmlr-v337-melo26a %I PMLR %P 4479--4496 %U https://proceedings.mlr.press/v337/melo26a.html %V 337 %X 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.
APA
Melo, G., de Saivre, T., Calissano, A. & d’Alché-Buc, F.. (2026). Conformal Graph Prediction with Z-Gromov Wasserstein Distances. Proceedings of the 42nd Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research 337:4479-4496 Available from https://proceedings.mlr.press/v337/melo26a.html.

Related Material