Research map / Graph learning / GNN architectures
On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Defines homophilic, heterophilic and gated link prediction via feature-similarity separation between edges and non-edges, gives a DistMult-based theory, and shows MLP/DistMult decoders and ego-neighbor-separated encoders (SAGE, SIGN) work best across feature-similarity regimes.
Problem
GNN link prediction is well studied under homophily, but it is unclear how feature heterophily (dissimilar features between connected nodes) affects GNN4LP performance, since existing homophily definitions rely on class labels that are unavailable for link prediction.
Approach
Defines link prediction task types (homophilic, heterophilic, gated) by how mean-centered feature-similarity distributions of edges and non-edges separate, proves that DistMult-style decoders adapt their sign to the task, and argues that ego/neighbor-separated message passing generalizes better under degree shift and feature heterophily.
Key results
- On synthetic graphs, SAGE+DistMult reaches 80.97 MRR at the negative extreme versus 25.53 for SAGE+DOT, and DistMult beats DOT by up to 55% in the negative-similarity regime.
- SAGE consistently outperforms GCN across feature-similarity levels by up to 44%, and BUDDY-SIGN beats BUDDY-GCN by up to 9.0%, supporting ego/neighbor separation.
- On real-world graphs, SAGE+MLP reaches 48.64 Hits@50 on ogbl-collab and 83.67 MRR on ogbl-citation2, with MLP the most robust decoder across feature-similarity buckets.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace DOT with DistMult as the decoder | SAGE link prediction model · Synthetic graph 0 | MRR: 25.53 -> 80.97 | Helped |
| Replace DOT with MLP as the decoder | SAGE link prediction model · Synthetic graphs across feature-similarity levels | MRR: +50% | Helped |
| Replace DOT with DistMult as the decoder | SAGE link prediction model · Synthetic graph 0 | MRR: +55% | Helped |
| Use MLP instead of DistMult as the decoder | SAGE link prediction model · Synthetic graph 9 | MRR: 88.97 -> 89.79 | Helped |
| Replace DistMult with MLP as the decoder | SAGE link prediction model · ogbl-citation2 | MRR: 82.26 -> 83.67 | Helped |
| Replace DOT with MLP as the decoder | SAGE link prediction model · e-comm | MRR: +2.3% | Helped |
| Replace GCN with SAGE as the encoder | Link prediction model with MLP decoder · Synthetic graphs across feature-similarity levels | MRR: up to 44% | Helped |
| Replace GCN with SIGN feature aggregation | BUDDY with MLP decoder · Synthetic graphs across feature-similarity levels | MRR: up to 9.0% | Helped |
| Replace GCN with SAGE as the encoder | Link prediction model with MLP decoder · e-comm | MRR | No clear effect |
| Replace SAGE+MLP with BUDDY-SIGN to add subgraph structural information | Synthetic link prediction · Synthetic graphs across feature-similarity levels | MRR: up to 26% | Hurt |
| Use node features with BUDDY instead of omitting features | BUDDY on e-comm · e-comm | MRR: 6.68 -> 13.13 | Helped |
| Add SIGN feature aggregation instead of GCN aggregation (ablation) | BUDDY with MLP decoder · ogbl-citation2 | MRR: 87.05 -> 87.53 | Helped |
Surprising findings
- Feature-agnostic heuristics such as Common Neighbors and PPR perform poorly except at the strongly positive feature-similarity extreme.
- A graph-agnostic NoGNN MLP decoder also shows a U-shaped performance trend across feature similarity, indicating the difficulty is not specific to GNNs.
Limitations
- Theoretical results are derived under simplified 2-D unit-vector and DistMult assumptions.
- Real-world e-comm dataset is a sparse, proprietary-style graph whose results show high variance (e.g., DOT 52.30 ± 5.11), and the paper's real-world evaluation covers only three datasets.
Experimental setup
Datasets: ogbl-collab ogbl-citation2 e-comm TUDataset
Benchmarks: ogbl-collab ogbl-citation2 e-comm synthetic feature-similarity graphs
Metrics: MRR Hits@50
Baselines: GCN+DOT SAGE+DOT GCN+DistMult SAGE+DistMult GCN+MLP BUDDY-GCN BUDDY-SIGN Common Neighbors Adamic-Adar Resource Allocation Personalized PageRank GPRGNN
Builds on: GCN GraphSAGE BUDDY DistMult SIGN
Closest papers by meaning
- Understanding Heterophily for Graph Neural Networks (ICML 2024 · similarity 0.91)
- What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks (NeurIPS 2024 · similarity 0.91)
- A Topological Perspective on Demystifying GNN-Based Link Prediction Performance (ICLR 2024 · similarity 0.90)
- HeterSEED: Semantics–Structure Decoupling for Heterogeneous Graph Learning under Heterophily (NeurIPS 2026 · similarity 0.90)
- Integrating Co-Training with Edge Discrimination to Enhance Graph Neural Networks Under Heterophily (AAAI 2025 · similarity 0.90)
- Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness–Generalization Perspective (NeurIPS 2025 · similarity 0.90)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.