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

2023/02/03 by Yunchong Song, Song, Yunchong, Chenghu Zhou +5 · 24 citations
Computer Science · Materials Science · #Advanced Graph Neural Networks #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning in Materials Science #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.2302.01524

openalex publication_date 2023/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• Interpretable and Adaptive Node Classification on Heterophilic Graphs via Combinatorial Scoring and Hybrid Learning
• ATLAS: Adaptive Topology-based Learning at Scale for Homophilic and Heterophilic Graphs
• Layered Division and Global Allocation for Community Detection in Multilayer Network
• GCL-OT: Graph Contrastive Learning with Optimal Transport for Heterophilic Text-Attributed Graphs
• Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily
• GraphTARIF: Linear Graph Transformer with Augmented Rank and Improved Focus
• Bridging Computational Social Science and Deep Learning: Cultural Dissemination-Inspired Graph Neural Networks
• Graph Homophily Booster: Rethinking the Role of Discrete Features on Heterophilic Graphs
• Flow Matters: Directional and Expressive GNNs for Heterophilic Graphs
• Wavy Transformer
• GraphTorque: Torque-Driven Rewiring Graph Neural Network
• Exploring Adaptive Structure Learning for Heterophilic Graphs
• Towards a deeper GCN: Alleviate over-smoothing with iterative training and fine-tuning
• Geometric deep learning assists protein engineering. Opportunities and Challenges
• How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?
• The Oversmoothing Fallacy: A Misguided Narrative in GNN Research
• Directed Homophily-Aware Graph Neural Network
• Graph Wave Networks
• Language Models as Messengers: Enhancing Message Passing in Heterophilic Graph Learning
• Partition-wise Graph Filtering: A Unified Perspective Through the Lens of Graph Coarsening
• It Takes a Graph to Know a Graph: Rewiring for Homophily with a Reference Graph
• Wide & Deep Learning for Node Classification
• A Generative Graph Contrastive Learning Model with Global Signal
• Simplifying Graph Convolutional Networks with Redundancy-Free Neighbors

Related

• Mitigating Oversmoothing Through Reverse Process of GNNs for Heterophilic Graphs
• Sign is Not a Remedy: Multiset-to-Multiset Message Passing for Learning on Heterophilic Graphs
• Heterophily-informed Message Passing
• PathMLP: Smooth Path Towards High-order Homophily
• Better Not to Propagate: Understanding Edge Uncertainty and Over-smoothing in Signed Graph Neural Networks