Conformal Graph Prediction with Z-Gromov Wasserstein Distances Gabriel Melo, Thibaut de Saivre, Anna Calissano, Florence d’Alché-Buc 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. 1 Introduction Figure 1 : Conformal metabolite prediction set at 90\% marginal coverage for molecule identification on MassSpecGym [ 5 ] . The green check-mark denotes the ground-truth. Motivated by various applications such as molecular identification [ 18 ] in chemistry or scene understanding in computer vision [ 21 ] , Supervised Graph Prediction (SGP) has recently attracted a growing interest in Machine Learning. This task consists in learning a predictive model that maps an input variable of any modality (text, image, tabular or distributional) to a target graph of arbitrary size. Approaches proposed in the literature leverage surrogate regression in graph representation spaces [ 4 ] or end-to-end learning [ 21 , 26 , 15 ] that boils down to graph-valued regression [ 6 ] . However, none of these approaches provides the user with confidence sets which raises a significant risk for discovery or identification, especially when experimental validation of the results is costly. Uncertainty quantification for graph-valued data aims to produce a set of plausible graphs rather than a single prediction. Although random graph models are well studied [ 10 ] , parametric approaches are often unrealistic in practice, especially for attributed graphs. Non-parametric methods therefore provide a more flexible alternative. In this paper, we choose the agnostic, distribution free, and post-training framework of Conformal Prediction (CP). Conformal Prediction [ 20 , 9 ] provides finite-sample coverage guarantees under minimal assumptions, requiring only exchangeability of the data, and can be applied on top of any pre-trained predictor without modifying the training procedure. Extending CP to graph-valued outputs raises several fundamental challenges. Even in the multivariate Euclidean setting, constructing informative conformal sets is known to be difficult due to the curse of dimensionality and the lack of natural orderings [ 8 , 13 , 22 ] . These challenges are amplified in the graph setting, where outputs live in a highly structured, non-Euclidean, and combinatorial space. For a graph with attributes on nodes and edges, uncertainty can revolve around the uncertainty at the global level, providing a conformal set made of a set of graphs with more or less different structure, or at a local level, measuring uncertainty at the level of the nodes and edges attribute. In this paper, we opt for a global framework. This choice is also supported by a specific focus on molecular identification tasks, where only a specific amount of configurations are possible. A central challenge is therefore the choice of a suitable non-conformity score, which determines the structure and informativeness of the resulting conformal sets. Since graphs are defined up to node permutation, one must either work in the quotient space or use a permutation-invariant discrepancy. We adopt Optimal Transport distances, namely Gromov–Wasserstein and its variants, to define permutation-invariant scores and extend Conformal Prediction to graph-valued outputs with validity in the quotiented graph space. We focus on Supervised Graph Prediction settings where each input is associated with a finite, input-dependent candidate set of graphs, as commonly assumed in structured output prediction and molecular identification. Standard conformal prediction relies on a single global threshold, implicitly assuming homogeneous uncertainty across inputs. To account for input-dependent variability, we introduce Score Conformalized Quantile Regression (SCQR), which calibrates conditional quantiles of the non-conformity score instead of a global cutoff. SCQR yields locally adaptive conformal sets while preserving marginal coverage guarantees. In short, our contributions include: • a framework for Conformal Graph Prediction based on Z-Gromov-Wasserstein non-conformity scores and the proof of its validity in quotiented graph spaces. • a locally adaptive variant, Score Conformalized Quantile Regression (SCQR), with proven marginal coverage. • a set of numerical experiments showing the effectiveness and the versatility of the framework on a synthetic image-to-graph task. 2 Related Work Prediction Models for Graphs. We consider supervised models whose outputs are graphs, including barycenter-based methods [ 3 , 26 ] , graph regression [ 6 ] , deep end-to-end predictors [ 15 , 21 ] , and graph-level autoencoders [ 14 ] . In molecular applications, graphs may also be predicted indirectly via SMILES representations [ 28 ] . Our framework is model-agnostic and applies to both direct graph predictors and SMILES-based pipelines. Conformal Prediction for Graphs. Recent efforts have extended CP to non-Euclidean domains. For node-level tasks, 11 introduced conformalized GNNs, establishing the importance of permutation invariance in base predictors, while [ 16 ] defined a node based CP sets. 27 proposed a general framework for conformal structured prediction, constructing structured prediction sets via implicit representations, e.g., directed acyclic graphs for hierarchical labels. Closer to our setting, 7 developed CP sets for populations of unlabeled graphs, utilizing quotient spaces to handle the lack of node correspondence. Our work extends these concepts to graphs with categorical attributes on nodes. In addition, by adopting the Z-Gromov-Wassertein distance, we work in a permutation invariant setting. 3 Background We begin by reviewing the two central components of our framework: conformal prediction and the Z -Gromov–Wasserstein ( Z -GW) distance, a metric on metric measure spaces, under which graphs naturally appear as an example of discrete metric measure spaces. Notation Let \Sigma_{n}:=\{a\in\mathbb{R}^{n}_{+}:\sum_{i=1}^{n}a_{i}=1\} denote the probability simplex, and let \sigma_{n}:=\{P\in\{0,1\}^{n\times n}:P\mathbf{1}_{n}=\mathbf{1}_{n},\;P^{\top}\mathbf{1}_{n}=\mathbf{1}_{n}\} be the set of permutation matrices, where \mathbf{1}_{n}\in\mathbb{R}^{n} denotes the all-ones vector. For finite sets \mathcal{X}=\{x_{1},\dots,x_{n}\} and \mathcal{Y}=\{y_{1},\dots,y_{m}\} , any discrete probability measures \mu\in\mathcal{P}(\mathcal{X}) and \nu\in\mathcal{P}(\mathcal{Y}) can be written as \mu=\sum_{i=1}^{n}a_{i}\delta_{x_{i}} and \nu=\sum_{j=1}^{m}b_{j}\delta_{y_{j}} with a\in\Sigma_{n} and b\in\Sigma_{m} . We identify admissible couplings \pi\in\Pi(\mu,\nu) with nonnegative matrices \pi\in\mathbb{R}_{+}^{n\times m} satisfying \pi\mathbf{1}_{m}=a , \pi^{\top}\mathbf{1}_{n}=b . When both measures are uniform, i.e. \mu(\{x_{i}\})=\nu(\{y_{j}\})=\tfrac{1}{n} for all i,j and n=m , the set \Pi(\mu,\mu) coincides with the Birkhoff polytope. 3.1 Conformal Prediction Definition 3.1 (Exchangeability) . A sequence of random variables (Z_{1},\dots,Z_{n+1}) taking values in a measurable space \mathcal{Z} is said to be exchangeable if, for any permutation \sigma of \{1,\dots,n+1\} and for any (z_{1},\dots,z_{n+1})\in\mathcal{Z}^{n+1} , \mathbb{P}(Z_{1}=z_{1},\dots,Z_{n+1}=z_{n+1})=\mathbb{P}(Z_{\sigma(1)}=z_{1},\dots,Z_{\sigma(n+1)}=z_{n+1}). Conformal Prediction (CP) provides finite-sample, distribution-free guarantees on the coverage of prediction sets. In the regression setting, we observe exchangeable pairs (X_{i},Y_{i}) and have a pre-trained base predictor f_{\theta}:\mathcal{X}\to\mathcal{Y} . The framework relies on a nonconformity score function s:\mathcal{X\times\mathcal{Y}\to\mathbb{R}} that measures the discrepancy between the target y and the prediction f_{\theta}(x) . For standard real-valued regression, a typical choice is the absolute residual: s(x,y)=|y-f_{\theta}(x)|. (1) Given a held-out calibration set \mathcal{D}_{\text{cal}}=\{(X_{i},Y_{i})\}_{i=1}^{n} , we compute the scores R=\{R_{1},\dots,R_{n}\} where R_{i}=s(X_{i},Y_{i}) . We then compute the adjusted empirical quantile: \hat{q}_{1-\alpha}=\text{Quantile}\left(\{R_{i}\}_{i=1}^{n},\frac{\lceil(n+1)(1-\alpha)\rceil}{n}\right). (2) For a new input X_{n+1} , the conformal prediction set is defined as: \mathcal{C}(X_{n+1})=\{y\in\mathcal{Y}:s(X_{n+1},y)\leq\hat{q}_{1-\alpha}\}. (3) By exchangeability of the calibration and test samples, the nonconformity scores \{R_{i}\}_{i=1}^{n+1} with R_{i}=s(X_{i},Y_{i}) form an exchangeable sequence. Consequently, the rank of R_{n+1} among \{R_{i}\}_{i=1}^{n+1} is uniformly distributed, which implies the marginal coverage guarantee [ 25 ] \mathbb{P}\big(Y_{n+1}\in\mathcal{C}(X_{n+1})\big)\geq 1-\alpha, without any assumptions on the data distribution or the accuracy of the predictor. We refer to 1 , 20 for more details on conformal prediction. Conformalized Quantile Regression To extend standard conformal prediction to better handle heteroscedasticity, Conformalized Quantile Regression (CQR) [ 19 ] improves the conformal framework by leveraging quantile regression [ 12 ] to construct input-adaptive prediction intervals. Instead of relying on a fixed, globally calibrated residual, CQR employs two base models, \hat{\psi}_{\alpha/2}(x) and \hat{\psi}_{1-\alpha/2}(x) , trained to estimate the lower and upper (\alpha/2,1-\alpha/2) quantiles of the conditional distribution Y|X=x . The nonconformity score is then defined as s(x,y)=\max\{\hat{\psi}_{\alpha/2}(x)-y,y-\hat{\psi}_{1-\alpha/2}(x)\} , which measures the signed distance of the target to the boundaries of the predicted interval. By computing the (1-\alpha) -th quantile of these scores, \hat{q}_{1-\alpha} , on a calibration set, the resulting prediction intervals \mathcal{C}(x)=[\hat{\psi}_{\alpha/2}(x)-\hat{q}_{1-\alpha},\hat{\psi}_{1-\alpha/2}(x)+\hat{q}_{1-\alpha}] achieve valid marginal coverage while dynamically adjusting their width to account for local uncertainty in the data. 3.2 Z-Gromov Wasserstein Distance To measure discrepancies between structured outputs such as graphs, which will later serve as the basis for conformal scoring, we work in the space of Z -networks equipped with the Z -Gromov–Wasserstein distance. Definition 3.2 (Metric Measure Spaces) . A metric measure space (mm-space) is defined as triple (\mathcal{X},d_{\mathcal{X}},\mu_{\mathcal{X}}) , where (\mathcal{X},d_{\mathcal{X}}) is a compact metric space and \mu_{\mathcal{X}} is a Borel probability measure on \mathcal{X} with \mu_{\mathcal{X}}(\mathcal{X})=1 and full support, \mathrm{supp}(\mu_{\mathcal{X}})=\mathcal{X} . Gromov–Wasserstein (GW) distances were introduced to compare mm-spaces via optimal transport [ 17 ] . Subsequent work in the machine learning literature proposed several variants to handle structured and attributed data, most notably Fused GW (FGW) [ 23 ] . The Z -Gromov–Wasserstein (Z-GW) distance [ 2 ] unifies these approaches by replacing the metric-valued distance function in classical GW with a general measurable pairwise relation taking values in a metric space (\mathcal{Z},d_{\mathcal{Z}}) , so that classical GW, FGW and other formulations arise as particular instances of this construction. Definition 3.3 ( Z -networks) . Let (\mathcal{Z},d_{\mathcal{Z}}) be a metric space. A Z -network is a triple (\mathcal{X},\omega_{\mathcal{X}},\mu_{\mathcal{X}}) , where \mathcal{X} is a measurable space, \mu_{\mathcal{X}} is a probability measure on \mathcal{X} , and \omega_{\mathcal{X}}:\mathcal{X}\times\mathcal{X}\to\mathcal{Z} is a measurable function encoding pairwise relational information. Unlike mm-spaces, \omega_{\mathcal{X}} is not required to be a metric. Z-Gromov–Wasserstein distance. Given two Z -networks (\mathcal{X},\omega_{\mathcal{X}},\mu_{\mathcal{X}}) and (\mathcal{Y},\omega_{\mathcal{Y}},\mu_{\mathcal{Y}}) , the Z -Gromov–Wasserstein p -distance ( p\geq 1 ) is defined as \displaystyle\mathrm{GW}^{Z}_{p}( \displaystyle\mathcal{X},\mathcal{Y})=\frac{1}{2}\inf_{\pi\in\Pi(\mu_{\mathcal{X}},\mu_{\mathcal{Y}})}\Bigg(\iint_{(\mathcal{X}\times\mathcal{Y})^{2}} (4) \displaystyle d_{\mathcal{Z}}\!\Big(\omega_{\mathcal{X}}(x,x^{\prime}),\omega_{\mathcal{Y}}(y,y^{\prime})\Big)^{p}\,\mathrm{d}\pi(x,y)\,\mathrm{d}\pi(x^{\prime},y^{\prime})\Bigg)^{1/p}. When \mathcal{Z}=\mathbb{R} and \omega_{\mathcal{X}} is the usual metric distance ( \omega_{\mathcal{X}}=d_{\mathcal{X}} ), \mathrm{GW}^{Z}_{p} reduces to the classical GW distance. Definition 3.4 (Weak isomorphism [ 2 ] ) . Two Z -networks (\mathcal{X},\omega_{\mathcal{X}},\mu_{\mathcal{X}}) and (\mathcal{Y},\omega_{\mathcal{Y}},\mu_{\mathcal{Y}}) are said to be weakly isomorphic , written \mathcal{X}\sim\mathcal{Y} , if there exists a Z -network (\mathcal{W},\omega_{\mathcal{W}},\mu_{\mathcal{W}}) and measure-preserving maps \phi_{\mathcal{X}}:\mathcal{W}\to\mathcal{X} and \phi_{\mathcal{Y}}:\mathcal{W}\to\mathcal{Y} such that \omega_{\mathcal{W}}(w,w^{\prime})=\omega_{\mathcal{X}}(\phi_{\mathcal{X}}(w),\phi_{\mathcal{X}}(w^{\prime}))=\omega_{\mathcal{Y}}(\phi_{\mathcal{Y}}(w),\phi_{\mathcal{Y}}(w^{\prime})) for \mu_{\mathcal{W}}\otimes\mu_{\mathcal{W}}\penalty\ \text{for almost every pair}\penalty\ (w,w^{\prime}). Weak isomorphism and metricity. The distance \mathrm{GW}^{Z}_{p} defines a pseudometric on the space of Z -networks. To obtain a genuine metric, one considers equivalence classes under weak isomorphism . We denote by \mathfrak{M} the collection of all Z -networks (\mathcal{X},\omega_{\mathcal{X}},\mu_{\mathcal{X}}) , and by \mathcal{M}:=\mathfrak{M}/\!\sim the corresponding quotient space under weak isomorphism. Theorem 3.5 ( [ 2 , Thm. 29] ) . For any separable metric space (\mathcal{Z},d_{\mathcal{Z}}) and p\geq 1 , the distance \mathrm{GW}^{Z}_{p} induces a genuine metric on \mathcal{M} . Remark 3.6 (Working with representatives in practice) . Although the quotient space \mathcal{M}:=\mathfrak{M}/\sim is the natural mathematical domain on which \mathrm{GW}^{Z}_{p} is well defined, it is not directly accessible in practice. Each element of \mathcal{M} corresponds to an equivalence class of isomorphic realizations, and any concrete representative in \mathfrak{M} is inherently arbitrary. In practical settings, observed data are therefore provided as explicit Z -networks in \mathfrak{M} (e.g., graphs, attributed graphs, or meshes), and learning algorithms operate on these representations. Consequently, both empirical datasets and prediction tasks are formulated at the level of \mathfrak{M} , while permutation-invariant losses such as \mathrm{GW}^{Z}_{p} ensure consistency with the underlying quotient structure. 4 Conformal Graph Prediction 4.1 Problem Setup Figure 2 : Z-GW distance Graphs as Z -networks. Graphs can be naturally viewed as finite Z -networks. Let G=(V,E,F) be a graph, where V is the node set with |V|=n\in\mathbb{N}^{*} , E\subseteq V\times V is the edge set, and \Psi:V\to\mathbb{R}^{d} is a node feature map, with \Psi(i) denoting the feature associated to node i\in V . We associate to G a Z -network (V,\omega_{G},\mu_{G}) , where \mu_{G}\in\mathcal{P}(V) is a probability measure on V (assumed uniform in this case), and \omega_{G}:V\times V\to\mathcal{Z} encodes pairwise relational information between nodes. This representation provides a unified way to encode both graph structure and node attributes, enabling the comparison of graphs within the general Z-GW distance. Example 4.1 (Fused Network Gromov-Wasserstein Distance) . Choosing the pairwise structure \omega_{G} such that it combines structural and node-level information allows to retrieve the so-called Fused Network Gromov-Wasserstein Distance introduced by 26 : \omega_{G}(i,k)=\big(\mathbf{A}(i,k),\;\mathbf{X}(i,k),\Psi(i)\big)\in\mathcal{Z}:=\Omega\times\mathbb{R}^{m}\times\mathbb{R}^{d}, where the matrix \mathbf{A}:V\times V\to\Omega defined from the set of edges E encodes graph connectivity (e.g. Adjacency, Shortest Path, Laplacian, etc), \mathbf{X}:V\times V\to\mathbb{R}^{m} represents edge features, and \Psi(i)\in\mathbb{R}^{d} denotes the feature associated to node i . For instance, when \mathbf{A} is the adjacency matrix, \Omega=\{0,1\} . The product space \mathcal{Z} is equipped with a weighted \ell_{q} metric \displaystyle d_{\mathcal{Z}} \displaystyle\big((a,x,\psi),(a^{\prime},x^{\prime},\psi^{\prime})\big)=\Big(\beta d_{\Omega}(a,a^{\prime})^{q} \displaystyle+\gamma d_{\mathbb{R}^{m}}(x,x^{\prime})^{q}+(1-\gamma-\beta)d_{\mathbb{R}^{d}}(\psi,\psi^{\prime})^{q}\Big)^{1/q}, (5) for \gamma,\beta\in[0,1],\;q\geq 1 . Example 4.2 (Fused Gromov-Wassertein Distance [ 24 ] ) . Setting \gamma=0 and \beta\in[0,1] , we recover the Fused Gromov-Wasserstein (no more edge features). Example 4.3 (Gromov-Wasserstein Distance [ 17 ] ) . To retrieve Gromov-Wasserstein distance between unlabeled graphs (no more feature nodes), we set \gamma=0 and \beta=1 . Discrete Z -Gromov–Wasserstein for graphs. Let G_{1}=(V_{1},\omega_{1},\mu_{1}) and G_{2}=(V_{2},\omega_{2},\mu_{2}) be finite graphs with |V_{1}|=n and |V_{2}|=m and uniform measures. The discrete Z -GW distance between G_{1} and G_{2} is defined as \min_{\pi\in\Pi(\mu_{1},\mu_{2})}\left(\sum_{i,k\in V_{1}}\sum_{j,l\in V_{2}}d_{\mathcal{Z}}\!\big(\omega_{1}(i,k),\omega_{2}(j,l)\big)^{p}\,\pi_{ij}\pi_{kl}\right)^{1/p}. (6) In the finite graph setting with uniform measures, weak isomorphism admits a simple characterization (see Proposition 4.4 below). As a consequence, \mathrm{GW}^{Z}_{p} defines a permutation-invariant distance on graphs. Proposition 4.4 (Weak isomorphism and permutation invariance) . Let (V_{1},\omega_{1},\mu_{1}) and (V_{2},\omega_{2},\mu_{2}) be finite Z -networks associated to G_{1} and G_{2} , respectively, with |V_{1}|=|V_{2}|=n and uniform measures \mu_{1}=\mu_{2} . Then G_{1}\sim_{n}G_{2} if and only if there exists a permutation matrix P\in\sigma_{n} such that \omega_{1}=P^{\top}\omega_{2}P . From now on, we specialize the spaces \mathfrak{M} and \mathcal{M} to graphs. We denote by \mathfrak{M} the collection of all graphs with at most N nodes, i.e. \mathfrak{M}=\bigsqcup_{n=1}^{N}\mathcal{G}_{n} , in which \mathcal{G}_{n} are the space of all graphs with n nodes represented in a labeled form, and by \mathcal{M}:=\bigsqcup_{n=1}^{N}(\mathcal{G}_{n}/\!\sim_{n}) , the union of the quotient graph spaces of size n , where graphs are identified up to node permutation. For simplicity, we note \mathcal{M}=\mathfrak{M}/\!\sim . Graph-valued prediction. We consider a graph-valued prediction model f_{\theta}:\mathcal{X}\to\mathfrak{M} that maps inputs x\in\mathcal{X} (e.g., spectra, images, or other descriptors) to graph-valued outputs y\in\mathfrak{M} . In the remainder, we assume that this model has been learned on the training dataset \{(X_{i},Y_{i})\}_{i=1}^{n} by minimizing a loss measuring discrepancy between predicted and ground-truth graphs. Crucially, such losses must be invariant to node relabeling; the \mathrm{GW}^{Z}_{p} distance, for instance, satisfies this requirement by construction. In the experimental part, we consider two off-the-shelves graph prediction models f_{\theta} : Any2Graph [ 15 ] , a general-purpose end-to-end graph predictor restricted to small-size graphs. 4.2 General Framework for Conformal Graph prediction Given the previous set up, for a given input x , we get a concrete graph \hat{y}=f_{\theta}(x)\in\mathfrak{M} . Uncertainty guarantees, however, must be invariant to node relabeling and are therefore stated on the quotient space \mathcal{M} . Assumption 4.5 (Exchangeable data) . The observed data (X_{i},Y_{i})_{i=1}^{n} are exchangeable and take values in \mathcal{X}\times\mathfrak{M} . Definition 4.6 (Canonical projection) . The canonical projection h:\mathfrak{M}\to\mathcal{M}:=\mathfrak{M}/\sim maps a graph y\in\mathfrak{M} to its equivalence class h(y):=[y]=\{y^{\prime}\in\mathfrak{M}\mid y^{\prime}\sim y\}, corresponding to all node relabelings of the same underlying graph. Given a graph predictor f_{\theta} and representative-valued data in \mathfrak{M} , we define the nonconformity score s:\mathcal{X}\times\mathfrak{M}\to\mathbb{R}_{+},\qquad s(x,y):=\mathrm{GW}^{Z}_{p}\!\big(f_{\theta}(x),\,y\big). Since \mathrm{GW}^{Z}_{p} is invariant under node permutation, the score s is invariant under the equivalence relation \sim . As a consequence, s factors through the canonical projection h and induces a well-defined score \tilde{s}:\mathcal{X}\times\mathcal{M}\to\mathbb{R}_{+},\qquad\tilde{s}(x,\tilde{y})=s(x,y),\quad\tilde{y}=h(y), which depends only \tilde{y}\in\mathcal{M} . Lemma 4.7 (Exchangeability is preserved under quotient maps) . Let (X_{i},Y_{i})_{i=1}^{n} be an exchangeable sequence of random variables taking values in \mathcal{X}\times\mathfrak{M} . Let h:\mathfrak{M}\to\mathcal{M}:=\mathfrak{M}/\sim be the canonical projection onto equivalence classes, and define \tilde{Y}_{i}:=h(Y_{i}) . Then the induced sequence (X_{i},\tilde{Y}_{i})_{i=1}^{n} taking values in \mathcal{X}\times\mathcal{M} is exchangeable. Lemma 4.7 ensures that the exchangeability of the observed data is preserved when passing from representative-valued outputs in \mathfrak{M} to their equivalence classes in the quotient space \mathcal{M} . We now establish conformal validity for Z -GW–based conformal sets. Let R_{i}=s(X_{i},Y_{i}) be the calibration scores and let \hat{q}_{1-\alpha} denote their empirical (1-\alpha) -quantile. For a new input X_{n+1} , define \mathcal{C}_{\alpha}^{\mathfrak{M}}(X_{n+1})=\Big\{y\in\mathfrak{M}:\mathrm{GW}^{Z}_{p}\big(f_{\theta}(X_{n+1}),y\big)\leq\hat{q}_{1-\alpha}\Big\}. (7) Proposition 4.8 (Conformal validity on \mathfrak{M} and \mathcal{M} ) . Let (X_{i},Y_{i})_{i=1}^{n} be exchangeable random variables taking values in \mathcal{X}\times\mathfrak{M} , and let f_{\theta}:\mathcal{X}\to\mathfrak{M} be a predictor. Define the nonconformity score s(x,y):=\mathrm{GW}^{Z}_{p}\!\big(f_{\theta}(x),\,y\big), and construct the conformal prediction set \mathcal{C}^{\mathfrak{M}}_{\alpha}(x)\subseteq\mathfrak{M} at level \alpha\in(0,1) using \tilde{s} . Then the following hold: 1. ( Marginal coverage ) \mathbb{P}\!\left(Y_{n+1}\in\mathcal{C}^{\mathfrak{M}}_{\alpha}(X_{n+1})\right)\;\geq\;1-\alpha. 2. ( Well-defined on Quotient ) \mathcal{C}^{\mathfrak{M}}_{\alpha}(x) is a union of equivalence classes and therefore induces a well-defined prediction set on the quotient space, \mathcal{C}^{\mathcal{M}}_{\alpha}(x):=h\!\left(\mathcal{C}^{\mathfrak{M}}_{\alpha}(x)\right)\subseteq\mathcal{M} , which satisfies \mathbb{P}\!\left(h(Y_{n+1})\in\mathcal{C}^{\mathcal{M}}_{\alpha}(X_{n+1})\right)\;\geq\;1-\alpha. All proofs are deferred to Appendix A . 4.3 Practical Restrictions The conformal set defined in Eq. 7 is an implicit subset of the graph space \mathfrak{M} , specified through a membership predicate rather than explicit enumeration. For any candidate graph y\in\mathfrak{M} , membership is determined by evaluating the nonconformity score s(x,y) and comparing it to the calibrated threshold. In molecular graph domains, however, \mathfrak{M} is combinatorially large, making the explicit materialization of \mathcal{C}(x) computationally infeasible. To obtain a finite and tractable prediction set, we intersect the implicit conformal set with an input-dependent candidate library \mathcal{L}(x)\subset\mathfrak{M} (e.g., a metabolite database determined by a mass spectrum): \mathcal{C}_{\mathcal{L}}(x)=\mathcal{C}(x)\cap\mathcal{L}(x)=\{y\in\mathcal{L}(x):s(x,y)\leq\hat{q}_{1-\alpha}\}. (8) In retrieval tasks, the candidate library is typically constructed to be complete, in the sense that the ground-truth output is contained almost surely, i.e., \mathbb{P}(Y_{n+1}\in\mathcal{L}(X_{n+1}))=1 . Under this assumption, \mathcal{C}_{\mathcal{L}}(x) coincides with the exact conformal prediction set restricted to the reduced output space \mathcal{L}(x) and therefore inherits the marginal coverage guarantee. Remark 4.9 . If the ground-truth output Y_{n+1} may lie outside \mathcal{L}(X) , the coverage degrades according to the probability of library incompleteness: \mathbb{P}(Y_{n+1}\in\mathcal{C}_{\mathcal{L}}(X_{n+1}))\;\geq\;(1-\alpha)-\mathbb{P}(Y_{n+1}\notin\mathcal{L}(X_{n+1})) . 5 Locally Adaptive Graph Conformal Prediction Previously, we extended conformal prediction to graph-valued outputs using a single global threshold on a nonconformity score. However, a global cutoff implicitly assumes homogeneous uncertainty across inputs. In practice, this assumption is rarely satisfied: some instances are intrinsically easy, while others are highly ambiguous. A single threshold therefore tends to produce overly conservative sets for easy inputs and risks undercoverage for difficult ones. In complex, high-dimensional, or structured output spaces (e.g. graphs, manifolds, or functional data), applying standard CQR directly in the output space \mathfrak{M} is often computationally or conceptually intractable, since conditional quantiles are not naturally defined for structured objects. To provide distribution-free locally adaptive guarantees in these settings, we introduce Score Conformalized Quantile Regression (SCQR). Score Conformalized Quantile Regression Given a point predictor f_{\theta}:\mathcal{X}\to\mathfrak{M} and a nonconformity score s(x,y)\in\mathbb{R} , with x\in\mathcal{X} and y\in\mathfrak{M} . SCQR relaxes the Graph conformal prediction one-size-fits-all assumption by allowing the threshold to depend on input-dependent attributes \omega(x)\in\Omega , which capture heteroscedasticity. These attributes may be the input itself (identity map) or derived quantities reflecting its complexity, e.g. size of candidate set or pre-trained embeddings. Concretely, we first train a quantile regression model \psi:\Omega\to\mathbb{R} using the pinball loss to estimate (1-\alpha) -conditional quantile of s(x,y) on a training set. We again compute the adaptive residuals E_{i}=s(X_{i},Y_{i})-\psi(\omega(X_{i})) . We then compute the empirical quantile of the residuals: \hat{q}_{1-\alpha}=\text{Quantile}\left(\{E_{i}\}_{i=1}^{n},\frac{\lceil(n+1)(1-\alpha)\rceil}{n}\right) . For a new input X_{n+1} , the conformal prediction set is: \mathcal{C}(X_{n+1})=\{y\in\mathfrak{M}:s(X_{n+1},y)\leq\psi(z(X_{n+1}))+\hat{q}_{1-\alpha}\}. (9) The residuals E_{i} may take both negative and positive values. Since s(x,y)\geq 0 and s(x,y)=0 indicates perfect conformity, negative residuals correspond to examples that are easier than predicted given \omega(x) , while positive residuals indicate an underestimation of difficulty. Retaining both is essential for adaptive and non-conservative conformal calibration. Proposition 5.1 (Marginal Coverage Guarantee of SCQR) . Let \{(X_{i},Y_{i})\}_{i=1}^{n+1} be exchangeable random variables, and let \omega:\mathcal{X}\to\Omega be a deterministic feature map. Assume that the nonconformity score s:\mathcal{X}\times\mathfrak{M}\to\mathbb{R} and the quantile regression function \psi:\Omega\to\mathbb{R} are fixed measurable functions, independent of the calibration sample. Then the SCQR prediction set expressed in Eq. 9 satisfies \mathbb{P}\!\left(Y_{n+1}\in\mathcal{C}(X_{n+1})\right)\geq 1-\alpha. (10) Remark 5.2 (One-Sided Nature of SCQR) . Unlike the original CQR for real-valued regression which often produces two-sided intervals [q_{low},q_{high}] , SCQR is inherently one-sided. This is because nonconformity scores are typically designed to be non-negative, where smaller values represent better fits. Table 1 : Comparison of conformal prediction (CP) and score conformalized quantile regression (SCQR) on graph-valued outputs with finite candidate sets on Coloring dataset. Both methods are evaluated at nominal coverage level 1-\alpha , with \alpha=0.1 . Arrows indicate whether higher ( \uparrow ) or lower ( \downarrow ) values are preferable. Implementation details are deferred to Appendix B Conformal Set Size \downarrow Candidate Set Size Reduction % \uparrow Task Z-GW distance Method Empirical Coverage Mean Median Mean Median Mean Median Empty rate (%) \downarrow Colors FGW - Adj + FD CP 90.2\% 4 1 205 223 95.8\% 98.9\% 8.9\% SCQR |\mathcal{L}(x)| 90.3\% 4 1 201 223 95.6\% 98.9\% 8.8\% Coloring — Conformal Prediction Coloring — SCQR Figure 3 : Conformal coverage and set size behavior across tasks. Histograms show empirical coverage versus candidate set size. Scatter plots show conformal set size versus candidate set size, the black dashed y=x line indicates no reduction, and points below the line demonstrate cases where conformal filtering reduces the set. Blue (resp. red) points indicate conformal sets containing the ground truth (resp. violations). For SCQR, the attribute function \omega(x) is task-dependent: \omega(x)=|\mathcal{L}(x)| (candidate set size) for Coloring. 6 Numerical Experiments To illustrate the general applicability of our approach, we consider both a synthetic graph prediction benchmark. The code will be made available. We refer to Appendix C for more details on implementations and extra results. 6.1 Synthetic Dataset We use the synthetic Coloring dataset [ 15 ] , consisting of pairs (X_{i},Y_{i}) where X_{i} is an image encoding a graph-coloring instance and Y_{i} is its ground-truth graph. Nodes take one of four discrete colors (blue, green, yellow, red) and edges indicate spatial neighboring. The task is to recover the underlying graph from the image, providing a controlled benchmark for image-to-graph prediction. Candidate sets. For each test instance (X_{i},Y_{i}) , we construct the candidate set \mathcal{L}(x) by selecting all graphs in the test split that share the same node-type configuration as Y_{i} , i.e., the same number of blue, green, yellow, and red nodes. This yields a controlled identification problem where structurally distinct graphs share identical node statistics. Model and protocol. We use Any2Graph [ 15 ] as graph predictor f_{\theta} (82% test accuracy), trained with the PMFGW loss. We use 100k samples for training and 10k each for calibration and testing. 6.2 Experimental Protocol Distance and nonconformity score. Our nonconformity score is based on the Z -GW, instantiated in practice as FGW with task-specific cost matrices. For Coloring, we use FGW with adjacency cost ( A ) and Feature Diffusion (FD) initialization of the solver. Calibration. Standard conformal prediction (CP) estimates a single global (1-\alpha) quantile from the calibration set. Score-Conformalized Quantile Regression (SCQR) instead conditions the threshold on an input-dependent attribute \omega(x) . For the synthetic Coloring task, we set \omega(x)=|\mathcal{L}(x)| , i.e., the candidate set cardinality. Evaluation metrics. All results are reported at nominal level 1-\alpha=0.9 . We measure empirical coverage, conformal set size (mean and median), reduction relative to the full candidate library, and empty-set rate. 7 Conclusion We introduced a conformal prediction framework for graph-valued outputs grounded in the Z -Gromov–Wasserstein geometry. By defining nonconformity through Z -GW, the method provides distribution-free coverage guarantees while respecting the permutation-invariant structure of graphs. We further proposed Score-Conformalized Quantile Regression (SCQR), which yields adaptive prediction sets by conditioning on input-dependent signals, improving efficiency without compromising validity. More broadly, the framework extends naturally to other structured output spaces representable as Z -networks, such as meshes, point clouds, and distributions, suggesting a general geometry-aware approach to uncertainty quantification in structured prediction. Appendix A More on Theoretical Results A.1 Proof of Proposition 4.4 Proof. Fix orderings V_{1}=\{v_{1},\dots,v_{n}\} and V_{2}=\{w_{1},\dots,w_{n}\} and identify \omega_{1},\omega_{2} with their matrix representations. ( \Rightarrow ) Assume G_{1}\sim G_{2} . By Definition 3.4 , there exist a finite Z -network W=(V_{W},\omega_{W},\mu_{W}) and measure-preserving maps \phi_{1}:V_{W}\to V_{1} and \phi_{2}:V_{W}\to V_{2} such that \omega_{W}=\phi_{1}^{*}\omega_{1}=\phi_{2}^{*}\omega_{2}\quad\mu_{W}\otimes\mu_{W}\text{-a.e.} Since \mu_{1} is uniform and measure preserving, \mu_{W}(\phi_{1}^{-1}(\{v\}))=\mu_{1}(\{v\})=\frac{1}{n}\qquad\forall v\in V_{1}, hence \phi_{1} is surjective; similarly for \phi_{2} . Writing \mu_{W}=\sum_{k=1}^{N}c_{k}\delta_{u_{k}} with c_{k}>0 , the above implies \sum_{u_{k}:\,\phi_{1}(u_{k})=v}c_{k}=\frac{1}{n}\qquad\forall v\in V_{1}, and analogously for \phi_{2} . Since V_{W} is finite with full-support measure, the pullback identity holds everywhere: \omega_{W}(u,u^{\prime})=\omega_{1}(\phi_{1}(u),\phi_{1}(u^{\prime}))=\omega_{2}(\phi_{2}(u),\phi_{2}(u^{\prime}))\qquad\forall u,u^{\prime}\in V_{W}. Choose a section s:V_{1}\to V_{W} with \phi_{1}\circ s=\mathrm{id}_{V_{1}} and define \varphi:=\phi_{2}\circ s:V_{1}\to V_{2} . Then \omega_{1}(v_{i},v_{j})=\omega_{2}(\varphi(v_{i}),\varphi(v_{j}))\qquad\forall i,j, so \omega_{1}=\varphi^{*}\omega_{2} . Since \mu_{1} and \mu_{2} are uniform atomic measures and \varphi is measure-preserving, each fiber \varphi^{-1}(\{w\}) has mass 1/n . As |V_{1}|=|V_{2}|=n , this implies that all fibers are singletons and hence \varphi is bijective. Let P=(P_{ij})\in\sigma_{n} be the permutation matrix defined by P_{ij}:=\mathbb{I}_{\{\,w_{j}=\varphi(v_{i})\,\}}, so that \omega_{1}=P^{\top}\omega_{2}P . ( \Leftarrow ) If \omega_{1}=P^{\top}\omega_{2}P for some P\in\sigma_{n} , let \varphi be the associated bijection and set W:=G_{1} , \phi_{1}:=\mathrm{id} , \phi_{2}:=\varphi . Both maps are measure-preserving and the pullback identity holds everywhere, hence G_{1}\sim G_{2} . ∎ A.2 Extra results for Section 4 Lemma A.1 (Measurable maps preserve equality in distribution) . Let (\Omega,\mathcal{F},\mathbb{P}) be a probability space. Let Z and Z^{\prime} be random variables taking values in a measurable space (\mathcal{Z},\Sigma_{\mathcal{Z}}) , and let g:\mathcal{Z}\to\mathcal{Y} be a measurable map into another measurable space (\mathcal{Y},\Sigma_{\mathcal{Y}}) . If Z\overset{d}{=}Z^{\prime}, then g(Z)\overset{d}{=}g(Z^{\prime}). Proof. Let B\in\Sigma_{\mathcal{Y}} be arbitrary. Since g is measurable, g^{-1}(B)\in\Sigma_{\mathcal{Z}} , and therefore \mathbb{P}\big(g(Z)\in B\big)=\mathbb{P}\big(Z\in g^{-1}(B)\big)=\mathbb{P}\big(Z^{\prime}\in g^{-1}(B)\big)=\mathbb{P}\big(g(Z^{\prime})\in B\big). Since this holds for all measurable sets B\subseteq\mathcal{Y} , we conclude that g(Z) and g(Z^{\prime}) have the same distribution. ∎ A.3 Proof of Lemma 4.7 Proof. Exchangeability of (X_{i},Y_{i})_{i=1}^{n} means that for any permutation \sigma of \{1,\dots,n\} , (X_{1},Y_{1},\dots,X_{n},Y_{n})\;\overset{d}{=}\;(X_{\sigma(1)},Y_{\sigma(1)},\dots,X_{\sigma(n)},Y_{\sigma(n)}). Define the measurable map g:\mathcal{X}\times\mathfrak{M}\to\mathcal{X}\times\mathcal{M} , g(x,y):=(x,h(y)) . Since h is measurable, so is g . Applying g componentwise and invoking Lemma A.1 , we obtain (X_{1},\tilde{Y}_{1},\dots,X_{n},\tilde{Y}_{n})\;\overset{d}{=}\;(X_{\sigma(1)},\tilde{Y}_{\sigma(1)},\dots,X_{\sigma(n)},\tilde{Y}_{\sigma(n)}), where \tilde{Y}_{i}=h(Y_{i}) . Since this holds for all permutations \sigma , the sequence (X_{i},\tilde{Y}_{i})_{i=1}^{n} is exchangeable. ∎ A.4 Proof of Proposition 4.8 Proof. By invariance of s under \sim , it factors through the canonical projection h and induces a score on \mathcal{M} . By Lemmas A.1 , the score sequence \{s(X_{i},Y_{i})\}_{i=1}^{n} is exchangeable. Standard conformal prediction theory 1 then yields \mathbb{P}\!\left(Y_{n+1}\in\mathcal{C}^{\mathfrak{M}}_{\alpha}(X_{n+1})\right)\geq 1-\alpha. Since \tilde{s}(x,h(y))=s(x,y) , membership in C^{\mathfrak{M}}_{\alpha}(x) depends only on the equivalence class h(y) . Hence, for any y,y^{\prime}\in\mathfrak{M} with h(y)=h(y^{\prime}) , y\in\mathcal{C}^{\mathfrak{M}}_{\alpha}(x)\quad\Longleftrightarrow\quad y^{\prime}\in\mathcal{C}^{\mathfrak{M}}_{\alpha}(x), so \mathcal{C}^{\mathfrak{M}}_{\alpha}(x) is a union of equivalence classes. Therefore the projection \mathcal{C}^{\mathcal{M}}_{\alpha}(x):=h\!\left(\mathcal{C}^{\mathfrak{M}}_{\alpha}(x)\right) is well defined. Let \tilde{Y}_{n+1}:=h(Y_{n+1}) denote the pushforward random variable, whose law is the pushforward measure P_{\tilde{Y}_{n+1}}=h_{\#}P_{Y_{n+1}} . Then \displaystyle\mathbb{P}\!\left(\tilde{Y}_{n+1}\in\mathcal{C}^{\mathcal{M}}_{\alpha}(X_{n+1})\right) \displaystyle=\mathbb{P}\!\left(\tilde{Y}_{n+1}\in h^{-1}\!\left(\mathcal{C}^{\mathcal{M}}_{\alpha}(X_{n+1})\right)\right) \displaystyle=\mathbb{P}\!\left(\tilde{Y}_{n+1}\in\mathcal{C}^{\mathfrak{M}}_{\alpha}(X_{n+1})\right), where the second equality follows from the fact that h^{-1}(\mathcal{C}^{\mathcal{M}}_{\alpha}(x))=\mathcal{C}^{\mathfrak{M}}_{\alpha}(x) . Combining with the conformal coverage guarantee in \mathfrak{M} yields \mathbb{P}\!\left(\tilde{Y}_{n+1}\in\mathcal{C}^{\mathcal{M}}_{\alpha}(X_{n+1})\right)\geq 1-\alpha . ∎ A.5 Proof of Proposition 5.1 Proof. Define the nonconformity scores (meta-scores) as E_{i}=s(X_{i},Y_{i})-\psi(\omega(X_{i})) for i=1,\dots,n+1 . Under the assumption that (X_{i},Y_{i}) are exchangeable and that the functions s , \omega , and \psi are measurable and independent of the calibration data, the sequence of scores \{E_{1},\dots,E_{n+1}\} is also exchangeable. Let E_{(1)}\leq E_{(2)}\leq\dots\leq E_{(n)} denote the sorted nonconformity scores of the calibration set. The threshold \hat{q}_{1-\alpha} is defined as the k -th smallest value: \hat{q}_{1-\alpha}=E_{(k)},\quad\text{where }k=\lceil(n+1)(1-\alpha)\rceil. (11) By the property of exchangeable random variables, the rank of E_{n+1} among the set \{E_{1},\dots,E_{n+1}\} is uniformly distributed over \{1,\dots,n+1\} . Thus, the probability that the test score E_{n+1} ranks among the k smallest of the n+1 total scores is: \mathbb{P}\left(E_{n+1}\leq\hat{q}_{1-\alpha}\right)=\frac{k}{n+1}=\frac{\lceil(n+1)(1-\alpha)\rceil}{n+1}\geq 1-\alpha. (12) Since Y_{n+1}\in\mathcal{C}(X_{n+1})\iff E_{n+1}\leq\hat{q}_{1-\alpha} , the marginal coverage guarantee follows directly. ∎ Appendix B Evaluation Metrics This appendix details the metrics reported in Table 1 for comparing conformal prediction (CP) and score-conditional quantile regression (SCQR) on graph-valued outputs with finite candidate sets. Setup. For each test input x , let \mathcal{L}(x) denote the associated candidate set of graphs, and let \mathcal{C}_{\alpha}(x)\subseteq\mathcal{L}(x) be the conformal prediction set constructed at nominal coverage level 1-\alpha . Let y denote the ground-truth graph. Empirical Coverage. Empirical coverage is computed as \widehat{\mathrm{Cov}}(1-\alpha)=\frac{1}{|\mathcal{D}_{\mathrm{test}}|}\sum_{(x,y)\in\mathcal{D}_{\mathrm{test}}}\mathbb{I}\big\{y\in\mathcal{C}_{\alpha}(x)\big\}. Both CP and SCQR are evaluated at the same nominal level 1-\alpha . Prediction Set Size. The prediction set size for an input x is given by |\mathcal{C}_{\alpha}(x)| . We report both the mean and the median of this quantity across the test set to account for potential skewness in the distribution of set sizes. Relative Reduction. To quantify efficiency relative to the original candidate set, we define the relative reduction for each input as \mathrm{Reduction}(x)=\frac{|\mathcal{L}(x)|-|\mathcal{C}_{\alpha}(x)|}{|\mathcal{L}(x)|}\times 100\%. We report the mean and median reduction over the test set. Empty Set Rate. The empty set rate is defined as \frac{1}{|\mathcal{D}_{\mathrm{test}}|}\sum_{(x,y)\in\mathcal{D}_{\mathrm{test}}}\mathbb{I}\big\{\mathcal{C}_{\alpha}(x)=\emptyset\big\}. This quantity reflects how often the conformal procedure returns no candidate graph and is reported as a sanity check in finite-candidate settings. Remark B.1 . Reporting both mean and median statistics is crucial due to the typically heavy-tailed distribution of candidate set sizes. While both CP and SCQR are guaranteed to satisfy marginal coverage, differences in set size and reduction reflect their relative efficiency, with SCQR expected to yield more adaptive prediction sets. Remark B.2 . We distinguish between validity, defined as marginal coverage, and efficiency, defined as the size of the conformal prediction set. Since prediction set size is meaningful only when the ground truth is contained in the conformal set, we report mean and median prediction set size and relative reduction conditioned on coverage, i.e., over the subset \{x\mid(x,y)\in\mathcal{D}_{\text{test}},\ y\in\mathcal{C}_{\alpha}(x)\}. As a consequence, the reported candidate set statistics in Table 1 may differ across methods, since they are computed only over the subset of inputs for which the conformal set contains the ground truth. Because each method achieves coverage on slightly different instances, the corresponding candidate set averages are evaluated on different subsets. Coverage itself is always reported over the full test set. Appendix C Experimental Details C.1 Datasets We describe here the datasets and evaluation protocols used for the Coloring. Coloring (Synthetic). For the Coloring task, we use the synthetic dataset introduced in 15 . The dataset already provides predefined test and validation splits, in which we used 10k for each. We use the test split for conformal calibration and report all evaluation metrics on the validation split. Figure 4 : Coloring dataset examples using Any2Graph as graph predictor. C.2 Training For the Coloring task, we use Any2Graph [ 15 ] . Both models were trained using the default configurations provided in their respective official repositories, without additional hyperparameter tuning. Training was performed on NVIDIA A100 GPU. Conformal calibration and evaluation were conducted on CPU. SCQR calibration based on candidate set size |\mathcal{L}(x)| was done by fitting a linear quantile regressor to predict calibration set non-conformity scores from |\mathcal{L}(x)| . SCQR calibration based on DreaMS embeddings was done by training a 2-layer neural network to predict non-conformity scores from them. The architecture is as follows: • Linear(768, 384) • ReLU • Linear(384, 1) The network was trained with the following parameters: Table 2 : embedding-based SCQR neural network training parameters Parameter Value Optimizer Adam Learning rate 0.001 Batch size 32 Early stopping patience 3 Early stopping minimum loss improvement 0.0001 Complete training on the 10 000 samples of the calibration set takes a few seconds.