Demystifying Structural Disparity in Graph Neural Networks: Can One Size
  Fit All?
Recent studies on Graph Neural Networks(GNNs) provide both empirical and
theoretical evidence supporting their effectiveness in capturing structural
patterns on both homophilic and certain heterophilic graphs. Notably, most
real-world homophilic and heterophilic graphs are comprised of a mixture of
nodes in both homophilic and heterophilic structural patterns, exhibiting a
structural disparity. However, the analysis of GNN performance with respect to
nodes exhibiting different structural patterns, e.g., homophilic nodes in
heterophilic graphs, remains rather limited. In the present study, we provide
evidence that Graph Neural Networks(GNNs) on node classification typically
perform admirably on homophilic nodes within homophilic graphs and heterophilic
nodes within heterophilic graphs while struggling on the opposite node set,
exhibiting a performance disparity. We theoretically and empirically identify
effects of GNNs on testing nodes exhibiting distinct structural patterns. We
then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs,
revealing reasons for the performance disparity, namely the aggregated feature
distance and homophily ratio difference between training and testing nodes.
Furthermore, we demonstrate the practical implications of our new findings via
(1) elucidating the effectiveness of deeper GNNs; and (2) revealing an
over-looked distribution shift factor on graph out-of-distribution problem and
proposing a new scenario accordingly.
Haitao Mao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, Jiliang Tang
# Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?

###### Abstract

Recent studies on Graph Neural Networks(GNNs) provide both empirical and theoretical evidence supporting their effectiveness in capturing structural patterns on both homophilic and certain heterophilic graphs. Notably, most real-world homophilic and heterophilic graphs are comprised of a mixture of nodes in both homophilic and heterophilic structural patterns, exhibiting a structural disparity. However, the analysis of GNN performance with respect to nodes exhibiting different structural patterns, e.g., homophilic nodes in heterophilic graphs, remains rather limited. In the present study, we provide evidence that Graph Neural Networks(GNNs) on node classification typically perform admirably on homophilic nodes within homophilic graphs and heterophilic nodes within heterophilic graphs while struggling on the opposite node set, exhibiting a performance disparity. We theoretically and empirically identify effects of GNNs on testing nodes exhibiting distinct structural patterns. We then propose a rigorous, non-i.i.d PAC-Bayesian generalization bound for GNNs, revealing reasons for the performance disparity, namely the aggregated feature distance and homophily ratio difference between training and testing nodes. Furthermore, we demonstrate the practical implications of our new findings via (1) elucidating the effectiveness of deeper GNNs; and (2) revealing an over-looked distribution shift factor on graph out-of-distribution problem and proposing a new scenario accordingly.

## 1 Introduction

Graph Neural Networks (GNNs) [1; 2; 3; 4] are a powerful technique for tackling a wide range of graph-related tasks [5; 3; 6; 7; 8; 9], especially node classification [2; 4; 10; 11], which requires predicting unlabeled nodes based on the graph structure, node features, and a subset of labeled nodes. The success of GNNs can be ascribed to their ability to capture structural patterns through the aggregation mechanism that effectively combines feature information from neighboring nodes [12].

GNNs have been widely recognized for their effectiveness on homophilic graphs [13; 2; 10; 4; 14; 15; 16]. In homophilic graphs, connected nodes tend to share the same label, which we refer to as _homophilic patterns_. An example of the homophilic pattern is depicted in the upper part of Figure 1, where node features and node labels are denoted by colors (i.e., blue and red) and numbers (i.e., 0 and 1), respectively. We can observe that all connected nodes exhibit homophilic patterns and share the same label 0. Recently, several studies have demonstrated that GNNs can also

Figure 1: Examples of homophilic and heterophilic patterns. Colors/numbers indicate node features/labels.
perform well on certain heterophilic graphs [17; 12; 18]. In heterophilic graphs, connected nodes tend to have different labels, which we refer to as _heterophilic patterns_. The example in the lower part of Figure 1 shows the heterophilic patterns. Based on this example, we intuitively illustrate how GNNs can work on such heterophilic patterns (lower right): after averaging features over all neighboring nodes, nodes with label 0 completely switch from their initial blue color to red, and vice versa; despite this feature alteration, the two classes remain easily distinguishable since nodes with the same label (number) share the same color (features).

However, existing studies on the effectiveness of GNNs [13; 17; 12; 18] only focus on either homophilic or heterophilic patterns solely and overlook the fact that real-world graphs typically exhibit a mixture of homophilic and heterophilic patterns. Recent studies [19; 20] reveal that many heterophilic graphs, e.g., Squirrel and Chameleon [21], contain over 20% homophilic nodes. Similarly, our preliminary study depicted in Figure 2 demonstrates that heterophilic nodes are consistently present in many homophilic graphs, e.g., PubMed [22] and Ogbn-arxiv [23]. Hence, real-world homophilic graphs predominantly consist of homophilic nodes as the majority structural pattern and heterophilic nodes in the minority one, while heterophilic graphs exhibit an opposite phenomenon with homophilic nodes in the majority and heterophilic ones in the minority.

To provide insights aligning the real-world scenario with structural disparity, we revisit the toy example in Figure 1, considering both homophilic and heterophilic patterns together. Specifically, for nodes labeled 0, both homophilic and heterophilic node features appear in blue before aggregation. However, after aggregation, homophilic and heterophilic nodes in label 0 exhibit different features, appearing blue and red, respectively. Such differences may lead to performance disparity between nodes in majority and minority patterns. For instance, in a homophilic graph with the majority pattern being homophilic, GNNs are more likely to learn the association between blue features and class 0 on account of more supervised signals in majority. Consequently, nodes in the majority structural pattern can perform well, while nodes in the minority structural pattern may exhibit poor performance, indicating an over-reliance on the majority structural pattern. Inspired by insights from the above toy example, we focus on answering following questions systematically in this paper: How does a GNN behave when encountering the structural disparity of homophilic and heterophilic nodes within a dataset? and Can one GNN benefit all nodes despite structural disparity?

**Present work**. Drawing inspiration from above intuitions, we investigate how GNNs exhibit different effects on nodes with structural disparity, the underlying reasons, and implications on graph applications. Our study proceeds as follows: **First**, we empirically verify the aforementioned intuition by examining the performance of testing nodes w.r.t. different homophily ratios, rather than the overall performance across all test nodes as in [12; 13; 18]. We show that GCN [2], a vanilla GNN, often underperforms MLP-based models on nodes with the minority pattern while outperforming them on the majority nodes. **Second**, we examine how aggregation, the key mechanism of GNNs, shows different effects on homophilic and heterophilic nodes. We propose an understanding of why GNNs exhibit performance disparity with a non-i.i.d PAC-Bayesian generalization bound, revealing that both feature distance and homophily ratio differences between train and test nodes are key factors leading to performance disparity. **Third**, we showcase the significance of these insights by exploring implications for (1) elucidating the effectiveness of deeper GNNs and (2) introducing a new graph out-of-distribution scenario with an over-looked distribution shift factor.

## 2 Preliminaries

**Semi-Supervised Node classification (SSNC).** Let \(G=(V,E)\) be an undirected graph, where \(V=\{v_{1},\cdots,v_{n}\}\) is the set of \(n\) nodes and \(E\subseteq V\times V\) is the edge set. Nodes are associated with node features \(\mathbf{X}\in\mathbb{R}^{n\times d}\), where \(d\) is the feature dimension. The number of class is denoted as \(K\). The adjacency matrix \(\mathbf{A}\in\{0,1\}^{n\times n}\) represents graph connectivity where \(\mathbf{A}[i,j]=1\) indicates an edge between nodes \(i\) and \(j\). \(\mathbf{D}\) is a degree matrix and \(\mathbf{D}[i,i]=d_{i}\) with \(d_{i}\) denoting degree of node \(v_{i}\). Given a small set of labeled nodes, \(V_{\text{tr}}\subseteq V\), SSNC task is to predict on unlabeled nodes \(V\setminus V_{\text{tr}}\).

**Node homophily ratio** is a common metric to quantify homophilic and heterophilic patterns. It is calculated as the proportion of a node's neighbors sharing the same label as the node [24; 25; 19]. It is formally defined as \(h_{i}=\frac{|\{u\in\mathcal{N}(v_{i}):y_{u}=y_{v}\}|}{d_{i}}\), where \(\mathcal{N}(v_{i})\) denotes the neighbor node set of \(v_{i}\) and \(d_{i}=|\mathcal{N}(v_{i})|\) is the cardinality of this set. Following [19; 26; 24], node \(i\) is considered to be homophilic when more neighbor nodes share the same label as the center node with \(h_{i}>0.5\). We
define the graph homophily ratio \(h\) as the average of node homophily ratios \(h=\frac{\sum_{i\in V}h_{i}}{|V|}\). Moreover, this ratio can be easily extended to higher-order cases \(h_{i}^{(k)}\) by considering \(k\)-order neighbors \(\mathcal{N}_{k}(v_{i})\).

**Node subgroup** refers to a subset of nodes in the graph sharing similar properties, typically homophilic and heterophilic patterns measured with node homophily ratio. Training nodes are denoted as \(V_{\text{tr}}\). Test nodes \(V_{\text{te}}\) can be categorized into \(M\) node subgroups, \(V_{\text{te}}=\bigcup_{m=1}^{M}V_{m}\), where nodes in the same subgroup \(V_{m}\) share similar structural pattern.

## 3 Effectiveness of GNN on nodes with different structural properties

In this section, we explore the effectiveness of GNNs on different node subgroups exhibiting distinct structural patterns, specifically, homophilic and heterophilic patterns. It is different from previous studies [12; 13; 17; 27; 18] that primarily conduct analysis on the whole graph and demonstrate effectiveness with an overall performance gain. These studies, while useful, do not provide insights into the effectiveness of GNNs on different node subgroups, and may even obscure scenarios where GNNs fail on specific subgroups despite an overall performance gain. To accurately gauge the effectiveness of GNNs, we take a closer examination on node subgroups with distinct structural patterns. The following experiments are conducted on two common homophilic graphs, Ogbn-arxiv [23] and Pubmed [22], and two heterophilic graphs, Chameleon and Squirrel [21]. These datasets are chosen since GNNs can achieve better overall performance than MLP. Experiment details and related work on GNN disparity are in Appendix G and A, respectively.

**Existence of structural pattern disparity within a graph** is to recognize real-world graphs exhibiting different node subgroups with diverse structural patterns, before investigating the GNN effectiveness on them. We demonstrate node homophily ratio distributions on the aforementioned datasets in Figure 2. We can have the following observations. **Obs.1:** All four graphs exhibit a mixture of both homophilic and heterophilic patterns, rather than a uniform structural patterns. **Obs.2:** In homophilic graphs, the majority of nodes exhibit a homophilic pattern with \(h_{i}{>}0.5\), while in heterophilic graphs, the majority of nodes exhibit the heterophilic pattern with \(h_{i}{\leq}0.5\). We define nodes in majority structural pattern as majority nodes, e.g., homophilic nodes in a homophilic graph.

Figure 3: Performance comparison between GCN and MLP-based models. Each bar represents the accuracy gap on a specific node subgroup exhibiting a homophily ratio within the range specified on the x-axis. MLP-based models often outperform GCN on heterophilic nodes in homophilic graphs and homophilic nodes in heterophilic graphs with a positive value.

Figure 2: Node homophily ratio distributions. All graphs exhibit a mixture of homophilic and heterophilic nodes despite various graph homophily ratio \(h\).
**Examining GCN performance on different structural patterns.** To examine the effectiveness of GNNs on different structural patterns, we compare the performance of GCN [2] a vanilla GNN, with two MLP-based models, vanilla MLP and Graphless Neural Network (GLNN) [28], on testing nodes with different homophily ratios. It is evident that the vanilla MLP could have a large performance gap compared to GCN (i.e., 20% in accuracy) [12; 28; 2]. Consequently, the performance disparity can be overwhelmed by such gap which renders the effect from structural patterns. Therefore, we also include an advanced MLP model GLNN. It is trained in an advanced manner via distilling GNN predictions and exhibits performance on par with GNNs. Notably, only GCN has the ability to leverage structural information during the inference phase while both vanilla MLP and GLNN models solely rely on node features as input. This comparison ensures a fair study on the effectiveness of GNNs in capturing different structural patterns with mitigating the effects of node features. Experimental results on four datasets are presented in Figure 3. In the figure, y-axis corresponds to the accuracy differences between GCN and MLP-based models where positive indicates MLP models can outperform GCN; while x-axis represents different node subgroups with nodes in the subgroup satisfying homophily ratios in the given range, e.g., [0.0-0.2]. Based on experimental results, the following key observations can be made: **Obs.1:** In homophilic graphs, both GLNN and MLP demonstrate superior performance on the heterophilic nodes with homophily ratios in [0-0.4] while GCN outperforms them on homophilic nodes. **Obs.2:** In heterophilic graphs, MLP models often outperform on homophilic nodes yet underperform on heterophilic nodes. Notably, vanilla MLP performance on Chameleon is worse than that of GCN across different subgroups. This can be attributed to the training difficulties encountered on Chameleon, where an unexpected similarity in node features from different classes is observed [29]. Our observations indicate that despite the effectiveness of GCN suggested by [12; 18; 13], GCN exhibits limitations with performance disparity across homophilic and heterophilic graphs. It motivates investigation why GCN benefits majority nodes, e.g., homophilic nodes in homophilic graphs, while struggling with minority nodes. Moreover, additional results on more datasets and significant test results are shown in Appendix H and L.

**Organization.** In light of the above observations, we endeavor to understand the underlying causes of this phenomenon in the following sections by answering the following research questions. Section 3.1 focuses on how aggregation, the fundamental mechanism in GNNs, affects nodes with distinct structural patterns differently. Upon identifying differences, Section 3.2 further analyzes how such disparities contribute to superior performance on the majority nodes as opposed to minority nodes. Building on these observations, Section 3.3 recognizes the key factors driving performance disparities on different structural patterns with a non-i.i.d. PAC-Bayes bound. Section 3.4 empirically corroborates the validity of our theoretical analysis with real-world datasets.

### How does aggregation affect nodes with structural disparity differently?

In this subsection, we examine how aggregation reveals different effects on nodes with structural disparity, serving as a precondition for performance disparity. Specifically, we focus on the discrepancy between nodes from the same class but with different structural patterns.

For a controlled study on graphs, we adopt the contextual stochastic block model (CSBM) with two classes. It is widely used for graph analysis, including generalization [12; 13; 30; 17; 31; 32], clustering [33], fairness [34; 35], and GNN architecture design [36; 37; 38]. Typically, nodes in CSBM model are generated into two disjoint sets \(\mathcal{C}_{1}\) and \(\mathcal{C}_{2}\) corresponding to two classes, \(c_{1}\) and \(c_{2}\), respectively. Each node with \(c_{i}\) is associated with features \(x\in\mathbb{R}^{d}\) sampling from \(N(\mathbf{\mu}_{i},I)\), where \(\mu_{i}\) is the feature mean of class \(c_{i}\) with \(i\in\{1,2\}\). The distance between feature means in different classes \(\rho=\|\mathbf{\mu}_{1}-\mathbf{\mu}_{2}\|\), indicating the classification difficulty on node features. Edges are then generated based on intra-class probability \(p\) and inter-class probability \(q\). For instance, nodes with class \(c_{1}\) have probabilities \(p\) and \(q\) of connecting with another node in class \(c_{1}\) and \(c_{2}\), respectively. The CSBM model, denoted as CSBM(\(\mathbf{\mu}_{1},\mathbf{\mu}_{2},p,q\)), presumes that all nodes follow either homophilic with \(p>q\) or heterophilic patterns \(p<q\) exclusively. However, this assumption conflicts with real-world scenarios, where graphs often exhibit both patterns simultaneously, as shown in Figure 2. To mirror such scenarios, we propose a variant of CSBM, referred to as CSBM-Structure (CSBM-S), allowing for the simultaneous description of homophilic and heterophilic nodes.

**Definition 1** (CSBM-S\((\mu_{1},\mu_{2},(p^{(1)},q^{(1)}),(p^{(2)},q^{(2)}),\Pr(\text{homo}))\)).: _The generated nodes consist of two disjoint sets \(\mathcal{C}_{1}\) and \(\mathcal{C}_{2}\). each node feature \(x\) is sampled from \(N(\mu_{i},I)\) with \(i\in\{1,2\}\). Each set \(\mathcal{C}_{i}\) consists of two subgroups: \(\mathcal{C}_{i}^{(1)}\) for nodes in homophilic pattern with intra-class and inter-class edge
probability \(p^{(1)}>q^{(1)}\) and \(\mathcal{C}_{i}^{(2)}\) for nodes in heterophilic pattern with \(p^{(2)}>q^{(2)}\). \(\Pr(\text{homo})\) denotes the probability that the node is in homophilic pattern. \(\mathcal{C}_{i}^{(j)}\) denotes node in class \(i\) and subgroup \(j\) with \((p^{(j)},q^{(j)})\). We assume nodes follow the same degree distribution with \(p^{(1)}+q^{(1)}=p^{(2)}+q^{(2)}\)._

Based on the neighborhood distributions, the mean aggregated features \(\mathbf{F}=\mathbf{D}^{-1}\mathbf{A}\mathbf{X}\) obtained follow Gaussian distributions on both homophilic and heterophilic subgroups.

\[\mathbf{f}_{i}^{(j)}\sim N\left(\frac{p^{(j)}\boldsymbol{\mu}_{1}+q^{(j)} \boldsymbol{\mu}_{2}}{p^{(j)}+q^{(j)}},\frac{\mathbf{I}}{\sqrt{d_{i}}}\right), \text{for}\;i\in\mathcal{C}_{1}^{(j)};\mathbf{f}_{i}^{(j)}\sim N\left(\frac{q ^{(j)}\boldsymbol{\mu}_{1}+p^{(j)}\boldsymbol{\mu}_{2}}{p^{(j)}+q^{(j)}}, \frac{\mathbf{I}}{\sqrt{d_{i}}}\right),\text{for}\;i\in\mathcal{C}_{2}^{(j)} \tag{1}\]

Where \(\mathcal{C}_{i}^{(j)}\) is the node subgroups with structural pattern with \((p^{(j)},q^{(j)})\) in label \(i\). Our initial examination of different effects on aggregation focuses on the aggregated feature distance between homophilic and heterophilic node subgroups within class \(c_{1}\).

**Proposition 1**.: _The aggregated feature mean distance between homophilic and heterophilic node subgroups within class \(c_{1}\), denoted as \(\left\|\frac{p^{(1)}\boldsymbol{\mu}_{1}+q^{(1)}\boldsymbol{\mu}_{2}}{p^{(1)} +q^{(1)}}-\frac{p^{(2)}\boldsymbol{\mu}_{1}+q^{(2)}\boldsymbol{\mu}_{2}}{p^{(2) }+q^{(2)}}\right\|>0\), since they are from different feature distribution after aggregation, larger than the distance \(0\) before aggregation since they draw from the same distribution, regardless of different structural pattern._

Notably, the distance between original features is regardless of the structural pattern. This proposition suggests that aggregation results in a distance gap between different patterns within the same class.

In addition to node feature differences with the same class, we further examine the discrepancy between nodes \(u\) and \(v\) with the same aggregated feature \(\mathbf{f}_{u}=\mathbf{f}_{v}\) but different structural patterns. We examine the discrepancy with the probability difference of nodes \(u\) and \(v\) in class \(c_{1}\), denoted as \(|\mathbf{P}_{1}(y_{u}=c_{1}|\mathbf{f}_{u})-\mathbf{P}_{2}(y_{v}=c_{1}| \mathbf{f}_{v})|\). \(\mathbf{P}_{1}\) and \(\mathbf{P}_{2}\) are the conditional probability of \(y=c_{1}\) given the feature \(\mathbf{f}\) on structural patterns \((p^{(1)},q^{(1)})\) and \((p^{(2)},q^{(2)})\), respectively.

**Lemma 1**.: _With assumptions (1) A balance class distribution with \(\mathbf{P}(Y=1)=\mathbf{P}(Y=0)\) and (2) aggregated feature distribution shares the same variance \(\sigma\). When nodes \(u\) and \(v\) have the same aggregated features \(\mathbf{f}_{u}=\mathbf{f}_{v}\) but different structural patterns, \((p^{(1)},q^{(1)})\) and \((p^{(2)},q^{(2)})\), we have:_

\[|\mathbf{P}_{1}(y_{u}=c_{1}|\mathbf{f}_{u})-\mathbf{P}_{2}(y_{v}=c_{1}| \mathbf{f}_{v})|\leq\frac{\rho^{2}}{\sqrt{2\pi}\sigma}|h_{u}-h_{v}| \tag{2}\]

Notably, above assumptions are not strictly necessary but employed for the sake of elegant expression. \(\rho=\|\boldsymbol{\mu}_{1}-\boldsymbol{\mu}_{2}\|\) is the original feature separability, independent with structure. Lemma 1 implies that nodes with a small homophily ratio difference \(|h_{1}-h_{2}|\) are likely to share the same class, and vice versa. The proof details and additional analysis on between-class effects are provided in Appendix D.

### How does Aggregation Contribute to Performance Disparity?

We have established that aggregation can affect nodes with distinct structural patterns differently. However, it remains to be elucidated how such disparity contributes to performance improvement predominantly on majority nodes as opposed to minority nodes. It should be noted that, notwithstanding the influence on features, test performance is also profoundly associated with training labels. Performance degradation may occur when the classifier is inadequately trained with biased training labels.

We then conduct an empirical discriminative analysis taking both mean aggregated features and training labels into consideration. Drawing inspiration from existing literature [39; 40; 41; 42], we describe the discriminative ability with the distance between train class prototypes [43; 44], i.e., feature mean of each class, and the corresponding test class prototype within the same class \(i\). For instance, it can be denoted as \(||\mu_{i}^{\text{tr}}-\mu_{i}^{\text{ma}}||\), where \(\mu_{i}^{\text{tr}}\) and \(\mu_{i}^{\text{ma}}\) are the prototype of class \(i\) on train nodes and test majority nodes, respectively. A smaller value suggests that majority test nodes are close to train nodes within the same class, thus implying superior discriminative ability. A relative

Figure 4: Illustration on discriminative ratio variation along with aggregation. x-axis denotes the number of aggregations and y-axis denotes the discriminative ratio.
discriminative ratio is then proposed to compare the discriminative ability between majority and minority nodes. It can be denoted as: \(r\)=\(\sum_{i=1}^{K}\frac{||\mathbf{\mu}_{i}^{\text{mi}}-\mathbf{\mu}_{i}^{\text{mi}}||}{||\mathbf{ \mu}_{i}^{\text{mi}}-\mathbf{\mu}_{i}^{\text{mi}}||}\) where \(\mu_{i}^{\text{mi}}\) corresponds to the prototype on minority test nodes. A lower relative discriminative ratio suggests that majority nodes are easier to be predicted than minority nodes.

The relative discriminative ratios are then calculated on different hop aggregated features and original features denote as 0-hop. Experimental results are presented in Figure 4, where the discriminative ratio shows an overall decrease tendency as the number of aggregations increases across four datasets. This indicates that majority test nodes show better discriminative ability than the minority test nodes along with more aggregation. We illustrate more results on GCN in Appendix K. Furthermore, instance-level experiments other than class prototypes are in Appendix C.

### Why does Performance Disparity Happen? Subgroup Generalization Bound for GNNs

In this subsection, we conduct a rigorous analysis elucidating primary causes for performance disparity across different node subgroups with distinct structural patterns. Drawing inspiration from the discriminative metric described in Section 3.2, we identify two key factors for satisfying test performance: (1) test node \(u\) should have a close feature distance \(\min_{v\in V_{t}}\|\mathbf{f}_{u}-\mathbf{f}_{v}\|\) to training nodes \(V_{\text{tr}}\), indicating that test nodes can be greatly influenced by training nodes. (2) With identifying the closest training node \(v\), nodes \(u\) and \(v\) should be more likely to share the same class, where \(\sum_{c_{i}\in\mathcal{C}}|\mathbf{P}(y_{u}=c_{i}|\mathbf{f}_{u})-\mathbf{P}(y _{v}=c_{i}|\mathbf{f}_{v})|\) is required to be small. The second factor, focusing on whether two close nodes are in the same class, is dependent on the homophily ratio difference \(|h_{u}-h_{v}|\), as shown in Lemma 1. Notably, since training nodes are randomly sampled, their structural patterns are likely to be the majority one. Therefore, training nodes will show a smaller homophily ratio difference with majority test nodes sharing the same majority pattern than minority test nodes, resulting in the performance disparity in distinct structural patterns. We substantiate the above intuitions with controllable synthetic experiments in Appendix B.

To rigorously examine the role of aggregated feature distance and homophily ratio difference in performance disparity, we derive a non-i.i.d. PAC-Bayesian GNN generalization bound, based on the Subgroup Generalization bound of Deterministic Classifier [45]. We begin by stating key assumptions on graph data and GNN model to clearly delineate the scope of our theoretical analysis. All remaining assumptions, proof details, and background on PAC-Bayes analysis can be found in Appendix F. Moreover, a comprehensive introduction on the generalization ability on GNN can be found in A.

**Definition 2** (Generalized CSBM-S model).: _Each node subgroup \(V_{m}\) follows the CSBM distribution \(V_{m}\sim\text{CSBM}(\mathbf{\mu}_{1},\mathbf{\mu}_{2},p^{(i)},q^{(i)})\), where different subgroups share the same class mean but different intra-class and inter-class probabilities \(p^{(i)}\) and \(q^{(i)}\). Moreover, node subgroups also share the same degree distribution as \(p^{(i)}+q^{(i)}=p^{(j)}+q^{(j)}\)._

Instead of CSBM-S model with one homophilic and heterophilic pattern, we take the generalized CSBM-S model assumption, allowing more structural patterns with different levels of homophily.

**Assumption 1** (GNN model).: _We focus on SGC [15] with the following components: (1) a one-hop mean aggregation function \(g\) with \(g(X,G)\) denoting the output. (2) MLP feature transformation \(f(g_{i}(X,G);W_{1},W_{2},\cdots,W_{L})\), where \(f\) is a ReLU-activated \(L\)-layer MLP with \(W_{1},\cdots,W_{L}\) as parameters for each layer. The largest width of all the hidden layers is denoted as \(b\)._

Notably, despite analyzing simple GNN architecture theoretically, similar with [45; 12; 46], our theory analysis could be easily extended to the higher-order case with empirical success across different GNN architectures shown in Section 3.4.

Our main theorem is based on the PAC-Bayes analysis which typically aims to bound the generalization gap between the expected margin loss \(\mathcal{L}_{m}^{0}\) on test subgroup \(V_{m}\) for a margin \(0\) and the empirical margin loss \(\widehat{\mathcal{L}}_{\text{tr}}^{\gamma}\) on train subgroup \(V_{\text{tr}}\) for a margin \(\gamma\). Those losses are generally utilized in PAC-Bayes analysis[47; 48; 49; 50]. More details are found in Appendix F. The formulation is shown as follows:

**Theorem 1** (Subgroup Generalization Bound for GNNs).: _Let \(\tilde{h}\) be any classifier in the classifier family \(\mathcal{H}\) with parameters \(\{\widetilde{W}_{l}\}_{l=1}^{L}\), for any \(0<m\leq M\), \(\gamma\geq 0\), and large enough number of the training nodes \(N_{\text{tr}}=|V_{\text{tr}}|\), there exist \(0<\alpha<\frac{1}{4}\) with probability at least \(1-\delta\) over the sample of
\(y^{\prime r}:=\{y_{i}\}_{i\in V_{\sigma}}\), we have:

\[\mathcal{L}_{m}^{0}(\tilde{h})\leq\widehat{\mathcal{L}}_{\nu}^{\gamma}(\tilde{h}) +O\left(\underbrace{\frac{K\rho}{\sqrt{2\pi}\sigma}(\epsilon_{m}+|h_{\mathbf{r}}-h_ {m}|\cdot\rho)}_{\mathbf{(a)}}+\underbrace{\frac{b\sum_{l=1}^{L}\|\widetilde{W}_{ l}\|_{F}^{2}}{(\gamma/8)^{2/L}N_{\mathbf{r}}^{\alpha}}(\epsilon_{m})^{2/L}}_{\mathbf{(b)}}+ \mathbf{R}\right) \tag{3}\]

The bound is related to three terms: **(a)** describes both large homophily ratio difference \(|h_{\mathbf{r}}-h_{m}|\) and large aggregated feature distance \(\epsilon=\max_{j\in bV_{m}}\min_{i\in V_{\mathbf{r}}}\|g_{i}(X,G)-g_{j}(X,G)\|_{2}\) between test node subgroup \(V_{m}\) and training nodes \(V_{\mathbf{r}}\) lead to large generalization error. \(\rho=\|\mathbf{\mu}_{1}-\mathbf{\mu}_{2}\|\) denotes the original feature separability, independent of structure. \(K\) is the number of classes. **(b)** further strengthens the effect of nodes with the aggregated feature distance \(\epsilon\), leads to a large generalization error. **(c)**\(\mathbf{R}\) is a term independent with aggregated feature distance and homophily ratio difference, depicted as \(\frac{1}{N_{\mathbf{r}}^{1-2\alpha}}+\frac{1}{N_{\mathbf{r}}^{2\alpha}}\ln\frac{LC(2B_ {m})^{1/L}}{\gamma^{1/L}\delta}\), where \(B_{m}=\max_{i\in V_{\mathbf{r}}\cup V_{m}}\|g_{i}(X,G)\|_{2}\) is the maximum feature norm. \(\mathbf{R}\) vanishes as training size \(N_{0}\) grows. Proof details are in Appendix F

Our theory suggests that both homophily ratio difference and aggregated feature distance to training nodes are key factors contributing to the performance disparity. Typically, nodes with large homophily ratio difference and aggregated feature distance to training nodes lead to performance degradation.

### Performance Disparity Across Node Subgroups on Real-World Datasets

To empirically examine the effects of theoretical analysis, we compare the performance on different node subgroups divided with both homophily ratio difference and aggregated feature distance to training nodes with popular GNN models including GCN [2], SGC [15], GAT [10], GCNII [51], and GPRGNN [52]. Typically, test nodes are partitioned into subgroups based on their disparity scores to the training set in terms of both 2-hop homophily ratio \(h_{i}^{(2)}\) and 2-hop aggregated features \(\mathbf{F}^{(2)}\) obtained by \(\mathbf{F}^{(2)}=(\mathbf{\bar{D}}^{-1}\mathbf{\tilde{A}})^{2}\mathbf{X}\), where \(\mathbf{\tilde{A}}=\mathbf{A}+\mathbf{I}\) and \(\mathbf{\bar{D}}=\mathbf{D}+\mathbf{I}\). For a test node \(i\), we measure the node disparity by (1) selecting the closest training node \(v=\text{arg}\min_{v\in V_{0}}||\mathbf{F}_{u}^{(2)}-\mathbf{F}_{v}^{(2)}||\) (2) then calculating the disparity score \(s_{u}=||\mathbf{F}_{u}^{(2)}-\mathbf{F}_{v}^{(2)}||_{2}+|h_{u}^{(2)}-h_{v}^{(2)}|\), where the first and the second terms correspond to the aggregated-feature distance and homophily ratio differences,

Figure 5: Test accuracy disparity across node subgroups by **aggregated-feature distance and homophily ratio difference** to training nodes. Each figure corresponds to a dataset, and each bar cluster corresponds to a GNN model. A clear performance decrease tendency can be found from subgroups 1 to 5 with increasing differences to training nodes.

Figure 6: Test accuracy disparity across node subgroups by **aggregated-feature distance** to train nodes. Each figure corresponds to a dataset, and each bar cluster corresponds to a GNN model. A clear performance decrease tendency can be found from subgroups 1 to 5 with increasing differences to training nodes.
respectively. We then sort test nodes in terms of the disparity score and divide them into 5 equal-binned subgroups accordingly. Performance on different node subgroups is presented in Figure 5 with the following observations. **Obs.1:** We note a clear test accuracy degradation with respect to the increasing differences in aggregated features and homophily ratios. Furthermore, we investigate on the individual effect of aggregated feature distance and homophily ratio difference in Figure 6 and 7, respectively. An overall trend of performance decline with increasing disparity score is evident though some exceptions are present. **Obs.2:** When only considering the aggregated feature distance, there is no clear trend among groups 1, 2, and 3 on GCN, SGC, and GAT on heterophilic datasets. **Obs.3:** When only considering the homophily ratio difference, there is no clear trend among groups 1, 2, and 3 across four datasets. These observations underscore the importance of both aggregated-feature distance and homophily ratio differences in shaping GNN performance disparity. Combining these factors together provides a more comprehensive and accurate understanding of the reason for GNN performance disparity. For a more comprehensive analysis, we further substantiate our finding involving higher-order information and a wider array of datasets in Appendix J.1.

**Summary** In this section, we study GNN performance disparity on nodes with distinct structural patterns and uncover its underlying causes. We primarily investigate the impact of aggregation, the key component in GNNs, on nodes with different structural patterns in Sections 3.1 and 3.2. We observe that aggregation effects vary across nodes with different structural patterns, notably enhancing the discriminative ability on majority nodes. These observed performance disparities inspire us to identify crucial factors contributing to GNN performance disparities across nodes with a non-i.i.d PAC-Bayes bound in Section 3.3. The theoretical analysis indicates that test nodes with larger aggregated feature distances and homophily ratio differences with training nodes experience performance degradation. We substantiate our findings on real-world datasets in Section 3.4.

## 4 Implications of graph structural disparity

In this section, we illustrate the significance of our findings on structural disparity via (1) elucidating the effectiveness of existing deeper GNNs (2) unveiling an over-looked aspect of distribution shift on graph out-of-distribution (OOD) problem, and introducing a new OOD scenario accordingly. Experimental details and discussions on more implications are in Appendix G and O, respectively.
Having identified where deeper GNNs excel, reasons why effectiveness primarily appears in the minority node group remain elusive. Since the superiority of deeper GNNs stems from capturing higher-order information, we further investigate how higher-order homophily ratio differences vary on the minority nodes, denoted as, \(|h_{u}^{(k)}-h_{v}^{(k)}|\), where node \(u\) is the test node, node \(v\) is the closest train node to test node \(u\). We concentrate on analyzing these minority nodes \(\mathbf{V}_{\text{mi}}\) in terms of default one-hop homophily ratio \(h_{u}\) and examine how \(\sum_{u\in\mathbf{V}_{\text{gi}}}|h_{u}^{(k)}-h_{v}^{(k)}|\) varies with different \(k\) orders. Experimental results are shown in Figure 9, where a decreasing trend of homophily ratio difference is observed along with more neighborhood hops. The smaller homophily ratio difference leads to smaller generalization errors with better performance. This observation is consistent with [19], where heterophilic nodes in heterophilic graphs exhibit large higher-order homophily ratios, implicitly leading to a smaller homophily ratio difference.

### A new graph out-of-distribution scenario

The graph out-of-distribution (OOD) problem refers to the underperformance of GNN due to distribution shifts on graphs. Many Graph OOD scenarios [61, 62, 63, 64, 23, 65, 45], e.g., biased training labels, time shift, and popularity shift, have been extensively studied. These OOD scenarios can be typically categorized into covariate shift with \(\mathbf{P}^{\text{train}}(\mathbf{X})\neq\mathbf{P}^{\text{test}}(\mathbf{X})\) and concept shift [66, 67, 68] with \(\mathbf{P}^{\text{train}}(\mathbf{Y}|\mathbf{X})\neq\mathbf{P}^{\text{test}}( \mathbf{Y}|\mathbf{X})\). \(\mathbf{P}^{\text{train}}(\cdot)\) and \(\mathbf{P}^{\text{test}}(\cdot)\) denote train and test distributions, respectively. Existing graph concept shift scenarios [61, 65] introduce different environment variables \(e\) resulting in \(\mathbf{P}(\mathbf{Y}|\mathbf{X},e_{\text{train}})\neq\mathbf{P}(\mathbf{Y}| \mathbf{X},e_{\text{test}})\) leading to spurious correlations. To address existing concept shifts, algorithms [61, 69] have been developed to capture the environment-invariant relationship \(\mathbf{P}(\mathbf{Y}|\mathbf{X})\). Nonetheless, existing concept shift settings overlook the scenario where there is not a unique environment-invariant relationship \(\mathbf{P}(\mathbf{Y}|\mathbf{X})\). For instance, \(\mathbf{P}(\mathbf{Y}|\mathbf{X}_{\text{homo}})\) and \(\mathbf{P}(\mathbf{Y}|\mathbf{X}_{\text{hete}})\) can be different, indicated in Section 3.1. \(\mathbf{X}_{\text{homo}}\) and \(\mathbf{X}_{\text{hete}}\) correspond to features of nodes in homophilic and heterophilic patterns. Notably, homophilic and heterophilic patterns are crucial task knowledge that cannot be recognized as the irrelevant environmental variable. Consequently, we find that homophily ratio difference between train and test sets could be an important factor leading to an overlook concept shift, namely, graph structural shift. Notably, structural patterns cannot be considered as environment variables given their integral role in node classification task. The practical implications of this concept shift are substantiated by the following scenarios: **(1)** graph structural shift frequently occurs in most graphs, with a performance degradation in minority nodes, as depicted in Figure 3. **(2)** graph structural shift hides secretly in existing graph OOD scenarios. For instance, the FaceBook-100 dataset [61] reveals a substantial homophily ratio difference between train and test sets, averaging 0.36. This discrepancy could be the primary cause of OOD performance deterioration since the exist OOD algorithms [61, 70] that neglect such a concept shift can only attain a minimal average performance gain of 0.12%. **(3)** graph structural shift is a recurrent phenomenon in numerous real-world applications where new nodes in graphs may exhibit distinct structural patterns. For example, in a recommendation system, existing users with rich data can receive well-personalized recommendations in the exploitation stage (homophily), while new users with less data may receive diverse recommendations during the exploration stage (heterophily).

Figure 8: Performance comparison between GCN and deeper GNNs. Each bar represents the accuracy gap on a specific node subgroup exhibiting homophily ratio within range specified on x-axis.

Figure 9: Multiple hop homophily ratio differences between training and minority test nodes.
Given the prevalence and importance of the graph structural shift, we propose a new graph OOD scenario emphasizing this concept shift. Specifically, we introduce a new data split on existing datasets, namely Cora, CiteSeer, PubMed, Ogbn-Arxiv, Chameleon, and Squirrel, where majority nodes are selected for train and validation, and minority ones for test. This data split strategy highlights the homophily ratio difference and the corresponding concept shift. To better illustrate the challenges posed by our new scenario, we conduct experiments on models including GCN, MLP, GLNN, GPRGNN, and GCNII. We also include graph OOD algorithms, SRGNN [62] and EERM [61], with GCN encoders. EERM(II) is a variant of EERM with a GCNII encoder For a fair comparison, we show GCN performance on an i.i.d. random split, GCN(i.i.d.), sharing the same node sizes for train, validation, and test. Results are shown in Table 1 while additional ones are in Appendix G.4. Following observations can be made: **Obs.1:** The performance degradation can be found by comparing OOD setting with i.i.d. one across four datasets, confirming OOD issue existence. **Obs.2:** MLP-based models and deeper GNNs generally outperform vanilla GCN, demonstrating the superiority on minority nodes. **Obs.3:** Graph OOD algorithms with GCN encoders struggle to yield good performance across datasets, indicating a unique challenge over other Graph OOD scenarios. This primarily stems from the difficulty in learning both accurate relationships on homophilic and heterophilic nodes with distinct \(\mathbf{P}(\mathbf{Y}|\mathbf{X})\). Nonetheless, it can be alleviated by selecting a deeper GNN encoder, as the homophily ratio difference may vanish in higher-order structure information, with reduced concept shift. **Obs.4:** EERM(II), EERM with GCNII, outperforms the one with GCN. Observations suggest that GNN architecture plays an indispensable role in addressing graph OOD issues, highlighting the new direction.

## 5 Conclusion & Discussion

In conclusion, this work provides crucial insights into GNN performance meeting structural disparity, common in real-world scenarios. We recognize that aggregation exhibits different effects on nodes with structural disparity, leading to better performance on majority nodes than those in minority. The understanding also serves as a stepping stone for multiple graph applications.

Our exploration majorly focuses on common datasets with clear majority structural patterns while real-world scenarios, offering more complicated datasets, posing new challenges Additional experiments are conducted on Actor, IGB-tiny, Twitch-gamer, and Amazon-ratings. Dataset details and experiment results are in Appendix G.3 and Appendices H-K, respectively. Despite our understanding is empirically effective on most datasets, further research and more sophisticated analysis are still necessary. Discussions on the limitation and broader impact are in Appendix N and O, respectively.

## 6 Acknowledgement

We want to thank Xitong Zhang, He Lyu at Michigan State University, Yuanqi Du at Cornell University, Haonan Wang at the National University of Singapore, and Jianan Zhao at Mila for their constructive comments on this paper.
