# Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing

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

## Key facts

- Cited by 67 papers in the map (data through 14 Oct 2026).
- Builds on 52 of its 63 references that are in the map.
- First posted on arXiv 3 Feb 2023.

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

- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [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)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering](https://mlsanity.com/paper/1606.09375/) (2016)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Spectral Networks and Locally Connected Networks on Graphs](https://mlsanity.com/paper/1312.6203/) (2013)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [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)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Gated Graph Sequence Neural Networks](https://mlsanity.com/paper/1511.05493/) (2015)
- [DropEdge: Towards Deep Graph Convolutional Networks on Node Classification](https://mlsanity.com/paper/1907.10903/) (2019)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (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)
- [Measuring and Relieving the Over-smoothing Problem for Graph Neural Networks from the Topological View](https://mlsanity.com/paper/1909.03211/) (2019)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)

## Built on by (most cited first, 30 of 67)

- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [Classic GNNs are Strong Baselines: Reassessing GNNs for Node Classification](https://mlsanity.com/paper/2406.08993/) (2024)
- [Polynormer: Polynomial-Expressive Graph Transformer in Linear Time](https://mlsanity.com/paper/2403.01232/) (2024)
- [Graph Machine Learning in the Era of Large Language Models (LLMs)](https://mlsanity.com/paper/2404.14928/) (2024)
- [AdaFGL: A New Paradigm for Federated Node Classification with Topology Heterogeneity](https://mlsanity.com/paper/2401.11750/) (2024)
- [How Universal Polynomial Bases Enhance Spectral Graph Neural Networks: Heterophily, Over-smoothing, and Over-squashing](https://mlsanity.com/paper/2405.12474/) (2024)
- [Breaking the Entanglement of Homophily and Heterophily in Semi-supervised Node Classification](https://mlsanity.com/paper/2312.04111/) (2023)
- [Beyond Message Passing: Neural Graph Pattern Machine](https://mlsanity.com/paper/2501.18739/) (2025)
- [Feature Transportation Improves Graph Neural Networks](https://mlsanity.com/paper/2307.16092/) (2023)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [Mitigating Oversmoothing Through Reverse Process of GNNs for Heterophilic Graphs](https://mlsanity.com/paper/2403.10543/) (2024)
- [Exploring the Potential of Large Language Models for Heterophilic Graphs](https://mlsanity.com/paper/2408.14134/) (2024)
- [Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs](https://mlsanity.com/paper/2405.20652/) (2024)
- [Graph Neural Networks Do Not Always Oversmooth](https://mlsanity.com/paper/2406.02269/) (2024)
- [From Cluster Assumption to Graph Convolution: Graph-based Semi-Supervised Learning Revisited](https://mlsanity.com/paper/2309.13599/) (2023)
- [Best of Both Worlds: Advantages of Hybrid Graph Sequence Models](https://mlsanity.com/paper/2411.15671/) (2024)
- [Revisiting the Message Passing in Heterophilous Graph Neural Networks](https://mlsanity.com/paper/2405.17768/) (2024)
- [HeTGB: A Comprehensive Benchmark for Heterophilic Text-Attributed Graphs](https://mlsanity.com/paper/2503.04822/) (2025)
- [Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily](https://mlsanity.com/paper/2511.06608/) (2025)
- [Diffusion-Jump GNNs: Homophiliation via Learnable Metric Filters](https://mlsanity.com/paper/2306.16976/) (2023)
- [DepWiGNN: A Depth-wise Graph Neural Network for Multi-hop Spatial Reasoning in Text](https://mlsanity.com/paper/2310.12557/) (2023)
- [DGNN: Decoupled Graph Neural Networks with Structural Consistency between Attribute and Graph Embedding Representations](https://mlsanity.com/paper/2401.15584/) (2024)
- [Taming Gradient Oversmoothing and Expansion in Graph Neural Networks](https://mlsanity.com/paper/2410.04824/) (2024)
- [GRAIN: Multi-Granular and Implicit Information Aggregation Graph Neural Network for Heterophilous Graphs](https://mlsanity.com/paper/2504.06649/) (2025)
- [The Oversmoothing Fallacy: A Misguided Narrative in GNN Research](https://mlsanity.com/paper/2506.04653/) (2025)
- [CAT: A Causally Graph Attention Network for Trimming Heterophilic Graph](https://mlsanity.com/paper/2312.08672/) (2023)
- [Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness-Generalization Perspective](https://mlsanity.com/paper/2412.09805/) (2024)
- [A Signed Graph Approach to Understanding and Mitigating Oversmoothing in GNNs](https://mlsanity.com/paper/2502.11394/) (2025)
- [Ordered Topological Deep Learning: a Network Modeling Case Study](https://mlsanity.com/paper/2503.16746/) (2025)
- [Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening](https://mlsanity.com/paper/2505.14033/) (2025)

## Abstract (arXiv)

Most graph neural networks follow the message passing mechanism. However, it faces the over-smoothing problem when multiple times of message passing is applied to a graph, causing indistinguishable node representations and prevents the model to effectively learn dependencies between farther-away nodes. On the other hand, features of neighboring nodes with different labels are likely to be falsely mixed, resulting in the heterophily problem. In this work, we propose to order the messages passing into the node representation, with specific blocks of neurons targeted for message passing within specific hops. This is achieved by aligning the hierarchy of the rooted-tree of a central node with the ordered neurons in its node representation. Experimental results on an extensive set of datasets show that our model can simultaneously achieve the state-of-the-art in both homophily and heterophily settings, without any targeted design. Moreover, its performance maintains pretty well while the model becomes really deep, effectively preventing the over-smoothing problem. Finally, visualizing the gating vectors shows that our model learns to behave differently between homophily and heterophily settings, providing an explainable graph neural model.