Abstract
Graph Neural Networks (GNNs) typically rely on the homophily assumption, where connected nodes share similar features or labels. While signed GNNs attempt to accommodate heterophily by assigning negative weights to edges between dissimilar nodes, they often suffer from edge uncertainty. This paper demonstrates that incorrect sign flipping can be more detrimental than edge pruning. We propose an adaptive Edge Weight Calibration framework that utilizes an EM-style algorithm to estimate local homophily and edge error ratios, allowing the model to "block" uncertain edges. Our approach consistently improves performance and feature separability across diverse homophilic and heterophilic graph benchmarks.
1. Introduction
The success of GNNs is largely attributed to message passing, which aggregates information from neighboring nodes. In homophilic graphs, this process smooths features within the same class. However, in heterophilic graphs—where neighbors often belong to different classes—standard message passing can lead to over-smoothing and performance degradation.
Signed propagation methods address this by flipping the sign of edges predicted to be heterophilic. Yet, this introduces a critical vulnerability: edge uncertainty. If a model misclassifies a homophilic edge as heterophilic (or vice versa), the resulting signed propagation introduces significant noise. This research proves that under high uncertainty, "less is more"—it is often better to block an edge (set its weight to zero) than to propagate information with the wrong sign.
2. Methodology: Edge Weight Calibration
The authors propose a framework that dynamically calibrates edge weights during training using an Expectation-Maximization (EM) style approach.
2.1 Parameter Estimation
The model estimates two key latent variables:
- Local Homophily ($b_i$): The probability that node $i$ shares a label with its neighbors.
- Edge Error Ratio ($e_t$): The probability of misclassifying an edge's nature at epoch $t$. A key theoretical contribution (Theorem 11) shows that $e_t$ can be accurately inferred from the model's validation accuracy.
2.2 Optimization and Blocking
Instead of universal signed propagation, the model calculates a "discrimination gap" ($Z_t$). When uncertainty is high ($Z_t < 0$), the model blocks the edge. When confidence is high, it proceeds with signed propagation. This mechanism prevents the propagation of erroneous signals that would otherwise merge distinct class representations.
3. Experimental Results
The calibration framework was applied to state-of-the-art models including GPRGNN, FAGCN, and GGCN across various datasets such as Cora, Actor, and Squirrel.
3.1 Performance Gains
The calibrated models (denoted with a ) showed substantial improvements. For instance, GPRGNN achieved an 8.47% accuracy increase on the Actor dataset and a 6.62% jump on Squirrel compared to the standard GPRGNN baseline.
3.2 Feature Separability
A critical metric for GNN performance is the "inter-class distance," which measures how well the model separates different classes in the embedding space. As shown in the figure below, calibrated models significantly increase this distance, particularly in heterophilic datasets, by preventing classes from merging due to noisy propagation.
4. Discussion and Conclusion
Theoretical analysis using the Contextual Stochastic Block Model confirms that signed propagation increases feature entropy more than blocking when error rates are high. By breaking the graph into more reliable components, the calibration method effectively halts the over-smoothing signal.
While the method introduces some computational overhead due to the additional estimation steps (MLP + EvenNet), the gains in robustness and accuracy across both small and large-scale graphs make it a compelling strategy for handling heterophily in real-world networks.
Summary updated