# GPatcher: A Simple and Adaptive MLP Model for Alleviating Graph Heterophily

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 42 references that are in the map.
- First posted on arXiv 25 Jun 2023.

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

- [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)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [LINE: Large-scale Information Network Embedding](https://mlsanity.com/paper/1503.03578/) (2015)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [A Survey of Transformers](https://mlsanity.com/paper/2106.04554/) (2021)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Multi-Label Image Recognition with Graph Convolutional Networks](https://mlsanity.com/paper/1904.03582/) (2019)
- [Revisiting Graph Neural Networks: All We Have is Low-Pass Filters](https://mlsanity.com/paper/1905.09550/) (2019)
- [Semantic Graph Convolutional Networks for 3D Human Pose Regression](https://mlsanity.com/paper/1904.03345/) (2019)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [A Semi-supervised Graph Attentive Network for Financial Fraud Detection](https://mlsanity.com/paper/2003.01171/) (2020)
- [Do We Really Need Complicated Model Architectures For Temporal Networks?](https://mlsanity.com/paper/2302.11636/) (2023)
- [A Survey of Visual Transformers](https://mlsanity.com/paper/2111.06091/) (2021)
- [A Generalization of ViT/MLP-Mixer to Graphs](https://mlsanity.com/paper/2212.13350/) (2022)
- [Beyond Smoothing: Unsupervised Graph Representation Learning with Edge Heterophily Discriminating](https://mlsanity.com/paper/2211.14065/) (2022)
- [SkipGNN: Predicting Molecular Interactions with Skip-Graph Networks](https://mlsanity.com/paper/2004.14949/) (2020)
- [Block Modeling-Guided Graph Convolutional Neural Networks](https://mlsanity.com/paper/2112.13507/) (2021)
- [HL-Net: Heterophily Learning Network for Scene Graph Generation](https://mlsanity.com/paper/2205.01316/) (2022)
- [Beyond Low-Pass Filters: Adaptive Feature Propagation on Graphs](https://mlsanity.com/paper/2103.14187/) (2021)
- [Using Fuzzy Logic to Leverage HTML Markup for Web Page Representation](https://mlsanity.com/paper/1606.04429/) (2016)

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

- [VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections](https://mlsanity.com/paper/2403.16030/) (2024)
- [Graph Tokenization for Bridging Graphs and Transformers](https://mlsanity.com/paper/2603.11099/) (2026)
- [Handling Feature Heterogeneity with Learnable Graph Patches](https://mlsanity.com/paper/2606.17667/) (2026)

## Abstract (arXiv)

While graph heterophily has been extensively studied in recent years, a fundamental research question largely remains nascent: How and to what extent will graph heterophily affect the prediction performance of graph neural networks (GNNs)? In this paper, we aim to demystify the impact of graph heterophily on GNN spectral filters. Our theoretical results show that it is essential to design adaptive polynomial filters that adapts different degrees of graph heterophily to guarantee the generalization performance of GNNs. Inspired by our theoretical findings, we propose a simple yet powerful GNN named GPatcher by leveraging the MLP-Mixer architectures. Our approach comprises two main components: (1) an adaptive patch extractor function that automatically transforms each node's non-Euclidean graph representations to Euclidean patch representations given different degrees of heterophily, and (2) an efficient patch mixer function that learns salient node representation from both the local context information and the global positional information. Through extensive experiments, the GPatcher model demonstrates outstanding performance on node classification compared with popular homophily GNNs and state-of-the-art heterophily GNNs.