Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?

Haitao MaoZhikai ChenWei JinHaoyu HanYao MaTong ZhaoNeil ShahJiliang Tang

article2023NeurIPS58 citations

Reveals why standard Graph Neural Networks systematically fail on minority-pattern nodes through theoretical generalization bounds and empirical evidence, uncovering critical implications for deep architectures and out-of-distribution graph learning.

Listen

Real-world graph datasets frequently contain a mixture of homophilic nodes (where connected nodes share identical labels) and heterophilic nodes (where connected nodes have different labels). Despite this natural structural diversity, standard evaluations of Graph Neural Networks (GNNs) typically assess accuracy globally across the entire graph. This aggregate approach masks severe localized performance drops and assumes that a single model architecture fits all node types equally well.

The article investigates the behavior and generalization limits of GNNs when encountering structural disparity within the same dataset. Specifically, it aims to evaluate why GNNs perform unevenly across different node subgroups and determine whether standard graph architectures can equitably benefit all nodes.

To analyze this phenomenon, the authors conducted empirical evaluations across multiple benchmark datasets, comparing standard GNNs against deeper architectures and feature-only multilayer perceptron (MLP) baselines. They developed a contextual stochastic block model variant to mathematically assess neighborhood aggregation effects. Furthermore, they formulated a non-i.i.d. PAC-Bayesian generalization bound to rigorously quantify the theoretical errors driving subgroup performance gaps.

The article yields four primary findings. First, vanilla GNNs exhibit substantial performance disparity: they excel on majority structural patterns (e.g., homophilic nodes in homophilic graphs) but frequently underperform simple MLP baselines on minority structural patterns. Second, mathematical analysis shows that neighborhood aggregation alters feature representations such that minority nodes are pushed further from training class prototypes, impairing discrimination. Third, the derived generalization bound proves that generalization error is fundamentally governed by the distance in aggregated features and the difference in homophily ratios between training and test nodes. Fourth, deeper GNN architectures mitigate this disparity primarily by capturing higher-order graph structures, where homophily differences between majority and minority nodes progressively narrow.

These findings indicate that relying strictly on overall accuracy creates hidden operational and fairness risks, as model predictions on minority structural subgroups can be highly unreliable. This dynamic also exposes a critical graph structural distribution shift in out-of-distribution (OOD) settings, explaining why standard OOD algorithms often fail when testing on minority structural patterns.

Organizations deploying GNNs should evaluate performance broken down by structural subgroups rather than relying solely on global metrics. When severe structural disparity exists, practitioners should adopt deeper GNN architectures with residual connections or deploy hybrid frameworks that combine feature-centric models with graph convolutions. Researchers addressing out-of-distribution problems must also explicitly account for homophily ratio shifts between training and deployment environments.

The findings are supported by consistent theoretical derivations and empirical results across multiple benchmark networks. However, the theoretical framework relies on idealized contextual stochastic block assumptions and primarily examines linear aggregation. Readers should exercise caution when applying these conclusions to complex graph domains where structural information provides minimal predictive value.

Emory University Michigan State University Rensselaer Polytechnic Institute Snap Inc.disparity disparity map graph neural networks structural disparity graph neural networks heterophilic graphs

arXiv: 2306.01323

Paper: Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs, Jiong Zhu et al. (2020). It establishes why standard GNNs degrade under heterophily and underperform MLPs, providing foundational architectural insights that the source evaluates in the context of localized structural disparity.
Paper: Geom-GCN: Geometric Graph Convolutional Networks, Hongbin Pei et al. (2020). It introduces standard disassortative and heterophilic benchmark datasets alongside geometric aggregation mechanisms to tackle non-homophilous neighborhood aggregation.
Paper: Simple and Deep Graph Convolutional Networks, Ming Chen et al. (2020). It develops deep GCN architectures using initial residual connections and identity mapping to combat over-smoothing, directly motivating the source's findings on deeper architectures for structural disparity.
Paper: Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf et al. (2017). It establishes the foundational first-order localized graph convolutional network framework that serves as the baseline architecture analyzed for subgroup performance failure in the source.
Paper: Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs, Cristian Bodnar et al. (2022). It provides a rigorous mathematical framework linking heterophily and over-smoothing failure modes to neighborhood aggregation dynamics.
Paper: Finding Global Homophily in Graph Neural Networks When Meeting Heterophily, Xiang Li et al. (2022). It explores resolving heterophily limitations by aggregating global structural patterns when local homophily assumptions break down.
Paper: Powerful Graph Convolutional Networks with Adaptive Propagation Mechanism for Homophily and Heterophily, Tao Wang et al. (2022). It investigates how standard propagation mixes conflicting neighbor signals and proposes adaptive propagation across varied homophily levels.
Paper: Learning Causally Invariant Representations for Out-of-Distribution Generalization on Graphs, Yongqiang Chen et al. (2022). It analyzes structural distribution shifts in graph out-of-distribution settings, contextualizing the source's findings on homophily ratio shifts across training and deployment.

Paper: Revisiting Graph-Based Fraud Detection in Sight of Heterophily and Spectrum, Fan Xu et al. (2024). It applies and extends the study of heterophilic neighborhood disparity and spectral filtering to real-world fraud detection scenarios where malicious nodes disguise among legitimate ones.
Paper: Ordered GNN: Ordering Message Passing to Deal with Heterophily and Over-smoothing, Yunchong Song et al. (2023). It develops a hierarchical message-passing architecture to adaptively process disparate homophilic and heterophilic neighborhood distances without over-smoothing.
Paper: Attribute and Structure Preserving Graph Contrastive Learning, Jialu Chen et al. (2023). It extends self-supervised contrastive learning to preserve both attribute similarity and multi-hop structure in networks with non-homophilous node disparities.

Cover for Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?

Abstract

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

Topics

disparity disparity map graph neural networks

Keywords

structural disparity graph neural networks heterophilic graphs homophilic graphs node classification generalization gap disparity score performance disparity largest-margin linear classifier

1 Introduction
2 Prelimaries
3 Effectiveness of GNN on nodes with different structural properties
3.1 How does aggregation affect nodes with structural disparity differently?
3.2 How does Aggregation Contribute to Performance Disparity?
3.3 Why does Performance Disparity Happen? Subgroup Generalization Bound for GNNs
3.4 Performance Disparity Across Node Subgroups on Real-World Datasets
4 Implications of graph structural disparity
4.1 Elucidate the effectiveness of Deeper GNNs
4.2 A new graph out-of-distribution scenario
5 Conclusion & Discussion
6 Acknowledgement
References
Appendix
A Related work
B Investigation on the effectiveness of homophily ratio difference with targeted synthetic edge addition algorithm.
B.1 Targeted heterophilic & homophilic edge addition algorithms
B.2 Detailed experiment results
B.3 Details on the generated graph
C Instance-level discriminative analysis
D Effects of aggregation on nodes in different classes with structural disparity
D.1 Linear separability analysis based on CSBM model
D.2 Linear separability experiment on synthetic CSBM dataset
D.3 Proof details of linear separability within the same pattern
D.4 Proof details of linear separability between different structural patterns
E Proof details of the conditional probability difference for nodes with the same feature but different structural patterns
F Proof details of PAC-Bayes Bound
F.1 Background Knowledge on PAC-Bayes Analysis
F.2 PAC-Bayesian Analysis on Subgroup Generalization bound of Deterministic classifier
F.3 Proof details of Expected Loss Discrepancy
F.4 Proof details of subgroup generalization Bound for GNNs
G Experiment details
G.1 Hardware & Software Environment
G.2 Model details & hyperparameter settings & results
G.3 Dataset details
G.4 OOD dataset statistics and details
H Additional results on performance comparison between GCN and MLP-based models
I Additional results on performance comparison between GCN and deeper GNN models
J Additional Experiment on performance disparity across subgroups
J.1 Additional investigation on higher-order neighborhood
J.2 Additional results on more datasets
K Additional investigation on the discriminative ability of GCN
L Significant test between GCN and MLP-based models
M Significant test between GCN and deeper GNN models
N Limitation
O Broader Impact
P Future work

Knowls

Knowl 1 — Subgroup Generalization Bound for Graph Neural Networks under Structural Disparity
theoretical result
Let a graph $G = (V, E)$ be partitioned into a training node set $V_{tr}$ of size $N_{tr} = |V_{tr}|$ with node homophily ratio $h_{tr}$ , and $M$ test node subgroups $V_1, \dots, V_M$ , where subgroup $V_m$ has homophily ratio $h_m$ . Let the graph data follow a generalized Contextual Stochastic Block Model with Structural Disparity (CSBM-S) with $K$ classes, class feature mean separation $\rho = \|\mu_1 - \mu_2\|_2$ , and feature variance $\sigma^2 I$ . Let $\tilde{h}$ be a deterministic classifier consisting of a one-hop mean aggregation $g(X, G) = D^{-1}AX$ followed by an $L$ -layer ReLU-activated MLP $f(g_i(X, G); W_1, \dots, W_L)$ with maximum hidden layer width $b$ and bounded layer spectral norms $\|W_l\|_F \le C$ .

Let $\epsilon_m = \max_{j \in V_m} \min_{i \in V_{tr}} \|g_i(X, G) - g_j(X, G)\|_2$ denote the maximum aggregated feature distance from subgroup $V_m$ to $V_{tr}$ , and let $B_m = \max_{i \in V_{tr} \cup V_m} \|g_i(X, G)\|_2$ . For any margin $\gamma \ge 0$ , probability confidence parameter $\delta \in (0, 1)$ , and constant $\alpha \in (0, 1/4)$ , the expected 0-margin classification loss $\mathcal{L}^0_m(\tilde{h})$ on test subgroup $V_m$ is bounded with probability at least $1 - \delta$ over training labels by the empirical $\gamma$ -margin training loss $\widehat{\mathcal{L}}^\gamma_{tr}(\tilde{h})$ on $V_{tr}$ :

$\mathcal{L}^0_m(\tilde{h}) \le \widehat{\mathcal{L}}^\gamma_{tr}(\tilde{h}) + \mathcal{O}\left( \frac{K\rho}{\sqrt{2\pi}\sigma}(\epsilon_m + |h_{tr} - h_m|\rho) + \frac{b\sum_{l=1}^L \|W_l\|_F^2}{(\gamma/8)^{2/L} N_{tr}^\alpha} (\epsilon_m)^{2/L} + R \right)$

where the vanishing term $R$ is defined as:

$R = \frac{1}{N_{tr}^{1-2\alpha}} + \frac{1}{N_{tr}^{2\alpha}}\ln\left(\frac{LC(2B_m)^{1/L}}{\gamma^{1/L}\delta}\right)$

This bound demonstrates that GNN generalization error on a test subgroup increases directly with both the aggregated feature distance $\epsilon_m$ and the homophily ratio discrepancy $|h_{tr} - h_m|$ relative to the training set.

Knowl 2 — Benchmark and Evaluation under Graph Structural Out-of-Distribution Shift

data/table

Graph structural disparity induces a concept shift where the conditional label distribution given aggregated features differs between homophilic and heterophilic nodes: $P(Y \mid X_{\text{homo}}) \neq P(Y \mid X_{\text{hete}})$ . To evaluate models under this shift, an out-of-distribution (OOD) split is constructed by allocating majority structural pattern nodes ( $h_i > 0.5$ for homophilic datasets, $h_i \le 0.5$ or $h_i < 0.4$ for heterophilic datasets) to training (80%) and validation (20%), while reserving minority structural pattern nodes entirely for testing.

Model	PubMed	Ogbn-Arxiv	Squirrel	Chameleon
GCN (i.i.d.)	89.18 $\pm$ 0.15	72.99 $\pm$ 0.14	58.09 $\pm$ 0.71	75.09 $\pm$ 0.79
GCN	51.04 $\pm$ 0.16	34.94 $\pm$ 0.07	32.13 $\pm$ 4.93	43.35 $\pm$ 3.47
MLP	68.38 $\pm$ 0.43	33.17 $\pm$ 0.37	24.57 $\pm$ 0.77	34.78 $\pm$ 4.97
GLNN	67.51 $\pm$ 0.25	35.89 $\pm$ 0.14	31.51 $\pm$ 0.70	47.01 $\pm$ 1.09
GCNII	67.76 $\pm$ 0.36	36.81 $\pm$ 0.14	37.15 $\pm$ 1.39	41.25 $\pm$ 2.03
GPRGNN	57.24 $\pm$ 0.18	34.95 $\pm$ 0.43	42.43 $\pm$ 7.71	35.27 $\pm$ 7.67
SRGNN	57.91 $\pm$ 0.10	40.37 $\pm$ 1.65	37.62 $\pm$ 1.74	42.09 $\pm$ 0.43
EERM	65.37 $\pm$ 1.35	34.23 $\pm$ 0.46	40.93 $\pm$ 0.57	45.84 $\pm$ 1.05
EERM(II)	67.59 $\pm$ 0.91	40.28 $\pm$ 0.84	44.31 $\pm$ 0.40	48.59 $\pm$ 0.78

The table reports test accuracy (mean $\pm$ standard deviation across 10 random seeds). The results establish four key behaviors: (1) standard GCN suffers severe accuracy degradation under the structural OOD split compared to an identical-size i.i.d. split; (2) structure-agnostic MLPs and deeper GNNs (GCNII, GPRGNN) consistently surpass vanilla GCN on minority test nodes; (3) conventional graph OOD methods with vanilla GCN backbones (SRGNN, EERM) struggle to resolve the concept shift; and (4) equipping OOD algorithms with deeper architectures, as in EERM(II) with a GCNII backbone, substantially improves performance across all datasets.

Knowl 3 — Contextual Stochastic Block Model with Structural Disparity
definition
The Contextual Stochastic Block Model with Structural Disparity (CSBM-S), parameterized as $\text{CSBM-S}(\mu_1, \mu_2, (p^{(1)}, q^{(1)}), (p^{(2)}, q^{(2)}), \text{Pr}(\text{homo}))$ , models graph-structured data where nodes within the same class coexist in distinct homophilic and heterophilic structural patterns.

Nodes belong to two disjoint class sets $C_1$ and $C_2$ . Original node features $x \in \mathbb{R}^d$ are sampled from $\mathcal{N}(\mu_1, I)$ for $C_1$ and $\mathcal{N}(\mu_2, I)$ for $C_2$ , with class mean separation $\rho = \|\mu_1 - \mu_2\|_2$ . Each class $C_i$ is partitioned into two structural subgroups:
1. Homophilic subgroup $C_i^{(1)}$ with probability $\text{Pr}(\text{homo})$ , where intra-class edge connection probability $p^{(1)}$ and inter-class connection probability $q^{(1)}$ satisfy $p^{(1)} > q^{(1)}$ .
2. Heterophilic subgroup $C_i^{(2)}$ with probability $1 - \text{Pr}(\text{homo})$ , where intra-class probability $p^{(2)}$ and inter-class probability $q^{(2)}$ satisfy $p^{(2)} < q^{(2)}$ .
All nodes share the same expected degree distribution such that $p^{(1)} + q^{(1)} = p^{(2)} + q^{(2)}$ .

The generalized CSBM-S model extends this definition to $M$ node subgroups $V_m \sim \text{CSBM}(\mu_1, \mu_2, p^{(m)}, q^{(m)})$ , where all subgroups share identical class feature distributions and degree sums $p^{(m)} + q^{(m)}$ , but exhibit different homophily levels determined by $(p^{(m)}, q^{(m)})$ .
Knowl 4 — Posterior Label Probability Discrepancy under Aggregated Feature and Homophily Disparity
theoretical result
Under the Contextual Stochastic Block Model with Structural Disparity (CSBM-S) with balanced class priors $P(Y = c_1) = P(Y = c_2) = 0.5$ and isotropic aggregated feature variance $\sigma^2 I$ , let node $u$ belong to structural pattern $(p^{(1)}, q^{(1)})$ with homophily ratio $h_u = \frac{p^{(1)}}{p^{(1)} + q^{(1)}}$ and aggregated feature $f_u = D^{-1}AX|_u$ . Let node $v$ belong to structural pattern $(p^{(2)}, q^{(2)})$ with homophily ratio $h_v = \frac{p^{(2)}}{p^{(2)} + q^{(2)}}$ and aggregated feature $f_v = D^{-1}AX|_v$ .

If the distance between aggregated features satisfies $\|f_u - f_v\|_2 \le \epsilon$ , the discrepancy between the conditional posterior class probabilities of node $u$ and node $v$ for class $c_1$ satisfies:

$|P_1(y_u = c_1 \mid f_u) - P_2(y_v = c_1 \mid f_v)| \le \frac{\rho}{\sqrt{2\pi}\sigma} (\epsilon + |h_u - h_v|\rho)$

where $\rho = \|\mu_1 - \mu_2\|_2$ is the original class feature mean distance. When $f_u = f_v$ (i.e., $\epsilon = 0$ ), the bound simplifies to:

$|P_1(y_u = c_1 \mid f_u) - P_2(y_v = c_1 \mid f_v)| \le \frac{\rho^2}{\sqrt{2\pi}\sigma} |h_u - h_v|$

This indicates that two nodes exhibiting identical or proximate aggregated features can have substantially different posterior class probabilities if their local homophily ratios differ.
Knowl 5 — Linear Separability Conditions under Structural Disparity
theoretical result
Under the Contextual Stochastic Block Model with Structural Disparity (CSBM-S), the aggregated feature vector $f_i = D^{-1}AX|_i$ of node $i$ with degree $d_i$ in class $c_k$ and subgroup $j$ follows $\mathcal{N}\left(\frac{p^{(j)}\mu_k + q^{(j)}\mu_{3-k}}{p^{(j)} + q^{(j)}}, \frac{1}{d_i}I\right)$ . Evaluating the optimal maximum-margin linear classifier reveals a disparity in feature separability improvements:
1. Intra-pattern classification: For nodes belonging to different classes within the same structural pattern $j$ , the linear classifier on aggregated features $f_i$ achieves a strictly lower misclassification probability than on raw node features $x_i$ if and only if node degree satisfies:
$d_i > \frac{(p^{(j)} + q^{(j)})^2}{(p^{(j)} - q^{(j)})^2}$
1. Inter-pattern classification: For nodes belonging to different classes from different structural patterns (e.g., node $i \in C_1$ with pattern $(p^{(1)}, q^{(1)})$ and node $j \in C_2$ with pattern $(p^{(2)}, q^{(2)})$ ), the linear classifier on aggregated features achieves lower misclassification error than on raw features if and only if:
$d_i > \frac{(p^{(1)} + q^{(1)})^2}{(p^{(1)} - q^{(2)})^2}$

Because $|p^{(1)} - q^{(2)}| < |p^{(1)} - q^{(1)}|$ when $p^{(1)} > q^{(1)}$ and $p^{(2)} < q^{(2)}$ , the degree requirement for separating inter-pattern classes is orders of magnitude higher (e.g., $d_i > 1.75$ for intra-pattern vs. $d_i > 100$ for inter-pattern when $p^{(1)}=0.9, q^{(1)}=0.1, p^{(2)}=0.2, q^{(2)}=0.8$ ), showing that aggregation fails to improve linear separability across mixed structural patterns under realistic node degrees.
Knowl 6 — Empirical Performance Disparity of GCN versus Structure-Agnostic Baselines
empirical result
Evaluating vanilla GCN against structure-agnostic models—standard Multi-Layer Perceptrons (MLP) and distilled Graph-less Neural Networks (GLNN)—across test node subgroups binned by node homophily ratio $h_i = \frac{|\{u \in \mathcal{N}(v_i) : y_u = y_{v_i}\}|}{d_i} \in [0, 1]$ reveals a consistent performance disparity:
1. In homophilic datasets (PubMed with graph homophily $h=0.79$ , Ogbn-arxiv with $h=0.63$ , Cora with $h=0.81$ , CiteSeer with $h=0.71$ , and IGB-tiny with $h=0.58$ ), GCN outperforms MLP and GLNN on majority homophilic nodes ( $h_i \in [0.6, 1.0]$ ), but MLP and GLNN significantly outperform GCN on minority heterophilic nodes ( $h_i \in [0.0, 0.4]$ ).
2. In heterophilic datasets (Squirrel with $h=0.25$ , Twitch-gamers with $h=0.56$ , and Amazon-ratings with $h=0.38$ ), GCN outperforms MLP and GLNN on majority heterophilic nodes ( $h_i \in [0.0, 0.4]$ ), while MLP-based models outperform GCN on minority homophilic nodes ( $h_i \in [0.6, 1.0]$ ).
Thus, overall graph-level GNN accuracy masks systematic failure on minority structural patterns, where neighborhood aggregation actively degrades performance relative to feature-only models.
Knowl 7 — Mechanism of Deeper GNN Superiority via Higher-Order Homophily Discrepancy Reduction
empirical result
Evaluating deeper GNN architectures designed to avoid over-smoothing—including GCNII, APPNP, and GPRGNN—against standard 2-layer GCN across node homophily subgroups reveals that their overall accuracy gains stem specifically from substantial improvements on minority structural subgroups (heterophilic nodes in homophilic graphs, and homophilic nodes in heterophilic graphs), accompanied by slight accuracy trade-offs on majority subgroups.

This behavior is explained by the convergence of higher-order neighborhood homophily. Defining the $k$ -hop homophily ratio of node $u$ as $h^{(k)}_u = \frac{|\{w \in \mathcal{N}_k(u) : y_w = y_u\}|}{|\mathcal{N}_k(u)|}$ , tracking the difference $|h^{(k)}_u - h^{(k)}_v|$ between minority test nodes $u$ and their nearest training nodes $v$ across hops $k \in \{1, 2, 3, 4, 5\}$ demonstrates a monotonic decline in homophily discrepancy as $k$ increases across PubMed, Ogbn-arxiv, Squirrel, and Chameleon. By expanding the receptive field, deeper GNNs diminish the effective structural disparity between training nodes and minority test nodes.
Knowl 8 — Monotonic Performance Degradation with Composite Node Disparity Score
empirical result
To empirically validate the subgroup generalization bound, test nodes $u \in V_{te}$ are ranked by a composite disparity score $s_u$ relative to the training set $V_{tr}$ using 2-hop aggregated features $F^{(2)} = (\tilde{D}^{-1}\tilde{A})^2 X$ (where $\tilde{A} = A + I, \tilde{D} = D + I$ ) and 2-hop node homophily ratios $h^{(2)}$ :

$s_u = \|F^{(2)}_u - F^{(2)}_v\|_2 + |h^{(2)}_u - h^{(2)}_v| \quad \text{where} \quad v = \arg\min_{w \in V_{tr}} \|F^{(2)}_u - F^{(2)}_w\|_2$

Partitioning test nodes into 5 equal-sized bins based on ascending values of $s_u$ demonstrates a strict, monotonic degradation in classification accuracy from subgroup 1 (lowest disparity) to subgroup 5 (highest disparity) across diverse GNN architectures (GCN, SGC, GAT, GCNII, GPRGNN) on PubMed, Ogbn-arxiv, Chameleon, Squirrel, Cora, CiteSeer, IGB-tiny, and Amazon-ratings.

Ablating the score shows that sorting by aggregated feature distance alone or homophily difference alone produces non-monotonic fluctuations in subgroups 1–3, confirming that both feature distance and homophily difference jointly drive subgroup performance degradation.
Knowl 9 — Targeted Synthetic Edge Addition for Controlled Structural Disparity
algorithm
The targeted edge addition algorithms controllably manipulate the homophily ratio on a targeted node subset $V_{\text{targeted}} \subseteq V$ by introducing $K$ synthetic edges while preserving the graph structure and homophily of non-targeted nodes.

For homophilic edge addition, pairs of nodes within $V_{\text{targeted}}$ sharing the same label are connected. For heterophilic edge addition, neighboring labels are sampled from a target label distribution $\mathcal{D}_{y_i}$ defined for each class.
Input: Graph $G = (V, E)$ , targeted node set $V_{\text{targeted}} \subseteq V$ , budget $K$ , class sets $\{V_c\}_{c=0}^{|C|-1}$ , label distribution $\{\mathcal{D}_c\}_{c=0}^{|C|-1}$
Output: Modified graph $G' = (V, E')$
$E' \leftarrow E$
$k \leftarrow 1$
while $k \le K$ do
    sample node $i \sim \text{Uniform}(V_{\text{targeted}})$
    obtain label $y_i$ of node $i$
    if Homophilic_Mode then
        sample node $j \sim \text{Uniform}(V_{y_i} \cap V_{\text{targeted}})$
    else if Heterophilic_Mode then
        sample label $c \sim \mathcal{D}_{y_i}$
        sample node $j \sim \text{Uniform}(V_c \cap V_{\text{targeted}})$
    end if
    if $(i, j) \notin E'$ then
         $E' \leftarrow E' \cup \{(i, j)\}$
         $k \leftarrow k + 1$
    end if
end while
return $G' = (V, E')$
Incrementally increasing the edge permutation ratio $K / K_{\text{max}}$ on Cora (with heterophilic edge addition) and Squirrel (with homophilic edge addition) causes monotonic drops in GCN test accuracy exclusively on the perturbed target sets, isolating homophily ratio discrepancy as a causal driver of performance degradation.
Knowl 10 — Assumptions and Limitations of GNN Structural Disparity Analysis
limitation
The theoretical and empirical analysis of GNN structural disparity possesses several stated boundaries:
1. Feature Distribution Assumption: Theoretical guarantees rely on the generalized CSBM-S model where node features within each class follow isotropic Gaussian distributions with independent dimensions, which abstracts away arbitrary real-world feature dependencies.
2. Architecture Scope in Theory: The non-i.i.d. PAC-Bayes bound is derived specifically for one-hop mean aggregation followed by an $L$ -layer MLP (SGC architecture); theoretical extension to multi-layer message-passing networks with non-linearities between aggregation steps is established empirically rather than through formal multi-layer PAC-Bayes bounds.
3. Graph Directionality: Homophily metrics and derivations assume undirected graphs; the behavior of structural disparity on directed graphs remains uncharacterized.
4. Informational Utility of Graph Structure: On datasets where graph structure provides negligible task-relevant information (such as the Actor co-occurrence network, where an MLP outperforms all GNNs), the homophily-driven disparity patterns and disparity score correlations do not consistently hold.

Coverage note — None was omitted; all key theoretical derivations, empirical findings, algorithms, benchmark formulations, and limitations from the paper and its appendix were synthesized into standalone knowls.

References

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 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-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.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):10–48550, 2017.
12.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.
13.Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily a necessity for graph neural networks? ArXiv, abs/2106.06134, 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–6871. 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 Representations, 2023.
19.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.
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 Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Networks, 9(2):cnab014, 2021.
23.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.
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 arXiv:2005.00687, 2020.
25.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.
26.Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in Neural Information Processing Systems, 33: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-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.
29.Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old mlps new tricks via distillation. ArXiv, abs/2110.08727, 2021.
30.Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Xiao-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-free graph contrastive learning. arXiv preprint arXiv:2204.04874, 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.10890, 2022.
33.Kimon Fountoulakis, Amit Levi, Shenghao Yang, Aseem Baranwal, and Aukosh Jagannath. Graph attention retrospective. arXiv preprint arXiv:2202.13060, 2022.
34.Santo Fortunato and Darko Hric. Community detection in networks: A user guide. Physics reports, 659:1–44, 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 bayesian-inference perspective. In Advances in Neural Information Processing Systems.
38.Yoonhyuk Choi, Jiho Choi, Taewook Ko, and Chong-Kwon Kim. Is signed message essential for graph neural networks? arXiv preprint arXiv:2301.08918, 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.15121, 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 on Machine Learning, pages 3090–3122. PMLR, 2022.
43.Tomer Galanti, András György, and Marcus Hutter. Generalization bounds for transfer learning with pretrained classifiers. arXiv preprint arXiv:2212.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 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.
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 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.
52.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.
53.Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations.
54.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.
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, 2020.
56.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.
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 arXiv:1905.10947, 2019.
59.T Konstantin Rusch, Michael M Bronstein, and Siddhartha Mishra. A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993, 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 on artificial intelligence, volume 34, pages 3438–3445, 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 arXiv:2202.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–27977, 2021.
64.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.
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-distribution 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.00955, 2021.
68.Joaquin Quinonero-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-Rodríguez, 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:2110.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. In The Eleventh International Conference on Learning Representations, 2023.
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. Reinforcement subgraph reasoning for fake news detection. In Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 2253–2262, 2022.
75.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.
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 networks for graph learning. In Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining, pages 2523–2532, 2020.
78.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.
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, 34:14239–14251, 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. Characterizing graph datasets for node classification: Beyond homophily-heterophily 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 convoltuional 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 Bhattacharjee. Measurement and analysis of online social networks. In Proceedings of the 7th ACM SIGCOMM conference on Internet measurement, pages 29–42, 2007.
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-bayesian approach to generalization bounds for graph neural networks. arXiv preprint arXiv:2012.07690, 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–chervonenkis dimension of graph and recursive neural networks. Neural Networks, 108:248–259, 2018.
93.Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. Advances in Neural Information Processing Systems, 34:9936–9949, 2021.
94.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.
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–268. Springer, 2022.
97.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.
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 A Tropp et al. An introduction to matrix concentration inequalities. 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 spectrally-normalized margin bounds for neural networks. arXiv preprint arXiv:1707.09564, 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 really making progress? In The Eleventh International Conference on Learning Representations, 2023.
105.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.
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 (llms) in learning on graphs. arXiv preprint arXiv:2307.03393, 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 on knowledge discovery & data mining, pages 2847–2856, 2018.
109.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, 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 on Artificial Intelligence, 2019.
111.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.
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 a 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. In 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 Jennifer Wortman Vaughan. A theory of learning from different domains. Machine learning, 79:151–175, 2010.

Citation

MLA

Mao, H., et al. “Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?”. Advances in Neural Information Processing Systems, vol. 36, 2023, pp. 37013–67, https://proceedings.neurips.cc/paper_files/paper/2023/file/74f1edadbdf495e7258ee8db7b1d3acd-Paper-Conference.pdf.

APA

Mao, H., Chen, Z., Jin, W., Han, H., Ma, Y., Zhao, T., Shah, N., & Tang, J. (2023). Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?. Advances in Neural Information Processing Systems, 36, 37013–37067. https://proceedings.neurips.cc/paper_files/paper/2023/file/74f1edadbdf495e7258ee8db7b1d3acd-Paper-Conference.pdf

Chicago

Mao, H., Z. Chen, W. Jin, et al. 2023. “Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?”. Advances in Neural Information Processing Systems 36: 37013–67. https://proceedings.neurips.cc/paper_files/paper/2023/file/74f1edadbdf495e7258ee8db7b1d3acd-Paper-Conference.pdf.

Harvard

Mao, H. et al. (2023) “Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 37013–37067. Available at: https://proceedings.neurips.cc/paper_files/paper/2023/file/74f1edadbdf495e7258ee8db7b1d3acd-Paper-Conference.pdf.

Vancouver

1. Mao H, Chen Z, Jin W, Han H, Ma Y, Zhao T, Shah N, Tang J (2023) Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 37013–37067

BibTeX

@inproceedings{mao2023demystifying,
  title = {Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?},
  author = {Mao, Haitao and Chen, Zhikai and Jin, Wei and Han, Haoyu and Ma, Yao and Zhao, Tong and Shah, Neil and Tang, Jiliang},
  year = {2023},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {36},
  pages = {37013-37067},
  url = {https://proceedings.neurips.cc/paper_files/paper/2023/file/74f1edadbdf495e7258ee8db7b1d3acd-Paper-Conference.pdf}
}

Metadata:DOI registry

Access the Paper

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

Open PDF

License: Authors

Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Subgroup Generalization Bound for Graph Neural Networks under Structural Disparity

Knowl 2 — Benchmark and Evaluation under Graph Structural Out-of-Distribution Shift

Knowl 3 — Contextual Stochastic Block Model with Structural Disparity

Knowl 4 — Posterior Label Probability Discrepancy under Aggregated Feature and Homophily Disparity

Knowl 5 — Linear Separability Conditions under Structural Disparity

Knowl 6 — Empirical Performance Disparity of GCN versus Structure-Agnostic Baselines

Knowl 7 — Mechanism of Deeper GNN Superiority via Higher-Order Homophily Discrepancy Reduction

Knowl 8 — Monotonic Performance Degradation with Composite Node Disparity Score

Knowl 9 — Targeted Synthetic Edge Addition for Controlled Structural Disparity

Knowl 10 — Assumptions and Limitations of GNN Structural Disparity Analysis

References

Citation

BibTeX

Access the Paper