#  GraphPatcher: Mitigating Degree Bias for
Graph Neural Networks via Test-time Augmentation

Mingxuan Ju1, Tong Zhao2, Wenhao Yu1, Neil Shah2, Yanfang Ye1
1University of Notre Dame, 2Snap Inc.
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### 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.

##  1 Introduction

Graph Neural Networks (GNNs) have gained significant popularity as a powerful
approach for learning representations of graphs, achieving state-of-the-art
performance on 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 as
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
be 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 be 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 $\sim$20% accuracy. Furthermore, the sub-optimal
performance of GNNs on low-degree nodes can be 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].

Figure 1: The classification accuracy of GCN and SoTA frameworks that mitigate
degree biases.

To bridge this gap, several frameworks have been proposed to specifically
improve GNNs’ performance on low-degree nodes [36, 25, 13, 55, 49]. These
frameworks either introduce designated architectures or training strategies
specifically for low-degree nodes. For examples, Tail-GNN [25] enhances latent
representations of low-degree nodes by incorporating high-degree structural
information; whereas Coldbrew [55] retrieves a set of existing nodes as
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
training [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 to 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, we propose a test-time augmentation framework for
GNNs, namely GraphPatcher. Given a well-trained GNN, GraphPatcher mitigates
the degree bias by patching corrupted 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 to 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 a test-time augmentation framework,
GraphPatcher is parameterized in parallel with the target GNN. Hence,
GraphPatcher is model-agnostic and requires no updates on the target GNN,
enabling practitioners to easily utilize it as a plug-and-play 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 are considered. In this case, a
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, GraphPatcher
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, a plug-
and-play module that is easily applicable to 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 state-of-the-art baselines.

##  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 as 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, 3], predictive user behavior
models [31, 52], question answering [18], and molecular 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 as
virtual neighbors for low-degree nodes; TuneUp [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-of-
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 out-of-distribution scenarios.

##  3 Methodology

###  3.1 Preliminary

In this work, we specifically focus on the node classification task. Let
$G=(V,E)$ denote a graph, where $V$ is the set of $|V|=N$ nodes and
$E\subseteq V\times V$ is the set of $|E|$ edges between nodes.
$\mathbf{X}\in\mathbb{R}^{N\times d}$ represents the feature matrix, with
$i$-th row representing node $v_{i}$’s $d$-dimensional feature vector.
$\mathbf{Y}\subseteq\\{0,1\\}^{N\times C}$ denotes the label matrix, where $C$
is the number of total classes. And $\mathbf{Y}^{(L)}$ denotes the label
matrix for training nodes. We denote the ego-graph of node $v_{i}$ is defined
as $\mathcal{G}(v_{i})=(V_{i},E_{i})$ with $V_{i}=\mathcal{N}_{k}(v_{i})$,
where $\mathcal{N}_{k}(v_{i})$ stands for all nodes within the $k$-hop
neighborhood of $v_{i}$ including itself and $E_{i}$ refers to the edges in-
between $\mathcal{N}_{k}(v_{i})$. A well-trained GNN
$f_{g}(\cdot;\bm{\theta}):G\rightarrow\mathbb{R}^{N\times C}$ parameterized by
$\bm{\theta}$ takes $G$ as input and maps every node in $G$ 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 $f_{g}(\cdot;\bm{\theta})$ and a graph G, a test-time node
patching framework $f(\cdot;\bm{\phi}):G\rightarrow G$ takes $G$ and outputs
the patched graph $\hat{G}$ with generated nodes and edges, such that the
performance of $f_{g}$ over nodes in $G$ is enhanced when $\hat{G}$ is
utilized:

$\arg\min_{\bm{\phi}}\;\mathcal{L}\Big{(}f_{g}\big{(}f(G;\phi);\bm{\theta}^{*}\big{)},\mathbf{Y}\Big{)},\quad\text{where}\quad\bm{\theta}^{*}=\arg\min_{\bm{\theta}}\mathcal{L}\big{(}f_{g}(G;\bm{\theta}),\;\mathbf{Y}^{(L)}\big{)},$
(1)

where $\mathcal{L}$ 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 $f(\cdot;\bm{\phi})$, such that the graphs patched by
$f(\cdot;\bm{\phi})$ enhance the performance of $f_{g}(\cdot;\bm{\theta}^{*})$
over low-degree nodes; and (2) how to derive a unified learning scheme that
allows $f(\cdot;\bm{\phi})$ to not only improve low-degree nodes but also
maintain the GNN’s original superiority over high-degree nodes.

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 a test-time augmentation framework for GNNs to
mitigate their degree biases. As shown in Figure 2, 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 to patch low-degree nodes, a 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-passing mechanism of GNNs
as well as the non-i.i.d. property of nodes in a graph. Besides, modeling over
the entire graphs requires 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.

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.i.d. sample of the anchor node [56, 19]. For each node
$v_{i}$, we have
$f_{g}(G;\bm{\theta})[v_{i}]=f_{g}(\mathcal{G}(v_{i});\bm{\theta})[v_{i}]$ if
$k$ equals to the number of layers in $f_{g}(\cdot;\bm{\theta})$. 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 a trained GNN
$f_{g}(\cdot;\bm{\theta}^{*})$, an anchor node $v_{i}$, and a corruption
function $\mathcal{T}(\cdot;t)$ with strength $t$ (i.e., first-order neighbor
dropping with probability $t$ to simulate a low-degree scenario), that is,
$\mathcal{G}^{\prime}(v_{i})=(V^{\prime}(v_{i}),E^{\prime}(v_{i}))=\mathcal{T}(\mathcal{G}(v_{i}),t)$.
GraphPatcher $f(\cdot;\bm{\phi})$ takes the corrupted ego-graph
$\mathcal{G}^{\prime}(v_{i})$ as input and outputs the augmented ego-graph
$\hat{\mathcal{G}}(v_{i})$ with a patching node $v_{p}$ and its feature
$\mathbf{x}_{p}$, which is directly connected to $v_{i}$. That is,

$\hat{\mathcal{G}}(v_{i})=f(\mathcal{G}^{\prime}(v_{i});\bm{\phi}),\;\;\text{where}\;\;\hat{V}=V^{\prime}(v_{i})\cup\\{v_{p}\\},\;\;\hat{E}=E^{\prime}(v_{i})\cup\\{e_{(i,p)}\\},$
(2)

where $e_{(i,p)}$ refers to the edge connecting $v_{i}$ and $v_{p}$ and
$V^{\prime}(v_{i})$ and $E^{\prime}(v_{i})$ refer to the nodes and edges in
$\mathcal{G}^{\prime}(v_{i})$, respectively. To optimize $f(\cdot:\bm{\phi})$
such that $f_{g}(\cdot;\bm{\theta}^{*})$ gives similar predictions to
$\hat{\mathcal{G}}^{\prime}(v_{i})$ and $\mathcal{G}(v_{i})$, we minimize the
Kullback–Leibler divergence between the frozen GNN’s predictions on these two
ego-graphs, which is defined as:

$\arg\min_{\bm{\phi}}\;\sum_{v_{i}\in V_{\text{tr}}}\text{KL-
Div}\Big{(}f_{g}\big{(}\mathcal{G}(v_{i});\bm{\theta}^{*}\big{)}[v_{i}],f_{g}\big{(}f(\mathcal{G}^{\prime}(v_{i});\bm{\phi});\bm{\theta}^{*}\big{)}[v_{i}]\Big{)},$
(3)

where $\text{KL-
Div}(\mathbf{y}_{1},\mathbf{y}_{2})=(\mathbf{y}_{1}+\epsilon)\cdot\big{(}\log(\mathbf{y}_{2}+\epsilon)-\log(\mathbf{y}_{1}+\epsilon)\big{)}$111KL
divergence used here is equal to the regularized cross-entropy. It is strongly
convex and Lipschitz continuous due to the incorporation of $\epsilon$. These
two properties are required for the derivation of Theorem 1. with $\epsilon>0$
and $V_{\text{tr}}$ refers to the set of anchor nodes for training.
Intuitively, the reconstruction process above enforces GraphPatcher to remedy
the corrupted neighborhood caused by $\mathcal{T}(\cdot;t)$ via adding a
patching node directly to 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, it falls short on the high-degree node that original GNNs
perform well at. This phenomenon may be attributed to the unintentially
created out-of-distribution 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.

####  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 a new bias towards high-
degree nodes. Therefore, besides enhancing the performance on low-degree
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 a lack of robustness: further remedying a
neighborhood that is informative enough to deliver a good classification
result should not jeopardize the performance.

To mitigate the degree bias, we propose a novel training scheme for
GraphPatcher such that it observes both low- and high-degree nodes
simultaneously during the optimization. Specifically, given a node $v_{i}$, we
firstly create a sequence of $M$ corrupted ego-graphs of $v_{i}$, denoted as
$\mathcal{S}(v_{i})=[\mathcal{G}^{\prime}(v_{i})_{m}=\mathcal{T}(\mathcal{G}(v_{i}),t_{m})]_{m=1}^{M}$,
with decreasing corruption strength (i.e., $\forall\;m,n\in\\{1,\dots,M\\}$,
$t_{m}>t_{n}$ 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 $\mathcal{S}(v_{i})$ 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:

$\displaystyle\arg\min_{\bm{\phi}}\;\sum_{v_{i}\in
V_{\text{tr}}}\sum_{m=1}^{M-1}$ $\displaystyle\text{KL-
Div}\Big{(}f_{g}\big{(}\mathcal{G}^{\prime}(v_{i})_{m+1};\bm{\theta}^{*}\big{)}[v_{i}],f_{g}(\hat{\mathcal{G}}(v_{i})_{m};\bm{\theta}^{*})[v_{i}]\Big{)},$
(4)
$\displaystyle\text{s.t.}\;\;\hat{\mathcal{G}}(v_{i})_{m}=f(\hat{\mathcal{G}}(v_{i})_{m-1};\bm{\phi}),$

where $\hat{\mathcal{G}}(v_{i})_{m}=(\hat{V}_{m},\hat{E}_{m})$ with
$\hat{V}_{m}=V^{\prime}_{1}(v_{i})\cup\\{v_{p}\\}_{p=1}^{m}$,
$\hat{E}_{m}=E^{\prime}_{1}(v_{i})\cup\\{e_{(i,p)}\\}_{p=1}^{m}$, and
$\hat{\mathcal{G}}(v_{i})_{0}=\mathcal{G}^{\prime}(v_{i})_{1}$.

The one-step patching described in Section 3.2.1 remedies low-degree anchor
nodes directly to 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 GraphPatcher to be an
iterative multi-step framework. At each step, it takes the previously patched
ego-graph as input and further remedies the partially patched ego-graph to
match the GNN’s prediction 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 $\hat{\mathcal{G}}(v_{i})_{m}$
reflects the neighbor distribution of ego-graphs corrupted by a specific
strength of $t_{m+1}$. GraphPatcher takes $\hat{\mathcal{G}}(v_{i})_{m}$ as
input and further generates another patching node $v_{m+1}$ to approach the
neighbor distribution of ego-graphs corrupted by a slightly weaker strength of
$t_{m+2}$. This process iterates until GraphPatcher traverses
$\mathcal{S}(v_{i})$. Intuitively, the incorporation of $v_{m+1}$ enriches the
neighbor distribution by an amount of $t_{m+2}-t_{m+1}$ corruption strength.
This optimization 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.,
$f_{g}\big{(}\mathcal{G}^{\prime}(v_{i})_{m+1};\bm{\theta}\big{)}[v_{i}]$ in
Equation 4) is not deterministic due to the stochastic nature of the
corruption function $\mathcal{T}$. Given an ego-graph $\mathcal{G}(v_{i})$ and
a corruption strength $t$, one can at most generate
${|V_{i}|\choose(1-t)|V_{i}|}$ different corrupted ego-graphs. With a large
corruption strength (e.g., ego-graphs early in the sequence
$\mathcal{S}(v_{i})$), 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 $L$
ego-graphs with the same corruption strength and let GraphPatcher approximate
multiple predictions over them, formulated as:

$\mathcal{L}_{\text{patch}}=\sum_{v_{i}\in
V_{\text{tr}}}\sum_{m=1}^{M-1}\sum_{l=1}^{L}\text{KL-
Div}\Big{(}f_{g}\big{(}\mathcal{G}^{\prime}(v_{i})_{m+1}^{l};\bm{\theta}^{*}\big{)}[v_{i}],f_{g}\big{(}\hat{\mathcal{G}}(v_{i})_{m};\bm{\theta}^{*}\big{)}[v_{i}]\Big{)},$
(5)

where
$\hat{\mathcal{G}}(v_{i})_{m}=f(\hat{\mathcal{G}}(v_{i})_{m-1};\bm{\phi})$ and
$\mathcal{G}^{\prime}(v_{i})_{m+1}^{l}$ 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-1$ virtual nodes patched to the ego-graph, we further ask GraphPatcher
to generate a last patching node to $\hat{\mathcal{G}}(v_{i})_{M-1}$ and
enforce the resulted graph $\hat{\mathcal{G}}^{\prime}(v_{i})_{M}$ to match
the GNN’s prediction on the original ego-graph. The last patching node could
be regarded as a slack variable to complement minor differences between the
original and the least corrupted ego-graphs, formulated as:

$\mathcal{L}_{\text{recon}}=\sum_{v_{i}\in V_{\text{tr}}}\text{KL-
Div}\Big{(}f_{g}\big{(}\mathcal{G}(v_{i});\bm{\theta}^{*}\big{)}[v_{i}],f_{g}\big{(}\hat{\mathcal{G}}(v_{i})_{M};\bm{\theta}^{*}\big{)}[v_{i}]\Big{)},$
(6)

where
$\hat{\mathcal{G}}(v_{i})_{M}=f(\hat{\mathcal{G}}(v_{i})_{M-1};\bm{\phi})$.
$\mathcal{L}_{\text{recon}}$ (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, GraphPatcher is optimized by a linear combination of the above two
objectives (i.e.,
$\arg\min_{\bm{\phi}}\mathcal{L}_{\text{patch}}+\mathcal{L}_{\text{recon}}$).

####  3.2.3 Theoretical Analysis

As shown in Equation 5, one of the important factors that contribute to the
success of GraphPatcher is sampling multiple ego-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
$P_{\beta}=\\{\bm{\phi}:||\bm{\phi}-\mathcal{N}(\mathbf{0}_{|\bm{\phi}|};\mathbf{1}_{|\bm{\phi}|})||_{F}<\beta\\}$
where $\beta>0$, with probability at least $1-\delta$ for all $\bm{\phi}\in
P_{\beta}$, the error (i.e.,
$\mathbb{E}(\mathcal{L}_{\text{patch}})-\mathcal{L}_{\text{patch}}$) is
bounded by
$\mathcal{O}(\beta\sqrt{\frac{|\bm{\phi}|}{L}}+\sqrt{\frac{\log(1/\beta)}{L}})$.

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., $|\bm{\phi}|$) 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, an affordable value of $L$ (e.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, Amazon-Photo, Coauthor-CS, ogbn-arxiv, Actor, and
Chameleon [44, 28, 12, 33]. This list of datasets covers graphs with
distinctive characteristics (i.e., graphs with different domains and
dimensions) to fully evaluate the effectiveness of GraphPatcher. The detail of
these datasets can be found in Appendix A.

Baselines. We compare GraphPatcher with six state-of-the-art graph learning
frameworks from three branches. The first branch specifically aims at
enhancing the performance on low-degree nodes, including Tail-GNN [25],
ColbBrew [55], and TuneUp [13]. The second branch consists of frameworks that
focus on handling out-of-distribution 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 GraphPatcher 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-arxiv, Cora, Citeseer, and Pubmed), we employ their the
provided splits for the model training and testing. Whereas for other
datasets, we create a random 10$\%$/10$\%$/80$\%$ split for the
training/validation/testing split, to simulate 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, GraphPatcher is also applicable to self-supervised GNNs.
To evaluate the model performance for them, we apply GraphPatcher 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.

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. Hyper-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.

Table 1: 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. A 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 | Cora | Citeseer | Pubmed | Wiki.CS | Am.Photo | Co.CS | Arxiv | Chameleon | Actor
---|---|---|---|---|---|---|---|---|---
Accuracy on Low-degree Nodes (Lower Percentile)
GCN | 73.27±0.01 | 64.86±0.92 | 76.88±0.40 | 72.98±0.50 | 75.59±0.43 | 84.59±0.45 | 63.15±0.13 | 54.05±0.18 | 27.30±0.52
ColbBrew | 73.82±0.98 | 65.60±0.08 | 77.72±0.63 | 73.98±0.52 | 76.18±0.80 | 85.56±0.69 | 63.02±0.21 | 53.41±0.22 |  27.88±0.13
Tail-GNN | 71.17±0.80 | 57.66±0.83 | 75.38±0.89 | 74.36±0.18 | 77.22±0.94 | 85.13±0.60 | OOM | 53.48±0.04 | 27.80±0.62
TuneUp | 74.47±0.34 | 65.17±0.22 | 77.18±0.39 | 72.60±0.75 | 76.08±0.62 | 84.68±0.50 | 63.34±0.32 | 53.87±0.43 | 27.94±0.14
EERM | 73.40±0.06 | 64.27±0.33 | 76.30±0.20 | 73.12±0.68 | 75.15±0.59 | 84.82±0.74 | 63.20±0.11 |  54.11±0.32 | 27.48±0.39
GTrans | 73.16±0.66 | 64.95±0.83 | 77.05±1.00 | 72.15±0.50 | 75.55±0.55 | 84.74±0.06 | 62.88±0.14 | 54.29±0.14 | 27.53±0.21
DropEdge | 73.57±0.97 | 65.47±0.27 | 75.68±0.82 | 73.94±0.20 | 76.49±0.03 | 84.31±0.33 | 61.33±0.33 | 54.12±0.41 | 27.39±0.24
GraphPatcher | 78.08±0.06 | 67.27±0.20 | 78.98±0.21 | 74.04±0.86 | 77.84±0.36 | 86.76±0.84 | 64.01±0.12 | 54.48±0.71 | 29.27±0.57
Accuracy on High-degree Nodes (Upper Percentile)
GCN | 86.83±0.17 | 77.25±1.00 | 80.84±0.76 | 83.40±0.70 | 84.07±0.71 | 90.20±0.37 | 80.46±0.18 | 54.11±0.73 | 27.41±0.29
ColbBrew | 84.80±0.04 | 75.33±0.84 | 78.66±0.38 | 71.98±0.95 | 77.07±0.14 | 82.16±0.39 | 70.57±0.36 | 53.72±0.48 | 26.67±0.29
Tail-GNN | 84.13±0.48 | 74.85±0.30 | 78.74±0.34 | 78.91±0.97 | 80.32±0.60 | 86.75±0.90 | OOM | 54.53±0.12 | 27.13±0.44
TuneUp | 87.13±0.67 | 76.95±0.63 | 81.74±0.49 | 83.11±0.53 | 81.57±0.07 | 90.65±0.86 | 80.09±0.51 | 54.25±0.59 | 26.64±0.71
EERM | 85.89±0.09 | 76.32±0.23 | 79.98±0.06 | 82.98±0.07 | 84.32±0.96 | 90.17±0.11 | 80.37±0.12 |  54.41±0.71 |  27.39±0.14
GTrans | 86.32±0.34 | 76.60±0.44 | 80.56±0.92 | 83.42±0.04 | 83.95±0.99 | 89.99±0.10 | 80.77±0.26 | 54.21±0.19 | 27.29±0.12
DropEdge | 86.53±0.99 | 76.35±0.17 | 81.44±0.51 | 83.37±0.43 | 84.97±0.56 | 89.28±0.08 | 80.64±0.36 | 54.17±0.11 | 27.38±0.21
GraphPatcher | 88.02±0.11 | 76.65±0.18 | 83.83±0.79 | 83.49±0.22 | 84.17±0.97 | 90.59±0.46 | 80.61±0.25 | 54.20±0.21 | 27.43±0.62
Overall Performance
GCN | 81.22±0.40 | 70.51±0.46 | 79.14±0.31 | 77.30±0.41 | 80.38±0.86 | 88.16±0.66 | 71.73±0.14 | 52.83±0.35 | 27.20±0.57
ColbBrew | 80.70±0.86 | 70.10±0.55 | 78.66±0.93 | 73.82±0.69 | 78.24±0.62 | 85.80±0.79 | 63.55±0.48 | 52.12±0.53 | 26.75±0.32
Tail-GNN | 79.44±0.64 | 65.80±0.04 | 76.14±0.25 | 74.66±0.18 | 80.68±0.58 | 87.02±0.33 | OOM | 52.46±0.12 |  27.62±0.47
TuneUp | 82.11±0.39 | 70.92±0.02 | 79.91±0.26 | 76.93±0.81 | 79.74±0.28 | 88.46±0.97 | 71.51±0.30 | 52.89±0.41 | 27.32±0.64
EERM | 81.47±0.19 | 70.08±0.19 | 78.65±0.43 | 77.29±0.96 | 79.79±0.61 | 88.07±0.30 | 71.70±0.18 |  52.93±0.24 | 27.65±0.29
GTrans | 80.79±0.51 | 69.51±0.93 | 78.67±0.93 | 76.39±0.27 | 80.02±0.80 | 88.06±0.96 | 71.77±0.19 | 52.67±0.35 | 26.93±0.41
DropEdge | 81.10±0.31 | 71.10±0.86 | 78.90±0.68 | 77.49±0.78 | 81.11±0.72 | 87.56±0.64 | 71.82±0.33 | 52.89±0.22 | 27.28±0.32
GraphPatcher | 84.17±0.54 | 71.65±0.05 | 81.13±0.68 | 78.12±0.57 | 81.23±0.32 | 89.44±0.79 | 72.31±0.22 | 53.21±0.39 | 28.34±0.24

###  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 on low-degree nodes are $\sim$10% 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 ColbBrew, 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 on Cora by Tail-GNN, -11.42% on 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, we notice that our proposed GraphPatcher
consistently improves the low-degree performance 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
original high-degree superiority, due to our iterative node patching. On
average, GraphPatcher improves GCN’s overall performance by a 1.4 accuracy
score across datasets.

Table 2: Performance (%) of GraphPatcher and TuneUp for different GNN
architectures.

Method | Cora | Citeseer | Pubmed | Wiki.CS | Am.Photo | Co.CS | Arxiv
---|---|---|---|---|---|---|---
Accuracy on Low-degree Nodes (Lower Percentile)
GCN | 73.27±0.01 | 64.86±0.92 | 76.88±0.40 | 72.98±0.50 | 75.59±0.43 | 84.59±0.45 | 63.15±0.13
+TuneUp | 74.47±0.34 | 65.17±0.22 | 77.18±0.39 | 72.60±0.75 | 76.08±0.62 | 84.68±0.50 | 63.34±0.32
+GraphPatcher | 78.08±0.06 | 67.27±0.20 | 78.98±0.21 | 74.04±0.86 | 77.84±0.36 | 86.76±0.84 | 64.01±0.12
G-Sage | 70.57±0.84 | 67.44±0.11 | 76.58±0.36 | 61.83±0.89 | 76.32±0.33 | 74.53±0.69 | 61.64±0.62
+TuneUp | 71.47±0.11 | 67.44±0.21 | 77.78±0.92 | 58.46±0.77 | 78.48±0.89 | 74.88±0.76 | 62.43±0.59
+GraphPatcher | 72.33±0.21 | 67.89±0.33 | 78.93±0.05 | 61.46±0.40 | 78.11±0.13 | 75.14±0.21 | 62.92±0.28
GAT | 73.27±0.51 | 69.07±0.11 | 72.37±0.27 | 73.72±0.64 | 79.66±0.58 | 86.93±0.50 | 63.54±0.20
+TuneUp | 76.58±0.07 | 66.67±0.33 | 72.07±0.81 | 72.08±0.20 | 81.08±0.25 | 86.72±0.84 | 63.71±0.31
+GraphPatcher | 76.88±0.32 | 70.87±0.78 | 74.47±0.63 | 74.26±0.72 | 80.05±0.19 | 89.50±0.93 | 64.12±0.14
Accuracy on High-degree Nodes (Upper Percentile)
GCN | 86.83±0.17 | 77.25±1.00 | 80.84±0.76 | 83.40±0.70 | 84.07±0.71 | 90.20±0.37 | 80.46±0.18
+TuneUp | 87.13±0.67 | 76.95±0.63 | 81.74±0.49 | 83.11±0.53 | 81.57±0.07 | 90.65±0.86 | 80.09±0.51
+GraphPatcher | 88.02±0.11 | 76.65±0.18 | 83.83±0.79 | 83.49±0.22 | 84.17±0.97 | 90.59±0.46 | 80.61±0.25
G-Sage | 82.04±0.01 | 72.46±0.70 | 80.24±0.12 | 60.83±0.18 | 77.30±0.56 | 69.24±0.55 | 78.66±0.08
+TuneUp | 80.84±0.36 | 73.95±0.36 | 81.14±0.41 | 60.90±0.05 | 79.36±0.89 | 70.12±0.25 | 79.26±0.51
+GraphPatcher | 82.14±0.48 | 73.22±0.25 | 81.66±0.46 | 61.02±0.44 | 78.57±0.14 | 70.53±0.68 | 79.91±0.31
GAT | 85.33±0.36 | 76.65±0.80 | 81.14±0.20 | 82.21±0.44 | 87.84±0.23 | 91.33±0.81 | 81.37±0.16
+TuneUp | 86.23±0.47 | 76.65±0.33 | 80.84±0.02 | 81.73±0.36 | 89.02±0.78 | 92.00±0.04 | 81.44±0.11
+GraphPatcher | 86.53±0.37 | 76.35±0.39 | 81.14±0.89 | 82.34±0.08 | 87.84±0.56 | 91.61±0.20 | 81.49±0.15

We further apply GraphPatcher 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 a performance gap between
low- and high-degree nodes around $\sim$10%. 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 a large margin.

###  4.3 Performance of GraphPatcher for Self-supervised GNNs

Table 3: Effectiveness for self-supervised GNNs.

Method | Cora | Pubmed | Wiki.CS
---|---|---|---
Low-degree Nodes (Lower Percentile)
DGI | 78.47±0.37 | 75.63±0.82 | 75.86±0.61
+GraphPatcher | 79.95±0.53 | 78.04±0.97 | 77.31±0.91
GRACE | 77.81±0.73 | 77.80±0.65 | 74.31±0.63
+GraphPatcher | 78.53±0.82 | 78.49±0.16 | 75.12±0.34
ParetoGNN | 78.85±0.71 | 78.32±0.33 | 74.17±0.18
+GraphPatcher | 79.91±0.62 | 79.11±0.89 | 76.41±0.22
High-degree Nodes (Upper Percentile)
DGI | 86.83±0.82 | 81.14±0.28 | 81.09±0.81
+GraphPatcher | 86.91±0.10 | 82.31±0.53 | 80.95±0.19
GRACE | 85.03±0.05 | 78.74±0.84 | 83.91±0.56
+GraphPatcher | 85.12±0.25 | 79.58±0.31 | 84.12±0.22
ParetoGNN | 87.03±0.84 | 80.89±0.84 | 81.57±0.84
+GraphPatcher | 87.32±0.27 | 80.55±0.32 | 81.78±0.51

To fully demonstrate the effectiveness of GraphPatcher, we also apply our
proposal to self-supervised GNNs, as shown in Table 3. 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 GraphPatcher, 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 accuracy scores respectively.

###  4.4 Effectiveness of GraphPatcher for Enhancing SoTA Method

Table 4: Effectiveness for SoTA.

Method | Cora | Citeseer | Pubmed
---|---|---|---
Low-degree Nodes (Lower Percentile)
GRAND | 80.18±0.64 | 70.57±0.68 | 80.48±0.14
+GraphPatcher | 81.58±0.45 | 72.73±0.29 | 84.68±0.29
High-degree Nodes (Upper Percentile)
GRAND | 88.32±0.75 | 79.64±0.86 | 83.53±0.52
+GraphPatcher | 88.92±0.18 | 79.54±0.13 | 84.43±0.21
Overall Performance
GRAND | 85.22±0.80 | 74.90±0.77 | 82.30±0.41
+GraphPatcher | 85.90±0.44 | 76.10±0.38 | 84.20±0.26

We apply GraphPatcher to GRAND [5], a strong GNN that utilizes a random
propagation strategy to perform graph data augmentation and significantly
improve the node classification performance. The performance improvement
brought by GraphPatcher is shown in Table 4. We observe that GraphPatcher can
still consistently improve the node classification for GRAND. Specifically, on
low-degree nodes, GraphPatcher can improve 1.40, 2.23, and 4.20 accuracy score
on Cora, Citeseer, and Pubmed, respectively. Overall, GraphPatcher further
enhances the SoTA performance on these three datasets, with an outstanding
accuracy score of 85.90, 76.10, and 84.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

Figure 3: Overall perf. (y-axis) w.r.t. the number of patching nodes (x-axis).

To investigate the necessity of patching multiple nodes, we conduct
experiments over the number of patching nodes at 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 of low-degree nodes.
Besides, we discover that the performance of GraphPatcher saturates with
around four nodes patched, which aligns with our training procedure, where the
length of the ego-graph sequence is at most five. Experiments concerning the
number of patching nodes during the optimization and the number of sampled
ego-graphs per corruption strength (i.e., $M$ and $L$ in Equation 5) can be
found in Appendix B.

##  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
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 [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
GraphPatcher, we aim at generating nodes to ego-nets such that the target GNN
models deliver better predictions 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.

##  6 Discussion w.r.t. Generation Methods for Graph

Most graph generation frameworks (including those using diffusion models)
explore iterative generation 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 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 [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 we
aim at 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 augmentation 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 performance by up to 3.6% and low-degree
performance by up to 6.5%, outperforming all baselines by a 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-art
performance (i.e., GRAND), GraphPatcher can further improve the SoTA
performance by a large margin, indicating that the effectiveness brought by
the test-time augmentation is 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-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.t. iterative
generation models for graphs). This work is partially supported by the NSF
under grants IIS-2334193, IIS-2321504, IIS-2203262, IIS-2214376, IIS-2217239,
OAC-2218762, CNS-2203261, and CMMI-2146076. 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.

## References

  * Ayhan and Berens [2018] 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.
  * Bianchi et al. [2020] Filippo Maria Bianchi, Daniele Grattarola, and Cesare Alippi.  Spectral clustering with graph neural networks for graph pooling.  In _Procs. of ICML_ , 2020.
  * Fan et al. [2019] Wenqi Fan, Yao Ma, Qing Li, Yuan He, Eric Zhao, Jiliang Tang, and Dawei Yin.  Graph neural networks for social recommendation.  In _Procs. of WWW_ , 2019.
  * Fan et al. [2022] Yujie Fan, Mingxuan Ju, Chuxu Zhang, and Yanfang Ye.  Heterogeneous temporal graph neural network.  In _Procs. of SDM_ , 2022.
  * Feng et al. [2020] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang.  Graph random neural networks for semi-supervised learning on graphs.  _Procs. of NeurIPS_ , 2020.
  * Goyal et al. [2020] Nikhil Goyal, Harsh Vardhan Jain, and Sayan Ranu.  Graphgen: A scalable approach to domain-agnostic labeled graph generation.  In _Procs. of WWW_ , 2020.
  * Guo et al. [2021] 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.
  * Guo et al. [2023] Zhichun Guo, William Shiao, Shichang Zhang, Yozen Liu, Nitesh V Chawla, Neil Shah, and Tong Zhao.  Linkless link prediction via relational distillation.  In _Procs. of ICML_ , 2023.
  * Hamilton et al. [2017] William L Hamilton, Rex Ying, and Jure Leskovec.  Inductive representation learning on large graphs.  In _Procs. of NeurIPS_ , 2017.
  * Ho et al. [2020] Jonathan Ho, Ajay Jain, and Pieter Abbeel.  Denoising diffusion probabilistic models.  _Procs. of NeurIPS_ , 2020.
  * Hu et al. [2019] Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay Pande, and Jure Leskovec.  Strategies for pre-training graph neural networks.  In _Procs. of ICLR_ , 2019.
  * Hu et al. [2020a] 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 NeurIPS_ , 2020a.
  * Hu et al. [2022] 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.
  * Hu et al. [2020b] 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_ , 2020b.
  * Jin et al. [2023] 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.
  * Jo et al. [2022] Jaehyeong 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.
  * Ju et al. [2022a] Mingxuan Ju, Shifu Hou, Yujie Fan, Jianan Zhao, Yanfang Ye, and Liang Zhao.  Adaptive kernel graph neural network.  In _Procs. of AAAI_ , 2022a.
  * Ju et al. [2022b] 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_ , 2022b.
  * Ju et al. [2023a] 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.  In _Procs. of AAAI_ , 2023a.
  * Ju et al. [2023b] 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 ICLR_ , 2023b.
  * Kim et al. [2020] Ildoo Kim, Younghoon Kim, and Sungwoong Kim.  Learning loss for test-time augmentation.  _Procs. of NeurIPS_ , 2020.
  * Kipf and Welling [2016] Thomas N Kipf and Max Welling.  Semi-supervised classification with graph convolutional networks.  In _Procs. of ICLR_ , 2016.
  * Klicpera et al. [2019] Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann.  Predict then propagate: Graph neural networks meet personalized pagerank.  In _Procs. of ICLR_ , 2019.
  * Liu et al. [2023] Gang Liu, Tong Zhao, Eric Inae, Tengfei Luo, and Meng Jiang.  Semi-supervised graph imbalanced regression.  In _Procs. of KDD_ , 2023.
  * Liu et al. [2021] Zemin Liu, Trung-Kien Nguyen, and Yuan Fang.  Tail-gnn: Tail-node graph neural networks.  In _Procs. of SIGKDD_ , 2021.
  * Long and Sedghi [2020] Philip M Long and Hanie Sedghi.  Generalization bounds for deep convolutional neural networks.  In _Procs. of ICLR_ , 2020.
  * Ma et al. [2022] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang.  Is homophily a necessity for graph neural networks?  In _Procs. of ICLR_ , 2022.
  * McAuley et al. [2015] Julian McAuley, Rahul Pandey, and Jure Leskovec.  Inferring networks of substitutable and complementary products.  In _Procs. of SIGKDD_ , 2015.
  * Mohri et al. [2018] Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar.  _Foundations of machine learning_.  MIT press, 2018.
  * Niu et al. [2020] 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.
  * Pal et al. [2020] 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.
  * Rombach et al. [2022] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In _Procs. of CVPR_ , 2022.
  * Sen et al. [2008] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad.  Collective classification in network data.  _AI magazine_ , 2008.
  * Shanmugam et al. [2021] Divya Shanmugam, Davis Blalock, Guha Balakrishnan, and John Guttag.  Better aggregation in test-time augmentation.  In _Procs. of CVPR_ , 2021.
  * Shiao et al. [2023] William Shiao, Uday Singh Saini, Yozen Liu, Tong Zhao, Neil Shah, and Evangelos E Papalexakis.  Carl-g: Clustering-accelerated representation learning on graphs.  _Procs. of KDD_ , 2023.
  * Tang et al. [2020] Xianfeng Tang, Huaxiu Yao, Yiwei Sun, Yiqi Wang, Jiliang Tang, Charu Aggarwal, Prasenjit Mitra, and Suhang Wang.  Investigating and mitigating degree-related biases in graph convoltuional networks.  In _Procs. of CIKM_ , 2020.
  * Tsitsulin et al. [2020] Anton Tsitsulin, John Palowitch, Bryan Perozzi, and Emmanuel Müller.  Graph clustering with graph neural networks.  _arXiv_ , 2020.
  * Veličković et al. [2017] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio.  Graph attention networks.  In _Procs. of ICLR_ , 2017.
  * Velickovic et al. [2019] Petar Velickovic, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm.  Deep graph infomax.  In _Procs. of ICLR_ , 2019.
  * Vignac et al. [2022] Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard.  Digress: Discrete denoising diffusion for graph generation.  In _Procs. of ICLR_ , 2022.
  * Wang et al. [2019] 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.
  * Wu et al. [2022] Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf.  Handling distribution shifts on graphs: An invariance perspective.  In _Procs. of ICLR_ , 2022.
  * Xu et al. [2018] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka.  How powerful are graph neural networks?  _In Procs. of ICLR_ , 2018.
  * Yang et al. [2016] Zhilin Yang, William Cohen, and Ruslan Salakhudinov.  Revisiting semi-supervised learning with graph embeddings.  In _Procs. of ICML_ , 2016.
  * Ying et al. [2018] 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.
  * You et al. [2018] Jiaxuan You, Rex Ying, Xiang Ren, William Hamilton, and Jure Leskovec.  Graphrnn: Generating realistic graphs with deep auto-regressive models.  In _Procs. of ICML_ , 2018.
  * You et al. [2020] Yuning You, Tianlong Chen, Yongduo Sui, Ting Chen, Zhangyang Wang, and Yang Shen.  Graph contrastive learning with augmentations.  In _Procs. of NeurIPS_ , 2020.
  * You et al. [2021] Yuning You, Tianlong Chen, Yang Shen, and Zhangyang Wang.  Graph contrastive learning automated.  In _Procs. of ICML_ , 2021.
  * Yun et al. [2022] Sukwon Yun, Kibum Kim, Kanghoon Yoon, and Chanyoung Park.  Lte4g: Long-tail experts for graph neural networks.  In _Procs. of CIKM_ , 2022.
  * Zhang and Chen [2018] Muhan Zhang and Yixin Chen.  Link prediction based on graph neural networks.  In _Procs. of NeurIPS_ , 2018.
  * Zhang et al. [2021] Zaixi Zhang, Qi Liu, Hao Wang, Chengqiang Lu, and Chee-Kong Lee.  Motif-based graph self-supervised learning for molecular property prediction.  _Procs. of NeurIPS_ , 2021.
  * Zhao et al. [2021] Tong Zhao, Tianwen Jiang, Neil Shah, and Meng Jiang.  A synergistic approach for graph anomaly detection with pattern mining and feature learning.  _IEEE Transactions on Neural Networks and Learning Systems_ , 2021\.
  * Zhao et al. [2022] Tong Zhao, Gang Liu, Daheng Wang, Wenhao Yu, and Meng Jiang.  Learning from counterfactual links for link prediction.  In _Procs. of ICML_ , 2022.
  * Zhao et al. [2023] 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.
  * Zheng et al. [2021] 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.
  * Zhu et al. [2021] 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.
  * Zhu et al. [2020] 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\.
  * Zhu et al. [2022] 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.

##  Appendix 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 5. 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)222https://ogb.stanford.edu and explore the provided splits. For Wiki.CS,
Amazon-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)333https://www.dgl.ai to load all datasets.

Table 5: Dataset Statistics.  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%/10%/80%
Amazon-Photo | 7,650 | 119,043 | 745 | 15.6 | 10%/10%/80%
Coauthor-CS | 18,333 | 81,894 | 6,805 | 4.5 | 10%/10%/80%
ogbn-arxiv | 169,343 | 1,166,243 | 128 | 6.9 | Public Split

##  Appendix B GraphPatcher Configuration and Experiment on Hyper-parameters

###  B.1 GraphPatcher Configuration

The architecture of GraphPatcher consists of two parts; the first part is a
2-layer GCN encoder that takes an ego-graph as input and vectorizes its nodes
and the second part is an 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 hyper-parameter
configurations of GraphPatcher 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.

Table 6: Hyper-parameters used for GraphPatcher.

Hyper-param. | Cora | Citeseer | Pubmed | Wiki.CS | Am.Photo | Co.CS | Arxiv
---|---|---|---|---|---|---|---
Augmentation strength | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 | 0.3 | 0.1
Patching step | 3 | 3 | 3 | 3 | 3 | 3 | 5
# of sampled graphs | 10 used for all datasets
Batch size | 64 | 64 | 64 | 8 | 16 | 4 | 16
Accumulation step | 16 | 16 | 16 | 32 | 16 | 16 | 64
Learning rate | 1e-4 used for all datasets
Optimizer | AdamW with a weight decay of 1e-5 used for all datasets

###  B.2 Experiment on Hyper-parameters

The hyper-parameters we 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 performance of GraphPatcher
improves as the number of patching nodes increases and the gain saturates with
4 to 5 nodes patched.

Figure 4: Overall perf. (y-axis) w.r.t. the number of patching nodes (x-axis).

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 a 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, 1e-4, 5e-5]; and we
tune the augmentation strength by searching over [0.1, 0.2, 0.3, 0.4].

Figure 5: GraphPatcher’s sensitivity to different hyper-parameters.

The hidden dimension refers to the intermediate dimension of the 2-layer GCNs
of GraphPatcher. GraphPatcher is constructed by a 2-layer GCN and features for
virtual nodes are generated by a 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 $\lfloor\frac{1}{t}\rfloor$. 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 hyper-parameters is 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 a learning rate of 1e-4. We also investigate GraphPatcher’s
sensitivity to the number of hidden dimensions (i.e., the model size). In
Figure 5.(b), we notice that for large graphs like Arxiv, the performance
gradually increases as the model size enlarges. And for small and medium
graphs like Cora and Pubmed, the performance saturates with a hidden dimension
of 128. Besides, in Figure 5.(c) we study GraphPatcher’s 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 of our proposed training scheme with multiple ego-graphs, we
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 $L=10$, empirically proving the effectiveness of the
exploration of multiple ego-graphs for the same corruption strength.

###  B.3 Hardware and Software Configuration

We conduct experiments on a server having one RTX3090 GPU with 24 GB VRAM. The
CPU we have on the server is an AMD Ryzen 3990X with 128GB RAM. The software
we use includes DGL 1.9.0 and PyTorch 1.11.0. As for the baseline models that
we compare GraphPatcher with, we explore the implementations provided by code
repositories listed as follows:

  * •

Tail-GNN [25]: https://github.com/shuaiOKshuai/Tail-GNN.

  * •

ColbBrew [55]: https://github.com/amazon-science/gnn-tail-generalization.

  * •

EERM [42]: https://github.com/qitianwu/GraphOOD-EERM.

  * •

GTrans [15]L https://github.com/ChandlerBang/GTrans.

  * •

DGI [39]: https://github.com/dmlc/dgl/tree/master/examples/pytorch/dgi.

  * •

GRACE [57]: https://github.com/dmlc/dgl/tree/master/examples/pytorch/grace.

  * •

ParetoGNN [20]: https://github.com/jumxglhf/ParetoGNN.

We sincerely appreciate the authors of these works for open-sourcing their
valuable code and researchers at DGL for providing reliable implementations of
these models. For TuneUp [13], since the authors have not released the code
yet, we manually implement it by ourselves, with a similar performance as
reported in its original paper.

##  Appendix C Proof to Theorem 1

Here we re-state Theorem 1 before diving into its proof:

Theorem 1. Assuming the parameters of GraphPatcher are initialized from the
set
$P_{\beta}=\\{\bm{\phi}:||\bm{\phi}-\mathcal{N}(\mathbf{0}_{|\bm{\phi}|};\mathbf{1}_{|\bm{\phi}|})||_{F}<\beta\\}$
where $\beta>0$, with probability at least $1-\delta$, for all $\bm{\phi}\in
P_{\beta}$, the error bound (i.e.,
$\mathbb{E}(\mathcal{L}_{\text{patch}})-\mathcal{L}_{\text{patch}}$) is
$\mathcal{O}(\beta\sqrt{\frac{|\bm{\phi}|}{L}}+\sqrt{\frac{\log(1/\beta)}{L}})$.

###### 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 1.

Suppose a set $P$ of functions is $(B,d)$-Lipschitz parameterized for $B>0$
and $d\in\mathbb{N}$ with input from a distribution $D$ and output in $(0,1)$.
There exist a constant $c$ such that for all $n\in\mathbb{N}$, for any
$\delta>0$, if $S$ is obtained by sampling $n$ times independently from $D$,
with probability at least $1-\delta$, for all $B$ and $f\in P$, we have:

$\mathbb{E}_{d\sim D}[f(d)]-\mathbb{E}_{S}[f]\leq
c\cdot\Big{(}B\sqrt{\frac{d}{n}}+\sqrt{\frac{\log(1/\delta)}{n}}\Big{)}.$ (7)

In order to prove
$\mathbb{E}(\mathcal{L}_{\text{patch}})-\mathcal{L}_{\text{patch}}$ is
$\mathcal{O}(\beta\sqrt{\frac{|\bm{\phi}|}{L}}+\sqrt{\frac{\log(1/\beta)}{L}})$,
we need to show that $\mathcal{L}_{\text{patch}}$ is Lipschitz continuous.
$\mathcal{L}_{\text{patch}}$, as discussed in Section 3.2.1, is a regularized
cross-entropy formulated as
$(\mathbf{y}_{1}+\epsilon)\cdot\big{(}\log(\mathbf{y}_{2}+\epsilon)-\log(\mathbf{y}_{1}+\epsilon)\big{)}$.
In this work, $\mathbf{y}_{1}$ and $\mathbf{y}_{2}$ refers to the prediction
distribution (i.e., $0<\mathbf{y}_{1}<1$) delivered by the GNN we aim at
improving. Hence, we need to show that for given a specific $\mathbf{y}_{1}$,
for any two
$\mathbf{y}^{a}_{2},\mathbf{y}^{b}_{2}\in\\{\mathbf{y}^{\prime}_{2}:0<\mathbf{y}^{\prime}_{2}<1\\}$
and $K\in\mathbb{R}^{+}$, we have

$\Big{|}\Big{|}(\mathbf{y}_{1}+\epsilon)\cdot\log(\frac{\mathbf{y}^{a}_{2}+\epsilon}{\mathbf{y}_{1}+\epsilon})-(\mathbf{y}_{1}+\epsilon)\cdot\log(\frac{\mathbf{y}^{b}_{2}+\epsilon}{\mathbf{y}_{1}+\epsilon})\Big{|}\Big{|}_{F}\leq
K\cdot\Big{|}\Big{|}\mathbf{y}^{a}_{2}-\mathbf{y}^{b}_{2}\Big{|}\Big{|}_{F}$
(8)
$\Big{|}\Big{|}(\mathbf{y}_{1}+\epsilon)\cdot\big{(}\log(\frac{\mathbf{y}^{a}_{2}+\epsilon}{\mathbf{y}_{1}+\epsilon})-\log(\frac{\mathbf{y}^{b}_{2}+\epsilon}{\mathbf{y}_{1}+\epsilon})\big{)}\Big{|}\Big{|}_{F}\leq
K\cdot\Big{|}\Big{|}\mathbf{y}^{a}_{2}-\mathbf{y}^{b}_{2}\Big{|}\Big{|}_{F}$
(9)
$\Big{|}\Big{|}(\mathbf{y}_{1}+\epsilon)\cdot\big{(}\log(\frac{\mathbf{y}^{a}_{2}+\epsilon}{\mathbf{y}^{b}_{2}+\epsilon})\big{)}\Big{|}\Big{|}_{F}\leq
K\cdot\Big{|}\Big{|}\mathbf{y}^{a}_{2}-\mathbf{y}^{b}_{2}\Big{|}\Big{|}_{F}$
(10)

Given the fact that $\log(\cdot)$ is strictly concave, Equation 10 holds and
hence $\mathcal{L}_{\text{patch}}$ is Lipschitz continuous. We can then
directly apply Lemma 1 to show that Theorem 1 holds. ∎