GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via
  Test-time Augmentation
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.
Mingxuan Ju, Tong Zhao, Wenhao Yu, Neil Shah, Yanfang Ye
# GraphPatcher: Mitigating Degree Bias for Graph Neural Networks via Test-time Augmentation

###### 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](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].

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.

Figure 1: The classification accuracy of GCN and SoTA frameworks that mitigate degree biases.
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

### 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;\mathbf{\theta}):G\rightarrow\mathbb{R}^{N\times C}\) parameterized by \(\mathbf{\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;\mathbf{\theta})\) and a graph G, a test-time node patching framework \(f(\cdot;\mathbf{\phi}):G\to 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_{\mathbf{\phi}}\ \mathcal{L}\Big{(}f_{g}\big{(}f(G;\phi);\mathbf{\theta}^{ *}\big{)},\mathbf{Y}\Big{)},\quad\text{where}\quad\mathbf{\theta}^{*}=\arg\min_{ \mathbf{\theta}}\mathcal{L}\big{(}f_{g}(G;\mathbf{\theta}),\ \mathbf{Y}^{(L)}\big{)}, \tag{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;\mathbf{\phi})\), such that the graphs patched by \(f(\cdot;\mathbf{\phi})\) enhance the performance of \(f_{g}(\cdot;\mathbf{\theta}^{*})\) over low-degree nodes; and (2) how to derive a unified learning scheme that allows \(f(\cdot;\mathbf{\phi})\) to not only improve low-degree nodes but also maintain the GNN's original superiority over high-degree nodes.
### 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;\mathbf{\theta})[v_{i}]=f_{g}(\mathcal{G}(v_{i});\mathbf{\theta})[v_{i}]\) if \(k\) equals to the number of layers in \(f_{g}(\cdot;\mathbf{\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;\mathbf{\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

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).
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;\mathbf{\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});\mathbf{\phi}),\ \ \text{where}\ \ \hat{V}=V^{\prime}(v_{i})\cup\{v_{p}\},\ \ \hat{E}=E^{\prime}(v_{i})\cup\{e_{(i,p)}\}, \tag{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:\mathbf{\phi})\) such that \(f_{g}(\cdot;\mathbf{\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_{\mathbf{\phi}}\ \sum_{v_{i}\in V_{\text{r}}}\text{KL-Div}\Big{(}f_{g} \big{(}\mathcal{G}(v_{i});\mathbf{\theta}^{*}\big{)}[v_{i}],f_{g}\big{(}f( \mathcal{G}^{\prime}(v_{i});\mathbf{\phi});\mathbf{\theta}^{*}\big{)}[v_{i}]\Big{)}, \tag{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{)}\)1 with \(\epsilon>0\) and \(V_{\text{rr}}\) 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.

Footnote 1: KL 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.

#### 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:

\[\arg\min_{\mathbf{\phi}}\ \sum_{v_{i}\in V_{u}}\sum_{m=1}^{M-1}\text{KL-Div} \Big{(}f_{g}\big{(}\mathcal{G}^{\prime}(v_{i})_{m+1};\mathbf{\theta}^{*}\big{)}[v_ {i}],f_{g}(\hat{\mathcal{G}}(v_{i})_{m};\mathbf{\theta}^{*})[v_{i}]\Big{)}, \tag{4}\] \[\text{s.t.}\ \ \hat{\mathcal{G}}(v_{i})_{m}=f(\hat{\mathcal{G}}(v_{i})_{m-1} ;\mathbf{\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};\mathbf{\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 \(\binom{|V_{i}|}{(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_{\mathbf{v}}}\sum_{m=1}^{M-1}\sum_{l=1 }^{L}\text{KL-Div}\Big{(}f_{g}\big{(}\mathcal{G}^{\prime}(v_{i})_{m+1}^{l}; \mathbf{\theta}^{\ast}\big{)}[v_{i}],f_{g}\big{(}\hat{\mathcal{G}}(v_{i})_{m}; \mathbf{\theta}^{\ast}\big{)}[v_{i}]\Big{)}, \tag{5}\]

where \(\hat{\mathcal{G}}(v_{i})_{m}=f(\hat{\mathcal{G}}(v_{i})_{m-1};\mathbf{\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_{\mathbf{v}}}\text{KL-Div}\Big{(}f_{g }\big{(}\mathcal{G}(v_{i});\mathbf{\theta}^{\ast}\big{)}[v_{i}],f_{g}\big{(}\hat{ \mathcal{G}}(v_{i})_{M};\mathbf{\theta}^{\ast}\big{)}[v_{i}]\Big{)}, \tag{6}\]

where \(\hat{\mathcal{G}}(v_{i})_{M}=f(\hat{\mathcal{G}}(v_{i})_{M-1};\mathbf{\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_{\mathbf{\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}=\{\mathbf{\phi}:||\mathbf{\phi}-\mathcal{N}(\mathbf{0}_{|\mathbf{\phi}|};\mathbf{1}_{| \mathbf{\phi}|})||_{F}<\beta\}\) where \(\beta>0\), with probability at least \(1-\delta\) for all \(\mathbf{\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{|\mathbf{\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., \(|\mathbf{\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.
Experiments

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

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

\begin{table}
\begin{tabular}{l|c c c c c c c c} \hline \hline Method & Cora & Citeseer & Pubmed & Wiki.CS & Am.Photoc & Co.CS & **Arxiv** & **Chameleon** & **Actor** \\ \hline \hline GCN & 73.27\({}_{\pm 0.01}\) & 64.86\({}_{\pm 0.02}\) & 76.88\({}_{\pm 0.04}\) & 72.98\({}_{\pm 0.02}\) & 75.59\({}_{\pm 0.43}\) & 84.59\({}_{\pm 0.45}\) & 63.15\({}_{\pm 0.13}\) & 54.05\({}_{\pm 0.18}\) & 27.30\({}_{\pm 0.32}\) \\ ColBrew & 73.82\({}_{\pm 0.98}\) & 65.00\({}_{\pm 0.02}\) & 77.22\({}_{\pm 0.63}\) & 73.98\({}_{\pm 0.32}\) & 76.18\({}_{\pm 0.80}\) & 85.56\({}_{\pm 0.65}\) & 63.02\({}_{\pm 0.21}\) & 53.41\({}_{\pm 0.22}\) & 27.88\({}_{\pm 0.13}\) \\ Tail-GNN & 71.71\({}_{\pm 0.80}\) & 57.60\({}_{\pm 0.33}\) & 75.38\({}_{\pm 0.78}\) & **74.30\({}_{\pm 0.72}\)** & 77.22\({}_{\pm 0.61}\) & 85.13\({}_{\pm 0.90}\) & OOM & 53.48\({}_{\pm 0.94}\) & 27.80\({}_{\pm 0.82}\) \\ TuneUp & 74.47\({}_{\pm 0.43}\) & 65.17\({}_{\pm 0.22}\) & 77.18\({}_{\pm 0.39}\) & 72.60\({}_{\pm 0.78}\) & 67.08\({}_{\pm 0.62}\) & 64.86\({}_{\pm 0.50}\) & 63.34\({}_{\pm 0.32}\) & 53.87\({}_{\pm 0.43}\) & 27.94\({}_{\pm 0.14}\) \\ EERM & 73.40\({}_{\pm 0.06}\) & 64.27\({}_{\pm 0.78}\) & 76.30\({}_{\pm 0.20}\) & 73.12\({}_{\pm 0.68}\) & 75.15\({}_{\pm 0.59}\) & 84.82\({}_{\pm 0.74}\) & 63.20\({}_{\pm 0.11}\) & 54.11\({}_{\pm 0.32}\) & 27.48\({}_{\pm 0.39}\) \\ GTrans & 73.16\({}_{\pm 0.64}\) & 64.95\({}_{\pm 0.83}\) & 77.05\({}_{\pm 0.75}\) & 12.51\({}_{\pm 0.50}\) & 75.55\({}_{\pm 0.55}\) & 84.74\({}_{\pm 0.70}\) & 62.88\({}_{\pm 0.11}\) & 54.29\({}_{\pm 0.14}\) & 27.53\({}_{\pm 0.21}\) \\ DropEdge & 73.57\({}_{\pm 0.79}\) & 65.47\({}_{\pm 0.72}\) & 75.68\({}_{\pm 0.72}\) & 73.94\({}_{\pm 0.70}\) & 76.49\({}_{\pm 0.54}\) & 83.41\({}_{\pm 0.33}\) & 54.13\({}_{\pm 0.33}\) & 54.12\({}_{\pm 0.41}\) & 27.39\({}_{\pm 0.24}\) \\ GraphPatcher & **78.08\({}_{\pm 0.06}\)** & **67.27\({}_{\pm 0.78}\)** & **79.85\({}_{\pm 0.21}\)** & 74.04\({}_{\pm 0.86}\) & **77.84\({}_{\pm 0.36}\)** & **86.76\({}_{\pm 0.54}\)** & **64.01\({}_{\pm 0.12}\)** & **54.48\({}_{\pm 0.17}\)** & **29.27\({}_{\pm 0.57}\)** \\ \hline \hline \multicolumn{10}{c}{Accuracy on High-degree Nodes (Upper Preciellite)} \\ \hline GCN & 86.83\({}_{\pm 0.17}\) & **77.25\({}_{\pm 1.00}\)** & 80.84\({}_{\pm 0.76}\) & 83.40\({}_{\pm 0.70}\) & 84.07\({}_{\pm 0.71}\) & 90.20\({}_{\pm 0.37}\) & 80.46\({}_{\pm 0.18}\) & 54.11\({}_{\pm 0.78}\) & 27.41\({}_{\pm 0.20}\) \\ ColBrew & 84.80\({}_{\pm 0.04}\) & 75.33\({}_{\pm 0.84}\) & 78.66\({}_{\pm 0.73}\) & 71.98\({}_{\pm 0.70}\) & 77.05\({}_{\pm 0.74}\) & 82.16\({}_{\pm 0.10}\) & 70.57\({}_{\pm 0.50}\) & 53.72\({}_{\pm 0.48}\) & 26.67\({}_{\pm 0.20}\) \\ Tail-GNN & 84.13\({}_{\pm 0.48}\) & 78.53\({}_{\pm 0.84}\) & 78.74\({}_{\pm 0.34}\) & 78.91\({}_{\pm 0.70}\) & 80.32\({}_{\pm 0.60}\) & 86.75\({}_{\pm 0.50}\) & OOM & **54.53\({}_{\pm 0.12}\)** & 27.13\({}_{\pm 0.44}\) \\ TuneUp & 87.13\({}_{\pm 0.67}\) & 76.95\({}_{\pm 0.83}\) & 81.74\({}_{\pm 0.31}\) & 83.11\({}_{\pm 0.57}\) & 81.57\({}_{\pm 0.60}\) & 90.65\({}_{\pm 0.80}\) & 80.09\({}_{\pm 0.51}\) & 54.25\({}_{\pm 0.59}\) & 26.64\({}_{\pm 0.71}\) \\ EERM & 85.99\({}_{\pm 0.76}\) & 76.52\({}_{\pm 0.22}\) & 79.98\({}_{\pm 0.60}\) & 82.98\({}_{\pm 0.60}\) & 84.32\({}_{\pm 0.96}\) & 90.17\({}_{\pm 0.11}\) & 80.37\({}_{\pm 0.72}\) & 54.41\({}_{\pm 0.17}\) & 27.39\({}_{\pm 0.44}\) \\ GTrans & 86.32\({}_{\pm 0.34}\) & 76.60\({}_{\pm 0.44}\) & 80.56\({}_{\pm 0.92}\) & 83.42\({}_{\pm 0.42}\) & 83.95\({}_{\pm 0.99}\) & 89.99\({}_{\pm 0.10}\) & **80.77\({}_{\pm 0.20}\)** & 54.21\({}_{\pm 0.19}\) & 27.29\({}_{\pm 0.12}\) \\ DropEdge & 86.53\({}_{\pm 0.90}\) & 76.35\({}_{\pm 0.17}\) & 81.44\({}_{\pm 0.51}\) & 83.37\({}_{\pm 0.73}\) & **84.97\({}_{\pm 0.96}\)** & 89.28\({}_{\pm 0.08}\) & 86.04\({}_{\pm 0.36}\) & 54.17\(
### Performance of GraphPatcher for Self-supervised GNNs

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.

### Effectiveness of GraphPatcher for Enhancing SoTA Method

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.

### Performance w.r.t. the Number of Patching Nodes

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

\begin{table}
\begin{tabular}{l|c c} \hline \hline Method & Cora & Citeseer & Pubmed \\ \hline \multicolumn{3}{c}{Low-degree Nodes (Lower Percentile)} \\ \hline GRAND & 80.18\({}_{\pm 0.64}\) & 70.57\({}_{\pm 0.68}\) & 80.48\({}_{\pm 0.14}\) \\ +GraphPatcher & 81.58\({}_{\pm 0.45}\) & 72.73\({}_{\pm 0.29}\) & 84.68\({}_{\pm 0.29}\) \\ \hline \multicolumn{3}{c}{High-degree Nodes (Upper Percentile)} \\ \hline GRAND & 88.32\({}_{\pm 0.75}\) & 79.64\({}_{\pm 0.86}\) & 83.53\({}_{\pm 0.52}\) \\ +GraphPatcher & 88.92\({}_{\pm 0.18}\) & 79.54\({}_{\pm 0.13}\) & 84.43\({}_{\pm 0.21}\) \\ \hline \multicolumn{3}{c}{Overall Performance} \\ \hline GRAND & 85.22\({}_{\pm 0.80}\) & 74.90\({}_{\pm 0.77}\) & 82.30\({}_{\pm 0.41}\) \\ +GraphPatcher & 85.90\({}_{\pm 0.44}\) & 76.10\({}_{\pm 0.38}\) & 84.20\({}_{\pm 0.26}\) \\ \hline \hline \end{tabular}
\end{table}
Table 4: Effectiveness for SoTA.

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

\begin{table}
\begin{tabular}{l|c c c} \hline \hline Method & Cora & Pubmed & Wiki.CS \\ \hline \multicolumn{3}{c}{Low-degree Nodes (Lower Percentile)} \\ \hline DGI & 78.47\({}_{\pm 0.37}\) & 75.63\({}_{\pm 0.82}\) & 75.86\({}_{\pm 0.61}\) \\ +GraphPatcher & 79.95\({}_{\pm 0.53}\) & 78.04\({}_{\pm 0.97}\) & 77.31\({}_{\pm 0.91}\) \\ GRACE & 77.81\({}_{\pm 0.73}\) & 77.80\({}_{\pm 0.65}\) & 74.31\({}_{\pm 0.63}\) \\ +GraphPatcher & 78.53\({}_{\pm 0.82}\) & 78.49\({}_{\pm 0.94}\) & 75.12\({}_{\pm 0.34}\) \\ ParetoGNN & 78.85\({}_{\pm 0.71}\) & 78.32\({}_{\pm 0.33}\) & 74.71\({}_{\pm 0.18}\) \\ +GraphPatcher & 79.91\({}_{\pm 0.62}\) & 79.11\({}_{\pm 0.89}\) & 76.41\({}_{\pm 0.22}\) \\ \hline \multicolumn{3}{c}{High-degree Nodes (Upper Percentile)} \\ \hline DGI & 86.83\({}_{\pm 0.82}\) & 81.14\({}_{\pm 0.28}\) & 81.09\({}_{\pm 0.81}\) \\ +GraphPatcher & 86.91\({}_{\pm 0.10}\) & 82.31\({}_{\pm 0.53}\) & 80.95\({}_{\pm 0.19}\) \\ GRACE & 85.03\({}_{\pm 0.05}\) & 78.74\({}_{\pm 0.84}\) & 83.91\({}_{\pm 0.56}\) \\ +GraphPatcher & 85.12\({}_{\pm 0.25}\) & 79.58\({}_{\pm 0.31}\) & 84.12\({}_{\pm 0.22}\) \\ ParetoGNN & 87.03\({}_{\pm 0.84}\) & 80.89\({}_{\pm 0.84}\) & 81.57\({}_{\pm 0.84}\) \\ +GraphPatcher & 87.32\({}_{\pm 0.27}\) & 80.55\({}_{\pm 0.32}\) & 81.78\({}_{\pm 0.53}\) \\ \hline \hline \end{tabular}
\end{table}
Table 3: Effectiveness for self-supervised GNNs.
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.