# Better Not to Propagate: Understanding Edge Uncertainty and Over-smoothing in Signed Graph Neural Networks

arXiv: https://arxiv.org/abs/2408.04895 · HTML: https://mlsanity.com/paper/2408.04895/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 30 of its 46 references that are in the map.
- First posted on arXiv 9 Aug 2024.

## Builds on (most cited first, 30 of 30)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Representation Learning on Graphs with Jumping Knowledge Networks](https://mlsanity.com/paper/1806.03536/) (2018)
- [Simple and Deep Graph Convolutional Networks](https://mlsanity.com/paper/2007.02133/) (2020)
- [How Attentive are Graph Attention Networks?](https://mlsanity.com/paper/2105.14491/) (2021)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Learning to Drop: Robust Graph Neural Network via Topological Denoising](https://mlsanity.com/paper/2011.07057/) (2020)
- [Specformer: Spectral Graph Neural Networks Meet Transformers](https://mlsanity.com/paper/2303.01028/) (2023)
- [GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily](https://mlsanity.com/paper/2110.15777/) (2021)
- [Graph-MLP: Node Classification without Message Passing in Graph](https://mlsanity.com/paper/2106.04051/) (2021)
- [Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization](https://mlsanity.com/paper/2102.06966/) (2021)
- [Signed Graph Attention Networks](https://mlsanity.com/paper/1906.10958/) (2019)
- [GEMSEC: Graph Embedding with Self Clustering](https://mlsanity.com/paper/1802.03997/) (2018)
- [Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyond](https://mlsanity.com/paper/2209.06177/) (2022)
- [Rethinking Graph Regularization for Graph Neural Networks](https://mlsanity.com/paper/2009.02027/) (2020)
- [Towards Deep Attention in Graph Neural Networks: Problems and Remedies](https://mlsanity.com/paper/2306.02376/) (2023)
- [Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs](https://mlsanity.com/paper/2302.12357/) (2023)
- [LSGNN: Towards General Graph Neural Network in Node Classification by Local Similarity](https://mlsanity.com/paper/2305.04225/) (2023)
- [SimCalib: Graph Neural Network Calibration based on Similarity between Nodes](https://mlsanity.com/paper/2312.11858/) (2023)
- [Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classification](https://mlsanity.com/paper/2302.09755/) (2023)
- [Representation Learning on Heterophilic Graph with Directional Neighborhood Attention](https://mlsanity.com/paper/2403.01475/) (2024)
- [Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks](https://mlsanity.com/paper/2312.16418/) (2023)

## Abstract (arXiv)

Traditional Graph Neural Networks (GNNs) rely on network homophily, which can lead to performance degradation due to over-smoothing in many real-world heterophily scenarios. Recent studies analyze the smoothing effect (separability) after message-passing (MP), depending on the expectation of node features. Regarding separability gain, they provided theoretical backgrounds on over-smoothing caused by various propagation schemes, including positive, signed, and blocked MPs. More recently, by extending these theorems, some works have suggested improvements in signed propagation under multiple classes. However, prior works assume that the error ratio of all propagation schemes is fixed, failing to investigate this phenomenon correctly. To solve this problem, we propose a novel method for estimating homophily and edge error ratio, integrated with dynamic selection between blocked and signed propagation during training. Our theoretical analysis, supported by extensive experiments, demonstrates that blocking MP can be more effective than signed propagation under high edge error ratios, improving the performance in both homophilic and heterophilic graphs.