Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

Jiong ZhuYujun YanLingxiao ZhaoMark HeimannLeman AkogluDanai Koutra

article2020NeurIPS1,476 citations

Identifies key architectural designs that prevent graph neural networks from failing under heterophily, introducing the H2GCN model to achieve substantial accuracy gains on graphs where connected nodes have dissimilar labels and features.

Listen

Graph neural networks are widely used for machine learning tasks on connected data, such as fraud detection, social networking, and molecular biology. However, most existing models rely on the assumption of homophily, which presumes that connected nodes share similar attributes and class labels. In real-world environments with heterophily—where linked nodes frequently belong to different classes or possess dissimilar features—standard architectures often fail to generalize. In such cases, these models are frequently outperformed by basic, graph-agnostic approaches like multilayer perceptrons, which ignore network connections entirely.

The article evaluates why traditional graph neural networks degrade under heterophily, identifies core structural design principles required to overcome this issue, and demonstrates how integrating these mechanisms enables robust classification performance across all network environments.

To conduct this evaluation, the researchers tested leading graph learning models and baseline networks across both synthetic datasets and diverse real-world benchmarks, spanning low-to-high homophily levels. The synthetic experiments utilized datasets generated under controlled homophily settings, while real-world evaluations encompassed university web link networks, Wikipedia topic subgraphs, and traditional citation graphs. By performing systematic ablation studies, the authors isolated the performance impact of specific architectural configurations.

The analysis produced several key findings. First, existing popular models like standard Graph Convolutional Networks and Graph Attention Networks experience severe degradation under heterophily, performing up to 42% worse than a simple multilayer perceptron. Second, three specific architectural designs effectively mitigate this degradation: separating a node's own embedding from its aggregated neighbor embeddings, explicitly incorporating higher-order (two-hop) neighborhoods, and combining intermediate representations from across layers into the final prediction. Third, synthesizing these designs into a unified model, termed H2GCN, delivers substantial accuracy gains—increasing classification accuracy by up to 40% on synthetic benchmarks and up to 27% on real-world heterophilic networks compared to models lacking these designs. Finally, the evaluation shows that low-degree nodes with fewer connections experience significantly larger accuracy drops under heterophily than under homophily, creating a 10% to 13% performance gap relative to high-degree nodes.

These findings indicate that deploying standard graph models in domains where 'opposites attract'—such as transaction fraud networks or molecular interaction maps—introduces significant risk of predictive failure and bias. The evidence shows that standard feature-averaging smooths out critical high-frequency signals necessary to distinguish distinct connected classes. Incorporating embedding separation and multi-hop modeling resolves this vulnerability without compromising accuracy when applied to traditional homophilic data.

Organizations developing graph machine learning systems should immediately audit whether their underlying datasets exhibit heterophily rather than defaulting to standard graph convolutional architectures. Model architectures in heterophilic environments should explicitly isolate ego-features from neighbor aggregations and integrate multi-hop representations. Future research and operational deployments should focus on creating higher-quality, large-scale heterophily benchmarks and developing specialized neighborhood aggregation techniques to address the high performance gap observed in low-degree nodes.

Confidence in these findings is supported by rigorous theoretical proofs and empirical tests across multiple network topologies. However, readers should note certain limitations: several real-world heterophily datasets used in testing have relatively small sample sizes, synthetic class assignments, or weak correlations between baseline node attributes and class labels. Consequently, results on specific dense or low-feature networks should be interpreted with appropriate caution.

Carnegie Mellon University University of Michigan class labels empirical analysis feedforward neural networks graph neural networks heterophily settings node classification

arXiv: 2006.11468 GemsLab/H2GCN

Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). Provides the foundational graph convolutional network architecture whose low-pass filtering and homophily assumptions underperform on heterophilous graphs.
Paper: Inductive Representation Learning on Large Graphs, William L. Hamilton et al. (2017). Introduces neighborhood aggregation and the separation of ego-node and neighbor representations that serve as a foundational design element in H2GCN.
Paper: Representation Learning on Graphs with Jumping Knowledge Networks, Keyulu Xu et al. (2018). Establishes multi-layer jumping knowledge connections that motivate combining intermediate representations across structural neighborhood orders.
Paper: Graph Attention Networks, Petar Veličković et al. (2018). Introduces the Graph Attention Network baseline evaluated in the paper when benchmarking message-passing architectures on heterophilous networks.
Paper: Pitfalls of Graph Neural Network Evaluation, Oleksandr Shchur et al. (2018). Highlights the critical importance of standardized data splits and rigorous evaluation protocols when comparing GNN architectures.
Paper: Predict then Propagate: Graph Neural Networks meet Personalized PageRank, Johannes Gasteiger et al. (2019). Demonstrates decoupling feature transformation from graph propagation, directly informing analysis of how neighborhood structures are traversed.
Paper: Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning, Qimai Li et al. (2018). Analyzes the Laplacian smoothing behavior of standard GCNs, explaining why basic graph convolution fails when neighboring labels diverge.
Paper: Simplifying Graph Convolutional Networks, Felix Wu et al. (2019). Analyzes linear message-passing propagation mechanisms and provides a baseline for evaluating feature aggregation without non-linearities.

Paper: Geom-GCN: Geometric Graph Convolutional Networks, Hongbin Pei et al. (2020). Addresses learning under heterophily and disassortativity by projecting graphs into continuous latent geometric spaces to define structural neighborhoods.
Paper: Simple and Deep Graph Convolutional Networks, Ming Chen et al. (2020). Extends deep GCN capabilities through initial residual connections and identity mappings, enabling competitive semi-supervised classification across heterophilous datasets.
Paper: How Attentive are Graph Attention Networks?, Shaked Brody et al. (2021). Investigates expressiveness bottlenecks in standard attention mechanisms and develops dynamic graph attention capable of distinguishing diverse neighborhood relationships.

Cover for Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

Abstract

We investigate the representation power of graph neural networks in the semi-supervised node classification task under heterophily or low homophily, i.e., in networks where connected nodes may have different class labels and dissimilar features. Many popular GNNs fail to generalize to this setting, and are even outperformed by models that ignore the graph structure (e.g., multilayer perceptrons). Motivated by this limitation, we identify a set of key designs -- ego- and neighbor-embedding separation, higher-order neighborhoods, and combination of intermediate representations -- that boost learning from the graph structure under heterophily. We combine them into a graph neural network, H2GCN, which we use as the base method to empirically evaluate the effectiveness of the identified designs. Going beyond the traditional benchmarks with strong homophily, our empirical analysis shows that the identified designs increase the accuracy of GNNs by up to 40% and 27% over models without them on synthetic and real networks with heterophily, respectively, and yield competitive performance under homophily.

Topics

class labels empirical analysis feedforward neural networks graph neural networks intermediate representations multilayer perceptrons graph structures network architecture graph embeddings recurrent neural networks

Keywords

graph neural networks heterophily settings node classification neighborhood aggregation neighbor-embedding separation higher-order neighborhoods Non-linear H2GCN-2 collective classification semi-supervised learning

1 Introduction
2 Notation and Preliminaries
3 Learning Over Networks with Heterophily
3.1 Effective Designs for Networks with Heterophily
3.1.1 (D1) Ego- and Neighbor-embedding Separation
3.1.2 (D2) Higher-order Neighborhoods
3.1.3 (D3) Combination of Intermediate Representations
3.2 H2GCN: A Framework for Networks with Homophily or Heterophily
4 Other Related Work
5 Empirical Evaluation
5.1 Evaluation on Synthetic Benchmarks
5.2 Evaluation on Real Benchmarks
6 Conclusion
References
A Nomenclature
B Homophily and Heterophily: Compatibility Matrix
C Proofs and Discussions of Theorems
C.1 Detailed Analysis of Theorem 1
C.2 Detailed Analysis of Theorem 2
C.3 Detailed Analysis of Theorem 3
D Our H2GCN model: Details
D.1 Pseudocode & Pipeline
D.2 Detailed Comparison of H2GCN to existing GNN models
D.3 H2GCN: Time Complexity in Detail
E Additional Related Work
F Experimental Setup & Hyperparameter Tuning
F.1 Setup
F.2 Tuning the GNN Models
G Synthetic Datasets: Details
G.1 Data Generation Process & Setup
G.2 Detailed Results on Synthetic Benchmarks
H Real Datasets: Details

Knowls

Knowl 1 — H2GCN Architecture and Inference Algorithm
algorithm
The $H_2GCN$ model is designed for semi-supervised node classification across arbitrary levels of network homophily and heterophily. It decomposes feature propagation into three distinct stages: ego-feature embedding, higher-order non-mixing neighborhood aggregation without intermediate non-linearities, and concatenation-based combination of all intermediate layer representations.
Input: Graph adjacency matrix $A \in \{0, 1\}^{n \times n}$ , node feature matrix $X \in \mathbb{R}^{n \times F}$ , label set $\mathcal{Y}$ , training set $T_V$
Hyperparameters: Feature embedding dimension $p$ , embedding rounds $K$ , activation function $\sigma$ , dropout rate
Learnable Parameters: Weight matrices $W_e \in \mathbb{R}^{F \times p}$ and $W_c \in \mathbb{R}^{(2^{K+1}-1)p \times |\mathcal{Y}|}$
Output: Node class predictions $\hat{y} \in \mathcal{Y}^n$
for $v \in V$ do
     $r_v^{(0)} = \sigma(x_v W_e)$
$A_0 = I_n$
$\bar{A}_1 = \mathbb{I}[A - I_n > 0]$
$\bar{A}_2 = \mathbb{I}[A^2 - A - I_n > 0]$
for $i \in \{1, 2\}$ do
    for $v \in V$ do
         $d_{v,i} = \sum_u [\bar{A}_i]_{vu}$
     $\bar{D}_i = \text{diag}(\{d_{v,i} : v \in V\})$
     $\tilde{A}_i = \bar{D}_i^{-1/2} \bar{A}_i \bar{D}_i^{-1/2}$
for $k = 1$ to $K$ do
     $R_1^{(k)} = \tilde{A}_1 R^{(k-1)}$
     $R_2^{(k)} = \tilde{A}_2 R^{(k-1)}$
     $R^{(k)} = [ R_1^{(k)} \, \| \, R_2^{(k)} ]$
$R^{(\text{final})} = [ R^{(0)} \, \| \, R^{(1)} \, \| \, \dots \, \| \, R^{(K)} ]$
$R^{(\text{final})} = \text{dropout}(R^{(\text{final})})$
for $v \in V$ do
     $p_v = \text{softmax}(r_v^{(\text{final})} W_c)$
     $\hat{y}_v = \arg\max_c (p_{v,c})$
return $\hat{y}$
Computational Complexity
1. Feature Embedding Stage ( $S1$ ): Calculating $\sigma(X W_e)$ requires $\mathcal{O}(\text{nnz}(X) \cdot p)$ time, where $\text{nnz}(X)$ is the number of non-zero entries in $X$ .
2. Neighborhood Computation & Aggregation ( $S2$ ): Deriving 2-hop neighborhoods via sparse matrix multiplication takes $\mathcal{O}(|E| d_{\max})$ time, where $d_{\max} = \max_{v \in V} d_v$ . Across $K$ aggregation rounds, computing $R^{(k)}$ requires $\mathcal{O}(2^K (|E| + |E_2|) p)$ operations, where $|E_2| = \frac{1}{2} \sum_{v \in V} |\bar{N}_2(v)|$ .
3. Overall Complexity: For small fixed $K$ (e.g., $K=1$ or $K=2$ ), the total runtime is $\mathcal{O}(|E| d_{\max} + (\text{nnz}(X) + |E| + |E_2|) p)$ .
Knowl 2 — Generalization Robustness of Ego-Neighbor Embedding Separation under Heterophily
theoretical result
Consider a graph $G = (V, E)$ without self-loops where node features are one-hot encodings of true labels ( $x_v = \text{onehot}(y_v)$ for all $v \in V$ ), and the training set $T_V \subset V$ is class-balanced. Assume every node $v \in T_V$ has degree $d$ , a fraction $h$ of its neighbors share its label $y_v$ , and the remaining fraction $1-h$ of neighbors are distributed uniformly across the other $|\mathcal{Y}| - 1$ classes.

Let a model optimize a linear layer to zero training loss on $T_V$ . Consider a test-time perturbation where the number of neighbors belonging to a non-ego class $y_p \ne y_v$ in $N(v)$ deviates by $\delta$ from expectation.

Under these conditions, if the edge homophily ratio satisfies: $h < \frac{1 - |\mathcal{Y}| + 2d}{2 |\mathcal{Y}| d}$ then a standard GCN aggregation layer that mixes ego- and neighbor-embeddings ( $(A + I)XW$ ) is strictly less robust to neighborhood perturbations than a layer that separates ego- and neighbor-embeddings ( $AXW$ ). Specifically, the minimum absolute perturbation $|\delta_1|$ required to cause misclassification in $(A + I)XW$ : $|\delta_1| = \left| \frac{-h |\mathcal{Y}| d - |\mathcal{Y}| + d + 1}{|\mathcal{Y}| - 1} \right|$ is strictly smaller than the perturbation $|\delta_2|$ required to misclassify under $AXW$ : $|\delta_2| = \left| \frac{(1 - h |\mathcal{Y}|) d}{|\mathcal{Y}| - 1} \right|$ meaning $(A+I)XW$ misclassifies under smaller deviations in the local label distribution than $AXW$ .
Knowl 3 — Expected Homophily Dominance in Two-Hop Graph Neighborhoods
theoretical result
Let a neighborhood $N(v)$ of node $v$ be defined as expectedly homophily-dominant if: $P(y_u = y_v \mid y_v) \ge P(y_u = y \mid y_v), \quad \forall u \in N(v), \; \forall y \in \mathcal{Y} \setminus \{y_v\}$ If the strict reverse inequality holds, $N(v)$ is expectedly heterophily-dominant.

Theorem: Consider a graph $G = (V, E)$ without self-loops and label set $\mathcal{Y}$ . Suppose for every node $v \in V$ , the class labels of its 1-hop neighbors $\{y_u : u \in N_1(v)\}$ are conditionally independent given $y_v$ , with conditional probabilities: $P(y_u = y_v \mid y_v) = h, \quad P(y_u = y \mid y_v) = \frac{1-h}{|\mathcal{Y}| - 1} \quad (\forall y \ne y_v)$ Then, for any node $v \in V$ and any node $w \in N_2(v)$ located exactly two hops away, the transition probability difference between the true class and any other class $j \ne i$ satisfies: $P(y_w = i \mid y_v = i) - P(y_w = j \mid y_v = i) = (h - \rho)^2 \ge 0$ where $\rho = \frac{1-h}{|\mathcal{Y}| - 1}$ .

Consequently, the 2-hop neighborhood $N_2(v)$ is always expectedly homophily-dominant, with equality holding if and only if $h = \frac{1}{|\mathcal{Y}|}$ (uniform class assignment across neighbors).
Knowl 4 — Spectral Energy Distribution of Graph Signals under Heterophily
theoretical result
Let $G = (V, E)$ be an undirected graph with unnormalized graph Laplacian $L = D - A$ , where $D$ is the diagonal degree matrix and $A$ is the adjacency matrix. Let $0 = \lambda_0 < \lambda_1 \le \lambda_2 \le \dots \le \lambda_{|V|-1} = \lambda_{\max}$ be the eigenvalues of $L$ with corresponding orthonormal eigenvectors $\{v_i\}_{i=0}^{|V|-1}$ . Any graph signal $s \in \mathbb{R}^{|V|}$ can be decomposed as $s = \sum_{i=0}^{|V|-1} c_{s,i} v_i$ , where $c_{s,i} = s^T v_i$ represents the coefficient of $s$ at frequency $\lambda_i$ .

The smoothness score of a binary graph signal $s \in \{0, 1\}^{|V|}$ is related to its edge homophily ratio $h_s$ by: $s^T L s = \sum_{(u,v) \in E} (s_u - s_v)^2 = 2|E|(1 - h_s)$

Theorem: For any two binary graph signals $s, t \in \{0, 1\}^{|V|}$ defined on $G$ with edge homophily ratios $h_s$ and $h_t$ :
1. $h_s < h_t \iff s^T L s > t^T L t$ .
2. If $h_s < h_t$ , there exists an integer cutoff $M \in \{1, \dots, |V|-1\}$ such that the energy of signal $s$ in the high-frequency components exceeds that of $t$ : $\sum_{i=M}^{|V|-1} c_{s,i}^2 > \sum_{i=M}^{|V|-1} c_{t,i}^2$
For one-hot encoded multi-class signals $Y_s, Y_t \in \{0, 1\}^{|V| \times |\mathcal{Y}|}$ , the edge homophily ratio becomes $h_s = 1 - \frac{1}{4|E|} \sum_{u \in V} \sum_{v \in N(u)} \sum_{j=1}^{|\mathcal{Y}|} ([Y_s]_{u,j} - [Y_s]_{v,j})^2$ , and the high-frequency energy dominance holds across channel coefficients $\sum_{i=M}^{|V|-1} \sum_{j=1}^{|\mathcal{Y}|} c_{s,j,i}^2 > \sum_{i=M}^{|V|-1} \sum_{j=1}^{|\mathcal{Y}|} c_{t,j,i}^2$ .
Knowl 5 — Definitions of Edge Homophily Ratio and Class Compatibility Matrix
definition
Let $G = (V, E)$ be an undirected, unweighted graph where each node $v \in V$ has a discrete class label $y_v \in \mathcal{Y}$ .

Edge Homophily Ratio ( $h$ )

The edge homophily ratio measures the global proportion of intra-class edges in a graph: $h = \frac{|\{(u,v) \in E : y_u = y_v\}|}{|E|}$
- $h \to 1$ indicates strong homophily (connected nodes predominantly share labels).
- $h \to 0$ indicates strong heterophily (connected nodes predominantly belong to different classes).
Empirical Class Compatibility Matrix ( $H$ )

The class compatibility matrix $H \in [0, 1]^{|\mathcal{Y}| \times |\mathcal{Y}|}$ captures fine-grained, asymmetric connection affinities between distinct class pairs. Its $(i, j)$ -th entry is defined as the fraction of outgoing edges from class $i$ nodes that connect to class $j$ nodes: $[H]_{i,j} = \frac{|\{(u,v) : (u,v) \in E \wedge y_u = i \wedge y_v = j\}|}{|\{(u,v) : (u,v) \in E \wedge y_u = i\}|}$ $H$ is a row-stochastic matrix where $\sum_{j=1}^{|\mathcal{Y}|} [H]_{i,j} = 1$ for each class $i$ .
Knowl 6 — Three Core Architectural Designs for GNNs under Heterophily
model/method
To enable effective representation learning on networks with low homophily or heterophily without sacrificing accuracy on homophilous graphs, GNN architectures require three primary structural mechanisms:
1. (D1) Ego- and Neighbor-Embedding Separation: In heterophilous settings, ego features $x_v$ and neighbor features $\{x_u : u \in \bar{N}(v)\}$ convey dissimilar signals. Standard GCN layers merge them by averaging $(A+I)X$ , causing node representations across classes to become indistinguishable. Separating the update as: $r_v^{(k)} = \text{COMBINE}\left(r_v^{(k-1)}, \text{AGGR}\left(\{r_u^{(k-1)} : u \in \bar{N}(v)\}\right)\right)$ (where $\bar{N}(v)$ excludes $v$ and COMBINE is concatenation) preserves distinct ego representations.
2. (D2) Higher-Order Neighborhood Aggregation: When immediate 1-hop neighborhoods are heterophily-dominant, 2-hop and higher-order neighborhoods $\bar{N}_i(v) = \{u : \text{dist}(u,v) = i\}$ provide homophily-dominant context: $r_v^{(k)} = \text{COMBINE}\left(r_v^{(k-1)}, \text{AGGR}\left(\{r_u^{(k-1)} : u \in \bar{N}_1(v)\}\right), \text{AGGR}\left(\{r_u^{(k-1)} : u \in \bar{N}_2(v)\}\right), \dots\right)$
3. (D3) Combination of Intermediate Representations: Because heterophily shifts informative label signals toward higher graph Laplacian frequencies, intermediate outputs $r_v^{(k)}$ from earlier rounds preserve high-frequency features that subsequent propagation steps smooth out. Combining all intermediate states at the final classification layer: $r_v^{(\text{final})} = \text{COMBINE}\left(r_v^{(0)}, r_v^{(1)}, \dots, r_v^{(K)}\right)$ retains both local high-frequency and global low-frequency information.

Knowl 7 — Node Classification Performance Across Real Heterophilous and Homophilous Benchmarks

data/table

Evaluations across real-world graph datasets spanning strong heterophily ( $h \le 0.3$ ) to strong homophily ( $h \ge 0.8$ ) demonstrate that models incorporating embedding separation (D1), higher-order neighborhoods (D2), and intermediate state combination (D3) consistently outperform standard GNNs (GCN, GAT) and graph-agnostic MLPs.

Dataset	Texas	Wisconsin	Actor	Squirrel	Chameleon	Cornell	Cora Full	Citeseer	Pubmed	Cora
Hom. ratio $h$	0.11	0.21	0.22	0.22	0.23	0.30	0.57	0.74	0.80	0.81
Nodes $\|V\|$	183	251	7,600	5,201	2,277	183	19,793	3,327	19,717	2,708
Edges $\|E\|$	295	466	26,752	198,493	31,421	280	63,421	4,676	44,327	5,278
Classes $\|\mathcal{Y}\|$	5	5	5	5	5	5	70	7	3	6
$H_2GCN$ -1	84.86	86.67	35.86	36.42	57.11	82.16	68.13	77.07	89.40	86.92
$H_2GCN$ -2	82.16	85.88	35.62	37.90	59.39	82.16	69.05	76.88	89.59	87.81
GraphSAGE	82.43	81.18	34.23	41.61	58.73	75.95	65.14	76.04	88.45	86.90
GCN-Cheby	77.30	79.41	34.11	43.86	55.24	74.32	67.41	75.82	88.72	86.76
MixHop	77.84	75.88	32.22	43.80	60.50	73.51	65.59	76.26	85.31	87.61
GraphSAGE+JK	83.78	81.96	34.28	40.85	58.11	75.68	65.31	76.05	88.34	85.96
Cheby+JK	78.38	82.55	35.14	45.03	63.79	74.59	66.87	74.98	89.07	85.49
GCN+JK	66.49	74.31	34.18	40.45	63.42	64.59	66.72	74.51	88.41	85.79
GCN	59.46	59.80	30.26	36.89	59.82	57.03	68.39	76.68	87.38	87.28
GAT	58.38	55.29	26.28	30.62	54.69	58.92	59.81	75.46	84.68	82.68
GEOM-GCN	67.57	64.12	31.63	38.14	60.90	60.81	N/A	77.99	90.05	85.27
MLP	81.89	85.29	35.76	29.68	46.36	81.08	58.76	72.41	86.65	74.75

Key Empirical Findings

On graphs with strong heterophily ( $h \le 0.3$ ), standard GCN and GAT underperform a graph-agnostic MLP by up to 25–30% accuracy (e.g., Texas: GCN 59.46% vs. MLP 81.89%).
Adding embedding separation (GraphSAGE vs. GCN) improves heterophily accuracy by up to 23%.
Adding jumping knowledge connections (D3) to GCN increases its heterophily accuracy by up to 14%.
$H_2GCN$ -2 achieves the highest overall average rank across all datasets (3.3 rank overall, 4.0 in heterophily, 2.0 in homophily), closely followed by $H_2GCN$ -1 (3.6 rank overall).

Knowl 8 — Synthetic Graph Generation Algorithm with Controlled Homophily
algorithm
To systematically evaluate GNNs across varying levels of homophily while maintaining realistic scale-free degree distributions, synthetic graphs are generated via a modified preferential attachment mechanism parameterized by a target class compatibility matrix $H$ .
Input: Target node count $|V|$ , class count $|\mathcal{Y}|$ , class compatibility matrix $H \in [0, 1]^{|\mathcal{Y}| \times |\mathcal{Y}|}$ , feature benchmark dataset $B$ with classes $\mathcal{Y}_b$
Output: Synthetic graph $G = (V, E)$ with node features $X$ and labels $y$
Initialize graph $G_0 = (V_0, E_0)$ with small number of connected nodes
Assign each node $v \in V$ a class $y_v \in \mathcal{Y}$ uniformly at random
for each new node $u$ assigned to class $i$ up to $|V|$ do
    for each existing node $v$ assigned to class $j$ do
         $P(u \sim v) \propto H_{ij} \cdot d_v$
    Sample edges incident to $u$ according to $P(u \sim v)$
    Add node $u$ and sampled edges to $G$
Establish an injective class mapping $\psi: \mathcal{Y} \to \mathcal{Y}_b$
for each class $i \in \mathcal{Y}$ do
    Sample node feature vectors for class $i$ nodes in $G$ from the corresponding class $\psi(i)$ nodes in benchmark $B$
return $G = (V, E)$ , $X$ , $y$
This procedure generates synthetic networks with power-law degree distributions where edge homophily $h$ is precisely controlled via the diagonal entries of $H$ .
Knowl 9 — Sensitivity of Heterophilous Node Classification to Node Degree
empirical result
The classification accuracy of GNNs under heterophily is heavily dependent on the degree of the target node, whereas under homophily, degree plays a negligible role.

Quantitative Observations
- In synthetic networks with heterophily ( $h = 0.2$ ), $H_2GCN$ -1 exhibits an accuracy gap of 13% between low-degree nodes (degree 4–7) and high-degree nodes (degree 64+). For $H_2GCN$ -2, the gap is 10%.
- In homophilous settings ( $h = 0.8$ ), the accuracy difference between low-degree and high-degree nodes drops to less than 3%.
Structural Mechanism

Under heterophily, predicting a node's class relies on accurately characterizing the empirical label distribution across its neighborhood. For low-degree nodes with few neighbors, sample variance in the local neighborhood distribution is high, leading to frequent misclassification. In contrast, under homophily, connected neighbors are overwhelmingly intra-class, making classification robust even with very few observed neighbors.
Knowl 10 — Ablation of Non-Linear Transformations in Heterophilous Neighborhood Aggregation
empirical result
In standard GNNs (e.g., GCN, GraphSAGE), non-linear activation functions (such as $\text{ReLU}$ ) and learnable weight matrices are applied after each neighborhood aggregation round. In $H_2GCN$ , non-linear transformations are restricted exclusively to the initial feature embedding stage ( $S1$ ), omitting all intermediate non-linearities during aggregation rounds ( $S2$ ).

Ablation Results on syn-products

Comparing $H_2GCN$ -2 (linear aggregation) against a variant incorporating per-round non-linear transformations ( $r_v^{(k)} = \text{COMBINE}(\sigma(W [ r_v^{(k-1)}, \text{AGGR}(\bar{N}_1(v)), \text{AGGR}(\bar{N}_2(v)) ]))$ :
- At $h = 0.00$ : Linear $H_2GCN$ -2 achieves $83.37\% \pm 0.38\%$ vs. Non-linear $82.23\% \pm 0.25\%$ .
- At $h = 0.10$ : Linear $H_2GCN$ -2 achieves $80.03\% \pm 0.84\%$ vs. Non-linear $78.78\% \pm 1.04\%$ .
- At $h = 0.50$ : Linear $H_2GCN$ -2 achieves $90.75\% \pm 0.43\%$ vs. Non-linear $89.78\% \pm 0.11\%$ .
- At $h = 0.80$ : Linear $H_2GCN$ -2 achieves $99.13\% \pm 0.05\%$ vs. Non-linear $98.55\% \pm 0.06\%$ .
Removing non-linear embedding transformations during aggregation simplifies the model, decreases parameter count, and consistently improves accuracy across both heterophilous and homophilous graph regimes.

Coverage note — No substantial contributed material was omitted. Specific non-contributed experimental details (command-line hyperparameter tuning grids, hardware specifications, and general background reviews of belief propagation/heterogeneous networks) were excluded to focus strictly on the core conceptual, theoretical, and empirical contributions.

References

1.Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. 2019. MixHop: Higher-Order Graph Convolution Architectures via Sparsified Neighborhood Mixing. In International Conference on Machine Learning (ICML).
2.Kristen M Altenburger and Johan Ugander. 2018. Monophily in social networks introduces similarity among friends-of-friends. Nature human behaviour 2, 4 (2018), 284–290.
3.A. L. Barabasi and R. Albert. 1999. Emergence of scaling in random networks. Science 286, 5439 (October 1999), 509–512. http://view.ncbi.nlm.nih.gov/pubmed/10521342
4.Aleksandar Bojchevski and Stephan Günnemann. 2018. Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Ranking. In International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=r1ZdKJ-0W
5.Ines Chami, Sami Abu-El-Haija, Bryan Perozzi, Christopher Ré, and Kevin Murphy. 2020. Machine Learning on Graphs: A Model and Comprehensive Taxonomy. arXiv preprint arXiv:2005.03675 (2020).
6.Alex Chin, Yatong Chen, Kristen M. Altenburger, and Johan Ugander. 2019. Decoupled smoothing on graphs. In Proceedings of the 2019 World Wide Web Conference. 263–272.
7.Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems (NeurIPS). 3844–3852.
8.Dhivya Eswaran, Stephan Günnemann, Christos Faloutsos, Disha Makhija, and Mohit Kumar. 2017. Zoobp: Belief propagation for heterogeneous networks. Proceedings of the VLDB Endowment 10, 5 (2017), 625–636.
9.Wolfgang Gatterbauer. 2014. Semi-supervised learning with heterophily. arXiv preprint arXiv:1412.3100 (2014).
10.Wolfgang Gatterbauer, Stephan Günnemann, Danai Koutra, and Christos Faloutsos. 2015. Linearized and Single-Pass Belief Propagation. Proceedings of the VLDB Endowment 8, 5 (2015).
11.Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. In Advances in neural information processing systems (NeurIPS). 1024–1034.
12.Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard T. B. Ma, Hongzhi Chen, and Ming-Chang Yang. 2020. Measuring and Improving the Use of Graph Information in Graph Neural Networks. In International Conference on Learning Representations (ICLR).
13.Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open Graph Benchmark: Datasets for Machine Learning on Graphs. arXiv preprint arXiv:2005.00687 (2020).
14.D. Jensen J. Neville. 2000. Iterative classification in relational data, In In Proc. AAAI. Workshop on Learning Statistical Models from Relational, 13–20.
15.Junteng Jia and Austion R Benson. 2020. Residual Correlation in Graph Neural Network Regression. In Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 588–598.
16.Fariba Karimi, Mathieu Génois, Claudia Wagner, Philipp Singer, and Markus Strohmaier. 2017. Visibility of minorities in social networks. arXiv preprint arXiv:1702.00150 (2017).
17.Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations (ICLR).
18.Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. 2019. Diffusion Improves Graph Learning. In Advances in Neural Information Processing Systems (NeurIPS).
19.Danai Koutra, Tai-You Ke, U Kang, Duen Horng Chau, Hsing-Kuo Kenneth Pao, and Christos Faloutsos. 2011. Unifying Guilt-by-Association Approaches: Theorems and Fast Algorithms. In Proceedings of the European Conference on Machine Learning and Principles and Practice of Knowledge Discovery in Databases (ECML PKDD). 245–260.
20.Qing Lu and Lise Getoor. 2003. Link-Based Classification. In Proceedings of the Twentieth International Conference on International Conference on Machine Learning (ICML). AAAI Press, 496–503.
21.Miller McPherson, Lynn Smith-Lovin, and James M Cook. 2001. Birds of a Feather: Homophily in Social Networks. Annual Review of Sociology 27, 1 (2001), 415–444.
22.Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. 2012. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, Vol. 8.
23.Mark Newman. 2018. Networks. Oxford university press.
24.Shashank Pandit, Duen Horng Chau, Samuel Wang, and Christos Faloutsos. 2007. NetProbe: A Fast and Scalable System for Fraud Detection in Online Auction Networks. In Proceedings of the 16th international conference on World Wide Web. ACM, 201–210.
25.Leto Peel. 2017. Graph-based semi-supervised learning for relational networks. In Proceedings of the 2017 SIAM International Conference on Data Mining. SIAM, 435–443.
26.Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-GCN: Geometric Graph Convolutional Networks. In International Conference on Learning Representations (ICLR). https://openreview.net/forum?id=S1e2agrFvS
27.Meng Qu, Yoshua Bengio, and Jian Tang. 2019. GMNN: Graph Markov Neural Networks. In International Conference on Machine Learning (ICML). 5241–5250.
28.Ryan A. Rossi, Di Jin, Sungchul Kim, Nesreen Ahmed, Danai Koutra, and John Boaz Lee. 2020. On Proximity and Structural Role-based Embeddings in Networks: Misconceptions, Techniques, and Applications. ACM Transactions on Knowledge Discovery from Data (TKDD) (2020).
29.Benedek Rozemberczki, Carl Allen, and Rik Sarkar. 2019. Multi-scale attributed node embedding. arXiv preprint arXiv:1909.13021 (2019).
30.Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. 2008. Collective classification in network data. AI magazine 29, 3 (2008), 93–93.
31.Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of Graph Neural Network Evaluation. Relational Representation Learning Workshop, NeurIPS 2018 (2018).
32.David I Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. 2013. The emerging field of signal processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains. IEEE signal processing magazine 30, 3 (2013), 83–98.
33.Otilia Stretcu, Krishnamurthy Viswanathan, Dana Movshovitz-Attias, Emmanouil Platanios, Sujith Ravi, and Andrew Tomkins. 2019. Graph Agreement Models for Semi-Supervised Learning. In Advances in Neural Information Processing Systems (NeurIPS). 8713–8723.
34.Yizhou Sun and Jiawei Han. 2012. Mining Heterogeneous Information Networks: Principles and Methodologies. Morgan & Claypool Publishers.
35.Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. 2009. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining. 807–816.
36.Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. International Conference on Learning Representations (ICLR) (2018). https://openreview.net/forum?id=rJXMpikCZ
37.Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying Graph Convolutional Networks. In International Conference on Machine Learning (ICML). 6861–6871.
38.Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. 2018. Representation Learning on Graphs with Jumping Knowledge Networks. In Proceedings of the 35th International Conference on Machine Learning, ICML, Vol. 80. PMLR, 5449–5458.
39.Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semi-supervised learning with graph embeddings. In International Conference on Machine Learning (ICML). PMLR, 40–48.
40.J.S. Yedidia, W.T. Freeman, and Y. Weiss. 2003. Understanding Belief Propagation and its Generalizations. Exploring Artificial Intelligence in the New Millennium 8 (2003), 236–239.
41.Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. 2019. Graph convolutional networks: a comprehensive review. Computational Social Networks (2019).
42.Z. Zhang, P. Cui, and W. Zhu. 2020. Deep Learning on Graphs: A Survey. IEEE Transactions on Knowledge and Data Engineering (TKDE) (2020).
43.Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and Danai Koutra. 2020. Graph Neural Networks with Heterophily. arXiv preprint arXiv:2009.13566 (2020).
44.Xiaojin Zhu. 2005. Semi-supervised learning with graphs. Ph.D. Dissertation. Carnegie Mellon University, Pittsburgh, PA, USA. http://portal.acm.org/citation.cfm?id=1104523

Citation

MLA

Zhu, J., et al. “Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs”. arXiv, 2020, http://arxiv.org/abs/2006.11468v2.

APA

Zhu, J., Yan, Y., Zhao, L., Heimann, M., Akoglu, L., & Koutra, D. (2020). Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. arXiv. http://arxiv.org/abs/2006.11468v2

Chicago

Zhu, J., Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. 2020. “Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs”. arXiv. http://arxiv.org/abs/2006.11468v2.

Harvard

Zhu, J. et al. (2020) “Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs”, arXiv [Preprint]. Available at: http://arxiv.org/abs/2006.11468v2.

Vancouver

1. Zhu J, Yan Y, Zhao L, Heimann M, Akoglu L, Koutra D (2020) Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs. arXiv

BibTeX

@article{zhu2020beyond,
  title = {Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs},
  author = {Zhu, Jiong and Yan, Yujun and Zhao, Lingxiao and Heimann, Mark and Akoglu, Leman and Koutra, Danai},
  year = {2020},
  journal = {arXiv},
  url = {http://arxiv.org/abs/2006.11468v2},
  eprint = {2006.11468}
}

Metadata:arXiv

Source Code

This paper has an official code repository available. Click below to access the source code.

View Repository

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Authors

Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — H2GCN Architecture and Inference Algorithm

Computational Complexity

Knowl 2 — Generalization Robustness of Ego-Neighbor Embedding Separation under Heterophily

Knowl 3 — Expected Homophily Dominance in Two-Hop Graph Neighborhoods

Knowl 4 — Spectral Energy Distribution of Graph Signals under Heterophily

Knowl 5 — Definitions of Edge Homophily Ratio and Class Compatibility Matrix

Edge Homophily Ratio (hhh)

Empirical Class Compatibility Matrix (HHH)

Knowl 6 — Three Core Architectural Designs for GNNs under Heterophily

Knowl 7 — Node Classification Performance Across Real Heterophilous and Homophilous Benchmarks

Key Empirical Findings

Knowl 8 — Synthetic Graph Generation Algorithm with Controlled Homophily

Knowl 9 — Sensitivity of Heterophilous Node Classification to Node Degree

Quantitative Observations

Structural Mechanism

Knowl 10 — Ablation of Non-Linear Transformations in Heterophilous Neighborhood Aggregation

Ablation Results on syn-products

References

Citation

BibTeX

Source Code

Access the Paper

Edge Homophily Ratio ( $h$ )

Empirical Class Compatibility Matrix ( $H$ )