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.

§ INTRODUCTION

Examples of homophilic and heterophilic patterns. Colors/numbers indicate node features/labels.

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

GNNs have been widely recognized for their effectiveness on homophilic graphs [13, 2, 10, 4, 14, 15, 16].
In homophilic graphs, connected nodes tend to share the same label, which we refer to as homophilic patterns.
An example of the homophilic pattern is depicted in the upper part of Figure <ref>, where node features and node labels are denoted by colors (i.e., blue and red) and numbers (i.e., 0 and 1), respectively.
We can observe that all connected nodes exhibit homophilic patterns and share the same label 0.
Recently, several studies have demonstrated that GNNs can also perform well on certain heterophilic graphs [17, 12, 18].
In heterophilic graphs, connected nodes tend to have different labels, which we refer to as heterophilic patterns. The example in the lower part of Figure <ref> shows the heterophilic patterns.
Based on this example, we intuitively illustrate how GNNs can work on such heterophilic patterns (lower right): after averaging features over all neighboring nodes, nodes with label 0 completely switch from their initial blue color to red, and vice versa; despite this feature alteration, the two classes remain easily distinguishable since nodes with the same label (number) share the same color (features).

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

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

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

§ PRELIMARIES

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

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

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

§ EFFECTIVENESS OF GNN ON NODES WITH DIFFERENT STRUCTURAL PROPERTIES

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

[PubMed ($h$=0.79)]

[Ogbn-arxiv ($h$=0.63)]

[Chameleon ($h$=0.22)]

[Squirrel ($h$=0.25)]

Node homophily ratio distributions. All graphs exhibit a mixture of homophilic and heterophilic nodes despite various graph homophily ratio $h$.

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

[PubMed ($h$=0.79)]

[Ogbn-arxiv ($h$=0.63)]

[Chameleon ($h$=0.22)]

[Squirrel ($h$=0.25)]

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

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

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 <ref> focuses on how aggregation, the fundamental mechanism in GNNs, affects nodes with distinct structural patterns differently.
Upon identifying differences, Section <ref> further analyzes how such disparities contribute to superior performance on the majority nodes  as opposed to minority nodes.
Building on these observations, Section <ref> recognizes the key factors driving performance disparities on different structural patterns with a non-i.i.d. PAC-Bayes bound.
Section <ref> empirically corroborates the validity of our theoretical analysis with real-world datasets.

§.§ How does aggregation affect nodes with structural disparity differently?

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

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

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

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

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

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

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

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

In addition to node feature differences with the same class, we further examine the discrepancy between nodes $u$ and $v$
with the same aggregated feature $\rvf_u=\rvf_v$ but different structural patterns.
We examine the discrepancy with the probability difference of nodes $u$ and $v$ in class $c_1$, denoted as $|\rmP_1(y_u=c_1|\rvf_u)-\rmP_2(y_v=c_1|\rvf_v)|$.
$\rmP_1$ and $\rmP_2$ are the conditional probability of $y=c_1$ given the feature $\rvf$ on structural patterns $(p^{(1)}, q^{(1)})$ and $(p^{(2)}, q^{(2)})$, respectively.

With assumptions (1) A balance class distribution with $\rmP(Y=1)=\rmP(Y=0)$ and (2) aggregated feature distribution shares the same variance $\sigma$.
When nodes $u$ and $v$ have the same aggregated features $\rvf_u=\rvf_v$ but different structural patterns, $(p^{(1)}, q^{(1)})$ and $(p^{(2)}, q^{(2)})$, we have:

\begin{equation}
|\rmP_1(y_u=c_1|\rvf_u)-\rmP_2(y_v=c_1|\rvf_v)| \le \frac{\rho^2}{\sqrt{2\pi}\sigma} |h_u - h_v|
\end{equation}

Notably, above assumptions are not strictly necessary but employed for the sake of elegant expression.
$\rho=\left \|\vmu_1-\vmu_2\right \|$
is the original feature separability, independent with structure.
Lemma <ref> implies that nodes with a small homophily ratio difference $|h_1 - h_2|$ are likely to share the same class, and vice versa.
The proof details and additional analysis on between-class effects are provided in Appendix <ref>.

§.§ How does Aggregation Contribute to Performance Disparity?

Illustration on discriminative ratio variation along with aggregation. x-axis denotes the number of aggregations and y-axis denotes the discriminative ratio.

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

We then conduct an empirical discriminative analysis taking both mean aggregated features and training labels into consideration.
Drawing inspiration from existing literature [39, 40, 41, 42],
we describe the discriminative ability with the distance between train class prototypes [43, 44], i.e., feature mean of each class, and the corresponding test class prototype within the same class $i$.
For instance, it can be denoted as $||\mu_i^{\text{tr} }-\mu_i^{\text{ma}}||$, where $\mu_i^{\text{tr}}$ and $\mu_i^{\text{ma}}$ are the prototype of class $i$ on train nodes and test majority nodes, respectively.
A smaller value suggests that majority test nodes are close to train nodes within the same class, thus implying superior discriminative ability.
A relative discriminative ratio is then proposed to compare the discriminative ability between majority and minority nodes.
It can be denoted as: $r$=$\sum_{i=1}^K\frac{|| \vmu_i^{\text{tr} }-\vmu_i^{\text{ma}}||}{|| \vmu_i^{\text{tr} }-\vmu_i^{\text{mi}}||}$
where $\mu_i^{\text{mi} }$ corresponds to the prototype on minority test nodes.
A lower relative discriminative ratio suggests that majority nodes are easier to be predicted than minority nodes.

The relative discriminative ratios are then calculated on different hop aggregated features and original features denote as 0-hop.
Experimental results are presented in Figure <ref>, 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 <ref>.
Furthermore, instance-level experiments other than class prototypes are in Appendix <ref>.

§.§ Why does Performance Disparity Happen? Subgroup Generalization Bound for GNNs

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

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

Each node subgroup $V_m$ follows the CSBM distribution $V_m \sim \text{CSBM}(\vmu_1, \vmu_2, p^{(i)}, q^{(i)})$, where different subgroups share the same class mean but different intra-class and inter-class probabilities $p^{(i)}$ and $q^{(i)}$. Moreover, node subgroups also share the same degree distribution as $p^{(i)} + q^{(i)} = p^{(j)} + q^{(j)}$.

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

[GNN model]
We focus on SGC [15] with the following components:
(1) a one-hop mean aggregation function $g$ with $g(X, G)$ denoting the output.
(2) MLP feature transformation $f(g_i(X, G); W_1, W_2, \cdots , W_L)$, where $f$ is a ReLU-activated $L$-layer MLP with $W_1, \cdots, W_L$ as parameters for each layer. The largest width of all the hidden layers is denoted as $b$.

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

Our main theorem is based on the PAC-Bayes analysis which typically aims to bound the generalization gap between the expected margin loss $\risk_m$ on test subgroup $V_m$ for a margin $0$ and the empirical margin loss $\hLg_{\text{tr}}$ on train subgroup $V_\text{tr}$ for a margin $\gamma$. Those losses are generally utilized in PAC-Bayes analysis[47, 48, 49, 50]. More details are found in Appendix <ref>.
The formulation is shown as follows:

Let $\tilde{h}$ be any classifier in the classifier family $\gH$ with parameters $\{\widetilde{W}_l\}_{l=1}^L$.
for any $0< m \le M$, $\gamma \ge 0$, and large enough number of the training nodes $N_\text{tr}=|V_\text{tr}|$,
there exist $0<\alpha<\frac{1}{4}$ with probability at least $1-\delta$ over the sample of $y^\text{tr}:=\{y_i\}_{i\in V_\text{tr}}$, we have:

\begin{equation}
\begin{aligned}
\label{eq:main}
\risk_m(\tilde{h}) \le \hLg_\text{tr}(\tilde{h}) + O\sbra   \underbrace{\frac{K\rho}{\sqrt{2\pi}\sigma}   (\epsilon_m + |h_\text{tr} - h_m|\cdot \rho)}_{\text{\textbf{(a)}}} + \underbrace{\frac{b\sum_{l=1}^L\|\widetilde{W}_l\|_F^2}{(\gamma/8)^{2/L}N_\text{tr}^{\alpha}}(\epsilon_m)^{2/L}}_{\text{\textbf{(b)}}} + \mathbf{R}\sket
\end{aligned}
\end{equation}

The bound is related to three terms:
(a) describes both large homophily ratio difference $|h_\text{tr} - h_m|$ and large aggregated feature distance $\epsilon = \max_{j\in bV_m}\min_{i\in V_\text{tr}} \|g_i(X, G)-g_j(X, G)\|_2$ between test node subgroup $V_m$ and training nodes $V_\text{tr}$ lead to large generalization error. $\rho=\left \|\vmu_1 - \vmu_2\right \|$ denotes the original feature separability, independent of structure. $K$ is the number of classes.
(b)  further strengthens the effect of nodes with the aggregated feature distance $\epsilon$, leads to a large generalization error.
(c) $\mathbf{R}$ is a term independent with aggregated feature distance and homophily ratio difference, depicted as $\frac{1}{N_\text{tr}^{1-2\alpha}} + \frac{1}{N_\text{tr}^{2\alpha}} \ln\frac{LC(2B_m)^{1/L}}{\gamma^{1/L}\delta} $, where $B_m= \max_{i\in V_\text{tr}\cup V_m}\|g_i(X,G)\|_2$ is the maximum feature norm. $\mathbf{R}$ vanishes as training size $N_0$ grows. Proof details are in Appendix <ref>

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

§.§ Performance Disparity Across Node Subgroups on Real-World Datasets

[PubMed ($h$=0.79)]

[Ogbn-arxiv ($h$=0.63)]

[Chameleon ($h$=0.22)]

[Squirrel ($h$=0.25)]

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

[PubMed ($h$=0.79)]

[Ogbn-arxiv ($h$=0.63)]

[Chameleon ($h$=0.22)]

[Squirrel ($h$=0.25)]

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

[PubMed ($h$=0.79)]

[Ogbn-arxiv ($h$=0.63)]

[Chameleon ($h$=0.22)]

[Squirrel ($h$=0.25)]

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

To empirically examine the effects of theoretical analysis, we compare the performance on different node subgroups divided with both homophily ratio difference and aggregated feature distance to training nodes with popular GNN models including GCN [2], SGC [15], GAT [10], GCNII [51], and GPRGNN [52].
Typically, test nodes are partitioned into subgroups based on their disparity scores to the training set in terms of both 2-hop homophily ratio $h_i^{(2)}$ and 2-hop aggregated features $\rmF^{(2)}$ obtained by $\rmF^{(2)}=(\tilde{\rmD}^{-1}\tilde{\rmA})^2 \mathbf{X}$, where $\tilde{\rmA} = \rmA + \rmI$ and $\tilde{\rmD} = \rmD + \rmI$.
For a test node $i$, we measure the node disparity by
(1) selecting the closest training node $v=\text{arg}\min_{v\in V_0} ||\rmF^{(2)}_u-\rmF^{(2)}_v||$
(2) then calculating the disparity score $s_u = ||\rmF^{(2)}_{u}-\rmF^{(2)}_v||_2 + |h^{(2)}_u - h^{(2)}_v|$, where the first and the second terms correspond to the aggregated-feature distance and homophily ratio differences, 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 <ref> with the following observations.
Obs.1: We note a clear  test accuracy degradation with respect to the increasing differences in aggregated features and homophily ratios.
Furthermore, we investigate on the individual effect of aggregated feature distance and homophily ratio difference in Figure <ref> and <ref>, respectively. An overall trend of performance decline with increasing disparity score is evident though some exceptions are present.
Obs.2: When only considering the aggregated feature distance, there is no clear trend among groups 1, 2, and 3 on GCN, SGC, and GAT on heterophilic datasets.
Obs.3: When only considering the homophily ratio difference, there is no clear trend among groups 1, 2, and 3 across four datasets.
These observations underscore the importance of both aggregated-feature distance and homophily ratio differences in shaping GNN performance disparity. Combining these factors together provides a more comprehensive and accurate understanding of the reason for GNN performance disparity.
For a more comprehensive analysis, we further substantiate our finding involving higher-order information and a wider array of datasets in Appendix <ref>.

In this section, we study GNN performance disparity on nodes with distinct structural patterns and uncover its underlying causes.
We primarily investigate the impact of aggregation, the key component in GNNs, on nodes with different structural patterns in Sections <ref> and <ref>.
We observe that aggregation effects vary across nodes with different structural patterns, notably enhancing the discriminative ability on majority nodes.
These observed performance disparities inspire us to identify crucial factors contributing to GNN performance disparities across nodes with a non-i.i.d PAC-Bayes bound in Section <ref>.
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 <ref>.

§ IMPLICATIONS OF GRAPH STRUCTURAL DISPARITY

In this section, we illustrate the significance of our findings on structural disparity via
(1) elucidating the effectiveness of existing deeper GNNs
(2) unveiling an over-looked aspect of distribution shift on graph out-of-distribution (OOD) problem, and introducing a new OOD scenario accordingly.
Experimental details and discussions on more implications are in Appendix <ref> and <ref>, respectively.

§.§ Elucidate the effectiveness of Deeper GNNs

Deeper GNNs [52, 51, 14, 53, 54, 55, 56] enable each node to capture more complex higher-order graph structure than vanilla GCN, via reducing the over-smoothing problem [57, 58, 59, 54, 60]
Deeper GNNs empirically exhibit overall performance improvement, as demonstrated in Appendix <ref>.
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[52], APPNP[14], and GCNII[51], on node subgroups with varying homophily ratios, adhering the same setting with Figure <ref>.
Experimental results are shown in Figure <ref>.
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 <ref> and <ref>.

[PubMed ($h$=0.79)]

[Ogbn-arxiv ($h$=0.63)]

[Chameleon ($h$=0.22)]

[Squirrel ($h$=0.25)]

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.

Multiple hop homophily ratio differences between training and minority test nodes.

Having identified where deeper GNNs excel, reasons why effectiveness primarily appears in the minority node group remain elusive.
Since the superiority of deeper GNNs stems from capturing higher-order information, we further investigate how higher-order homophily ratio differences vary on the minority nodes, denoted as, $|h_u^{(k)}-h_v^{(k)}|$, where node $u$ is the test node, node $v$ is the closest train node to test node $u$.
We concentrate on analyzing these minority nodes $V_{\text{mi}}$ in terms of default one-hop homophily ratio $h_u$ and examine how $\sum_{u\in V_{\text{mi}}}|h_u^{(k)}-h_v^{(k)}|$ varies with different $k$ orders.
Experimental results are shown in Figure <ref>, where a decreasing trend of homophily ratio difference is observed along with more neighborhood hops.
The smaller homophily ratio difference leads to smaller generalization errors with better performance.
This observation is consistent with [19], where heterophilic nodes in heterophilic graphs exhibit large higher-order homophily ratios, implicitly leading to a smaller homophily ratio difference.

§.§ A new graph out-of-distribution scenario

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

Performance (Accuracy) on the proposed OOD split.

Pubmed     Ogbn-Arxiv     Squirrel     Chameleon
GCN(i.i.d)     89.18±0.15     72.99±0.14     58.09±0.71     75.09±0.79
GCN      51.04±0.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     47.01±1.09

GCNII     67.76±0.36     36.81±0.14     37.15±1.39     41.25±2.03

GPRGNN     57.24±0.18     34.95±0.43     42.43±7.71     35.27±7.67
SRGNN     57.91±0.10     40.37±1.65     37.62±1.74     42.09±0.43

EERM     65.37±1.35     34.23±0.46     40.93±0.57      45.84±1.05

EERM(II)     67.59±0.91     40.28±0.84     44.31±0.40     48.59±0.78

Given the prevalence and importance of the graph structural shift, we propose a new graph OOD scenario emphasizing this concept shift.
Specifically, we introduce a new data split on existing datasets, namely Cora, CiteSeer, PubMed, Ogbn-Arxiv, Chameleon, and Squirrel, where majority nodes are selected for train and validation, and minority ones for test.

This data split strategy highlights the homophily ratio difference and the corresponding concept shift.
To better illustrate the challenges posed by our new scenario, we conduct experiments on models including GCN, MLP, GLNN, GPRGNN, and GCNII. We also include graph OOD algorithms, SRGNN [62] and EERM [61], with GCN encoders. EERM(II) is a variant of EERM with a GCNII encoder
For a fair comparison, we show GCN performance on an i.i.d. random split, GCN(i.i.d.), sharing the same node sizes for train, validation, and test.
Results are shown in Table <ref> while additional ones are in Appendix <ref>.
Following observations can be made:
Obs.1: The performance degradation can be found by comparing OOD setting with i.i.d. one across four datasets, confirming OOD issue existence.
Obs.2: MLP-based models and deeper GNNs generally outperform vanilla GCN,  demonstrating the superiority on minority nodes.
Obs.3: Graph OOD algorithms with GCN encoders struggle to yield good performance across datasets, indicating a unique challenge over other Graph OOD scenarios.
This primarily stems from the difficulty in learning both accurate relationships on homophilic and heterophilic nodes with distinct $\rmP(\rmY|\rmX)$.
Nonetheless, it can be alleviated by selecting a deeper GNN encoder, as the homophily ratio difference may vanish in higher-order structure information, with reduced concept shift.
Obs.4: EERM(II), EERM with GCNII, outperforms the one with GCN.
Observations suggest that GNN architecture plays an indispensable role in addressing graph OOD issues, highlighting the new direction.

§ CONCLUSION & DISCUSSION

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

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

§ ACKNOWLEDGEMENT

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

[1]
Yao Ma and Jiliang Tang.
Deep learning on graphs.
Cambridge University Press, 2021.

[2]
Thomas Kipf and Max Welling.
Semi-supervised classification with graph convolutional networks.
ArXiv, abs/1609.02907, 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.
Lightgcn: Simplifying and powering graph convolution network for
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
Drug Discovery Today: Technologies, 37:1–12, 2020.

[8]
Zhaocheng Zhu, Zuobai Zhang, Louis-Pascal Xhonneux, and Jian Tang.
Neural bellman-ford networks: A general graph neural network
framework for link prediction.
Advances in Neural Information Processing Systems,
34:29476–29490, 2021.

[9]
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.

[10]
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro
Lio, Yoshua Bengio, et al.
Graph attention networks.
stat, 1050(20):10–48550, 2017.

[11]
Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang.
Learning from counterfactual links for link prediction.
In International Conference on Machine Learning, pages
26911–26926. PMLR, 2022.

[12]
Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang.
Is homophily a necessity for graph neural networks?
ArXiv, abs/2106.06134, 2021.

[13]
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.

[14]
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann.
Predict then propagate: Graph neural networks meet personalized
In International Conference on Learning Representations, 2018.

[15]
Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian
Simplifying graph convolutional networks.
In International conference on machine learning, pages
6861–6871. PMLR, 2019.

[16]
Tong Zhao, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil
Data augmentation for graph neural networks.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 35, pages 11015–11023, 2021.

[17]
Aseem Baranwal, Kimon Fountoulakis, and Aukosh Jagannath.
Effects of graph convolutions in multi-layer networks.
In The Eleventh International Conference on Learning
Representations, 2023.

[18]
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang,
Xiao-Wen Chang, and Doina Precup.
Revisiting heterophily for graph neural networks.
In Advances in Neural Information Processing Systems.

[19]
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Wei
Finding global homophily in graph neural networks when meeting
In International Conference on Machine Learning, 2022.

[20]
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.

[21]
Benedek Rozemberczki, Carl Allen, and Rik Sarkar.
Multi-scale attributed node embedding.
Journal of Complex Networks, 9(2):cnab014, 2021.

[22]
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher,
and Tina Eliassi-Rad.
Collective classification in network data.
AI magazine, 29(3):93–93, 2008.

[23]
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 arXiv:2005.00687, 2020.

[24]
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang.
Geom-gcn: Geometric graph convolutional networks.
In International Conference on Learning Representations.

[25]
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai
Beyond homophily in graph neural networks: Current limitations and
effective designs.
Advances in Neural Information Processing Systems,
33:7793–7804, 2020.

[26]
Lun Du, Xiaozhou Shi, Qiang Fu, Xiaojun Ma, Hengyu Liu, Shi Han, and Dongmei
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.

[27]
Sitao Luan, Chenqing Hua, Minkai Xu, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang,
Jie Fu, Jure Leskovec, 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.

[28]
Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah.
Graph-less neural networks: Teaching old mlps new tricks via
ArXiv, abs/2110.08727, 2021.

[29]
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Xiao-Wen Chang, and Doina
When do we need gnn for node classification?
arXiv preprint arXiv:2210.16979, 2022.

[30]
Haonan Wang, Jieyu Zhang, Qi Zhu, and Wei Huang.
Augmentation-free graph contrastive learning.
arXiv preprint arXiv:2204.04874, 2022.

[31]
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.10890, 2022.

[32]
Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, and Aukosh
Graph attention retrospective.
arXiv preprint arXiv:2202.13060, 2022.

[33]
Santo Fortunato and Darko Hric.
Community detection in networks: A user guide.
Physics reports, 659:1–44, 2016.

[34]
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.

[35]
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.

[36]
Rongzhe Wei, Haoteng Yin, Junteng Jia, Austin R Benson, and Pan Li.
Understanding non-linearity in graph neural networks from the
bayesian-inference perspective.
In Advances in Neural Information Processing Systems.

[37]
Yoonhyuk Choi, Jiho Choi, Taewook Ko, and Chong-Kwon Kim.
Is signed message essential for graph neural networks?
arXiv preprint arXiv:2301.08918, 2023.

[38]
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.

[39]
Tomer Galanti, András György, and Marcus Hutter.
On the role of neural collapse in transfer learning.
arXiv preprint arXiv:2112.15121, 2021.

[40]
Tomer Galanti, András György, and Marcus Hutter.
Improved generalization bounds for transfer learning via neural
In First Workshop on Pre-training: Perspectives, Pitfalls, and
Paths Forward at ICML 2022, 2022.

[41]
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 on Machine Learning, pages
3090–3122. PMLR, 2022.

[42]
Tomer Galanti, András György, and Marcus Hutter.
Generalization bounds for transfer learning with pretrained
arXiv preprint arXiv:2212.12532, 2022.

[43]
Oriol Vinyals, Charles Blundell, Timothy Lillicrap, Daan Wierstra, et al.
Matching networks for one shot learning.
Advances in neural information processing systems, 29, 2016.

[44]
Jake Snell, Kevin Swersky, and Richard Zemel.
Prototypical networks for few-shot learning.
Advances in neural information processing systems, 30, 2017.

[45]
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.

[46]
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.

[47]
David McAllester.
Simplified pac-bayesian margin bounds.
In Learning Theory and Kernel Machines: 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.

[48]
Andreas Maurer.
A note on the pac bayesian theorem.
arXiv preprint cs/0411099, 2004.

[49]
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.

[50]
Gintare Karolina Dziugaite, Kyle Hsu, Waseem Gharbieh, 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. PMLR, 2021.

[51]
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li.
Simple and deep graph convolutional networks.
In International conference on machine learning, pages
1725–1735. PMLR, 2020.

[52]
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic.
Adaptive universal generalized pagerank graph neural network.
In International Conference on Learning Representations.

[53]
Sami Abu-El-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina
Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan.
Mixhop: Higher-order graph convolutional architectures via sparsified
neighborhood mixing.
In international conference on machine learning, pages 21–29.
PMLR, 2019.

[54]
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, 2020.

[55]
Guohao Li, Matthias Muller, Ali Thabet, and Bernard Ghanem.
Deepgcns: Can gcns go as deep as cnns?
In Proceedings of the IEEE/CVF international conference on
computer vision, pages 9267–9276, 2019.

[56]
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.

[57]
Kenta Oono and Taiji Suzuki.
Graph neural networks exponentially lose expressive power for node
arXiv preprint arXiv:1905.10947, 2019.

[58]
T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra.
A survey on oversmoothing in graph neural networks.
arXiv preprint arXiv:2303.10993, 2023.

[59]
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 on artificial
intelligence, volume 34, pages 3438–3445, 2020.

[60]
Qimai Li, Zhichao Han, and Xiao-Ming Wu.
Deeper insights into graph convolutional networks for semi-supervised
In Proceedings of the AAAI conference on artificial
intelligence, volume 32, 2018.

[61]
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf.
Handling distribution shifts on graphs: An invariance perspective.
arXiv preprint arXiv:2202.02466, 2022.

[62]
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.

[63]
Yizhou Zhang, Guojie Song, Lun Du, Shuwen Yang, and Yilun Jin.
Dane: Domain adaptive network embedding.
International Joint Conference on Artificial Intelligence,
abs/1906.00684:4362–4368, 2019.

[64]
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.

[65]
Shurui Gui, Xiner Li, Limei Wang, and Shuiwang Ji.
Good: A graph out-of-distribution benchmark.
In Thirty-sixth Conference on Neural Information Processing
Systems Datasets and Benchmarks Track.

[66]
Joaquin Quinonero-Candela, Masashi Sugiyama, Anton Schwaighofer, and Neil D
Dataset shift in machine learning.
Mit Press, 2008.

[67]
Jose G Moreno-Torres, Troy Raeder, Rocío Alaiz-Rodríguez, Nitesh V
Chawla, and Francisco Herrera.
A unifying view on dataset shift in classification.
Pattern recognition, 45(1):521–530, 2012.

[68]
Gerhard Widmer and Miroslav Kubat.
Learning in the presence of concept drift and hidden contexts.
Machine learning, 23:69–101, 1996.

[69]
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:2110.03865, 2021.

[70]
Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah.
Empowering graph representation learning with test-time graph
In The Eleventh International Conference on Learning
Representations, 2023.

[71]
Yao Ma, Xiaorui Liu, Tong Zhao, Yozen Liu, Jiliang Tang, and Neil Shah.
A 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.

[72]
Meiqi Zhu, Xiao Wang, Chuan Shi, Houye Ji, and Peng Cui.
Interpreting and unifying graph neural networks with an optimization
In Proceedings of the Web Conference 2021, pages 1215–1226,

[73]
Jonathan Halcrow, Alexandru Mosoi, Sam Ruth, and Bryan Perozzi.
Grale: Designing networks for graph learning.
In Proceedings of the 26th ACM SIGKDD international conference
on knowledge discovery & data mining, pages 2523–2532, 2020.

[74]
Jiong Zhu, Ryan A Rossi, Anup Rao, Tung Mai, Nedim Lipka, Nesreen K Ahmed, and
Danai Koutra.
Graph neural networks with heterophily.
In Proceedings of the AAAI Conference on Artificial
Intelligence, volume 35, pages 11168–11176, 2021.

[75]
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.

[76]
Mingguo He, Zhewei Wei, Hongteng Xu, et al.
Bernnet: Learning arbitrary graph spectral filters via bernstein
Advances in Neural Information Processing Systems,
34:14239–14251, 2021.

[77]
Sannat Singh Bhasin, Vaibhav Holani, and Divij Sanjanwala.
What do graph convolutional neural networks learn?
arXiv preprint arXiv:2207.01839, 2022.

[78]
Oleg Platonov, Denis Kuznedelev, Artem Babenko, and Liudmila Prokhorenkova.
Characterizing graph datasets for node classification: Beyond
homophily-heterophily dichotomy.
arXiv preprint arXiv:2209.06177, 2022.

[79]
Tahleen Rahman, Bartlomiej Surma, Michael Backes, and Yang Zhang.
Fairwalk: Towards fair graph embedding.

[80]
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,

[81]
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.

[82]
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.

[83]
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.

[84]
Alan Mislove, Massimiliano Marcon, Krishna P Gummadi, Peter Druschel, and Bobby
Measurement and analysis of online social networks.
In Proceedings of the 7th ACM SIGCOMM conference on Internet
measurement, pages 29–42, 2007.

[85]
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
Advances in neural information processing systems, 32, 2019.

[86]
Renjie Liao, Raquel Urtasun, and Richard Zemel.
A pac-bayesian approach to generalization bounds for graph neural
arXiv preprint arXiv:2012.07690, 2020.

[87]
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.

[88]
Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner.
The vapnik–chervonenkis dimension of graph and recursive neural
Neural Networks, 108:248–259, 2018.

[89]
Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi.
On provable benefits of depth in training graph convolutional
Advances in Neural Information Processing Systems,
34:9936–9949, 2021.

[90]
Ran El-Yaniv 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
35–49. Springer, 2006.

[91]
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.

[92]
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–268.
Springer, 2022.

[93]
Anthony Sicilia, Xingchen 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
Intervention–MICCAI 2021: 24th International Conference, Strasbourg, France,
September 27–October 1, 2021, Proceedings, Part III 24, pages 560–570.
Springer, 2021.

[94]
Zifan Wang, Nan Ding, Tomer Levinboim, Xi Chen, and Radu Soricut.
Improving robust generalization by direct pac-bayesian bound
arXiv preprint arXiv:2211.12624, 2022.

[95]
Joel A Tropp et al.
An introduction to matrix concentration inequalities.
Foundations and Trends® in Machine Learning,
8(1-2):1–230, 2015.

[96]
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro.
A pac-bayesian approach to spectrally-normalized margin bounds for
neural networks.
arXiv preprint arXiv:1707.09564, 2017.

[97]
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,

[98]
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.

[99]
Jure Leskovec and Andrej Krevl.
Snap datasets: Stanford large network dataset collection, 2014.

[100]
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila
A critical look at the evaluation of GNNs under heterophily: Are we
really making progress?
In The Eleventh International Conference on Learning
Representations, 2023.

[101]
Arpandeep Khatua, Vikram Sharma Mailthody, Bhagyashree Taleka, Tengfei Ma,
Xiang Song, and Wen-mei Hwu.
Igb: Addressing the gaps in labeling, features, heterogeneity, and
size of public graph datasets for deep learning research.
arXiv preprint arXiv:2302.13522, 2023.

[102]
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.

[103]
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
on knowledge discovery & data mining, pages 2847–2856, 2018.

[104]
Yiwei Sun, Suhang Wang, Xianfeng Tang, Tsung-Yu Hsieh, and Vasant Honavar.
Adversarial attacks on graph neural networks via node injections: A
hierarchical reinforcement learning approach.
In Proceedings of the Web Conference 2020, pages 673–683,

[105]
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
on Artificial Intelligence, 2019.

[106]
Simon Geisler, Tobias Schmidt, Hakan Şirin, Daniel Zügner, Aleksandar
Bojchevski, and Stephan Günnemann.
Robustness of graph neural networks at scale.
Advances in Neural Information Processing Systems,
34:7637–7649, 2021.

[107]
Wei Jin, Yaxing Li, Han Xu, Yiqi Wang, Shuiwang Ji, Charu Aggarwal, and Jiliang
Adversarial attacks and defenses on graphs.
ACM SIGKDD Explorations Newsletter, 22(2):19–34, 2021.

[108]
Marcin Waniek, Tomasz P Michalak, Michael J Wooldridge, and Talal Rahwan.
Hiding individuals and communities in a social network.
Nature Human Behaviour, 2(2):139–147, 2018.

[109]
Daniel Zügner and Stephan Günnemann.
Adversarial attacks on graph neural networks via meta learning.
In International Conference on Learning Representations.

[110]
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.

[111]
Kuan Li, Yang Liu, Xiang Ao, and Qing He.
Revisiting graph adversarial attack and defense from a data
distribution perspective.
In The Eleventh International Conference on Learning
Representations, 2023.

[112]
Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and
Jennifer Wortman Vaughan.
A theory of learning from different domains.
Machine learning, 79:151–175, 2010.