# Make Heterophily Graphs Better Fit GNN: A Graph Rewiring Approach

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 51 references that are in the map.
- First posted on arXiv 17 Sep 2022.

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

- [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)
- [Dynamic Graph CNN for Learning on Point Clouds](https://mlsanity.com/paper/1801.07829/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (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)
- [On the Bottleneck of Graph Neural Networks and its Practical Implications](https://mlsanity.com/paper/2006.05205/) (2020)
- [GraphSAINT: Graph Sampling Based Inductive Learning Method](https://mlsanity.com/paper/1907.04931/) (2019)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Learning Sparse Neural Networks through L0 Regularization](https://mlsanity.com/paper/1712.01312/) (2017)
- [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)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Learning Discrete Structures for Graph Neural Networks](https://mlsanity.com/paper/1903.11960/) (2019)
- [Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings](https://mlsanity.com/paper/2006.13009/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Adaptive Graph Convolutional Neural Networks](https://mlsanity.com/paper/1801.03226/) (2018)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Bayesian graph convolutional neural networks for semi-supervised classification](https://mlsanity.com/paper/1811.11103/) (2018)
- [Differentiable Graph Module (DGM) for Graph Convolutional Networks](https://mlsanity.com/paper/2002.04999/) (2020)
- [GBK-GNN: Gated Bi-Kernel Graph Neural Networks for Modeling Both Homophily and Heterophily](https://mlsanity.com/paper/2110.15777/) (2021)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [A Survey on Graph Structure Learning: Progress and Opportunities](https://mlsanity.com/paper/2103.03036/) (2021)
- [MotifNet: a motif-based Graph Convolutional Network for directed graphs](https://mlsanity.com/paper/1802.01572/) (2018)
- [TabularNet: A Neural Network Architecture for Understanding Semantic Structures of Tabular Data](https://mlsanity.com/paper/2106.03096/) (2021)
- [CAGNN: Cluster-Aware Graph Neural Networks for Unsupervised Graph Representation Learning](https://mlsanity.com/paper/2009.01674/) (2020)
- [TSSRGCN: Temporal Spectral Spatial Retrieval Graph Convolutional Network for Traffic Flow Forecasting](https://mlsanity.com/paper/2011.14638/) (2020)

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

- [A Survey of Graph Neural Networks in Real world: Imbalance, Noise, Privacy and OOD Challenges](https://mlsanity.com/paper/2403.04468/) (2024)
- [A Comprehensive Survey on Data Augmentation](https://mlsanity.com/paper/2405.09591/) (2024)
- [Beyond Homophily: Reconstructing Structure for Graph-agnostic Clustering](https://mlsanity.com/paper/2305.02931/) (2023)
- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [Homophily-oriented Heterogeneous Graph Rewiring](https://mlsanity.com/paper/2302.06299/) (2023)
- [Node Embedding from Neural Hamiltonian Orbits in Graph Neural Networks](https://mlsanity.com/paper/2305.18965/) (2023)
- [BeMap: Balanced Message Passing for Fair Graph Neural Network](https://mlsanity.com/paper/2306.04107/) (2023)
- [Predicting the Silent Majority on Graphs: Knowledge Transferable Graph Neural Network](https://mlsanity.com/paper/2302.00873/) (2023)
- [Bridged-GNN: Knowledge Bridge Learning for Effective Knowledge Transfer](https://mlsanity.com/paper/2308.09499/) (2023)
- [Cross-Domain Graph Data Scaling: A Showcase with Diffusion Models](https://mlsanity.com/paper/2406.01899/) (2024)
- [Neural Snowflakes: Universal Latent Graph Inference via Trainable Latent Geometries](https://mlsanity.com/paper/2310.15003/) (2023)
- [Diffusion-Jump GNNs: Homophiliation via Learnable Metric Filters](https://mlsanity.com/paper/2306.16976/) (2023)
- [Enhancing the Influence of Labels on Unlabeled Nodes in Graph Convolutional Networks](https://mlsanity.com/paper/2411.02279/) (2024)
- [Graph Domain Adaptation via Homophily-Agnostic Reconstructing Structure](https://mlsanity.com/paper/2602.07573/) (2026)
- [A Comparative Study of Population-Graph Construction Methods and Graph Neural Networks for Brain Age Regression](https://mlsanity.com/paper/2309.14816/) (2023)
- [CAT: A Causally Graph Attention Network for Trimming Heterophilic Graph](https://mlsanity.com/paper/2312.08672/) (2023)
- [Task-driven Heterophilic Graph Structure Learning](https://mlsanity.com/paper/2512.23406/) (2025)
- [Revisiting Generalized p-Laplacian Regularized Framelet GCNs: Convergence, Energy Dynamic and Training with Non-Linear Diffusion](https://mlsanity.com/paper/2305.15639/) (2023)
- [Professional Network Matters: Connections Empower Person-Job Fit](https://mlsanity.com/paper/2401.00010/) (2023)
- [Posterior Label Smoothing for Node Classification](https://mlsanity.com/paper/2406.00410/) (2024)
- [Gumbel-MPNN: Graph Rewiring with Gumbel-Softmax](https://mlsanity.com/paper/2508.17531/) (2025)
- [Beyond Observed Auxiliary Relations: Environment-Conditioned Modeling for Multi-Behavior Recommendation](https://mlsanity.com/paper/2608.22920/) (2026)
- [Learning the Graph and the Embedding Together: Classifier-Independent Rewiring for Heterophilic Node Classification](https://mlsanity.com/paper/2609.32613/) (2026)

## Abstract (arXiv)

Graph Neural Networks (GNNs) are popular machine learning methods for modeling graph data. A lot of GNNs perform well on homophily graphs while having unsatisfactory performance on heterophily graphs. Recently, some researchers turn their attention to designing GNNs for heterophily graphs by adjusting the message passing mechanism or enlarging the receptive field of the message passing. Different from existing works that mitigate the issues of heterophily from model design perspective, we propose to study heterophily graphs from an orthogonal perspective by rewiring the graph structure to reduce heterophily and making the traditional GNNs perform better. Through comprehensive empirical studies and analysis, we verify the potential of the rewiring methods. To fully exploit its potential, we propose a method named Deep Heterophily Graph Rewiring (DHGR) to rewire graphs by adding homophilic edges and pruning heterophilic edges. The detailed way of rewiring is determined by comparing the similarity of label/feature-distribution of node neighbors. Besides, we design a scalable implementation for DHGR to guarantee high efficiency. DHRG can be easily used as a plug-in module, i.e., a graph pre-processing step, for any GNNs, including both GNN for homophily and heterophily, to boost their performance on the node classification task. To the best of our knowledge, it is the first work studying graph rewiring for heterophily graphs. Extensive experiments on 11 public graph datasets demonstrate the superiority of our proposed methods.