Pith. sign in

REVIEW 2 major objections 5 minor 22 references

Graph conformal prediction sets stay small on heterophilic graphs

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · deepseek-v4-flash

2026-08-01 02:53 UTC pith:5CJBF74D

load-bearing objection A useful diagnostic of DAPS' heterophily failure with a sound coverage proof, but the headline efficiency claims rest on an invalid oracle test and an insignificant selector. the 2 major comments →

arxiv 2607.25273 v1 pith:5CJBF74D submitted 2026-07-28 cs.LG

HeAD-CP: Heterophily-Aware Diffused Conformal Prediction Sets for Graph Neural Networks

Phan Binh Nguyen Lam , Nguyen Thai Anh This is my paper
classification cs.LG
keywords conformal predictiongraph neural networksheterophilyuncertainty quantificationdiffusionprediction setsnode classificationcoverage guarantee
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper identifies a failure mode in Diffused Adaptive Prediction Sets (DAPS), a standard conformal prediction method for graphs: its uniform diffusion of scores across edges assumes neighboring nodes share similar labels, which is false on heterophilic graphs and can inflate prediction-set sizes by up to 10.6% relative to plain APS. To fix this, the authors propose HeAD-CP, a family of diffusion variants whose per-node or per-edge coefficients are computed from the GNN's own softmax output, allowing the diffusion to reverse direction (high-pass) where neighborhoods are label-dissimilar. All variants provably preserve the marginal coverage guarantee, and on ten benchmarks the best variant per dataset stays at or below plain APS on every dataset, whereas DAPS exceeds APS on six. The paper's central claim is that making diffusion heterophily-aware—not just stronger or weaker—recovers the efficiency that uniform diffusion loses.

Core claim

The paper's central discovery is that the uniform diffusion coefficient in DAPS is the root cause of its failure on heterophilic graphs: a one-hop low-pass filter forces each node's non-conformity score toward its neighborhood mean, which is appropriate only when neighbors share labels. HeAD-CP replaces the global λ with label-free local estimates of homophily derived from the GNN softmax. Three variants—signed (per-node γ_v = γ_max(2h_v−1) with hard pseudo-label homophily h_v), edge-compatibility (per-edge ρ(u,v) based on softmax inner products), and a DAPS-baseline-with-correction (v3)—together span the homophily spectrum, and all preserve marginal coverage (Theorem 1) regardless of coeffi

What carries the argument

The key machinery is a set of node-wise or edge-wise diffusion coefficients computed from the GNN's softmax output, which serve as a label-free proxy for local homophily. The signed variant uses hard pseudo-label homophily h_v (Laplace-smoothed fraction of neighbors sharing the node's pseudo-label) to set a per-node coefficient that flips sign: positive for low-pass diffusion on homophilic neighborhoods, negative for high-pass diffusion on heterophilic ones. The edge-compatibility variant defines a per-edge similarity ρ(u,v) from softmax inner products, allowing mixed neighborhoods to be handled edge-by-edge. The v3 variant combines a DAPS-style baseline with a soft-homophily, confidence-gat

Load-bearing premise

The efficiency gains rely on the GNN's softmax being an informative label-free proxy for true local homophily; if the softmax does not track label agreement, the derived diffusion coefficients can mis-set the direction of diffusion as badly as uniform DAPS.

What would settle it

Take a heterophilic graph with known high homophily in the true labels but shuffle or randomize the node features so the GNN softmax is essentially uninformative (e.g., near-uniform predictions). If HeAD-CP's signed and edge variants then fail to beat plain APS, or produce prediction sets larger than DAPS, the softmax-proxy assumption is falsified.

Watch this falsifier. Get emailed when new claim-graph text bears on it.

If this is right

  • If correct, any graph-conformal method that diffuses scores uniformly should be re-examined on heterophilic benchmarks, since the paper shows such diffusion can degrade efficiency rather than improve it.
  • The coverage guarantee (Theorem 1) holds even with negative diffusion coefficients, so practitioners can safely use signed or edge-level high-pass diffusion without special calibration procedures.
  • The HeAD-CP family provides an upper bound on what any label-free selector can achieve: the post-hoc oracle stays at or below plain APS on every dataset, whereas DAPS exceeds APS on six.
  • The fixed hyperparameters (λ=0.5, γ_max=0.5) yield a wide flat plateau in efficiency across diffusion strengths, reducing sensitivity to hyperparameter tuning compared to DAPS.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The softmax-proxy assumption is the main risk: if the GNN's softmax is mis-calibrated or near-uniform on a heterophilic graph, the signed coefficients may be essentially random, and the method could degrade to plain APS or worse. This could be tested by corrupting node features to produce uninformative softmax outputs and measuring efficiency.
  • The paper's selector rule (7) based on dataset-mean soft homophily recovers only 66.8% of the oracle gain, suggesting that a more calibrated selector—perhaps using confidence-gating or held-out validation—could close much of the gap; this is a concrete next step the paper leaves open.
  • The edge-compatibility variant's use of softmax inner products could be extended to weighted graphs or directed graphs, where the edge-level diffusion naturally respects asymmetric relationships, but this is not explored in the paper.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. The paper identifies a failure mode of DAPS, a graph-aware conformal-prediction baseline that diffuses APS scores with a uniform coefficient λ, on heterophilic graphs. It proposes HeAD-CP, a family of three variants whose per-node or per-edge diffusion coefficients are derived from the GNN softmax via pseudo-label homophily, edge compatibility, or a soft confidence-gated correction. The paper proves marginal coverage for all variants (Theorem 1), reports a CSBM experiment isolating the low-pass failure mechanism, and evaluates on ten real benchmarks with three GNN backbones. The headline empirical claim is that a post-hoc oracle over the three HeAD-CP variants strictly outperforms DAPS on 8/10 datasets at p<0.01, while the only label-free selector recovers 66.8% of the oracle gain at p=0.21.

Significance. If the claims held, this would be a useful contribution: it documents a previously underappreciated deficiency of DAPS-style uniform diffusion on heterophilic graphs, proposes a coverage-preserving signed/edge-aware alternative, and provides a clean synthetic confirmation. The coverage argument in Theorem 1 is a standard split-CP exchangeability argument and appears sound: all auxiliary coefficients are deterministic functions of (X,A,f_θ) fixed before calibration, so the proof is not circular. The empirical point estimates are suggestive, and the CSBM experiment cleanly isolates the low-pass failure mechanism. However, the central statistical claim is undermined by an invalid oracle-based significance test, and the abstract's 'family stays at or below plain APS' is only true for the row-wise oracle, not for any fixed deployable variant. The practical benefit over DAPS therefore remains unproven in the current manuscript.

major comments (2)
  1. [§V-D and Abstract] The paired Wilcoxon test for the 'post-hoc oracle' is statistically invalid. For each (model, seed) replicate, the oracle efficiency is the minimum of the three correlated variant efficiencies (signed, edge, v3) computed on the same 100 calibration–test partitions. Under the null that all three variants are no better than DAPS, the minimum of three random variables is stochastically smaller than any fixed variant, making the signed-rank p-values anti-conservative. Thus the abstract's claim that the oracle improves over DAPS on 8/10 datasets at p<0.01, and the pooled p<10^-17, do not establish even an oracle-level advantage, let alone a practical one. The later caveat that the oracle is an 'upper bound' is appropriate, but Significance tests on a selected upper bound are not valid. Please report per-variant paired tests with multiplicity correction, or select the variant on an independent
  2. [§I, Abstract, Table I] The statement that the 'HeAD-CP family stays at or below plain APS on every dataset' is only true for the row-wise oracle, not for the family as a set of fixed variants. In Table I, HEAD-CP-v3 exceeds APS on all six heterophilic datasets (e.g., Roman-Empire 9.374 vs 8.544, Texas 3.184 vs 2.879, Cornell 3.918 vs 3.880, Wisconsin 2.690 vs 2.546, Squirrel 4.048 vs 3.956, Chameleon 3.139 vs 3.039), and HEAD-CP-signed exceeds APS on Cornell (3.895 vs 3.880). Since no label-free selector achieves the oracle, the abstract's unconditional wording overstates the result. Please qualify the claim as applying to the post-hoc row-wise oracle only, or provide a deployable selection rule with valid statistical support.
minor comments (5)
  1. [Throughout] The method name is spelled inconsistently: 'HeAD-CP' in the title and abstract, but 'HEAD-CP' in most of the body. Please standardize.
  2. [Table I caption and column 'Best'] The 'Best' column includes DAPS on Citeseer and PubMed, although the paper frames the oracle as being over HeAD-CP variants. Clarify whether the oracle is over all methods or only the three proposed variants, and adjust the caption and discussion accordingly.
  3. [§V-D] The sentence 'The same 8/10 remain significant under Benjamini–Hochberg at α=0.01 (7/10 under Holm–Bonferroni)' inherits the invalid oracle p-values and should be removed or recomputed with a valid testing procedure.
  4. [Figure 3] The legend labels the signed variant as 'HeAD-CP (ours)', but the paper has three variants. Please label it 'signed HeAD-CP' to avoid implying the other variants were not run in the CSBM experiment.
  5. [§VI] The label-free selector (7) never activates v3 because h_soft ranges from 0.09 to 0.51, below the 0.6 threshold. This makes the selector effectively a binary choice between signed and edge. If v3 is intended as a production variant, please discuss how a calibrated selector could ever select it, or adjust the threshold design.

Circularity Check

0 steps flagged

No circularity: the coverage proof is a standard split-CP argument with score coefficients that are deterministic functions of (X,A,f_theta), and the oracle/selector claims are explicitly labeled post-hoc empirical upper bounds.

full rationale

The paper's central derivation is Theorem 1, which states that HeAD-CP variants (Eqs. 3, 5, 6) preserve marginal coverage. The proof conditions on the unlabeled graph (X,A), the trained GNN f_theta, and the APS randomization variables, and every auxiliary quantity (gamma_v, rho(u,v), h_v, h_soft_v, conf_v) is built from the GNN softmax p_v alone, with no pool label used. The calibrated threshold tau is then the standard split-CP quantile, and the rank-uniformity argument applies unchanged even for negative diffusion coefficients. None of the definitions of the coefficients presuppose the coverage or efficiency result. The empirical efficiency claims use fixed hyperparameters (lambda = gamma_max = eta = gamma_base = gamma_var = 0.5), and the "post-hoc oracle" is explicitly admitted to be an upper bound over the three variants, not a fitted parameter renamed as a prediction. The proposed label-free selector (Eq. 7) is evaluated honestly and reported as not significant (p = 0.21), so there is no fitted-input-called-prediction pattern. The manuscript also openly flags the pseudo-label homophily limitation and leaves the selector design as an open question. The only notable concern is that the paired Wilcoxon test on the oracle selects the best of three correlated variants, which is a statistical selection-bias problem rather than a circular-derivation problem; it does not make the coverage result equivalent to its inputs and does not fall under the enumerated circularity patterns. No self-citations are load-bearing, and no uniqueness theorem or ansatz is imported from the authors' prior work.

Axiom & Free-Parameter Ledger

6 free parameters · 4 axioms · 0 invented entities

The method contributes no new physical or mathematical entities. It introduces hand-chosen global diffusion constants that are not fitted to test data, and relies on standard split-CP assumptions plus the empirical premise that softmax-derived homophily proxies carry signal.

free parameters (6)
  • γ_max = 0.5
    Global signed-diffusion strength in Eqs. 3 and 5; fixed to 0.5 to avoid per-dataset tuning; robustness swept in Fig. 4.
  • η = 0.5
    Edge-diffusion strength in Eq. 5, set equal to γ_max.
  • γ_base = 0.5
    DAPS baseline coefficient in the v3 update, Eq. 6.
  • γ_var = 0.5
    Soft-homophily correction strength in the v3 update, Eq. 6.
  • λ = 0.5
    DAPS baseline coefficient used for comparison and embedded in v3.
  • selector thresholds (0.4, 0.6) = 0.4, 0.6
    Fixed, not tuned, but chosen by the authors for Eq. 7; the realized h_soft range makes the rule assign signed to 9/10 datasets and never activate v3.
axioms (4)
  • standard math Uniform random split of calibration/test pool preserves exchangeability of scores.
    Theorem 1 depends on the standard split-CP exchangeability argument.
  • domain assumption The GNN f_θ is trained on a TRAIN split disjoint from the calibration-test pool, so its outputs and derived coefficients use no pool labels.
    Stated in Theorem 1 proof; if violated, the coverage guarantee breaks.
  • ad hoc to paper Pseudo-label/softmax homophily proxies (h_v, ρ, h_soft) are informative about true label homophily.
    No theoretical guarantee is given; Section VI concedes pseudo-label homophily is unreliable when validation accuracy is low.
  • domain assumption Softmax outputs are treated as meaningful class-probability estimates for confidence and compatibility.
    Used in Eq. 4 and conf_v; miscalibrated softmax weakens edge/v3 signals but does not affect coverage.

pith-pipeline@v1.3.0-alltime-deepseek · 9771 in / 12674 out tokens · 110828 ms · 2026-08-01T02:53:23.204917+00:00 · methodology

0 comments
read the original abstract

Conformal prediction (CP) provides distribution-free uncertainty quantification, and its extension to graphs is an active research direction. Diffused Adaptive Prediction Sets (DAPS) is a widely used graph-aware diffusion baseline, propagating Adaptive Prediction Sets (APS) non-conformity scores along edges with a uniform coefficient $\lambda$. We identify a fundamental shortcoming of this design: the uniform low-pass diffusion presupposes graph homophily and proves detrimental on heterophilic graphs, enlarging the mean prediction-set size by up to 10.6% relative to plain APS. To mitigate this, we propose HeAD-CP, a family of node-wise diffusion variants whose coefficients are determined by a label-free local-homophily estimate derived from the GNN softmax. Three variants, namely signed-$\gamma$, edge-compatibility, and a DAPS-baseline-with-correction, are most effective at extreme heterophily, intermediate heterophily, and moderate-to-high homophily, respectively, and all preserve the marginal coverage guarantee. On ten benchmarks, the HeAD-CP family stays at or below plain APS on every dataset, while DAPS exceeds APS on six. The post-hoc oracle over the family improves over DAPS on 8/10 datasets at $p<0.01$ (paired Wilcoxon), with the largest gains on heterophilic graphs (10.3% on Texas); on the two homophilic datasets where DAPS still wins (CiteSeer, PubMed), it retains a marginal advantage of at most 0.002, statistically insignificant on CiteSeer ($p=0.23$). Designing a calibrated label-free selector that approaches this oracle is the main outstanding empirical question.

Figures

Figures reproduced from arXiv: 2607.25273 by Nguyen Thai Anh, Phan Binh Nguyen Lam.

Figure 1
Figure 1. Figure 1: Per-dataset percentage efficiency change relative to APS (negative = better). DAPS (red) and HEAD-CP-v3 (blue) inflate sizes on heterophilic graphs (v3 inherits the failure since it carries a DAPS-style baseline). HEAD-CP-signed (green) covers the lowest-homophily datasets (Roman-Empire, texas, wisconsin), while HEAD-CP-edge (orange) covers the mid-heterophily datasets (cornell, chameleon, squirrel). The p… view at source ↗
Figure 2
Figure 2. Figure 2: Normalized efficiency (APS = 1.0) across 10 datasets (lower is better). DAPS (red) and HEAD-CP-v3 (blue) cross 1.0 on heterophilic data because v3 carries a DAPS-style baseline. HEAD-CP-signed (green) is below 1.0 at extreme heterophily, while HEAD-CP-edge (orange) covers the mid-heterophily datasets (cornell, squirrel, chameleon) where signed slightly exceeds 1.0. The HEAD-CP-v2 (purple) ablation never st… view at source ↗
Figure 3
Figure 3. Figure 3: Synthetic CSBM mechanism confirmation. Com￾parison of APS, DAPS, and signed HEAD-CP. Marginal coverage (right) is preserved by all methods, while efficiency (left) reveals that DAPS catastrophically inflates prediction￾set sizes on heterophilic graphs, whereas signed HEAD-CP circumvents the failure. The post-hoc oracle attains the row minimum on 8 of 10 datasets.: On the remaining two homophilic datasets, … view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

22 extracted references · 6 linked inside Pith

  1. [1]

    Classification with valid and adaptive coverage,

    Y . Romano, M. Sesia, and E. Candes, “Classification with valid and adaptive coverage,”Advances in neural information processing systems, vol. 33, pp. 3581–3591, 2020

    2020

  2. [2]

    Least ambiguous set-valued classifiers with bounded error levels,

    M. Sadinle, J. Lei, and L. Wasserman, “Least ambiguous set-valued classifiers with bounded error levels,”Journal of the American Statistical Association, vol. 114, no. 525, pp. 223–234, 2019

    2019

  3. [3]

    Conformal prediction: A gentle introduction,

    A. N. Angelopoulos and S. Bates, “Conformal prediction: A gentle introduction,”Foundations and Trends in Machine Learning, vol. 16, no. 4, pp. 494–591, 2023

    2023

  4. [4]

    Conformal pre- diction sets for graph neural networks,

    S. H. Zargarbashi, S. Antonelli, and A. Bojchevski, “Conformal pre- diction sets for graph neural networks,” inInternational Conference on Machine Learning. PMLR, 2023, pp. 12 292–12 318

    2023

  5. [5]

    Similarity- navigated conformal prediction for graph neural networks,

    J. Song, J. Huang, W. Jiang, B. Zhang, S. Li, and C. Wang, “Similarity- navigated conformal prediction for graph neural networks,”Advances in Neural Information Processing Systems, vol. 37, pp. 48 541–48 567, 2024

    2024

  6. [6]

    Uncertainty quantifica- tion over graph with conformalized graph neural networks,

    K. Huang, Y . Jin, E. Candes, and J. Leskovec, “Uncertainty quantifica- tion over graph with conformalized graph neural networks,”Advances in Neural Information Processing Systems, vol. 36, pp. 26 699–26 721, 2023

    2023

  7. [7]

    Residual reweighted conformal prediction for graph neural networks,

    Z. Zhang, J. Bao, Z. Zhou, N. Colombo, L. Cheng, and R. Luo, “Residual reweighted conformal prediction for graph neural networks,” arXiv preprint arXiv:2506.07854, 2025

    Pith/arXiv arXiv 2025

  8. [8]

    V ovk, A

    V . V ovk, A. Gammerman, and G. Shafer,Algorithmic learning in a random world. Springer, 2005

    2005

  9. [9]

    Distribution-free predictive inference for regression,

    J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman, “Distribution-free predictive inference for regression,”Journal of the American Statistical Association, vol. 113, no. 523, pp. 1094–1111, 2018

    2018

  10. [10]

    Geom-gcn: Geo- metric graph convolutional networks,

    H. Pei, B. Wei, K. C.-C. Chang, Y . Lei, and B. Yang, “Geom-gcn: Geo- metric graph convolutional networks,”arXiv preprint arXiv:2002.05287, 2020

    Pith/arXiv arXiv 2002

  11. [11]

    Beyond homophily in graph neural networks: Current limitations and effective designs,

    J. Zhu, Y . Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra, “Beyond homophily in graph neural networks: Current limitations and effective designs,”Advances in neural information processing systems, vol. 33, pp. 7793–7804, 2020

    2020

  12. [12]

    Beyond low-frequency infor- mation in graph convolutional networks,

    D. Bo, X. Wang, C. Shi, and H. Shen, “Beyond low-frequency infor- mation in graph convolutional networks,” inProceedings of the AAAI conference on artificial intelligence, vol. 35, no. 5, 2021, pp. 3950–3957

    2021

  13. [13]

    Adaptive universal general- ized pagerank graph neural network,

    E. Chien, J. Peng, P. Li, and O. Milenkovic, “Adaptive universal general- ized pagerank graph neural network,”arXiv preprint arXiv:2006.07988, 2020

    Pith/arXiv arXiv 2006

  14. [14]

    Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods,

    D. Lim, F. Hohne, X. Li, S. L. Huang, V . Gupta, O. Bhalerao, and S. N. Lim, “Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods,”Advances in neural informa- tion processing systems, vol. 34, pp. 20 887–20 902, 2021

    2021

  15. [15]

    Graph posterior network: Bayesian predictive uncertainty for node classification,

    M. Stadler, B. Charpentier, S. Geisler, D. Z ¨ugner, and S. G ¨unnemann, “Graph posterior network: Bayesian predictive uncertainty for node classification,”Advances in Neural Information Processing Systems, vol. 34, pp. 18 033–18 048, 2021

    2021

  16. [16]

    Be confident! towards trust- worthy graph neural networks via confidence calibration,

    X. Wang, H. Liu, C. Shi, and C. Yang, “Be confident! towards trust- worthy graph neural networks via confidence calibration,”Advances in Neural Information Processing Systems, vol. 34, pp. 23 768–23 779, 2021

    2021

  17. [17]

    A critical look at the evaluation of gnns under heterophily: Are we really making progress?

    O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova, “A critical look at the evaluation of gnns under heterophily: Are we really making progress?”arXiv preprint arXiv:2302.11640, 2023

    Pith/arXiv arXiv 2023

  18. [18]

    Semi-supervised classification with graph convolutional networks,

    T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,”arXiv preprint arXiv:1609.02907, 2016

    Pith/arXiv arXiv 2016

  19. [19]

    Graph attention networks,

    P. Veli ˇckovi´c, G. Cucurull, A. Casanova, A. Romero, P. Lio, and Y . Ben- gio, “Graph attention networks,”arXiv preprint arXiv:1710.10903, 2017

    Pith/arXiv arXiv 2017

  20. [20]

    Inductive representation learning on large graphs,

    W. Hamilton, Z. Ying, and J. Leskovec, “Inductive representation learning on large graphs,”Advances in neural information processing systems, vol. 30, 2017

    2017

  21. [21]

    Contextual stochastic block models,

    Y . Deshpande, S. Sen, A. Montanari, and E. Mossel, “Contextual stochastic block models,”Advances in neural information processing systems, vol. 31, 2018

    2018

  22. [22]

    Con- formal prediction under covariate shift,

    R. J. Tibshirani, R. Foygel Barber, E. Candes, and A. Ramdas, “Con- formal prediction under covariate shift,”Advances in neural information processing systems, vol. 32, 2019

    2019