Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?
Authors: Haitao Mao
Zhikai Chen
Wei Jin
Haoyu Han
Yao Ma
Tong Zhao
Neil Shah
Jiliang Tang
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph Neural Network
TL;DR: This study investigates the performance disparity of GNNs on homophilic and heterophilic nodes in the same graph.

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.

Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?
Haitao Mao', Zhikai Chen', Wei Jin', Haoyu Han',
Yao Ma², Tong Zhao", Neil JillanJ Tang'
Michigan State University Snap Inc *Rensselaer Polytechnic Institute. (haitaoma, chenzh85,hanhag 1ar.5Shhhhaoy...aa ttangjili) @ msu.edu, (tshao, @ @saap.com may ma@rpieii,
4 Emory University
wei.jnn@emory.ddi
Abstract
Recent studies on Graph Neural Networks(GNNs) provide both empirical and theoretical evidence supporting their effectiveness in capturing structural patterss 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 structural disparity. However, the analysis of GNN performance with respect to nodes exhibiting dif- ferent structural patterns, e.g.. homophilic nodes heterophilic graphs, remains rather limited. In the present study, we provide evidence that Graph Neural Net- works(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 testing nodes exhibiting distinct structural patterns. We then propose rigorous, non-i.i.d PAC-Baycsian 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, 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 -iiitii-iitiitttioon problem and proposing new scenario accordingly.
Introduction
Graph Neural Networks (GNNs) 1 are powerful technique for lackling a wide range of graph-related tasks [ 3 6010,, especially node classification 2
Homophily
12 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 their ability to capture structural patterns through the aggregation mechanism that effectively combines feature information from neighboring nodes [3]
Aggregation
Heterophily
GNNs have been widely recognized for their effectiveness on homophilic graphs [4 2
17] 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 I where node features and node labels are denoted by colors (i.e., blue and red) and numbers (i.e., O and 1), respectively. We can observe that all connected nodes exhibit homophilic patterns and share the same label Recently, several studies have demonstrated that GNNs can also perform well on certain heterophilic graphs [8
ggu egation
Figure 1: Examples of ho- mophilic and heterophilic patterns. Colors/numbers in- dicate node features/labels.
19
In heterophilic graphs, connected nodes
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

tend to have different labels, which we refer to as heterophilic patterns. The example in the lower part of Figure I 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 homophilic or heterophilic patterns solely and overlook the fact that real-world graphs typically exhibit mixture of homophilic and heterophilic patterns. Recent studies (20] 21 reveal that
14
19 only focus on either
many heterophilic graphs, e.g., Squirrel and Chameleon [22], 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 (23] and Ogbn-arxiv (24]. 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 heterophilic nodes in the majority and homophilic ones in the minority.
To provide insights aligning the real-world scenario with structural disparity, we revisit the toy example in Figure [ 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 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 applica- tions. 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 [13 14 19]. We show that GCN (2), 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 non-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- oi-tiitiibttiinn scenario with over-looked distribution shift factor. Codes available at here
2 Prelimaries
Semi-Supervised Node classification (SSNC). Let G (V,E) be undirected graph, where == En} is the set of n nodes and E CVVV x V is the edge set. Nodes are associated with node features X E rdd where d is the feature dimension. The number of class is denoted as K. The adjacency matrix A E {0, 1 represents graph connectivity where A|i 1 indicates an edge between nodes i and j. D is a degree matrix and D(i, i] = d, with d; denoting degree of node vs Given a small set of labeled nodes, Vr C V. SSNC task is predict on unlabeled nodes V \ Vr.
Node homophily ratio is common metric to quantify homophilic and heterophilic patterns. is calculated as the proportion of a node's neighbors sharing the same label as the node (25 26 20). It is formally defined as h; (uEN(v.)......))
where N(xx) denotes the neighbor node set of U;
d;
and d = (wx) is the cardinality of this set. Following 20 27 25), node i considered to be
homophilic when more neighbor nodes share the same label as the center node with h; > 0.5. We

---

define the graph homophily ratio h as the average of node homophily ratios h = Eicy he [V] Moreover,
this ratio can be casily extended to higher-order cases h by considering k-order neighbors. (v.)..)
Node subgroup refers to a subset of nodes in the graph sharing similar properties, typically ho- mophilic and heterophilic patterns measured with node homophily ratio. Training nodes are denoted as Vr. Test nodes Ve can be categorized into M node subgroups, Ve= = U Vm. where nodes in the same subgroup Vm share similar structural pattern.
3 Effectiveness of GNN nodes with different structural properties
In this section, we explore the effectiveness of GNNs different node subgroups exhibiting distinct structural patterns, specifically, homophilic and heterophilic patterns. It is different from previous studies [3 14
28 [9] that primarily conduct analysis the whole graph and demonstrate effectiveness with an overall performance gain. These studies, while useful, do not provide insights into the effectiveness of GNNs 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, take closer examination patterns. The following experiments are conducted on two common homophilic graphs, Ogbn- arxiv 24 and Pubmed [23], and two heterophilic graphs, Chamelcon and Squirrel [22]. These datasets are chosen since GNNs can achieve better overall performance than MLP. Experiment details and related work GNN disparity in Appendix G and A respectively.
18
node subgroups with distinct structural
Deneity
Density
Density
Density
50
0.
00
Prode
Noode
(a) PubMed (h=0.79)
(b) Ogbn-arxiv (h=0.63) (c) Chameleon (h=0.22)
(d) Squirrel (h=0.25)
Figure 2: Node homophily ratio distributions. All graphs exhibit mixture of homophilic and heterophilic nodes despite various graph homophily ratio h.
Existence of structural pattern disparity within a graph is recognize real-world graphs ex- hibiting 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 mixture of both homophilic and heterophilic patterns, rather than a uniform structural patterns. Obs.2: In homophilic graphs, the majority of nodes exhibit homophilic pattern with h,55, while in heterophilic graphs, the majority nodes exhibit the heterophilic pattern with 5.5.. We define nodes in majority structural pattern majority nodes, e.g., homophilic nodes in a homophilic graph.
GUAY
Difference sec GCN 22
Didferunce in ace model GEN
ago
strdel GEN
Dictrranee in ana motel GCN
Differunce in
eo
0.10
da1e
do0d
8204
d40d
Homophily Ratio Range
Homophily Rati Range
Homophal Ratio Range
Homopally
Range
(a) PubMed 779
(b) Ogbn-arxiv (h=0.63) (c) Chameleon (h=0.22)
(d) Squirrel (h=0.25)
Figure 3: Performance comparison between GCN and MI.P-based models. Fach bar represents the accuracy gap specific node subgroup exhibiting a homophily ratio within the range specified on the x-axis. ML.P-baedd models often outperform GCN on heterophilic nodes in homophilic graphs and homophilic nodes in heterophilic graphs with positive value.

---

Examining GCN performance on different structural patterns. To examine the effectiveness of GNNs on different structural patterns, we compare the performance of GCN [2 vanilla GNN, with two MILP-based models, vanilla MI.P and Graphless Neural Network (GINN) (2)], on testing nodes with different homophily ratios. It is evident that the vanilla MI. could have a large performance gap compared to GCN (i.e., 20% in accuracy) [33 29, 2) Consequently, an under-trained vanilla MLP comparing with a well-trained GNN leads to an unfair comparison without rigorous conclusion. 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 30) Our observations indicate that despite the effectiveness of GCN suggested by 13 19 14, 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.] 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- PAC-Bayes bound. Section 3.4 empirically corroborates the validity of our theoretical analysis with real-world datasets.
3.1 How does aggregation affect nodes with structural disparity differently?
In this subsection, we examine how aggregation reveals different effects nodes with structural dis- parity, 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 13 31 I8 32 33 clustering (34], fairness [35] (6), and GNN architecture design (37-39). Typically, nodes in CSBM model are generated into two disjoint sets Ci and C2 corresponding to two classes, ei and o2, respectively. Each node with C is associated with features I E Rd sampling from N N I), where μú is the feature mean of class e, with i E 21. The distance between feature means in different classes = || - [2 |l. indicating the classification difficulty on node features. Edges are then generated based on intra-class probability p and inter-class probability g. For instance, nodes with class C₁ have probabilities p and q of connecting with another node in class ej and C22 respectively. The CSBM model, denoted as CSBM(H1 f42, p, P.q). presumes that all nodes follow either homophilic with p > q or heterophilic patterns < 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- (CSBM-S), allowing for the simultaneous description of homophilic and heterophilic nodes.
Definition 1 (CSBM-S( #2, (p(),g()) ( of two disjoint sets C₁ and Cz. Each node feature x is sampled from N N(H,, 1) with E [1,2]. Each set C, consists of two subgroups: ci for nodes in homophilic pattern with intra-class and
(2))), Pr(homo))). The generated nodes consist
4

---

inter-class edge probability plt) > g0) and C,2² for nodes in heterophilic pattern with g < g Pr(homo) denotes the probability that the node is in homophilic patter. c. denotes node in class and subgroup j with (plt), g(0)). We assume nodes follow the same degree distribution with p(l) q()) = =p + q(2).
Based on the neighborhood distributions, the mean aggregated features F DD1AA AX obtained follow Gaussian distributions on both homophilic and heterophilic subgroups.
p( N NO( (
110ppm p +g u22 pb) + g(o) Vd,
)aa) for E r N (g00 pi + +
I
(2") pb) + +gg))
Va. ) for c
(I)
Where C. is the node subgroups with structural pattern with (pln), ,(0)) 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 c1.
Proposition 1. The aggregated feature mean distance between homophilic and heterophilic node subgroups within class 01 is
p pu R0 pg u2 > 0, indicating the aggregated feature p()++())
pl9) +gt))))
of homophilic and heterophilic subgroups are from different feature distributions, with a mean distance larger than O distance before aggregation, since original node features draw from the same distribution, regardless of different structural patterns.
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 e with the same aggregated feature f. f, but different structural patterns. We examine the discrepancy with the probability difference of nodes u and v in class c₁ denoted as [P = ci (f.)= - P2 c1 [f. P1 and P2 are the conditional probability of y C1 given the feature f on structural patterns (p(2), ((11) and (p(2), (2))), respectively.
Lemma 1. With assumptions (1) A balance class distribution with P(Y = =) = P(Y = 0) and (2) aggregated feature distribution shares the same variance When nodes and have the same aggregated features fu = f. but different structural patterns, (p(2), (22) and (p(2), 2222), we have:
(1 = e. (f,) P2(y. c1 cf,] V2TO
hh hel
Notably, above assumptions are not strictly necessary but employed for elegant expression. Lemma I implies that nodes with a small homophily ratio difference | byy are likely to share the same class, and vice versa. Proof details and additional analysis on between-class effects are in Appendix D
3.2 How does Aggregation Contribute to Performance Disparity?
Chameleon
Arxy
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 pre- dominantly on majority nodes as opposed to minority nodes. It should be noted that, notwithstanding the influence on features, test performance also profoundly associated with training labels. Per- formance degradation may occur when the classifier is inadequately trained with biased training labels.
Squireel
PubMod
1.50
Ratio
1.00
0.75
0.50
0.55
We then conduct an empirical discriminative analysis taking both mean aggregated features and training labels into consideration. Drawing inspiration from existing literature 40 43 we describe the discriminative ability with the distance between train class proto- types [4445)) i.e., feature mean of each class, and the corresponding test class prototype within the same class i. For instance, can be denoted as || [, where ni and ya 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
0.00
#aggregation
Figure 4: Illustration on discriminative ratio variation along with aggregation. x-axis denotes the number of aggre- gations and y-axis denotes the discriminative ratio.
5

---

the same class, thus implying superior discriminative ability. A relative discriminative ratio is then proposed to compare the discriminative ability between majority and minority nodes. can be denoted as: >=>m= T| -
-|-""=""1| where 14 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 O-hop. Experimental results are presented in Figure | 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
3.3 Why does Performance Disparity Happen? Subgroup Generalization Bound for GNNs
In this subsection, conduct 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 (.2] we identify two key factors for satisfying test
performance: (1) test node u should have close feature distance min.ey, l[f. - f.ll to training nodes Vi. 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 Ex,ec (y,, = ca cg Ply cg|fo)] is required
be small. The second factor, focusing on whether two close nodes are in the same class, is dependent on the homophily ratio difference 1 as shown Lemma [ Notably, since training nodes are randomly sampled, their structural patterns are likely to be the majority one. Therefore, training nodes will show 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 non-i.i.d PAC-Bayesian GNN generalization bound, based on the Subgroup Generalization bound of Deterministic Classifier [46). 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 (Generalized CSBM-S model). Each node subgroup Vm follows the CSBM distribution Vm CSBM( 12, pgggg"gg))))) where different subgroups share the same class mean but different intra-class and inter-class probabilities ( and q0), Moreover, node subgroups also share the same degree distribution as p()) + g0 = =pú) + q()).
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 (66] with the following components: (1) one-hop mean aggregation function g with g(X, G) denoting the output. (2) MLP feature transformation f(g(X, G); W1, W2, WL). where f is ReLU-activated L-layer MLP with ".. WL 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 44
13 47], our
theory analysis could be easily extended to the higher-order case with empirical success across different GŇN architectures shown in Section (.4]
Our main theorem is based on the PAC-Bayes analysis which typically aims to bound the generaliza- tion gap between the expected margin loss Co, on test subgroup V., for a margin 0 and the empirical margin loss 2% on train subgroup V,, for a margin 7. Those losses are generally utilized in PAC-Bayes analysis 48 51. More details are found in Appendix [F] The formulation is shown as follows:
Theorem 1 (Subgroup Generalization Bound for GNNs). Let h be any classifier in the classifier family H with parameters (Wi) for any 0 m S M, 2 0. and large enough number of the training nodes N₂ |Virl. there exist 0 < 1/2 with probability at least - 8 over the sample of

---

== fuiliv we have:
Kp
b bΣ (7/ (7/8)2/L No
Will
(m(h) S (h)
(cm + [hr hml mmll-p p)
(cm))
+R.
/2n
(a)
(b)
The bound is related three terms: (a) describes both large homophily ratio difference /hrr hm and large aggregated feature distance = max min [X g3 (X, G) between test node subgroup Vm and training nodes Vrr lead large generalization error. p = || peel 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 e, leads large generalization error. (c) R. is a term independent with aggregated feature distance and homophily ratio difference,
depicted as NI-25 + N2 In LC(2Bm))'Z where Bm = max:ev,vv. llg: X, G) is the maximum 7 feature norm. R vanishes training size No 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.
3.4 Performance Disparity Across Node Subgroups on World Datasets
0.
84
2.4
000 130 1138
102 20000220
D0N PAT CORIEO
2010
(a) PubMed (/=0.79)
(b) Ogbn-arxiv (h=0.63)
(c) Chameleon (h=0.22)
(d) Squirrel (h=0.25)
Figure Test accuracy disparity across node subgroups by aggregated feature distance and homophily ratio difference to training nodes. Each figure corresponds to dataset, and each bar cluster corresponds to a GNN model. A clear performance decrease tendency can be found from subgroups to 5 with increasing differences to training nodes.
0.8
64
0.6
Re4
0.4
64
852
(a) PubMed (/=0.79)
(b) Ogbn-arxiv (h=0.63)
(c) Chameleon (h=0.22)
(d) Squirrel (h=0.25)
Figure 6: Test accuracy disparity across node subgroups by aggregated-feani featuur distance train nodes. Each figure corresponds to dataset, and each bar cluster corresponds GNN model. A clear performance decrease tendency can found from subgroups
with increasing differences to training nodes.
To empirically examine the effects of thcoretical 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 (16), GAT [II, GCNII [52). and GPRGNN [53] Typically, test nodes are partitioned into subgroups based on their disparity
scores the training set in terms of both 2-hop homophily ratio fi and 2-hop aggregated features F(2) obtained by (2) (D-1 11 A where À + and D For a test node we measure the node disparity by (1) selecting the closest training node arg min
|| FF(2)
(2) then calculating the disparity score 8, = || F(2) ||2 + |M [1( where the first and the second terms correspond to the aggregated-featt -ecture distance and homophily ratio differences.
7

---

R04
204
20
67
62
60
0.
(a) PubMed (h=9.79
(b) Ogbn-arxiv (h=0.63) (c) Chameleon (h=0.22)
(d) Squirrel (h=0.25)
Figure 7: Test accuracy disparity across node subgroups by homophily ratio difference to train nodes. Each figure corresponds to dataset, and each bar cluster corresponds GNN model. A clear performance decrease tendency can be found from subgroups 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 with the following observations. Obs.1: We note 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 clear trend among groups I, 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-feant feature distance and homophily ratio differences in shaping GNN performance disparity. Combining these factors together provides more comprehensive and accurate understanding of the reason for GNN performance disparity. For a more comprehensive analysis, we further substantiate finding involving higher-order information and wider array of datasets in Appendix J.1
Summary 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 to identify crucial factors contributing GNN performance disparities across nodes with a non-i.i.d PAC-Bayee 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 -fi-t-ddiittitttion (OOD) problem, and introducing new OOD scenario accordingly. Experimental details and discussions on more implications are in Appendix and respectively.
4.1 Elucidate the effectiveness of Deeper GNNs
Deeper GNNs 53 52 15 54 enable each node to capture more complex higher-order graph structure than vanilla GCN, via reducing the over-smoothing problem [58] 55| 61 Deeper GNNs empirically exhibit overall performance improvement, Nonetheless, which structural patterns deeper GNNs can exceed and the reason for its effectiveness remain unclear. To investigate this problem, we compare vanilla GCN with different deeper GNNs, including GPRGNN[33, APPNP[[S), and GCN on node subgroups with varying homophily ratios, adhering the same setting with Figure Experimental results are shown in Figure g We can observe that deeper GNNs primarily surpass GCN on minority node subgroups with slight performance trade-offs on the majority node subgroups. We conclude that the effectiveness of deeper GNNs majorly contributes to improved discriminative ability on minority nodes. Additional results on more datasets and significant test are in Appendix and M
demonstrated in Appendix G.2
8

---

Dillereee in woo model .CNN
pucforenie in are
model GCM
0.00
tiodel GEN
Deiffreence in anm modell -GENN
0.02
L. 2
0.00
Diffornnce
e
0.00
0.80
0.88
0200
8446
Homophily Bange
Homophily Range
Homophlly Ratto Range
Homophity Radi Range
(a) PubMed (h=0.79)
(b) Ogbn-arxiv (/=0.63)
(c) Chameleon (h=0.22)
(d) Squirrel (h=0.25)
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.
Having identified where deeper GNNs excel, reasons why effectiveness primarily appears the minority node group remain elusive, Since the superiority of deeper GNNs stems from capturing higher-order informa- tion, we further investigate how higher-order homophily ratio differences
Ratio difference
PubMed
n.
Arxiv
Squirel
0.6-
Chameleon
vary on the minority nodes, denoted as, [ ) where node u is the test node, node is the closest train node test node u. We concen-
0.2
trate on analyzing these minority nodes Vni in terms of default one-hop
homophily ratio h, and examine how Euey, I ho varies with different orders. Experimental results are shown in Figure 9 where 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 200), where heterophilic nodes in heterophilic graphs ex- hibit large higher-order homophily ratios, implicitly leading smaller homophily ratio difference.
# &hop
Figure 9: Multiple hop homophily ratio differ- ences between training and minority test nodes.
4.2 A new graph fit-of-dditribuuton scenario
The graph duttif-distiibution (OOD) problem refers to the underperformance of GNN due to distri- bution shifts on graphs. Many Graph OOD scenarios 662 24 666 46) 67], 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 ptrain # ptst (x)((X) (X) and concept shift [68]770 with purain ( (X) # piest (Y X). Piran (-) and plest, (.) denote train and test distributions, respectively,
Existing graph concept shift scenarios 62 661 introduce diffferent environment variables resulting in P Crain) * P (wsa leading to spurious correlations. To address existing concept
X,
shifts, algorithms 62 7 have been developed to capture the environment-invarinn relationship P(Y Nonetheless, existing concept shift settings overlook the scenario where there is not unique patrronment-invariane relationship P(Y|X). For instance, P(Y|X and P(Y ( can be different, indicated in Section 3.1 Xhomo and X correspond to features of nodes in ho- mophilic 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 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 (22) reveals 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 62 72) that neglect such a concept shift can only attain a minimal average performance gain of 0.12%. (3) graph structural shift is 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 pell-personalized recommendations in the exploitation stage (homophily), while new users with less data may receive diverse recommendations during the exploration stage (heterophily).

---

Given the prevalence and importance of the graph structural shift, we pro- pose a new graph OOD scenario em- phasizing this concept shift. Specif- ically, we introduce new data split on existing datasets, namely Cora, CiteSeer, PubMed, Ogbn-Arxiv, Chameleon, and Squirrel, where ma- jority nodes 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 models including GCN, ML., GLNN, GPRGNN, and GCNII. We also include graph OOD algorithms, SRGNN 63 and EERM [62], with GCN encoders. EERM(II) is variant of EERM with GCNII encoder For a fair comparison, we show GCN performance on an i..d. random split, GCN(L..d.), sharing the same node sizes for train, validation, and test. Results are shown in Table D while additional ones in Appendix G.44 Following observations can be made: Obs.1: The performance degradation can be found by com- paring 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 supe- riority on minority nodes. Obs.3: Graph OOD algorithms with GCN encoders struggle yield good performance across datasets, indicating 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 P(Y[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(I), 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.
Table Performance (Accuracy) on the proposed OOD split.
Pubmed
Ogbn-Arxiv
Squirrel
Chameleon
GCN(Ldd)
89.1820.15
72.99=0.14
58.0920.71
75.09=0.79
GCN
51.0420.16 16
34.94=0.07
32.13+4.93
43.35=3.47
MLP
68.38+0.43
33.17=0.37
24.57+0.77
34.78+4.97
GLNN
67.51+0.25
35.89#0.14
31.51+0.70
1.00
GCNIT
67.76+0.36
36.81
37.15+1.39
41.25522.33
GPRGNN
57.24+0.18
34, 14.9540.43
42.43+7.71
35.27=7 .67
SRGNN EERM
57.91#0.10
40.37=1.65
37.62+1.74
42,0920 43
65.37+1.35
34 $4.2340.46
40.93=0.57
45 1.45.05
EERM(II)
67.59+0.91
40.28=0.84
44.31=0.40
48.59=0.78
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 nodes with structural disparity, leading to better performance on majority nodes than those in minority. The understanding also serves 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- gameer, and Amazon-ratinge
Dataset details and experiment results 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 the limitation and broader impact are in Appendix N and O respectively.
6 Acknowledgement
We want to thank Xitong Zhang, He Lyu, Wenzhuo Tang at Michigan State University, Yuanqi Du at Cornell University, Haonan Wang at the National University of Singapore, and Jianan Zhao Mila for their constructive comments on this paper.
This research is supported by the National Science Foundation (NSF) under grant numbers CNS 2246050, IIS 1845881 IIS22 2032, 1442, IIS2153326, IIS2212145, IOS2107215, DUE 2234015, DRL 2025244 and IOS2035472, the Army Research Office (ARO) under grant num- ber 191 the Home Depot, Cisco Systems Inc, Amazon Faculty Award, John- son&Johnson, JP Morgan Faculty Award and SNAP.
References
[1] Yao Ma and Jiliang Tang. Deep learning on graphs. Cambridge University Press, 2021.
10

---

[2] Thomas Kipf and Max Welling. Semi Semi-supervised classification with graph convolutional networks. ArXiv, abs/ N1016669900,, 2016.
[3] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations.
[4] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 30, 2017.
[5] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
[6] Xiangnan He, Kuan Deng, Xiang Wang. Yan Li, Yongdong Zhang, and Meng Wang. Lightenn: Simplifying and powering graph convolution network for recommendation. In Proceedings of the 43rd International ACM SIGIR conference on research and development in Information Retrieval, pages 639- 648, 2020.
[7] Oliver Wieder, Stefan Kohlbacher, Mélaine Kuenemann, Arthur Garon, Pierre Ducrot, Thomas Seidel, and Thierry Langer. A compact review of molecular property prediction with graph neural networks. Drug Discovery Today: Technologies, 37:1-12, 2020.
[8] Zhaocheng Zhu, Zuobai Zhang, Louis-Pascaa Xhonneux, and Jian Tang. Neural bellman-for networks: A general graph neural network framework for link prediction. Advances in Neural Information Processing Systems, 34:29476-29499 2021.
[9] Juanhui Li, Harry Shomer, Haitao Mao, Shenglai Zeng. Yao Ma, Neil Shah, Jiliang Tang, and Dawei Yin. Evaluating graph neural networks for link prediction: Current pitfalls and new benchmarking. arXiv preprint arXiv:2306.10453, 2023.
[10] Yanci Zhang, Yutong Lu, Haitao Mao, Jiawei Huang. Cien Zhang, Xinyi Li, and Rui Dai. Company competition graph. arXiv preprint arXiv:2304. 00323, 2023.
[11] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, Yoshua Bengio, et al. Graph attention networks. stat, 1050(20):00-4855)) 2017.
[12] Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counter- factual links for link prediction. In International Conference on Machine Learning, pages 26911-26926. PMLR, 2022.
[13] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? ArXiv, abs/2106.06 134, 2021.
[14] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi- supervised classification: Improved linear separability and out-of-distribution generalization. arXiv preprint arXiv:2102.06966 2021.
[15] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
[16] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. Simplifying graph convolutional networks. In International conference on machine learning, pages 6861-6877 PMLR, 2019.
[17] Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. Data augmentation for graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 11015-11023 2021.
[18] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In The Eleventh International Conference on Learning Representa- tions, 2023.
[19] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wat Chang, and Doina Precup. Revisiting heterophily for graph neural networks. In Advances in Neural Information Processing Systems.
11

---

[20] Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Wei Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, 2022.
[21] Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser Nam Lim. Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods. Advances in Neural Information Processing Systems, 34:20887-20902 2021.
[22] Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9()):nabb11,, 2021.
[23] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):33-93, 2008
[24] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. arXiv preprint wrxiv:2005.00687 2020.
[25] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen. Geometric graph convolutional networks. In International Conference on Learning Represen- lations.
[26] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Be- yond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 14:7793-7804 2020.
[27] Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei Zhang. Gbk-gnn: Gated bi-kernel graph neural networks for modeling both homophily and heterophily. In Proceedings of the ACM Web Conference 2022, pages 1550-1558, 2022.
[28] Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao Chang, Jie Fu, Jure Leskovee, and Doina Precup. When do graph neural networks help with node classification: Investigating the homophily principle on node distinguishability. arXiv preprint arXiv:2304. 14274, 2023.
[29] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mips new tricks via distillation. ArXiv, abs/21 10.08727, 2021.
[30] Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Kiao-Wen Chang, and Doina Precup. When do we need gnn for node classification? arXiv preprint arXiv:2210. 16979, 2022.
[31] Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang. Augmentation--ree graph contrastive learning. arXiv preprint arXiv:2204. 048744 2022.
[32] Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang. Can single-pass contrastive learning work for both homophilic and heterophilic graph? arXiv preprint arXiv:2211. 2022.
[33] Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. arXiv preprint arXiv:2202.13660 2022.
[34] Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 659:1 -4, 2016.
[35] Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Na Zou, Ali Mostafavi, and Xia Hu. Fmp: Toward fair graph message passing against topology bias. arXiv preprint arXiv:2202.04187. 2022.
[36] Zhimeng Jiang, Xiaotian Han, Chao Fan, Zirui Liu, Xiao Huang, Na Zou, Ali Mostafavi, and Xia Hu. Topology matters in fair graph learning: a theoretical pilot study.
[37] Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R Benson, and Pan Li. Understanding non- linearity in graph neural networks from the payesian-inference perspective. In Advances in Neural Information Processing Systems.
12

---

[38] Yoonhyuk Choi, Jiho Choi, Taewook Ko, and Chong- Kwon Kim. Is signed message essential for graph neural networks? arXiv preprint arXiv:2301.08911 2023.
[39] Xinyi Wu, Zhengdao Chen, William Wang, and Ali Jadbabaie. A non-asymptotic analysis of oversmoothing in graph neural networks. arXiv preprint arXiv:2212. 10701, 2022.
[40] Tomer Galanti, András György, and Marcus Hutter. On the role of neural collapse in transfer learning. arXiv preprint arXiv:2112.15122 2021.
[41] Tomer Galanti, András György, and Marcus Hutter. Improved generalization bounds for transfer learning via neural collapse. In First Workshop on Pre-training: Perspectives, Pitfalls, and Paths Forward at ICML 2022, 2022.
[42] Mayee Chen, Daniel Y Fu, Avanika Narayan, Michael Zhang, Zhao Song, Kayvon Fatahalian, and Christopher Ré. Perfectly balanced: Improving transfer and robustness of supervised contrastive learning. In International Conference Machine Learning, pages 119003122. PMLR, 2022.
[43] Tomer Galanti, András György, and Marcus Hutter. Generalization bounds for transfer learning with pretrained classifiers. arXiv preprini arXiv:22/2.12532, 2022.
[44] Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al. Matching networks for one shot learning. Advances in neural information processing systems, 29, 2016.
[45] Jake Snell, Kevin Swersky, and Richard Zemel. Prototypical networks for few-shot learning. Advances in neural information processing systems, 30, 2017.
[46] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems, 34:1048-1061, 2021.
[47] Vikas Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. In International Conference on Machine Learning, pages 3419-3430. PMLR, 2020.
[48] David McAllester. Simplified pac-bayesian margin bounds. In Learning Theory and Kernel Ma- chines: 16th Annual Conference on Learning Theory and 7th Kernel Workshop. COLT/Kernel 2003, Washington, DC, USA, August 24-27, 2003. Proceedings, pages 203-215. Springer, 2003.
[49] Andreas Maurer. A note on the pac bayesian theorem. arXiv preprint cs/0411099 2004.
[50] Eugenio Clerico, George Deligiannidis, and Arnaud Doucet. Wide stochastic networks: Gaussian limit and pac-bayesian training. In International Conference on Algorithmic Learning Theory, pages 447-470. PMLR, 2023.
[51] Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbich, Gabriel Arpino, and Daniel Roy. On the role of data in pac-bayes bounds. In International Conference on Artificial Intelligence and Statistics, pages 604-612 612. PMLR, 2021.
[52] Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. In International conference machine learning, pages 1725-1735. PMLR, 2020.
[53] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference Learning Representations.
[54] Sami Abu-EI-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-oree graph convolutional architectures via sparsified neighborhood mixing. In international conference on machine learning, pages 21-29. PMLR, 2019.
[55] Meng Liu, Hongyang Gao, and Shuiwang Ji. Towards deeper graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 338-348.4 2020.
13

---

[56] Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem. Deepgens: Can gens go as deep as cnns? In Proceedings of the IEEE/CVF international conference on computer vision, pages 9267-9276, 2019.
[57] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International conference on machine learning, pages 5453-5462. PMLR, 2018.
[58] Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. arXiv preprint urXiv:/905, 10947, 2019.
[59] T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint MrXXi:233031099 2023.
[60] Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. In Proceedings of the AAAI conference artificial intelligence, volume 34, pages
2020.
[61] Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the AAAI conference on artificial intelligence, volume 32, 2018.
[62] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. arXiv preprint ar arXiv2220..02466. 2022.
[63] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 34:27965- 2021.
[64] Yizhou Zhang, Guojie Song, Lun Du, Shuwen Yang, and Yilun Jin. Dane: Domain adaptive network embedding. International Joint Conference Artificial Intelligence, abs/1906.00688. 0060044406044322222 4368446663-388, 2019.
[65] Hongrui Liu, Binbin Hu, Xiao Wang, Chuan Shi, Zhiqiang Zhang, and Jun Zhou. Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference 2022, pages 1248-1258, 2022.
[66] Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji. Good: A graph out-of-distribttion benchmark. In Thirty-sixth Conference on Neural Information Processing Systems Datasets and Benchmarks Track.
[67] Haitao Mao, Lun Du, Yujia Zheng, Qiang Fu, Zelin Li, Xu Chen, Shi Han, and Dongmei Zhang. Source free unsupervised graph domain adaptation. arXiv preprint arXiv:2112.0095. 2021.
[68] Joaquin Quinonero- Muinonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D Lawrence. Dataset shift in machine learning. Mit Press, 2008
[69] Jose G Moreno-Torres, Troy Raeder, Rocío Alaiz-Rodriguez Nitesh V Chawla, and Francisco Herrera. A unifying view on dataset shift in classification. Pattern recognition, 45(1):521-530 2012.
[70] Gerhard Widmer and Miroslav Kubat. Learning in the presence of concept drift and hidden contexts. Machine learning, 23:69-101, 1996.
[71] Shengyu Zhang, Kun Kuang, Jiezhong Qiu, Jin Yu, Zhou Zhao, Hongxia Yang. Zhongfei Zhang, and Fei Wu. Stable prediction on graphs with agnostic distribution shift. arXiv preprint arXiv:2 10.03865, 2021.
[72] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. The Eleventh International Conference on Learning Representations, 2023.
14

---

[73] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In The world wide web conference, pages 417-426, 2019.
[74] Ruichao Yang, Xiting Wang, Yiqiao Jin, Chaozhuo Li, Jianxun Lian, and Xing Xie. Reinforce- ment subgraph reasoning for fake news detection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2253 2262,226,,222 2022.
[75] Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah. unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 1202-1211, 2021.
[76] Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui. Interpreting and unifying graph neural networks with an optimization framework. In Proceedings of the Web Conference 2021, pages 1215-1226, 2021.
[77] Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi. Grale: Designing net- works for graph learning. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & data mining, pages 2523-2532, 2020.
[78] Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen Ahmed, and Danai Koutra, Graph neural networks with heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 168-11176, 2021.
[79] Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the same coin: Heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), pages 1287-1292. IEEE, 2022.
[80] Mingguo He, Zhewei Wei, Hongteng Xu, et al. Bernnet: Learning arbitrary graph spectral filters via bernstein approximation. Advances in Neural Information Processing Systems, 11.14229-1425/1 2021.
[81] Sannat Singh Bhasin, Vaibhav Holani, and Divij Sanjanwala. What do graph convolutional neural networks learn? arXiv preprint arXiv:2207.01839, 2022.
[82] Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova. Characteriz- ing graph datasets for node classification: Beyond homophily-heteroophn dichotomy, arXiv preprint arXiv:2209.06177 2022.
[83] Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang. Fairwalk: Towards fair graph embedding. 2019.
[84] Indro Spinelli, Simone Scardapane, Amir Hussain, and Aurelio Uncini. Fairdrop: Biased edge dropout for enhancing fairness in graph representation learning. IEEE Transactions on Artificial Intelligence, 3(3):344-354, 2021.
[85] Ziqian Zeng, Rashidul Islam, Kamrun Naher Keya, James Foulds, Yangqiu Song, and Shimei Pan. Fair representation learning for heterogeneous information networks. In Proceedings of the International AAAI Conference on Web and Social Media, volume 15, pages 877-887,
2021.
[86] Xianfeng Tang, Huaxiu Yao. Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltu- ional networks. In Proceedings of the 29th ACM International Conference on Information & Knowledge Management, pages 1435-1444, 2020.
[87] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigating data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, pages 1259-1269, 2022.
[88] Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, and Bobby Bhat- tacharjee. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference Internet measurement, pages 29-42, 2007.
15

---

[89] Simon S Du, Kangcheng Hou, Russ R Salakhutdinov, Barnabas Poczos, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. Advances in neural information processing systems, 32, 2019.
[90] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac- mac-bayesian approach to generalization bounds for graph neural networks. arXiv preprini urXiv:2012.076690 2020.
[91] Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In Proceedings of the 25th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 1539-1548, 2019.
[92] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik chervk-cervonnnkis dimension of graph and recursive neural networks. Neural Networks, 108:248-2555 259, 2018.
[93] Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances Neural Information Processing Systems, 34:9936-9949 2021.
[94] Ran Ylnia and Dmitry Pechyony. Stable transductive learning. In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25, 2006. Proceedings 19, pages 45-49. Springer, 2006.
[95] Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. In Proceedings of the 33rd Annual Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
[96] Nan Ding, Xi Chen, Tomer Levinboim, Soravit Changpinyo, and Radu Soricut. Pactran: Pac-bayesian metrics for estimating the transferability of pretrained models to classification tasks. In Computer Vision-ECCV 2022: 17th European Conference, Tel Aviv, Israel, October 23-27, 2022, Proceedings, Part XXXIV, pages 252 22-26...222 Springer, 2022.
[97] Anthony Sicilia, Xingehen Zhao, Anastasia Sosnovskikh, and Seong Jae Hwang. Pac bayesian performance guarantees for deep (stochastic) networks in medical imaging. In Medical Image Computing and Computer Assisted Cnterventtoo-MMCCCA 2021: 24th International Conference, Strasbourg, France, September 27-October 1, 2021, Proceedings, Part III 24, pages 560-570. Springer, 2021.
[98] Zifan Wang, Nan Ding, Tomer Levinboim, Xi Chen, and Radu Soricut. Improving robust generalization by direct pac-bayesian bound minimization. arXiv preprint arXiv:2211.12624 2022.
[99] Joel Tropp al. An introduction matrix concentration incqualities. Foundations and Trends@ in Machine Learning, 8(1-2):1-230 2015.
[100] Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to decetraly-normallin margin bounds for neural networks. arXiv preprint arXiv:1707.0956. 2017.
[101] Cheng Yang, Jiawei Liu, and Chuan Shi. Extract the knowledge of graph neural networks and go beyond it: An effective knowledge distillation framework. In Proceedings of the web conference 2021, pages 1227-1237, 2021.
[102] Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and data mining, pages 807-816, 2009.
[103] Jure Leskovec and Andrej Krevl. Snap datasets: Stanford large network dataset collection, 2014.
[104] Oleg Platonov, Denis Kuznedelev. Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of GNNs under heterophily: Are we re- ally making progress? The Eleventh International Conference on Learning Representations, 2023.
16

---

[105] Arpandeep Khatua, Vikram Sharma Mailthody, Bhagyashree Taleka, Tengfei Ma, Xiang Song. and Wen-mei Hwu. Igb: Addressing the gaps labeling, features, heterogeneity, and size of public graph datasets for deep learning research. arXiv preprini arXiv:2302. 13522, 2023.
[106] Arthur Gretton, Karsten M Borgwardt, Malte J Rasch, Bernhard Schölkopf, and Alexander Smola. A kernel two-sample test. The Journal of Machine Learning Research, 13(1):723-773, 2012.
[107] Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al. Exploring the potential of large language models (Ilms) in learning on graphs. arXiv preprint arXiv:230.003993 2023.
[108] Daniel Zügner, Amir Akbarnejad, and Stephan Günnemann. Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD international conference 2018.
on knowledge discovery & data mining, pages
[109] Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung- Yu Hsieh, and Vasant Honavar. Adversarial attacks graph neural networks via node injections: A hierarchical reinforcement learning approach. In Proceedings of the Web Conference 2020, pages 673-683, 2020.
[110] Kaidi Xu, Hongge Chen, Sijia Liu, Pin Yu Chen, Tsui Wei Weng, Mingyi Hong, and Xue Lin. Topology attack and defense for graph neural networks: An optimization perspective. In 28th International Joint Conference on Artificial Intelligence, IJCAI 2019, pages 3961-3967. International Joint Conferences Artificial Intelligence, 2019.
[111] Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Alcksandar Bojchevski, and Stephan Günnemann. Robustness of graph neural networks at scale. Advances in Neural Information Processing Systems, 34:7637-7649, 2021.
[112] Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang Tang. Adversarial attacks and defenses on graphs. ACM SIGKDD Explorations Newsletter, 22(2):19- 34, 2021.
[113] Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan. Hiding individuals and communities in social network. Nature Human Behaviour, 2(2):139-147, 2018.
[114] Daniel Zügner and Stephan Günnemann. Adversarial attacks on graph neural networks via meta learning. In International Conference on Learning Representations.
[115] Jiong Zhu, Junchen Jin, Donald Loveland, Michael T Schaub, and Danai Koutra. How does heterophily impact the robustness of graph neural networks? theoretical connections and practical implications. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2637-2647, 2022.
[116] Kuan Li, Yang Liu, Xiang Ao, and Qing He. Revisiting graph adversarial attack and defense from a data distribution perspective. The Eleventh International Conference on Learning Representations, 2023.
[117) Yu Song and Donglin Wang. Learning on graphs with out-of-distribution nodes. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1635-1645, 2022.
[118] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jen- nifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79:151-175, 2010.
17

---

Appendix
Table of Contents
A Related work
19
B Investigation on the effectiveness of homophily ratio difference with targeted synthetic
edge addition algorithm.
20
B.1
Targeted heterophilic & homophilic edge addition algorithms
20
B.2
Detailed experiment results
21
B.3 Details on the generated graph
22
Instance-level discriminative analysis
23
D
Effects of aggregation nodes in different classes with structural disparity
25
D.1
Linear separability analysis based CSBM model
25
D.2
Linear separability experiment on synthetic CSBM datasct
27
D.3 Proof details of linear seperability within the same pattern
27
Proof details linear separability between different structural patterns
29
E
Proof details of the conditional probability difference for nodes with the feature different structural patterns
F
Proof details of PAC-Bayes Bound
33
F.1
Background Knowledge PAC- Bayes Analysis
33
F2
PAC PAC-Bayesian Analysis on Subgroup Generalization bound of Deterministic classilier
33
F3
Proof details of Expected Loss Discrepancy)
34
Proof details of subgroup generalization Bound for GNNS
38
Experiment details
40
Hardware Software Environment
40
G.2
Model details & hyperparameter settings & results
40
3 Dataset details
41
G.4
OOD dataset statistics and details
43
Additional results on performance comparison between GCN and MLP-based models
46
Additional results on performance comparison between GCN and deeper GNN models
Additional Experiment performance disparity across subgroups
47
J.1 Additional investigation on higher-order neighborhood
49
122 Additional results on more dalasets
49
Additional investigation on the discriminative ability of GCN
50
L Significant between GCN and MLP-based models
51
Significant test between GCN and deeper GNN models
51
N Limitation
52
Broader Impact
53
Future work
18

---

A Related work
Graph Neural Networks (GNNs) have emerged as powerful technique in Deep Learning, specifi- cally designed for graph-structured data. They address the limitations of traditional neural networks in dealing with irregular data structures. GNNs learn node representations by aggregating neighborhood and transforming features recursively. The node representation can then be successfully utilized to wide range of graph-related downstream tasks 2
6 73 74).
The aggregation mechanism in GNNs is often viewed as feature smoothing [6] 75 76.. This
perspective leads some recent studies [26 53 20 77 claiming that GNN models are overly reliant
on homophilic patterns and unsuited to capturing heterophilic patterns To accommodate heterophilic graphs, recent works propose carefully designed GNN architectures, e.g., CPGNN 78 GGNN (79),
GPRGNN [53, GCNII [52] GBK-GNN [27]. ACM-GNN [19], Bernnet [80).
33 19 indicate that even GCN (2] vanilla GNN, can deliver strong performance on certain heterophilic graphs. According to these findings, new metrics and un- have been proposed further expose the remaining weaknesses
More recent analyses on GNNs 18
derstandings 81
19
28
of GNNs.
There is concurrent work 28 investigates when Graph Neural Networks help with node classifica- tion with a comparison between GNN and MLP. Nonetheless, our work is distinct from (2 in two primary ways:
28 is majorly grounded on the CSBM-H model focusing on different feature variances for
different classes, from a feature perspective. In contrast, our work examines the homophilic and heterophilic patterns from a structural perspective instead of sharing the same node homophily ratio across the graph.
[28] proposes a new metric to identify whether GNN can outperform graph- happoshgnsticc MLP on particular datasets. Nonetheless, it still focuses on all the nodes in the whole graph together. In contrast, our work reveals the scenario where GNNs show performance degradation on certain node subgroup across most homophilic and heterophilic graph datasets. Typically, we focus on a node subgroup perspective, rather than all nodes in the whole graph. Our paper highlights the drawback of GNNs in more general case.
Fairness on Graph Although recent years have seen a satisfying performance from Graph Neural Networks (GNNs), risks can be found. GNNs may unintentionally learn and perpetuate biases present in the training data, potentially resulting in unfair outcomes for certain populations. Such risks raise concerns about biases and discriminatory behaviors when GNNs are used in human-centric applications.
Fairness issues on graphs can be roughly categorized into attribute bias and structural bias, based on the source of the bias. Several works (35 83) focus on fairness issues originating from sensitive node attributes, c.g., gender or underrepresented ethnic groups. Other literature [63] 46 86
focuses on addressing fairness issues arising from different structural information, e.g.. degree, geodesic distance to the training node, and Personal Pagerank score. Our work aligns closely with structural bias, showing that larger homophily ratio difference between training and test nodes may lead to performance degradation. To the best of our knowledge, we are the first to propose this performance disparity induced by the homophily ratio difference.
Generalization ability analysis on Graph Neural Network The generalization ability analysis on Graph Neural Networks aims to develop theoretical understandings of GNNs with focus on the uniqueness of the graph structure. Recent research progress reveals the generalization ability [89] 47 92 of GNN across different tasks and settings. Our work typically studies the generalization ability on the transductive node classification task indicating relationship with [93] 14 18 13]
Typically, [93] employs the transductive uniform stability [94] to understand why deeper GNNs
generalize better than the vanilla GCN. Several studies [14, 18 [3] investigate the generalization
of GCN under the CSBM model assumption, while they focus on either homophilic or heterophilic patterns rather than consider both patterns together. (46) provides the first non-i.i.d. PAC-Bayes However, there are key
generalization bound on GNNs, serving as the basis of our theory |
differences between our work and [46] detailed as follows:
19

---

Assumption difference. 46 assumes the existence of e-Lipschitz continuous functions on the conditional probability of y, k given the aggregated feature gi(X,, G). denoted as P P(y kgge( (1,((X,C0 G)). The assumption suggests that nodes with a closer distance are likely to belong to the same class. However, this assumption may not align with the real-world scenario where nodes with closer distances may belong to different classes when they exhibit a large homophily ratio difference, as shown in Lemma] [ In contrast, we utilize a different assumption considering the influence of the structural pattern on the conditional probability, enabling analyses on the scenario that nodes with closer distance but from different classes. This scemario happens frequently when the graph is mixture of homophilic and heterophilic patterns. An intuitive illustration can be found in Figure |
Application scope difference. [46] is primarily focused on the homophilic graphs and does not easily extend to the heterophilic ones. Empirical evidence can be found in Section 3.4 and Appendix [ In contrast, our theory can be established on most datasets except for the Actor dataset which structural information hardly helps.
Disclaimer: Structural disparity is different from distribution shift between train and test data. The structural disparity is that homophilic and heterophilic patterns exist simultancously a single node set. Such disparity consistently exists in all graphs, as shown in Figure 2 If randomly sample train and test data, the distribution shift between train and test will not happen. Both train and test sets will have homophilic and heterophilic patterns, indicating structural disparity happens on both the train and test sets.
B Investigation on the effectiveness of homophily ratio difference with targeted synthetic edge addition algorithm.
In Section 3.4 we intuitively show that a larger homophily ratio difference could be a key reason for performance disparity. We demonstrate the effectiveness of intuition with both theoretical analysis and experiments conducted on real-world datasets. To further verify the influence of the homophily ratio difference, we conduct more controllable synthetic experiments adopted from [33, adding different amounts of synthetic edges on real-world datasets, to further evaluate how the performance of GCN, a vanilla GNN, changes on varied homophily ratio differences. Typically, we are to manually make heterophilic nodes more homophilic and make homophilic nodes more heterophilic with the targeted homophilic edge addition and the targeted heterophilic edge addition algorithms, respectively. Notably, despite synthetic edges added, we utilize the real- woold dataset serves as the entrance to keep the analysis more approach to the real-world scenario. The following subsections are organized as follows. We first introduce the targeted heterophilic and homophilic edge addition algorithms and how it leads to larger homophily ratio difference in Appendix [.I] Detailed experiment analysis can be found in Appendix B.2 Further experiment details can be found in the Appendix B.3
B.1 Targeted heterophilic & homophilic edge addition algorithms
Both targeted heterophilic and homophilic edge addition algorithms commence with standard, real- world benchmark graphs, modifying the structure by adding synthetic edges to manipulate the homophily ratio on either train nodes or test nodes. For example, we can add synthetic heterophilous edges on the targeted test nodes in homophily graph. Consequently, a homophily ratio difference between the training and testing nodes can be observed.
We first introduce the homophilic edge addition algorithm, shown in Algorithm I Specially, we introduce a total of K edges on either training or targeted test nodes on heterophilic dataset, denoted Virrgeted. For each edge addition, node u is uniformly sampled from the targeted node set, Virgeted. and obtains its corresponding label, ya. Another targeted node v sharing the same label, yeu is selected, and a homophilic edge is added between them, resulting in homophily ratio decrease. Consequently, we can observe a homophily ratio decrease on both target nodes u and e with the new homophily edge added. Notably, we only add synthetic edges among targeted nodes, ensuring the homophily ratio unchanged on the other nodes.
The heterophilic edge addition algorithm, shown in the Algorithm 2 is analogous to the homophilic one. The only difference is the selection of a newly added heterophilic edge instead of the homophilic one. While homophilic edges can be readily added by connecting nodes within the same label, adding
20

---

cross-label heterophilic edges poses a new challenge that the target node should be connected to which label, other than the target label ya- Typically. we follow the principle [ that nodes with the same label should share similar neighborhood label distributions. This principle aligns with the CSBM assumption, discussed in Section 3 Specifically, given a real-world graph G, we first define discrete neighborhood target label distribution De for each label c E C. Examples of D. can be found in Appendix [B.3] Specifically, we will first randomly select label e based on distribution De. Another node in the target set with label e is then selected, and heterophilic edge is added between them. This process enables us to add heterophilic edges on target nodes following similar neighborhood label distributions.
Algorithm 1: Targeted Homophilie Edge Addition
input :G (V.E), Viargeted E V, K, and (V output: = =[V."}
Initialize 5 =E 1;
while S S K do
do
Sample node i ~ Unifunn (Varrgmn)aagge)dd)): Obtain the label, of node i; Sample node j Uni Veargeted);
while (i E E
Update edge E" E' ((1,))); + 1;
10 return G' = (V,E"}
Algorithm 2: Targeted Heterophilous Edge Addition
input :g {V,E). Viargeted V. K, ( and (V. -el-1 output::" (V,E'
Initialize 8" E =
while S. k S. K do Sample node i Unitorr((iarggtedl)
Obtain the label, yr of node i;
Sample number r ~ Uniform(0.1);
Sample label e ~ D Sample node j Uniform(V. n Veargetea); {(i,))};
Update edge set E' k 4- & + 1; return g' = (V,8")
B.2 Detailed experiment results
In this section, we conduct experiments on the homophilic graph, Cora, employing the targeted homophilic edge addition algorithm, and the heterophilic graph. Squirrel, employing the targeted heterophilic edge addition algorithm. For each dataset, we apply the synthetic edge addition algorithm to training nodes and a subset of test nodes, respectively, resulting in homophily ratio difference between training and test sets. The synthetic edges are added gradually until reaching the predefined maximum budget Kmax- resulting in multiple synthetic graphs generated. More experimental details on the synthetic graphs can be found in Appendix B..3 The GCN, vanilla GNN model, trained from the sketch on each synthetic graph. The experimental results are illustrated in Figure [T] where the z-axis represents the edge permutation ratio calculated as Kan where K is the number of added edges on the i-th synthetic graph. The y-axis represents the test performance when adding synthetic edge on training nodes. When adding synthetic edges on the targeted test subset, The y-axis represents the performance on the targeted test node subset. clear degradation in test performance is observed with more and more synthetic edges added to test nodes and training nodes exclusively. The above observations clearly demonstrate that the GCN test performance will degrade with larger homophilic ratio difference between train and test nodes.
21

---

1.0
0.6
train
train
test
tost
0.5
Test acc
Test acc
0.6
0.4
0.4
0.3
0.0
0.2
0.4
0.6
0.8
1.0
0.2
0.0
0.2
0.4
0.6
0.8
1.0
Edge ratio
Edge ratio
(a) Synthetic graphs generated from Cora with the (b) Synthetic graphs generated from Squireel with the targeted heterophilic edge algorithm
targeted homophilious edge algorithm
The performance of GCN on synthetic graphs with various edge permutation ratios. The y-axis represents the test performance all nodes when adding synthetic edge training nodes. When adding synthetic edges on the targeted test subset, The y-axis represents the performance on the targeted node subset. Test performance generally decrease with more synthetic edges added with large homophily ratio difference.
Figure 10:
B.3 Details on the generated graph
In this subsection, we elaborate on the details of the synthetic graphs generated Appendix [.2 Specifically, provide more details regarding the distributions De, E C employed in the Cora and Squirrel datasets. We adopted circulant matrix-like designs for simplicity and straightforward implementation. We also show details on the number of added edges, and the corresponding graph homophily ratio on the Cora and Squirrel datasets.
Cora We utilize the targeted heterophilic edge addition algorithm on the Cora dataset. The Cora dataset has seven labels that we represent as 1, 2, 3, 4, 5, 6. and the neighborhood distributions Des E C for adding heterophilic synthetic edges are presented as follows.
Do Categorical 0, 0,,,0,,,),
D1 : Categorical 0,.,
D2 Categorical(0,, (,,,,,0,,,00,,,,,,0,0,,
D3 : (ategorical(0),.) (,,0, 0,000
D4 (1000oricaa(00,,,,,00...,,
D3 Categorical (0,0,0,0,055,00000,))
Da
The number of added edges K and the corresponding homophily ratio / on the targeted test nodes and the train nodes are presented in Table and respectively.
Table 2: K and h values for graphs with synthetic edges added targeted test nodes on Cora
100
200
300
400
500
600
700
800
900
h 0.645
0.483
0.382
0.321
0.279
0.249
0.223
0.206
0. 194
Table 3: K and h values for graphs with synthetic edges added targeted training nodes Cora
K
200
400
600
800
1000
1200
1400
1600
1800
h 0.620
0.507
0.424
0.365
0.324
0.292
0.264
0.243
0.224
22

---

Squirrel We utilize the targeted homophilic edge addition algorithm on the Squiree dataset. We first sample the label from discrete uniform distributions. Then, we randomly select two nodes with the same label and do not have an edge between them. The number of added edges K and the corresponding homophily ratio h on the targeted test nodes and train nodes are presented in Table and respectively.
Table 4: K and h values for graphs with synthetic edges added targeted test nodes on Squirrel
K
100
200
300
400
500
600
700
800
900
0.237
0.345
0.412
0.467
0.505
0.536
0.562
0.585
0.606
Table 5: K and h values for graphs with synthetic edges added targeted train nodes on Squirrel
K'
1500
3000
4500
6000
7500
9000
10500
12000
13500
h 0.261
0.299
0.330
0.356
0.379
0.399
0,417
0.434
0.448
C
Instance-level discriminative analysis
In section 3.2
we conduct a discriminative analysis considering the distance between the feature means from different classes from a global perspective. In this section, we further investigate the discriminability from an instance-level perspective. Specifically, we focus on the feature distance between different nodes feature rather than the feature mean.
To qualify the discriminative difficulty on the feature of each individual test node, we propose the two metrics, local agreement ratio, and local accuracy difference. The local agreement ratio aims to measure the local clustering property in a KNN manner. It can be calculated with the following steps: (1) Given a particular node, find the top-k feature-close train nodes. We set A = 9 in our experiment, and L2 distance is utilized as the feature distance metric. (2) Given the top-k closest train nodes, we examine the number of nodes each label. If there exists a particular label e with the number of nodes over $ it indicates that over half of neighborhood nodes reach an agreement on the class (3) The local agreement ratio can then be calculated as the proportion of nodes reaching an agreement in the test set, denoted as:
Evev. 1 [3c E &.C.MMM A
VVal
where is the local agreement ratio, Vie and C are the test node set and class set, respectively. M,, is the node set including top-k nearest training of the node v. [M&) is the number of nearest training nodes in class A larger agreement ratio on the test set indicates the data are more clustered with close distance between train and test nodes. Nonetheless, a higher agreement ratio does not naturally lead to a better discriminative ability. Despite the top-k feature-close nodes reaching agreement on a particular class, the test node may have a different class from the agreement. It indicates that the center node misaligns with the top-k feature-close nodes.
The local accuracy is then proposed to identify whether the category of the center node aligns with the agreement from top-k feature-close nodes. Concretely speaking, the local agreement accuracy is the proportion of agreement nodes in the test set. It can be calculated as:
EveVine
[c. cN.)
AcCiocal
V
Vagreel
where Vagree is the test node set reaching top-k feature-close nodes agreement. c, is the category of node v. CM, is the agreement category from feature-closs nodes. A higher local agreement accuracy indicates that most agreement nodes are aligned with the same category.
Similar to the relative discriminative ratio proposed Section 3.2 we illustrate the local agreement accuracy improvement on the majority nodes over minority nodes. Experiments are conducted on four homophilic datasets, Cora, CiteSeer, PubMed and Ogbn-arxiv, and two heterophilic datasets, Chameleon and Squirrel. The experimental setting details can be found in Section G Experiment
23

---

1.0
1.0
hete
hete
homo
homo
0.8
0.8
0.6
0.6
Ratio
Ratio
0.4
0.4
0.2-
0.2
0.0
1
2
3
4
1
2
3
4
#aggregation
#aggregation
(a) Cora (/=0.81)
(b) CiteSeer (/=0.711)
hete homp
hete
homo
1.0
Ratio
Ratio
0.8
0.6
0.6
0.4
0.4
2
3
0.2
#aggregation
#aggregation
(c) PubMed (h=0.79)
(d) Ogbn arxiv Drxivarxiv (/=0.63)
hete
hete
homo
homo
1.0
Ratio
Ratio
0.6
0.6
0.4
0.4
0.2
2
3
3
#aggregation Chameleon (/=0.25)
#aggregation
(f) Squirrel (k=0.22)
Figure 11: Illustration of the change local agreement ratio along with the aggregation. The x-axis represents the number of aggregations and the y-axis represents the local agreement ratio. For homophilic graphs, the local agree ratio generally increases along with more aggregations, indicating better cluster effects. For heterophilic graphs, the local agreement ratio shows an opposite phenomenon, which decreases consistently.
results on local agreement ratio and local agreement accuracy difference are illustrated in Figure [] respectively.
and [2]
24

---

The observations can be found as follows: (1) For homophilic graphs, the local agree ratio generally increases along with more aggregations, indicating better cluster effects. Meanwhile, the relative accuracy improvement on the majority nodes also increases, further indicating the disparity effects on different nodes group with more improvement on the majority nodes. (2) For heterophilic graphs, the local agreement ratio shows an opposite phenomenon, which decreases consistently. Meanwhile, the relative accuracy improvement on the majority nodes only increases on the first two hops and decrease and decline from the third hop. The potential reason is that, despite general global trend, the heterophilic patterns on each individual node may still be quite complicated, with a local pattern shift disparity. We leave the discussion more complex local structure patterns as the future work.
Cora
PubMed
CiteSeer
Arxiv
Chamelean
Squirrel
0.5
0.4
0.4
0.3
0.3
Acc
Acc
0.2
0.2
0.0
0.1
-01
-0.2
4
5
3
4
5
#aggregation
#aggregation
(a) Homophilic graphs
(b) Heterophilic graphs
Figure 12: Illustration of the change on local agreement accuracy difference between the majority and minority patterns along with the aggregation. The x-axis represents the number of aggregations and the y-axis represents the majority local agreement accuracy minus the minority local agreement accuracy. For homophilic graphs, the relative accuracy improvement increases, further, while the relative accuracy improvement on the majority nodes only increases on the first hops and decrease and decline from the third hop.
the majority nodes also
D Effects of aggregation on nodes in different classes with structural disparity
In Section 3.1 we examine the behavior difference between nodes from the same class but with different structural patterns. In this section, we further provide more complicated analysis focusing on the between-class patterns, i.e., linear separability. Notably, linear separability is good indicator of feature differences in different classes, where features with better linear separability can be easier to distinguish with a suitable linear classifier.
D.1 Linear separability analysis based CSBM model
To ease the analysis, we utilize the CSBM-S model as the data assumption showing as follows:
Definition 1 (CSBM-S(11, u2, (p(2), g (n!2), (2))), Pr(homo))), The generated nodes consist of two disjoint sets Cn and Cz. each node feature x is sampled from N I) with E (1,2). Each set C, consists of two subgroups: c, for nodes in homophilic pattern with intra-class and inter-class edge probability (()) > (1) and c(2) for nodes in heterophilic pattern with 2!2) > q(2), Pr(homo) denotes the probability that the node is in the homophilic pattern. c(a) denotes node in class and subgroup with (p(i), g())). We assume nodes follow the same degree distribution with (!)) (1) (2)) + (2))
The original node features follow the Gaussian distribution:
X, N (Mi for i Cj; and x4 N I) for e C2
(6)
25

---

Where C corresponds to the node set corresponding to class i.
Based on the neighborhood distributions, the mean aggregated features F D-1D-AAN obtained follow Gaussian distributions on both homophilic and heterophilic subgroups.
(DD pp0pp p1 + &gg I ) for i E c/ ~ N (89 + 12 (pl) + +g()) vd.)
p/0 N
for i c(
pb)
+ +q))) Vd.
(7) Where c. is the node subgroups with structural pattern with (p (00)) in label i. To more accurately assess the effectiveness of the aggregation mechanism, we execute the largest-margin linear classifiers on nodes and evaluate their performance, to illustrate the linear separability. Notably, linear separability depends on the distance between the mean features of different classes as well as the standard deviations within each class. Typically, we focus on examining the linear separability on (1) nodes from different classes with the same structural patterns (2) nodes from different classes with different structural patterns, i.e., homophilic and heterophilic patterns.
We first examine the linear separability for nodes from different classes within the same structural pattern. We can summarize the proposition as follows:
Lemma 2 (Linear separability on nodes with the same structural patterns ). Considering mean aggregated features are from the same structural pattern r(") for , E {1,2}. For any node the
largest-margle linear classifier on p(5) will have a lower probability to misclassify than xi, when
d;
(p
The detailed proof can be found in Appendix D.3 The proposition suggests that aggregated features
f have better linear separability than the original feature x when the node i satisfies dN > (p()) q (( (1)))/((0)> show better linear separability with d; > 1.75, which are commonly met in real-world scenarios. This indicates that aggregation is likely to contribute to improved feature separability within the same node subgroup sharing similar structural property.
For instance, when p(2) = 0.9 and (( = 0.1, the aggregated features are easier
We then examine the linear separability for nodes from different classes within different structural patterns, e.g., (1(t) and ( Before diving deep into the rigorous analysis, we first illustrate a special
example to show how the structure can lead to worse linear separability. When p(!) = =g (2)) and
(1)) p2)), we can identify that the f and 1:(2) are exactly generated from the same distribution. Such distribution can hardly be linearly separable. We then conduct a more rigorous analysis showing
a similar observation with the same pattern one. We can summarize the proposition as follows:
Lemma 3 (Linear separability on nodes with different structural patterns). Consider features are from different structural patterns, where f(D) for i E C₁ and r!2) for i E Cz. For any node i, the largest-mon margin linear classifier will have a lower probability to misclassify f(2) for E C1 and (p00)0007 202
p/2) for E C2 than x, when d, (p00 1085
we can find that aggregated feature show better separability when d. > (p(1) +
-2(2) 2
The detailed proof can be found in Appendix D.4 For instance, when (()) = 0.9, ())) 0.1 and p(2) = 0.2, ( 0.8, the aggregated features can only show better linear separability with d, > 100, which are hardly met in real-world scenarios. Notice that the only difference with the one in the same pattern one that the denominator is (p(1) q(2) 2 smaller than the Ip(1) - (2) since (12) (2) It indicates that only nodes with higher degrees. e.g., d; 100, can achieve improved linear separability.
analysis, we draw the conclusion that when nodes are in the same pattern, aggregation can show improved linear separability on (p()) + (2))// /Ip(1) - (1) < d, < (p(") + (')) )2 - (²)) while the ones in the different patterns cannot. It indicates that ag- gregation can help when nodes are in the same pattern, however, show limitation when nodes are from different patterns. Notice that, such linear separability can be evidence for different behavior on nodes with different patterns. Nonetheless, it cannot directly indicate the performance disparity. Feature separability is conducted based on the ideal classifier with the largest margin. Better feature
Based
26

---

separability does not necessarily result in better performance if the classifier is not well-trained with biased training data.
D.2 Linear separability experiment on synthetic CSBM dataset
In this section, aim empirically examine the validity of the theoretical analysis results in Section D.I. We generate graph with the CSBM model with the following detailed settings. The class mean distance p ||ا| - اوl set to 0.1. The feature dimension d and the number of nodes are set to 50, and 500, respectively. and q correspond to probabilities of the intra-class and inter-class probability, respectively. The mean aggregation defined as F = D- X.. is the key to generating graphs with different structural properties. To generate the homophilic node subgroup with p > 9. we utilize the following settings with (p 0.01, q = 0.005). (p 0.01, q = 0.003). and (p = 0.01, 9 = 0.001). To generate the heterphilic node subgroup with p < g. we utilize the following settings with (p = 0.001, q = 0.005), (p- = 0.001, q = 0.003), and (p = 0.001, q = 0.002).
Experiments are conducted to examine how a linear model, logistic regression, fits effectively on the aggregated features. Higher performance on logistic regression indicates better linear separability of features. It is important to note that we focus on the fitting ability rather than the generalization performance. Consequently, we do not evaluate with a test set; instead, we provide all labels for training and assess the performance on all the nodes.
Experiments the logistic regression conducted on the homophilic nodes solely, heterophilic nodes solely, and a mixture of homophilic and heterophilic nodes. Typically, we aim to show the linear separability both within the same structural pattern and between homophilic and heterophilic patterns. Experimental results are presented in Table 6 The following observations can be made: (1) When considering nodes following the same structural pattern, either homophilic pattern or heterophilic pattern, better performance can be observed when the probability difference |p ql between intra-class and inter-class probability is larger. (2) Comparing the performance considering both structural patterns with the one on a single structural pattern, we reveal a noticeable performance degradation on the one with mixture patterns. This suggests that the nodes with different structural patterns results in decreased linear separability. (3) Comparing the performance among different mixing structural patterns, it is evident that larger homophily ratio differences, e.g., (p=0.01,, q=0.005) compared to (p=0.001, q=0.005), yield poorer performance than those with smaller homophily ratio differences. The above observations further supports the validity of Lemma 2 andd] 3 Theorem I
Table 6: The performance of logistic regression algorithm on homophilic nodes, heterophilic nodes, and a mixture of homophilic and heterophilic nodes. The results on the first row and first column correpond to the performance on homophilic nodes and heterophilic nodes, solely. Hete
p=0.11 q=0.005
p=0.01, q=0.003
p=0.01, q=0.001
7..69
82.71+1.86
92.08+1.113
+2.64 Q=0.00
0..64+0066
62.08+
81.38+11002
p=0.001, q=0.003 Q=0.00
70.0
59.72++.01
61.58
76.60++0.98
62.0813.00
65.92+1..55
69.42+1.03
14.16+1.09
D.3 Proof details of linear seperability within the same pattern
In this section, we provide detailed proof of the improved linear separability on aggregated features where nodes from different classes follow the same structural pattern. The following theoretical results indicate that it is more difficult to have improved linear separability when nodes follow different structural patterns. Notably, the following proof is derived based on (13). For completeness, we show the previous proof as follows, the difference is that we consider a more complicated CSBM-S model with both homophilic and heterophilic patterns rather than the simple CSBM model only describing either homophilic or heterophilic pattern.
Lemma 2 (Linear separability on nodes with the same structural patterns ). Considering mean aggregated features are from the same structural pattern f!",, for E (1, For any node the pargest-margün linear classifier on f(5) will have a lower probability to misclassify than Xs, when (p1))
d, (p0) -115
27

---

Notably, we only show the case p()) > g()) in Appendix D.1 for simplicity, It can be easily extend to pla) g( Proof details can be found as follows.
Consider the vanilla mean aggregation F D D--1A AX, the aggregated features with the same structure patterns follow Gaussian distributions:
f(5) N
p p1 + g00) 42
va.)) for : N
I
( (g0) ppp0ppp p2 I vT.) for i E C2 p() +()+ Vdd.)
pp)) +
Then we denote the expectation of the original node features in two classes as B,g [x,] and Eeg [xi) Similarly, we denote the expectation the aggregated features Eeg [f:] and Ees [f.].
Proposition 2. [Ec, [x.] Ec, [x.]) and (Ec, [f:] Ee, [f.]) share the same middle point. Ec, [x]]
Eey [x:] and Ee, [ Ec, [..] share the same direction.
The proposition can be calculated through direct calculations. we consider the feature distributions of two classes, we can observe that both x and f exhibit systematic relationship. As consequence, we can determine the optimal linear classifier for both x; and f,. We then define decision boundary #1 P2 and passes through the middle as the hyperplane that is orthogonal the direction w Mime wall
point m = (11 + (22 /2 as:
P x w x w (Iu + 12) /2]
We then show the proof details on when has a lower mis-classified probability than x with the same decision boundary, indicating better linear separability.
Proof. We provide the proof only for nodes belonging to class co. as the case for nodes from class ci is symmetric and the proof follows the same logic. For node in C1, We have the following:
P (x; is mis-classified ) PP (w + b 0) for C₁ IP (f, is mis-classified PP w f, + S 0) E C1,
(10)
can then scale the decision boundary without changing the original meaning. Then have (w f. + < 0) = P (Vd,w f, + d& S 0) We denote the scaled version of f, as fl = ddf, Then, f follows:
Vdl (p(i) u1 + (())pe)) pld) + g(5)
I 1) for i E C1
f
(11)
Given the scale in Eq. equation 11 the decision boundary for f/ is consequently shifted w If' Vd,b Now, considering that x; and f/ have the variance, classification probabilities by merely comparing the distance from their expected values to their corresponding decision boundaries. Specifically, the distances can be described follows:
compare the mis-
|| 12ll2
disx.
(12)
Talp() 96) p() + q0)
| 12ll2
disg
The larger the distance from the expectation to the decision boundary indicates a smaller the mis- classification probability. Therefore, when dis;: > disx,, ff has lower probability of being
(19)+ the
misclassified than x;. By comparing the two distances, we conclude that when d; (p())ggh p0n)=
mean aggregated feature f exhibits lower probability of misclassification compared to the original node feature x,.
pb0) + ++(5))) pp5) g(5)
P (f, is mis-classified ) < P (x; is mis-classified) ) if if
(13)
which completes the proof.
28

---

D.4 Proof details of linear separability between different structural patterns
In this section, we provide detailed proof of the improved linear separability on aggregated features where nodes from different classes follow different structural patterns. The following theoretical results indicate that is more difficult have improved linear separability when nodes follow different structural patterns. Notably, the following proof is derived based on [13]. For completeness, we show the previous proof as follows, the difference is that we consider a more complicated
CSBM-S model with both homophilic and heterophilic patterns rather than the simple CSBM model only describing either homophilic or heterophilic pattern
Lemma 3 (Linear separability on nodes with different structural patterns). Consider features are
from different structural patterns, where f for i C1 and r,²) for i C2. For any node i, the
largest-margin linear classifier will have a lower probability to misclassify F(t) for E C₁ and (p0))+00)
F(22) for E C2 than x; when d; > (n:0) (1155
In the following discussion, we only focus on the scenario where nodes in class o are in homophilic pattern with p(²) g(d), and nodes in class 02 are heterophilic pattern with p(2) < (()), The other scenario is symmetric and the proof follows the same logic.
Consider the vanilla mean aggregation as F D-1AA-AA AAX, the aggregated features with different structure patterns follow Gaussian distributions:
(1)) + (0)) p()) + q()) vT)) for (o; ~ N
( ( + +p2)) p42 pl2) + q(2)
) for i E
(1) N
"vd.)
(14)
Similar to the notation in Proposition 2 we denote the expectation of the original node features x in and Eeg [x:]. Similarly, we denote the expectation the aggregated features
two classes as Ee, [x.]
as Ee, [f:] and Eeg [f.].
Proposition 3. (Ee, [x,],Ee, Ee, [x:]) and (Ee, [f.] Eoz [f.)) share the same middle point. When satisfying p( q(2), Ec, [x,] Ec, [xx] and Ec, [f.] Eeg [f,] share the opposite direction.
Specifically, the middle point m and the shared direction w are as follows: m = (μ) + u2) /2, ) / [|m
and w = (M) (4)))))
-22l2-- When satisfying q(2) > p()) Ex, [x,] Ec, [x,] and
Ec, [h,] Ec, [hj] are same directions. It indicates that the largest-margin linear model still shares the same discriminative boundary which flips the prediction on class 01 and
Notably, with the assumption p()) + ( = =p(2) (2) the linear classifier can be generally to two cases according to whether the decision boundary direction flips: (1) The decision boundary
direction unchanged with q > >p()) > p(2) > ( (2) The decision boundary direction flipped with p)11) (2) > (2) > 2(2), Notably, the two cases symmetric with the same conclusion and proof
logic. We will focus on the unchanged case with q > (() > 22)) (1)
The proposition can be calculated through direct calculations. we consider the feature distributions of two classes, we can observe that both x and f exhibit a systematic relationship. As consequence, we can determine the optimal linear classifier for both x; and f,, We then define decision boundary as the hyperplane that is orthogonal the direction w [[ wall
P2 and passes through the middle
point m (11) + (22) / as:
P
x
w x w
(mI + m2) /2]
(15)
We then show the proof details when f has lower mis-classified probability than x with the same decision boundary, indicating better linear separability.
Proof. We provide the proof only for nodes belonging to class co, as the case for nodes from class Ci symmetric and the proof follows the same logic. For node in Ci, We have the following:
P (x, is mis-classified ) = P ( x; +b < 0) for fories C₁ TP (f, is mis-classified
(16)
w f, + bbb < 0) for u Ci,
we can then scale the decision boundary without changing the original meaning. Then we can have P (wT) f, b < 0) P (Vd,w") f, + /d,b < 0) We denote the scaled version of f, as fl /dfff Then, f follows:
29

---

Vdl (p(t) (d 1o + +200 pll) + q(1)
1) for E Ciiff N [dd (p!2) us + + (2) p(2) + 9(2)
N
1) for Co
(17)
Given the scale in Eq. equation 17 the decision boundary for f; is consequently shifted to w f + Vd,b 0. Now, considering that and f. have the same variance, we can compare the mis- classification probabilities by merely comparing the distance from their expected values to their corresponding decision boundaries. Specifically, the distances can be described as follows:
|1 12ll2
disx.
2 di Vdilp! - -0021
(18)
|1
Mall2
vdipp()) - 2 p()) + (1))
|| 12212
disg:
pl1) + q()1)
2
2
The larger the distance from the expectation to the decision boundary indicates a smaller the mis- classification probability. Notably, ((1) -p))) = p(1) - with the assumptin +p))) = +0)+
Therefore, when dise: > disx,, ff' has lower probability of being misclassified than By (10)) comparing the two distances, conclude that when d, -00)) the mean aggregated feature f exhibits a lower probability of misclassification compared to the original node feature x,.
((2) + g ((1) ((3)
IP (f, is mis-classified) ) < IP (x; is mis-classified) if d;
(19)
which completes the proof.
A comparison between linear separability within classes and between classes Notice that the only difference with the one in the same pattern one is that the denominator Ip()) 22) smaller than the (p()) - 122 since ((2) q (2)) It indicates that only nodes with higher degrees. For instance, when ( 0.9. (1)) 0.1 and p(2) 0.2, q(2) 0.8, the aggregated features can only show better linear separubility with d; > 100 when nodes are from different structural patterns. The above condition can be hardly met in real-world scenarios. Based on our analysis, we can draw the conclusion that when nodes are in the same pattern, aggregation can show improved linear separability on (p()) + (2)) (1)))/1p(2) - 1) < d; < (p!") + /( - y(2) 2 while the ones in the different patterns cannot. It indicates that aggregation can help more when nodes in the same pattern, however, show limitation when nodes are from different patterns.
E Proof details of the conditional probability difference for nodes with the same feature but different structural patterns
examine the discrepancy between nodes and with the same aggregated feature f. = fz but different structural patterns. Typically, we examine the discrepancy with the probability difference of nodes and 2 in class eı, denoted [p ci (f..) P2(y ci [f.)]- P1 and p2 are the conditional probabilities of node labels in e given the feature f for nodes on homophilic and heterophilic structural patterns, respectively. The lemma is shown follows:
In section 3.1
Lemma 1. With assumptions (1) balance class distribution with P(Y =) = P(Y 0) and (2) aggregated feature distribution shares the same variance oI. When nodes and v have the same aggregated features f,, f, but different structural patterns, (p()), (1)) and (2(2), (2))), we can have:
p²
Pv. = PP2 cf)...)
hm hol
(20)
V
||| المم is the original feature separability, independent with structure. P1 and P2 are the conditional probability of y Ci given the feature f on structural patterns (p(1), (())) and (2(2) (2)).
30

---

respectively. Lemma] I implies that nodes with small homophily ratio difference h1 - h22 are likely share the same class, and vice versa.
We first remind the assumptions of the CSBM-S model. There are two assumptions on the models: (1) Nodes from different components share the same feature distribution. In other word, node features within the same class are sampled from the same Gaussian distribution, regardless of different structural patterns. (2) Nodes from different components share similar degree distribution with p(!) + (()) 2 + q(²) Notably, our conclusions still valid without the above assumptions. Those assumptions are not strictly necessary but employed for the elegant expression.
Based on the neighborhood distributions, the mean aggregated features F D-'AX obtained follow Gaussian distributions on both homophilic and heterophilic node subgroups.
p(5) N (P (DUip + g(0 u2
.I) for i : ~ N (n + +l
.01) for i E cl ( (b6)) + g(0))
pp))
pb) + q()))
(21)
Where c( the node subgroups with structural pattern with (pl)),(0) typically homophilic pattern with p(4) > g(2) and heterophilic pattern with p!2) < q(2), To simply
) in label i. Notably, there are
p(0) ue as
the assumption for an elegant expression, we denote the aggregated feature mean, p
Mb where i and j correspond to the class and the structural pattern, respectively. For instance, μI1 represents the mean of nodes in class oj with the homophilic pattern. We then show the proof details as follows:
Proof. The conditional probability of class e₁ given the aggregated feature f, Pr = c1 (f:) can be derived with the Bayes theorem:
a) (faly. =
Pily. =(lua) Pf = 9 P(y, =1) + PI = P2), = C2)
Pf = =q)
(a)
P Pf Yu = 9) + Pi Pf(fulyu C2)
(22)
(fu (ru""
exp
(f--M111P
[fu-H'aa1
exp
+exp
where (a) we utilize the assumption Pyy a) = Ply 02). Notably, such assumption aims to
simplify for an elegant expression and better understanding, which is not necessary in our proof.
Hence, we have:
Py = ci(F.) - P2(y, = ci [f.)]
exp (- llf. -k'v111
llfo 11f211
exp
a²
exp (-1lfu- (iil=))i1)) + exp
[llu
1ifu-46111
[lfe -
lIfe -للييرريي
exp
+ exp
exp (fu (((=²² exp
(f. - مومم
(f. (F/=)
(fu, ((يzي
exp
exp
[Ilfe + exp
fu M4 1P
Ifo- M oz
exp
exp
+ exp
(23)
Notably, the denominator can be denoted as
exp (- |lf. --/iii11
[f, 1ff.-ubill
16n 112
) exp /expp(
[|f (-Ife (IIfo--aall?) texp
| pL22 112
m
eexp
o²
r²
(24)
|lf. [1fe-1ll 13)
where each exponential component is in exp is in the range [0, 4]. We then denote m (A), where A is constant, correspondingly Hence,
E [0. 1]. Therefore, the denominator m
31

---

we can have:
Pi(yu = = Pz(y. =1(
(f, -4i1" o²
[f, [f1--112))
exp (- -
(-
exp
exp
exp
o²
o²
(fu - -o/112 + +fo--1b22)
(fu -112)2
+ (f2 - -12213 -1)
-A) -cxp
exp
o²
[[(. - 1111)2 - -(f, - 11/2) (f2--1(2)21 + [(f -1/21) - -ff, - (22) )
(a) 0²
1
fu 10 #1 + 9 f2
2
tf (l
+ ( f2l
f.
(6) -2
pl1) + g(2)
+ p
(2)
p()) pez + (10) p1
(2))
p2 + 9( 11
fw
fr
p(1) 9(1)
p + 9(2)
12ll
p(1)
222)
(llEa
fell + p(1) + q(1)
11 H2ll)
V2Ta
p(2) + g(2)
1111 h22 .p p²
(e) v 12T
(25)
|| Mell is the original feature separability, independent with structure. |/1 hel is the homophily ratio difference between node and 2. We explain the key steps as follows: (a) is derived from Lagrange's 's mean value theorem. From the Lagrange mean value theorem we have,
exp(-x) x) - exp(
exp(-c)) x)
(26)
where & is between æ and y. Therefore,
lexp(-x) x)) = exp(-E)\b - x S x - yyl
(27)
since exp(-E) S
Knowing that (y = =.lf. P2(yo c.(fo)] < 1, we can easily get
exp (Lo-wún)² exp
exp( B) (f-- (
(28)
exp(-A)
where exp(B) 0, we
can
get
(f.-M11)
+ -Hhr
A. (fe (fa-u'z) +ile - ubx) > A.
Similarly, with
PP c. P2(y. f.)l O, we can get
0²
In conclusion, we have:
A (fa-1i 2 (fg m21)²
< 0
(29)
un ++(Fi mly
< 0
Let = A- (fe + 116-- and y = (f) k + = 0²
The proof is in equation 27
o²
complete.
p 1 and 1/2 p 12
(b) we utilize 1h11
p( +g(0)
+gl0
(c) we utilize f. = f, and h; = piy Notice that, (c) step can be easily generally to the case that f, o fo with l|f, - full S We can easily proof with the same logis. The lemma is shown as follows:
Lemma 2. With assumptions (1) A balance class distribution with P(Y = =P 0) and (2) aggregated feature distribution shares the same variance aI. When nodes have the same aggregated can have:
features [|f, f,ll S but different structural patterns, (pi)). (Q()) and (g(2).(())
P1 = c1 c.) -P2(u = c.(f,)) S
P. (cm + 1/1 - h2l .p)
(30)
2
32

---

P= || - -ell is the original feature separability, independent with structure. Lemma implies that nodes with a small homophily ratio difference [h, h21 are likely to share the same class, and vice versa.
F Proof details of PAC-Bayes Bound
In this section, we provide background knowledge, assumptions, and proof details on the PAC-Bayes analysis. Our PAC-Bayes bound is derived based on [46), which is the first PAC-Bayesiad analysis for GNN on the semi-supervised node classification task. details comparison between our bound and [46]
can be found in Appendix A
F1 Background Knowledge on PAC-Bayes Analysis
PAC-Bayes Analysis The Probably Approximately Correct-Bayesian (PAC-Bayes) analysis 48 is powerful theoretical framework utilizing Bayesian learning principles for analyzing the generalization ability of machine learning models. Typically. PAC-Bayesian Analysis is to connect and bound the difference between a training eπror of a machine learning model with its expected generalization 50 5T are proposed for advanced Deep Learning models in recent years. Such theoretical guidance shows practical success in many real-world applications
error. Various PAC-Bayes bounds 49 95
including pretraining model (96), medical image 197. and robustness
98
PAC-Bayes analysis on Graph Neural Networks (90 is the first -ay-eaaeii generalization bound for GNNs. Nonetheless, it focuses on the i.i.d. graph classification task, which is different from the non-i.i.d. node classification task. [46) provides the first PAC-Bayesian generalization bound for GNN on semi-supervised node classification task. Our following theorem is developed based on it and generalized into more generalized scenarios. A more detailed discussion on the difference of our work and [46] can be found in the Appendix
F.2 PAC-Bayesian Analysis on Subgroup Generalization bound of Deterministic classifier
In this section, we provide a more detailed discussion on the PAC-Bayesial analysis with the semi- supervised subgroup Generalization bound of Deterministic classifiers proposed in [46], which serves as the basis of proof. Notably, in the main content, we denote the training node subgroup as Vn, As focus the relationship between the train nodes and test subgroups Vm with m M, re-denote the train nodes as Vo The PAC-Bayesian analysis on subgroup Generalization bound of Deterministic classifiers, focusing on the deterministic classifiers h, a classifier drawn in the predictor family H. learned on training nodes. The primary objective of the PAC-Bayesian analysis bounds on the generalization gap between the empirical margin loss of h denoting as 2 (h) on the train node subgroup Vo and the corresponding expected margin loss C% (h) on the test node subgroup Vm. The empirical marginal loss 23 (h) on the train node subgroup Vo is defined as:
derive
1 (b) = No
Σ VeVo
[ (ha(x,G)uu S + + (X, (k) k
(31)
where 1 [:] is the indicator function and y is the margin. Vo is the training node set. No VV the number of the training node. Yi is the label corresponding to node i E V.. hx, G) E R K is the
predictor output, where (,(X, [k) refers to the prediction probability of class k on sample E Vo-
The expected margin loss is the expectation of C) (h) on the test node subgroup Vm of the corre- sponding empirical loss 29 (h).
c (h) = Pt..
(h).
(32)
where Pr(y 99: (X,G) is the conditional distribution. g(X, G) NND GN + NND' is the aggregation function, typically, g; G) = (: Ejen() X, as default. Gn is the space for all undirected graphs with nodes.
To bound the generalization gap between the expected margin loss Ca (h) on test subgroup V., and the empirical margin loss 23 on train subgroup Vo. The theorem is shown as follows:
33

---

Theorem 2 (Subgroup Generalization of Deterministic Classifiers [46]). Let h be any classifier in H. For any m S M, for any À > and 7 2 0. for any "prior" distribution P on H. that is independent of the training data on Vo, with probability at least 1 - 8 over the sample of y for any Joy
Q on H such that Pra-Q maaxeeoov... [|,((X, G) h2 G) < 3)) > 2 we have
(h) - (b) + 1
X
2 (QIP()
+ (m.((P:)) 4N
(33)
(a)
The generalization bound is typically related to the following four terms: (a) DRI((Q))P) ==
I In dp is the KL-divergence between the learned (posterior) predictor distribution Q and the predefined (prior) distribution P. independent of the training data. The generalization gap is bounded by the discrepancy between P and Q. It is general term in PAC-Bayes analysis considering as the X²
model complexity measurement. (2) ANa will vanish with larger number of training samples No
Notably, the above two common terms in PAC-Bayes analysis are not our focus. (3) In 1 is the term related with the probability 1 - 8. (4) The expected loss Discrepancy between the training nodes Vo and targeted test node subgroup Vm is essential our analysis, denoted as:
DMd (PP A) In In X
(P;
(34)
where prior distribution P over H. 7 is the correponding loss margin, À 0 is parameter, reflects the concentration of the learning distribution Q. Intuitively speaking, the term D (P:)) A) signifies the difference in expected loss between Vn, and Vo. evaluated in an expectation with respect to the prior distribution P.
The expected loss Discrepancy is typically for the non-i.i.d semi-supervised setting, which trivially comes true in i.i.d. setting. In the i.i.d. case, all samples in Vn, and Vo are i.i.d., where C7/*(h)) (P; A) < To
(h) < /3 S O for any classifier h, leading to a trivial upper bound D7 provide meaningful upper bound, we are required essentially assume there exists the relationship between train node subgroup Vo and test node subgroup Vm. Typically, we expect the expected margin loss 17/+ (h) on Vm is not much larger than ( on Vo when the number of samples
becomes large. Taking a further step, to bound the difference Cyl((h) (h) / (h), (h)² we should find suitable assumptions and derive proof to bound (1) the difference on P(g( X, G)) controlling with
the feature distance between Vn and Vn (2) The differencce on P(Y gg((( G)) controlling with the homophily ratio as shown in Lemma
F.3 Proof details of Expected Loss Discrepancy
To establish the generalization guarantee, becomes necessary to provide an upper bound for the expected loss discrepancy, D',, (P: A), which is the main focus in the proof. It emerges that certain assumptions about the data are required to derive a meaningful and useful upper bound. The assumptions are shown follows. Notably, the assumptions 2 and 3 are adapted from (46). Remark: Notably, the following proof is derived based on [46]. For completeness, we show the previous proof as follows, the difference is that consider more complicated conditional probability ((y: = (X, G)), correlated with the homophily ratio difference, rather than consider the conditional probability as c-Lipschitz continuous functions. In other words, our proof further strengthens the effect of the structure disparity.
Definition (Generalized CSBM-S model), ). Each node subgroup V follows the CSBM distribution Vn (HBM(H1, M2, p'").("""")))))) ()))), where different subgroups share the same class mean but different intra-class and inter-class probabilities ( and q()) Moreover, node subgroups also share the same degree distribution as p()) + q = pld) + q())
Instead of only considering one homophilic and one heterophilic pattern in CSBM-S model, the generalized CSBM-S model allows more diverse structural patterns with different levels of homophily.
Assumption 1 (Data follows Generalized CSBM-S model assumption). The graph data is generated from the Generalized CSBM-S model.
34

---

Assumption 2 (Equal-Sized and Disjoint Near Sets ). For any 0 < m S M. assume the near sets of each i Vo with respect to Vm are disjoint and have the same size 8m E N
Assumption 2 assumes that Vm can be divided into equally sized partitions, each can be identified by the corresponding training samples. assumes that test nodes are closely aligned with the respective training sample, while distant to the other training samples.
Definition 2 (Distance To Training Set and Near Set). For each O < m S M, define the distance from the subgroup Vm to the training set Vo as
== max min 1l, G) - (X, G) JeVm VEVo
Further, for each E Vo, define the near set of with respect to Vn
V((
{j E V.
|1: G) 9j(X, G) S mm)-
Clearly,
Vn = Usevo V m
Assumption (Concentrated Expected Loss Difference). Let P be a distribution on H. defined by sampling the vectorized MLP parameters from (0, o2 I) for some 0² (n/8em) 2b(ANo 2b2) For any L-
layer GNN classifier h E H with model parameters W w....., WT, define Th == max || Assume that there exists some 0 <a0 a satisfying
(1)) - 12 -2600 > No + cKem The em > 2) S se SeN hwP
Pr
Assumption 3 postulates that the expected margin loss on the test node subgroup, V.,. is not sig-
nificantly larger that on the train node subgroup, Vo, as the number of training samples No [Vo
becomes larger. More discussions about this assumption can found Appendix A.5 of 46
Lemma 4 (Bound for DT Di,, (P; (P:)) (Adaption of Lemma 6 in (46)). Under Assumption 7 and 3
for any 0 < m S M, any 0 X S No and 7 2 O, assume the "prior" on H is defined by (7/8rm)
sampling the vectorized MLP parameters from o0, for some o² S 26(AN, 411bb))"
We have
AKp (c+ [ho hml p))
00 (P: (PAA S In
(35)
V
We first present the following Lemma that bounds the difference between the margin loss on Vn and that on Vo-
Lemma 5 (Adaption of Lemma 5 in 46 ). Suppose an L-layer GNN classifier h is associated with
model parameters WI,..., Wi. Define Ty max Willl Under Assumption 7 and 2 for
any 0 & M and 2 0, if cm Th s 7. then
Kp (E tho hmml-
(2) (h)) <
(36)
V2T0"
Proof. For simplicity in this proof, for any i E Vo V U Vm and k -,...., K, we use hy to denote h,(X, G) and use (i( to denote Pr(μ = k G)). And define L (T v.)
[h<[vi] & 7 + maxk4y, he [ Then we can write
62 (h)) (h)
E
Σ
vi)
- Egy
Σ LT vi)
Nm
No
jEVm
iEVo
Eyg..m
Σ
e2 (133(1))))))
L² (bs,
No
8m
VoVo
jEv
35

---

M, any where in the last step we have used Assumption 2 Therefore,
Σ VEV
Byg
(h)
Ry (. (hi,
No
8m
ieVo
K nh (1) (2,,)))))))))))))
K
Σ VEV ==1
Pr(v: = (1,,,
No iEV9
-
(h), (Ta,)
No
8m
iEVo
JEV
K
Σ 8m
Σ
me(i) (12/2(1), x (he,,
+ (mx(()) - (i)) C (b,, (37)
No
iEVo
jEVA
k=1
K
$
Σ VVV
Σ JEV
Σ
(1
(c722(())))) - (h,,, k)) + (nx(i) - (t)) .1).
(38)
No
where the last incquality utilizes the facts that both mh (i) and C (T k) are upper-bounded by 1. According to the lemma we can get:
P -_ (E + lho hmll
(J) (i) S
(39)
V2TO
p M4 Mell ll denotes the original feature separability, independent with structure.
Further, as h; = f (g:( G): WI...., WL) where f is a ReLU-activated MLP, so
|| hilloo S (19i(X, (X, Willa S Tm S ? 4 This implies that, for any = 1,.... K,
/2 k) < L (h,,
Detailed proof can be found in Lemma 5
So we have
C2/ (2/221) - (h)
K
P P_
0
(E + |/10 - -mml p)
No ioVo
V2TTO
jEV
k=1
Kp (e+ 1ho hmll .p) p)
V2na
Then we can prove the Bound for D D7 (P (P;
Lemma 3 (Bound for D DP, X)). Under Assumption 7 and 3 for any 0 <
0 << X 2 and 7 assume the "prior" P H is defined by sampling the vectorized MLP
parameters from (0, o² I) for some o² 17/8em.) 2/L
2b(2N, 2b2)))" We have
AKp
71/2 (P:A) < In3
(c+ + tho - hml p).
(40)
m.0
2na
36

---

Proof. Recall that (T((P En (eal
We prove the upper bound of
DM.0 (P: by decomposing the space H into the two regimes: regime with bounded spectral norms of the model parameters required by Lemma and its complement. Following Lemma [ for any classifier h with parameters W1, WL, define Th == max;=1..... ||ill22
We first prove an upper bound on the probability Pr(TA fm > ()) over the drawing of h ~ P. For any h, as its vectorized MLP parameters (W)) for each 1 = 1..... L, is sampled from (0 I
we have the following spectral norm bound |99. for any >
Pr(I > t) S 26e zhe?
( ạ
1/b
where b is the maximum width of all hidden layers of the MLP. Setting t = a union bound, we have that
and applying
8em
1/L
Pr Pr(Ti'mm cm > )) Pr Tx >
Y
<
2bLe
fr/hem 1222 200
S ANT
88m
where the last inequality utilizes the condition 0² < (x//8em) P/h
26(NN, 26L)
5 we know that > E33 S
For any satisfying em S 3. by Lemma
Ra (mm))o-bmml-))) For all h such that Them > 3. by Assumption with probability at least e evane
1 N86-N
(EH s:aN0"
"
RAe (e+1hh--ie homml-l) Vina
Also note that LTh (h) - (h) <
trivially holds for any h. Therefore we have
Dml
In Empeee (1))
(1) -k))
In Pr The >>
2)
(e-N8- -e + (1 -NN8") ee ANo=
RAo 1270 (c-1ho 1ooo-hh l.p)
+ Pr
The cm S
?
E vino
Nsc (e+ (e+1 Iho -hmm
8
S 3n3 + K\p
(E + |h00
hmal p)
V
Lemma 5. Define LJ y1) = [bx[vvi] S + maxe/y he[k]] if [|,, hyllo S 7, for any
k == 1-1,,,--- K, ( k) < (hi,,, k)
We need to proof from hy[k] 2 + max h210 to halk] S y + max;34 hi[l]
hylk| < 2
+ max h [[]
2
1ikk
h5(k] (ho[k]]
hy]4 < 2
+ max hg [1] (h. [k] hk((k)
2
izk
ha[k| < 2
+ max h + (ha[k) - h2 [k)
lzfk
h4[k] < r
max h1
37

---

Then we need to proof y + max14 h I + maX14e h:[[]
max 1*k
h,10]
max [m( myrk
max
h max h4 [ml]
14t
max 1
[R,[1]] h,,11]]
?
4
The proof complete.
E,4
Proof details of subgroup generalization Bound for GNNs
With the bound for D P
(P: A), we can then derive the subgroup generalization Bound for GNNs. Notably, the following proof is derived based on [46]. For completeness, show the previous proof as follows, the difference is that we consider a more complicated conditional probability (vy: (X, G)), correlated with the homophily ratio difference, rather than consider the conditional probability as c- --pschitt continuous functions. In other words, our proof further strengthens the effect of the structure disparity.
Remark:
Assumption 1 (GNN model). We focus SGC (16] with the following components: (1) one-hop mean aggregation, function g with g(X, G) denoting the output. (2) MLP feature transformation f G); W1, W2, Wt). where f is Rel.U-activated L-layer MLP with "..... WL parameters for each layer. The largest width of all the hidden layers is denoted as
Despite analyzing simple GNN architecture theoretically, similar with 46
our theory
analysis could be easily extended to the higher-order case with empirical success across different GNN architectures shown Section 3.4 Notably, the following assumptions and are adapted from 46
Assumption 2. Define Bm := maxiev,vv. (X, G) For any classifier E H with parameters (Wi)_ assume ||ill for .,..., L. Assume Bmg C are constants with respect No-
Theorem 1 (Subgroup Generalization Bound for GNNs). Let h be any classifier in H with parameters (Wi) for any 0 < m M, 7 2 0, and large enough No, with probability at least 1 - over the sample yf we have
2et
DΣ WiilP
(h) < (2) +
(cm + hoo
hml |p4
P1))
+
(
V2Ta
(1/8)2/L 2 LNB
(41)
LC(22m)
In
No
2a
2a
NZa
11/L8
The proof of Theorem result of the Theorem
relies the combination of Theorem Lemma and intermediate [00] (which we state as Lemma below).
Lemma 6 (100)) Let h be any classifier in H with parameters (Wi) Define B I/L
(ITL [111l2))
Let {Uitee be the random perturbation to be added (Witt and If
vec( (ec((U)))))) ~ ~N(00, o²))) Define Bn max4evovv..
7
o 0 84LBm BL-1 bln(4bL)
and B is any constant satisfying |3 -111 - then with respect to the random draw of (Ui)
Pr max [If( (Witt (X, (0,(()))) G); (W) + UiNE < ? LEV
1
2
Then we prove Theorem re-stata as Theorem with replacing the notation of training node subgroup Viain to Vo.
38

---

Theorem (Subgroup Generalization Bound for GNNs (Adaption of Theorem 3 in 46 Let be any classifier in H with parameters (Wi) Under Assumptions
and 3 for any m M, 0, and large enough No. with probubility at least 1 ô over the sample of y², we have
Kp V2TO
b D Will.
E (b)))+
(em + thy hmml P) + (7/8)2/LNN/ (em) 2/
In
No
No
(42)
Proof. Note that, the following proof is adopted from [46]. There are two main steps in the proof. In the first step, for a given constant 3 >> 0, we first define the "prior" P and the "posterior" Q on H in way complying the conditions in Lemma 4 and Lemma
satisfying | 3 < 1. where _ [II ( I/L 6 Then for all classifiers with parameters
we can derive a generalization bound by applying Theorem 2 and Lemma 4 In the second step, we investigate the number of we need to cover all possible relevant classifier parameters and apply union bound to get the final bound. The second step essentially the same [10) while the first step differs by the need of incorporating Lemma
We first show the first step. Given choice of independent of the training data, let
)
min
26(ANN + 26L) SALBmB3-- /bln(bb)))
Assume the "prior" P on H is defined by sampling the vectorized MLP parameters from (0 o and the "posterior" Q on H. is defined by first sampling a set of random perturbations {Ui]_ with vec({U))f=) ~ ~NO, o² and then adding them to (Wi) the parameters of h. Then for any with (Wi) satisfying | B I. by Lemma 6 we have
Pr h~Q
max G) (,, -,((X,G))(,(xG))) VEVOUV..
< 2 8 >
1
Therefore, by applying Theorem
2 know the bound 33 holds for h, i.c., with probability least
1 6.
c - (h)
2(DKI +1) +1
In
1
+
X²
D2/2
DMB((PN))
4N
2(DKL(Q11P)) + +1)
In
1
+
X²
+
II3+
+
AKP
(cm + 1/a hm .mml... p))
(43)
5
4No
V2To
2
Kp (Em + 1/1 - hmll p),
(Q] +
In
+2
+
+
(44)
Nga
N2
4N-
V
where in 443 we have applied Lemma in (44) we have set N22a.
4 to bound D (P; A) under Assumptions
and
and
Moreover, since both P and Q are normal distributions, we know that
Σl Will 1
DkI((Q)P) S
202
By Assumption 2 both B,, and are constant with respect to Ng. Later we will show that we only need / < C. Therefore, for large enough No. we can have
(n/86m) 1/L
2b(Ng + -In 1bI.)
84LBm 1
which implies,
(7/8em) ) 1/L
/ 2/2(N8 + In 2bL)
39

---

and hence,
(KI( 8(N + In 26L) Σ 1Wil 2
(em)
(45)
(7/8)2/L
Therefore, with probability at least 1 - 5, C (h) - (h)
2 Kp (cm + 1ho hml p) + (QL(Q +
3
In
+ 2
+
2
Nº
4No 1a
Kp (Em + lho - hml
PΣ I
1 8
00
Amllpp. .p)
(7/8)2/L (Em)
(em)2/T.
2/T.
+
+
In
(46)
V2TO
NJ
2a
No
Then we show the second step, i.e., finding out the number of 3 we need cover all possible relevant classifier parameters. Similarly as [100], we will show that we only need to consider
11/2 < 3 < (recall that |[]] S C, I,..., L). For any 3 outside this range, the 28m
bound 47 automatically holds. 1 < (2 (1 then for any node i E Vo. [|,, (T,((,))lll G) 3.
which implies (h) = 1 as the difference between any two output logits for any training node is smaller than y. Also noticing that C (h) < by definition, the bound (47) trivially holds. And for 3 in this range, 3 < 2 1/2 a sufficient condition for ,3 to satisfy / 3 s L. and need most AC(2B,.)' of 8 cover all / in the above range. Taking union bound all 7:/2
such 8, which is equivalent to replace å with 5
LC(38m 177 in (46), it gives us the final result: with 1/6
probability at least 1 1-6, 6,
( Kp
b TΣ
1111 IWIE
c (h) < (T)+ +0
(em + 1ho hmll (
(em) 2
V2To
(7/ 1r/8)2/LN7
(47)
1
LC L2 1/1.
In
N1
111220
N2a
7 1/46
G Experiment details
G.1 Hardware & Software Environment
The experiments are performed on two Linux servers (CPU: Intel(R) Xeon(R) CPU E5-2690 v4 @ 2.60GHz, Operation system: Ubuntu 16.04.6 LTS). For GPU resources, four NVIDIA Tesla V100 cards are utilized The python libraries we use to implement our experiments are Py PoTchh 1.12.1 and PyG 2.0.p.. The maximum time for training one epoch no more than minute.
G.2 Model details & hyperparameter settings & results
In this section, we provide details for baseline methods, hyperparameter search space, and the accuracy results.
Details for baseline methods We provide details for baseline methods in this section. MLP, GCN 12). GAT (U) and SGC [66 are classical baseline models, we directly adopt the implementation of them from Pytorch Geometric, Notice that, SRGNN and EERM are two baseline method specifically for the Graph OOD scenario.
GLNN, as proposed by 29 address the scalability challenges faced by Graph Neural Net- works (GNNs) practical industry deployments due to their data dependency. By leveraging the strengths of both GNNs and MLPs through knowledge distillation (KD), the authors
40

---

demonstrate that MLP performance can be significantly improved. The authors' code can be found at |nttps://github com/ snap-researchi hwtp:/ggaaapaagaaeeeeeee neurall -etworks In this work, we adopt GCN as the teacher model.
APPNP, developed by [15]. leverages the relationship between graph convolutional networks (GCN) and PageRank develop an enhanced propagation scheme based personalized PageRank. APPNP focuses on addressing the limitations of traditional neural message- passing algorithms in graph-based semi-supervised classification, which only considers small, fixed neighborhood of nodes. The author's code is available at hattps://githe com/ conngaasteigggj///ppiin
GPRGNN, introduced by [53], aggregates features across multiple steps and subsequently combines them linearly, with the weights of the linear combination being learned during model training. The original features prior to aggregation also incorporated into the combination. The authors' code is available at htttps///itthu GPRGNN
com/jiannao2011
GCNII, developed by 152] is deep learning method for graph-structured data that extends the traditional GCN model by incorporating two innovative yet straightforward techniques: "Initial residual" and "Identity mapping." These techniques effectively address the over- smoothing issue commonly encountered in shallow GCN models. The author's code is available httpps///github. com/ cwwnnnM/GCCI
SRGNN, introduced by 63 is a novel framework incorporating shift-robust regularizer that encourages the learned representation to enhance the ood generalization capabilities of GNNs and overcome the limitations posed by localized graph training data. The author's code is available at (https: /tthhggtttb..../// com cww/ Shthhh//hhhhtttout--tOttt GNNs
EERM, introduced by 622. proposes a principled methodology identify and quantify these factors in graph data and incorporate a novel invariance-inducing regularization term into the GNN training objective. The author's code available hattp:://gitie giwbgtthhuu.... com/
Bettianuu/GraphooD--- EERM
hyperparameter searching range For model-specific parameters, we use the same notations for the following models considering brevity. Details are shown follows.
A: For GLNN, À refers to the weight of knowledge distillation loss. For GCNII, À refers to the strength of identity mapping.
For APPNP and GPRGNN, refers to the teleport probability. For GCNII, refers to the strength of residual connection.
K: For SGC, APPNP, and GPRGNN, K refers to the number of transformation layers.
In hyperparameter searching, we utilize the common range of hyperparameters for most models. Notice that, there are particular models where the reported optimal parameters in their papers are quite specific. In order to achieve better implementation results, we expand the search range on top of the original reported set for these models.
Table 7: Hyperparameter searching range for baseline models on Cora, CiteSeer, PubMed
viggi Liory
despos (2. DS)
Lakks
Ga leab
OCN
1le2
Sc4,
S00
nx] 85,
11.11
(123))
(1448
GUADN
1163 5- 50
So4, Sod]
23, BR]
[16, 22,023
[1.21
(05-L2)
156TA9U1
MLP
Se2 30-31
Soal, 56-51
(0.05 63)
[in. 11.541
GPRENN
16-2
51
3e-3,
Se4,
P2, B:]
(16. 20,
12:1
S6.5
Reimplementation experimental results We illustrate the experimental results with the above hyperparameter search in Table 10 11 on homophilic and heterophilic datasets, respectively.
G.3 Dataset details
In this paper, we majorly focus on two homophilic datasets, PubMed and Ogbn-Arxiv and two het- crophilic datasets, Squirrel and Chameleon. Moreover, consider more datasets for comprchensive
41

---

Table 8: Hyperparameter searching range for baseline models on Chameleon, Squirrel, Actor, Amazon-ratings
Repepamentrs
wight Menl
Teblee
06N
lied
229
[2544]
20-1
(1222)
2561
DLAM
[M6.
204)
11.70
(30:00)
5-3
(SSTARIN)
[604 3-3
[5 13-5c44 Sec 2ed.26-1
26-1
(0.82
[16.22
22.66
2290
GINE
(665,-03,1663)
08. 13.5--.5-41 56-4
[0.43:00 [a)
( [16.32 254]
(2.4 56.30
[00-100
Table 9: Hyperparameter searching range for baseline models on OGB-Arxiv, Twitch- gamer, IGB-tiny
Reperparantiin Blasline GAN
dirguat
CCN
[ted Sol.
E1 3oS3
Jo. OuS
IES, 156, 3121
GAT
[e-3 Se3 60-11
Se-l 5o-51
26, D.S 0.5
(66, 136, 266, 913)
13 [125, 512)
[1.33)
3o51
[IIGA,218
(50-10)
APPAP
Se3
1e:2.
(30-10)
(567
[1-3 6-7.
00: S-1
OCNE
(5.0093300 204g
(3. 04.00.22000000 04.03.03)
144. 125, 275. 312)
22.4 16 16.22,40 32.64)
(SA-10)
Table 10: The accuracy of GNN and MLP models on homophilic graphs
Dataset
Cora
Citeseer
Pubmed
Arxiv
IGB-tiny
MLP
61.121.2
60.0+1.4
69.0#2.3
54.040.1
73.240.1
GLNN
81.3+1.5
73.0+2.7
78.2+2.6
71.7+0.1
73.2+0.1
GCN
81.5+1.4
73.7+1.6
77.9+2.0
71.4+0.1
70.7=0.1
SGC
81.7+1.4
72.7+2.2
77.0=2.7
68.0+0.1
71.0=0.1
GAT
82.2+1.1
73.6+1.6
77.3+1.5
71.040.1
70.8+0.2
APPNP
83.1+1.3
75.0#1.1
79.6#1.3
70.3+0.5
71.2=0.1
GCNII
82.8+1.1
73.8+1.7
79.0+2.5
71.740.5
73.5+0.1
GPRGNN
82.9+1.4
72.4+188
78.3+2.1
72.3+0.3
73.920.1
Table 11: The accuracy of GNN and MLP models on heterophilic graphs
Dataset
Chameleon
Squirrel
Twitch-gamers
Actor
Amazon-ratings
MLP
49.0+2,4
30.1
60.7#0.2
37.0#0.7
45.9#0.8
GLNN
39.2+2.7
52.3+1.4
61.1+0.1
37.3+1.0
54.0=0.7
GCN
68.0+2.0
54.7#1.4
62.2+0.2
30.7#0.9
49.0#0.6
SGC
69.1#1.8
53.0#1.1
62.0+2.0
30.0+1.5
46,5+0.6
GAT
67.0+1.9
53.2+1.7
59.940.3
30.7+1.0
48.0+0.5
APPNP
56.7+2.5
42,4+1.9
59.720.1
37.0+1.3
44.9+0.8
GCNII
64.7+1.8
44.0=1.5
64.5+0.3
36.0+1.2
50.0+0.5
GPRGNN
68.5+1.4
53,8+1.4
61.940.2
36.5+1.4
49.8+0.5
experimental results including Cora, CiteSeer, IGB-tiny, Actor, Amazon-rating, and Twitch- critch-gamers. Dataset statistics details can be found in Tab. [3 The license of datasets can be found in Table [2]
Table 12: The license of datasets.
Dataset
license
Cora
NLM license
CiteSeer
NLM license
PubMed
NLM license
Ogbn-arxiv
ODC-BY
IGB-tiny
ODC-By-1.0
Chameleon
MIT license
Squirrel
MIT license
Actor
MIT license
Amazon-ratings
MIT license
Twitch-game -eattssggamers
MIT license
We then provide a detailed description on those datasets and the corresponding data split follows:
42

---

Planetoid datasets include Cora, CiteSeer, and PubMed. They consist of scientific publi- cations as nodes. The citation links between the papers create graph structure, with nodes representing papers and edges representing citations. We utilize the 10 fixed splits in [OT]. For each split, we have 20 nodes per class for training, 30 nodes per class for validation, and all other nodes for testing. More details can be found on https://githuu: com GAMPPA-GMMA//AAA CAATTTGAAAA//////EEAAA http://////eeee/a/eerr/eeeeeeeee
Ogbn-Arxiv dataset is based on large-scale scholarly paper citation network, where nodes represent papers and edges represent citation links between them. We utilize the default fix split provided by [24). More details can be found on htttt::/ stanford. edu/ docs/nooeeprop/HHe hhtp://ooonnoooroeeee
Wikipedia datasets include Chameleon and Squirrel, which are a collection of web pages from Wikipedia. The node features correspond to several informative nouns in the respective Wikipedia pages. The edge represents the link between node. We utilize the 10 fixed splits in [25]. For each split, we have 48% nodes for training, 32% nodes for validation, and 20% for test. More details can be found on https ///gi///gttuet github. com/ graphdml coaiodmmmuuuucc. wiuc- jlu/
The Actor dataset [02 is a graph that represents the co-occurrence relationships between actors. We utilize the 10 fixed splits in [25]. For each split, we have 48% nodes for training, 32% nodes for validation, and 20% for test. More details can be found on https //github. com/ graphdmml
jlu/geom-gen
The Switch-gamens dataset represents the relationships between accounts the streaming platform Twitch, where each node corresponds to a Twitch account, and edges are present between accounts that mutual followers. We utilize the 5 fixed splits in (1.. For each split, we have 50% nodes for training, 25% nodes for validation, and 25% for test. More details can be found on https::////// thub. www /ww.//CAA/////// MMtiAAN/ooo-eee http:ooooooooopplllaar-r---eeeee
Amazon-ratings new dataset derived from the Amazon product co-purchasing network metadata dataset, which is part of the SNAP Datasets [103] We utilize the 10 fixed splits in [104). For each split, have 50% nodes for training, 25% nodes for validation, and 25% for test. More details can be found on https: thub wtt./oo////m// yandex- come heterophilous-gragee ggraphs/tree/mainnn data
IGB-tiny is recent new citation graph dataset. It utilizes two publicly available datasets: Microsoft Academic Graph (MAG) and SemanticScholar Corpus. We utilize the homo- geneous setting with default fix split provide by [105]. More details can be found on https:// wwt.cooommci...ie...e
Sawaaaarkii-----ttettteee Datassets
Details on Data distribution The node homophily ratio distribution for different datasets are presented in Figure 13 The following observations can be made: (1) Cora, CiteSeer, PubMed, and Ogbn-Arxiv are four homophilic datasets where most nodes have a homophily ratio h > 0.5. (2) Chamaleon, Squirrel, and Actor three heterophilic datasets where most nodes have homophily ratio h < O.5. Nonetheless, the Actor dataset exhibits entirely different properties from Chamaleon and Squirrel where graph structure information is barely useful, leading to performance degradation. Empirical evidence can be found in Table TT where the vanilla MLP outperforms all the GNN models. (3) IGB (105) and Twitch-gamers (2 are two representative datasets with apparent majority structural pattern, exhibiting graph homophily ratios of 0.567 and 0.556, respectively. Specifically, IGB-tiny contains both large numbers of homophilic and heterophilic nodes, respectively, whereas, most nodes in the Twitch-gamers dataset do not show a clear homophilic nor heterophilic pattern with homophily ratio close 0.5. Notably, the IGB-tiny is still recognized
homophilic graph 1005 while Twitch-gamers is generally recognized as a homophilic graph [20 21). (4) Nodes in Amazon- ratings [104] exhibit diverse structural patterns with multiple peaks observed for homophily ratios 0.0. 0.2, 0.4, 0.6, and 0.8.
G.4 OOD dataset statistics and details
We provide more analysis and statistics details about datasets with our proposed out-of- distribution (OOD) data split for a more comprehensive analysis. The data split statistics can be found Table [4] 20% of the majority nodes are selected as the validation set. Notably, we generally use nodes with h, 0.5 and h; > 0.5 the majority and minority on heterophilic graph.
43

---

Table 13: Detailed dataset statistics
Dataset
Cora
CiteSeer
PubMcd
Arxiv
IGB-tiny
Squirrel
Chaneloon
Amazon-ratings
Actor
Twitch-gamers
Homo Ratio
0.814
0.714
0.792
0.631
0,567
0.216
0.247
0.376
0.221
0.556
Nodes
2110
19717
169343
100000
2277
24492
7600
249992
Edges
5009
3668
44324
583121
223538
198493
31421
93050
15009
93050
Features
2235
Classes
6
3
40
19
5
5
5
5
Densily
Density
Density
0.0
Anode
Andde
Andde
(a) Cora (/=0.81)
(b) CiteSeer (/=0.71)
(c) PubMed (/=0.79)
Densily
Density
0.0
Anode
Andde
(d) Ogbn-Arxiv (h=0.63)
(c) IGB -iny (h=0,57)
Density
Density
Density
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.4
0.6
0.8
1.0
Anode
Anode
Nnode
Chameleon (f=0.25)
(g) Squirrel (h=0.22)
(h) Actor (h=0.22)
Densily
Density
0.0
0.2
0.4
0.6
0.8
1.0
0.0
0.2
0.6
1.0
Anode
Anode
(i) Twitch-gamers gamers (/c00.56)
Amazon-ratinge (/=0.38)
Figure 13: Node homophily ratio distributions of different datasets. Both homophilic and heterophilic nodes exist across all graphs
44

---

Table 14: the numbers of train, validation, test nodes on OOD data split
Dataset
Cora
CiteSeer
PubMed
Arxiv
Squirrel
Chameleon
#train 1599
1160
12466
85788
3709
1642
#valid
400
290
3117
21447
928
441
#test 486
660
4134
62108
564
564
Nonetheless, the Squirrel dataset only has 71 nodes with h; > 0.5. To ensure enough test nodes, we adapt the nodes with h; > 0.4 as the minority nodes for test. We conduct experiments measure the distributional shift between train and test nodes. To further analysis on the distribution shift, we employ Maximum Mean Discrepancy (MMD) [166] discrepancy metric. A large MMD dis- tance indicates the covariate shift with pemin + ples (X). MMD measures the distance between distributions follows:
1 Σ 6 (2,)
1
MMD XX," =
(U5)
(48)
where & a kernel function that maps the input samples into a higher-dimensionnll feature space, and Il ||2 denotes the L2 norm. Using the Gaussian kernel, we can define the kernel matrices as:
Kaz,i k (1)) K 14,65 k (xi, Wj).
K Kyn.i (yrs Mj
(49)
K Kyn.ij = ls (yi, 1rj
where the kernel function is given by:
|| 8113
k(x, v) exp
(50)
2
and a is parameter that controls the width of the kernel. In our experiment, we choose multiple o including [0.01, 0.1, 1, 10, 100]. We average the MMD distance with different a for more robust distance measurement. The MMD distance can be computed using these kernel matrices:
MMD*(X,,)= n(n 1) ΣKan,s
Kan,ij
2 THT
Kaysi m(m 1)
Σ K Kyu.ij
(51)
where the first and third terms represent the within-set variations, and the second term represents the between-set variations. We then conduct experiments to determine where the source distribution discrepancy from the covariate shift concept shift. We measure the MMD distance between the train set and validation set as the i.i.d. distribution distance, and the MMD distance between the training set and test set the OOD distribution distance. However, the in-distribution and out-distribution distances may not be directly comparable due to potential estimation errors introduced by different numbers of nodes in valid and test sets.
To enable fair comparison, we also measure in-distribution and out-distribution distances on i.i.d. data split control group. The MMD distances are measured on the last hidden representation of well-trained GCN. The experiment results are provided in Table [5] Focusing on the i.dd setting, we observe an MMD distance difference the validation set and test set to the training set, induced by the difference in node counts between the validation and test set. Comparing the OOD setting with the i.i.d one significant MMD differences are found, except for PubMed. This suggests that the primary factor driving the distribution shift is not the covariate shift with ( 7 prest (X). but the concept shift with pimin (Y X) * piest (Y X). The above observations further indicate the existence the concept shift in our proposed OOD scenario.
Additional OOD results: We show additional experimental results on Cora and CiteSeer datasets in Table 16 with a consistent observation. Notice that, all experimental results are average with 10 random seeds including (1, 3, 7, 11, 13, 17, 19, 29).
45

---

Table 15: MMD distance between train and validation, test sets on both i..d. and ood settings.
Dataset
Cora
CiteSeer
PubMed
Arxiv
Chameleon
Squirrel
III valid
0.565
0.345
0.082
0.149
0.951
1.04
IID test 0.610
0.600)
0.050
0.276
0.882
0.92
OOD valid
0.564
0.233
0.127
0.211
0.977
1.192
OOD test
0.597
0.598
0.442
0.420
0.854
0.92
Table 16: Additional performance with OOD data split on Cora and CiteSeer.
Dataset
Cora
CiteSeer
GCN (i.i.))
07.53+0.35
77.30#1.22
GCN
51.05+0.58
43.74=0.88
MLP
51.09+0.74
45.26+0.62
GLNN
54.14+0.89
47.21=0.33
GCNII
55.33+0.41
46.47=0.59
GPRGNN
55.16+0.51
45.76+0.50
SRGNN
62.79+0.87
49 49.62+0.96
EERM
54.34+0.78
47.72+0.50
EERM(II)
1..9
51.12 + 0.82
MLP
MLP
GLAN
Difference in acc
model GCN
Difference in aoc
model- -CN
Difference in apc
model GCN
0.125
0.05
0.0
0.075
0.00
-0.1
0.025
0.000
.0.005
-0.5
-0.030
0.442
02404
0440.
0.0.8
08-10
0.0.0.2
2-0.4
040.6
$0.00
0.8-1
0.002
0244
0..006
0.801.
a
Homophily Ratio Range
Homophily Ratio Range
Homophily Ratio Range
Cora 01=))
(b) CiteSeer (l=0.71)
(c) IGB-tiny (1=0.58)
MLP
GLAN
MLP
GLAN
Difference in aoc model CCN
Difference in acc model- -CN
Difference in acc GCN
0.75
80se
0.05-
0025
0.0
-0075
-0.
-01
0.0.0.2
0.3-.
0.46
0.6.0.8
0.....
0.0022
0.204
0.4.0.6
0.60..
0.80
0.00.22
0.2.04
0.400
060.8
0.8.1.0
Homophily Ratio Range
Homophily Ratio Range
Homophily Ratio Range
(d) Actor (/=0.222)
(e) twitch-gamers (/=0.56)
(f) Amazon-ratings (/=0.38)
Figure 14: Performance comparison between GCN and MLP-based models more datasets. Each bar represents the accuracy gap on a specific test node subgroup exhibiting a local homophily ratio within the range specified on the x-axis.
H Additional results on performance comparison between GCN and MLP-based models
conduct performance comparison between GCN with two MLP-based models, i.e., MLP and GLNN, on test nodes with different structural patterns. this section, we provide more elaboration why using GLNN and conduct additional experiments
In Section 3
datasets.
We first provide more elaborations on why using GINNN. The experiment is to examine the effec- tiveness of GCN utilizing different structural patterns. Therefore, compare GCN and MLP
46

---

architectures as GCN utilizes graph structure during inference while MLP cannot, serving as structure-age -ggnosi baseline. When GCN surpasses MLPit indicates GNN benefits from structural patterns effectively, and vice visa. Notably, GINN can be viewed as better-trained MLP model. GLNN also utilizes the same MLP model architecture as vanilla MIP,, the only difference between vanilla MLP and GLNN is that GLNN is trained in an advanced distillation manner while vanilla MLP is trained with cross-entropy loss The reason why we utilize GLNN rather than only comparing GCN with vanilla MLP is that MLP meets optimization issue training. Such an obstacle leads to large performance gap (more than 20%) between under-trained vanilla MLP and well-trained GCN, Consequently, large performance gap induced by training difficulty hinders the potential for MLP architecture. Contrastly, GLNN enjoys a better training process leads to a more clear comparison between well-trained GNN and well-trained MLP(GLNN) architecture with convincing conclusion
Additional experiments are illustrated in Fig 14 Cora and CiteSeer are two Planetoid datasets, showing similar properties as PubMed. Observations on Cora and CiteSeer are consistent with those in Section further substantiating our conclusions. should be noted that our paper primarily focuses on homophilic graphs and heterophilic graphs with clear major structural pattern. Nonetheless, there exists more complicated real-world graphs with more diverse structural properties, as demonstrated in Figure 13 We conduct further investigations on these datasets, including IGB-tiny, Twitch- gamers, Amazon-rating and Actor. A comprehensive discussion on those datasets can be found in Appendix G.3 Experimental results are depicted in Figure [4] We make initial observations as follows: (1) IGB-tiny is a homophilic dataset exhibiting consistent observations in line with the main analysis in Section B] where the MLP-bbasd models outperform GCN on the heterophilic nodes and underperform on homophilic nodes. (2) Twitch-gamers and Amazon-rating are two heterophilic datasets exhibiting consistent observations in line with the main analysis in Section 3 where the MI.P-based models outperform GCN on the homophilic nodes while falling short on the heterophily nodes. (3) Actor is a heterophilic dataset where graph information is of limited utility. Empirical evidence shows that MLP-based models show an overall better performance than GCN. From local perspective, the MLP-based models outperform GCN on the heterophilic nodes while underperforming on the homophily nodes. Those observations indicate our conclusion can be extended on most datasets with diverse structural patterns Nonetheless, still remains mystery on the Actor dataset. We leave a more comprehensive investigation especially on the Actor dataset as the future work.
I Additional results on performance comparison between GCN and deeper GNN models
In Section 4.1 we conduct performance comparison between GCN with deeper GNN models, on test nodes with different structural patterns. In this section, we conduct additional experiments on more datasets, correspondingly. Cora and CiteSeer are two Planetoid datasets, showing similar properties as PubMed. Notably, deeper GNNs generally show better performance across different structural patterns, where the improvement still primarily lies in the minority groups, Observations on Cora and CiteSeer are consistent with those in Section 3 further substantiating our conclusions.
It should be noted that our paper primarily focuses on homophilic graphs and heterophilic graphs with a clear major structural pattern. Nonetheless, there exist more complicated real-world graphs with more diverse structural properties, as demonstrated in Figure 13 We conduct further investigations
on these datasets, including IGB-tiny, Twitch-gamers, discussion on those datasets can be found in Appendix G.3 New experimental results are depicted in Figure [3] We observe that deeper GNNs generally outperform GCN on the heterophilic node while underperforming on the homophilic nodes those datasets with diverse structural properties. We can conclude that the effectiveness of GNN on those datasets with no clear majority structural patterns primarily from the improvement from the heterophilic nodes. We leave a more comprehensive investigation as the future work.
Amazon-ratings and Actor. A comprehensive
J Additional Experiment on performance disparity across subgroups
In Section 3.4
we conduct experiments to empirically examine the effects of two-hop aggregated- feature distance and the homophily ratio difference on the test performance of different GNN models. Despite the empirical success the second hop, we conduct additional experiment results focusing
47

---

OCNB
APTINP
OCNNL
AFFIN
FXNI
GPRONN
APPNP
0.10
0.06
Difference model .GCN
Difference in acc
model CCN
Difference in are
GCN
0.10
0.00
0.00
0.02
-0.02
0.00
-0.0
-0.02
0.0.2.2
0204
04:0
0.40
0.0.0.2
0.204
0.40,00
0.000
0.8
000.2
02.04
0400
06000.
Homophily Ratio Range
Homophily Ratio Range
ophily Rabo Range
(a) Cora (1=).81)
(b) CiteSeer (h=0.71)
(c) IGB-tiny (h=0.57)
GUACNN
APPNP
G2MZ
GPRONN
ATPNP
0.05
0.10
model- GCN
Difference in ace
model- GON
0.1
0.0
Difference
0.00
Differunce
model
0.00
-0.1
0.05
00.05
0.2
-0.15
000.2
0244
06a8
83..0
0003
02484
0440
06:8
08100
-0.3.
0.00.2
0.3414
0440.6
0660888
0.8-1.
Homophily Ratio Range
Homophily Ratio Range
Homophily Ratio Range
(d) Actor (/=0.222)
(e) twitch-gamers (/=0.566
(f) Amazon-ratings (/=0.38)
Figure 15: Performance comparison between GCN and deeper GNN models more datasets. Each bar represents the accuracy gap on a specific test node subgroup exhibiting a local homophily ratio within the range specified on the x-axis.
observations higher-order homophily ratios, higher-order aggregated feature distance, and more datasets this section. Notably, despite more complicated datasets, our thcoretical analysis can still achieve empirical success.
0.
08
C.F.
00K
1230
23387
1244
GCN 100 GAT
63 522
Sotichick
1311
1200
22
(a) PubMed
(b) Ogbn-arxiv
(c) Chameleon
(d) Squirrel
Figure Test accuracy disparity across node subgroups by aggregated-feamur distance and higher- order homophily ratio differences to training nodes. Each figure corresponds to dataset, and each bar cluster corresponds to a GNN model. Bars labeled to represent subgroups with increasing differences to training set.
06
68
0.-
PubMed
(b) Ogbn-arxiv
Chameleon
(d) Squirrel
Test accuracy disparity across node subgroups by higher-order eagregated-feature distance and homophily ratio differences to training nodes. Each figure corresponds to a dataset, and each bar cluster corresponds to GNN model. Bars labeled to 5 represent subgroups with increasing difference to training set.
Figure 17:
48

---

904
0.2
00
0.0
60
50c Ge
GCN 500 GAT 60h001900
300
GA
(a) PubMed
(b) Ogbn- arxiv
(c) Chameleon
(d) Squirrel
Figure 18: Test accuracy disparity across node subgroups by higher-order aggregated feature distance and higher-order homophily ratio differences to training nodes. Each figure corresponds to a dataset, and each bar cluster corresponds a GNN model. Bars labeled to represent subgroups with increasing difference to training set.
J.1 Additional investigation on higher-order neighhorhood
Our theory in Section 3.3 focuses on the one-hop aggregation while it could be easily extended the higher-order aggregation case in the real-world scenario. More experiments revolving on higher-order homophily ratio and aggregated features are shown this subsection. In particular, the k-hop node homophily ratio be calculated as:
(R) = (uu E Nk((s)) : yu = yoHl [Wa(1:)]
(52)
where (1s) denotes the k-hop neighbor node set of et. We then sort test nodes in terms of the disparity score and split them into 5 equal-size. Figures [6] and 17 illustrate results on higher- order (third hop) homophily ratio difference and higher-order aggregated feature distance (third hop), respectively while Figure [88 illustratee on the result on higher-order homophily ratio difference and higher-order aggregated feature distance.
similar phenomenon can be found with the expected trend of test accuracy in terms of increasing differences on the aggregated feature distance and homophily ratio differences in different scenarios. Exceptional observation can be found in the following scenarios: (1) Squirrel dataset with higher- order aggregated feature. It may be because such higher-order feature aggregation leads more distribution overlapping between different categories. (2) PubMed with both higher-order aggregated features and homophily ratio. The potential reason is that the PubMed dataset does not rely higher-order information. Overall speaking, those results further indicate that for the generalization of our theory in the real-world scenario.
J.2 Additional results more datasets
In this subsection, we conduct more experimental results on the datasets with more complicated with more diverse structural patterns, including Cora, CiteSeer, (GB-tiny, Twitch-gamers, Amazon- ratings, and Actor. A comprchensive discussion can be found in Appendix G.3 The performance on different node subgroups is presented in Figure 19 A consistent observation can be found with the expected test accuracy degradation trend in terms of larger feature distance and homophily ratio. the difference in most datasets, except for the Actor. The potential reason is that its structure could hardly provide useful information. The key evidence is that the vanilla MLP model outperforms all the GNN models shown in Table []] The actor dataset shows entirely different properties with other datasets. Furthermore, we investigate on the individual effect of aggregated feature distance and homophily ratio difference in Figure 20 and 21] respectively. An overall trend of performance decline with increasing disparity score is evident though some exceptions are present. When only considering the aggregated feature distance to training nodes, the accuracy in Twitch-gamers exhibits an opposite increasing tendency along with the increasing difference to train nodes, Notably, when considering only the homophily ratio difference, the decreasing tendency clear across datasets exception Actor. We can observe even better phenomenon on the Amazon-rating dataset than combining both homophily ratio difference and the aggregated feature distance. It indicates that the homophily ratio difference w.r.t structural disparity significantly contributes to those datasets with more diverse structural patterns. We make the above initial observations showing the practicability of our theoretical analysis more datasets with more diverse structural patterns. Moreover, exception can still be found on the Actor dataset. We leave a more comprehensive discussion on the Actor, as the future work.
49

---

0.8
0.8
0.6
0 0.6
0.6
0.4
20.4
0.4
0.2
0.2
0.0
1256
12545
12315
14845
0.0
12385
14385
14545
1234g
0.0
12345
12345
1235
12545
12.355
(a) Cora 01=0.81)
(b) CiteSeer (/=00.11)
(c) IGB IGB-Tiny (4=0.57)
0.4
0.6
0.6
ACC
0.4
0.2
0.2
0.2
0.0
234
1230
1231
1234.
0.0
120
2245
2221
0.0
1234
12149
1221:
50C
GPRGNN
500
OPRENN
(d) Actor (l=0.222
(e) Twitch- gannersgggersss.mmoee (/=0.56)
(I) Amazon-ratings (h=0.38)
Figure 19: Test accuracy disparity across node subgroups by aggregated-feature distance and homophily ratio differences to training nodes on more datasets. Each figure corresponds to a dataset, and each bar cluster corresponds to a GNN model. Bars labeled 1 to 5 represent subgroups with increasing difference training set. clear performance decrease tendency can be found from subgroups to 5 with increasing differences to the training set except the Actor dataset.
0.8
g
4,0.4
0.4
0.4
0.2
0.2
0.2
0.0
12345
12343 GUMI GPRENN
12335
n.o
12345
12MY 12315
0.0
12363 12345
GCN
S0C
GKT
OEN
S0C
GAT
GONI GPRGNN
OCN
966
GAT
GUNI GPRENN
(a) Cora
(b) CiteSeer
(c) IGB-Tiny
0.4
0.6
0.6
ACO
0.4
0.4
0.2
0.2
0.0
1224
1234
12345
1234
12345
0.0
2244
12345
1240
12313
1234
0.0
12315
1234
12385
1238
(d) Actor
(c) Twitch-gamers
(f) Amazon-
Figure 20: Test accuracy disparity across node subgroups by aggregated-feature distance training nodes on more datasets. Each figure corresponds to dataset, and each bar cluster corresponds to GNN model. Bars labeled to 5 represent subgroups with increasing differences to the training set.
K
Additional investigation on the discriminative ability of GCN
we examine discriminative ratios on input features and multiple hops aggregated features for homophilic and heterophilic test nodes, respectively. Nonetheless, those experiments only focus on feature aggregation while ignoring the feature transformation and the training procedure. In this section, we further explore the discriminative ratios well-trained GCNs with both feature aggregation and transformation. Typically, we utilize the hidden representation trained with the best hyperparameter as shown in Appendix G Experimental results can be found in Figure 22 Observations on GCN are consistent with those in Section 3.2 focusing on aggregation, where majority nodes generally show a larger discriminative improvement than the minority nodes along with more aggregation layers, indicating a better discriminative ability on majority nodes than the minority ones. Those observations further substantiate conclusions in more general setting,
In Section 3.2
50

---

0.8
0.6
0.6
0.4
0.4
0.2
0.2
0.0
220
123
125
1233 1234;
0.0
234
1234
1231a 1233g
0.0
1230
1234
122
124
(a) Cora
(b) CiteSeer
(c) IGB-Tiny
0.4
0.6
0.6
ACC
0.4
0.4
0.2
0.2
0.0
0.0
0.0
GCN
GAT
GONE GERONN
GEN
900
GAT
OCNT GPRGNN
02N
500
GENH OPRGNN
(d)
Actor
(c) Twitch-gamers
(f) Amazon-ratings
Figure 21: Test accuracy disparity across node subgroups by homophily ratio differences to training nodes on more datasets. Each figure corresponds dataset, and each bar cluster corresponds to GNN model. Bars labeled to 5 represent subgroups with increasing differences to the training set.
PubMed Arxiv
Chamelcon
Squirrel
2.5
2.0
1.5
Ratio
1.0
0.5
0.0
#aggregation
Figure 22: Illustration of the change on relative discriminative ratio along with the aggregation. The x-axis represents the number of aggregations and the y-axis represents the relative discriminative ratio.
L Significant test between GCN and MLP-based models
We conduct the performance comparison between GCN with MI.--ased models, on test nodes with different homophily ratios, as shown in Fig the corresponding, we include the p-values of paired t-test and confidence intervals between GCN and MLP-base models in Table 23 to determine whether the performance difference is statistically significant. The z-axis corresponds to the node homophily ratio range. The y-axis corresponds to p-values of whether the performance of GCN significantly better or worse than the corresponding MLP model. Typically, p < 0.05 indicates statistical significance.
M Significant test between GCN and deeper GNN models
We conduct the performance comparison between GCN with deeper GNNs, on test nodes with different homophily ratios, as shown in Fig g the corresponding, we include the p-values of
paired t-test and confidence intervals between GCN and deeper GNN models in Table to determine
51

---

MLP
0.24
c.n
9.14
MLP
0.14
-0.6
40.6
006
GLNN
0.4
GLNN
0.4
GUNN
0.4
0.0-0.2
0.2404
6
0.6-0.8
0.3-1.0
0.0-022
0.2-0.4
0.40.6
0.6-0.8
0.8-1.0
0.0-0.2
0.2-0.4
0440 n
0.6-0.8
0.81.0
(a) Cora
(b) CiteSeer
(c) PubMed
1.0
MLP
0.03
0.0
GLXN MLP
0.83
0.01
0.86
0.8
M.P
0.67
0.19
0.8
GLNN
GLNN
0.01
0.5
0.2
0.08
0.01
0.24
0.04
0.26
0.0-0.2
0.2-0.4
0440.6
0.640.8
0.8-1.0 .0
8.0
0.0-0.2
0.2-0.
0.4-0.6
0.640.8
0.0
0.0-0.
0.2-0.4
0.4-0.6
0.6-0.8
0.0
0.8.1
0,8-1
(d) Chameleon
(e) Squirel
Actor
-1.0
11.0
6.8
MLP
0.8
GENN
0.4
GLNN
0.83
0.2
42
0.0-0.2
0.2.0.4
0.4.0.6
0.640.8
0.8-1.0
0.0
0.0.0.2
0,2-0.4
0.4.0.6
6.0.8
0.8-1.0
0.0
gg)
Twitch-gamer gamers
(h) Amazon-ratings
Figure p-value of the paired t-test between GCN and MLP--aaed models with respect to accuracy on nodes with different homophily ratios.
whether the performance difference is statistically significant. The z-axis corresponds to the node homophily ratio range. The y-axis corresponds to p-values whether the performance GCN significantly better worse than the corresponding deeper model. Typically, 0.05 indicates statistical significance.
N
Limitation
It is important to acknowledge certain limitations in our work despite our research providing valuable insights into the effectiveness of GNN on structural disparity. In order to facilitate more feasible theoretical analysis, we have made several assumptions, the most significant of which is the use of the generalized CSBM-S model assumption in our theoretical analysis. This CSBM assumption, although prevalent in graph analysis, is subject to a notable drawback as the CSBM assumption postulates that feature dimensions are independent and identically distributed. restricts the generality of our analysis.
Our current findings lay strong foundation for further exploration. worth mentioning that our theoretical analysis predominantly focuses on simple aggregation techniques. We hope that these efforts will contribute significantly to the Graph Neural Network research community. Moving forward, we aspire to broaden our findings to encompass more advanced message-passing passing neural networks, with particular emphasis on deeper GNN models. Currently, there only empirical evidence showing the effectiveness of the deeper GNN models. Besides, the node homophily ratio is calculated on the undirected graph while the one on the directed graph still under exploration. More comprehensive analyses on the higher-order aggregated feature and higher-order homophily ratio are still under-explored. Moreover, We aim to utilize our understanding to mitigate the performance difference induced by the structural disparity in the future.
52

---

1.0
APPNP GPRONN GONT
APPNE GPRONN CCNIT
APPNE GPRONN GCNI
0.04
0.01
0.81
0.61
0.46
4.66
-0.6
0.43
0.85
0.03
0.97
0.11
0.08
0.03
0.04
0.53
0.19
0.35
6.4
-04
4044
0.18
0.53
0.02
0.03
0.1
8.2
0.11
0.87
0.01
0.03
0.01
0,3
02
0,0-0.2
0.2-1.4
0-4-0.6
0.6-1.8
0.8-1
0.0
0.0.0.2
0.240.4
0.4-0.8
06488
0.8-1.
0.040
0.240.4
0.4.0
0.6.0.8
0,8-1 0
(a) Cora
(b) CiteSeer
(c) PubMed
1.0
1.0
1.0
APPNP GPRGNN GONT
APPNT GPRGNN GONTI
APPNF GPRONN GONT
0.47
0.1
4.8
0.8
0.8
0.0-0.2
0.2-0.4
0
0.6-0.8 8
0.8-1 o
0.0-0.2
0.2-04
0 d
0.6-0.8
0.3-1.0 0
a.0-0.2
0.2-04
0.4-0.6
0.6-0.8 8
0:8-1.0
Chameleon
(e) Squirrel
( Actor
APPNT GPRONN GCNI
APPNP GPRONN GONI
0.54
-0.6
0.26
0.46
0.09
0.56
0.87
0.02
-0.4
04
8.17
0.2
02
0.0-0.2
0.2-0.4
0.4-0.6
0.6-0.8
0.8-1
0.0-0.2
0:2-0.4
0-4-0.6
0.6-0.8
0.8-1.0
0.0
Twitch-gamen gamers
(h) Amazon-ratings
Figure 24: value of the paired t-test between GCN and deep GNN models with respect to accuracy on nodes with different homophily ratios.
Broader Impact
Graph Neural Networks (GNNs) have emerged as powerful architecture for modeling graph- structured data across a wide range of practical applications 5
73 107]. key aspect of 6
GNNs is the inductive bias on leveraging neighborhood information. However, such characteristics may lead to a biased test prediction, particularly when majority neighborhood patterns are prevalent. For example, a scenario in which we required predict the gender of individuals with dating network. GNN may excessively rely on the pattern that when all neighboring nodes are female, the center node should be male. This approach disregards the minority group of individuals who are more likely to date others of the same gender. This overlooked trawback in GNN may lead to ethical concerns.
In this study, we reveal the potential for performance disparity inherent in Graph Neural Networks and propose a novel OOD scenario for exploring methods to mitigate such issues. It is important to emphasize that our research offers an understanding of these limitations rather than introducing new methodology approach. We only identify the problem and show the potential solution to
53

---

address this issue. Consequentl,, we do not foresee any negative broader impacts stemming from our findings. We expect our work to contribute significantly to the ongoing research efforts aimed at enhancing the versatility and fairness of GNN models when applied to diverse data settings.
Our findings can also help to boost different graph domains. In section 4 understanding can help to elucidate the effectiveness of deeper GNN, reveal an overlooked OOD factor, and propose new Graph out-of-distribtiion scenario. is worth noting that our findings can derive new understandings of more graph applications and inspire us to identify new problems in graph domains. We further illustrate more understanding on the robustness of GNN and more initial understanding on Graph out- oit-of-dee distribbttttnn problem as follows.
we show how our
Graph Robustness. Recent studies have exposed the susceptibility of GNNs to graph adversarial attacks [12) where small perturbations can mislead GNNs into making incorrect predictions.
several literature [133 reveals that increasing the heterophily of the homophily graph could be
key factor contributing to a successful attack. More recently. [16] observes that (1) learning- basee attacks M14 tend to increase the heterophily in the smaller of train and test sets. (2) Directed attacks
on particular nodes can outperform the undirected attack on the whole graph. Those observations
are aligned with the understanding in our paper that (1) Increasing the heterophily of the homophilic
graph enlarges the homophily ratio difference, leading to performance degradation. (2) Perturbations lying in the smaller set can efficiently enlarge the homophily ratio difference between training and test nodes with minimal perturbation budgets. (3) Undirected attack on the whole graph may not lead larger homophily ratio difference between the train and test nodes with permutation on both train and test nodes, leading to performance degradation.
Understanding on Graph -uttof-disttibution problem. Despite the new proposed Graph Out- Of-Distribution (OOD) scenario, our findings can further inspire a new understanding of existing graph OOD problems. We provide an initial discussion follows. The uniqueness challenge of the OOD problem in the graph domain is that the discrepancy in graph structure can also lead to test performance degradation, in addition to node feature differences. There exists various graph OOD scenarios (2tuarioss62266 64
[4]24]] 24] 66 46), e.g., graph density, biased training labels, time shift, and popularity shift. Nonetheless, despite various graph OOD scenarios with different qualitative concepts, it still lacks of quantitative graph metrics to measure how the distribution shift happens, causing performance degradation. Inspired by our finding, We can roughly recognize the main reasons as graph covariate shift and concept shift (68-70 117 in graph context: (1) Graph covariate shift [118] is defined as ptriin (X) * pist (X) where ptrain (-) and piest)) are training and test distribution, respectively. Such graph covariate shift corresponds to the large feature distance |[f,, f.lll between train and test nodes. (2) Graph concept shift is defined as pirim (Y + piest ( [X)). Such graph concept shift corresponds to the homophily ratio difference 1h,,. h.l between train and test nodes. We leave more detailed discussion and careful design on the graph OOD quantative metries as a further work.
P Future work
Further investigation on Deeper GNN In section 4 we conduct experiments on the effectiveness of deeper GNNs, indicating the performance gain is majorly from the improved discriminative ability on nodes in minor patterns. It could be a good direction to further explain and understand why such phenomenon happens. A potential reference for conducting discriminative analysis of deeper GNN is (3). aims to theoretically quantify the discriminative ability on deeper GNNs with more aggregations. Nonetheless, their analysis uses the vanilla CSBM model as the data assumption, denoted as CSBM(H4, μ22 P. 9). The CSBM model presumes that all nodes follow either homophilic with p q heterophilic patterns with p < 9 exclusively. However, this assumption conflicts with real-world scenarios as homophilic and heterophilic patterns coexist across different graphs, as shown in Figure 2. As far as we can see, conducting a similar discriminative analysis as [1] our proposed CSBM-M model considering both homophily and heterophily patterns could be good solution.
Other factors on performance disparity Existing literature 63
shows that some other 86
structural information, e.g., degree, geodesic distance to the training node, and Personal Pagerank score, could lead to a performance disparity. Nonetheless, all those analyses and conclusions are conducted on homophilic graphs, e.g., PubMed and ogbn-arxiv, while ignoring the heterophilic graphs e.g., Chameleon and Squirrel, which also broadly exist in the graph domain. It could be good new research direction to see how the above factors, focus on the homophilic pattern in the context
54

---

of both homophilic and heterophilic properties. Another one could be how to find other important factors both homophilic and heterophilic graphs.
Solutions on performance disparity In this paper, we propose and analyze the importance of the performance disparity problem without no explicit solution. We provide two potential solution as follows:
Combining MLP and GNN an adaptive approach since MLPs can achieve better perfor- mance minority nodes and GNNs better majority nodes. Ideally, can adaptively se- lect MLP for minority nodes and GNN for majority nodes, using an adaptively gated function to control the proportion of MLP and GNN. Our findings suggest the homophilic/heteroohiiii pattern selection can serve as a guide for learning the gate function.
Utilizing global structural information, as the global pattern is more robust, showing less disparity than the local structural pattern. Empirical evidence can be found in Figure 9 that the higher-order homophily ratio differences are smaller than the local structure disparity.
55


Reviews:
[{"review_id": "J6bNhjMVdk", "reviewer": "Reviewer_pgwY", "summary": "This work tries to understand the effectiveness of GNNs w.r.t different structural disparities within a graph. Previous studies have focussed on GNN's effectiveness on overall graphs, but here the authors try to understand GNN's effectiveness w.r.t structural patterns such as homophilic and heterophilic nodes to provide deeper insight into GNN's performance. \n\nContributions include understanding why the performance of GNNs is rather good on homophilic nodes in homophilic graphs and heterophilic nodes in heterophilic graphs, but not on the opposite set. Specifically, how aggregated feature distances and homophily ratio differences in mixed graphs impact the GNN performance. Authors also present experimental results on how deeper GNNs perform better on minority node subgroups while also proposing a new data split strategy to where majority nodes are selected for train/validation and minority nodes for test.", "questions": "1. Is there a way to prove deeper GNNs improved discriminative ability on minority nodes? \n2. Are there any additional factors other than aggregation and homophily ratio difference that you thought about?", "limitations": "None", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "GNN performance studies on datasets across difference structural subgroups is a crucial metric to understand the overall performance of the model. Quantitive understanding of the effect of aggregation and homophily ratio difference w.r.t train nodes is a significant metric to compare different GNN architectures. This provides new evaluation strategies for future GNN studies. The effect of new data splitting strategy is again a significant contribution and is useful to evaluate the overall GNN performance.\n\n", "weaknesses": "The work by itself is strong and would have been even stronger if presented with more understanding of the effectiveness of Deeper GNNs on doing comparatively well on minority nodes. ", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** The work by itself is strong and would have been even stronger if presented with more understanding of the effectiveness of Deeper GNNs on doing comparatively well on minority nodes.\n\n**Q1:** Is there a way to prove deeper GNNs improved discriminative ability on minority nodes?\n\n**R:** Thanks for your great question which inspires us in the future work on analyzing the effectiveness of Deeper GNN, especially on proving deeper GNNs improved discriminative ability on minority nodes. Note that, the following content, providing a detailed discussion of more understanding on deeper GNN, will be added in the revision. The potential approach to achieve analysis on deeper GNN can be found as follows:\n\n1. To empirically verify the improved discriminative ability on minority nodes, we apply a discriminative analysis with initial results in Figure 1(rebuttal pdf).The y-axis indicates the discriminative value $r=\\sum_{i=1}^K\\|\\mu_i^{tr}-\\mu_i^{mi} \\|$ where $\\mu_i^{tr},\\mu_i^{mi}$ is are the prototype of class i on train nodes and test minority nodes. x-axis indicates the hidden representation of different hops. With more hops of aggregations, the discriminative value decrease, indicates improved discriminative ability. The above discussion and experimental results will add to the revision.\n\n2. To theoretically verify the improved discriminative ability on minority nodes, we provide a potential thought based on our CSBM-S assumption and discrminative analysis of [1] in ICLR2023. [1] aims to theoretically quantify the discriminative ability on deeper GNNs with more aggregations. However, their analysis uses the vanilla CSBM model as the data assumption, denoted as $CSBM(\\mu_1, \\mu_2, p, q)$, where $\\mu_i$ is the feature mean of class $c_i$ with $i \\in \\{1, 2\\}$. The CSBM model presumes that all nodes follow either homophilic with $p>q$ or heterophilic patterns $p<q$ exclusively. However, this assumption conflicts with real-world scenarios as homophilic and heterophilic patterns coexist across different graphs, as shown in Figure 2. In contrast, our proposed CSBM-S model (Definition 1, line 167), $\\text{CSBM-S}(\\mu_1,\\mu_2,(p^{(1)}, q^{(1)}),(p^{(2)},q^{(2)}), \\Pr(homo))$, is more practical than the CSBM model.As far as we can see,conducting a similar discriminative analysis as [1] on our proposed CSBM-M model could be a good solution.\n\nNotably, the above discussion and experimental results will add to the future work section in the revision.\n\n**Q2:** Are there any additional factors other than aggregation and homophily ratio difference that you thought about?\n\n**R:** Thanks for your great question which inspires us in the future work on other important factors for performance disparity. Note that, the following content, providing a more detailed discussion of the important factor for performance disparity,will be added in Appendix. \n\nWe first want to clarify that,in our paper, we find that both the aggregated feature distance and homophily ratio difference could lead to the performance disparity along with aggregation, the key operation in GNNs. Detailed discussion can be found in Section 3. \n\nMoreover, a comprehensive discussion in the Related Work section (Appendix A). Existing literature [2-5] shows that some other structural information, e.g., degree, geodesic distance to the training node, and Personal Pagerank score, could lead to a performance disparity. Nonetheless, all those analyses and conclusions are conducted on homophilic graphs, e.g., PubMed and ogbn-arxiv, while ignoring the heterophilic graphs e.g., Chameleon and Squirrel, which also broadly exists in the graph domain. It could be an exciting new research direction to see how the above factors, which focus on the homophilic pattern in the context of both homophilic and heterophilic properties. \n\n\n\n[1] Wu, Xinyi, et al. \"A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks.\" The Eleventh International Conference on Learning Representations. 2022.\n\n[2] Qi Zhu, Natalia Ponomareva, Jiawei Han, and Bryan Perozzi. Shift-robust gnns: Overcoming the limitations of localized graph training data. Advances in Neural Information Processing Systems, 34:27965–27977, 2021.\n\n[3] Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. Subgroup generalization and fairness of graph\n521 neural networks. Advances in Neural Information Processing Systems, 34:1048–1061, 2021.\n\n[4] Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional networks. In Proceedings of the 29th ACM International Conference on Information Knowledge Management, pages 1435–1444, 2020.\n\n[5] Yushun Dong, Ninghao Liu, Brian Jalaian, and Jundong Li. Edits: Modeling and mitigatin data bias for graph neural networks. In Proceedings of the ACM Web Conference 2022, pages 629 1259–1269, 2022.630 "}, {"review_id": "O02PWqkgAV", "reviewer": "Reviewer_JCYy", "summary": "This paper provides a rigorous analysis of the effect of structural disparity on the performance of GNNs. The proposed CSBM-S model and the application of PAC-Bayes analysis, among others, show the different effects of aggregation on the performance of nodes with different structural disparity. The analysis further indicate subgroup generalization bound for GNN and elucidate the effectiveness of deeper GNNs.", "questions": "There are two assumptions that nodes from different subgroup share the same distribution and similar degree distribution. How does the conclusions are still valid without the above assumptions as stated in the supplementary material. \t", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "1.\tThe problem considered in this paper is extremely important. I agree with the authors that real-world graphs can’t be easily classified as homophilic or heterophilic. Therefore, analyzing how structural disparity influences the performance is essential to GNN design.\n2.\tIt is well backed up by theoretical analysis and examples. The authors show several nice analysis methods, including CSBM-S model and subgroup generalization bound for GNNs.\n3.\tExtensive experiment enables the conclusions presented in this paper to be convincing\n", "weaknesses": "1.\tThe conclusions hold in this paper share the same promise that the aggregation operation is neighbourhood averaging, which may not generalize to a broad range of GCNs models\n2.\tThe writing could be improved in terms of tone and phrases. There are also some grammar and spelling errors\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** The conclusions hold in this paper share the same promise that the aggregation operation is neighborhood averaging, which may not generalize to a broad range of GCNs models. \n\n**R:** Thanks for your great question pointing out the gap between our theoretical analysis and empirical result. We want to first clarify that the reason for utilizing average aggregation is for better motivation with the toy model in the introduction section and the theoretical analysis in Section 3.1 and 3.3, but not our ultimate conclusion.  Such mean aggregation is also widely adopted for theoretical analysis in many existing GNN literature [1-5]. Despite most existing GNNs may not be exact neighborhood averaging, they are still generally based on weighted neighborhood averaging''.\n\nMoreover, inspired by the theoretical understanding, we verify the conclusion with comprehensive empirical experiments which could be found in Section 3.4 and Appendix J. We can see that our theoretical results are still valid qualitatively across different datasets and various architectures. Note that, the experimental results include both shallow GNN, e.g., GCN, GAT and deeper GNN, e.g., GCNII, GPRGNN.Therefore, our conclusion that GNN can perform well on nodes in the majority pattern but not the minority pattern is still valid across architectures empirically. \n\n**W2:** The writing could be improved in terms of tone and phrases. There are also some grammar and spelling errors. \n\n**R:** We sincerely thank the reviewer for your valuable feedback. We have carefully revised the paper to address these weaknesses to meet the required standards. \n\n**Q1:** There are two assumptions that nodes from different subgroup share the same distribution and similar degree distribution. How does the conclusions are still valid without the above assumptions as stated in the supplementary material.\n\n**R:** Thanks for your great questions revolving on the necessity of assumptions in. We first need to clarity that assumptions are not strictly necessary but employed for the sake of elegant expression. We want to clarify that we only claim that assumption 2 can be loose but not assumption 1. Assumption 1 tells that node features within the same class are sampled from the same Gaussian distribution, regardless of different structural patterns. The reason why we adopt assumption 1 is that our paper majorly focuses on the structure disparity, controlling by $p$ and $q$, but not the disparity on the original node feature. Therefore, we just keep the samples from the same distribution. \nSuch an assumption is also aligning with the real-world graph as most original node feature shows a strong correlation with the class information. Empirical evidence can be found in Table 10 and 11. We can see that the MLP taking only node feature as input also shows certain discriminative ability. \n\nThe assumption 2 is that nodes follow the same degree distribution with $p^{(1)} + q^{(1)} = p^{(2)} + q^{(2)}$. To get rid of this assumption, we can assume that $p^{(1)} + q^{(1)} = \\alpha (p^{(2)} + q^{(2)})$, where $\\alpha \\in [0, +\\infty)$ is a proportionality coefficient. \n\nThen the new Lemma 1 is: \n$$\n    |\\mathbf{P}_1(y_u=c_1|\\mathbf{f}_u)-\\mathbf{P}_2(y_v=c_1|\\mathbf{f}_v)| \\le \\frac{\\alpha \\rho^2}{\\sqrt{2\\pi}\\sigma} |h_u - h_v|\n$$\nOriginal Lemma 1 is \n$$\n|\\mathbf{P}_1(y_u=c_1|\\mathbf{f}_u)-\\mathbf{P}_2(y_v=c_1|\\mathbf{f}_v)| \\le \\frac{\\rho^2}{\\sqrt{2\\pi}\\sigma} |h_u - h_v|\n$$\n$\\rho=\\left \\|\\mathbf{u}_1-\\mathbf{u}_2\\right \\|$ is original feature separability, independent with structure.We can see that the only difference is an additional coefficient $\\alpha$ depending on the degree distribution differences. Such minor difference does not affect our conclusion that nodes with a small homophily ratio difference $\\|h_1 -h_2\\|$ are likely to share the same class. \n\n[1] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? The Eleventh International Conference on Learning Representations. 2022.\n\n[2] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Graph convolution for semi-supervised classification: Improved linear separability and out-of-distribution generalization. International Conference on Machine Learning. PMLR, 2021.\n\n[3] Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath. Effects of graph convolutions in multi-layer networks. In The Eleventh International Conference on Learning Representtions, 2023.\n\n[4] Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang. Augmentation-free graph contrastive learning. arXiv preprint arXiv:2204.04874, 2022.\n\n[5] Wu, Xinyi, et al. \"A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks.\" The Eleventh International Conference on Learning Representations. 2022."}, {"review_id": "ZMiSnS4vHI", "reviewer": "Reviewer_GxBV", "summary": "This paper focuses on the performance disparity on homophily and heterophily nodes in node-level classification tasks. It claims that although GNNs have good performance on both pure homophily and pure heterophily graphs, GNNs cannot perform well when dealing with graphs with both these two types of nodes. The paper then analyses the reason for different impact on majority and minority nodes and illustrates the aggregation function's contribution on this. It delves into the theoretical analysis, deriving a non-i.i.d PAC-Bayesian generalization bound based on the Subgroup Generalization bound of Deterministic Classifier. The theoretical analysis indicates that test nodes with larger aggregated feature distances and homophily ratio differences from training nodes experience performance degradation. The practical implications of the findings are demonstrated on real-world datasets.", "questions": "See the weaknesses section.", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper provides sufficient real-world experiments to show how the homophily ratio and the feature distance influence the GNN’s aggregation and the actual performance on both homophilic and heterophilic datasets. This could sever as a foundation for future GNN architecture design.\n-  The paper performs the theoretical analysis that reveals potential reasons for the performance disparity. The findings are supported by experimental results.\n- The paper is well structured with good clarity in presentation. \n", "weaknesses": "- The paper identifies the problem of performance disparity but does not provide a solution to address it. \n- The classification of nodes into homophily and heterophily classes using a hard threshold is a simple and ideal setting. This setting may fail to capture the complexity and nuances that may exist in real-world scenarios. Do the conclusions/findings still hold if we directly use the continuous homophily ratio rather than thresholding it? \n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1:** The paper identifies the problem of performance disparity but does not provide a solution to address it \n\n**R:** Thanks for the great question revolving the contribution of this paper. We would like to first provide a more comprehensive understanding on the motivation and contribution of our paper and then discuss the potential solution \n\nWe first clarify the contribution of our paper as follows:\n\n1. points out the missing fact that homophilic and heterophilic patterns coexist across graphs \n2. offers a new local perspective to evaluate GNN performance and indeed\n3. gains insights into which nodes and why GNN can work well or not. \n\nOverall speaking, our paper does not focus on specific model design but **provides a new landscape for understanding existing GNNs and paving the way for future GNN design.** \n\nMore specifically, our work can\n\n1. bring insights for previous research progress. We figure out how recent-developed deeper GNNs are better than vanilla GNNs\n2. provide an outlook for future research to solve the performance disparity across different GNN architectures. It clearly points out the remaining improvement space for GNN design\n3. give insights into different graph applications including Graph OOD, robustness,and fairness\n\nWe believe our work is technique-sound with both empirical and theoretical insights, helping to understand and push the graph domain further.\n\nAccordingly, we will **add future work section with potential solutions and preliminary solution to mitigate performance disparity** as follows, leaving as inspiration for future work. Potential solutions are as follows: \n\n1. combine MLP and GNN in an adaptive approach since MLPs can achieve better performance on minority nodes and GNNs better on majority nodes. Ideally, we can adaptively select MLP for minority nodes and GNN for majority nodes, using an adaptively gated function to control proportion of MLP and GNN. Our findings suggest the homophilic/heterophilic pattern selection can serve as a guide for learning the gate function.\n2. utilize global structural information, as the global pattern is more robust, showing less disparity than the local structural pattern. Empirical evidence can be found in Figure 9 that the higher-order homophily ratio differences are smaller than the local structure disparity \n\nWe then propose a simple solution to solve **performance disparity problem** inspired by the first potential solution. Instead of learning a gate function with homophilic/heterophilic pattern selection as guidance, we use a simple heuristic threshold to identify whether a node is in majority pattern or minority pattern, then select GCN and GLNN (an MLP-based model) for inference on test nodes in majority pattern and minority pattern, respectively. A simple smoothness-based metric $r=\\frac{1}{|\\mathcal{N}_i|}\\sum_{j\\in \\mathcal{N}_i}\\|\\mathbf{x}_i-\\mathbf{x}_j\\|_F^2$ is then applied.A small r indicates center node i is similar to neighborhood nodes, reflecting the homophilic pattern\n\nOur proposed **minor selection** has the following steps\n\n1. calculate $R=\\{r_1,\\cdots,r_n\\}$ for all test nodes\n2. sort the smoothness list R\n3. If graph is a homophilic one, select largest $\\alpha$% test nodes, utilizing MLP for inference, while others utilize GCN \n4. If graph is a homophilic one, select smallest $\\alpha$% test nodes, utilizing MLP for inference, while others utilize GCN \n\nNotably,**our preliminary study is based on the vanilla GCN model**, our minority selection can also combine with other GNNs.The focus of the proposed method is to mitigate the performance disparity issue while keeping the overall performance\n\nThe overall accuracy, WDP, and WSD scores are shown in Table 1(rebuttal pdf). Overall accuracy is comparable with other models.  WDP and WSD are to evaluate performance disparity, defined as:\n$$\nWDP=\\frac{\\sum_{i=1}^D N_i\\cdot|A_i-A_{avg}|}{N_{total}}\n$$\n\n$$\nWSD=\\sqrt{\\frac{1}{N_{total}}\\sum_{i=1}^DN_i\\cdot (A_i-A_{avg})^2}\n$$\n\nD is the number of groups,$N_i$ is the node number of group i,$A_i$ is the accuracy of group i, $A_{avg}$ is the weighted average accuracy of all groups.**A smaller WSD and WDP indicate the performance disparity is small**. Our proposed method shows much better fairness than vanilla GCN, and even better than deeper GNN in most datasets. Although our study was conducted on a tight schedule and is preliminary, the impressive performance indicates a promising direction. Further refined designs could enhance it.\n\n**W2:** The classification of nodes into homophily and heterophily classes using a hard threshold is a simple and ideal setting. It may fail to capture nuances that may exist in real-world scenarios. Do conclusions still hold if we directly use the continuous homophily ratio rather than thresholding it?\n\n**R:** Thanks for the question on homophilic and heterophilic patterns. We initially utilize node homophily ratio $h>0.5$ as homophilic node and $h<0.5$ as heterophilic node. Nonetheless, we want to clarify that the purpose of **using a hard threshold 0.5 is to ease the problem statement** and better understanding at the beginning of the paper. Notably, **most of analyses and conclusions do not revolve around the hard threshold.** For theoretical analysis in Sections 3.1 and 3.3, we majorly consider the homophily ratio difference $|h_i-h_j|$ where $h_i$ is the continuous homophily ratio. \n\nFor empirical analysis, disparity scores $s_u=\\|F_u^{(2)}-F_v^{(2)}\\|+|h_u^{(2)}-h_v^{(2)}|$ in Section 3.4 also **considers the continuous homophily ratio case.** Moreover, we also verify the conclusion on multiple datasets with complexity and nuances scenarios as shown in Figure 13. Additional experiments shown in Figure 15-21 of Appendix J indicate the validity of our conclusion on Cora, CiteSeer, Amazon-rating, IGB-tiny, and Twitch-gamers datasets. The above observations indicate that our conclusion could successfully extend to multiple datasets with complexity and nuances.\n"}, {"review_id": "7zKQ1L6iNa", "reviewer": "Reviewer_itvA", "summary": "This paper investigates the effectiveness of GNNs on nodes with different structural patterns in real-world graphs and proposes a new method to identify the reasons for performance disparities. The authors found that GNNs tend to perform well on homophilic nodes within homophilic graphs, but struggle with the opposite node set, and they provide insights into the performance disparities by analyzing aggregated feature distance and homophily ratio difference between training and testing nodes.", "questions": "1.\tLine 49-50, “while heterophilic graphs exhibit an opposite phenomenon with homophilic nodes in the majority and heterophilic ones in the minority.” Check this definition of heterophilic graphs.\n2.\tLine 55-56, “ Such differences may lead to performance disparity between nodes in majority and minority patterns.” If you randomly sample training and test data, the distribution of the majority and minority patterns should be the same for training and test nodes. Thus, the disparity shown in this example is not valid in practice.\n3.\t“Consequently, the performance disparity can be overwhelmed by such gap which renders the effect from structural patterns.” I don’t understand this sentence. Please elaborate the reason why you use GLNN here.\n4.\tAre the observations in Figure 3 also hold on other benchmark datasets?\n5.\tLine 170, why both homophilic and heterophilic patterns have p>q? In your definition, nodes from the subgroup but different classes have the same (p,q)?\n6.\tLine 179-181, check the English.\n7.\t“This proposition suggests that aggregation results in a distance gap between different patterns within the same class.” I cannot see how this proposition suggests the distance gap. Please elaborate it.\n8.\tIn Lemma 1, are nodes u,v from the same class? Why do you want to examine “discrepancy between nodes and with the same aggregated feature but different structural patterns.”? How does this relates to the proposed claim about majority and minority nodes?", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "This paper provides both empirical and theoretical evidence to support its findings. It conducts rigorous analyses and derives a non-i.i.d. PAC-Bayesian generalization bound for GNNs, which adds credibility to the research. The authors substantiate their findings with controllable synthetic experiments and real-world datasets, further strengthening the quality of the paper.", "weaknesses": "1.\tWriting needs to improve.\n2.\tSome explanation needs more elaboration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Q2:** Such differences lead to performance disparity between nodes in majority and minority patterns.If randomly sample train and test data,the distribution of majority and minority patterns is same for train and test nodes.Thus,the disparity shown in example is not valid in practice\n\n**R:** The focus of this paper is structural disparity but not distribution shift, which are not the same concept.Disparity shown in example is valid in practice for **there are always both homophilic and heterophilic nodes in the same graph**. The only difference from toy example is homophilic and heterophilic patterns may not be so extreme, there are some heterophilic edges in homophilic nodes,and vice versa.\n\n\nDetails explanations:Structural disparity is that homophilic and heterophilic patterns exist simultaneously in a single node set. Such disparity consistently exists in all graphs, as shown in Figure 2, 13.If randomly sample train and test data, **both train and test set will have homophilic and heterophilic patterns, indicating structural disparity** happens on both train and test set.**Example is to show two patterns together in the same graph, not train is in homophilic pattern, but test is in heterophilic pattern.**\n\nEmpirical evidence in Figure 2 shows structural disparity leads to performance disparity, where **experiments follow random split setting without distribution shift.**The reason for performance disparity is GNNs tend to learn better on the train majority pattern with more supervised signals while ignoring the minority ones. Then GNNs will perform well on the test majority node but not minority ones.\n\n**Q8:** In Lemma 1,are nodes u,v from the same class?Why examine discrepancy between nodes with the same aggregated feature but different structural patterns?How this relates to claim about majority and minority nodes?\n\n**R:** In lemma 1,we do not necessarily require nodes u, v from the same class, instead, we attempt to measure how likely nodes u and v are in the same class regarding to the structure disparity.\n\nWe clarify section 3.1 aims to answer:How does aggregation affect nodes with different structural patterns? We examine how nodes with structure disparity(homophily ratio difference $|h_i-h_j|$) show different behaviors along with aggregation, the key operation in GNN.Thus, our analysis focuses on the node aggregated features in different structural patterns\n\nFollowing explanations are four-folds:1.what and how to measure behavior differences 2.what is structural disparity 3.Lemma 1 explanation:structural disparity leads to behavior difference 4.how lemma is correlated with claim about majority and minority nodes\n\n1. In the case that behavior difference **does not exist**,nodes u and v the same aggregated feature $f_u = f_v$ **should be in the same class**. In contrast, behavior difference corresponds to the case that the same feature but not in the same class.The probability gap of two nodes sharing the same class $|P(y=c_1|f_u)-P(y=c_1|f_v)|$ is utilized to measure what extent behavior difference happens. Large $|P(y=c_1|f_u)-P(y=c_1|f_v)|$ indicates more likely that two nodes are in different class \n2. Structural disparity is nodes in the same set but different structural patterns.We measure it with $|h_u-h_v|$\n3. Lemma 1 shows when structure disparity $|h_u-h_v|$ is large, $|P(y=c_1|f_u)-P(y=c_1|f_v)|$ could be large, indicating node u and v are likely to have different classes,**violating the consistency behavior (with no structural disparity) expecting the same aggregated feature should map to the same class**\n4. Lemma 1 does not directly correlate to majority and minority nodes, but serve as a necessary preliminary step for the claim about majority and minority nodes.Notably,in section 3.1,we only mention the existence of both homophilic and heterophilic patterns,without identifying which pattern is the majority.Lemma 1 only shows the existence of behavior disparity,serving as a preliminary step for analysis on majority and minority nodes.Once only behavior disparity exists on different structural patterns,it is possible for performance difference exists in majority and minority patterns\n\n**Q3:** Elaborate reason why use GLNN in Figure 1\n\n**R:** We rephrase with more evidence: Consequently, an under-trained vanilla MLP comparing with a well-trained GNN leads to an unfair comparison without rigorous conclusion\n\nThe experiment is to examine the effectiveness of GCN on utilizing different structural patterns. Therefore, we compare GCN and MLP architectures as GCN utilizes graph structure during inference while MLP cannot, serving as a structure-agnostic baseline. When GCN surpasses MLP,it indicates GNN benefits from structural patterns effectively, and vice visa.Notably, GLNN can be viewed as a better-trained MLP model. GLNN also utilizes the same MLP model architecture as vanilla MLP, the only difference between vanilla MLP and GLNN is that GLNN is trained in an advanced distillation manner while vanilla MLP is trained with cross-entropy loss\n\nThe reason why we utilize GLNN rather than only comparing GCN with vanilla MLP is that MLP meets optimization issue on training. Experimental results are shown in Figure 1(rebuttal pdf). Such an obstacle leads to a large performance gap (more than 20%) between under-trained vanilla MLP and well-trained GCN.**Consequently, large performance gap induced by training difficulty hinders the potential for MLP architecture.** Contrastly, GLNN enjoys better training process leads to a more clear comparison between well-trained GNN and well-trained MLP(GLNN) architecture with a convincing conclusion\n\n**Q4:** Are observations in Figure 3 hold on other datasets?\n\n**R:** Yes.See additional results in Figure 14, Appendix H. Conclusions also hold for Cora, CiteSeer, IGB-tiny, twitch-gamers, and Amazon-ratings datasets\n\n**Response on other questions on explanation and typos are in global rebuttal**\n\n- Q6,7->problem1\n- Q5->problem2\n- Q1->problem3"}]

Author rebuttal:
Thanks to all reviewers for their constructive reviews. The pdf file contains new experimental results for reviewers pgwY and GxBV.



With the help of reviewers, we find some typos and writing issues in our paper. We will correct those mistakes and add more explanations for better understanding in our revision. Detailed problems are shown as follows. 

**Problem1:** Grammar problem in Lines 179-181. Elaborate proposition 1.

**R:** The updated version of Proposition 1 is as follows. The aggregated feature mean distance between homophilic and heterophilic node subgroups within class $c_1$ is$\left\|\frac{p^{(1)}\mu_{1}+q^{(1)}\mu_{2}}{p^{(1)}+q^{(1)}}-\frac{p^{(2)}\mu_{1}+q^{(2)}\mu_{2}}{p^{(2)}+q^{(2)}}\right\|>0$, indicating the aggregated feature of homophilic and heterophilic subgroups are from different feature distributions, with a mean distance larger than 0 distance before aggregation, since original node features draw from the same distribution, regardless of different structural patterns.

The Lemma aims to show how nodes with structural disparity $|h_i-h_j|$ behave differently along with aggregation. Typically, behavior difference is measured with the distance of feature means from different structural patterns within the same class. **Behavior disparity and feature mean distance does not exist before aggregation**, since nodes in the same class are samples from the same original feature distribution $\mathcal{N}(\mu_1,\sigma^2)$, regardless of different groups, **with the same feature mean**. The feature mean distance should be $\|\mu_1-\mu_1\|=0$.

After aggregation, the aggregated feature mean of the homophilic group will be $\frac{p^{(1)} \mu_{1}+q^{(1)}\mu_{2}}{p^{(1)}+q^{(1)}}$ while the heterophilic group will be $\frac{p^{(2)}\mu_{1}+q^{(2)}\mu_{2}}{p^{(2)}+q^{(2)}}$. Since $p^{(1)}\ne p^{(2)}$ and $q^{(1)}\ne q^{(2)}$, the aggregated mean feature distance $\left\|\frac{p^{(1)}\mu_{1}+q^{(1)}\mu_{2}}{p^{(1)}+q^{(1)}}-\frac{p^{(2)}\mu_{1}+q^{(2)}\mu_{2}}{p^{(2)}+q^{(2)}}\right\|>0$. It indicates that **there is a distance gap feature mean from different node subgroups in the same class**, indicating behavior differences. 

**Problem2:** typo in Line 170, heterophilic patterns have $p>q$ 

**R:** Heterophilic pattern should have $p^{(2)}<q^{(2)}$ as shown in line 163. We will correct it in revision. Consequently, the CSBM-S model has different p and q values where $p^{(1)}>q^{(1)}$ and $p^{(2)}<q^{(2)}$. 

**Problem3:** typo in line 58-60 on homophilic and heterophilic

**R:** The revision is: while heterophilic graphs exhibit an opposite phenomenon with **heterophilic** nodes in the majority and **homophilic** ones in the minority.



Meta-review: This paper studies the problem of understanding why GNNs work well on certain types of graph settings and not on others (for node classification tasks). For this purpose the authors propose to study the effect of the presence of homophillic and heterophillic nodes and show that GNNs work well when only one types of patterns are present but not when the two patterns are mixed. This is supported by theoretical analysis in the form of generalization bounds and experiments on real world graphs. 

Overall the reviewers liked the paper and were positive about the results presents and the problem studied. During the discussion phase a few presentation issues were noted by the reviewers and the authors are strongly encouraged to fix these in the next version of the paper.
Decision: Accept (poster)