# MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing

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

## Key facts

- Cited by 443 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Apr 2019.

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

- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [A Survey on Deep Semi-supervised Learning](https://mlsanity.com/paper/2103.00550/) (2021)
- [Language is All a Graph Needs](https://mlsanity.com/paper/2308.07134/) (2023)
- [Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs](https://mlsanity.com/paper/2202.04579/) (2022)
- [NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification](https://mlsanity.com/paper/2306.08385/) (2023)
- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Finding Global Homophily in Graph Neural Networks When Meeting Heterophily](https://mlsanity.com/paper/2205.07308/) (2022)
- [Are we really making much progress? Revisiting, benchmarking, and refining heterogeneous graph neural networks](https://mlsanity.com/paper/2112.14936/) (2021)
- [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)
- [On Over-Squashing in Message Passing Neural Networks: The Impact of Width, Depth, and Topology](https://mlsanity.com/paper/2302.02941/) (2023)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Interpreting and Unifying Graph Neural Networks with An Optimization Framework](https://mlsanity.com/paper/2101.11859/) (2021)
- [Decoupled Dynamic Spatial-Temporal Graph Neural Network for Traffic Forecasting](https://mlsanity.com/paper/2206.09112/) (2022)
- [Pre-training Enhanced Spatial-temporal Graph Neural Network for Multivariate Time Series Forecasting](https://mlsanity.com/paper/2206.09113/) (2022)
- [How to Find Your Friendly Neighborhood: Graph Attention Design with Self-Supervision](https://mlsanity.com/paper/2204.04879/) (2022)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Decoupling the Depth and Scope of Graph Neural Networks](https://mlsanity.com/paper/2201.07858/) (2022)
- [How Powerful are K-hop Message Passing Graph Neural Networks](https://mlsanity.com/paper/2205.13328/) (2022)
- [Edge Directionality Improves Learning on Heterophilic Graphs](https://mlsanity.com/paper/2305.10498/) (2023)
- [Shift-Robust GNNs: Overcoming the Limitations of Localized Graph Training Data](https://mlsanity.com/paper/2108.01099/) (2021)
- [Graph Mamba: Towards Learning on Graphs with State Space Models](https://mlsanity.com/paper/2402.08678/) (2024)
- [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)
- [DRew: Dynamically Rewired Message Passing with Delay](https://mlsanity.com/paper/2305.08018/) (2023)
- [New Benchmarks for Learning on Non-Homophilous Graphs](https://mlsanity.com/paper/2104.01404/) (2021)
- [Graph Representation Learning in Biomedicine](https://mlsanity.com/paper/2104.04883/) (2021)
- [Graph-based Semi-supervised Learning: A Comprehensive Review](https://mlsanity.com/paper/2102.13303/) (2021)

## Abstract (arXiv)

Existing popular methods for semi-supervised learning with Graph Neural Networks (such as the Graph Convolutional Network) provably cannot learn a general class of neighborhood mixing relationships. To address this weakness, we propose a new model, MixHop, that can learn these relationships, including difference operators, by repeatedly mixing feature representations of neighbors at various distances. Mixhop requires no additional memory or computational complexity, and outperforms on challenging baselines. In addition, we propose sparsity regularization that allows us to visualize how the network prioritizes neighborhood information across different graph datasets. Our analysis of the learned architectures reveals that neighborhood mixing varies per datasets.