# Exploring Heterophily in Graph-level Tasks

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 48 references that are in the map.
- First posted on arXiv 23 Sep 2025.

## Builds on (most cited first, 20 of 20)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [DeepWalk: Online Learning of Social Representations](https://mlsanity.com/paper/1403.6652/) (2014)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [Revisiting Heterophily For Graph Neural Networks](https://mlsanity.com/paper/2210.07606/) (2022)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Is Heterophily A Real Nightmare For Graph Neural Networks To Do Node Classification?](https://mlsanity.com/paper/2109.05641/) (2021)
- [Molecular graph generation with Graph Neural Networks](https://mlsanity.com/paper/2012.07397/) (2020)
- [Break the Ceiling: Stronger Multi-scale Deep Graph Convolutional Networks](https://mlsanity.com/paper/1906.02174/) (2019)
- [Understanding convolution on graphs via energies](https://mlsanity.com/paper/2206.10991/) (2022)
- [MUDiff: Unified Diffusion for Complete Molecule Generation](https://mlsanity.com/paper/2304.14621/) (2023)
- [The Heterophilic Graph Learning Handbook: Benchmarks, Models, Theoretical Analysis, Applications and Challenges](https://mlsanity.com/paper/2407.09618/) (2024)
- [ReactZyme: A Benchmark for Enzyme-Reaction Prediction](https://mlsanity.com/paper/2408.13659/) (2024)
- [Community detection and graph partitioning](https://mlsanity.com/paper/1305.4974/) (2013)
- [Flexible Diffusion Scopes with Parameterized Laplacian for Heterophilic Graph Learning](https://mlsanity.com/paper/2409.09888/) (2024)
- [Rethinking Structure Learning For Graph Neural Networks](https://mlsanity.com/paper/2411.07672/) (2024)
- [Transportation Network Analysis, Volume I: Static and Dynamic Traffic Assignment](https://mlsanity.com/paper/2502.05182/) (2025)

## Abstract (arXiv)

While heterophily has been widely studied in node-level tasks, its impact on graph-level tasks remains unclear. We present the first analysis of heterophily in graph-level learning, combining theoretical insights with empirical validation. We first introduce a taxonomy of graph-level labeling schemes, and focus on motif-based tasks within local structure labeling, which is a popular labeling scheme. Using energy-based gradient flow analysis, we reveal a key insight: unlike frequency-dominated regimes in node-level tasks, motif detection requires mixed-frequency dynamics to remain flexible across multiple spectral components. Our theory shows that motif objectives are inherently misaligned with global frequency dominance, demanding distinct architectural considerations. Experiments on synthetic datasets with controlled heterophily and real-world molecular property prediction support our findings, showing that frequency-adaptive model outperform frequency-dominated models. This work establishes a new theoretical understanding of heterophily in graph-level learning and offers guidance for designing effective GNN architectures.