REVIEW 3 major objections 4 minor 8 references
Conformal Graph Prediction with Z-Gromov-Wasserstein Distances
T0 review · 3 major / 4 minor · reviewed 2026-08-02 · deepseek-v4-flash
Pith's one-line read The paper proves that conformal prediction sets for graph-valued outputs achieve finite-sample marginal coverage when the nonconformity score is a Z-Gromov-Wasserstein distance, and that an input-adaptive variant (SCQR) preserves the guaran
desk verdict The theory is a clean but mostly textbook conformal argument; the empirical validation has two fixable but real problems that undercut the reported coverage numbers. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The Z-Gromov-Wasserstein distance: a distance on Z-networks, i.e. measurable spaces equipped with a pairwise relation valued in a metric space (Z,dZ), which compares graphs through an optimal-transport coupling and is invariant to node permutation. In the finite graph setting, weak isomorphism collapses exactly to permutation relabeling, so the score factors through the quotient graph space M/∼, making the conformal sets well defined on unlabeled graphs. SCQR's meta-score, the residual between the raw Z-GW score and a quantile-regression prediction ψ(ω(x)), is the device that converts a global cutoff into an input-dependent one while keeping the score sequence exchangeable.
What would settle it
Run the Coloring protocol exactly as written: build the candidate library L(x) from the test split and evaluate coverage on the validation split. If the validation ground-truth graphs are not among the test-split candidates, coverage should be 0%, contradicting the reported 90.2%; a corrected run should instead construct L(x) containing the true graph and confirm coverage is at least 90%.
Extended reading notes
Core claim
Define the nonconformity score as the Z-Gromov-Wasserstein distance between the predicted graph and a candidate graph. Because this distance is invariant under node permutation, the score is well defined on the quotient graph space, and exchangeability of the data survives passing to equivalence classes. The conformal set built by thresholding this score at the empirical quantile then has marginal coverage at least 1−α, and the set is a union of equivalence classes, so it is a legitimate prediction set for unlabeled graphs. SCQR replaces the single global threshold with a quantile-regression-thresholded residual score, yielding input-adaptive sets while preserving the same marginal coverage
Load-bearing premise
The true output graph must belong to the finite candidate library for every new input; the paper's synthetic evaluation appears to violate this by drawing libraries from the test split while evaluating on validation-split ground truths.
Editorial extensions
If this is right
- Any pretrained graph predictor can be wrapped with a conformal set that carries a finite-sample 1−α marginal coverage guarantee without retraining, provided calibration data are exchangeable.
- Prediction sets are permutation-invariant, so they are meaningful for unlabeled or node-relabeled graphs where node ordering is arbitrary.
- SCQR gives locally adaptive thresholds, conditioning on quantities such as candidate-set size, which can shrink sets for easy inputs without sacrificing the marginal coverage guarantee.
- In retrieval and molecular-identification settings with complete candidate libraries, the conformal set is a filtered subset of the database, with empty-set rate as a sanity metric.
- The same argument extends to other structured outputs representable as Z-networks, such as meshes, point clouds, and distributions, giving a geometry-aware route to uncertainty quantification in structured prediction.
Reading between the lines
- Editorial: The reported synthetic experiment appears internally inconsistent: Section 6.1 constructs candidate libraries from the test split, while Appendix C.1 says evaluation ground truths come from the validation split. As written, the true graph would not be in the library, which would break the completeness assumption; a clean evaluation should build libraries that contain the ground truth or
- Editorial: The abstract promises a real molecule-identification evaluation, but the experimental section reports only the synthetic Coloring task, so the applied claim for molecular identification remains unsupported by the experiments shown.
- Editorial: The marginal coverage guarantee is not conditional on the input; SCQR's adaptivity improves efficiency but does not provide per-instance coverage, so users needing conditional guarantees would require additional machinery.
- Editorial: The practical bottleneck is computational, since each candidate graph requires an optimal-transport evaluation; the method is most useful for small graphs or small candidate libraries, and its benefit over plain CP depends on how well the attribute ω(x) tracks true difficulty.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a conformal prediction framework for graph-valued structured outputs. It represents graphs as Z-networks and uses the Z-Gromov–Wasserstein (Z-GW) distance, instantiated as Fused Gromov–Wasserstein (FGW), to define a permutation-invariant nonconformity score. The authors prove finite-sample marginal coverage for conformal sets in both the graph space and its quotient under node permutation (Prop. 4.8), and introduce Score Conformalized Quantile Regression (SCQR), a CQR-style method that conditions the conformal threshold on an input-dependent attribute with a marginal coverage guarantee under a fixed quantile-regression function (Prop. 5.1). The empirical section reports a synthetic Coloring image-to-graph benchmark, comparing CP and SCQR at 90% nominal coverage. The central theoretical arguments are standard split-conformal arguments and are essentially correct under their stated assumptions, but the experimental implementation as written conflicts with those assumptions in two load-bearing ways: SCQR is calibrated by fitting the quantile regressor on the calibration set, and the candidate-library construction contradicts the stated split protocol.
Significance. If the reported experiments are corrected, the framework would be a useful and natural extension of conformal prediction to structured graph-valued outputs. The permutation-invariant Z-GW score and the quotient-space formulation are conceptually appropriate, and the proof that coverage transfers from representative graphs to the quotient space is clean. The SCQR extension is a straightforward but sensible adaptation of CQR to non-Euclidean outputs, and its theoretical statement is correct when the quantile regressor is fixed in advance. The paper also benefits from being model-agnostic and from explicitly discussing the candidate-library restriction that is unavoidable in molecule-retrieval applications. However, the empirical validation currently does not instantiate the theorem's assumptions: the SCQR quantile regressor is trained on the calibration set, and the synthetic experiment's candidate-library construction is internally inconsistent with the split description. These issues undermine the main applied claims, but they are fixable within the manuscript's scope.
major comments (3)
- [§5, Prop. 5.1, App. C.2] The marginal coverage guarantee of SCQR assumes that the quantile regression function ψ is fixed and independent of the calibration sample. Appendix C.2 states that 'SCQR calibration based on candidate set size |L(x)| was done by fitting a linear quantile regressor to predict calibration set non-conformity scores from |L(x)|', and that the embedding-based SCQR neural network is trained on the same 10,000 calibration samples. When ψ is fitted on the calibration set, the residuals E_i = s(X_i,Y_i) − ψ(ω(X_i)) are computed in-sample, so the joint distribution of (E_1,...,E_{n+1}) is not exchangeable and the rank argument in Appendix A.5 does not apply. The reported 90.3% SCQR coverage therefore cannot be attributed to Prop. 5.1. This is a load-bearing issue for the paper's main methodological novelty. Fix: train ψ on a separate training split (or on part of the calibration data), compute th
- [§4.3, Eq. (8), Remark 4.9, §6.1, App. C.1] Candidate-library completeness is load-bearing for the practical prediction set C_L = C ∩ L. If the ground-truth output is not in L, coverage degrades by the incompleteness probability (Remark 4.9). The synthetic experiment as written violates this condition. Section 6.1 says that for each test instance the candidate set L(x) is constructed by selecting graphs from the test split with the same node-type configuration, while Appendix C.1 says that the test split is used for conformal calibration and all evaluation metrics are reported on the validation split. Under this protocol, a validation-set ground-truth graph is not guaranteed to be in L(x), so the reported empirical coverage of about 90% cannot be interpreted as conformal coverage. This is not a minor wording issue: the experiment needs to ensure P(Y ∈ L(X)) = 1 on the evaluation split, and the split roles must be described consist
- [Abstract, §6, §7, Fig. 1] The abstract states that the method is evaluated on 'a synthetic task and a real problem of molecule identification', and Figure 1 displays a MassSpecGym metabolite-prediction example. However, Section 6 only reports the synthetic Coloring benchmark, and Section 7 refers only to 'a synthetic graph prediction benchmark'. If the molecule-identification experiment is part of the paper, it must be described with its full experimental protocol, including the candidate library, the predictor, calibration details, and results. If it is not part of the paper, the abstract and Figure 1 overclaim the empirical scope. This mismatch should be corrected in revision.
minor comments (4)
- [§6.1] The sentence 'To illustrate the general applicability of our approach, we consider both a synthetic graph prediction benchmark' uses 'both' but only one benchmark is described; remove 'both' or add the missing experiment.
- [App. B, Remark B.2] The reported mean/median candidate set size and reduction are computed conditionally on coverage, and Remark B.2 acknowledges that the two methods cover different subsets. This makes the direct comparison of set-size statistics in Table 1 potentially biased. Please also report unconditional statistics or a matched-efficiency comparison.
- [§6.2] The text says 'We use the test split for conformal calibration and report all evaluation metrics on the validation split' in Appendix C.1, but Section 6.1 describes the candidate set as coming from the 'test split'. Please unify terminology ('calibration set' vs 'test set') and clarify which split is used for constructing L(x).
- [Appendix C.2] For the embedding-based SCQR, the reported training time on the calibration set is a few seconds; if this is retained after the revision, specify how the separate calibration split is chosen and how overfitting is controlled.
Circularity Check
No significant circularity in the theoretical derivation; the SCQR coverage proof is a standard exchangeability argument, and the experimental assumption violations are correctness issues rather than circular derivations.
full rationale
The main theoretical claims are self-contained and do not reduce to their own inputs. Proposition 4.8 follows directly from exchangeability of the score sequence, which is inherited from the exchangeability of (Xi,Yi) and the measurability of the Z-GW score; the threshold q̂ is the standard conformal quantile. Proposition 5.1 is likewise the textbook CQR rank argument applied to one-sided residuals, with the key assumption that ψ is fixed and independent of the calibration sample. No fitted parameter is reused as its own prediction inside the proof. The Z-GW metricity result is imported from Bauer et al. (external work), and self-citations to the authors' earlier papers are used only for base predictors (ANY2GRAPH) or related graph-conformal work, not as load-bearing support for the coverage theorems. Two experimental concerns exist but are not circularity: Appendix C.2 states that 'SCQR calibration based on candidate set size |L(x)| was done by fitting a linear quantile regressor to predict calibration set non-conformity scores from |L(x)|', which violates the independence condition of Proposition 5.1 and means the reported 90.3% coverage cannot be attributed to the theorem; and Section 6.1 constructs L(x) from the test split while Appendix C.1 evaluates on the validation split, contradicting the completeness assumption of Section 4.3. These are serious empirical validity flaws, but they do not make the derivation equivalent to its inputs, so the circularity score remains low.
Assumptions & free parameters
free parameters (2)
- FGW metric weights β and γ =
not reported
- SCQR quantile regressor parameters (linear or 2-layer MLP) =
trained on calibration data
assumptions (5)
- domain assumption Exchangeability of observed pairs (X_i,Y_i) in X×M (Assumption 4.5)
- domain assumption Candidate-library completeness P(Y_{n+1}∈L(X_{n+1}))=1 (Section 4.3)
- standard math Z-GW is a genuine metric on Z-network isomorphism classes (Bauer et al., Thm 29)
- standard math Canonical projection h and score s are measurable
- domain assumption Base predictor f_θ is fixed and independent of calibration data
Cite this review
Pith. "Pith review of Conformal Graph Prediction with Z-Gromov-Wasserstein Distances." pith.science (2026). https://pith.science/paper/RLT7NFDA
@misc{pith2026260302460,
author = {Pith},
title = {Pith review of: Conformal Graph Prediction with Z-Gromov-Wasserstein Distances},
year = {2026},
howpublished = {\url{https://pith.science/paper/RLT7NFDA}},
note = {Machine review of arXiv:2603.02460}
}
read the original 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
Figures from the paper (1 more)
Reference graph
Works this paper leans on
-
[1]
, En+1}is also exchangeable
Under the assumption that (Xi, Yi) are exchangeable and that the functions s, ω, and ψ are measurable and independent of the calibration data, the sequence of scores{E 1, . . . , En+1}is also exchangeable. Let E(1) ≤E (2) ≤ · · · ≤E(n) denote the sorted nonconformity scores of the calibration set. The threshold ˆq1−α is defined as thek-th smallest value: ...
2024
-
[5]
Opti- mal transport-based conformal prediction.arXiv preprint arXiv:2501.18991,
Gauthier Thurin, Kimia Nadjahi, and Claire Boyer. Opti- mal transport-based conformal prediction.arXiv preprint arXiv:2501.18991,
-
[7]
Yiwen Zhang, Keyan Ding, Yihang Wu, Xiang Zhuang, Yi Yang, Qiang Zhang, and Huajun Chen. Breaking the modality barrier: Generative modeling for accurate molecule retrieval from mass spectra.arXiv preprint arXiv:2511.06259,
-
[1978]
Neural optimal transport meets multivariate conformal prediction.arXiv preprint arXiv:2509.25444,
Vladimir Kondratyev, Alexander Fishkov, Nikita Kotelevskii, Mahmoud Hegazy, Remi Flamary, Maxim Panov, and Eric Moulines. Neural optimal transport meets multivariate conformal prediction.arXiv preprint arXiv:2509.25444,
-
[2011]
Dai Hai Nguyen, Canh Hao Nguyen, and Hiroshi Mamit- suka. Recent advances and prospects of computational methods for metabolite identification: a review with em- phasis on machine learning approaches.Briefings in bioinformatics, 20(6):2028–2043,
-
[2022]
Conformal prediction sets for populations of graphs.arXiv preprint arXiv:2404.18862,
Anna Calissano, Matteo Fontana, Gianluca Zeni, and Si- mone Vantini. Conformal prediction sets for populations of graphs.arXiv preprint arXiv:2404.18862,
-
[2023]
The z-gromov-wasserstein distance.arXiv preprint arXiv:2408.08233,
Martin Bauer, Facundo Mémoli, Tom Needham, and Mao Nishino. The z-gromov-wasserstein distance.arXiv preprint arXiv:2408.08233,
-
[2024]
Conformal structured prediction.arXiv preprint arXiv:2410.06296,
Botong Zhang, Shuo Li, and Osbert Bastani. Conformal structured prediction.arXiv preprint arXiv:2410.06296,
Reviewed August 2, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.