Conformal Graph Prediction with Z-Gromov Wasserstein Distances
This work addresses uncertainty quantification for researchers and practitioners in fields like chemistry or bioinformatics where predicting structured graphs (e.g., molecules) is critical, though it is incremental as it extends existing conformal methods to graph outputs.
The paper tackles the problem of uncertainty quantification in supervised graph prediction by proposing a conformal prediction framework that provides distribution-free coverage guarantees for graph-valued outputs, achieving coverage rates close to the target (e.g., 90% coverage) in experiments on synthetic and molecule identification tasks.
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.