mlsanityData to 14 Oct 2026

SIGMA: An Efficient Heterophilous Graph Neural Network with Fast Global Aggregation

arXiv 2305.09958 ↗First posted 17 May 2023cs.LG cs.SIcited by 10

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) realize great success in graph learning but suffer from performance loss when meeting heterophily, i.e. neighboring nodes are dissimilar, due to their local and uniform aggregation. Existing attempts of heterophilous GNNs incorporate long-range or global aggregations to distinguish nodes in the graph. However, these aggregations usually require iteratively maintaining and updating full-graph information, which limits their efficiency when applying to large-scale graphs. In this paper, we propose SIGMA, an efficient global heterophilous GNN aggregation integrating the structural similarity measurement SimRank. Our theoretical analysis illustrates that SIGMA inherently captures distant global similarity even under heterophily, that conventional approaches can only achieve after iterative aggregations. Furthermore, it enjoys efficient one-time computation with a complexity only linear to the node set size O(n). Comprehensive evaluation demonstrates that SIGMA achieves state-of-the-art performance with superior aggregation and overall efficiency. Notably, it obtains 5× acceleration on the large-scale heterophily dataset pokec with over 30 million edges compared to the best baseline aggregation.

Key facts. Cited by 10 papers in the map (data through 14 Oct 2026). Builds on 31 of its 53 references that are in the map. First posted on arXiv 17 May 2023.

Builds on

31 of 53 references.

References · 31

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2019Simplifying Graph Convolutional Networkscited by 1,477
  5. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  6. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  7. 2020Simple and Deep Graph Convolutional Networkscited by 860
  8. 2020Geom-GCN: Geometric Graph Convolutional Networkscited by 826
  9. 2020Adaptive Universal Generalized PageRank Graph Neural Networkcited by 595
  10. 2019Multi-scale Attributed Node Embeddingcited by 548
  11. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 541
  12. 2019MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixingcited by 443
19 more
  1. 2019Diffusion Improves Graph Learningcited by 414
  2. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 335
  3. 2021Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methodscited by 311
  4. 2022Finding Global Homophily in Graph Neural Networks When Meeting Heterophilycited by 179
  5. 2020Scaling Graph Neural Networks with Approximate PageRankcited by 174
  6. 2019On the Use of ArXiv as a Datasetcited by 103
  7. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  8. 2020Non-Local Graph Neural Networkscited by 91
  9. 2020Scalable Graph Neural Networks via Bidirectional Propagationcited by 87
  10. 2021GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophilycited by 84
  11. 2021Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?cited by 82
  12. 2021Graph Pointer Neural Networkscited by 27
  13. 2022Spiking Graph Convolutional Networkscited by 27
  14. 2021Approximate Graph Propagationcited by 21
  15. 2022SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimizationcited by 19
  16. 2020CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Datacited by 7
  17. 2022GSim: A Graph Neural Network based Relevance Measure for Heterogeneous Graphscited by 2
  18. 2020Exact Single-Source SimRank Computation on Large Graphscited by 1
  19. 2023Massively Parallel Single-Source SimRanks in o(log n) Roundscited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 2; 2026: 2.

10 papers.

  1. 2024Position: Graph Foundation Models are Already Herecited by 86
  2. 2023Revisiting Link Prediction: A Data Perspectivecited by 29
  3. 2024LLM as Prompter: Low-resource Inductive Reasoning on Arbitrary Knowledge Graphscited by 13
  4. 2024A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectivenesscited by 6
  5. 2024Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphscited by 6
  6. 2025MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Expertscited by 3
  7. 2024Unifews: You Need Fewer Operations for Efficient Graph Neural Networkscited by 2
  8. 2026LION: A Clifford Neural Paradigm for Multimodal-Attributed Graph Learningcited by 2
  9. 2025When Deepfake Detection Meets Graph Neural Network:a Unified and Lightweight Learning Frameworkcited by 1
  10. 2026LION: A Clifford Neural Paradigm for Multimodal-Attributed Graph Learningcited by 0