GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation
Authors: Mingxuan Ju
Tong Zhao
Wenhao Yu
Neil Shah
Yanfang Ye
Venue: NeurIPS 2023 poster (2023)
Keywords: Graph neural network
Test-time Augmentation
TL;DR: We propose GraphPatcher, a novel test-time augmentation framework that mitigates the degree bias problem for graph neural networks.

Abstract: Recent studies have shown that graph neural networks (GNNs) exhibit strong biases towards the node degree: they usually perform satisfactorily on high-degree nodes with rich neighbor information but struggle with low-degree nodes. Existing works tackle this problem by deriving either designated GNN architectures or training strategies specifically for low-degree nodes. Though effective, these approaches unintentionally create an artificial out-of-distribution scenario, where models mainly or even only observe low-degree nodes during the training, leading to a downgraded performance for high-degree nodes that GNNs originally perform well at. In light of this, we propose a test-time augmentation framework, namely GraphPatcher, to enhance test-time generalization of any GNNs on low-degree nodes. Specifically, GraphPatcher iteratively generates virtual nodes to patch artificially created low-degree nodes via corruptions, aiming at progressively reconstructing target GNN's predictions over a sequence of increasingly corrupted nodes. Through this scheme, GraphPatcher not only learns how to enhance low-degree nodes (when the neighborhoods are heavily corrupted) but also preserves the original superior performance of GNNs on high-degree nodes (when lightly corrupted). Additionally, GraphPatcher is model-agnostic and can also mitigate the degree bias for either self-supervised or supervised GNNs. Comprehensive experiments are conducted over seven benchmark datasets and GraphPatcher consistently enhances common GNNs' overall performance by up to 3.6% and low-degree performance by up to 6.5%, significantly outperforming state-of-the-art baselines. The source code is publicly available at https://github.com/jumxglhf/GraphPatcher.

GRAPHPATCHER: Mitigating Degree Bias for
Graph Neural Networks via Test-time Augmentation
Mingxuan Ju', Tong Zhao?, Wenhao Yu', Neil Shah?, Yanfang Ye!
University of Notre Dame, SSna Inc. wyu1, and. edu; {[tzhao (ttzhao,nshah mswaahessapp...... @snap.
Abstract
Recent studies have shown that graph neural networks (GNNs) exhibit strong biases towards the node degree: they usually perform satisfactorily on high-degree nodes with rich neighbor information but struggle with low-degree nodes. Existing works tackle this problem by deriving either designated GNN architectures or training strategies specifically for low-degree nodes. Though effective, these approaches un- intentionally create an artificial -ittrf-disttibuttion scenario, where models mainly or even only observe low-degree nodes during the training, leading to downgraded performance for high-degree nodes that GNNs originally perform well at. In light of this, propose test-time augmentation framework, namely GRAPHPATCHER, to enhance test-time generalization of any GNNs on low-degree nodes. Specifically, GRAPHPATO CHER iteratively generates virtual nodes to patch artificially created low-degree nodes via corruptions, aiming at progressively reconstructing target GNN's predictions over sequence of increasingly corrupted nodes. Through this scheme, GRAPHPATCHER not only learns how to enhance low- low-degree nodes (when the neighborhoods are heavily corrupted) but also preserves the original superior performance of GNNs on high-degree nodes (when lightly corrupted). Additionally, GRAPHPATCHER is model-agnostic and also mitigate the degree bias for either self-supervised or supervised GNNs. Comprehensive experiments are conducted over seven benchmark datasets and GRAPUPATCHER consistently enhances com- mon GNNs' overall performance by up to 3.6% and low-degree performance by up 6.5%, significantly outperforming state-of-the-art baselines. The source code is publicly available at https: //tpthgttttt/tt//// com/ jumxglhf/ hattt//raaaPaaahaaece
Introduction
Graph Neural Networks (GNNs) have gained significant popularity as a powerful approach for learning representations of graphs, achieving state-of-the-art performance various predictive tasks, such as node classification [22, 38, 9], link prediction [50, 53], and graph classification [43, 47, 11]. These tasks further form the archetypes of many real-world applications, such recommendation systems [45, 3], predicative user behavior models [31, 52], and molecular property prediction [51, 48).
While existing GNNs are highly proficient at capturing information from rich neighborhoods (i.e., high-degree nodes), recent studies [13, 25, 36, 55] have revealed a significant performance degradation of GNNs when dealing with nodes that have sparse neighborhoods (i.e., low-degree nodes). This observation can attributed to the fact that GNNs make predictions based on the distribution of node neighborhoods [27]. According to this line of theory, GNNs struggle with low-degree nodes due to the limited amount of available neighborhood information, which may not able to precisely depict the learned distributions. Empirically, as shown in Figure 1, the classification accuracy of GCN [22] proportionally decays as the node degree decreases, resulting in a performance gap of ~00% accuracy. Furthermore, the sub-optimal performance of GNNs on low-degree nodes can be
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Node Degree vs. Accuracy across SoTA
Graph: Cora
Graph: Citeseer
Acc. (%))
of Nodes
Acc (%)
of Nodes
6001
10
GCN Overall
350
250
75
GCN Overay
400
2001
70
1-2
3-4
5-6
9-10
1-2
3-4
5-6
1-8
9-10
Degree
Degree
GCN
Up
Tail-GNN
GraphPatcher ColdBrew # of Nodes
Figure 1: The classification accuracy of GCN and SoTA frameworks that mitigate degree biases.
aggravated by the power-law degree distribution commonly observed in real-world graphs, where the number of low-degree nodes significantly exceeds that of high-degree nodes [36].
To bridge this gap, several frameworks have been proposed to specifically improve GNNs' perfor- mance on low-degree nodes [36, 25, 13, 55, 49]. These frameworks either introduce designated architectures training strategies specifically for low-degree nodes. For examples, Tail-GNN [25] enhances latent representations of low-degree nodes by incorporating high-degree structural infor- mation; whereas Coldbrew [55] retrieves set of existing nodes virtual neighbors for low-degree nodes. However, these approaches suffer from two significant drawbacks. Firstly, while benefiting low-degree nodes, they inadvertently create an artificial out-of-distribution scenario during train- ing [42], where models primarily observe low-degree nodes, leading to a downgraded performance for high-degree nodes that GNNs originally perform well on. Secondly, deploying these frameworks often requires changing model architectures, which can be impractical in real-world scenarios where the original models are well-trained due the expensive re-training cost (on large-scale graphs) and the shared usage of it across different functionalities in production.
In light of these drawbacks, propose test-time augmentation framework for GNNs, namely GRAPHPATCHER. Given a well-trained GNN, GRAPHPATCHER mitigates the degree bias by patching comupted ego-graphs with multiple generated virtual neighbors. Notably, GRAPHPATCHER not only enhances the performance of low-degree nodes but also maintains (sometimes improves) GNNs performance on high-degree nodes. This behavior is empirically important because practitioners can universally apply GRAPHPATCHER to all nodes without, like previous works, manually discovering a degree threshold that differentiates the low- and high-degree nodes. To achieve so, we first generate a sequence of ego-graphs corrupted with increasing strengths. Then, GRAPHPATCHER recursively generates multiple virtual nodes patch the mostly corrupted graph, such that the frozen GNN gives similar predictions for the patched graph and the corresponding corrupted ego-graph in the sequence. Through this scheme, GRAPHPATCHER not only learns how to patch low-degree nodes (i.e., heavily corrupted) but also maintains GNNs original superior performance on high-degree nodes (i.e., lightly corrupted). As test-time augmentation framework, GRAPHPATCHER is parameterized in parallel with the target GNN. Hence, GRAPUPATCING is model-agnostic and requires no updates on the target GNN, enabling practitioners to easily utilize as a plug-and-pla module to existing well-established infrastructures. Overall, our contributions are summarized as:
We study a more practical setting of degree biases on graphs, where both the performances on low- and high-degree nodes considered. In this case, good framework is required to not only improve the performance over low-degree nodes but also maintain the original superior performance over high-degree nodes. We evaluate existing frameworks in this setting and observe that many of them trade off performance on high-degree nodes for that on low-degree nodes.
To mitigate degree biases, we propose GRAPHPATCHER, a novel test-time augmentation framework for graphs. Given a well-trained GNN, GRAPUPATCHER iteratively generates multiple virtual nodes and uses them to patch the original ego-graphs. These patched ego-graphs not only improve GNNs' performance on low-degree nodes but also maintains that over high-degree nodes. Moreover, GRAPHPATCHER is applied at the testing time for GNNs, plug-and- and-play module that is easily applicable existing well-established infrastructures.
We conduct extensive evaluation of GRAPHPATCHER along with six state-of-the-art frameworks that mitigate degree biases on seven benchmark datasets. GRAPHPATCHER consistently enhances the overall performance by up to 3.6% and low-degree performance by up to 6.5% of multiple GNNs, significantly outperforming sate-of-the-art basclines.

---

2 Related Works
Graph Neural Networks. Graph Neural Networks (GNNs) have become one of the most popular paradigms for learning representations over graphs [22, 38, 9, 43, 23, 17, 4]. GNNs aim at mapping the input nodes into low-dimensional vectors, which can be further utilized to conduct either graph- level or node-level tasks. Most GNNs explore a layer-wise message passing scheme, where a node iteratively extracts information from its first-order neighbors, and information from multi-hop neighbors can be captured by stacked layers. They achieved state-of-the-art performance on various tasks, such node classification [22, 44, 12, 35], link prediction [50, 53, 8), node clustering [2, 37], etc. These tasks further form the archetypes of many real-world applications, such as recommendation systems [45, 31, predictive user behavior models [31, 52], question answering [18], and molccular property prediction [51, 48, 7, 24].
Degree Bias underlying GNNs. Recent studies have shown that GNNs exhibit strong biases towards the node degree: they usually perform satisfactorily over high-degree nodes with rich neighbor information but suffer over low-degree nodes [13, 25, 36, 55]. Existing frameworks that mitigate degree biases derive either designated architectures or training strategies specifically for low-degree nodes. For instance, Tail-GNN [25] enhances low-degree nodes' latent representations by injecting high-degree structural information learned from high-degree nodes; Coldbrew [55] retrieves a set of existing nodes virtual neighbors for low-degree nodes; Tune [13] fine-tunes the well-trained GNNs with pseudo labels and heavily corrupted graphs. Though effective for low-degree nodes, they unintentionally create an artificial out-o--distribution scenario [42], where models only observe low-degree nodes during the training, leading to downgraded performance for high-degree nodes that GNNs originally perform well at.
Test-time Augmentation. While data augmentations during the training phase have become one of the essential ingredients for training machine learning models [54], the augmentation applied during the testing time is far less studied, especially for the graph learning community. It has been moderately researched in the computer vision field, aimed at improving performance or mitigating uncertainties [34, 21, 41, 1]. They usually corrupt the same sample by different augmentation approaches and aggregate the model's predictions on all corrupted samples. Whereas in the graph community, GTrans [15] proposes a test-time enhancement framework, where the node feature and graph topology are modified at the test time to mitigate potential -uioo--distribution scenarios.
3 Methodology
3.1 Preliminary
In this work, we specifically focus on the node classification task. Let G (V. E) denote graph, where V is the set of [V] N nodes and S V x V the set of |E] edges between nodes. X Rxd represents the feature matrix, with i-th row representing node v d-dimensional feature vector. Y C {0, 1 denotes the label matrix, where C' is the number of total classes. And (1) denotes the label matrix for training nodes. We denote the ego- ego-graph of node is defined as ((v,) = Ex) with V2 = (1;)..). where Nv stands for all nodes within the k-hop neighborhood of including itself and E, refers to the edges in-between N2. (v;). A well-trained GNN (= ; 0): G - XC parameterized by takes as input and maps every node in to a C-dimensional class distribution. Formally, we define test-time node patching as the following:
Definition 1 (Test-time Node Patching). Given a GNN fa 0) and a graph G, a test-time node patching framework f(: : G + G takes G and outputs the patched graph & with generated nodes and edges, such that the performance of Jg over nodes in G is enhanced when G is utilized:
arg min (f(:))))) x). where 0" = arg min argmin (fa 0), Y(D)).
(I)
+
where C refers to the loss function evaluating the GNN (e.g., cross-entropy or accuracy).
In this work, we aim at mitigating the degree bias via test-time node patching. To achieve so, two challenges need to be addressed: (1) how to optimize and formulate [(::)) such that the graphs patched by f(:; Φ) enhance the performance of [g(:; 0*) over low-degree nodes; and (2) how to derive a unified learning scheme that allows f(= Φ)) to not only improve low-degree nodes but also maintain the GNN's original superiority over high-degree nodes.
3

---

Increasing Corruption Strength
Anchor Node
Real Neighbor
Patching Node
Feed-forward
Gradient Descent
Lightly Corrupted Ego-graph (High-degree case)
Heavily Corrupted Ego-graph (Low-degree case)
Original Ego-graph
Intermediate Ego-graph
Targel GNN ())0)
arggt GNN (+:8)
GNN 0(
Patching from the most corrupted graph
KL Divergence Matching
Divergence Matching
Divergence Matching
GraphPatccee
GraphPatcher
GraphPatcher
Iterative Node Patching
Figure 2: GRAPHPATCHER is presented ego-graphs corrupted by increasing strengths (i.e., the top half of the figure). From the most corrupted graph, it iteratively generates patching nodes to the anchor node, such that the target GNN behaves similarly given the currently patched graph or the corrupted graph next in the hierarchy (i.e., the bottom half of the figure).
3.2 The Proposed Framework: GRAPHPATCHER
Our proposed GRAPHPATCHER is test-time augmentation framework for GNNs to mitigate their degree biases. As shown in Figure GRAPHPATCHER is presented a sequence of ego-graphs corrupted by increasing strengths. Starting from the most corrupted graphs, GRAPHPATCHER iteratively generates patching nodes to augment the anchor nodes. Compared with the corrupted graphs next in the hierarchy, the patched graphs should allow the target GNN to deliver similar outputs. Through this scheme, GRAPHPATCHER not only learns how to patch low-degree nodes while preserving the superior performance over high-degree nodes.
3.2.1 Patching Ego-graphs via Prediction Reconstruction
In order patch low-degree nodes, straightforward approach is to corrupt high-degree nodes into low-degree nodes, and allowing the learning model to patch the corrupted nodes to restore their original properties [25, 13]. However, patching low-degree nodes not only affects their own representations but also those of their neighbors due to the message- passaagg mechanism of GNNs as well as the non-i.i.d. property of nodes in graph. Besides, modeling the learning model to consider all potential circumstances, whose overheads grow quadratically w.r.t. the number of nodes. Consequently, it becomes challenging to simultaneously determine both features and neighbors of the patching nodes given the entire graph.
the entire graphs requires
To reduce the complexity of the optimization process, instead of working over the entire graph, we conduct node patching over ego-graphs and regard each ego-graph as an i.idd sample of the anchor node [56, 19]. For each node 24 we have (G; [). fg (G(v:;; [b] if equals to the number of layers in f, (:: 0). To further simplify the optimization process, we directly wire the generated virtual nodes to the anchor node (i.e., the generated virtual nodes are the first-order neighbors of the anchor node). This implementation is simple yet effective, because we no longer consider the location to place the patching node: any modification that affects the latent representation of the anchor node can be achieved by patching nodes (with different features) directly to the anchor nodes.
We start explaining GRAPHPATCHER by the most basic case where we only conduct node patching once. Specifically, given the trained GNN (: 0*), an anchor node v;, and corruption function T(::t) with strength & (i.c., first-order neighbor dropping with probability t to simulate low-degree

---

scenario), that is, (e())) (V'(t) = (v)( t). GRAPHPATCHER f(: Φ) takes the corrupted ego-graph (v,) as input and outputs the augmented ego-graph (1;) with patching node Up and its feature Xp. which is directly connected to U,. That is,
((v))) = ((g (v:): 4), where = V'o))) U (up): = Evv,)) (c(up))
where e(i.p) refers to the edge connecting i; and up and V'(u.) and (e())) refer to the nodes and edges in G'(e)). respectively. To optimize f(- : Φ) such that fo(:; 0*) gives similar predictions to (v;) and ((v)), we minimize the Kullback-Leibe divergence between the frozen GNN's predictions on these two ego-graphs, which is defined as:
arg min Σ KI.-DDv
V.VV
where KL-Div(y1, of anchor nodes for training. Intuitively, the reconstruction process above enforces GRA PIRAPIPTRR remedy the corrupted neighborhood caused by (:: via adding a patching node directly the anchor node. It is philosophically similar to the existing works (e.g.. TuneUp [13] and Tail-GNN [25]), where models gain better generalization over low-degree nodes via the corrupted high-degree nodes. Empirically, we observe that this branch of approaches can effectively enhance performance over low- degree nodes. Though promising, according to our empirical studies, falls short on the high-degree node that original GNNs perform well at. This phenomenon may be attributed to the unintentially created -fittr-iistiitttion scenario [42], wherein models primarily encounter nodes with low degrees during the training. Consequently, the performance of GNNs, which is typically proficient with high-degree nodes, is adversely affected and downgraded.
+c) (log(y2 + - log(y) + +c) with 0 and Vr refers to the set
3.2.2 Iterative Patching to Mitigate Degree Bias
In this work, we emphasize that: mitigating degree bias should not focus specifically on the low-degree nodes: trading off performance on high-degree nodes for that on low-degree nodes simply creates new bias towards nodes, maintaining GNN's original superiority on high-degree nodes is equally critical. This behavior is empirically desirable because practitioners can universally apply GRAPHPATCHER to all nodes without, like previous works do, manually discovering the degree threshold that differentiates the low- and high-degree nodes. Furthermore, the fact that these frameworks are applicable only to low-degree nodes indicates lack of robustness: further remedying a neighborhood that informative enough to deliver good classification result should not jeopardize the performance.
nodes. Therefore, besides enhancing the performance on low-degree
To mitigate the degree bias, we propose novel training scheme for GRAPUPATCIER such that it observes both low- and high-degree nodes simultaneously during the optimization. Specifically, given a node Fg we firstly create sequence of M corrupted ego-graphs of U, denoted S(v;) ( (v)) = (GG(u, fm M with decreasing corruption strength (i.c., V m,n E {I...., M}. tm tn if m < n). Instead of the one-step patching to match the prediction on the original ego- graph as described in Section 3.2.1, GRAPHPATCHER traverses S(u;) and recursively patches the corrupted ego-graph to match the target GNN's prediction on the ego-graph next in the sequence. As also illustrated in Figure 2, this optimization process is formulated as:
M-1 KL-Div (Jg (g'((i)) 03) (v.:l)
Σ
arg min
2 Vo
s.t. ((())m f(g(1))m
where ((()) m (Vm, Ema) with V.,. = Vi((;) pmppm E.,. E((()) U {amm) and (V.)) ('(v))1.
The one-step patching described in Section 3.2.1 remedies low-degree anchor nodes directly the distributions of high-degree nodes. During this process, the model does not observe distributions of high-degree nodes and hence delivers sub-optimal performance. Therefore, we design GRAPH- PATCHER to be an iterative multi-step framework. At each step, it takes the previously patched
KL divergence used here is equal to the regularized cross-entropy. It is strongly convex and Lipschitz continuous due to the incorporation of These two properties are required for the derivation of Theorem 1.
5

---

ego-graph as input and further remedies the partially patched ego-graph to match the GNN's predic- tion on the ego-graph next in the sequence. This scheme enables GRAPHPATCHER to learn to patch low-degree nodes in early steps when the ego-graphs are heavily corrupted (e.g., low-degree case in Figure 2) and maintain the original performance in later steps when ego-graphs are lightly corrupted (e.g., high-degree case in Figure 2). Specifically, at the m-th patching step, the currently patched
ego-graph (v:)m reflects the neighbor distribution of ego-graphs corrupted by a specific strength of fm+1. GRAPHPATCHER takes ((:)) input and further generates another patching node Um++1 to approach the neighbor distribution of ego-graph, corrupted by a slightly weaker strength of tm+22- This process iterates until GRAPHPATCHER traverses ((,)). Intuitively, the incorporation of Cm++1 enriches the neighbor distribution by an amount of lm+2 (m++1 corruption strength. This opti- mization scheme allows GRAPHPATCHER to observe neighbor distributions with varying corruption strengths and makes our proposal applicable to both low- and high-degree nodes.
However, the target distribution at each step (i.e., (g" [ua) in Equation (4)) is not deterministic due to the stochastic nature of the corruption function T. Given an ego-graph ((e)) [V4|
and corruption strength I, one can at most generate ((1-)) ) different corrupted ego-graphs. With a large corruption strength (e.g.. ego- ago-graphs early in the sequence S(u;)), two corrupted ego-graphs generated by the same exact priors might exhibit completely different topologies. Such differences could bring high variance to the supervision signal and instability to the optimization process. To alleviate the issue above, at each step we sample I. ego-graphs with the same corruption strength and let GRAPHPATCHER approximate multiple predictions over them, formulated as:
M-1 L
Cptch
Σ
Σ
KL-Div (f,
fg 0*) (ual)
(5)
1 mm 1=1
where ((1)) = (m) and G' (m:)) refers to one of the L target corrupted ego graphs that GRAPHPATCHER aims to approximate at the m-th step. This approach allows GRAPHPATCHER to patch the anchor node towards a well-approximated region where its high-degree counterparts should locate, instead of one point randomly sampled from this region.
With M - virtual nodes patched to the ego-graph, we further ask GRAPHPATCHER to generate a last patching node to (v:)M-I and enforce the resulted graph ('(v)) M to match the GNN's prediction on the original ego-graph. The last patching node could be regarded slack variable to complement minor differences between the original and the least corrupted ego- ggo-graphs, formulated as:
Lrooon
Σ KL-Div ( (I(())))))))))) [u.), fg (G(v)) (v:l), N.EV
(6)
where ((::)ar f(G(v:) Lreom (Equation (6) also prevents GRAPHPATCHER from overfitting to the low-degree nodes and enforces GRAPHPATCHER to maintain the target GNN's performance over high-degree nodes, since only marginal distribution modification should be expected with this last patching node. Hence, GRAPUPATCIER is optimized by a linear combination of the above two objectives (i.e., arg ming Lpatch + Lrecon).
3.2.3 Theoretical Analysis
As shown in Equation (5), one of the important factors that contribute to the success of GRAPHI PATCHER is sampling multiple ggo-graphs with the same corruption strength. The following theorem shows that the error is bounded w.r.t. the number of sampled ego-graphs L.
Theorem 1. Assuming the parameters of GRAPHPATCHER are initialized from the set P3 = ( l1Φ - -N(0 : 10))ll < B} where 3 > O, with probability at least 1 - 8 for all &o E Pss, the error
(i.e., ((ppuu))) - Epatch) is bounded by OBB +l T.
+ log(1/3)
The proof of Theorem 1 is provided in Appendix C. From the above theorem, we note that without the sampling strategy (i.e., L = 1), the generalization error depends only on the number of parameters (i.e., (+)) given the same objective function, which could lead to high variance to the supervision signal and instability to the optimization process. According to this theorem and our empirical observation, affordable value of L (c.g., L 10) delivers stable results across datasets.

---

4 Experiments
4.1 Experimental Setting
Datasets. We conduct comprehensive experiments on seven real-world benchmark datasets that are broadly utilized by the graph community, including Cora, Citeseer, Pubmed, Wiki. CS, Coauthor-C33 ogbn-arxity Actor, and Chameleon [44, 28, 12, 33J. This list of datasets covers graphs with distinctive characteristics (i.e., graphs with different domains and dimensions) to fully evaluate the effectiveness of GRAPUPATCIERR The detail of these datasets can be found in Appendix A.
Baselines. We compare GRAPHPATCHER with six state-of-the-ane graph learning frameworks from three branches. The first branch specifically aims enhancing the performance on low-degree nodes, including TAIL-GNN [25], BRE [55], and TUNEUP [13]. The second branch con- sists of frameworks that focus handling distii--itiiittinnnn scenarios, including EERM [42] and GTRANS [15]. We list this branch of frameworks as baselines because the sub-optimal performance of GNNS over low-degree nodes could be regarded as an out-of-distribution scenario. As GRAPHI PATCHER is a test-time augmentation framework, the last branch of baseline includes DROPEDGE, which is a data augmentation framework employed during training.
Evaluation Protocol. We evaluate all models using the node classification task [22, 38], quantified by the accuracy score. For datasets with publicly avaiable (i.e., ogbn -rxiiv, Cora, Ci teseee,, and Pubmed), we employ their the provided splits for the model training and testing. Whereas for other datasets, we create a random 10%/10%/800 a semi-supervised learning setting. All reported performance is averaged over 10 independent runs with different random seeds. Both mean values and standard deviations for the performances of all models are reported. Besides mitigating the degree bias for supervised GNNs, GRAPUPATCHER also applicable self-supervised GNNs. To evaluate the model performance for them, we apply GRAPUPATCHER and TUNEUP to state-of-the-art self-supervised GNNs including DGI [39], GRACE [57], and PARETOGNN [20]. We only compare our proposal with TUNEUP since other frameworks require specific model architectures and hence do not apply to self-supervised GNNs.
split for the training/validatoon/essng split, simulate
Hyper-parameters. We use the optimal settings on all baselines given by the authors for the shared datasets and a simple two-layer GCN [22] as the backbone model architecture for all applicable baselines. slyper-parameters we tune for GRAPHPATCHER include learning rate, hidden dimension, the augmentation strength at each step, and the total amount of patching steps with details described in Appendix B. Besides, all of our models are trained on a single RTX3090 with 24GB VRAM; additional hardware information can also be found in the appendix.
4.2 Performance Comparison with Baselines
We compare GRAPHPATCHER with six state-of-the-art frameworks that mitigate the degree bias problem and the performances of all models are shown in Table 1. Firstly we notice that the problem of degree bias is quite serious across datasets for GCN. The performances are ~00% lower than those over high-degree nodes. Comparing GCN with COLBBREW, TAIL- GNN, and TUNEUP, we can observe that frameworks that focus specifically on low-degree nodes can usually enhance GNN's performance over the lower percentile (e.g., 1.2% accuracy gain on Cora by TUNEUP, 0.74% on Citeseer by COLB 1.38% on Pubmed by TAIL-GNN, etc.). However, these frameworks fall short on the high-degree nodes and sometimes perform worse than the vanilla GCN (e.g., -2.7% accuracy degradation Cora by TAIL-GNN, -11.4% Wiki.CS by COLBBREW, and -2.5% on Amazon Photo by TUNEUP). This phenomenon could result from that they unintentionally create an artificial out-of-distribution scenario, where they only observe low-degree nodes during the training, leading to downgraded performance for high-degree nodes that GNNs originally perform well at. Comparing GCN with GTRANS and EERM, we observe that they deliver similar performances as the vanilla GCN does, indicating that frameworks targeting out-of- distribution scenarios cannot mitigate degree biases. Comparing GRAPHPATCHER with all baselines, consistently improves the low-degree performance
low-degree nodes
we notice that our proposed with an average improvement gain of 2.23 accuracy score. Besides, unlike other frameworks that have downgraded performance over high-degree nodes, GRAPHPATCHER can maintain GCN's 's original high-degree superiority, due to our iterative node patching. On average, GRAPHPATCHER improves GCN's s overall performance by 1.4 accuracy score across datasets.
7

---

Table I: Performance (%) of all models over nodes with different degrees. Lower and upper percentile indicate the set of nodes whose degree is ranked in the lower and upper 33% population respectively. two-layer GCN is used as the backbone model for all applicable baselines. Bold indicates the best performance and underline indicates the runner-up, with standard deviations as subscripts.
Method
Core
Citeseer
Pubned
Miki.cS C3
An. Photo
Co.CS
Arxiv
Chameleon
Actor
ACCURACY ON LOW-DUGREE NODES (LowER PERCENTILE)
GCN
73.27
64 64.86
76.88 20.40
72.98
75. 20.41
84.59.0.45
63.15
24.05
27. a7.3
CoL BBREW
73.8220.00
77.72.063
73.98_0.e
76. 18..00
85.56.0.0
63.02gmm1
20
27. 15
TAIL-GNN
71.17.0..0
57. 57.6610083
75.38
74.36.0.38
77.2240.44
85.13
0OM
53,482004
27. 27.80
TUNEUP
74.47
65.17 65.17
77.18
72.60
76.08
84.68
63.34
10.87
1711
EERM
73.40
64.27+0..s
76.30=nz0
73. 12:0..
15
84.8
84.82:074
63, 63,20 20.11
=4.11
27.48.0op
OTRANS
64.95 73.1610..
17.05m1.0
72.15
75.55 10.55
84.741000
62.88 10:
54.29
37.53100m
DROPEDGE
73.57+0.07
65. 07
75. 2:.88
73.94.0.30
76.4940.00
84,31
61.33
54,1220
27.39
GRAPHPATCHER
20.00
67.27
78.98_00 gmmm1
74.04 20000...0m 46
20.84
86.76
64.01 go:r
54.48.0
ACCURACY ON HIGH--EERREE NODES (UPPER PERCENTILE)
GCN
86.83 10.37
17.25
80.84_n.76
83.40 (u.m
84.07 10.71
90.20,o.a7
80.46_u.1
14.11
10:2
COLSBREW
84.80.0.04
75.3320
78.6610.3
71.98_0.0 86
10.07
82.1610
70.57
53.7220
19
TAIL-GNN
84.13+0.42
74.85+0.80
78.74=034
78.91
80.32+0.00
86.75=0..0
00M
54.53-011
27.13=0044
TUNEUP
37.13
76.95.0.01
81.74g0.10
23.11
81.57
a0.65
80,09
54.2520.5
26.64-071
EERM
85.8920.00
76.3740.25
79.98-0.00
82.9820.om
90.17=0.11 32..02
80.37
74.41=0.71
27. 27.39+0.14
GTRANS
86.32.10.34
46.6020
83.42.00.4 80.56
ne
83.95 ms
89.99
20.77.000
54.21
17
DROPEDGE
86.53 86.53
76.35
8 81.44
83.37 2...0..
84.97
89 89.28-00.5
80.64-0:0
54.17-0.11
27. 27.38
GRAPHPATCHER
88.02.0.11
76.65
23.83.0.9
$3.49....2
$4.17
g0.61
54.20=0
27.43
OVERALL PERPORMANCH
GCN
81. 11.22.20.4
79.1 14:0a1
77.30...41
80. 30.38
88, 16
71.73
52.83
27.20
COLBBREW
80. 70.0.
70. 70.1040.65
78. 98.66
73.82.0..0
78.2440.02
85. 85.80
63.55_0.4s
$2.1220058
26.75
TAIL-GNN
79.44 79.4442.64
65 8040..00
76. 76.14:025
74.66-0.118
80.68 80.68:0..e
87 $7.02200.s
00M
52,4620.12
27.6 27.62=0047
TUNFUPP
12.m1
70.92
79.91
76.93_o.s
79. 10.74
88.46.007
71.51
12.89
27.32.00t
EERM
81.4 81.4720.19
70.08:0.13
78.65
77.29.0.00
79: 79.0.0
07.00
71,20=0.18
52,93=024
27 27.65=0029
OTRANS
10.59
69 19.51
78.67
76.39 20.27
80.02..o.u
71.77 10.
52.67
20.93
DROVEDGE
81. 81.10
71. 71.10zous
78. 78.90=aas
77.49
81. 11 11
87. 56.66600.
71.82
$2.89
27 27.28
GRAPHPATCHER
10.54
71.65
78.12 (0:57
81,2310..r 1o.30
_9.44.0.7
72.31_0.2 _o.32
53.21g003
28.34_o.21
Table 2: Performance (%) of GRAPUPATCHER and TUNEUP for different GNN architectures.
Method
Cora
Citeseer
Pubmed
Wiki.CS CC
Photo
Co. CS
Arxiv
ACCURACY ON LOW-DEGREE NODES (LOWER PERCENTILE)
GCN
73.27
64.86+0.92
76.88
72.98
75.59
84.59+0.45
13.15
+TUNEUP
10.47
65.17
77.18 -0.39
72.60
16.08
84.68
63.34.0.32
+GRAPUPATCHER
78.08
67.27
78.98_0.21
74.04 86
27.84
86.7620.84
14.01
G-SAGE
10.57
67.44_m.
76.58 L0.38
61.83
16.32
1..59
61.6410.80
+TUNBUP
71.47+0.11
67. 27.44
77.78
58.4622077
78.48
74.88
62.433a.58
+GRAPUPATCHER
42.33
67.89 20.3
78.93
61.46
78. 11.11
75.14
62.92=0.29
GAT
69.07 13.27
72.37
73.72
79.6610.58
86.93
63.54
+TUNEUP
16.5810.07
66.6710.3
72.07
_0.81
72.08 10.20
81.08 10.25
86.72
63.71
*GRAPHPATCHER
76.88
70.87 20.78
74.47 =0.63
74.26_0077
80.0540.19
89.50
64.1220.14
ACCURACY ON HIGH-DEGRER NODES (UPPER PERCENTILE)
GCN
77.25 86.13
1.00
80.
80.84_0.76
84.07 83.40.00.70
80.46 90.20
+TUNEUP
76.95 80.13
81.74_0.49
83.1 83.11 =0.53
81.57
90.65+0.88
u..51
+GRAPHPATCHER
88.02
76.65.00.18
83.83 _3.73_
83.49 10.22
14.07
10.49
80.61
G-SAGE
82.04.0.01
72.4610.70
80.24_..12
60.83 10.18
77. 10.30
10.55
78.66 20.8
+TUNEUP
80. 80.84
73.95 2:036
81.14 10.14
60.90.20.00
79.36
70. 12.0255
79. 29.26620.51
+GRAPHPATCHER
40.44 40.48
73.22
81.66_0.46
61.02.40.44
78.57
+0.63
79.91
GAT
85.33 10.36
76.65
81. 11.14_..20
82.21 10.44
87. 87.84
91.33
11.37.0.11
+TUNEUP
40.47
76.65
20.33
80.84 04.0z
81.73 20.36
89,02
92.00+0.04 20.04
81.44=0.11
+GRAPHPATCHER
86.53
76.35
81.14 -0.00 0.89
82.34.0.00
87. 87.8410.56
91.61 10,20
15
We further apply GRAPHIATCHER to other GNN architectures (i.e., GraphSAGE [9] and GAT [38])
and compare its performance to TUNEUP. We only compare with TUNEUP since other baselines explore specific model architectures that do not allow a different backbone. From Table 2, we can observe that the issue of degree bias still exists on GAT and GraphSAGE with performance gap between low- and high-degree nodes around ~00% Both TUNEUP and GRAPHPATCHER can improve the performance over low-degree nodes. Specifically, TUNEUP on average improves 0.27 low-degree accuracy for GraphSAGE. and 0.40 for GAT across datasets; whereas GRAPHPATCHER improves 1.13 for GraphSAGE and 1.66 for GAT, outperforming TUNEUP by large margin.
8

---

4.3 Performance of GRAPHPATCHER for Self-supervised GNNs
Table 3: Effectiveness for self self-supervised GNNs.
To fully demonstrate the effectiveness of GRAPHPATCHER, we also apply our proposal to self-supervised GNNs, as shown in Table We can observe that self-supervised learning can mitigate degree bias by itself, proved by smaller gaps between low- and high-degree nodes than those of semi-supervised GNNs. Combined with GRAPIIPATCIER the degree biases can be further without sacrificing GNN's original superiority over high-degree nodes. On average, GRAPHPATCHER can enhance the low-degree performance of these three self- supervised GNNs by 1.78, 0.74, and 1.36 ac- curacy scores respectively.
Method
Cora
Pubmed
Wiki. CS
LOW-DEGREE NODES (LOWER PERCENTILE)
DGI *GRAPHPATCHER
78.47
75.63
75.86
79.95
78.04.0.97
77.31
GRACE
77.80 77.80.0.5
74.31
+GRAPHPATCHER
78.53
78.49
75.12220.44
PARETOGNN
78.85
78.3220-55
14.17.0.18
+GRAPUPTTCHER
79.1 79.1 79.91
76.41
HIGH-DEGREE NODES (UPPER PERCENTILE)
DGI +GRAPHPATCHER
86.83-20.92
81.14:0022
81.0920.81
=6.91
82.31
80.95
GRACE *GRAPHPATCHER
85.03-20.05
78.74g0.84
K3.91
85. 12:20.5
79.58
84.1220.22
PARETOGNN
87.03
20.89
81.57
+GRAPHPATCHER
87.32.0.27
80.55
81.78g0.51
4.4 Effectiveness of GRAPHPATCHER for Enhancing So Method
We apply GRAPHIPTTCHER GRAND [5], strong GNN that utilizes random propagation strategy to perform graph data augmentation and significantly improve the node classification performance. The performance improvement brought by GRAPHPATCHER is shown in Ta- ble We observe that GRAPHPATCHER can still consistently improve the node classifica- tion for GRAND. Specifically, on low-degree nodes, GRAPUPATCHER can improve 1.40, 2.23, and 4.20 accuracy score on Cora, Citeseer, and Pubmed, respectively. Overall, GRAPH- PATCHER further enhances the SoTA perfor- mance these three datasets, with outstanding accuracy score of 85.90, 76.10, and 84.20.
Table 4: Effectiveness for SoTA.
Method
Cora
Citeseer
Pubmed
LOW-DEGREE NODES (LOWER PERCENTILE)
GRAND +GRAPHPATCHER 81.58
80.18 70.57 72.73
80.48
84.68
HIGH-DEGREE NODES (UPPER PERCENTILE)
GRAND +GRAPHPATCHER 88.92 79.54.0.13
88.32.0.70
79.6420.86
83.53
84.43
OVERALL PERFORMANCE
GRAND *GRAPHPATCHER
22
74.90 24.90
82.30
85. 85.9020..4
76. 10
84.2010.20
The significant gain from GRAPHPATCHER indicates that the effectiveness brought by the test-time augmentation is not overlapped with the data augmentation during the training.
4.5 Performance w.r.t. the Number of Patching Nodes
Cora
To investigate the necessity of patching multiple nodes, we conduct experiments over the number of patching nodes the test time. As shown in Figure 3, we notice that the overall performance gradually increments as the number of patching nodes increases, demonstrating that multiple patching nodes are required to remedy the incomplete neighborhood low-degree nodes. Besides, we discover that the performance of GRAPUPATCHER saturates with around four nodes patched, which aligns with our training procedure, where the length of the ego-graph sequence at most five. Experiments concerning the number of patching nodes during the optimization and the number of sampled ego- -ro-graphs per corruption strength (i.c., M and T. in Equation (5)) can be found in Appendix B.
42.5
Original Perf
Pubmed
$0.5
Original Perf
Arxiv
Original Perf.
Figure Overall perf. (y-axis) w.r.t the number of patching nodes (x-axis).
5 Discussion w.r.t. Diffusion Models
Both diffusion models and GRAPHPATCHER conduct multiple corruptions to training samples with increasing strengths and generate examples in an iterative fashion. This scheme is conceptually inspired by heat diffusion from physies. However, the motivations behind them are different, where diffusion models focus on the generation quality (i.c., fidelity to the original data distribution) but ours

---

aims at the results brought by our generated nodes (i.e., the performance improvement). Specifically, diffusion models [10, 32] aim at learning the probability distribution of the data and accordingly generating examples following the learned distribution. Their goal is to generate samples that follow the original data distribution, agnostic of any other factor like the target GNN we have in our scenario. Whereas for models deliver better predictions when the node degree low. We mostly care about performance improvement and the generated node may be very different from the original nodes in the graph.
we aim at generating nodes to ego-nets such that the target GNN
Discussion w.r.t. Generation Methods for Graph
Most graph generation frameworks (including those using diffusion models) explore iterative genera- tion schemes to synthesize real graphs [58, 46, 6, 30, 16, 40]. They improve the generation quality and focus on applications such as molecule design, protein design, and program synthesis. Though GRAPHPATCHER also generates patching nodes for ego-graphs, ours is a different research direction than these methods. We do not focus whether not the generated patching nodes are faithful to the original data distribution, as long as the low-degree performance is enhanced and the high-degree performance is maintained. Another relevant work named GPT-GNN [14] explores an iterative node generation for pre-training, which also falls under the category of maintaining the original data distribution. In summary, GRAPHPATCHER is relevant to these frameworks in the sense that it generates nodes to add to ego-graphs. However, our proposal is motivated by a different reason and aim the performance improvement brought by generated nodes in downstream tasks.
7 Conclusion
We study the problem of degree bias underlying GNNs and accordingly propose a test-time aug- mentation framework, namely GRAPHPATCHER. GRAPHPATCHER iteratively patches ego-graphs with its generated virtual nodes to remedy the incomplete neighborhood. Through our designated optimization scheme, GRAPHPATCHER not only patches low-degree nodes but also maintains GNN's original superior performance over high-degree nodes. Comprehensive experiments are conducted over seven benchmark datasets and our proposal can consistently enhance GNN's overall perfor- mance by up to 3.6% and low-degree performance by up to 6.5%, outperforming all baselines by large margin. Besides, GRAPHPATCHER can also mitigate the degree bias issue for self-supervised GNNs. When applied to graph learning methods with state-of-the-an performance (i.c., GRAND), GRAPHPATCHER can further improve the SoTA performance by large margin, indicating that the effectiveness brought by the test-time augmentation not overlapped with existing inductive biases.
Limitation and Broader Impact
One limitation is the additional overhead entailed by generating ego-graphs. To address this limitation, we generate all ego-gres graphs before the optimization to avoid duplicated computations. This operation takes more hard-disk storage, which is relatively cheap compared with computational resources. Furthermore, we observe no ethical concern entailed by our proposal, but we note that both ethical or unethical applications based on graphs may benefit from the effectiveness of our work. Care should be taken to ensure socially positive and beneficial results of machine learning algorithms.
Acknowledgement
We appreciate Shifu Hou from University of Notre Dame for valuable discussions and suggestions. We would also like to thank anonymous reviewers for their constructive suggestions and comments (i.e.. experiments over heterophilic datasets, connections to diffusion models, and discussion w.r.. iterative generation models for graphs). This work is partially supported by the NSF under grants IIS-2334 505-2321504, IIS-2203262, IIS-2214377 4376, IIS-22i7239, OAC-2218762, CNS-2203261, and CMM1-2146077 Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of any funding agencies.
10

---

References
[1] Murat Seckin Ayhan and Philipp Berens. Test-time data augmentation for estimation of heteroscedastic aleatoric uncertainty in deep neural networks. In Medical Imaging with Deep Learning, 2018.
[2] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi. Spectral clustering with graph neural networks for graph pooling. In Procs. of ICML, 2020.
[3] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Erie Zhao, Jiliang Tang, and Dawei Yin. Graph neural networks for social recommendation. In Procs. of www, 2019.
[4] Yujie Fan, Mingxuan Ju, Chuxu Zhang, and Yanfang Yc. Heterogeneous temporal graph neural network. In Procs. of SDM, 2022.
[5] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. Graph random neural networks for cumi-supervised learning on graphs. Procs. of NeurlPS, 2020.
[6] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu. Graphgen: A scalable approach to domain-agnostic labeled graph generation. In Procs. of WWW, 2020.
[7] Zhichun Guo, Chuxu Zhang, Wenhao Yu, John Herr, Olaf Wiest, Meng Jiang, and Nitesh V Chawla. Few-shot graph learning for molecular property prediction. In Procs. of WWW, 2021.
[8] Zhichun Guo, William Shiao, Shichang Zhang. Yozen Liu, Nitesh Chawla, Neil Shah, and Tong Zhao. Linkless link prediction via relational distillation. In Procs. of ICML, 2023.
[9] William Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Procs. of NeurlPS, 2017.
[10] Jonathan Ho, Ajay Jain, and Picter Abbeel. Denoising diffusion probabilistic models. Procs. of NeurlPS, 2020.
[11] Weihua Hu. Bowen Liu, Joseph Gomes, Marinka Zimik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. In Procs. of ICLR, 2019.
[12] 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. In Procs. of NewrIPS, 2020.
[13] Weihua Hu, Kaidi Cao, Kexin Huang, Edward W Huang, Karthik Subbian, and Jure Leskovec. Tuneup: A training strategy for improving generalization of graph neural networks. arXiv, 2022.
[14] Ziniu Hu, Yuxiao Dong, Kuansan Wang, Kai-Wei Chang, and Yizhou Sun, Gpt-gnn: Generative pre-training of graph neural networks. In Procs. of KDD, 2020.
[15] Wei Jin, Tong Zhao, Jiayuan Ding, Yozen Liu, Jiliang Tang, and Neil Shah. Empowering graph representation learning with test-time graph transformation. In Procs. of ICLR, 2023.
[16] Jaehycong Jo, Seul Lee, and Sung Ju Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In Procs. of ICML, 2022.
[17] Mingxuan Ju, Shifu Hou, Yujie Fan, Jianan Zhao, Yanfang Ye, and Liang Zhao. Adaptive kernel graph neural network. In Procs. of AAAI, 2022.
[18] Mingxuan Ju, Wenhao Yu, Tong Zhao, Chuxu Zhang, and Yanfang Ye. Grape: Knowledge graph enhanced passage reader for open-domain question answering. In Findings of EMNLP, 2022.
[19] Mingxuan Ju, Yujie Fan, Chuxu Zhang, and Yanfang Ye. Let graph be the go board: gradient- free node injection attack for graph neural networks via reinforcement learning. Procs. of AAAI, 2023.
11

---

[20] Mingxuan Ju, Tong Zhao, Qianlong Wen, Wenhao Yu, Neil Shah, Yanfang Ye, and Chuxu Zhang. Multi-task self-supervised graph neural networks enable stronger task generalization. In Procs. of ICIR,, 2023.
[21] Ildoo Kim, Younghoon Kim, and Sungwoong Kim. Learning loss for test-time augmentation. Procs. of NeurIPS, 2020.
[22] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. Procs. of ICLR, 2016.
[23] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In Procs. of ICLR, 2019.
[24] Gang Liu, Tong Zhao, Eric Inae, Tengfei Luo, and Meng Jiang. Semi-supervised graph imbalanced regression. In Procs. of KDD, 2023.
[25] Zemin Liu, Trung- Kien Nguyen, and Yuan Fang. Tail-gnn: Tail-node graph neural networks. In Procs. of SIGKDD, 2021.
[26] Philip M Long and Hanie Sedghi. Generalization bounds for deep convolutional neural networks. In Procs. of ICLR, 2020.
[27] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. homophily a necessity for graph neural networks? In Procs. of ICLR, 2022.
[28] Julian McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In Procs. of SIGKDD, 2015.
[29] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of machine learning. MIT press, 2018.
[30] Chenhao Niu, Yang Song, Jiaming Song, Shengjia Zhao, Aditya Grover, and Stefano Ermon. Permutation invariant graph generation via score-based generative modeling. In Procs. of AISTATS, 2020.
[31] Aditya Pal, Chantat Eksombatchai, Yitong Zhou, Bo Zhao, Charles Rosenberg, and Jure Leskovec. Pinnersage: Multi-modal user embedding framework for recommendations at pinterest. In Procs. of SIGKDD, 2020.
[32] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Bjöm Ommer. High-resolution image synthesis with latent diffusion models. In Procs. of CVPR, 2022.
[33] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 2008.
[34] Divya Shanmugam, Davis Blalock, Guha Balakrishnan, and John Guttag, Better aggregation in test-time augmentation. In Procs. of CVPR, 2021.
[35] William Shiao, Uday Singh Saini, Yozen Liu, Tong Zhao, Neil Shah, and Evangelos Pa- palexakis. Carl-g: Clustering-acceleratee representation learning on graphs. Procs. of KDD, 2023.
[36] Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mi- tra, and Suhang Wang. Investigating and mitigating degree-related biases in graph convoltuional networks. In Procs. of CIKM, 2020.
[37] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller. Graph clustering with graph neural networks. arXiv, 2020.
[38] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In Procs. of ICLR, 2017.
[39] Petar Velickovic, William Fedus, William I. Hamilton, Pietro Liò, Yoshua Bengio, and Devon Hjelm. Deep graph infomax. In Procs. of ICLR, 2019.
12

---

[40] Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard. Digress: Discrete denoising diffusion for graph generation. In Procs. of ICLR, 2022.
[41] Guotai Wang, Wenqi Li, Michael Aertsen, Jan Deprest, Sébastien Ourselin, and Tom Vercauteren. Aleatoric uncertainty estimation with test-time augmentation for medical image segmentation with convolutional neural networks. Neurocomputing. 2019.
[42] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. Handling distribution shifts on graphs: An invariance perspective. In Procs. of ICLR, 2022.
[43] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Procs. of ICLR, 2018.
[44] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervisee learning with graph emheddings. In Procs. of ICMI, 2016.
[45] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Procs. of SIGKDD, 2018.
[46] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec. Graphrnn: Generat- ing realistic graphs with deep auto-regressive models. In Procs. of ICML, 2018.
[47] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen. Graph contrastive learning with augmentations, In Procs. of NeurlPS, 2020.
[48] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang. Graph contrastive learning automated. In Procs. of ICML,, 2021.
[49] Sukwon Yun, Kibum Kim, Kanghoon Yoon, and Chanyoung Park. Lte4g: Long-tail experts for graph neural networks. In Procs. of CIKM, 2022.
[50] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In Procs. of NeurlPS, 2018
[51] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee- Kong Lee. Motif-based graph self-supervised learning for molecular property prediction. Procs. of NeurlPS, 2021.
[52] Tong Zhao, Tianwen Jiang, Neil Shah, and Meng Jiang. synergistic approach for graph anomaly detection with pattern mining and feature learning. IEEE Transactions on Neural Networks and Learning Systems, 2021.
[53] Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang. Learning from counterfac- tual links for link prediction. In Procs. of ICML, 2022.
[54] Tong Zhao, Wei Jin, Yozen Liu, Yingheng Wang. Gang Liu, Stephan Günnemann, Neil Shah, and Meng Jiang. Graph data augmentation for graph machine learning: A survey. IEEE DEBULL, 2023.
[55] Wenqing Zheng, Edward W Huang, Nikhil Rao, Sumeet Katariya, Zhangyang Wang, and Karthik Subbian. Cold brew: Distilling graph node representations with incomplete or missing neighborhoods. In Procs. of ICLR, 2021.
[56] Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, and Jiawei Han. Transfer learning of graph neural networks with ego-graph information maximization. In Procs. of NeurIPS, 2021.
[57] Yanqiao Zhu Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep Graph Contrastive Representation Learning. In ICML Workshop on Graph Representation Learning and Beyond, 2020.
[58] Yanqiao Zhu, Yuanqi Du, Yinkai Wang, Yichen Xu, Jieyu Zhang, Qiang Liu, and Shu Wu. A survey on deep graph generation: Methods and applications. In Procs. of LOG, 2022.
13

---

A Dataset Description
We evaluate our proposed GRAPHPATCHER as well as other frameworks that mitigate the degree bias problem on seven real-worlds datasets spanning various fields such as citation network and merchandise network. Their statistics are shown in Table For Cora, Citeseer and, Pubmed, we explore the community acknowledged public splits (i.e., fixed 20 nodes per class for training, 500 nodes for validation, and 1000 nodes for testing); whereas for ogbn-arxiv, we use the API from Open Graph Benchmark (OGB)² and explore the provided splits. For Wiki. CS, mraazon-Photo and Coauthor-CS, we randomly select 10% nodes for training, another 10% for validation, and the remaining 80% for testing. We use the API from Deep Graph Library (DGL)² to load all datasets.
Table Dataset Statisties.
Dataset
# Nodes
# Edges
# Features
Avg. Degree
Split
Cora
2,708
5,429
1,433
2.0
Public Split
Citeseer
3,327
4,732
3,703
1.4
Public Split
Pubmed
19,717
88,651
500
4.5
Public Split
Wiki-CS
11,701
216,123
300
18.5
10% /00%
Amazon-Photo
7,650
119,043
745
15.6
10%/10%/800
Coauthor-CS
18,333
81,894
6,805
4.5
10%/10%//80%
ogbn- arxiiv
169.343
1,166,243
128
6.9
Public Split
B GRAPHPATCHER Configuration and Experiment on Hyper-parameter:
B.1 GRAPHPATCHER Configuration
The architecture of GRAPHPATCHER consists two parts; the first part is a 2-layer GCN encoder that takes ego-graph as input and vectorizes its nodes and the second part is MLP that takes the representation of the anchor node and outputs the generated feature for the virtual patching node.
To ensure the reproducibility, we also provide the detailed PATCHER for all datasets, as shown in Table 6. Besides, we use an early stopping strategy to decide the number of optimization steps, where the optimization stops if the validation loss stops decreasing for two consecutive steps.
configurations of GRAPH-
Table 6: Hyper-parametery used for GRAPUPATCHER,
Hyper-param.
Cora
Citeseer
Pubmed
Wiki.CS CS
Am. Photo
Co. CS
Arxiv
Augmentation strength
0.3
0.3
0.3
0.3
0.3
0.3
0.1
Patching step # of sampled graphs
3
3
3
10 used for all datasets
Batch size Accumulation step Learning rate Optimizer
64
64
8
16
16
16.
16
32
16
16
64
1e-4 used for all datasets
AdamW with weight decay le-5 used for all datasets
B.2 Experiment on Hyper-parameters
The hyper-parameters tune for GRAPHPATCHER include the number of patching nodes during the testing time, learning rate, hidden dimension, the augmentation strength at each step, and the total amount of patching steps. Experiments w.r.t. the number of patching nodes during the testing time has been showcased in Figure 3 and here we also append the results for the other four datasets, as shown in Figure 4. We observe similar trends as the aforementioned three datasets exhibit, where the
http::///ggbettaood....o
14

---

Citeseer
78.5 Wiki.CS
78
71
Original Perf.
77.5
Original Perf.
70
77
81.5
Am. Photo
89.5 Co.CS
80.5
Original Perf.
88.5
Original Perf.
Figure 4: Overall perf. (y-axis) w.r.t. the number of patching nodes (x-axis).
(a) Accuracy w.r.t. learning rate
(b) Accuracy w.r.t. hidden dimension
90
90
85
85
Acc (96)
Acc(%)
80
75
75
70
65
65
arxiv
Cora
Pubmed
arxiv
Cora
Pubmed
O 1.00E-03 D 5.00E-04 12 1.00E-04
5.00E-05
664 E 128
2 256
m 1024
(c) Accuracy w.r.t. augmentation strength
(d) Accuracy w.r.t. sampled graphs
90
85
85
Acc(%)
Acc(%)
80
75
75
70
65
arxiv
Cora
Pubmed
arxiv
Cora
Pubmed
U00.1 010.2 0.3 II 0.4
C5
M
Figure 5: GRAPHPATCHER' sensitivity different hyper-parameters..
performance of GRAPHPATCHES improves the number of patching nodes increases and the gain saturates with 4 to nodes patched.
We also conduct experiments w.r.t. learning rate, hidden dimension, the augmentation strength at each step, and the total amount of patching steps during the training. We tune the hidden dimension by conducting grid search over common selections of [64, 128, 256, 1024] hidden units; we tune the learning rate similarly by searching over [1e-3, 5e-4, le-4, 5e-5]; and we tune the augmentation strength by searching over 10 0.2, 0.3, 0.4).
The hidden dimension refers the intermediate dimension of the 2-layer GCNs of GRAPHPATCHER. GRAPHPATCHER is constructed by 2-layer GCN and features for virtual nodes are generated by following multi-layer perceptron with the same hidden dimension. To reduce the search complexity, we explore an arithmetic sequence for the augmentation strength (i.e., the difference between any two consecutive strengths is the same) and set the total amount of patching steps during the training to 1. For instance, an augmentation strength of 0.3 would lead to a 3-step training with augmentation strength of 0.3, 0.6, and 0.9 respectively. GRAPHPATCHER'S sensitivity to these nyper-parameter shown in Figure 5, Specifically, in Figure 5.(a) we can observe that across datasets, a large learning rate (i.e., 1e-3) leads to sub-optimal performance and GRAPHPATCHER achieves the best performance with learning rate of le-4. We also investigate GRAPHPATCHER? sensitivity to the number of
15

---

hidden dimensions (i.e.. the model size), In Figure 5.(b), we notice that for large graphs like Arxiv, the performance gradually increases the model size enlarges. And for small and medium graphs like Cora and Pubmed, the performance saturates with hidden dimension of 128. Besides, in Figure 5.(c) we study GR GRAPHPATCHER performance w.r.t. the augmentation strength (which can also be interpreted as the number of patching steps as described previously). We can observe that, for small and medium graphs, strong augmentation strength leads to better performance, due to the sparsity of the graph structures. Whereas for large graphs, small augmentation strength delivers good performance. Furthermore, to prove the effectiveness our proposed training scheme with train GRAPHPATCHER with different numbers of sampled graphs (i.e., L in Equation (5)), with the performance shown in Figure 5.(d). We can observe that without our proposed sampling strategy (i.e., the first column with L 1), the performance of GRAPHPATCHER degrades significantly. As the number of sampled graphs gradually increases, the performance keeps improving and saturates with I. 10, empirically proving the effectiveness of the exploration of multiple ego-graphs for the same corruption strength.
multiple ego-gran gro-graphs,
B.3 Hardware and Software Configuration
We conduct experiments server having RTX3090 GPU with 24 GB VRAM. The CPU have on the server an AMD Ryzen 3990X with 128GB RAM. The software we use includes DGL 1.9.0 and PyTorch 1.0. As for the baseline models that compare GRAPHPATCHER with, explore the implementations provided by code repositories listed as follows:
TAII--GNN http::///ggghhuu..oo////////a/aa
COLBBREW http://///tttthhoooo////////oo/a
EERM [42]: http:://ggtttttioooooo//aaaaaaaa
GTRANS [15] http://ttt/rgggggooooo//////aa/r
DGI [39] http://ttttt..ooaaa/////////////
GRACE [57]: http:///gtthoooooo/c//////////tt
PARETOGNN [20]: http:p///gggttt....o/////o/////t /ttpt///aaggggaooooooo////////aa
We sincerely appreciate the authors these works for open-sourcing their valuable code and researchers DGL for providing reliable implementations of these models. For TUNEUP [13], since the authors have not released the code yet, we manually implement by ourselves, with a similar performance reported in its original paper.
C Proof to Theorem 1
Here we re-state Theorem before diving into its proof:
Theorem 1. Assuming the parameters of GRAPHPATCHER initialized from the P3 { || NO Φ0: 1 1o)))le < B} where 0, with probability at least 1 8, for all & E Pp. the error
bound (i.e., E(Cpunch Cpanch) is ( [
log(1/9)
Proof. To prove Theorem 1, we need the following lemma, which has been broadly utilized in the literature of generalization error bound [26, 29].
Lemma Suppose a set functions is (B, d)- -ipscchht parameterized for B > and d E N with input from distribution D and output in (0, 1). There exist constant such that for all n e N, for any > 0, if S is obtained by sampling n times independently from D, with probability at least
1 for all B and f P, we have:
- - (B d +
log (1g(1/))
In order to prove E(Cparch) - Epanch is 0 A
log(1/M) V L we need to show that Cpanch is
Lipschitz continuous. Lpanch. as discussed in Section 3.2.1, is regularized cross-entropy formulated
16

---

as (y1 +c)- (ly)+c)-(oottllle (log(y2+<) -) +)). In this work, and y2 refers to the prediction distribution
(i.e., 0 < Yı 1) delivered by the GNN we aim improving. Hence, we need to show that for given
specific yI. for any two y2 y2 E {y2 0 < y2
< <1} and k E RRt, we have
(1) + +)) log(
y2 + ) (y1 c) log(
S K.
|22 v22l
(8)
y1 +
Y1
(1) +c) (log(?
y2 + ) - log
y2 + c
|)|
' ||5 - 3لو
(9)
Y1 +
y1 +
|(v] +e) (log( y2 + y2
K
| y
(10)
Given the fact that log(.) strictly concave, Equation (10) holds and hence Lpach is Lipschitz continuous. We can then directly apply Lemma 1 to show that Theorem holds.
17


Reviews:
[{"review_id": "QyhitqjsaK", "reviewer": "Reviewer_xNZm", "summary": "The paper proposes GRAPHPATCHER, a test-time augmentation framework for graphs, to mitigate the degree biases in Graph Neural Networks. GRAPHPATCHER adopts a corruption function with increasing strength to simulate low-degree ego-graphs from a high-degree one. From the most corrupted graph, it then iteratively generates virtual nodes to the anchor node, such that the frozen GNN model behaves similarly given the currently patched graph or the corrupted graph next in the hierarchy. The authors then examine the effectiveness on seven real-world benchmark datasets, and observe that GRAPHPATCHER enhances the low-degree performance up to 6.5%, when enhancing the overall performance by up to 3.6% at the same time.", "questions": "Please refer to the weaknesses part.", "limitations": "The paper has properly addressed the limitations of the proposed method. One limitation is the additional computational cost entailed by generating ego-graphs. The authors provide solutions to mitigate the problem.", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The proposed GRAPHPATCHER avoids creating an artificial out-of-distribution scenario when focusing only on low-degree nodes, and hence avoids significantly sacrificing the performance on high-degree nodes. \n2. The modelling and optimization are conducted through aligning the ego-graph sequence and its reconstruction. The test-time augmentation framework avoids changing model architectures and the expensive re-training cost. The structure is simple with good performance.\n", "weaknesses": "1. The way GRAPHPATCHER patches the corrupted ego-graph (adding one node and the corresponding edge at a time) might limit the expressive ability of the model, as it could be difficult for this strategy to reflect more complex structures between the anchor node's neighbors.\n2. The continuous corruption and patching on ego-graph share some similarities to the diffusion model. It would be more insightful if the theory behind the methodology and the similarity/dissimilarity with the diffusion model are discussed.\n3. In the experimental part, Tail-GNN performs worse than GCN in almost all cases. Even for the low-degree nodes, Tail-GNN cannot always beat GCN, which is unexpected since Tail-GNN is specially designed for low-degree nodes. If there is a problem with the baseline tuning, some conclusions cannot be well supported (e.g., Tail-GNN falls short on the high-degree nodes). This also affects the convincingness of the superiority of GRAPHPATHCER over baselines.\n4. It is claimed that the chosen datasets cover graphs with distinctive characteristics, but all datasets used are homophilic ones. It is expected to have more experiments on heterophilic datasets. Since heterophilic graphs often have more complex topologies, they are more susceptible to node adding and dropping.\n\nOther minor issues:\nTypo in row 8: \"orizinally\".\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer xNZm,\n\nThank you for your valuable feedback. We sincerely appreciate your acknowledgment of the effectiveness of our proposed framework. Our detailed response to your concerns is listed as follows:\n\n**[Limited expressive ability]** \\\nWe agree with you on the fact that the way we patch nodes to ego-graphs will not enhance the expressive ability from the perspective of graph-level isomorphism (e.g., making two ego-graphs distinguishable). However, **this is not a problem for our method** because we are not focusing on graph-level distinguishability (e.g., patching nodes to distinguish two ego-graphs that are indistinguishable before). Instead, we care about enhancing node-level predictions over low-degree nodes, where nodes with the same class are mapped to the same class after the node patching. For node classification tasks, a **stronger expressive ability might not always lead to good performance**. For instance, GIN has a stronger expressive ability than GCN, but GCN consistently outperforms GIN on many node classification benchmarks [3]. Moreover, training-time augmentation frameworks that add additional edges/nodes to the graph might also impact the expressive ability of the learning model [1,2]. Furthermore, even for graph-level classification tasks where expressive ability is very important, a model with better expressive ability does not necessarily outperform models with lower expressive ability [3,4]. \n\n[1] Zhao, Tong, Yozen Liu, Leonardo Neves, Oliver Woodford, Meng Jiang, and Neil Shah. \"Data augmentation for graph neural networks.\" AAAI’21\n\n[2] Mehdi Azabou, Venkataramana Ganesh, Shantanu Thakoor, Chi-Heng Lin, Lakshmi Sathidevi, Ran Liu, Michal Valko, Petar Veličković, and Eva L Dyer. \"Half-Hop: A graph upsampling approach for slowing down message passing.\" ICML’23\n\n[3] Dwivedi, Vijay Prakash, Chaitanya K. Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. \"Benchmarking Graph Neural Networks.\" JMLR’23\n\n[4] Zhao, Lingxiao, Neil Shah, and Leman Akoglu. \"A practical, progressively-expressive GNN.\" NeurIPS’22\n\n**[Similarity/Dissimilarity with the diffusion model]** \\\nPlease refer to G1 in the general response. We will update the final version of our paper by adding the discussion above and we sincerely appreciate your suggestions. \n\n**[Performance of Tail-GNN]** \\\nThanks for your attention to our experiments. We fully acknowledge the contributions brought by Tail-GNN as it is one of the earliest works that enhance low-degree performance by learning from corrupted high-degree nodes. When the evaluation setting aligns with Tail-GNN’s motivation, the low-degree performance indeed is improved by a lot. As shown in our results, Tail-GNN’s low-degree performances on dense datasets like Wiki. CS, Am. Photo and Co. CS are competitive (i.e., 1st on Wiki. CS, 2nd on Am. Photo, and 3rd on Co. CS) compared to GCN and other SoTA methods. However, Tail-GNN is well motivated by solving the cold start problem and it is evaluated in a setting specifically designed for low-degree nodes. Tail-GNN explores warm nodes only for training (i.e., all nodes with a degree higher than 5 across all datasets) and cold nodes only for testing (i.e., all the remaining nodes). This setup enables Tail-GNN to perform well on low-degree nodes over dense datasets like Wiki. CS, Co. Photo, and Co. CS. \n\nUnlike TailGNN, GraphPatcher explores a different research direction: while enhancing the low-degree node performance, GraphPatcher also aims at maintaining good performances over high-degree nodes. In order to evaluate this goal, we need to train and evaluate models by a mixture of low- and high-degree nodes. This setting might not favor Tail-GNN as it is different from the original setting that Tail-GNN is evaluated on. We followed the optimal hyper-parameters provided by the authors of Tail-GNN in the original paper and utilized the official GitHub repo to conduct the experiment. For Cora, Citeseer, and Pubmed, they are relatively sparse with average degrees lower than 5, which also does not favor Tail-GNN due to the lack of high-degree nodes for Tail-GNN to train from.\n\n**[Experiments over heterophilic datasets]** \\\nPlease refer to G2 in the general response. The updated experiments over heterophilic datasets are included in our provided one-page pdf. We will update the final version of our paper with these additional experiments. \n\nWe sincerely appreciate your suggestions over our manuscript. We will **accordingly modify the manuscript to clarify your concerns** when the anonymous period ends and we hope we have satisfactorily answered your questions. If so, could you please consider increasing your rating? If you have any remaining doubts or concerns, please let us know, and we will happily respond. Thank you! \n\nBest regards, \\\nGraphPatcher's authors\n"}, {"review_id": "vVrrryUpT8", "reviewer": "Reviewer_ZZgb", "summary": "This paper introduces GraphPatcher, a novel test-time augmentation framework designed to mitigate degree bias in graph neural networks (GNNs). Degree bias causes GNNs to perform well with high-degree nodes (rich neighbor information) and poorly with low-degree nodes. Current strategies tend to focus on low-degree nodes during training, which can compromise performance on high-degree nodes. To overcome this, GraphPatcher creates virtual nodes to progressively 'patch' low-degree nodes, enhancing performance without sacrificing the capabilities of GNNs on high-degree nodes. The framework is model-agnostic, applicable to self-supervised or supervised GNNs, and shows significant improvement in overall and low-degree node performance across multiple benchmark datasets.", "questions": "**Some Connections to Iterative Graph Generation And Diffusion Models**: The proposed GraphPatcher is conceptually to iterative graph generation framework, only the training objective is different. The way KL-divergence is used is also similar to a lot of graph generation methods. It is recommended to consider the connection to the graph generation works to see what can be adopted. I feel an autoregressive model like autoregressive transformer or LSTM can be a good candidate for generating the sequence of patched node. The main idea is that it could be possible to know when to stop (predict stop token). \n\nThe recent works on graph generation using diffusion models could also be a very relevant. These are just some random thoughts, I will appreciate the thoughts from the authors on how this could relate to this work, and maybe adding some future directions into the discussion section if it is indeed relevant.", "limitations": "No limitations are left unaddressed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- I like the reasoning of the paper, which makes the proposed method well motivated and natural.\n- The proposed method is more \"adaptive\" to both low-degree and high-degree nodes, without special treatments that is only for low degree node. The iterative patching sounds like denoising diffusion models, which is interesting.\n- There are enough details for reproducibility and the code is attached to the supplementary.\n", "weaknesses": "**Concern About Weak Model Performances**: Though the experiment results show the GraphPatcher sometimes is more accurate than the baselines, it is less convincing because the baselines does not look strong enough. For example, for citation networks like Cora, Citeseer and Pubmed, the SOTA accuracy are much better than the best performance shown in Table 1. I recommend the authors to check https://paperswithcode.com/area/graphs for SOTA performances.\n\nIt is very important because there are non-negligible accuracy gaps. For example, for Citeseer, there are a lot of models achieved more than 80% accuracy, but in Table 1, the best model achieved only around 71% accuracy. Same for Cora (90% vs 84%), Pubmed (91% vs 81%).\n\nI feel it would be better that the authors can evaluate the GraphPatcher on some SOTA models and evaluate the effect (improvement) of the proposed graph patching methods, rather than demonstrating improvements over some well-established models that is proposed years ago. It is crucial to understand the real-world value of the proposed methods in this fast-moving community.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer ZZgb,\n\nThank you for your valuable and kind feedback. We sincerely appreciate your acknowledgment of the motivation and reproducibility of our proposed framework. Our detailed response to your concerns is listed as follows:\n\n**[Baseline not strong]** \\\nThe baselines we compare GraphPatcher with are SoTA methods recently published on top venues (e.g., GTrans on ICLR’23, EERM and ColdBrew on ICLR’22, Tail-GNN on KDD’21, etc). We compare GraphPatcher with other test-time augmentation methods or cold-start/low-degree methods and evaluate by the relative improvement. \n\nBy strong baselines, we believe you mean strong backbone models. If this is the right interpretation, we have self-supervised methods that can perform better than early models like GCN. For these strong methods (i.e., Table 3), GraphPatcher can still consistently improve the performance, aligning with our observation in the main table. \n\nTo further address your concern, we explore the top model on the leaderboard (i.e., GRAND [1]) and apply GraphPatcher to it. As shown in the table below, GraphPatcher still enhances performance by a significant margin, with 1.5, 1.8, and 4.2 low-degree accuracy gains. Overall, GraphPatcher combined with GRAND can reach 85.9, 76.1, and 84.2 accuracy scores. The current SoTA scores are 85.5, 75.4, and 83.8 and we further improve them by 0.4, 0.7, and 0.4 accuracy scores, making **GraphPatcher the top 1 model on the leaderboard**. Please note that the leaderboard you were referring to is not the public split leaderboard. The correct one that aligns with our setting is “Cora/Citeseer/Pubmed with Public Split: fixed 20 nodes per class”. **We will update the leaderboard with the numbers we provide in this discussion** after the anonymous period and publicize the code.\n||Cora|Citeseer|Pubmed|\n|:-|:-:|:-:|:-:|\n|||Low-degree|||\n|GRAND|80.18±0.64|70.57±0.68|80.48±0.14|\n|+GraphPatcher|81.68±0.45|72.37±0.29|84.68±0.29|\n|||High-degree|||\n|GRAND|88.32±0.75|79.64±0.86|83.53±0.52|\n|+GraphPatcher|88.92±0.18|79.54±0.13|41.13±0.21|\n|||Overall|||\n|GRAND|85.22±0.80|74.90±0.77|82.30±0.41|\n|+GraphPatcher|85.90±0.44|76.10±0.38|84.20±0.26|\n\n[1] Wenzheng Feng et al. \"Graph random neural networks for semi-supervised learning on graphs.\" NeurIPS 2020.\n\n**[Connection to Iterative Graph Generation and Diffusion Models]** \\\nWe agree that our proposed framework is relevant to diffusion models and iterative graph generation models. Most graph generation frameworks (including those using diffusion models) explore iterative generation schemes to synthesize real graphs [1-7]. They improve the generation quality and focus on applications such as molecule design, protein design, and program synthesis. Though GraphPatcher also generates patching nodes for ego-graphs, ours is a different research direction than these methods. We do not focus on whether or not the generated patching nodes are faithful to the original data distribution, as long as the low-degree performance is enhanced and the high-degree performance is maintained. Another relevant work named GPT-GNN [8] explores an iterative node generation for pre-training, which also falls under the category of maintaining the original data distribution. In summary, GraphPatcher is relevant to these frameworks in the sense that it generates nodes to add to ego-graphs. However, our proposal is motivated by a different reason and we aim at the performance improvement brought by generated nodes in downstream tasks. Hence it is also difficult for us to directly compare GraphPatcher with these iterative generation models due to their different purposes and motivations. As for other diffusion models, we have detailed discussions in G1 in the general response. They are conceptually similar to this section but start from a more general point. \n\n**[Discussion on Auto-regressive Architecture]** \\\nThe architecture of GraphPatcher is auto-regressive where the node to be generated depends on previous generations. For mechanisms that terminate the generation like a stop token you mentioned, we believe it might be difficult in our setting. Unlike language generation where a sentence stops at its period, our node patching does not have such a ground truth. Right now we simply decide the generation length by the validation accuracy. A suitable heuristic could be the amount of changes (as measured in cosine similarity or other metrics) after a node patching. If the node representation stops updating with an additional node, then that indicates GraphPatcher is satisfied and the generation process could stop. We have not tested this idea yet and it might be a good further exploration. \n\nWe sincerely appreciate your suggestions. We will **accordingly modify the manuscript to clarify your concerns** when the anonymous period ends and we hope we have satisfactorily answered your questions. If so, could you please consider increasing your rating? If you have any remaining doubts or concerns, please let us know, and we will happily respond. Thank you! \n\nBest regards, \\\nGraphPatcher's authors\n\n[1] Yanqiao Zhu, et al. \"A survey on deep graph generation: Methods and applications.\" LOG’22\n\n[2] Jiaxuan You, et al.. \"Graphrnn: Generating realistic graphs with deep auto-regressive models.\" ICML’18\n\n[3] Nikhil Goyal et al. \"Graphgen: A scalable approach to domain-agnostic labeled graph generation.\"  WWW’22\n\n[4] Chenhao Niu, et al. \"Permutation invariant graph generation via score-based generative modeling.\" AISTATS’22.\n\n[5] Jaehyeong Jo et al.. \"Score-based generative modeling of graphs via the system of stochastic differential equations.\" ICML’22\n\n[6] Clement Vignac, et al. \"Digress: Discrete denoising diffusion for graph generation.\" ICLR’23\n\n[7] Meng Liu, et al. \"Graphebm: Molecular graph generation with energy-based models.\" EBM@ICLR’23\n\n[8] Ziniu Hu, et al. \"Gpt-gnn: Generative pre-training of graph neural networks.\" KDD’20\n"}, {"review_id": "98THS7R1u7", "reviewer": "Reviewer_Cs3J", "summary": "This paper addresses degree bias in node classification. The authors show that current methods suffer performance degradation for high-degree nodes. Thus, they freeze the original GNN and train GraphPatcher to enhance low-degree nodes with node patching in the testing stage. In the experiments, they demonstrate that their approach significantly improves performance without performance drop in high-degree nodes on various homophilous graphs. ", "questions": "- Following [W1], could you provide the comparison with baselines from the perspective of the training time (including vanilla GNN)? Also, it would be better to show memory usage in GPU when training GraphPatcher and baselines.\n- Following [W2], could you provide a performance comparison on heterophilous graphs?", "limitations": "As the authors mentioned, the additional computational cost might be considerable.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "- They exhibit that the existing approaches suffer performance drops in high-degree nodes.\n- Their method improves performance without performance degradation in high-degree nodes.", "weaknesses": "- [W1] From my understanding, it seems difficult to train in a node-parallel manner with a single large graph, as the graphs used by each node differ, unlike vanilla GNN training. Then, I’m concerned that training GraphPatcher might take an excessively long time.\n- [W2] The validation is only conducted on homophilous graphs.\n- [W3] I found that there is a performance drop for high-degree nodes on CiteSeer in Table 1. Is there any reason for this phenomenon?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer Cs3J,\n\nThank you for your valuable and kind feedback. We sincerely appreciate your acknowledgment of the good motivation and performance of our proposed framework. Our detailed response to your concerns is listed as follows:\n\n\n**[Node-parallel manner/Training time/Memory usage]** \\\nPlease refer to G3 in our general response for details. In summary, the training for GraphPatcher is fast and brings little extra computational overhead if we pre-compute all ego-graphs beforehand. With sufficient CPU cores, the training would be as fast even if we compute all ego-graphs on the fly, due to the \n\n**[Experiments over heterophilic datasets]** \\\nPlease refer to G2 in our general response for details. In summary, GraphPatcher exhibits similar trends for heterophilic datasets as we observe for homogeneous graphs. GraphPatcher improves the low-degree performance by 0.44 and 1.97 accuracy score and the overall performance by 0.38 and 1.14 on Chameleon and Actor respectively. Updated experiments over heterophilic datasets are included in our provided one-page pdf. We will update the final version of our paper with these additional experiments. \n\n\n**[Performance drop for high-degree nodes on Citeseer]** \\\nWe appreciate your attention to our experiments. We believe that the performance drop in Table 1 is a dataset-specific phenomenon. For instance, as you noticed, all models in Table 1 show sub-optimal performance for high-degree nodes in Citeseer. Most of the frameworks in this table explore graph convolution schemes similar to GCN. However, when the backbone model used is GraphSage, as shown in Table 2, both TuneUp and GraphPatcher improve Citeseer’s high-degree performance by 1.49 and 0.76 accuracy scores respectively. From these two ablations, we can conclude that the performance of high-degree nodes on Citeseer is sensitive to the model architecture.\n\nMoreover, when applied to self-supervised learning-based frameworks (even with GCN as the backbone model that does not favor high-degree nodes on Citeseer), both TuneUp and GraphPatcher can improve the high-degree performance, as demonstrated in Table 3. Hence, we can also conclude that the supervision signal (e.g., self-supervised learning vs. supervised learning) will also impact the high-degree performance. \n\nRecently, [1] discovers that there exist subgroups of nodes within each graph where different GNNs might exhibit distinct results, depending on factors such as the model architecture, supervision signal, etc. This paper might be a good reference for explanations of dataset-specific or subgroup-specific abnormal behaviors shown by different GNNs, and subgroup-level understanding is still an actively underexplored direction. \n\nWe sincerely appreciate your suggestions for our manuscript. We will **accordingly modify the manuscript to clarify your concerns** when the anonymous period ends and we hope we have satisfactorily answered your questions. If so, could you please consider increasing your rating? If you have any remaining doubts or concerns, please let us know, and we will happily respond. Thank you! \n\nBest regards, \\\nGraphPatcher's authors\n\n[1] Mao, Haitao, Zhikai Chen, Wei Jin, Haoyu Han, Yao Ma, Tong Zhao, Neil Shah, and Jiliang Tang. \"Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?.\" arXiv preprint arXiv:2306.01323 (2023)."}, {"review_id": "Zss4uPUJPk", "reviewer": "Reviewer_LJuX", "summary": "This paper addresses the issue of degree bias in node classification, which refers to the poorer performance of Graph Neural Network (GNN) models on nodes with lower degrees compared to the average level. While previous works have attempted to mitigate this bias, they often trade off the performance on higher-degree nodes for improvements on low-degree nodes. In light of this, the authors propose GraphPatcher, a method that introduces virtual nodes during the test phase to tackle this problem. To make the approach computationally feasible, the authors limit the search space to 1-order neighbors and devise an iterative procedure to repair a series of corrupted ego graphs by adding one virtual node at each step. Additionally, the authors provide theoretical results that establish the relationship between the number of sampled ego graphs and the accuracy of the estimated patching loss. The proposed GraphPatcher is extensively evaluated through experiments, demonstrating its effectiveness in addressing the degree bias issue.", "questions": "When working with graph samplers that are necessary for training on large graphs, whether we need a larger/smaller L?", "limitations": "None", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-written, allowing readers to easily grasp the core ideas and delve into the authors' detailed explanations.\n\n2. The motivation behind the proposed GraphPatcher is well-founded, as it intuitively aims to enhance overall performance rather than compromising it through trade-offs.\n\n4. The empirical evaluations consistently demonstrate the effectiveness of GraphPatcher, with statistically significant improvements observed. Furthermore, the increasing number of patched virtual nodes correlates with increasingly noticeable enhancements, providing strong support for the rationale behind the iterative procedure designed for GraphPatcher.", "weaknesses": "1. While the theoretical analysis provided in the paper is logically sound, its relevance to the community's primary concern of reducing the generalization risk of the original GNN model is unclear. Consequently, the presented theoretical results may not be perceived as a significant contribution.\n\n2. Although the experiments in the paper are well-designed, there is room for improvement in terms of comprehensiveness. For instance, the inclusion of more visually informative figures/tables showcasing the improvements across different degree levels would enhance the clarity of the results. Additionally, comparisons on heterophilic graphs would provide a more comprehensive evaluation. It is also important to consider evaluating the efficiency of GraphPatcher since it introduces additional computational overhead.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer LJuX,\n\nThank you for your valuable and kind feedback. We sincerely appreciate your acknowledgment of the good writing quality, motivation, and performance of our proposed framework. Our detailed response to your concerns is listed as follows:\n\n**[Relevance of our theoretical analysis]** \\\nWe appreciate your thoughtful consideration and valuable feedback. We recognize that the theorem we propose in our manuscript might not be directly applicable to any GNN in general. However, it is important to note that this theorem remains distinct from other GNNs, as it substantiates the iterative node patching and reconstruction processes, both of which are specifically tailored to our model. The significance of Theorem 1 lies in its demonstration that the upper bound of error for GraphPatcher can be notably reduced through the utilization of multiple sampled ego-graphs (i.e.,  Equation 5). We believe it serves as an important theoretical motivation for our sampling strategy. Along with the promising empirical results we have shown in our experiments, it further strengthens the credibility and substantiates the merits of our proposed GraphPatcher model.\n\n**[Performance on heterophilic datasets]** \\\nPlease refer to G2 in our general response for details. In summary, GraphPatcher exhibits similar trends for heterophilic datasets as we observe for homogeneous graphs. GraphPatcher improves the low-degree performance by 0.44 and 1.97 accuracy score and the overall performance by 0.38 and 1.14 on Chameleon and Actor respectively. Updated experiments over heterophilic datasets are included in our provided one-page pdf. We will update the final version of our paper with these additional experiments. \n\n\n**[Performance w.r.t. different degree levels]** \\\nThanks for raising this point -- we agree this would help clarify further where performance improvements are derived.  We have taken the liberty of incorporating additional plots into the one-page PDF that was submitted for the global rebuttal. In these new visuals, we meticulously analyze the performance of GCN, TuneUp, and GraphPatcher across a spectrum of 10 distinct degree ranges, ranging from the 0th to the 10th percentile, all the way up to the 90th to 100th percentile. Furthermore, we also include comparative graphs depicting the relative enhancements achieved by GraphPatcher and TuneUp in contrast to the baseline performance of GCN. These supplementary graphs exhibit consistent trends, mirroring the observations we made in the original manuscript regarding the coarse degree levels. Notably, GraphPatcher consistently showcases improvements in low-degree performance while concurrently preserving or even elevating high-degree performance. We appreciate your point and are looking forward  to incorporating these enlightening visuals into the appendix of our manuscript should it meet the criteria for acceptance. Your consideration of these additions would be greatly appreciated.\n\n\n**[Selection of L on large datasets]** \\\nIn the appendix (i.e., Figure 5 in Section B.2), we have presented GraphPatcher's performance in relation to the number of sampled graphs (referred to as L). Our observations indicate that consistently across all datasets, an L value below 10 tends to impact the overall performance. Notably, the performance reaches a saturation point at L=10, beyond which further increments in L do not yield discernible improvements across all datasets. As a result, we are led to the conclusion that, particularly when dealing with sizable graphs (such as the ogbn-arxiv dataset examined in this study), employing 10 sampled graphs is likely to yield promising and sufficient outcomes.\n\nWe sincerely appreciate your suggestions for our manuscript. We will **accordingly modify the manuscript to clarify your concerns** when the anonymous period ends and we hope we have satisfactorily answered your questions. If so, could you please consider increasing your rating? If you have any remaining doubts or concerns, please let us know, and we will happily respond. Thank you! \n\nBest regards, \\\nGraphPatcher's authors\n"}]

Author rebuttal:
Dear ACs and reviewers,

We thank the reviewers for their feedback and constructive suggestions. We are pleased that most reviewers appreciated **the promising effectiveness and performance of our framework**, e.g.: “simple with good performance” (xNZm), “method improves performance without performance degradation” (Cs3J), and “statistically significant improvements observed” (LJuX). Moreover, most reviewers also acknowledged **the good motivations behind our framework**, said: “the proposed method well motivated and natural” (ZZgb), “exhibit that the existing approaches suffer performance drops in high-degree nodes” (Cs3J), and “motivation behind the proposed GraphPatcher is well-founded” (LJuX). 

**[G1: Connection between diffusion models and GraphPatcher]** \
 At the same time, multiple reviewers asked about the connection between diffusion models and our GraphPatcher. We appreciate the insightful suggestions and agree that GraphPatcher is relevant to diffusion models. Both diffusion models and our proposal conduct multiple corruptions to the training samples with increasing strengths and generate examples in an iterative fashion. This scheme is conceptually inspired by heat diffusion from physics. However, the motivations behind them are different, where diffusion models focus on the generation quality (i.e., fidelity to the original data distribution) but ours aims at the results brought by our generated nodes (i.e., the performance improvement). Specifically, diffusion models aim at learning the probability distribution of the data and accordingly generating examples following the learned distribution. Their goal is to generate samples that follow the original data distribution (i.e., P(X)), agnostic of any other factor like the target GNN we have in our scenario. Whereas for GraphPatcher, we aim at generating nodes to ego-nets such that the target GNN models deliver better predictions (i.e., P(Y|X)) when the node degree is low. We mostly care about performance improvement and the generated node may be very different from the original nodes in the graph. 

**[G2: Experiments on heterophilic datasets]** \
Besides, reviewers also worried about GraphPatcher’s effectiveness over heterophilic graphs. We agree that incorporating heterophilic datasets would help us better understandGraphPatcher’s behavior, and also benefit readers. We have accordingly added experiments on two heterophilic datasets (i.e., Chameleon and Actor), with results shown in the table from our provided one-page pdf.  One interesting behavior of these two heterophilic datasets is that even though the degree distribution is power-law, GNN’s performance doesn’t downgrade much on low-degree nodes compared with the performance on high-degree nodes. As shown in the table, GCN’s performances on low- and high-degree percentiles are pretty close. On these two heterophilic datasets, GraphPatcher universally improves GNN’s performance across all degrees. Specifically, GraphPatcher improves the low-degree performance by 0.44 and 1.97 accuracy score and the overall performance by 0.38 and 1.14 on Chameleon and Actor respectively. 

**[G3: Efficiency and running time]** \
Some reviewers raised concerns about the efficiency and running time of our proposed GraphPatcher. While designing GraphPatcher, we paid attention to its scalability and potential applications to industrial pipelines, which is one of the reasons why we explore the ego-net design. In a single forward pass, we only generate a fixed number of ego-graphs (i.e., mostly 16 or 64 ego-graphs per batch across our experiments) for the back-propagation. In this setting with small batch sizes, GraphPatcher can already deliver good performance improvements to target GNN models with light GPU usage and little computational overhead compared with baselines, with the GPU usage and running time shown in the table below. 
|||TuneUp|Tail-GNN|GraphPatcher|
|:-|:-:|:-:|:-:|:-:|
| | |Cora | | ||
| Training Time (s) | 2.3 |17.7|14.5|8.1|
| Train+Eval Time (s)| 2.3|17.7|14.5| 13.3 (34.8)|
|GPU Consumption (GB)| 1.4|2.0|1.6|3.1|
| | |Citeseer         | | ||
| Training Time (s) | 2.6 |9.7|35.4|8.3|
| Train+Eval Time (s)| 2.6|9.7|35.4|12.1 (32.3)|
|GPU Consumption (GB)| 1.4|1.5|3.8|2.2|
| | |Pubmed         | | ||
| Training Time (s) | 3.2 |17.3|47.6|9.1|
| Train+Eval Time (s)| 3.21|17.3|47.6|14.4 (36.9)|
|GPU Consumption (GB)| 1.6|1.7|1.9|3.4|

The training for GraphPatcher is fast and brings little extra computational overhead. When all the evaluation ego-graphs are pre-computed beforehand, the total running times for Cora, Citeseer, and Pubmed are under 15 seconds (i.e., 13.3, 12.1, and 14.4 seconds). However, as we mentioned in the limitation section, if evaluation ego-graphs are extracted on the fly, the running time will be jeopardized (i.e., 34.8, 32.3, and 36.9 for these three datasets). This issue can be easily resolved by using more CPU cores as this step is embarrassingly parallelizable (currently we only use 24 cores). With sufficient CPU cores, the batch loading time would be close to the time needed to extract 1 ego-net, which only brings neglectable overhead compared with loading them from the disk.

We will **accordingly modify the manuscript to clarify your concerns** when the anonymous period ends, and we hope we have satisfactorily answered your questions. If so, could you please consider increasing your rating? If you have any remaining doubts or concerns, please let us know, and we will happily respond. Thank you! 

Best regards,\
GraphPatcher's authors


Meta-review: This paper proposes an interesting and novel technique for ameliorating the degree bias issue in GNNs, leading to measurable improvements in performance. While the reviewers initially pointed out several limitations in the work as presented, the Authors have put together a very convincing rebuttal, which led to a unanimously positive assessment of the paper. I congratulate the authors for their efforts, and recommend this paper for acceptance without reserve.
Decision: Accept (poster)