# Auto-HeG: Automated Graph Neural Network on Heterophilic Graphs

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- Builds on 44 of its 58 references that are in the map.
- First posted on arXiv 23 Feb 2023.

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

- [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)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [DARTS: Differentiable Architecture Search](https://mlsanity.com/paper/1806.09055/) (2018)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (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)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Connecting the Dots: Multivariate Time Series Forecasting with Graph Neural Networks](https://mlsanity.com/paper/2005.11650/) (2020)
- [DeepGCNs: Can GCNs Go as Deep as CNNs?](https://mlsanity.com/paper/1904.03751/) (2019)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [Composition-based Multi-Relational Graph Convolutional Networks](https://mlsanity.com/paper/1911.03082/) (2019)
- [Beyond Low-frequency Information in Graph Convolutional Networks](https://mlsanity.com/paper/2101.00797/) (2021)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [SNAS: Stochastic Neural Architecture Search](https://mlsanity.com/paper/1812.09926/) (2018)
- [Searching for A Robust Neural Architecture in Four GPU Hours](https://mlsanity.com/paper/1910.04465/) (2019)
- [Progressive Differentiable Architecture Search: Bridging the Depth Gap between Search and Evaluation](https://mlsanity.com/paper/1904.12760/) (2019)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [Design Space for Graph Neural Networks](https://mlsanity.com/paper/2011.08843/) (2020)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Learning Disentangled Representations for Recommendation](https://mlsanity.com/paper/1910.14238/) (2019)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [Rethinking Architecture Selection in Differentiable NAS](https://mlsanity.com/paper/2108.04392/) (2021)
- [Trustworthy Graph Neural Networks: Aspects, Methods and Trends](https://mlsanity.com/paper/2205.07424/) (2022)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)

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

- [A Survey on Graph Neural Networks for Time Series: Forecasting, Classification, Imputation, and Anomaly Detection](https://mlsanity.com/paper/2307.03759/) (2023)
- [Structure-free Graph Condensation: From Large-scale Graphs to Condensed Graph-free Data](https://mlsanity.com/paper/2306.02664/) (2023)
- [Towards Self-Interpretable Graph-Level Anomaly Detection](https://mlsanity.com/paper/2310.16520/) (2023)
- [Learning Strong Graph Neural Networks with Weak Information](https://mlsanity.com/paper/2305.18457/) (2023)
- [Finding the Missing-half: Graph Complementary Learning for Homophily-prone and Heterophily-prone Graphs](https://mlsanity.com/paper/2306.07608/) (2023)
- [GNNEvaluator: Evaluating GNN Performance On Unseen Graphs Without Labels](https://mlsanity.com/paper/2310.14586/) (2023)
- [Uncertainty-Aware Graph Neural Networks: A Multi-Hop Evidence Fusion Approach](https://mlsanity.com/paper/2506.13083/) (2025)
- [A Survey on Learning from Graphs with Heterophily: Recent Advances and Future Directions](https://mlsanity.com/paper/2401.09769/) (2024)
- [Online GNN Evaluation Under Test-time Graph Distribution Shifts](https://mlsanity.com/paper/2403.09953/) (2024)
- [Two Trades is not Baffled: Condensing Graph via Crafting Rational Gradient Matching](https://mlsanity.com/paper/2402.04924/) (2024)
- [Optimizing Polynomial Graph Filters: A Novel Adaptive Krylov Subspace Approach](https://mlsanity.com/paper/2403.07954/) (2024)
- [Beyond Fixed Depth: Adaptive Graph Neural Networks for Node Classification Under Varying Homophily](https://mlsanity.com/paper/2511.06608/) (2025)
- [LLM4GNAS: A Large Language Model Based Toolkit for Graph Neural Architecture Search](https://mlsanity.com/paper/2502.10459/) (2025)
- [CAT: A Causally Graph Attention Network for Trimming Heterophilic Graph](https://mlsanity.com/paper/2312.08672/) (2023)
- [Sheaf Graph Neural Networks via PAC-Bayes Spectral Optimization](https://mlsanity.com/paper/2508.00357/) (2025)
- [Graph Neural Architecture Search with GPT-4](https://mlsanity.com/paper/2310.01436/) (2023)
- [Hierarchical Uncertainty-Aware Graph Neural Network](https://mlsanity.com/paper/2504.19820/) (2025)
- [ABG-NAS: Adaptive Bayesian Genetic Neural Architecture Search for Graph Representation Learning](https://mlsanity.com/paper/2504.21254/) (2025)
- [Gauge-Equivariant Graph Networks via Self-Interference Cancellation](https://mlsanity.com/paper/2511.16062/) (2025)
- [Explainable Graph Neural Architecture Search via Monte-Carlo Tree Search (Full version)](https://mlsanity.com/paper/2308.15734/) (2023)
- [Better Not to Propagate: Understanding Edge Uncertainty and Over-smoothing in Signed Graph Neural Networks](https://mlsanity.com/paper/2408.04895/) (2024)
- [Persistent Tri-State Message Passing](https://mlsanity.com/paper/2601.01207/) (2026)
- [AutoHGNN: Robust and Efficient Neural Architecture Search for Hypergraph Neural Networks](https://mlsanity.com/paper/2609.33392/) (2026)

## Abstract (arXiv)

Graph neural architecture search (NAS) has gained popularity in automatically designing powerful graph neural networks (GNNs) with relieving human efforts. However, existing graph NAS methods mainly work under the homophily assumption and overlook another important graph property, i.e., heterophily, which exists widely in various real-world applications. To date, automated heterophilic graph learning with NAS is still a research blank to be filled in. Due to the complexity and variety of heterophilic graphs, the critical challenge of heterophilic graph NAS mainly lies in developing the heterophily-specific search space and strategy. Therefore, in this paper, we propose a novel automated graph neural network on heterophilic graphs, namely Auto-HeG, to automatically build heterophilic GNN models with expressive learning abilities. Specifically, Auto-HeG incorporates heterophily into all stages of automatic heterophilic graph learning, including search space design, supernet training, and architecture selection. Through the diverse message-passing scheme with joint micro-level and macro-level designs, we first build a comprehensive heterophilic GNN search space, enabling Auto-HeG to integrate complex and various heterophily of graphs. With a progressive supernet training strategy, we dynamically shrink the initial search space according to layer-wise variation of heterophily, resulting in a compact and efficient supernet. Taking a heterophily-aware distance criterion as the guidance, we conduct heterophilic architecture selection in the leave-one-out pattern, so that specialized and expressive heterophilic GNN architectures can be derived. Extensive experiments illustrate the superiority of Auto-HeG in developing excellent heterophilic GNNs to human-designed models and graph NAS models.