mlsanityData to 7 Oct 2026

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

arXiv 2408.04895 ↗First posted 9 Aug 2024cs.LG cs.AIcited by 0

Not on the map. Why?

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.

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

Builds on

30 of 46 references.

References · 30

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  4. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 987
  5. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  6. 2020Simple and Deep Graph Convolutional Networkscited by 857
  7. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 821
  8. 2021How Attentive are Graph Attention Networks?cited by 818
  9. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 592
  10. 2021Beyond Low-frequency Information in Graph Convolutional Networkscited by 361
  11. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 309
  12. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
18 more
  1. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  2. 2018Contextual Stochastic Block Modelscited by 134
  3. 2020Learning to Drop: Robust Graph Neural Network via Topological Denoisingcited by 127
  4. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  5. 2021GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophilycited by 84
  6. 2021Graph-MLP: Node Classification without Message Passing in Graphcited by 73
  7. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  8. 2019Signed Graph Attention Networkscited by 62
  9. 2018GEMSEC: Graph Embedding with Self Clusteringcited by 61
  10. 2022Characterizing Graph Datasets for Node Classification: Homophily-Heterophily Dichotomy and Beyondcited by 60
  11. 2020Rethinking Graph Regularization for Graph Neural Networkscited by 36
  12. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  13. 2023Auto-HeG: Automated Graph Neural Network on Heterophilic Graphscited by 23
  14. 2023LSGNN: Towards General Graph Neural Network in Node Classification by Local Similaritycited by 15
  15. 2023SimCalib: Graph Neural Network Calibration based on Similarity between Nodescited by 10
  16. 2023Finding Heterophilic Neighbors via Confidence-based Subgraph Matching for Semi-supervised Node Classificationcited by 7
  17. 2024Representation Learning on Heterophilic Graph with Directional Neighborhood Attentioncited by 6
  18. 2023Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networkscited by 4

Built on by

Not cited yet.