Research map / Graph learning / GNN architectures
Understanding Heterophily for 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.
Proposes Heterophilous Stochastic Block Models (HSBM) to theoretically analyze how graph convolution affects multi-class separability under different heterophily patterns, neighborhood inconsistency, and stacked layers, validated on synthetic and eight real-world datasets.
Problem
Heterophily's impact on multi-class node classification with GNNs is not quantitatively understood; existing heterophily ratios and binary CSBM analyses do not capture diverse heterophily patterns, neighborhood inconsistency, or multi-layer over-smoothing.
Approach
A general random graph model (HSBM) where edges depend on the classes of endpoints, with class-specific neighborhood distributions plus node-wise topological noise and Gaussian features; separability gain after graph convolution is shown to be the Euclidean distance of degree-weighted neighborhood distributions scaled by sqrt(average degree).
Key results
- On synthetic HSBM data (n=1000, c=5), GCN outperforms MLP in the good heterophily pattern (a=0.25) for all class pairs, while the bad pattern (a=0.18) reduces separability for all pairs.
- On real data, Cora (MLP 77.68 vs GCN 90.04), Chameleon (54.29 vs 70.33) and Workers are classified as good heterophily, while Actor (35.00 vs 30.33) is bad.
- Stacking GC layers keeps separability gains nonzero as l grows, but accuracy drops sharply near l=50 in float64 due to precision limits.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add one GC operation to the second MLP layer | MLP · Cora | accuracy: 77.68 -> 90.04 | Helped |
| add one GC operation to the second MLP layer | MLP · Chameleon | accuracy: 54.29 -> 70.33 | Helped |
| add one GC operation to the second MLP layer | MLP · Workers | accuracy: 76.81 -> 78.66 | Helped |
| add one GC operation to the second MLP layer | MLP · Actor | accuracy: 35.00 -> 30.33 | Hurt |
| add one GC operation to the second MLP layer | MLP · Amazon-ratings | accuracy: 50.58 -> 48.01 | Hurt |
| add one GC operation to the second MLP layer | MLP · Squirrel | accuracy: 36.63 -> 60.67 | Helped |
| add one GC operation to the second MLP layer | MLP · Arxiv-year | accuracy: 36.40 -> 42.44 | Helped |
| add one GC operation to the second MLP layer | MLP · Snap-patents | accuracy: 31.50 -> 34.42 | Helped |
| increase the averaged node degree (ablation) | GCN on synthetic HSBM graphs with a=0.20 · Synthetic HSBM | accuracy | Helped |
| increase topological-noise variance (ablation) | GCN on synthetic HSBM graphs with a=0.20 · Synthetic HSBM | accuracy | Hurt |
| stack multiple GC operations (ablation) | MLP with GC operations on synthetic HSBM graphs · Synthetic HSBM | accuracy | Mixed |
| use a higher-precision data format (ablation) | GCN with multiple GC operations · Synthetic HSBM | accuracy | Helped |
Surprising findings
- Accuracy drops sharply around 50 GC layers because of floating-point precision limits, not only over-smoothing.
- Nodes can retain separability under over-smoothing when using normalized neighborhood distances.
Limitations
- Theory assumes Gaussian node features and independence among node features and edges.
- Real-world results require a lower varsigma_n (e.g., 0.2) to be interpreted, indicating the theory does not fully hold for real data.
- Analysis is restricted to the ideal Bayes classifier and GCN with the nonlinearity neglected.
Experimental setup
Datasets: Cora Chameleon Workers Actor Amazon-ratings Squirrel Arxiv-year Snap-patents
Benchmarks: Cora Chameleon Workers Actor Amazon-ratings Squirrel Arxiv-year Snap-patents
Metrics: accuracy separability gain confusion matrix difference
Baselines: MLP GCN
Builds on: CSBM GCN SGC
Closest papers by meaning
- On the Impact of Feature Heterophily on Link Prediction with Graph Neural Networks (NeurIPS 2024 · similarity 0.91)
- Making Classic GNNs Strong Baselines Across Varying Homophily: A Smoothness–Generalization Perspective (NeurIPS 2025 · similarity 0.90)
- Integrating Co-Training with Edge Discrimination to Enhance Graph Neural Networks Under Heterophily (AAAI 2025 · similarity 0.90)
- Refining Latent Homophilic Structures over Heterophilic Graphs for Robust Graph Convolution Networks (AAAI 2024 · similarity 0.90)
- What Is Missing For Graph Homophily? Disentangling Graph Homophily For Graph Neural Networks (NeurIPS 2024 · similarity 0.89)
- PC-Conv: Unifying Homophily and Heterophily with Two-Fold Filtering (AAAI 2024 · similarity 0.89)
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.