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

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

## 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 (most cited first, 30 of 31)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [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)
- [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)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networks](https://mlsanity.com/paper/1905.07953/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [On the Use of ArXiv as a Dataset](https://mlsanity.com/paper/1905.00075/) (2019)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Non-Local Graph Neural Networks](https://mlsanity.com/paper/2005.14612/) (2020)
- [Scalable Graph Neural Networks via Bidirectional Propagation](https://mlsanity.com/paper/2010.15421/) (2020)
- [GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily](https://mlsanity.com/paper/2110.15777/) (2021)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Graph Pointer Neural Networks](https://mlsanity.com/paper/2110.00973/) (2021)
- [Spiking Graph Convolutional Networks](https://mlsanity.com/paper/2205.02767/) (2022)
- [Approximate Graph Propagation](https://mlsanity.com/paper/2106.03058/) (2021)
- [SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization](https://mlsanity.com/paper/2207.09179/) (2022)
- [CAST: A Correlation-based Adaptive Spectral Clustering Algorithm on Multi-scale Data](https://mlsanity.com/paper/2006.04435/) (2020)
- [GSim: A Graph Neural Network based Relevance Measure for Heterogeneous Graphs](https://mlsanity.com/paper/2208.06144/) (2022)
- [Exact Single-Source SimRank Computation on Large Graphs](https://mlsanity.com/paper/2004.03493/) (2020)

## Built on by (most cited first, 10 of 10)

- [Position: Graph Foundation Models are Already Here](https://mlsanity.com/paper/2402.02216/) (2024)
- [Revisiting Link Prediction: A Data Perspective](https://mlsanity.com/paper/2310.00793/) (2023)
- [LLM as Prompter: Low-resource Inductive Reasoning on Arbitrary Knowledge Graphs](https://mlsanity.com/paper/2402.11804/) (2024)
- [A Comprehensive Benchmark on Spectral GNNs: The Impact on Efficiency, Memory, and Effectiveness](https://mlsanity.com/paper/2406.09675/) (2024)
- [Towards Graph Foundation Models: Training on Knowledge Graphs Enables Transferability to General Graphs](https://mlsanity.com/paper/2410.12609/) (2024)
- [MoSE: Unveiling Structural Patterns in Graphs via Mixture of Subgraph Experts](https://mlsanity.com/paper/2509.09337/) (2025)
- [Unifews: You Need Fewer Operations for Efficient Graph Neural Networks](https://mlsanity.com/paper/2403.13268/) (2024)
- [LION: A Clifford Neural Paradigm for Multimodal-Attributed Graph Learning](https://mlsanity.com/paper/2608.24795/) (2026)
- [When Deepfake Detection Meets Graph Neural Network:a Unified and Lightweight Learning Framework](https://mlsanity.com/paper/2508.05526/) (2025)
- [LION: A Clifford Neural Paradigm for Multimodal-Attributed Graph Learning](https://mlsanity.com/paper/2601.21453/) (2026)

## 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.