# On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 60 references that are in the map.
- First posted on arXiv 26 Sep 2024.

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

- [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)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [Pitfalls of Graph Neural Network Evaluation](https://mlsanity.com/paper/1811.05868/) (2018)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Geom-GCN: Geometric Graph Convolutional Networks](https://mlsanity.com/paper/2002.05287/) (2020)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [MixHop: Higher-Order Graph Convolutional Architectures via Sparsified Neighborhood Mixing](https://mlsanity.com/paper/1905.00067/) (2019)
- [A critical look at the evaluation of GNNs under heterophily: Are we really making progress?](https://mlsanity.com/paper/2302.11640/) (2023)
- [Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking](https://mlsanity.com/paper/1707.03815/) (2017)
- [Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods](https://mlsanity.com/paper/2110.14446/) (2021)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Graph Neural Networks with Heterophily](https://mlsanity.com/paper/2009.13566/) (2020)
- [BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation](https://mlsanity.com/paper/2106.10994/) (2021)
- [Graph Neural Networks for Graphs with Heterophily: A Survey](https://mlsanity.com/paper/2202.07082/) (2022)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Predicting multicellular function through multi-layer tissue networks](https://mlsanity.com/paper/1707.04638/) (2017)
- [Cooperative Game Theory Approaches for Network Partitioning](https://mlsanity.com/paper/1707.03587/) (2017)
- [Graph Neural Networks for Link Prediction with Subgraph Sketching](https://mlsanity.com/paper/2209.15486/) (2022)
- [User Preference-aware Fake News Detection](https://mlsanity.com/paper/2104.12259/) (2021)
- [Neo-GNNs: Neighborhood Overlap-aware Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2206.04216/) (2022)
- [Evaluating Graph Neural Networks for Link Prediction: Current Pitfalls and New Benchmarking](https://mlsanity.com/paper/2306.10453/) (2023)
- [Shopping Queries Dataset: A Large-Scale ESCI Benchmark for Improving Product Search](https://mlsanity.com/paper/2206.06588/) (2022)

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

- [Graph4MM: Weaving Multimodal Learning with Structural Information](https://mlsanity.com/paper/2510.16990/) (2025)
- [Learning Laplacian Positional Encodings for Heterophilous Graphs](https://mlsanity.com/paper/2504.20430/) (2025)
- [Understanding GNNs and Homophily in Dynamic Node Classification](https://mlsanity.com/paper/2504.20421/) (2025)
- [Disentangled and Self-Explainable Node Representation Learning](https://mlsanity.com/paper/2410.21043/) (2024)
- [Graph homophily booster: Reimagining the role of discrete features in heterophilic graph learning](https://mlsanity.com/paper/2602.07256/) (2026)
- [How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?](https://mlsanity.com/paper/2506.11869/) (2025)
- [Adaptive Node Feature Selection For Graph Neural Networks](https://mlsanity.com/paper/2510.03096/) (2025)
- [Are Heterogeneous Graph Neural Networks Truly Effective for Node Classification? A Causal Perspective](https://mlsanity.com/paper/2510.05750/) (2025)
- [Inductive Subgraphs as Shortcuts: Causal Disentanglement for Heterophilic Graph Learning](https://mlsanity.com/paper/2604.19186/) (2026)
- [EO-Agents: A Three-Agent LLM Pipeline for Earth Observation Hypothesis Generation](https://mlsanity.com/paper/2607.01584/) (2026)

## Abstract (arXiv)

Heterophily, or the tendency of connected nodes in networks to have different class labels or dissimilar features, has been identified as challenging for many Graph Neural Network (GNN) models. While the challenges of applying GNNs for node classification when class labels display strong heterophily are well understood, it is unclear how heterophily affects GNN performance in other important graph learning tasks where class labels are not available. In this work, we focus on the link prediction task and systematically analyze the impact of heterophily in node features on GNN performance. Theoretically, we first introduce formal definitions of homophilic and heterophilic link prediction tasks, and present a theoretical framework that highlights the different optimizations needed for the respective tasks. We then analyze how different link prediction encoders and decoders adapt to varying levels of feature homophily and introduce designs for improved performance. Our empirical analysis on a variety of synthetic and real-world datasets confirms our theoretical insights and highlights the importance of adopting learnable decoders and GNN encoders with ego- and neighbor-embedding separation in message passing for link prediction tasks beyond homophily.