HeAD-CP is proposed, a family of node-wise diffusion variants whose coefficients are determined by a label-free local-homophily estimate derived from the GNN softmax, which are most effective at extreme heterophily, intermediate heterophily, and moderate-to-high homophily, respectively, and all preserve the marginal coverage guarantee.
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.
Hypergraph representation learning has gained immense popularity over the last few years due to its applications in real-world domains like social network analysis, recommendation systems, biological network modeling, and knowledge graphs. However, hypergraph neural networks (HGNNs) lack rigorous uncertainty estimates, which limits their deployment in critical applications where the reliability of predictions is crucial. To bridge this gap, we propose Contrastive Conformal HGNN (CCF-HGNN) that accounts for uncertainty in hypergraph-based models by explicitly regularizing on the hypergraph structure for guaranteed and robust uncertainty estimates. CCF-HGNN accounts for epistemic uncertainty in HGNN predictions by producing a prediction set that leverages the topological structure and provably contains the true label with a pre-defined coverage probability. It also accounts for aleatoric uncertainty by leveraging contrastive learning on the structure of the hypergraph. To enhance the power of the predictions, CCF-HGNN performs an additional auxiliary task of hyperedge degree prediction with an end-to-end differentiable sampling-based approach. Extensive experiments on real-world hypergraph datasets demonstrate the superiority of CCF-HGNN by improving the efficiency of prediction sets while maintaining valid coverage.
Akash Choudhuri, Bijaya Adhikari· Proceedings of the 32nd ACM...· 0 citations
Experiments show that replacing PageRank with alternative centralities yields similar F1-scores while offering notable runtime savings, and that GraphHD-Order remains competitive with the original GraphHD baseline while providing consistent speedups in encoding time.
This work proposes a self-expressive solver that captures the complementary homophily between meta-paths and node features to obtain ho-mophilous representations and designs separate path encoders to model diverse interactions, thus explicitly including cross-type interactions while mitigating noise via adaptive fusion.
Minda Chen, Yujie Mo, Junkai Huang et al.· 0 citations
Graph Neural Networks (GNNs) deliver strong performance through message passing (MP), yet they can become fragile when graphs contain many heterophilic links or when edge types are predicted incorrectly. Earlier analyses suggest that signed message propagation can reduce over-smoothing when the edge misclassification rate is low. However, many such analyses condition on accurately identified edge types and blur the distinction between neighbor propagation and self-retention. This work re-examines these assumptions and shows that under high uncertainty in edge labels, message passing can reduce node distinguishability even when signed edge weights are applied. The central insight is that uncertain edges should not always be propagated: it can be preferable to adaptively block a message when the estimated edge-type error outweighs the expected gain from signed propagation. Concretely, we analyze neighbor propagation without treating self-loops as edge-type observations, use a row-normalized operator for the neighbor process, and estimate two latent reliability factors during training: the local homophily and the edge classification error rate. To avoid leakage between reliability estimation and model selection, the edge error rate is estimated from a separate calibration split or from a train-only proxy, while validation labels are reserved for hyperparameter and checkpoint selection. We provide theoretical guarantees for the selective blocking rule by deriving the signed-versus-blocked decision boundary, separating signed-matrix effects from nonnegative block-operator spectral arguments, and showing when adaptive blocking preserves class-dependent components. Experiments on homophilic, heterophilic, and large-scale graphs show that the proposed strategy consistently improves signed GNN backbones and remains competitive with strong heterophily-oriented baselines. Compared with the UAI 2025 conference version [11], this journal version adds an extension analysis, tightened derivations, a leakage-free calibration protocol, and expanded empirical results.
Jiho Choi, Yumin Lee, Chanran Kim et al.· ACM Transactions on Intellig...· 0 citations