On Performance Discrepancies Across Local Homophily Levels in Graph
  Neural Networks
Graph Neural Network (GNN) research has highlighted a relationship between
high homophily (i.e., the tendency of nodes of the same class to connect) and
strong predictive performance in node classification. However, recent work has
found the relationship to be more nuanced, demonstrating that simple GNNs can
learn in certain heterophilous settings. To resolve these conflicting findings
and align closer to real-world datasets, we go beyond the assumption of a
global graph homophily level and study the performance of GNNs when the local
homophily level of a node deviates from the global homophily level. Through
theoretical and empirical analysis, we systematically demonstrate how shifts in
local homophily can introduce performance degradation, leading to performance
discrepancies across local homophily levels. We ground the practical
implications of this work through granular analysis on five real-world datasets
with varying global homophily levels, demonstrating that (a) GNNs can fail to
generalize to test nodes that deviate from the global homophily of a graph, and
(b) high local homophily does not necessarily confer high performance for a
node. We further show that GNNs designed for globally heterophilous graphs can
alleviate performance discrepancy by improving performance across local
homophily levels, offering a new perspective on how these GNNs achieve stronger
global performance.
Donald Loveland, Jiong Zhu, Mark Heimann, Benjamin Fish, Michael T. Schaub, Danai Koutra
# On Performance Discrepancies Across Local Homophily Levels

###### Abstract

Graph Neural Network (GNN) research has highlighted a relationship between high homophily (i.e., the tendency of nodes of the same class to connect) and strong predictive performance in node classification. However, recent work has found the relationship to be more nuanced, demonstrating that simple GNNs can learn in certain heterophilous settings. To resolve these conflicting findings and align closer to real-world datasets, we go beyond the assumption of a global graph homophily level and study the performance of GNNs when the local homophily level of a node deviates from the global homophily level. Through theoretical and empirical analysis, we systematically demonstrate how shifts in local homophily can introduce performance degradation, leading to performance discrepancies across local homophily levels. We ground the practical implications of this work through granular analysis on five real-world datasets with varying global homophily levels, demonstrating that (a) GNNs can fail to generalize to test nodes that deviate from the global homophily of a graph, and (b) high local homophily does not necessarily confer high performance for a node. We further show that GNNs designed for globally heterophilous graphs can alleviate performance discrepancy by improving performance across local homophily levels, offering a new perspective on how these GNNs achieve stronger global performance.

## 1 Introduction

Deep learning with Graph Neural Networks (GNNs) has become common in many learning tasks over collaboration networks [1], social networks [2], financial networks [3], and more [4; 5; 6]. However, given the relative infancy of GNNs, retrospectives on GNN performance are limited. Understanding the conditions that will cause a GNN's performance to degrade promotes a proactive approach to GNN development, rectifying any issues that may arise once deployed to the public. One previously studied degradation mechanism of GNN performance is the presence of heterophilous connections [7; 8]. Heterophily, or the tendency for nodes of different classes to connect, has been found in a variety of graph applications where sensitive factors may influence the connective patterns, necessitating its study [9; 10; 11; 12]. However, more recent retrospectives have argued that performance does not necessarily degrade with heterophily, and in fact simple GNN architectures, such as GCN, can perform well in certain settings [13; 14; 15]. These seemingly conflicting results indicate a gap in understanding, demanding further research on the influence of heterophily on GNNs.
To better understand the factors which govern GNN performance, we begin by exploring the assumptions made in previous works. Surprisingly, many assume that constituent nodes of a graph possess local homophily levels similar to the global homophily of the entire graph, leading to a disregard for the impact of a node's local homophily level on performance [7, 13, 14]. For the few works that consider local homophily, it is often assumed that homophilous nodes should perform better, creating unclear conclusions due to biased interpretation of the localized results [16, 17]. Moreover, local homophily has yet to be the focal point of previous works, leading to limited discussion on why certain patterns emerge. Practically, assuming a constant local homophily makes it difficult to determine if new models are improving performance across all nodes, or simply increasing performance for certain node subsets. Furthermore, by myopically assuming higher homophily is indicative of higher performance, analysis on discrepancies that arise from model choice, global homophily, and local homophily is limited, slowing the development of new GNNs that could address these concerns.

**This work.** We investigate how shifts in local homophily can impact GNNs, extending beyond current assumptions and aligning closer to real-world settings. Our analysis considers a GNN trained on nodes biased towards a graph's global homophily, and then applied to test nodes of varying local homophily levels. We _theoretically analyze_ the scenario by obtaining a closed-form solution for a GNN's weight matrix and demonstrate, through perturbation analysis, that a GNN's performance can degrade when a node's local homophily level is shifted relative to the global homophily of the graph. We show that our findings generalize to a variety of settings through a broad empirical analysis facilitated by our proposed _synthetic graph generator_ that enables control over the local homophily levels of nodes. We also show the practical repercussions of our theoretical and empirical analyses on a representative set of five _real-world_ datasets with varying global homophily levels. Across our synthetic and real-world datasets, we additionally study nine different GNN architectures, demonstrating that those tailored to handle heterophily often maintain more uniform performance, minimizing discrepancies. Together, our theoretical and empirical analysis describes a new failure point of GNNs - an expected distribution of labels over a node's neighbors, stemming from an over-reliance on the global homophily of a graph - presenting a challenge for nodes with underrepresented homophily levels to be correctly predicted. While previous works have noted fairness issues in GNNs based on sensitive attributes, e.g. race or gender, determined exogenously [18, 19], our results point to a novel inequality rooted in a network's structure that could lead to unfairness in human-centric settings. Our main contributions are:

* **Theoretical Analysis:** We theoretically connect how a shift in local homophily level can impact a model's predictions, providing intuition on how GNN performance can degrade for nodes with local homophily levels far from the global homophily level of the entire graph.
* **Synthetic Experiments and Model Comparison:** We perform empirical analysis by modifying the preferential attachment model to allow for more granular control over the distribution of local homophily levels. This capability facilitates empirical verification of our theory under more general graph structures and GNN architectures. Additionally, we perform the first node-level analysis that directly compares GNNs that assume homophily and GNNs that are adjusted for heterophily, demonstrating different levels of performance discrepancy across GNN designs.
* **Real-world Experiments:** We provide the first granular analysis of GNN performance as local homophily levels are varied across a set of five real-world datasets. We find that our theoretical performance degradation trends hold more generally, confirming GNNs designed for heterophily can aid in minimizing performance discrepancy across nodes with varying local homophily patterns.

## 2 Related Work

In this section, we begin by discussing GNN architectures designed to improve learning under heterophily. We then detail previous approaches towards local property analysis, as well as discrepancy analysis, connecting both to our study of local homophily.

**Learning GNNs in Diverse Neighborhoods.** To learn node representations, GNNs adopt an aggregation function to combine the ego-node's (the node being updated) features and the neighboring nodes' features. Depending on the neighborhood structure of a node, a particular aggregation mechanism may be insufficient to adequately learn representations [8]. For example, GCN [20], GAT [21], and SGC [22] were built to learn over homophilous neighborhoods through their weighted average of the ego-node and neighboring nodes' features. To remedy this issue, methods such as GraphSAGE [23], GPR-GNN [24], FA-GCN [25], and GCNII [26] separate the ego and neighbor embeddings, ei
ther through a residual connection or concatenation. GPR-GNN and FA-GCN additionally follow a predict-before-propagate paradigm to help alleviate the harm that can come from mixing representation learning and aggregation [27, 28], while GCNII utilizes identity mapping to mitigate oversmoothing, a known problem for homophily [8]. H2GCN [7] adopts further decoupling across higher order neighborhoods, aggregating each \(k\)-hop neighborhood separately. _In previous works, there is limited analysis of the impact of GNN architectures on the performance nodes with varying local homophily. In this work, we provide the first granular analysis of these models, showing a different perspective on how they perform and their (in)ability to mitigate performance discrepancies._

**Local Property Analysis.** Studies on GNN performance relative to an input graph's structural properties have gained traction; however, the adjustment to considering a per-node local perspective is still under-explored. For instance, many studies have argued the conditions in which a node is able to benefit from message passing with respect to homophily, but only consider a constant local homophily level for all nodes [8, 13, 14]. Du et al. offers the first local analysis, however the results are contradictory across datasets and are only performed for a single model [16]. More recent work has developed other homophily-inspired metrics to contextualize local performance, however the proposed metric can still fail to explain performance depending on the dataset [17]. Both works assume that higher local homophily should always improve performance, ultimately guiding their development of new architectures and metrics that reinforce this assumption. However, the conflicting results across datasets seen in both works indicate that this assumption may oversimplify the behavior of a GNN and fail to consider other drivers for performance degradation. Closely related to our work, Ma et al. analyzes the disparate treatment of individual nodes defined by their shortest path distance to the training dataset, showing a degradation in performance as distance increases [29]. We build upon the idea of structural property subgroup analysis, but instead consider variations in local homophily rather than distance to the training set, creating a shift in how performance is analyzed in the context of homophily. _Thus, we analyze the performance of GNNs, breaking the assumption that the local homophily levels are constant, and demonstrate how node predictions systematically degrade as the local homophily levels deviate from the global homophily of the training graph._

## 3 Preliminaries

In this section, we provide key notations and definitions, the notation is summarized in App. A.1.

### Graphs

Let \(G=(V,E,\mathbf{X},\mathbf{Y})\) denote a simple graph with node set \(V\) and edge set \(E\), where \(\mathbf{X}\in\mathbb{R}^{|V|\times f}\) represents the node feature matrix with \(f\) features per node and \(\mathbf{Y}\in\{0,1\}^{|V|\times c}\) represents the one-hot encoded node label matrix with \(c\) classes. A specific node \(i\in G\) has feature vector \(\mathbf{x_{i}}\), class \(y_{i}\in\{1,...,c\}\), and one-hot encoded class label vector \(\mathbf{y_{i}}\). The edge set can also be represented as an adjacency matrix, \(\mathbf{A}\in\{0,1\}^{|V|\times|V|}\), where a value of \(1\) at index \((i,j)\) denotes an edge between nodes \(i\) and \(j\) in \(G\), otherwise the index is set to \(0\). We use both \(E\) and \(\mathbf{A}\) throughout the paper, opting for \(E\) when explicitly discussing the edges of \(G\) and \(\mathbf{A}\) when describing matrix computations on the edge set. A _\(k\)-hop neighborhood_ of node \(i\in V\), \(N_{k}(i)\), denotes the subgraph induced by the nodes that are reachable within \(k\)-steps of \(i\).

### Node Classification with GNNs

We focus on node classification through a GNN, where the goal is to learn a mapping between \(\mathbf{X}\) and \(\mathbf{Y}\). This mapping is estimated through a subset of \(V\), referred to as the set of training nodes \(n_{train}\). For a \(k\)-layer GNN, learning is facilitated through message passing over \(k\)-hop neighborhoods of a graph. The steps, at a high level, include (1) embedding \(\mathbf{X}\) through a non-linear transformation parameterized by a weight matrix \(\mathbf{W}\) and (2) aggregating the embedded features across neighborhoods of each node. Message passing over all nodes in the graph can be computed through matrix multiplication, where the most basic formulation updates node representations through \(\mathbf{R}_{l}=\sigma((\mathbf{A}+\mathbf{I})\mathbf{R}_{l-1}\mathbf{W}_{l})\) for a layer \(l\in\{1,2,...,k\}\) of the GNN, where \(\mathbf{R}_{0}=\mathbf{X}\) and \(\sigma\) is an activation function. The update is applied \(k\) times, resulting in final representations for each node that can be used for classification.
### Homophily and Heterophily

In this work, we focus on edge homophily and present the following definitions to describe our homophily-based analysis. We begin with the global homophily ratio of a graph, \(h\).

**Definition 1 - Global Homophily Ratio.**_The global homophily ratio \(h\) over a graph's edge set \(E\) is the fraction of edges in \(E\) that connect two nodes, \(u\) and \(v\), with the same label, \(y_{u}\) and \(y_{v}\):_

\[h=\frac{|\{(u,v):(u,v)\in E\wedge y_{u}=y_{v}\}|}{|E|}. \tag{1}\]

The global homophily ratio is used to describe the overall homophily level in graphs; \(h=0\) indicates a fully heterophilous graph and \(h=1\) indicates a fully homophilous graph [10]. Additionally, the empirical class compatibility matrix of a graph, \([\mathbf{H}_{L}]\) describes the probability of two nodes with certain labels connecting, where the \((u,v)\)-th entry is the fraction of edges between a node in class \(u\) and a node in class \(v\): \([\mathbf{H}_{L}]_{u,v}=\frac{|\{(i,j):(i,j)\in E\wedge y_{i}=u\wedge y_{j}=v\}|} {|\{(i,j):(i,j)\in E\wedge y_{i}=u\}|}\). However, both the global homophily ratio and compatibility matrix oversimplify the mixing patterns in a graph when there are varying neighborhood compositions. To perform more granular analysis on a per-node basis, we also define the local homophily ratio of a node \(t\), \(h_{t}\).

**Definition 2 - Local Homophily Ratio.**_The local homophily ratio of a node \(t\), \(h_{t}\), is the fraction of edges in the neighborhood of \(t\) that connect \(t\) to a neighbor \(u\) with the same class:_

\[h_{t}=\frac{|\{(u,t):(u,t)\in N_{1}(t)\wedge y_{u}=y_{t}\}|}{|N_{1}(t)|}. \tag{2}\]

Given GNNs are often shallow and only depend on a small \(k\)-hop neighborhood for a single node prediction, it is natural to analyze GNNs through the local, rather than global, homophily ratio. Moreover, many real-world graphs display a wide range of local homophily ratios across the constituent nodes, as seen in App. A.4.1, necessitating local analysis.

## 4 Relationship between a Node's Local Homophily Level and Performance

In this section, we aim to characterize the impact of local homophily on the accuracy of node-level predictions by considering shifts in local homophily levels, at test time, relative to the global homophily level the GNN was trained on. We begin by revealing the drivers for performance discrepancies through theoretical analysis and discuss their implications on node-level performance. Leveraging these insights, we relax our assumptions in Section 5.2 and show that our theory holds in more general settings via extensive empirical analysis on synthetic data. Additionally, we consider even more general real-world graphs (without any constraints) in Section 6.

**Setup.** Following previous theoretical GNN work [7, 14, 16, 30] and popular models such as SGC and LightGCN [22, 31], we assume a GNN, \(F\), formulated as \((\mathbf{A}+\mathbf{I})\mathbf{X}\mathbf{W}\), where \(\mathbf{A}+\mathbf{I}\) is \(G\)'s adjacency matrix with self-loops and \(\mathbf{W}\) is \(F\)'s weight matrix. Similar to the setup in [32], we consider a graph \(G\) with a subset of training nodes \(n_{train}\), each of which has an associated node feature vector \(\mathbf{x_{i}}\), one-hot encoded class label vector \(\mathbf{y_{i}}\), \(1\)-hop homophily ratio \(h\), and degree \(d\). For brevity, we focus on binary classification (though we consider multi-class settings in our experiments) and represent \(\mathbf{y_{i}}\)= \(onehot(y_{i})=[1\quad 0]\) when node \(i\)'s class is \(y_{i}=0\) and \([0\quad 1]\) when \(y_{i}=1\). We consider node feature vectors that are sampled from a uniform distribution and biased towards a particular class: when \(y_{i}=0,\mathbf{x_{i}}=[(0.5+p)\quad(0.5-p)]\) and when \(y_{i}=1,\mathbf{x_{i}}=[(0.5-p)\quad(0.5+p)]\), where parameter \(p\in[0,0.5]\) controls the 'agreement' between the node features and its class label. The final prediction for node \(i\) is \(\mathbf{argmax}\mathbf{z_{i}}\) where \(\mathbf{z_{i}}\) is the output logit vector of \(F\). We begin by solving for \(F\)'s optimal weight matrix \(\mathbf{W}\), and then apply \(F\) to \(t\). We consider a test node \(t\) with local homophily ratio as \(h+\alpha_{t}=h_{t}\), where \(\alpha_{t}\in[-h,1-h]\) is the shift \(i\) local homophily level compared to the global homophily level. Under this setup, we analyze how \(t\)'s prediction is impacted as its local homophily ratio \(h_{t}\) shifts relative to \(h\), the global homophily ratio used to train \(F\). In Thereom 1, without loss of generality, we consider the impacts of \(h_{t}\) when t's class label is \(y_{t}=0\).

**Theorem 1**: _Consider a test node \(t\) with local homophily ratio \(h+\alpha_{t}\), label \(\mathbf{y_{t}}=[1\quad 0]\), and node features \(\mathbf{x_{t}}=[(0.5+p)\quad(0.5-p)]\). The class prediction from \(F\) for node \(t\) is a function of the global homophily level and the shift of the local homophily level, given by \(\mathbf{argmax}\mathbf{z_{t}}\), where \(\mathbf{z_{t}}=\mathbf{y_{t}}+b_{1}\left[\alpha_{t}\quad-\alpha_{t}\right]\) and \(b_{1}=d/(1+d(2h-1))\)._
**Proof.** The proof can be found in App. A.2.1. We provide additional analysis on a 2-layer variant of \(F\), formulated as \((\mathbf{A}+\mathbf{I})^{\mathbf{2}}\mathbf{X}\mathbf{W}\) in App. A.2.3.

**Main Implications of Theorem 1.** This theorem provides a _direct relationship between a test node's performance and the node's local homophily ratio_ as it deviates from the global homophily ratio. Specifically, we can expect the _performance to degrade_ when a test node either becomes _more homophilous relative to a heterophilous graph_ or _more heterophilous relative to a homophilous graph_. To further understand and demonstrate the implications of \(\alpha_{t}\), we analyze three settings that naturally arise for the global homophily: (1) \(0\leq h<0.5\), (2) \(h=0.5\), and (3) \(0.5<h\leq 1\). We note that while the node degrees can influence the conditions that cause \(\alpha_{t}\) to impact \(\mathbf{z_{t}}\) (through \(b_{1}\)), we show in App. A.2.1 that this mostly occurs for extremely low-degree nodes. Furthermore, previous work corroborates our findings regarding the difficulty with low-degree nodes under heterophily [7, 8, 33]; however, our analysis extends this observation to demonstrate a significantly more complex interplay between node degree, global homophily, and shift in local homophily.

**Setting 1: Heterophilous \((\mathbf{0}\leq\boldsymbol{h}<\mathbf{0.5})\):** In this scenario, when \(d(2h-1)<-1\), \(b_{1}<0\), leading to \(\mathbf{z_{t}}=\mathbf{y_{t}}+|b_{1}|\left[-\alpha_{t}\quad\alpha_{t}\right]\), where \(b_{1}\)'s sign has been distributed into the vector. Thus,

\[\mathbf{z_{t}}=\begin{cases}\mathbf{y_{t}}+|b_{1}|\left[\left|\alpha_{t} \right|\quad-|\alpha_{t}|\right],&\text{if }h_{t}\leq h\\ \mathbf{y_{t}}+|b_{1}|\left[-\alpha_{t}\quad\alpha_{t}\right],&\text{if }h_{t}>h, \end{cases} \tag{3}\]

where the sign of \(\alpha_{t}\) has been integrated into the vectors. We can then deduce that (globally) heterophilous graphs, when \(b_{1}<0\) is satisfied, **will cause \(F\) to degrade in performance as the test node's local homophily increases**, denoted by the score increase of the wrong class in the second case of Equation (3). Additionally, when local homophily decreases, the predictions will improve given the increase in score for the correct class of the first case in Equation (3), however as \(h<0.5\), \(\alpha_{t}\) has a smaller possible range of values, minimizing the impact on \(F\)'s predictions.

**Setting 2: Mixed Homophily (\(\boldsymbol{h}=\mathbf{0.5}\))**: When the graph is not strongly homophilous nor strongly heterophilous (i.e., \(h=0.5\)), \(b_{1}=d\), leading to:

\[\mathbf{z_{t}}=\begin{cases}\mathbf{y_{t}}+d\left[-|\alpha_{t}|\quad|\alpha_{ t}|\right],&\text{if }h_{t}\leq 0.5\\ \mathbf{y_{t}}+d\left[\alpha_{t}\quad-\alpha_{t}\right],&\text{if }h_{t}>0.5. \end{cases} \tag{4}\]

In this case, we find that \(F\) will have improved performance when the local homophily of a test node is increased. Conversely, decreased local homophily for a test node will decrease performance. This is the only case that agrees with previous work regarding high homophily as a direct indicator of performance. Notably, the prediction directly depends on \(d\), potentially leading to performance variations that are dominated by degree, rather than local homophily.

**Setting 3: Homophilous (\(\mathbf{0.5}<\boldsymbol{h}\leq\mathbf{1}\))**: In this scenario, \(b_{1}>0\), leading to:

\[\mathbf{z_{t}}=\begin{cases}\mathbf{y_{t}}+|b_{1}|\left[-|\alpha_{t}|\quad| \alpha_{t}|\right],&\text{if }h_{t}\leq h\\ \mathbf{y_{t}}+|b_{1}|\left[\alpha_{t}\quad-\alpha_{t}\right],&\text{if }h_{t}>h. \end{cases} \tag{5}\]

We can then deduce that (globally) homophilous graphs **will cause \(F\) to degrade in performance as a test node's local homophily decreases**, denoted by the score increase of the first case of Equation (5). When local homophily increases, the predictions will improve, however as \(h>0.5\), \(\alpha_{t}\) has a smaller range of values, minimizing impact on the predictions.

## 5 Generalization of Theoretical Results via Synthetic Data Analysis

To display how the theoretical relationship between local homophily and classification performance generalizes, we introduce a graph generator that enables control over the local homophily ratios across a graph and conduct an extensive empirical analysis to study the following research questions: **(Q1)** What performance disparities arise across the range of local homophily values as the global homophily is varied? and **(Q2)** Do GNNs built specifically for heterophily display different performance patterns across varying local homophily ratio ranges as compared to simpler GNN architectures?

### Synthetic Data Generation

Building on the preferential attachment model where a compatibility matrix governs edge likelihood [7, 12], we modify the generator to allow a node's homophily level to be either randomly
assigned or defined by the compatibility matrix. Below we explain the generation process and detail the graph generation model in Algorithm 1. At a high level, the steps to add a node to a synthetic graph are: (1) Sample a class label, (2) Generate node features, and (3) Add connections based on assigned homophily level. The code is available in an anonymized repository1. We provide related work for graph generation in App. A.3.1, and additional property analysis in App. A.3.3.

Footnote 1: [https://anonymous.4open.science/r/HeterophilyDiscrepancyGNN-85FB](https://anonymous.4open.science/r/HeterophilyDiscrepancyGNN-85FB)

**Class and Feature Generation.** For a node \(i\), label \(y_{i}\) is sampled from probability distribution \(P(\{0,...,c\})\) with \(c\) possible classes. Features \(\mathbf{x_{i}}\) are generated from a 2D Gaussian, where each dimension has a mean of \(\epsilon*y_{i}\) and standard deviation of 1, where \(\epsilon\in[0,1]\) introduces noise into the features. When \(\epsilon=1\), the label \(y_{i}\) is explicitly encoded, when \(\epsilon=0\), \(y_{i}\) is unrecoverable.

**Structure Generation.** Similar to previous heterophily analyses, we define a class compatibility matrix \(\mathbf{H}_{L}\) with diagonal elements \(h\), denoting the probability of connecting nodes with similar classes (homophilous), and off-diagonals elements \((1-h)/c\), denoting the probability of connecting nodes with different classes (heterophilous) [7; 12]. During generation, a new node \(u\) is attached to an existing node \(v\) as \(P\left((u,v)\in E\right)\propto\left[\mathbf{H}_{L}\right]_{y_{u},y_{v}}\). To control the local homophily ratios, we introduce a uniformity parameter \(\rho\) such that with probability \(\rho\), a node \(i\)'s local homophily ratio \(h_{i}\) is sampled at random from a uniform distribution, \(U(0,1)\). As \(\rho\) increases, more local homophily ratios follow the random distribution, rather than the compatibility matrix. Since the preferential attachment model adds nodes sequentially, it is possible that the local homophily of nodes early in the generation process drift from their original values. To correct this, we keep track of the drift per node \(i\) through \(drift_{i}\), and prioritize connections to high-drift nodes (i.e., a node \(drift_{i}>\delta\), where \(\delta\) is a hyperparameter that defines the drift threshold) that would return the node's local homophily ratio back to its original value.

``` Input: Total nodes \(n\), \(m\) edges to add per step, label probability distribution \(P(\{0,...,c\})\), uniformity probability \(\rho\), class compatibility matrix \(\mathbf{H}_{L}\), drift change cutoff \(\delta\)
1 Initialize \(G\) with \(m\) nodes and \(m\) edges according to \(\mathbf{H}_{L}\) ; // Details in App. A.3.2
2 Initialize vector \(drift\) to hold change in homophily per node \(drift_{0},...,drift_{m}=0\)
3for\(u=m\) to \(n\)do
4 Add node \(u\) to \(G\)
5 Sample label \(y_{u}\sim P(\{0,...,c\})\)
6\(N_{1}(u)\) = GetNeighbors(\(G\), \(m\), \(u\), \(drift\), \(\rho\), \(\mathbf{H}_{L}\), \(\delta\))
7for\(v\) in \(N_{1}(u)\)do
8 Add edge \((u,v)\) to \(G\)
9if\(y_{u}\) = \(y_{v}\)then
10\(drift[v]\) *= 1 ; // Drifted more homophilous
11else
12\(drift[v]\) *= 1 ; // Drifted more heterophilous
13\(drift[u]=0\)
14
15
16
17
18
19
20
21 end
22
23 end
24
25 end
26
27 end
28
29 end
30 end
310
32 end
333 end
34
35 end
36
37 end
38
39 end
30 end
30 end
311
32 end
33 end
34
35 end
36
37 end
38 end
39
40 end
41 end
42 end
43 end
44 end
45
46 end
47 end
48
49 end
50 end
510
52 end
53 end
540
55 end
56
57 end
58 end
590 end
591 end
60 end
611 end
62
63 end
64
65 end
66 end
67
68 end
692 end
693
70 end
80 end
810
82 end
83
84 end
85
86 end
87
88 end
894
895 end
80
80 end
811 end
820
83 end
84
85 end
86
87 end
88 end
896
897 end
80
80 end
821
898 end
80
899 end
810
830 end
84
850 end
86
871 end
88
899 end
88 end
890
891 end
800
892 end
801
893 end
894
895 end
896
897 end
898
899 end
802
899 end
803
899 end
804
897 end
805
898 end
806
899 end
807
899 end
810
811 end
822
812 end
813
814 end
815
816 end
817
818 end
823
83 end
840
841 end
85
851 end
867
878 end
88
889
889 end
899
88 end
890
891 end
800
892 end
803
893 end
894
895
896 end
897
898 end
899
898
899 end
800
899
899 end
810
899 end
8110
812 end
813
8140 end
815
816
817 end
818
818 end
8199
8190
8191 end
824
8192 end
825
826
827 end
828
830 end
831
832 end
843
844 end
856
857 end
868
871 end
872
873 end
874
875
889 end
889
896
897 end
898
899
898 end
899
899 end
800
899
899 end
8100
8999
899 end
8111 end
8000
812 end
813
8141 end
815
816
817 end
818
818 end
8192
8193 end
8194
8195
8196 end
817
8197 end
818
8198
8198 end
820
81997
8198 end
8210
822
8210 end
823
823 end
824
825
826
827 end
828
828 end
8299
830
8310 end
832
833 end
834
835
836 end
837
838 end
839
847
848 end
849
849
8499 end
850
851
850 end
852
853
854 end
856
857
858 end
859
860
859
859 end
857
859
8610 end
862
863
864 end
867
868
869 end
878
879
888 end
889
889
889 end
899
899
8999
899 end
899
899
899
8999

8999 end
8100
8999
8999

89999

89999

999999

999999

9999999

9999999

9999999
GNNs while jointly varying global and local homophily levels. An additional study for \(\rho=0.75\) is provided in Figure 8 of App. A.3.4, demonstrating how discrepancy can be alleviated when the entire range of local homophily ratios has a sufficient number of nodes. For each combination of \(h\) and \(\rho\), we generate 10 graph with 5000 nodes and 100k edges (i.e. n = 5000, m = 20), and split the nodes into a 50-25-25% split for train, validation, and test. To match our theoretical analysis, we focus on binary classification. For evaluation, we compare the performance across models and global homophily ratios as the local homophily ratio is varied. To compute localized performance, we split the test nodes into four groups based on their local homophily ratios and calculate an F1 score per group. Per bin, we report the average and standard deviation for F1 over the 10 generated graphs. Results are presented in Figures 1 of the main text, and Figures 6, 7 in App. A.3.4
performance often degrades as local homophily increases, while when \(h>0.5\) (higher global homophily), performance often degrades as local homophily decreases. The results align well with our theoretical analysis, showing strong generalization of our findings to more complex graph structures and GNN architectures. Together, **our theoretical and empirical results indicate that assuming high homophily always indicates high performance may oversimplify the GNN's behavior, leading retrospective analyses astray when diagnosing performance degradation.**

**(Q2) Performance disparities for homophilous vs. heterophilous GNNs.** To understand how different GNN designs amplify or reduce discrepancy, we analyze the trend of local performances across models. While all models achieve similar global performance, we observe that the models perform differently depending on the local homophily range. As shown in Figure 1 (and Figure 5 in App. A.3.4), homophilous models often have higher performance for test nodes with local homophily levels that are close to the global homophily, whereas heterophily-based models perform better than homophilous models for nodes with local homophily levels far from the global homophily. These insights highlight the different behaviors of the two architectural designs, indicating that **models designed for heterophily are able to alleviate performance discrepancies across nodes, while homophilous models exacerbate discrepancy in strongly homophilous/heterophilous graphs**. These results suggest that heterophilous models offer a better performance trade-off between nodes with over- and under-represented local homophily levels, displaying minor degradation on the over-represented nodes and significant improvement on the under-represented nodes.

## 6 Real-world Empirical Evaluation

We now demonstrate how our results extend to real-world datasets.

**Data and Setup.** We choose five real-world graphs: two homophilous (Cora [34], Coauthor-CS [35]) and three heterophilous (Cornell [36], Wisconsin [36], Squirrel [37]). We choose the heterophilous datasets due to their historically inconclusive performance when comparing GNNs to non-graph-based deep learning baselines [7; 13]. Our analysis aims to provide insight into why prior results have been inconclusive and explain their poor performance from a local perspective. For each dataset, we perform 30 random 50-25-25% splits of the nodes to obtain the train, validation, and test sets, except for Cora and Coauthor-CS where we perform 5 splits due to graph size and low variance. We train the same architectures as in the synthetic experiments, seen in Section 5.2.

We report results in Figure 2 of the main text, and Figure 10 in App. A.4.2. While we group all test nodes into four local homophily ranges, we limit the ranges for Cornell and Wisconsin in Figure 2 due to having less than three test nodes in local homophily ranges above 0.5 and 0.6, respectively. Additionally, features may be more informative in certain local homophily ranges, obscuring when performance degrades due to homophily or uninformative features. Thus, we report the difference in F1 score between the different GNNs and the graph-agnostic MLP, \(\Delta\)F1 = (F1-score GNN - F1-score MLP), to disentangle how performance relies on the node features as compared to the graph structure.

### Performance Discrepancies in Homophilous vs. Heterophilous Real-World Datasets

**Homophilous Graphs.** The homophilous graphs are shown in the two right-most plots of Figure 2. First, we highlight the nearly **0.6 drop in \(\Delta\)F1 across both datasets for test nodes with local homophily ratios far from the global homophily ratio**, performing worse than an MLP as denoted by the negative F1 score difference. Furthermore, this degradation is consistent across all of the GNN architectures, with H2GCN, which leverages heterophilous designs, maintaining generally higher performance as the nodes become more heterophilous. This result demonstrates the practical implications of our theoretical analysis, allowing us to additionally demonstrate that degradation can occur under rich feature sets. Notably, the MLP outperforms all of the GNN architectures in the heterophilous parts of the graph, implying the neighborhood information is actively corrupting performance in these regions due to the GNN's reliance on the global homophily.

**Heterophilous Graphs.** The heterophilous datasets are shown on the three left-most plots of Figure 2. Compared to the homophilous datasets, the GNNs achieve poor performance relative to the MLP for nearly all local homophily ranges. However, our local analysis identifies a mechanism for _how_ this arises: exacerbated performance degradation for nodes with local homophily ratios far from the global homophily ratio. Despite the MLP model outperforming the GNN models across Cornell, Wisconsin, and Squirrel, there is still a notable degradation in performance as the local homophily
ranges increase, **causing a 0.2-0.4 drop in \(\Delta\)F1 between the region which contains the global homophily ratio and the furthest bin**. We hypothesize that degree can influence whether GNNs degrade in performance on heterophilous graphs, as seen in our theoretical analysis in App. A.2.1, causing this drop to be lower as compared to the homophilous graphs. Again, H2GCN displays high uniformity across these regimes for both datasets, following the trends seen in the synthetic data. Interestingly, for Squirrel, we also observe a significant difference in MLP performance across the various local homophily ranges, indicating that the features are intrinsically more informative in certain regions. When accounting for this through \(\Delta\)F1, we see similar degradation to that in the synthetic and homophilous datasets, again with the heterophilous GNNs tending to perform best.

### Discussion

Two key insights emerge that have yet to be established in other analyses: (a) nodes with higher local homophily are not inherently easier to classify, as seen by the relative drops in performance on heterophilous datasets, and (b) heterophilous designs improve learning across nearly all local homophily ranges, not just one particular range, alleviating performance discrepancies across nodes. We note that there might be additional factors which give rise to performance variations across local homophily ratios. For instance, previous works have identified that, under certain settings, nodes with extreme homophily levels can be easier to classify [13, 16, 17]. Moreover, the ease of classification has been tied to the interaction of degree and homophily, pointing towards high degree nodes as the easiest setting [8]. Performance variations due to raw structural properties (e.g. degree or local homophily ratio) and local homophily shift are not necessarily mutually exclusive, nor do they conflict with our results. Instead, we hypothesize both factors can interact, amplifying performance disparities across homophily ranges, further necessitating future work which studies their interplay.

## 7 Conclusion

In this work, we take a local perspective focused on discerning how nodes of varying local homophily levels can experience performance discrepancies. We first theoretically demonstrated that classification performance degrades as the local homophily ratio of a node deviates from the global homophily ratio. To demonstrate the generalizability of our findings, we proposed a new parsimonious synthetic graph generator that allows generating graphs with varying global and local homophily. We demonstrated that our theoretical insights still hold in more general settings, finding that performance degradation can occur in either highly homophilous or heterophilous settings. Furthermore, we showed that this disparity in performance can be reduced by using GNN models which adopt explicit mechanisms to support heterophily, providing insight into how GNNs with heterophilous designs improve performance globally. Our experiments on real-world datasets of varying global homophily

Figure 2: Real-words graphs: Difference in performance, \(\Delta\)F1=F1(GNN) - F1(MLP), for GNN models across ranges of local homophily ratios (more GNNs in App. A.4.2), averaged over multiple splits. Our results elucidate _how_ models achieve different global performance, where heterophilous models (bars in reds) better tend to combat the systematic performance discrepancy seen in homophilous models (bars in blues). Gray indicates the range that the global homophily ratio falls in; negative bars indicate worse performance than MLP.
ratios confirm the practical implications of our insights, exhibiting similar disparity patterns. The discovery and characterization of GNN degradation through shifts in local homophily relative to a graph's global homophily necessitates the development of new GNNs that are able to explicitly handle such data shifts. Additionally, our findings highlight how, in human-facing applications of GNNs, individuals might experience disparate treatment under a GNN due to structural properties of the underlying graph, opening new research directions in algorithmic fairness.
