Uncertainty-Aware Adaptive Edge Blocking in Heterophilic Graph Neural Networks
TL;DR
This work provides 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.
Abstract
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.