IGL-Bench: Establishing the Comprehensive Benchmark for Imbalanced Graph Learning

## Abstract

Abstract Deep graph learning has gained grand popularity over the past years due to its versatility and success in representing graph data across a wide range of domains.
However, the pervasive issue of imbalanced graph data distributions, where certain parts exhibit disproportionally abundant data while others remain sparse, undermines the efficacy of conventional graph learning algorithms, leading to biased outcomes.
To address this challenge, Imbalanced Graph Learning (IGL) has garnered substantial attention, enabling more balanced data distributions and better task performance.
Despite the proliferation of IGL algorithms, the absence of consistent experimental protocols and fair performance comparisons pose a significant barrier to comprehending advancements in this field.
To bridge this gap, we introduce IGL-Bench , a foundational comprehensive benchmark for imbalanced graph learning, embarking on 16 diverse graph datasets and 24 distinct IGL algorithms with uniform data processing and splitting strategies.
Specifically, IGL-Bench systematically investigates state-of-the-art IGL algorithms in terms of effectiveness , robustness , and efficiency on node-level and graph-level tasks, with the scope of class-imbalance and topology-imbalance .
Extensive experiments demonstrate the potential benefits of IGL algorithms on various imbalanced conditions, offering insights and opportunities in the IGL field.
Further, we have developed an open-sourced and unified package to facilitate reproducible evaluation and inspire further innovative research, which is available at https://github.com/RingBDStack/IGL-Bench .

### 1 Introduction

Graphs are widely acknowledged as powerful for representing networks such as social networks [, ], citation networks [, ], e-commerce networks [, ], etc. In graphs, nodes represent individual entities, and edges signify relationships between nodes.
Graph representation learning seeks to embed the graph structures (nodes, edges, or entire graphs) into a low-dimensional space while retaining their structural semantics []. Recently, Graph Neural Networks (GNNs) [, , ] have emerged as the dominant approach for graph representation learning owing to their exceptional ability to leverage both the graph topology and node attributes. Though GNNs achieve satisfying performance in various tasks, they are typically designed assuming that training data is comprehensive and balanced. However, real-world graph data often feature imbalanced distributions with some parts possessing abundant data while others are scarce [], which greatly compromises task performance. The non-Euclidean nature of graph data precludes the use of traditional imbalance learning algorithms, presenting a considerable obstacle to the deployment of GNNs in real-world scenarios, which is also a heated research topic in the community.

Imbalanced Graph Learning (IGL).
To address the challenge of imbalance, a wide range of methods have been proposed in the realms of computer vision [] and language [] on the broadly concerning class-imbalance learning issue []. Nevertheless, the non-Euclidean graph data presents distinct challenges due to its inherent non-i.i.d. and diverse topological nature. As a result, not only do these conventional methods become infeasible for graphs, but they also fail to address other distinctive topology-imbalance challenges intrinsic in graph data [, , , ]. To mitigate the aforementioned imbalanced issues on graphs, Imbalanced Graph Learning (IGL) has recently attracted considerable research interest, as highlighted in Figure [1](#S1.F1). The increasing literature each year reflects the rising significance and profound effect of tackling challenges in IGL, which are categorized into various kinds of research problems, presenting distinct characteristics, necessitating the creation of specialized techniques to handle the imbalance issues inherent to each scenario effectively.

Figure: Figure 1: Overview of the established IGL-Bench. Both IGL algorithms and datasets are categorized into node-level and graph-level, where the algorithms are further divided into class-imbalance, topology-imbalance, or both. Click $\rhd$ and link to the corresponding sections for in-depth analysis.

Despite the emerging studies of IGL algorithms, there lacks a comprehensive and unified benchmark, which would significantly impede the understanding and progress of IGL for the following aspects.
❶ Dataset preparation rule. The use of different datasets, data processing approaches, and imbalanced data-splitting strategies in previous works makes many of the results incomparable.
❷ Experiment conduction protocol. The variability in experimental setups, including parameter settings, initialization procedures, and convergence criteria, hinders reproducibility and comparability across studies.
❸ Performance evaluation standard. The metric for evaluating task performance is not consistent. Apart from effectiveness, understanding the efficiency and complexity of each algorithm is imperative, yet often overlooked in the literature. Hence, there is an urgent necessity within the community for the creation of a comprehensive and open-sourced benchmark for IGL.

In this work, we establish a comprehensive Imbalanced Graph Learning Benchmark (IGL-Bench), which serves as the first open-sourced benchmark for graph-specific imbalanced learning to the best of our knowledge.
IGL-Bench encompases 24 state-of-the-art IGL algorithms and 16 diverse graph datasets covering node-level and graph-level tasks, addressing class- and topology-imbalance issues, while also adopting consistent data processing and splitting approaches for fair comparisons over multiple metrics with different investigation focus. Through benchmarking the existing IGL algorithms for effectiveness, robustness, and efficiency, we make the following contributions:

- •
First Comprehensive IGL Benchmark. IGL-Bench  enables a fair and unified comparison among 19 state-of-the-art node-level and 5 graph-level IGL algorithms by unifying the experimental settings across 16 graph datasets of diverse characteristics, providing a comprehensive understanding of the class-imbalance and topology-imbalance problems in IGL for the first time.
- •
Multi-faceted Evaluation and Analysis. We conduct a systematic analysis of IGL methods from various dimensions, including effectiveness, efficiency, and complexity. Based on the results of extensive experiments, we uncover both the potential advantages and limitations of current IGL algorithms, providing valuable insights to guide future research endeavors.
- •
Open-sourced Package. To facilitate future IGL research, we develop an open-sourced benchmark package for public access. Users can evaluate their algorithms or datasets with less effort.

### 2 Preliminary and Problem Formulation

Notations.
Let $\mathcal{G}=\{\mathcal{V},\mathcal{E},\mathbf{A},\mathbf{X}\}$ be a graph, where $\mathcal{V}$ is the node set with $N$ nodes, $\mathcal{E}$ is the edge set, $\mathbf{A}\in\mathbb{R}^{N\times N}$ is the adjacency matrix, $\mathbf{X}\in\mathbb{R}^{N\times d}$ is the node feature matrix with $d$-dimension.

Node-level Classification.
Given the labeled node set $\mathcal{V}_{L}$ and their labels $\mathbf{Y}_{L}\in\mathbb{R}^{C}$, where each node $v_{i}$ is associated with a label $\mathbf{y}_{i}$. Semi-supervised node classification aims to train a node classifier $f_{\bm{\theta}}:v\mapsto\mathbb{R}^{C}$ to predict the labels $\mathbf{Y}_{U}$ of the remaining nodes $\mathcal{V}_{U}=\mathcal{V}\setminus\mathcal{V}_{L}$.

Graph-level Classification.
Denote $\mathbf{G}$ as the graph set. Given the labeled graph set $\mathbf{G}_{L}$ and their labels $\mathbf{Y}_{L}\in\mathbb{R}^{C}$, where each graph $\mathcal{G}_{i}$ is associated with a label $\mathbf{y}_{i}$. Graph classification task aims to train a graph classifier $\mathcal{F}_{\bm{\theta}}:\mathcal{G}\mapsto\mathbb{R}^{C}$ to predict the labels $\mathbf{Y}_{U}$ of the unlabeled graphs $\mathbf{G}_{U}=\mathbf{G}\setminus\mathbf{G}_{L}$.

We formulate the IGL problems into two categories: class-imbalance and topology-imbalance.

###### Definition 1 ( Class-Imbalance ) .

There exists an imbalance in the number of labeled samples (nodes or graphs) across different classes, leading to the long-tailed sample quantity distribution [].

###### Definition 2 ( Topology-Imbalance ) .

For node-level tasks, there exists an imbalance in the topological distribution of labeled nodes. The imbalance is brought by two main aspects: ❶ Local. Imbalanced node degree distribution []. ❷ Global. Under-reaching and Over-squashing phenomenon []. For graph-level tasks, the imbalance is facilitated by the uneven graph size (the number of nodes) distribution [], which offers potentially biased topological structures.

Figure: Figure 2: The research scope of the proposed IGL-Bench. Definitions of the imbalance ratio ($\rho$) corresponding to each imbalance issue are further concluded in Table [B.1](#A2.T1). Click $\rhd$ and check details.
Refer to caption: /html/2406.09870/assets/x1.png

###### Definition 1 ( Class-Imbalance ) .

###### Definition 2 ( Topology-Imbalance ) .

### 3 IGL-Bench: Imbalanced Graph Learning Benchmark

In this section, we introduce the overview of the IGL-Bench with considerations of the datasets (Section [3.1](#S3.SS1)), algorithms (Section [3.2](#S3.SS2)), and research questions that guide the benchmark study (Section [3.3](#S3.SS3)).
More details can be found in the Appendix provided in the Supplementary Material.

#### 3.1 Benchmark Datasets

To comprehensively and effectively evaluate the performance of IGL algorithms, we have integrated 16 real-world datasets from various domains for both the node-level and graph-level tasks. We briefly introduce each category in the following sections. More details are provided in Appendix [A.1](#A1.SS1).

Node-level Classification Datasets. We utilize nine graph datasets, including three citation networks from Plantoid [] (i.e., Cora, CiteSeer, PubMed), two co-occurrence networks in Amazon [] (i.e., Computers, Photo), the large-scale ogbn-arXiv [], two page-page networks in Wikipedia [] (i.e., Chameleon, Squirrel), and an actor-only induced subgraph of the film-director-actor-writer network Actor []. Datasets range from strong homophily to strong heterophily [].

Graph-level Classification Datasets. We integrate 7 widely adopted real-world datasets. PTC-MR [] and FRANKENSTEIN [] are molecule datasets, where each graph is a molecule with or without mutagenicity.
PROTEINS [, ] and D&D [, ] are protein datasets marked as enzyme or non-enzyme.
IMDB-B [] and REDDIT-B [] are social networks in movies and online discussions, respectively. The scientific collaboration dataset COLLAB [] is derived from three publicly available collaboration datasets that represent distinct research fields.

#### 3.2 Benchmark Algorithms

Table [A.3](#A1.T3) conclude the overall 24 IGL algorithms integrated in IGL-Bench  with their technique categorization, complexity analysis, and links to implementations (Details in Appendix [A.2](#A1.SS2)).

Class-Imbalanced IGL Algorithms. Node-level class-imbalanced IGL refers to the uneven allocation of labeled nodes among classes. The classifier prioritizes learning from classes abundant in labeled instances, potentially neglecting those with fewer instances. We implement 10 representative algorithms including DRGCN [], DPGNN [], ImGAGN [], GraphSMOTE [], GraphENS [], GraphMixup [], LTE4G [], TAM [], TOPOAUC [] and GraphSHA []. Graph-level class-imbalanced IGL manifests in practical situations where the distribution of labeled graphs across classes is skewed, typically favoring the majority class with more labeled graphs. We select 4 typical algorithms including G^2GNN [], TopoImb [], DataDec [], and ImGKB [].

Topology-Imbalanced IGL Algorithms. Node-level topology-imbalanced IGL occurs when the node topology properties display an unequal distribution. An important metric is the node degree, which can reflect the proximity richness. We incorporate DEMO-Net [], meta-tail2vec [], Tail-GNN [], Cold Brew [], LTE4G [], RawlsGCN [], and GraphPatcher []. Another profound topology imbalance is brought by the under-reaching and over-squashing problem [], which critically influences the label propagation process. We take ReNode [], TAM [], PASTEL [], TOPOAUC [], and HyperIMBA [] as our investigation scope.
Graph-level topology-imbalanced IGL stems from the intricate interconnections within graphs. This imbalance frequently presents as variations in graph sizes and topology groups. We implement SOLT-GNN [] and TopoImb [].

#### 3.3 Research Questions

We systematically design the IGL-Bench to comprehensively evaluate the existing IGL algorithms and inspire future research. In particular, we aim to investigate the following research questions.

RQ1: How much progress has been made by the existing IGL algorithms?

Motivation and Experiment Design. Existing IGL algorithms are conducted under inconsistent imbalance settings, making it unfair to compare the task performance. Given the fair data and experiment environment by IGL-Bench, RQ1 aims to gain a deeper understanding of the strengths and weaknesses of IGL algorithms and identify directions that offer avenues for prospective improvements. To achieve this, we conduct node and graph classifications, where the train/val/test split satisfies the consistent ratio of 1:1:8. We facilitate dataset imbalance with the imbalance ratio $\rho$ follows definitions in Figure [2](#S2.F2) (Details in Appendix [B.1](#A2.SS1)). Results are reported with the metric of Accuracy (Acc.), Balanced Accuracy (bAcc.), Macro-F1 (M-F1), and AUC-ROC over 10 runs.

RQ2: How effective are the IGL algorithms generalizing to the changing imbalance ratio?

Motivation and Experiment Design. Since RQ1 has already investigated the performance of IGL algorithms on datasets of certain fixed imbalance ratios, RQ2 further explores the robustness of IGL algorithms as the degree of imbalance varies by quantitatively controlling the imbalance ratio of each dataset to study the diverse capabilities of IGL algorithms. To achieve this, we quantitatively set the imbalance ratio to exhibit a staggered distribution of imbalance levels from (relatively) balanced to extremely imbalanced under the predefined splitting constraints.

RQ3: Does classifiers benefit from the IGL algorithms to learn clearer boundaries?

Motivation and Experiment Design. Imbalanced data can cause unexpected shifts of classifier boundary, negatively impacting task performance. RQ3 aims to investigate whether the performance improvement in downstream tasks results from clearer classification boundaries under the influence of the IGL algorithms. To achieve this, we compare changes in inter-class clustering coefficients (the Silhouette score []). Additionally, we use t-SNE [] to visualize the learned embeddings, aiding in intuitively understanding boundary shifts between classes.

RQ4: How efficient are these IGL algorithms in terms of time and space?

Motivation and Experiment Design. Existing IGL algorithms handle the imbalance issues generally by redistributing data at either the data level or algorithm level to achieve balance, a process that naturally incurs extra computational and spatial complexity compared to vanilla GNNs. However, the algorithm efficiency has been largely overlooked, where RQ4 is proposed to understand the trade-off between efficiency and task performance. To achieve this, we evaluate the algorithm efficiency by reporting the training time and peak GPU memory consumption on consistent configurations.

### 4 Experiment Results and Analysis

In this section, we compare IGL algorithms covering node-level and graph-level tasks, addressing class-imbalance and topology-imbalance issues.
Detailed experiment settings and additional results on more metrics and backbones can be found in Appendix [B](#A2), Appendix [C](#A3), and Appendix [D](#A4).

#### 4.1 Effectiveness Evaluations for IGL Algorithms (RQ1)

##### 4.1.1 Performance of Node-Level Class-Imbalanced IGL Algorithms

Results (Table [1](#S4.T1)).
❶ All algorithms surpass GCN [] on at least 5 datasets, showing a smaller performance gain on heterophilic graph datasets compared to homophilic ones.
❷ Compared to resampling algorithms (e.g., ImGAGN [], GrapSMOTE [], GraphENS [], and GraphSHA []), data-augmentation algorithms (e.g., LTE4G [] and GraphMixup []) generally achieve better performance on 6 out of 9 datasets.
❸ The loss-engineered algorithm TOPOAUC [] achieves optimal or near-optimal results in 5 out of 7 datasets, attributed to its tailored components for handling class-imbalanced and global topology-imbalanced data.

**Table 1: Accuracy score (% ± standard deviation) of node classification on manipulated class-imbalanced graph datasets (Low) over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined (the same for tabels below).**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GCN (bb.) [] | 76.36<br>±0.13 | 52.96<br>±0.55 | 60.57<br>±0.19 | 75.06<br>±0.50 | 69.80<br>±6.15 | 59.83<br>±0.23 | 26.35<br>±0.24 | 17.16<br>±0.17 | 24.06<br>±0.14 |
| DRGCN [] | 71.35<br>±0.77 | 55.22<br>±1.82 | 62.59<br>±4.62 | 67.71<br>±3.10 | 85.67<br>±5.30 | — | 26.40<br>±0.35 | 17.11<br>±0.81 | 25.03<br>±0.23 |
| DPGNN [] | 72.91<br>±3.95 | 56.78<br>±2.23 | 81.87<br>±2.80 | 68.69<br>±8.62 | 81.66<br>±9.19 | — | 30.58<br>±1.48 | 25.35<br>±1.48 | 21.66<br>±1.68 |
| ImGAGN [] | 73.48<br>±3.07 | 55.29<br>±3.00 | 72.16<br>±1.51 | 74.92<br>±1.87 | 83.10<br>±3.42 | — | 24.38<br>±2.86 | 18.75<br>±1.80 | 24.54<br>±3.38 |
| GraphSMOTE [] | 77.21<br>±0.27 | 53.55<br>±0.95 | 60.11<br>±0.27 | 76.04<br>±1.52 | 89.07<br>±1.12 | — | 27.23<br>±0.21 | 16.79<br>±0.14 | 25.08<br>±0.31 |
| GraphENS [] | 79.34<br>±0.49 | 61.98<br>±0.76 | 80.84<br>±0.17 | 80.72<br>±0.68 | 90.38<br>±0.37 | 53.23<br>±0.52 | 24.34<br>±1.62 | 20.05<br>±1.61 | 25.03<br>±0.38 |
| GraphMixup [] | 79.88<br>±0.43 | 62.66<br>±0.70 | 75.94<br>±0.09 | 86.15<br>±0.47 | 89.69<br>±0.31 | 56.08<br>±0.31 | 30.95<br>±0.40 | 17.83<br>±0.32 | 24.75<br>±0.37 |
| LTE4G [] | 80.53<br>±0.65 | 64.48<br>±1.56 | 83.02<br>±0.33 | 79.35<br>±1.39 | 87.94<br>±1.82 | — | 31.91<br>±0.34 | 19.37<br>±0.41 | 25.43<br>±0.26 |
| TAM [] | 80.69<br>±0.27 | 64.16<br>±0.24 | 81.47<br>±0.15 | 81.30<br>±0.53 | 90.35<br>±0.42 | 53.49<br>±0.54 | 23.27<br>±1.38 | 21.17<br>±0.95 | 24.53<br>±0.33 |
| TOPOAUC [] | 83.34<br>±0.31 | 69.03<br>±1.33 | — | 70.85<br>±4.55 | 83.72<br>±2.23 | — | 33.60<br>±1.51 | 21.38<br>±1.03 | 25.16<br>±0.46 |
| GraphSHA [] | 80.03<br>±0.46 | 60.51<br>±0.61 | 77.94<br>±0.36 | 82.71<br>±0.40 | 91.55<br>±0.32 | 60.30<br>±0.13 | 23.73<br>±1.97 | 20.05<br>±1.61 | 23.59<br>±1.01 |

##### 4.1.2 Performance of Node-Level Local Topology-Imbalanced IGL Algorithms

Results (Table [2](#S4.T2)).
❶ Most algorithms outperform GCN [] on seven datasets, with DEMO-Net [] and GraphPatcher [] surpassing GCN [] on all datasets.
❷ Neighbor-augmented algorithms (e.g., Tail-GNN [], Cold Brew [], and GraphPatcher []) achieve greater performance gains compared to model-modified algorithms (e.g., DEMO-Net [] and RawlsGCN []). However, they produce varying results across different datasets.
❸ Tail-GNN [] and GraphPatcher [] excel on high-homophily datasets, whereas Cold Brew [] performs better on high-heterophily datasets.

**Table 2: Accuracy score (% ± standard deviation) of node classification on manipulated local topology-imbalanced graph datasets (Mid) over 10 runs. “—” denotes out of memory or time limit.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GCN (bb.) [] | 80.16<br>±1.09 | 66.87<br>±0.85 | 83.97<br>±0.13 | 71.65<br>±2.10 | 89.43<br>±0.58 | 52.93<br>±0.33 | 52.74<br>±0.60 | 28.70<br>±0.68 | 21.55<br>±1.74 |
| DEMO-Net [] | 80.37<br>±0.52 | 69.73<br>±1.31 | 84.11<br>±0.20 | 79.38<br>±0.98 | 88.09<br>±1.30 | 65.81<br>±0.11 | 55.51<br>±0.87 | 39.45<br>±0.62 | 29.12<br>±0.30 |
| meta-tail2vec [] | 32.17<br>±0.68 | 29.97<br>±3.61 | 59.82<br>±2.86 | 68.17<br>±1.07 | 79.82<br>±1.02 | 33.71<br>±1.16 | 38.78<br>±0.44 | 24.90<br>±0.25 | 26.09<br>±0.07 |
| Tail-GNN [] | 79.05<br>±1.15 | 69.97<br>±1.03 | 85.78<br>±0.41 | 84.09<br>±1.01 | 92.21<br>±0.09 | — | 53.20<br>±0.80 | 30.43<br>±1.06 | 28.02<br>±0.71 |
| Cold Brew [] | 73.84<br>±2.10 | 67.42<br>±0.97 | 86.51<br>±0.04 | 80.19<br>±0.24 | 88.13<br>±0.24 | 69.97<br>±0.07 | 59.16<br>±0.40 | 43.04<br>±0.24 | 33.01<br>±0.19 |
| LTE4G [] | 82.54<br>±0.46 | 70.55<br>±0.54 | 84.77<br>±0.78 | 81.32<br>±2.21 | 91.09<br>±0.19 | — | 55.84<br>±2.86 | 32.43<br>±3.31 | 24.00<br>±0.49 |
| RawlsGCN [] | 80.52<br>±0.14 | 72.38<br>±0.43 | 86.05<br>±0.12 | 78.78<br>±1.40 | 90.53<br>±1.32 | 40.00<br>±0.05 | 44.96<br>±0.79 | 29.93<br>±0.65 | 28.29<br>±0.24 |
| GraphPatcher [] | 83.25<br>±0.42 | 73.38<br>±0.42 | 85.60<br>±0.16 | 83.68<br>±0.69 | 92.28<br>±0.06 | 66.74<br>±0.04 | 55.19<br>±0.41 | 36.94<br>±0.11 | 23.85<br>±0.92 |

##### 4.1.3 Performance of Node-Level Global Topology-Imbalanced IGL Algorithms

Results (Table [3](#S4.T3)).
❶ Re-weighting IGL algorithms (e.g., Renode [], TAM [], and HyperIMBA []) generally outperform vanilla GCN [] on highly homophilic datasets but struggle on heterophilic ones.
❷ Structure-refined PASTEL [] achieves optimal or near-optimal results on most datasets, showing significant improvements on highly heterophilic datasets due to its alleviation of both under-reaching and over-squashing phenomena. However, the structure learning mechanism introduces a heavy quadratic computational burden, making PASTEL [] challenging to adapt to large-scale graphs, e.g., ogbn-arXiv [].
❸ TOPOAUC [] has limited ability to address the global topology-imbalance problem and even performs worse than GCN [] on heterophilic datasets.

**Table 3: Accuracy score (% ± standard deviation) of node classification on manipulated global topology-imbalanced graph datasets (High) over 10 runs.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| GCN (bb.) [] | 79.10<br>±1.28 | 68.37<br>±1.73 | 83.44<br>±0.16 | 75.02<br>±2.20 | 86.32<br>±1.90 | 51.04<br>±0.18 | 33.90<br>±0.70 | 23.27<br>±0.82 | 22.40<br>±0.68 |
| ReNode [] | 79.91<br>±1.52 | 69.89<br>±0.73 | 82.97<br>±0.12 | 77.95<br>±1.71 | 87.80<br>±0.52 | 50.68<br>±0.15 | 32.92<br>±0.98 | 23.80<br>±0.59 | 22.39<br>±0.62 |
| TAM [] | 80.50<br>±0.18 | 73.14<br>±0.13 | 84.07<br>±0.12 | 82.35<br>±0.19 | 89.80<br>±0.23 | 52.09<br>±0.06 | 35.64<br>±0.27 | 24.58<br>±0.09 | 22.55<br>±0.06 |
| PASTEL [] | 80.91<br>±0.36 | 72.73<br>±0.26 | — | 83.24<br>±0.85 | 89.10<br>±0.41 | — | 47.12<br>±2.82 | 33.15<br>±0.66 | 27.56<br>±1.04 |
| TOPOAUC [] | 79.27<br>±0.52 | 70.08<br>±0.83 | — | 75.35<br>±1.32 | 87.10<br>±0.98 | — | 33.39<br>±2.09 | 22.86<br>±0.36 | 22.56<br>±0.18 |
| HyperIMBA [] | 79.81<br>±0.78 | 71.78<br>±0.40 | 84.75<br>±0.30 | 83.43<br>±0.65 | 90.65<br>±0.14 | — | 38.30<br>±2.70 | 29.97<br>±1.79 | 25.30<br>±2.56 |

##### 4.1.4 Performance of Graph-Level Class-Imbalanced IGL Algorithms

Results (Table [4](#S4.T4)).
❶ DataDec [] achieves optimal or near-optimal results on all datasets. It identifies an informative subset for model training via dynamic sparse graph contrastive learning, which leverages abundant of unlabeled information to enhance the performance.
❷ G^2GNN [] generally outperforms GIN [] on binary classification datasets but fails to surpass GIN [] on multi-classification datasets.
❸ TopoImb [] and ImGKB [] show considerable instability across different datasets in class-imbalanced settings. Despite meticulous hyperparameter tuning detailed in Appendix [C](#A3) to ensure thorough and impartial evaluations, we were unable to consistently train TopoImb [] to outperform the backbones, due to its sensitivity to dataset-specific characteristics.

**Table 4: Accuracy score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets (Low) over 10 runs.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| GIN (bb.) [] | 47.83<br>±2.95 | 63.38<br>±1.93 | 55.38<br>±3.57 | 51.05<br>±5.07 | 62.31<br>±3.99 | 61.10<br>±4.86 | 65.01<br>±1.33 |
| G^2GNN [] | 51.88<br>±6.23 | 61.13<br>±1.05 | 63.61<br>±5.03 | 56.29<br>±7.30 | 63.87<br>±4.64 | 69.58<br>±3.59 | 62.05<br>±3.06 |
| TopoImb [] | 44.86<br>±3.52 | 49.49<br>±7.14 | 52.12<br>±10.51 | 49.97<br>±7.24 | 59.95<br>±5.19 | 59.67<br>±7.30 | 65.88<br>±0.75 |
| DataDec [] | 55.72<br>±2.88 | 67.99<br>±0.75 | 66.58<br>±1.35 | 63.51<br>±1.62 | 67.92<br>±3.37 | 78.39<br>±5.01 | 71.48<br>±1.03 |
| ImGKB [] | 50.11<br>±5.95 | 40.83<br>±0.02 | 66.60<br>±2.64 | 65.85<br>±3.70 | 47.74<br>±0.29 | 48.57<br>±2.14 | 51.21<br>±0.10 |

##### 4.1.5 Performance of Graph-Level Topology-Imbalanced IGL Algorithms

Results (Table [5](#S4.T5)).
❶ SOLT-GNN [] surpasses GIN [] in five datasets by transferring head graphs’ knowledge to augment tail graphs, showcasing the effectiveness of knowledge transfer mechanisms in improving imbalanced classification.
❷ Though TopoImb [] is proposed primarily to address uneven sub-structure distribution, results also demonstrate its ability to alleviate topology-imbalance problems across several datasets.
❸ Despite recent advancements, a significant performance gap persists between current graph-level IGL algorithms and their node-level counterparts. This observation underscores the need for continued research into more effective strategies to bridge this disparity.

**Table 5: Accuracy score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets (Mid) over 10 runs.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| GIN (bb.) [] | 51.38<br>±6.78 | 54.82<br>±2.26 | 62.14<br>±2.43 | 61.46<br>±2.43 | 65.08<br>±5.78 | 68.32<br>±1.77 | 65.84<br>±3.12 |
| SOLT-GNN [] | 53.04<br>±3.91 | 68.71<br>±1.60 | 71.95<br>±2.36 | 63.33<br>±1.86 | 69.38<br>±1.23 | 73.51<br>±1.14 | 69.69<br>±2.45 |
| TopoImb [] | 51.59<br>±4.30 | 54.52<br>±0.87 | 64.03<br>±4.43 | 65.99<br>±1.25 | 68.10<br>±0.87 | 71.54<br>±0.75 | 68.68<br>±1.34 |

#### 4.2 Robustness to Different Imbalance Ratios (RQ2)

In this section, we quantitatively set the imbalance ratios of each dataset defined in Table [B.1](#A2.T1) to further investigate the robustness of IGL algorithms as the degree of imbalance varies.

##### 4.2.1 Robustness Analysis of Node-Level Class-Imbalanced IGL Algorithms

Settings.
We manipulate datasets for the node classification following settings in Appendix [B.2](#A2.SS2) to exhibit a staggered imbalance ratio from $\rho=$ 1 to 100 (denoted as Balanced to High). We compare the algorithms’ performance changes along with their relative decrease. The single bar chart reflects the algorithm’s effectiveness, a set of bar charts further illustrates the robustness, and the line chart depicts the algorithm’s ability to control the performance degradation in an imbalanced data distribution.

Results (Figure [3](#S4.F3)).
❶ As the imbalance ratio increases, all node-level IGL algorithms encounter greater challenges, resulting in a gradual decline in performance.
❷ Among the class-imbalanced IGL algorithms, those based on resampling demonstrate better robustness compared to algorithms based on re-weighting and data augmentation.
❸ For extreme class imbalance (High, $\rho=$ 100),
class-imbalance-specific IGL algorithms generally exhibit higher robustness and
performance compared to GCN [] and global topology imbalance methods.
Additionally, algorithms designed for both class- and topology-imbalance (e.g., TAM [] and TOPOAUC []) further enhance performance.
❹ Node-level class-imbalance and global topology-imbalance are orthogonal issues.
Future research should further explore the impact of topology in class-imbalanced graph learning for new insights.

Figure: Figure 3: Robustness analysis of node-level algorithms under different class-imbalance levels on Cora (homophilic). Results are Accuracy and its relative decrease compared to the balanced split.
Refer to caption: /html/2406.09870/assets/x2.png

Figure: (a) Node-level local topology-imbalance.
Refer to caption: /html/2406.09870/assets/x3.png

##### 4.2.2 Robustness Analysis of Node-Level Local Topology-Imbalanced IGL Algorithms

Settings.
We manipulate datasets for the node classification following settings in Appendix [B.3](#A2.SS3) with the local topology-imbalance ratios from Low to High.
For each dataset, we randomly select training nodes to facilitate different imbalance ratios while ensuring an equal number of nodes per class.

Results (Figure [4(a)](#S4.F4.sf1)).
❶ IGL algorithms commonly demonstrate a certain degree of robustness to varying imbalanced scenarios, as they tend to exhibit more stable performance than GCN [].
❷ Different algorithms display varying levels of robustness when facing different types of datasets. For example, neighbor-augmented algorithms are robust to extreme local topology-imbalance and they consistently boost performance in the homophilic dataset (e.g., Computers []) by a significant margin. Their advantages are even more prominent under higher topology-imbalance.
However, they are relatively sensitive to different levels of imbalance in the heterophilic datasets (e.g., Actor []).

##### 4.2.3 Robustness Analysis of Node-Level Global Topology-Imbalanced IGL Algorithms

Settings.
We manipulate datasets for the node classification following settings in Appendix [B.4](#A2.SS4) with different levels of the global topology-imbalance ratios from Low to High, concerning multiple degrees of the under-reaching and over-squashing phenomena to evaluate algorithm robustness.

Results (Figure [4(b)](#S4.F4.sf2)).
❶ All algorithms perform worse in highly imbalanced scenarios
due to the difficulty in balancing the uneven topological distributions of training nodes.
❷ Topology-imbalanced IGL algorithms generally exhibit robustness across different imbalanced scenarios and tend to enhance performance on both homophilic and heterophilic datasets by utilizing structure learning to alleviate topological imbalance (e.g., PASTEL [] and HyperIMBA []).
❸ Class-imbalanced GraphSHA [] synthesizes nodes and connections with different labels, which promotes the global propagation of supervised signals and aids in addressing topological imbalance.

##### 4.2.4 Robustness Analysis of Graph-Level Class-Imbalanced IGL Algorithms

Settings.
Previous research emphasizes the impact of class-imbalance issues on the binary graph classification task.
We manipulate datasets for both the binary and multi-class graph classification task following settings in Appendix [B.5](#A2.SS5) with varying levels of class-imbalance to explore the robustness of IGL algorithms from Balanced ($\rho=$ 1) to extremely imbalanced scenarios (High, $\rho=$ 100).

Results (Figure [4(c)](#S4.F4.sf3)).
❶ IGL algorithms display varying degrees of robustness on different types of datasets.
For example, with an increased imbalance ratio, the performance of IGL gradually decreases on binary classification datasets such as D&D [, ].
❷ On the contrary, in the multi-class dataset COLLAB [], IGL algorithms demonstrate strong robustness across varying levels of imbalance. This indicates that these algorithms can maintain their performance on imbalanced data, effectively handling the complexity and diversity of multiple classes.
❸ Among these IGL algorithms, DataDec [] stands out for its remarkable stability in different imbalanced scenarios. It consistently shows great performance gains across various datasets, highlighting its effectiveness and reliability.

##### 4.2.5 Robustness Analysis of Graph-Level Topology-Imbalanced IGL Algorithms

Settings.
We manipulate datasets for the graph classification following settings in Appendix [B.6](#A2.SS6) with different levels of the topology-imbalance ratios from Low to High, concerning multiple degrees of the graph size distribution to evaluate algorithm robustness.

Results (Figure [4(d)](#S4.F4.sf4)).
❶ SOLT-GNN [] demonstrated remarkable robustness across a spectrum of datasets and topology-imbalance scenarios,
indicating its efficacy in handling varying levels of topology-imbalance.
❷ Contrarily, TopoImb [] did not consistently surpass GIN [] and exhibited notable variability in performance across different topology-imbalance degrees, suggesting that TopoImb [] may not be as reliable in maintaining performance stability for topology-imbalance changes.
❸ The results underscore the importance of algorithm choice in graph classification tasks, particularly in scenarios involving topology-imbalance, where robustness becomes a critical factor.

#### 4.3 Visualizations of the Classifier Boundary (RQ3)

Results (Figure [5](#S4.F5)). The visualizations offer an intuitive observation of the classifier boundary between classes through t-SNE [] on Cora [] and COLLAB []. Each sample is colored according to its predicted class label.
For a quantitative analysis perspective, the Silhouette score [] provides a more accurate depiction of the clustering coefficient of sample embeddings in the representation space. This score ranges from $-$1 to 1, with higher values indicating better clustering.
In summary, the IGL algorithms generally enhance downstream tasks by training classifiers under various imbalanced scenarios, leading to clear decision boundaries. Furthermore, these algorithms effectively shift the decision boundaries toward the minority class, facilitating the utilization of the minor class subspace.

#### 4.4 Efficiency and Scalability Analysis (RQ4)

In this section, we analyze the efficiency and scalability of node- and graph-level IGL algorithms. The results on Cora [] and Proteins [, ] are shown in Figure [6](#S4.F6).
Additional statistics on other datasets are in Appendix [D](#A4).
As we can observe, IGL algorithms generally have higher time or space complexity compared to backbones.
Some algorithms (e.g., GraphMixup [], LTE4G [] and DataDec []) can achieve relatively good performance improvement with less complexity increase.
Besides, although some algorithms (e.g., TOPOAUC [], GraphPatcher [] and PASTEL []) achieve remarkable effectiveness improvement, they largely increase the complexity of time and space.
Additionally, the efficiency problem of IGL is specially pronounced on the large-scale dataset (ogbn-arXiv []), as shown in Tables [1](#S4.T1), [2](#S4.T2), and [3](#S4.T3), nearly half of IGL algorithms run out of memory.
IGL algorithms struggle to achieve a satisfactory balance between performance and efficiency.

Figure: (a) Node-level class-imbalance (Cora, Low).
Refer to caption: /html/2406.09870/assets/x7.png

Figure: Figure 6: Time and space analysis of node- and graph-level IGL algorithms on Cora and Proteins.
Refer to caption: /html/2406.09870/assets/x19.png

### 5 Conclusion and Future Directions

This paper introduces the first comprehensive imbalanced graph learning benchmark, IGL-Bench, by integrating 24 methods across 16 datasets covering varying types and scopes.
We conduct extensive experiments to reveal the performance of IGL algorithms in terms of effectiveness, robustness and efficiency on node- and graph- level tasks.
We design and implement a package IGL-Bench ([https://github.com/RingBDStack/IGL-Bench](https://github.com/RingBDStack/IGL-Bench)) that incorporates all the aforementioned protocols, baseline algorithms, processed datasets, and scripts to reproduce the results in this paper.
Drawing upon our empirical analysis, we point out some promising future directions for the IGL community:

❶ Designing adaptive IGL algorithms for intertwined imbalanced problems.
Graph imbalance issues are often intertwined in real-world situations. The performance of IGL algorithms can be further improved by taking into account different aspects of imbalanced problems.

❷ Developing imbalance quantification metrics for more complex graphs.
Current IGL algorithms are predominantly tailored to the attribute graphs, overlooking the imbalanced issues on more complex graphs such as heterogeneous graphs, directed graphs, hypergraphs, dynamic graphs, etc. There is a pressing need for research on imbalanced graph learning methods that cater to more complex graphs.

❸ Improving the efficiency and scalability of IGL algorithms.
Designing efficient and scalable IGL algorithms is a critical challenge, as the practical utility of current methods is often hindered by efficiency issues.
While some approaches introduce plug-in modules to alleviate these problems, their performance is still constrained by backbones, particularly on large-scale datasets.
Future efforts should focus on overcoming the efficiency limitations of IGL.

### Checklist

- 1.
For all authors…
(a)
Do the main claims made in the abstract and introduction accurately reflect the paper’s contributions and scope?
[Yes] See lines 10 to 16 in the Abstract and lines 63 to 72 in Section [1](#S1).
(b)
Did you describe the limitations of your work?
[Yes] See Appendix [F](#A6).
(c)
Did you discuss any potential negative societal impacts of your work?
[N/A]
(d)
Have you read the ethics review guidelines and ensured that your paper conforms to them?
[Yes]
- 2.
If you are including theoretical results…
(a)
Did you state the full set of assumptions of all theoretical results?
[N/A]
(b)
Did you include complete proofs of all theoretical results?
[N/A]
- 3.
If you ran experiments (e.g. for benchmarks)…
(a)
Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)?
[Yes] We discuss the details of the experimental settings to reproduce the main results in Appendix, and we also provide the URL linking to the GitHub repository.
(b)
Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)?
[Yes] See Appendix [B](#A2) and Appendix [C](#A3).
(c)
Did you report error bars (e.g., with respect to the random seed after running experiments multiple times)?
[Yes] See Section [4](#S4).
(d)
Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)?
[Yes] See Appendix [C](#A3).
- 4.
If you are using existing assets (e.g., code, data, models) or curating/releasing new assets…
(a)
If your work uses existing assets, did you cite the creators?
[Yes] See Appendix [A](#A1).
(b)
Did you mention the license of the assets?
[Yes] See Appendix [A](#A1).
(c)
Did you include any new assets either in the supplemental material or as a URL?
[Yes] We provide the URL linking to the GitHub repository.
(d)
Did you discuss whether and how consent was obtained from people whose data you’re using/curating?
[Yes] See Appendix [A](#A1).
(e)
Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content?
[Yes] See Appendix [F](#A6).
- 5.
If you used crowdsourcing or conducted research with human subjects…
(a)
Did you include the full text of instructions given to participants and screenshots, if applicable?
[N/A]
(b)
Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable?
[N/A]
(c)
Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation?
[N/A]

## Appendix

### Appendix A Datasets and Algorithms

#### A.1 Benchmark Datasets

We adopt 16 benchmark datasets since
❶ they are extensively utilized for training and assessing IGL algorithms;
❷ they encompass a broad range of graph properties, spanning from small-scale to large-scale, from homophilic to heterophilic, and from node-level to graph-level;
❸ they cover diverse domains including citation networks, social networks, website networks, biochemicals, and co-occurrence networks.
All the datasets integrated into our IGL-Bench are either published or publicly accessible. Table [A.1](#A1.T1) and Table [A.2](#A1.T2) provide the detailed statistics of the benchmark datasets, and their detailed descriptions are as follows.

- •
Cora [] is a citation network dataset containing scientific publications classified into one of seven research areas. Each publication is represented by a feature vector indicating the presence or absence of words. The task is to predict the one-hot category label of a given publication. The dataset is licensed under Creative Commons 4.0.
- •
CiteSeer [] is a citation network dataset, consisting of scientific publications, each labeled with one of six classes in the ont-hot vector form. It is commonly used for tasks such as document classification and citation prediction. The dataset is licensed under Creative Commons 4.0.
- •
PubMed [] is a dataset of the biomedical literature, commonly used for tasks like document classification, information retrieval, and citation analysis. Each document is associated with a one-hot MeSH (Medical Subject Headings) topic label, which is used for document classification. The dataset is licensed under Creative Commons 4.0.
- •
Computers [] and Photo [] are Amazon products co-occurrence networks. Nodes represent goods and edges represent that two goods are frequently bought together. The task is to map goods to their respective product category. The datasets are licensed with MIT License.
- •
ogbn-arXiv [] is a benchmark citation network derived from the arXiv website, consisting of a large number of nodes and edges, covering a wide range of research fields. Each node represents a paper, which is described by the word embeddings extracted from the title and abstract. Each directed edge indicates the citations between papers. It is used for tasks such as node classification and link prediction in academic citation networks. The dataset is licensed under ODC-BY.
- •
Chameleon [] and Squirrel [] are the Wikipedia page-page networks. Nodes represent web pages and edges represent hyperlinks between them. Node features represent several informative nouns on the Wikipedia pages. The task is to predict the average daily traffic of the web page. The datasets are licensed with GPL-3.0 License.
- •
Actor [] is the actor-only induced subgraph of the film-director-actor-writer network. Each node corresponds to an actor, and the edge denotes co-occurrence on the same Wikipedia page. Node features represent keywords on the Wikipedia pages. The task is to classify nodes into five categories from the actor’s Wikipedia. The dataset is made public with a license unspecified.
- •
PTC-MR [] is a dataset of chemical compounds labeled with their mutagenic activity on bacteria. It has 344 molecules with a binary label indicating the carcinogenicity of compounds in rodents. It is used for tasks such as chemical compound classification and toxicity prediction. The dataset is made public with a license unspecified.
- •
FRANKENSTEIN [] is a set of molecular graphs with node features containing continuous values. A label denotes whether a molecule is a mutagen or non-mutagen. The dataset is made public with a license unspecified. The dataset is licensed under Creative Commons 1.0.
- •
PROTEINS [] is a set of macromolecules derived from Dobson and Doig, where nodes are structure elements. Edges denote nodes in an amino acid sequence or a close 3D space. The task is to predict whether a protein is an enzyme. The dataset is licensed under Creative Commons 4.0.
- •
D&D [] contains graphs of protein structures. A node represents an amino acid and edges are constructed if the distance of two nodes is less than 6Å. The label denotes whether a protein is an enzyme or a non-enzyme. The dataset is made public with a license unspecified.
- •
IMDB-B [] is a movie collaboration dataset where actor/actress and genre information of different movies are collected. For each graph, nodes represent actors/actresses and there is an edge between them if they appear in the same movie. The dataset is licensed under Creative Commons 4.0.
- •
REDDIT-B [] is a balanced dataset where each graph corresponds to an online discussion thread where nodes correspond to users, and there is an edge between two nodes if at least one of them responds to another’s comment. The dataset is licensed under Creative Commons 4.0.
- •
COLLAB [] is the scientific collaboration dataset, deriving from three public collaboration datasets. The networks of researchers were generated from each field, and each was labeled as the researcher field. The task is to determine to which field the collaboration network of a researcher belongs. The dataset is licensed under Creative Commons 4.0.

**Table A.1: Statistics of benchmark datasets for node classification.**
| Dataset | $\#$Nodes | $\#$Edges | $\#$Classes | $\#$Features | Avg. $\#$Degree | $\#$Homophily(^1^11We report the node homophily ratio [], which normalizes the edge homophily across neighborhoods.) |
| --- | --- | --- | --- | --- | --- | --- |
| Cora [] | 2,708 | 5,278 | 7 | 1,433 | 3.90 | 0.81 |
| CiteSeer [] | 3,327 | 4,614 | 6 | 3,703 | 2.77 | 0.74 |
| PubMed [] | 19,717 | 44,325 | 3 | 500 | 4.50 | 0.80 |
| Computers [] | 13,752 | 245,861 | 10 | 767 | 35.76 | 0.78 |
| Photo [] | 7,487 | 119,081 | 8 | 745 | 31.13 | 0.82 |
| ogbn-arXiv [] | 169,343 | 1,157,799 | 40 | 767 | 13.67 | 0.65 |
| Chameleon [] | 2,277 | 36,101 | 5 | 2,325 | 27.60 | 0.23 |
| Squirrel [] | 5,201 | 217,073 | 5 | 2,089 | 76.33 | 0.22 |
| Actor [] | 7,600 | 26,659 | 5 | 932 | 7.02 | 0.22 |

**Table A.2: Statistics of benchmark datasets for graph classification.**
| Dataset | $\#$Graphs | Avg.<br>$\#$Nodes | Avg.<br>$\#$Edges | $\#$Classes | $\#$Features | Avg.<br>$\#$Degree | $\#$$\bm{\mathcal{G}}_{\textbf{head}}$(^2^22For each dataset, we divide graphs into head and tail with a predefined ratio based on the Pareto principle [] (also known as 20/80 rule) to employ the 20% largest graphs as head graphs, and the rest 80% as tail graphs.) |
| --- | --- | --- | --- | --- | --- | --- | --- |
| PTC-MR [] | 344 | 14.29 | 14.69 | 2 | 18 | 2.06 | 67 |
| FRANKENSTEIN [] | 4,337 | 16.90 | 17.88 | 2 | 780 | 2.12 | 757 |
| PROTEINS [] | 1,113 | 39.06 | 72.82 | 2 | 3 | 3.73 | 218 |
| D&D [] | 1,178 | 284.32 | 715.66 | 2 | 89 | 5.03 | 234 |
| IMDB-B [] | 1,000 | 19.77 | 96.53 | 2 | 65 | 9.77 | 194 |
| REDDIT-B [] | 2,000 | 429.63 | 497.75 | 2 | 566 | 2.32 | 400 |
| COLLAB [] | 5000 | 74.49 | 2457.78 | 3 | 369 | 65.99 | 991 |

#### A.2 Benchmark Algorithms

In our developed IGL-Bench, we integrate 24 state-of-the-art IGL algorithms, including 10 node-level class-imbalanced IGL algorithms: DRGCN [], DPGNN [], ImGAGN [], GraphSMOTE [], GraphENS [], GraphMixup [], LTE4G [], TAM [], TOPOAUC [] and GraphSHA [];
12 node-level topology-imbalanced IGL algorithms: DEMO-Net [], meta-tail2vec [], Tail-GNN [], Cold Brew [], LTE4G [], RawlsGCN [], GraphPatcher [], ReNode [], TAM [], PASTEL [], TOPOAUC [], and HyperIMBA [];
4 graph-level class-imbalanced IGL algorithms: G^2GNN [], TopoImb [], DataDec [], and ImGKB [];
2 graph-level topology-imbalanced IGL algorithms: SOLT-GNN [] and TopoImb [].

We conclude the aforementioned representative IGL algorithms in Tabel [A.3](#A1.T3) in terms of the downstream task, method level, and computational complexity.
The Task column indicates the specific downstream tasks the algorithm can handle, where “NC” stands for node classification, and “GC” stands for graph classification.
The Data-Level column implies the algorithm handles the imbalance issue from the training data perspective, where “IG” stands for generating samples by interpolating, “AG” stands for generating samples by adversarial training, and “PL” stands for generating pseudo labels for a large number of unlabeled nodes.
The Algorithm-Level column suggests an algorithm-level contribution to solve the imbalance learning problems, where “MR” denotes refining GNN models for improving the representation learning process, “Loss” represents designing or engineering loss function for sample reweighting, etc., and “RG” stands for utilizing extra regularizers for the imbalance recalibrating. We further introduce all the IGL algorithms as follows.

**Table A.3: Summary of representative Imbalanced Graph Representation Learning (IGL) algorithms integrated in IGL-Bench concerning the imbalance types, downstream tasks, method levels, and computational complexity. We also provide public access to the official algorithm implementations.**
| Type | Algorithm | Task | Data-Level | Algorithm-Level | Computational<br>Complexity(^3^33For brevity, only the main bottlenecks of the algorithm’s computational complexity are analyzed here, while the remaining negligible parts are uniformly ignored. The meanings of notations follow definitions in Section 2.) | Code |  |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| IG | AG | PL | MR | Loss | RG |  |  |  |  |  |  |
| Node-Level<br>Class-Imbalance |  | DRGCN [] | NC |  | ✓ |  |  |  | ✓ | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/codeshareabc/DRGCN) |
|  | DPGNN [] | NC |  |  | ✓ | ✓ | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/YuWVandy/DPGNN) |  |
|  | ImGAGN [] | NC |  | ✓ |  |  |  |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/Leo-Q-316/ImGAGN) |  |
|  | GraphSMOTE [] | NC | ✓ |  |  |  |  |  | $\mathcal{O}(|\mathcal{V}|^{2})+\mathcal{O}(|\mathcal{E}|)$ | [link](https://github.com/TianxiangZhao/GraphSmote) |  |
|  | GraphENS [] | NC | ✓ |  |  |  |  |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/JoonHyung-Park/GraphENS) |  |
|  | GraphMixup [] | NC | ✓ |  |  |  |  |  | $\mathcal{O}(|\mathcal{V}|^{2})+\mathcal{O}(|\mathcal{E}|)$ | [link](https://github.com/LirongWu/GraphMixup) |  |
|  | LTE4G [] | NC |  |  |  | ✓ |  | ✓ | $\mathcal{O}(|\mathcal{V}|^{2})+\mathcal{O}(|\mathcal{E}|)$ | [link](https://github.com/SukwonYun/LTE4G) |  |
|  | TAM [] | NC |  |  |  |  | ✓ |  | $\mathcal{O}(|\mathcal{V}|C+|\mathcal{E}|)$ | [link](https://github.com/Jaeyun-Song/TAM) |  |
|  | TOPOAUC [] | NC |  |  |  |  | ✓ | ✓ | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/TraceIvan/TOPOAUC) |  |
|  | GraphSHA [] | NC | ✓ |  |  |  |  |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/wenzhilics/GraphSHA) |  |
| Node-Level<br>Topology-Imbalance | local | DEMO-Net [] | NC |  |  |  | ✓ |  |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/jwu4sml/DEMO-Net) |
| meta-tail2vec [] | NC |  |  |  | ✓ | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/smufang/meta-tail2vec) |  |  |
|  | Tail-GNN [] | NC |  |  |  | ✓ | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/shuaiOKshuai/Tail-GNN) |  |
|  | Cold Brew [] | NC |  |  |  | ✓ | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/amazon-research/gnn-tail-generalization) |  |
|  | LTE4G [] | NC |  |  |  | ✓ |  | ✓ | $\mathcal{O}(|\mathcal{V}|^{2})+\mathcal{O}(|\mathcal{E}|)$ | [link](https://github.com/SukwonYun/LTE4G) |  |
|  | RawlsGCN [] | NC |  |  |  |  | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/jiank2/RawlsGCN) |  |
|  |  | GraphPatcher [] | NC | ✓ |  |  |  |  | ✓ | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/jumxglhf/GraphPatcher) |
|  | global | ReNode [] | NC |  |  |  |  | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/victorchen96/ReNode) |
|  | TAM [] | NC |  |  |  |  | ✓ |  | $\mathcal{O}(|\mathcal{V}|C+|\mathcal{E}|)$ | [link](https://github.com/Jaeyun-Song/TAM) |  |
|  | PASTEL [] | NC |  |  |  | ✓ | ✓ | ✓ | $\mathcal{O}(|\mathcal{V}^{2}|)+\mathcal{O}(|\mathcal{E}|)$ | [link](https://github.com/RingBDStack/PASTEL) |  |
|  | TOPOAUC [] | NC |  |  |  |  | ✓ | ✓ | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/TraceIvan/TOPOAUC) |  |
|  |  | HyperIMBA [] | NC |  |  |  | ✓ | ✓ |  | $\mathcal{O}(|\mathcal{V}|+|\mathcal{E}|)$ | [link](https://github.com/RingBDStack/HyperIMBA) |
| Graph-Level<br>Class-Imbalance |  | G^2GNN [] | GC | ✓ |  |  | ✓ | ✓ |  | $\mathcal{O}(\binom{|\mathbf{G}|}{2}\max|\mathcal{V}^{\mathcal{G}_{i}}|^{3})$ | [link](https://github.com/submissionconff/G2GNN) |
|  | TopoImb [] | NC, GC |  |  |  |  | ✓ |  | $\mathcal{O}(\sum(|\mathcal{V}^{\mathcal{G}_{i}}|+|\mathcal{E}^{\mathcal{G}_{i}}|))$ | [link](https://github.com/zihan448/TopoImb) |  |
|  | DataDec [] | NC, GC |  |  |  | ✓ |  |  | $\mathcal{O}(\sum(|\mathcal{V}^{\mathcal{G}_{i}}|+|\mathcal{E}^{\mathcal{G}_{i}}|))$ | [link](https://www.dropbox.com/sh/8jaq9zekzl3khni/AAA0kNDs_UMxj4YbTEKKyiXna?dl=0) |  |
|  |  | ImGKB [] | GC |  |  |  | ✓ | ✓ |  | $\mathcal{O}(\sum(|\mathcal{V}^{\mathcal{G}_{i}}|+|\mathcal{E}^{\mathcal{G}_{i}}|))$ | [link](https://github.com/Tommtang/ImGKB) |
| Graph-Level<br>Topology-Imbalance |  | SOLT-GNN [] | GC |  |  |  |  | ✓ | ✓ | $\mathcal{O}(\sum(|\mathcal{V}^{\mathcal{G}_{i}}|+|\mathcal{E}^{\mathcal{G}_{i}}|))$ | [link](https://github.com/shuaiOKshuai/SOLT-GNN) |
|  | TopoImb [] | NC, GC |  |  |  |  | ✓ |  | $\mathcal{O}(\sum(|\mathcal{V}^{\mathcal{G}_{i}}|+|\mathcal{E}^{\mathcal{G}_{i}}|))$ | [link](https://github.com/zihan448/TopoImb) |  |

- •
DRGCN [] is proposed to address the node-level class-imbalance issue. It employs a GNN-centric strategy, incorporating a conditioned generative adversarial network (GAN) to create synthetic nodes to balance redistribution. Additionally, it utilizes a KL-divergence constraint to harmonize the representation distribution of unlabeled nodes with that of labeled ones. The code is made available with a license unspecified.
- •
DPGNN [] is proposed to address the node-level class-imbalance issue. It employs a class prototype-driven training approach to balance training loss across classes and transfer knowledge from head classes to tail classes, with the help of distance metric learning to accurately capture the relative positions of nodes concerning class prototypes, as well as smoothing representations of adjacent nodes while separating interclass prototypes. The code is made available with a license unspecified.
- •
ImGAGN [] is proposed to address the node-level class-imbalance issue. It applies the generative adversarial network (GAN) to generate synthetic nodes, which simulates both the minority class nodes’ attribute distribution and network topological structure distribution by generating a set of synthetic minority nodes such that the number of nodes in different classes can be balanced. The code is made available with a license unspecified.
- •
GraphSMOTE [] is proposed to address the node-level class-imbalance issue. It evolves around the generation of synthetic nodes to balance classes by a technique inspired by SMOTE [], which is the first data interpolation method on graphs by generating a synthetic minority node through interpolation between two real minority nodes in the embedding space. It pre-trains an edge predictor using a graph reconstruction objective on real nodes and existing edges to determine the connectivity between the synthetic node and existing nodes. The code is made available with a license unspecified.
- •
GraphENS [] is proposed to address the node-level class-imbalance issue. It creates a synthetic minority node by blending a real minority node with a randomly chosen target node. Notably, GraphENS [] prioritizes the neighbors of minority nodes, recognizing their significant informational value. To address this bias, it incorporates neighbor sampling and saliency-based node mixing techniques. The code is made available with an MIT License.
- •
GraphMixup [] is proposed to address the node-level class-imbalance issue. GraphMixup [] executes reinforcement mixup within the semantic space instead of the input or embedding space, thereby averting the creation of out-of-domain minority samples. It integrates two supplementary self-supervised learning objectives: local-path prediction and global-path prediction, aiming to encompass both local and global insights within the graph structure. The code is made available with an MIT License.
- •
LTE4G [] is proposed to address the node-level class-imbalance issue. It takes into account the imbalance in both node classes and degrees. LTE4G [] divides nodes into balanced subsets and assigns them to specialized Graph Neural Networks (GNNs) based on their similarity to each class prototype vector. The class with the highest similarity score is assigned to each node subset. Subsequently, LTE4G [] utilizes knowledge distillation to train class-specific student models, thereby improving classification performance. The code is made available with a license unspecified.
- •
TAM [] is proposed to address the node-level class-imbalance issue and topology-imbalance issue simultaneously. TAM [] resolves the class-imbalance issue by integrating graph topology information into its loss function designs and addressing the decreased homogeneity among minority nodes. Particularly, TAM [] introduces connectivity- and distribution-aware margins to guide the model, highlighting class-wise connectivity and neighbor-label distribution in an innovative manner. The code is made available with an MIT License.
- •
TOPOAUC [] is proposed to address the node-level class-imbalance and topology-imbalance issue simultaneously. It develops a multi-class AUC optimization work to deal with the class imbalance problem. With respect to topology imbalance, TOPOAUC [] proposes a Topology-Aware Importance Learning mechanism (TAIL), which considers the topology of pairwise nodes and different contributions of topology information to pairwise node neighbors. The code is made available with a license unspecified.
- •
GraphSHA [] is proposed to address the node-level class-imbalance issue. It aims to expand the decision boundaries of minority classes by generating more challenging synthetic samples from these classes. Additionally, GraphSHA [] introduces a module named SemiMixup, which is designed to transfer the enlarged boundary information into the interior of the minority classes while preventing the leakage of information from the minority classes to their neighboring majority classes. This helps to enhance the separability of minority classes without compromising their integrity. The code is made available with an MIT License.
- •
DEMO-Net [] is proposed to address the node-level topology-imbalance issue. Inspired by the Weisfeiler-Lehman graph isomorphism test, DEMO-Net [] explicitly captures integrated graph topology and node attributes. It introduces multi-task graph convolution, where each task focuses on learning node representations for nodes with specific degree values, thereby preserving the degree-specific graph structure. Furthermore, DEMO-Net [] devises a new graph-level pooling/readout scheme to learn graph representations, ensuring they reside in a degree-specific Hilbert kernel space. The code is made available with a license unspecified.
- •
meta-tail2vec [] is proposed to address the node-level local topology-imbalance issue. It frames the objective of learning from imbalanced data, particularly focusing on learning embeddings for tail nodes, as a few-shot regression task, considering the limited connections associated with each tail node. Moreover, meta-tail2vec [] recognizes that each node exists within its unique local context and therefore adapts the regression model individually for each tail node, personalizing the learning process. The code is made available with an MIT License.
- •
Tail-GNN [] is proposed to address the node-level local topology-imbalance issue. While GNNs are capable of learning effective node representations, they often handle all nodes in a generic manner and do not specifically cater to the numerous tail nodes. Tail-GNN [] leverages the innovative concept of transferable neighborhood translation to capture the diverse relationships between a node and its neighboring nodes. In essence, Tail-GNN [] develops a node-specific adaptation technique that tailors the global translation to the individual needs of each node. The code is made available with a license unspecified.
- •
Cold Brew [] is proposed to address the node-level local topology-imbalance issue, with a particular focus on the most extreme cases in graphs where a node lacks any neighboring connections, known as the Strict Cold Start (SCS) problem []. Cold Brew [] employs a teacher-student distillation framework to address the SCS issue and the challenge posed by noisy neighbors in the context of GNNs. Additionally, Cold Brew [] introduces the concept of feature contribution ratio, a metric that quantifies the performance of inductive GNNs in resolving the SCS problem. The code is made available with an Apache-2.0 License.
- •
RawlsGCN [] is proposed to address the node-level local topology-imbalance issue. It approaches the issue of degree-related performance disparities through the lens of the Rawlsian difference principle, a concept derived from the theory of distributive justice. RawlsGCN [] is designed to equalize the performance between nodes with low and high degrees while also optimizing for task-specific objectives, ensuring a fairer allocation of predictive utility across the graph. The code is made available with an MIT License.
- •
GraphPatcher [] is proposed to address the node-level local topology-imbalance issue. It suggests a test-time augmentation framework designed to improve the test-time generalization ability of any GNNs for low-degree nodes. In detail, GraphPatcher [] successively creates virtual nodes to repair the artificially generated low-degree nodes through corruptions, with the goal of incrementally reconstructing the target GNN’s predictions across a series of progressively corrupted nodes. The code is made available with a license unspecified.
- •
ReNode [] is proposed to address the node-level global topology-imbalance issue. ReNode [] adjusts the weights of labeled nodes according to their proximity to class boundaries, thereby enhancing performance, especially for nodes near boundaries and those distant from them. Additionally, a metric is devised to measure this imbalance, utilizing influence conflict detection. ReNode [] effectively addresses both class-imbalance and topology-imbalance challenges concurrently. The code is made available with an MIT License.
- •
PASTEL [] is proposed to address the node-level global topology-imbalance issue. PASTEL [] addresses topology imbalance by optimizing the paths of information propagation. Its goal is to mitigate the under-reaching and over-squashing effects by improving intra-class connectivity and employing a position encoding mechanism. Additionally, PASTEL [] utilizes a class-wise conflict measure for edge weights to aid in node class separation. The code is made available with an MIT License.
- •
HyperIMBA [] is proposed to address the node-level global topology-imbalance issue. HyperIMBA [] employs hyperbolic geometric embedding to assess the hierarchy of labeled nodes. It then modifies label information propagation and adjusts the objective margin according to the node’s hierarchy, effectively tackling issues arising from hierarchy imbalance. The code is made available with a license unspecified.
- •
G^2GNN [] is proposed to address the graph-level class-imbalance issue. It employs additional supervision at both global and local levels: globally, through neighboring graphs, and locally, via stochastic augmentations. G^2GNN [] constructs a Graph of Graphs (GoG) by utilizing kernel similarity and implements GoG propagation for information aggregation. Furthermore, it utilizes topological augmentation with self-consistency regularization at the local level. These combined strategies improve model generalizability and consequently enhance classification performance. The code is made available with a license unspecified.
- •
TopoImb [] is proposed to address the graph-level class-imbalance and topology-imbalance issues. Graph-level topology imbalance often stems from uneven motif distribution (e.g., functional groups), resulting in a lack of training instances for minority groups. TopoImb [] tackles this challenge by dynamically updating the identification of topology groups and assigning importance weights to under-represented instances during training. This approach enhances the learning efficacy of minority topology groups and mitigates overfitting to majority groups. The code is made available with a license unspecified.
- •
DataDec [] is proposed to address both the node-level and graph-level class-imbalance issues. DataDec [] develops a unified data-model dynamic sparsity framework to address challenges brought by training upon massive class-imbalanced graph data. The key idea of DataDec [] is to identify the informative subset dynamically during the training process by adopting sparse graph contrastive learning. The code is made available with a license unspecified.
- •
ImGKB [] is proposed to address the graph-level class-imbalance issue. It combines the restricted random walk kernel with the global graph information bottleneck (GIB) [] to enhance the performance of imbalanced graph classification tasks. To prevent the dominant class graphs from introducing redundant information into the kernel outputs, ImGKB [] frames the entire kernel learning process as a Markovian decision process. It then utilizes the global GIB [] approach to optimize the learning, ensuring that the kernel effectively captures the relevant information for each class. The code is made available with a license unspecified.
- •
SOLT-GNN [] is proposed to address both the graph-level topology-imbalance issues. Graphs with larger sizes (number of nodes) tend to possess more complex topological structures. To counter performance biases caused by the intricate topological structures, SOLT-GNN [] enhances the performance of smaller graphs. It identifies co-occurrence patterns in larger graphs (or “head” graphs) and transfers this knowledge to augment smaller graphs, improving their performance. The code is made available with a license unspecified.

### Appendix B Details of the Dataset Settings

#### B.1 Imbalance Ratio Definition

**Table B.1: Definitions of the imbalance ratio ($\rho$) across different imbalance types.**
| Imbalance Type | Definition | Explanation |
| --- | --- | --- |
| Node-Level Class-Imbalance<br>Graph-Level Class-Imbalance | $\rho=\dfrac{\max_{i=1}^{C}|\mathcal{C}_{i}|}{\min_{j=1}^{C}|\mathcal{C}_{j}|}$ | The imbalance ratio is set to the ratio between the number<br>of samples ($|\mathcal{C}|$) in the majority and the minority class. |
| Node-Level<br>Topology-Imbalance<br>(local and global) | $\rho=\dfrac{\frac{1}{|\mathcal{H}_{\text{n}}|}\sum d(v),v\in\mathcal{H}_{\text{n}}}{\frac{1}{|\mathcal{T}_{\text{n}}|}\sum d(v),v\in\mathcal{T}_{\text{n}}}$ | The local imbalance ratio is set to the ratio of the average<br>node degree ($d(v)$) of the head node set ($\mathcal{H}_{\text{n}}$) to the aver-<br>age node degree of the tail node set ($\mathcal{T}_{\text{n}}$). |
| $\rho=-10\cdot\log|RC\cdot SC|$ | The global imbalance ratio is set to the negative logarithm<br>of the absolute value of the product of the Reaching<br>Coefficient ($RC$) and the Squashing Coefficient ($SC$). |  |
| Graph-Level<br>Topology-Imbalance | $\rho=\dfrac{\frac{1}{|\mathcal{H}_{\text{g}}|}\sum|\mathcal{G}_{i}|,\mathcal{G}_{i}\in\mathcal{H}_{\text{g}}}{\frac{1}{|\mathcal{T}_{\text{g}}|}\sum|\mathcal{G}_{j}|,\mathcal{G}_{j}\in\mathcal{T}_{\text{g}}}$ | The imbalance ratio is set to the ratio of the average graph<br>size (number of nodes) of the head graph set ($\mathcal{H}_{\text{g}}$) to the<br>average graph size of the tail graph set ($\mathcal{T}_{\text{g}}$). |

We provide additional explanations on the details of the imbalance ratio defined in Tabel [B.1](#A2.T1).

- •
Node/Graph-Level Class-Imbalance.
Given a set of labeled training node/graph classes $\mathcal{V}_{L}=\bigcup_{1\leq i\leq C}\mathcal{C}_{i}$, the imbalance ratio is defined to be the ratio between the number of nodes/graphs in the majority class and the number of nodes/graphs in the minority class, i.e.,
$\rho=\frac{\max_{i=1}^{C}|\mathcal{C}_{i}|}{\min_{j=1}^{C}|\mathcal{C}_{j}|}.$
(B.1)
Node-level class-imbalance occurs when there is an uneven spread of labeled nodes among different classes. This can lead the model to prioritize learning from classes abundant in labeled instances, potentially neglecting those with fewer examples. Graph-level is similar to node-level class-imbalance. This issue frequently arises in practical contexts, such as imbalanced chemical compound classification, where the distributions of labeled graphs are skewed. Typically, this bias favors the majority class, which comprises more labeled graphs.
- •
Node-Level Topology-Imbalance.
$-$
Local Imbalance. Given a set of labeled nodes $\mathcal{V}_{L}=\{v_{1},\cdots,v_{N}\}$ with the splits designating the top 20% of nodes by degree as high-degree head node set $\mathcal{H}_{\text{n}}$ and the rest 80% as low-degree tail node set $\mathcal{T}_{\text{n}}$ following the Pareto principle (also known as the 20/80 rule) [].
The local node-level topology-imbalance is set to the ratio of the average node degree of the head training node set to the average node degree of the tail training node set, i.e.,
$\rho=\dfrac{\frac{1}{|\mathcal{H}_{\text{n}}|}\sum d(v),v\in\mathcal{H}_{\text{n}}}{\frac{1}{|\mathcal{T}_{\text{n}}|}\sum d(v),v\in\mathcal{T}_{\text{n}}},$
(B.2)
where $d(\cdot)$ denotes node degree and we require $d(v)\geq 1$. Node degrees frequently exhibit a long-tail distribution. Head nodes, which have high degrees, benefit from richer structural information, resulting in superior performance in downstream tasks such as node classification. In contrast, tail nodes with low degrees possess limited topological information, which hampers their performance [, ].
$-$
Global Imbalance. The global imbalance is facilitated by two aspects: Under-Reaching and Over-Squashing []. Under-Reaching refers to the phenomenon that the influence from labeled nodes decays with the topology distance, resulting in the nodes being far away from labeled nodes lacking supervision information. Over-Squashing refers to the phenomenon of the supervision information of valuable labeled nodes being squashed when passing across the narrow path together with other useless information. The global node-level topology-imbalance ratio is set to the 10x negative logarithm of the absolute value of the product of the Reaching Coefficient ($RC$) and the Squashing Coefficient ($SC$) [], i.e.,
$\rho=-10\cdot\log|RC\cdot SC|.$
(B.3)
$\circ$
Reaching Coefficient ($\bm{RC}$) is the mean length of the shortest path from unlabeled to the labeled nodes of their corresponding classes, i.e.,
$RC=\frac{1}{|\mathcal{V}_{U}|}\sum_{v_{i}\in\mathcal{V}_{U}}\frac{1}{|\mathcal{V}^{\textbf{y}_{i}}_{L}|}\sum_{v_{j}\in\mathcal{V}^{\textbf{y}_{i}}_{L}}\left(1-\frac{\log|\mathcal{P}_{sp}(v_{i},v_{j})|}{\log D_{\mathcal{G}}}\right),$
(B.4)
where $\mathcal{V}^{\textbf{y}_{i}}_{L}$ denotes the nodes in $\mathcal{V}_{L}$ whose label is $\textbf{y}_{i}$, $\mathcal{P}_{sp}(v_{i},v_{j})$ denotes the shortest path between $v_{i}$ and $v_{j}$, and $|\mathcal{P}_{sp}(v_{i},v_{j})|$ denotes its length, and $D_{\mathcal{G}}$ is the graph diameter.
$\circ$
Squashing Coefficient ($\bm{SC}$) is the mean Ricci curvature [] of edges on the shortest path from unlabeled nodes to the labeled nodes of their corresponding classes, i.e.,
$SC=\frac{1}{|\mathcal{V}_{U}|}\sum_{v_{i}\in\mathcal{V}_{U}}\frac{1}{|\mathcal{N}_{\textbf{y}_{i}}(v_{i})|}\sum_{v_{j}\in\mathcal{N}_{\textbf{y}_{i}}(v_{i})}\frac{\sum_{e_{kt}\in\mathcal{P}_{sp}(v_{i},v_{j})}Ric(v_{k},v_{t})}{|\mathcal{P}_{sp}(v_{i},v_{j})|},$
(B.5)
where $\mathcal{N}_{\textbf{y}_{i}}(v_{i})$ denotes the labeled nodes of class $\textbf{y}_{i}$ that can reach the node $v_{i}$, $Ric(\cdot,\cdot)$ denotes the Ricci curvature, and $|\mathcal{P}_{sp}(v_{i},v_{j})|$ denotes the length of shortest path between node pair $v_{i}$ and $v_{j}$.
- •
Graph-Level Topology-Imbalance.
Given a set of labeled graphs $\mathbf{G}_{L}=\{\mathcal{G}_{1},\cdots,\mathcal{G}_{N}\}$ with the splits designating the top 20% of graphs by graph size (the number of nodes) as large-size head graph set $\mathcal{H}_{\text{g}}$ and the rest 80% as small-size tail graph set $\mathcal{T}_{\text{g}}$ following the Pareto principle (20/80 rule) [].
The imbalance ratio is set to the ratio of the average graph size of the head graph set to the average graph size of the tail graph set, i.e.,
$\rho=\frac{\frac{1}{|\mathcal{H}_{\text{g}}|}\sum|\mathcal{G}_{i}|,\mathcal{G}_{i}\in\mathcal{H}_{\text{g}}}{\frac{1}{|\mathcal{T}_{\text{g}}|}\sum|\mathcal{G}_{j}|,\mathcal{G}_{j}\in\mathcal{T}_{\text{g}}}.$
(B.6)
The complex connections within graphs can result in topology imbalances across different graphs. This imbalance frequently appears as variations in graph sizes. Generally, graphs with larger sizes tend to be more expressive and thus produce better performance compared to smaller counterparts. This dynamic can introduce bias in applications like molecular or protein prediction.

#### B.2 Manipulated Class-Imbalanced Datasets for Node Classification

Dataset Settings.
We perform the node classification task semi-supervised on nine manipulated class-imbalanced datasets, where the train/val/test split satisfies the ratio of 1:1:8. Specifically, to construct the long-tailed distribution of the number of training nodes concerning varying imbalance ratio $\rho$ defined in Eq. ([B.1](#A2.E1)), we assume that the number of nodes in each class in the training set grows exponentially, i.e., $|\mathcal{C}_{i+1}|=\mu|\mathcal{C}_{i}|$, where $i$ is the class index, $|\mathcal{C}_{i}|$ is the number of $i$-th indexed class training samples and $\mu\in$ (0,1) is the coefficient.
Therefore, given the total number of nodes in the training set and $\rho$, the number of nodes used for training in each class can be calculated deterministically. All nodes other than those used for training and validation are assigned to the test set.
To provide a thorough evaluation, we consider three typical situations in IGL-Bench, i.e., the class-balanced setting ($\rho=$ 1 and each class has an equal number of training nodes), the class-imbalanced setting ($\rho=$ 20), and the extreme class-imbalanced setting ($\rho=$ 100).

Dataset Preview.
We present a visualization of the distribution of the number of nodes in the training sets for each dataset in Figure [B.1](#A2.F1). It clearly reveals that the distribution of training nodes follows a long-tail pattern. Notably, as the parameter $\rho$ increases, the number of nodes decreases more sharply, accentuating the long-tail effect. The higher the value of $\rho$, the more pronounced decline in node numbers, resulting in an even longer and more extended “tail”. This trend indicates a significant imbalance, where a few classes are highly prevalent while the majority are sparsely represented.

Figure: Figure B.1: Visualizations of the distribution of the number of nodes in the training sets for nine benchmark datasets with different imbalance ratios. Note that, we calculate the imbalance ratio for the ogbn-arXiv [] by the ratio between the number of nodes/graphs in the majority class and the number of nodes/graphs in the sub-minority class due to insufficient training nodes in some classes.
Refer to caption: /html/2406.09870/assets/x20.png

**Table B.2: Statistics of the manipulated local topology-imbalanced datasets (training) for node classification. The number of nodes for each class is equal (class-balanced), and the imbalance ratio $\rho$ is the ratio between the average degree of the head nodes and the average degree of the tail nodes.**
| Dataset | Level | $\#$Nodes<br>per Class | $\#$Head Nodes<br>per Class | $\#$Tail Nodes<br>per Class | Avg. $\#$Degree<br>(Head Nodes) | Avg. $\#$Degree<br>(Tail Nodes) | Imbalance<br>Ratio $\bm{\rho}$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Cora [] | Low | 39 | 4 | 35 | 5.64 | 2.84 | 1.98 |
| Mid | 8 | 31 | 8.96 | 2.74 | 3.27 |  |  |
| High | 12 | 27 | 13.53 | 2.00 | 6.74 |  |  |
| CiteSeer [] | Low | 55 | 6 | 49 | 4.47 | 1.83 | 2.44 |
| Mid | 12 | 43 | 6.78 | 1.62 | 4.18 |  |  |
| High | 18 | 37 | 9.61 | 1.17 | 8.21 |  |  |
| PubMed [] | Low | 657 | 66 | 591 | 8.58 | 2.08 | 4.12 |
| Mid | 132 | 525 | 15.04 | 1.83 | 8.23 |  |  |
| High | 198 | 459 | 22.93 | 1.51 | 15.23 |  |  |
| Computers [] | Low | 138 | 14 | 124 | 58.21 | 21.85 | 2.66 |
| Mid | 28 | 110 | 99.77 | 20.23 | 4.93 |  |  |
| High | 42 | 96 | 133.14 | 12.98 | 10.26 |  |  |
| Photo [] | Low | 96 | 10 | 86 | 48.96 | 19.56 | 2.50 |
| Mid | 20 | 76 | 84.03 | 17.50 | 4.80 |  |  |
| High | 30 | 66 | 116.33 | 13.13 | 8.85 |  |  |
| ogbn-arXiv [] | Low | 423 | 42 | 381 | 21.56 | 8.22 | 2.62 |
| Mid | 84 | 339 | 40.75 | 5.10 | 7.99 |  |  |
| High | 126 | 297 | 56.08 | 3.80 | 14.74 |  |  |
| Chameleon [] | Low | 46 | 5 | 41 | 51.28 | 12.12 | 4.23 |
| Mid | 10 | 36 | 108.28 | 12.20 | 8.88 |  |  |
| High | 15 | 31 | 159.44 | 9.29 | 17.16 |  |  |
| Squirrel [] | Low | 104 | 11 | 93 | 162.02 | 22.35 | 7.24 |
| Mid | 22 | 82 | 328.33 | 21.71 | 15.13 |  |  |
| High | 33 | 71 | 496.67 | 14.75 | 33.67 |  |  |
| Actor [] | Low | 152 | 15 | 137 | 15.24 | 4.66 | 3.27 |
| Mid | 30 | 122 | 26.77 | 4.11 | 6.52 |  |  |
| High | 45 | 107 | 37.93 | 3.02 | 12.56 |  |  |

#### B.3 Manipulated Local Topology-Imbalanced Datasets for Node Classification

Dataset Settings.
We conduct the semi-supervised node classification task on nine manipulated locally topology-imbalanced datasets. The datasets are split into training, validation, and test sets with a ratio of 1:1:8.
Local topology-imbalance is characterized by a long-tailed distribution in terms of node degree. Following the Pareto principle (the 20/80 rule) [], we designate the top 20% of nodes by degree as high-degree (head) nodes, and the remaining 80% as low-degree (tail) nodes.
High-degree nodes benefit from more abundant structural information with superior performance in downstream tasks, while low-degree nodes suffer from limited topological information, which hinders their performance.
To evaluate local topology-imbalance, we randomly select training and validation nodes according to the pre-defined splitting ratio (10%/10%) while ensuring an equal number of nodes per class for fairness. The remaining nodes are used for testing.
To thoroughly assess the performance of the IGL algorithms, we create training sets with different imbalance ratios, as defined in Eq. ([B.2](#A2.E2)). These ratios depend on the proportion of nodes selected from the head and tail sets. We repeat the node selection process multiple times, calculate the resulting imbalance ratios, and choose three groups of splits exhibiting significant variations in the imbalance ratio. These groups are categorized as Low, Mid, and High, based on their respective levels of local topology imbalance.

Dataset Preview.
We conclude the statistics of the manipulated local topology-imbalanced datasets (training) for node classification in Table [B.2](#A2.T2). To guarantee a fair evaluation, we ensure the number of nodes for each class is equal (class-balanced). We also observe that the imbalance ratio corresponding to Low, Mid, and High roughly doubles, which can better simulate the various degrees of the imbalanced distribution of node degree.

#### B.4 Manipulated Global Topology-Imbalanced Datasets for Node Classification

Dataset Settings.
We conduct the semi-supervised node classification task on eight manipulated globally topology-imbalanced datasets. We select 10% nodes for training and 10% nodes for validation. For a fair comparison, we assign the same number of nodes for each class to guarantee the class-balance when evaluating the global topology-imbalance issue. The remaining nodes are used for testing.
The global topology-imbalance issue is facilitated by both the under-reaching and over-squashing phenomenon, which are quantified with the metrics of the Reaching Coefficient ($RC$) and the Squashing Coefficient ($SC$). Considering that $RC$ and $SC$ reflect two aspects of the causes of global topology-imbalance simultaneously, and both variables change monotonically, the negative logarithm of their product is used to define the imbalance ratio according to Eq. ([B.3](#A2.E3)) (since $RC$ is positive and $SC$ is negative, the purpose of 10x and taking the negative logarithm is to amplify the observable variation of the imbalance ratio). Note that, larger $RC$ means better reachability and larger $SC$ means lower squashing. Consequently, the lower the degree of global topology-imbalance ratio.
We randomly generate 100 groups of training splits and calculate the imbalance ratio for each.
We select 10 groups with the minimum, maximum, and uniformly varying imbalance ratios within the range to simulate the change in the degree of global topology imbalance from high to low.

**Table B.3: Statistics of the manipulated global topology-imbalanced datasets (training) for node classification. The number of nodes for each class is equal (class-balanced), and the imbalance ratio $\rho$ is the 10x negative logarithm of the absolute value of the product of $RC$ and $SC$.**
| Imbalance<br>Level | Split | Dataset | Cora<br>[] | CiteSeer<br>[] | PubMed<br>[] | Computers<br>[] | Photo<br>[] | Chameleon<br>[] | Squirrel<br>[] | Actor<br>[] |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Low<br>↓<br>Mid<br>↓<br>High | 1 | $RC$ | 0.60 | 0.84 | 0.62 | 0.73 | 0.54 | 0.49 | 0.46 | 0.56 |
| $SC$ | -0.62 | -0.41 | -0.81 | -0.87 | -0.63 | -0.66 | -0.53 | -0.71 |  |  |
| $\bm{\rho}$ | 4.23 | 4.62 | 3.02 | 1.99 | 4.70 | 4.87 | 6.13 | 4.01 |  |  |
| 2 | $RC$ | 0.60 | 0.84 | 0.61 | 0.72 | 0.54 | 0.49 | 0.45 | 0.56 |  |
| $SC$ | -0.62 | -0.41 | -0.81 | -0.87 | -0.63 | -0.67 | -0.53 | -0.71 |  |  |
| $\bm{\rho}$ | 4.26 | 4.66 | 3.03 | 1.99 | 4.71 | 4.87 | 6.22 | 4.03 |  |  |
| 3 | $RC$ | 0.60 | 0.84 | 0.61 | 0.72 | 0.54 | 0.48 | 0.45 | 0.56 |  |
| $SC$ | -0.62 | -0.41 | -0.81 | -0.87 | -0.63 | -0.67 | -0.53 | -0.71 |  |  |
| $\bm{\rho}$ | 4.26 | 4.69 | 3.03 | 2.00 | 4.72 | 4.93 | 6.23 | 4.02 |  |  |
| 4 | $RC$ | 0.60 | 0.83 | 0.61 | 0.72 | 0.54 | 0.48 | 0.45 | 0.56 |  |
| $SC$ | -0.62 | -0.41 | -0.81 | -0.87 | -0.63 | -0.67 | -0.54 | -0.70 |  |  |
| $\bm{\rho}$ | 4.31 | 4.75 | 3.04 | 2.01 | 4.73 | 4.96 | 6.21 | 4.08 |  |  |
| 5 | $RC$ | 0.59 | 0.83 | 0.61 | 0.72 | 0.54 | 0.46 | 0.43 | 0.55 |  |
| $SC$ | -0.62 | -0.40 | -0.81 | -0.87 | -0.63 | -0.67 | -0.53 | -0.71 |  |  |
| $\bm{\rho}$ | 4.35 | 4.77 | 3.04 | 2.02 | 4.73 | 5.11 | 6.41 | 4.10 |  |  |
| 6 | $RC$ | 0.59 | 0.81 | 0.61 | 0.72 | 0.54 | 0.46 | 0.43 | 0.55 |  |
| $SC$ | -0.62 | -0.41 | -0.81 | -0.87 | -0.63 | -0.67 | -0.54 | -0.70 |  |  |
| $\bm{\rho}$ | 4.35 | 4.80 | 3.05 | 2.03 | 4.74 | 5.11 | 6.36 | 4.16 |  |  |
| 7 | $RC$ | 0.59 | 0.81 | 0.61 | 0.72 | 0.54 | 0.45 | 0.41 | 0.54 |  |
| $SC$ | -0.62 | -0.40 | -0.81 | -0.87 | -0.62 | -0.67 | -0.53 | -0.70 |  |  |
| $\bm{\rho}$ | 4.35 | 4.87 | 3.08 | 2.04 | 4.75 | 5.20 | 6.56 | 4.16 |  |  |
| 8 | $RC$ | 0.58 | 0.80 | 0.60 | 0.72 | 0.54 | 0.44 | 0.41 | 0.54 |  |
| $SC$ | -0.63 | -0.40 | -0.81 | -0.87 | -0.62 | -0.67 | -0.54 | -0.70 |  |  |
| $\bm{\rho}$ | 4.38 | 4.94 | 3.11 | 2.04 | 4.76 | 5.32 | 6.63 | 4.19 |  |  |
| 9 | $RC$ | 0.58 | 0.80 | 0.60 | 0.72 | 0.54 | 0.42 | 0.40 | 0.54 |  |
| $SC$ | -0.63 | -0.40 | -0.81 | -0.87 | -0.62 | -0.67 | -0.53 | -0.70 |  |  |
| $\bm{\rho}$ | 4.39 | 4.96 | 3.12 | 2.05 | 4.77 | 5.47 | 6.73 | 4.20 |  |  |
| 10 | $RC$ | 0.58 | 0.80 | 0.59 | 0.72 | 0.53 | 0.41 | 0.41 | 0.54 |  |
| $SC$ | -0.62 | -0.39 | -0.81 | -0.87 | -0.62 | -0.68 | -0.52 | -0.69 |  |  |
| $\bm{\rho}$ | 4.43 | 5.05 | 3.16 | 2.06 | 4.77 | 5.51 | 6.79 | 4.24 |  |  |

Dataset Preview.
We conclude the statistics of the manipulated local topology-imbalanced datasets (training) for node classification in Table [B.3](#A2.T3). To guarantee a fair evaluation, we ensure the number of nodes for each class is equal (class-balanced). It can be observed that as the imbalance degree increases from low to high, the imbalance ratio also increases from small to large.

#### B.5 Manipulated Class-Imbalanced Datasets for Graph Classification

Dataset Settings.
We conduct the graph classification task on seven manipulated class-imbalanced graph datasets, which are split into training, validation, and test sets with a ratio of 1:1:8.
Datasets can be divided into two categories: binary classification and multi-class classification. Consequently, our manipulations also involve two different types of processing methods.
For ❶ binary classification, we randomly sample 10%/10% graphs for training and validation, and the rest are for testing to ensure the sufficiency of the minority class instances in both training and validation set given the skewed imitative data distribution.
According to Eq. ([B.1](#A2.E1)), the imbalance ratio for the graph-level class-imbalance problem is set to the ratio between the number of graphs in the majority and the number of graphs in the minority class. To construct graph datasets with different imbalance ratios, we select the class with a larger number of graphs as the majority class, and the remaining class as the minority class. We then create training datasets with different imbalance ratios by adjusting the training sample ratios to 9:1 ($\rho=$ 9.0), 7:3 ($\rho=$ 2.3), and 5:5 ($\rho=$ 1.0, class-balanced), while ensuring that the number of training samples constitutes 10% of the total. In the validation set, an equal number of samples are allocated for each class for fairness. All remaining samples are then assigned to the test set.
For ❷ multi-class classification, situations are similar to manipulations defined in Section [B.2](#A2.SS2). We hypothesize that the number of graphs in each class within the training dataset multiplies exponentially. Given the total number of graphs in the training dataset and $\rho$, the number of graphs allocated for training in each class can be determined with certainty. Any graphs not allocated for training or validation are assigned to the test set.
For a thorough performance evaluation, we consider three scenarios within IGL-Bench: a class-balanced scenario ($\rho=$ 1), a class-imbalanced scenario ($\rho=$ 20), and an extreme class-imbalanced scenario ($\rho=$ 100).

**Table B.4: Statistics of the manipulated class-imbalanced datasets for graph classification. The imbalance ratio for the graph-level class-imbalance problem is set to the ratio between the number of graphs in the majority and the number of graphs in the minority class. The number of graphs for each class is equal in the validation set for fair evaluation.**
| Dataset | Task | Level | $\#$Graphs (val.)<br>per Class | $\#$Graphs<br>(Majority Class) | $\#$Graphs<br>(Minority Class) | Imbalance<br>Ratio $\bm{\rho}$ |
| --- | --- | --- | --- | --- | --- | --- |
| PTC-MR [] | Binary | Balanced | 17 | 17 | 17 | 1.0 (5:5) |
| Low | 23 | 11 | 2.3 (7:3) |  |  |  |
| High | 30 | 4 | 9.0 (9:1) |  |  |  |
| FRANKENSTEIN [] | Binary | Balanced | 216 | 216 | 216 | 1.0 (5:5) |
| Low | 302 | 130 | 2.3 (7:3) |  |  |  |
| High | 388 | 44 | 9.0 (9:1) |  |  |  |
| PROTEINS [] | Binary | Balanced | 55 | 55 | 55 | 1.0 (5:5) |
| Low | 77 | 33 | 2.3 (7:3) |  |  |  |
| High | 99 | 11 | 9.0 (9:1) |  |  |  |
| D&D [] | Binary | Balanced | 58 | 58 | 58 | 1.0 (5:5) |
| Low | 80 | 36 | 2.3 (7:3) |  |  |  |
| High | 104 | 12 | 9.0 (9:1) |  |  |  |
| IMDB-B [] | Binary | Balanced | 50 | 50 | 50 | 1.0 (5:5) |
| Low | 70 | 30 | 2.3 (7:3) |  |  |  |
| High | 90 | 10 | 9.0 (9:1) |  |  |  |
| REDDIT-B [] | Binary | Balanced | 100 | 100 | 100 | 1.0 (5:5) |
| Low | 140 | 60 | 2.3 (7:3) |  |  |  |
| High | 180 | 20 | 9.0 (9:1) |  |  |  |
| COLLAB [] | Multi-<br>Class | Balanced | 167 | 167 | 167 | 1 |
| Low | 380 | 19 | 20 |  |  |  |
| High | 400 | 4 | 100 |  |  |  |

Dataset Preview.
We conclude the statistics of the manipulated class-imbalanced datasets for graph classification in Table [B.4](#A2.T4). It can be observed that the constructed datasets can not only evaluate the ideal class-balanced ($\rho=$ 1) scenario but also comprehensively assess the performance of IGL algorithms under the general class-imbalanced and extremely class-imbalanced conditions.

#### B.6 Manipulated Topology-Imbalanced Datasets for Graph Classification

Dataset Settings.
We conduct the graph classification task on seven manipulated topology-imbalanced graph datasets. These datasets are divided into training, validation, and test sets with a ratio of 1:1:8. To ensure fairness, we maintain an equal number of graphs per class within each set, achieving a class-balanced scenario.
Eq. ([B.6](#A2.E6)) defines the imbalance ratio to be the ratio of the average graph size in the head graph set to the average graph size in the tail graph set. Specifically, the head graph set consists of the top 20% of graphs in terms of size (measured by the number of nodes each graph contains), while the remaining 80% comprise the tail graph set [].
Typically, larger graphs are more expressive due to their complex structures and richer information content. This expressiveness often translates to improved performance in graph classification tasks compared to smaller graphs. However, this advantage can also introduce biases in applications such as molecular or protein prediction, where larger graphs might inherently contain more predictive features, overshadowing the smaller graphs.
To comprehensively evaluate the performance of graph-level topology-imbalance IGL algorithms, we create training datasets with varying degrees of imbalance. The degree of imbalance is manipulated by altering the proportion of graphs selected from the head and tail sets. We perform the graph selection process multiple times, each time computing the resulting imbalance ratios. From these computations, we identify three distinct sets of splits that exhibit significant variations in imbalance levels. These sets are categorized and labeled as Low, Mid, and High to reflect their respective levels of local topology imbalance.
By systematically varying the imbalance levels, we aim to simulate diverse real-world scenarios. This approach allows us to rigorously test the robustness and adaptability of IGL algorithms under different degrees of topology imbalance. Ultimately, this comprehensive evaluation provides a deeper understanding of the performance of IGL algorithms across datasets with varying characteristics, highlighting their strengths and potential areas for improvement in handling topology-imbalanced graph data.

**Table B.5: Statistics of the manipulated topology-imbalanced datasets (training) for graph classification. The number of nodes for each class is equal (class-balanced), and the imbalance ratio $\rho$ is the ratio between the average size of the head graphs and the average size of the tail graphs.**
| Dataset | Level | $\#$Graphs<br>per Class | $\#$Head Graphs<br>per Class | $\#$Tail Graphs<br>per Class | Avg. $\#$Size<br>(Head Graphs) | Avg. $\#$Size<br>(Tail Graphs) | Imbalance<br>Ratio $\bm{\rho}$ |
| --- | --- | --- | --- | --- | --- | --- | --- |
| PTC-MR [] | Low | 17 | 2 | 15 | 29.50 | 18.40 | 1.60 |
| Mid | 34.25 | 11.80 | 2.90 |  |  |  |  |
| High | 56.00 | 11.37 | 4.93 |  |  |  |  |
| FRANKENSTEIN [] | Low | 217 | 22 | 195 | 33.09 | 21.19 | 1.56 |
| Mid | 32.43 | 13.78 | 2.35 |  |  |  |  |
| High | 77.55 | 13.78 | 5.63 |  |  |  |  |
| PROTEINS [] | Low | 56 | 6 | 50 | 93.50 | 45.81 | 2.04 |
| Mid | 90.25 | 22.26 | 4.05 |  |  |  |  |
| High | 276.00 | 22.76 | 12.13 |  |  |  |  |
| D&D [] | Low | 59 | 6 | 53 | 548.00 | 350.58 | 1.56 |
| Mid | 524.83 | 207.70 | 2.53 |  |  |  |  |
| High | 1765.00 | 198.11 | 8.91 |  |  |  |  |
| IMDB-B [] | Low | 50 | 5 | 45 | 37.50 | 22.92 | 1.64 |
| Mid | 34.30 | 16.29 | 2.11 |  |  |  |  |
| High | 70.30 | 15.81 | 4.45 |  |  |  |  |
| REDDIT-B [] | Low | 100 | 10 | 90 | 1180.75 | 423.23 | 2.79 |
| Mid | 1097.75 | 223.04 | 4.92 |  |  |  |  |
| High | 2442.70 | 222.73 | 10.97 |  |  |  |  |
| COLLAB [] | Low | 167 | 17 | 150 | 141.41 | 80.14 | 1.76 |
| Mid | 147.22 | 50.04 | 2.94 |  |  |  |  |
| High | 309.41 | 50.77 | 6.09 |  |  |  |  |

Dataset Preview.
We conclude the statistics of the manipulated class-imbalanced datasets for graph classification in Table [B.4](#A2.T4). To guarantee a fair evaluation, we ensure the number of graphs for each class is equal (class-balanced). We also observe that the imbalance ratio corresponds to Low, Mid, and High roughly doubles, which can better simulate the various degrees of the imbalanced distribution of graph sizes.

### Appendix C Details of the Experimental Settings

#### C.1 General Experimental Configurations

The number of training epochs for optimizing all IGL algorithms is set to 1000. We adopt the early stopping strategy, i.e., stop training if the performance on the validation set does not improve for 50 epochs. All parameters are randomly initiated. We adopt the Adam optimizer [] with an appropriate learning rate and weight decay for the best performance on the validation split. We randomly run all the experiments ten times, and report the average results with standard deviations.

#### C.2 Evaluation Metrics

We briefly introduce and analyze the evaluation metrics employed to assess the performance of IGL algorithms. The metrics discussed include Accuracy (Acc.), Balanced Accuracy (bAcc.), Macro-F1, and AUC-ROC.

Accuracy [].
It reflects the ratio of correctly predicted instances to the total number of instances. It is formally defined as:

$$ $\text{Accuracy}=\frac{TP+TN}{TP+TN+FP+FN},$ (C.1) $$

where $TP$ denotes true positives, $TN$ denotes true negatives, $FP$ denotes false positives, and $FN$ denotes false negatives.
❶ Advantages: Accuracy is simple and ease of interpretation. Further, it provides an immediate, overall performance measure of the algorithm.
❷ Disadvantages: In the imbalanced datasets, Accuracy can be misleading as it tends to favor the majority class, and fails to account for the distribution of classes, underrepresenting the performance of minority classes.

Balanced Accuracy [].
Balanced Accuracy adjusts the conventional Accuracy to account for class imbalance. It is the average of recall obtained in each class. For multi-class classification, it is defined as:

$$ $\text{Balanced Accuracy}=\frac{1}{N}\sum_{i=1}^{N}\frac{TP_{i}}{TP_{i}+FN_{i}},$ (C.2) $$

where $N$ is the number of classes.
❶ Advantages: Accuracy accounts for class imbalance, providing a more equitable evaluation, and it reflects performance across all classes more accurately than standard accuracy.
❷ Disadvantages: May be sensitive to noise and outliers, particularly in minority classes. In addition, it is potentially less intuitive to interpret compared to simple accuracy.

Macro-F1 [].
The Macro-F1 score is the harmonic mean of precision and recall, calculated independently for each class and then averaged. It is expressed as:

$$ $\text{Macro-F1}=\frac{1}{N}\sum_{i=1}^{N}\frac{2\cdot\text{Precision}_{i}\cdot\text{Recall}_{i}}{\text{Precision}_{i}+\text{Recall}_{i}},$ (C.3) $$

where $\text{Precision}_{i}=\frac{TP_{i}}{TP_{i}+FP_{i}}$ and $\text{Recall}_{i}=\frac{TP_{i}}{TP_{i}+FN_{i}}$.
❶ Advantages: Macro-F1 emphasizes both precision and recall, ensuring consideration of both false positives and false negatives. Moreover, it provides a balanced view of the classification performance across all classes.
❷ Disadvantages: It can be disproportionately affected by very small classes and does not account for the prevalence of different classes.

AUC-ROC [].
AUC-ROC (Area Under the Receiver Operating Characteristic Curve) measures the area under the ROC curve, which plots the true positive rate (recall) against the false positive rate (fall-out) at various threshold settings. For binary classification, it is defined as:

$$ $\text{AUC-ROC}=\int_{0}^{1}\text{ROC}(t)\,\mathrm{d}t.$ (C.4) $$

For multi-class problems, an average of the AUC-ROC scores for each class against the rest can be employed.
❶ Advantages: AUC-ROC evaluates the algorithm’s performance across all possible classification thresholds.
❷ Disadvantages: It is computationally intensive, particularly for large datasets. Further, it does not provide a clear threshold for decision-making, focusing instead on overall ranking performance.

Analysis.
When evaluating node-level and graph-level tasks under class-imbalance and topology-imbalance conditions, selecting the appropriate evaluation metric is crucial.
❶ Accuracy is often unsuitable for imbalanced scenarios due to its tendency to favor the majority class, potentially providing a false sense of model performance when minority classes are present.
❷ Balanced Accuracy and Macro-F1 are more appropriate for imbalanced datasets as they offer a more equitable assessment of performance across classes. Macro-F1, in particular, is informative in tasks where both precision and recall are critical.
❸ AUC-ROC is advantageous in ranking-based scenarios and for evaluating models across different thresholds. Its robustness to class imbalance is beneficial, though its interpretation can be less straightforward in multi-class problems.

In summary, while no single metric is universally optimal, a combination of these metrics can provide a comprehensive evaluation of imbalanced graph learning algorithms. Accuracy offers a general overview, while Balanced Accuracy and Macro-F1 provide insights into class-specific performance. AUC-ROC, on the other hand, offers a threshold-independent evaluation, particularly useful in highly imbalanced scenarios.

#### C.3 Hyperparameter

We meticulously optimize hyperparameters to guarantee a rigorous and unbiased assessment of the integrated IGL methods. In cases where the original paper or source code for a specific algorithm lacks guidance on hyperparameter selection, we perform the hyperparameter tuning through Bayesian search on the Weights & Biases (wandb) platform(^4^44[https://wandb.ai/](https://wandb.ai/)). The hyperparameter search space for all IGL algorithms is detailed in Table [C.1](#A3.T1) (for node-level class-imbalanced IGL algorithms), Table [C.2](#A3.T2) (for node-level topology-imbalanced IGL algorithms), and Table [C.3](#A3.T3) (for graph-level class-imbalanced and topology-imbalanced IGL algorithms). For interpretations of these hyperparameters, please consult the respective papers. More detailed and comprehensive hyperparameter configurations for all algorithms are accessible within our publicly released GitHub package.

**Table C.1: Hyperparameter search space for node-level class-imbalanced IGL algorithms.**
| Algorithm | Hyperparameter | Search Space |
| --- | --- | --- |
| General Settings | dropout | 0.2, 0.3, 0.4, 0.5, 0.6 |
| weight decay | 0, 5e–6, 5e–5, 5e–4, 5e–3 |  |
| number of max training epochs | 500, 1000, 2000 |  |
| learning rate | 0.005, 0.0075, 0.01, 0.015 |  |
| GCN [] | number of layers | 1, 2, 3 |
| hidden size | 32, 64, 128 |  |
| DRGCN [] | $\alpha$ for loss trade-off | 0.5, 0.6, 0.7, 0.8, 0.9 |
| DPGNN [] | $\lambda_{\text{1}}$ for $\mathcal{L}_{\text{ssl}_{\text{p}}}$ | 1, 10 |
| $\lambda_{\text{2}}$ for $\mathcal{L}_{\text{ssl}_{\text{s}}}$ | 1, 10 |  |
| threshold $\eta$ for the hard pseudo label | 0, 1, 2, 3, 4, 5, 6 |  |
| ImGAGN [] | $\lambda_{\text{1}}$ for minority nodes ratio | 0.1, 0.2, 0.3, 0.4, 0.5, 0.6 |
| $\lambda_{\text{2}}$ for discriminator training steps | 20, 30, 40, 50, 60 |  |
| GraphSMOTE [] | $\lambda$ for $\mathcal{L}_{edge}$ | 1e–6, 2e–6, 4e–6 |
| GraphENS [] | number of warming up epochs | 1, 5 |
| $k$ for feature masking | 1, 5, 10 |  |
| $\tau$ for temperature | 1, 2 |  |
| LTE4G [] | $\alpha$ for the focal loss | 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 |
| $\gamma$ for curve shape controlling | 0, 1, 2 |  |
| TAM [] | $\phi$ for the class–wise temperature | 0.8, 1.2 |
| $\alpha$ for the ACM term of node $v$ | 0.25, 0.5, 1.5, 2.5 |  |
| $\beta$ for the ADM term of node $v$ | 0.125, 0.25, 0.5 |  |
| the base model | GraphENS [], ReNode [] |  |
| GraphSHA [] | sampled $\beta$-distribution | $\beta$(1,100), $\beta$(1,10) |

**Table C.2: Hyperparameter search space for node-level topology-imbalanced IGL algorithms.**
| Algorithm | Hyperparameter | Search Space |
| --- | --- | --- |
| General Settings | dropout | 0.2, 0.3, 0.4, 0.5, 0.6 |
| weight decay | 0, 5e–6, 5e–5, 5e–4, 5e–3 |  |
| number of max training epochs | 500, 1000, 2000 |  |
| learning rate | 0.005, 0.0075, 0.01, 0.015, |  |
| GCN [] | number of layers | 1, 2, 3 |
| hidden size | 32, 64, 128 |  |
| Tail-GNN [] | $\mu$ for $\mathcal{L}_{m}$ | 0.01, 0.001 |
| $\eta$ for $\mathcal{L}_{d}$ | 0.1, 1.0 |  |
| Cold Brew [] | $\alpha$ for mixing coefficient | 0.01, 0.1, 0.5, 0.9, 0.99 |
| number of propagations | 10, 20, 50, 100, 200 |  |
| LTE4G [] | $\alpha$ for the focal loss | 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 |
| $\gamma$ for curve shape controlling | 0, 1, 2 |  |
| RawlsGCN [] | $\alpha$ for probability scalar | 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9 |
| GraphPatcher [] | batch size | 4, 8, 16, 64 |
| number of accumulation steps | 16, 32, 64 |  |
| number of patching steps | 3, 4, 5 |  |
| augmentation length | 0.1, 0.2, 0.3 |  |
| ReNode [] | PageRank teleport probability | 0.05, 0.1, 0.15, 0.2 |
| lower bound of reweighting | 0.25, 0.5, 0.75 |  |
| upper bound of reweighting | 1.25, 1.5, 1.75 |  |
| TAM [] | $\phi$ for the class–wise temperature | 0.8, 1.2 |
| $\alpha$ for the ACM term of node v | 0.25, 0.5, 1.5, 2.5 |  |
| $\beta$ for the ADM term of node v | 0.125, 0.25, 0.5 |  |
| PASTEL [] | $\lambda_{\text{1}}$ for structure mixing | 0.7, 0.8, 0.9 |
| $\lambda_{\text{2}}$ for structure mixing | 0.7, 0.8, 0.9 |  |

**Table C.3: Hyperparameter search space for both the graph-level class-imbalanced and topology-imbalanced IGL algorithms.**
| Algorithm | Hyperparameter | Search Space |
| --- | --- | --- |
| General Settings | dropout | 0.2, 0.3, 0.4, 0.5, 0.6 |
| weight decay | 0, 5e–6, 5e–5, 5e–4, 5e–3 |  |
| number of max training epochs | 500, 1000, 2000 |  |
| learning rate | 0.001,0.005,0.01,0.0125,0.05 |  |
| GCN [], GIN [] | number of layers | 2, 3, 4 |
| hidden size | 32, 64, 128 |  |
| G^2GNN [] | $k$ for the number of neighboring graphs | 1, 2, 3 |
| drop edge ratio | 5e–5,1e–4,5e–4,1e–3,5e–5 |  |
| mask node ratio | 5e–5,1e–4,5e–4,1e–3,5e–5 |  |
| TopoImb [] | $\alpha$ for $\mathcal{L}_{RE}$ | 0.2, 0.3, 0.4, 0.5, 0.6 |
| ImGKB [] | $\beta$ for compression coefficient | 0.3, 0.4, 0.5, 0.6 |
| $k$ for the number of neighboring graphs | 2, 4, 6, 8, 10 |  |
| SOLT-GNN [] | $\alpha$ for loss trade-off | 0.1, 0.15, 0.3 |
| $\mu_{\text{1}}$ for $\mathcal{L}_{\text{rel}}^{\text{node}}$ | 0, 0.5, 1, 1.5, 2 |  |
| $\mu_{\text{2}}$ for $\mathcal{L}_{\text{rel}}^{\text{subg}}$ | 0, 0.5, 1, 1.5, 2 |  |

#### C.4 Computation Resouces

We conduct the experiments with the following resources and configurations:

- •
Operating System: Ubuntu 20.04 LTS.
- •
CPU: Intel(R) Xeon(R) Platinum 8358 CPU@2.60GHz with 1TB DDR4 of Memory.
- •
GPU: NVIDIA Tesla A100 SMX4 with 40GB of Memory.
- •
Software: CUDA 10.1, Python 3.8.12, PyTorch [] 1.9.1, PyTorch Geometric [] 2.0.1.

### Appendix D Additional Experimental Results

#### D.1 Additional Results for Algorithm Effectiveness (RQ1)

##### D.1.1 Performance of Node-Level Class-Imbalanced Algorithms

**Table D.1: Accuracy score (% ± standard deviation) of node classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 80.41<br>±0.78 | 66.39<br>±0.86 | 82.88<br>±0.15 | 79.29<br>±0.66 | 88.30<br>±0.56 | 45.92<br>±0.48 | 26.76<br>±1.89 | 21.46<br>±0.87 | 23.07<br>±0.38 |
| DRGCN [] | 77.78<br>±1.22 | 66.99<br>±1.70 | 81.37<br>±2.96 | 63.71<br>±26.04 | 85.67<br>±0.93 | — | 33.81<br>±1.64 | 24.90<br>±0.48 | 24.19<br>±1.55 |
| DPGNN [] | 74.20<br>±2.47 | 62.07<br>±3.03 | 80.96<br>±3.09 | 66.15<br>±11.96 | 87.58<br>±2.77 | — | 32.06<br>±2.41 | 25.00<br>±1.32 | 22.49<br>±2.80 |
| ImGAGN [] | 80.58<br>±0.65 | 66.27<br>±0.60 | 82.78<br>±0.11 | 76.67<br>±1.15 | 86.62<br>±0.37 | — | 29.19<br>±2.26 | 21.61<br>±0.84 | 22.55<br>±0.94 |
| GraphSMOTE [] | 78.92<br>±0.48 | 65.50<br>±0.42 | 81.85<br>±0.19 | 79.46<br>±0.60 | 86.89<br>±0.66 | — | 25.05<br>±2.01 | 21.32<br>±0.22 | 25.96<br>±0.31 |
| GraphENS [] | 80.41<br>±0.78 | 66.42<br>±0.86 | 82.87<br>±0.15 | 78.71<br>±0.98 | 88.63<br>±1.44 | 46.68<br>±0.68 | 26.76<br>±1.89 | 21.46<br>±0.87 | 23.07<br>±0.38 |
| GraphMixup [] | 79.30<br>±0.64 | 69.95<br>±1.09 | 83.85<br>±0.11 | 82.16<br>±1.18 | 90.56<br>±0.35 | 43.88<br>±1.02 | 35.05<br>±0.34 | 24.59<br>±0.32 | 24.29<br>±1.16 |
| LTE4G [] | 80.48<br>±1.12 | 67.77<br>±2.25 | 84.27<br>±0.30 | 74.23<br>±4.72 | 88.48<br>±3.83 | — | 35.71<br>±0.53 | 24.62<br>±0.47 | 24.88<br>±1.11 |
| TAM [] | 81.33<br>±0.62 | 66.26<br>±0.52 | 74.56<br>±0.78 | 78.76<br>±0.78 | 88.49<br>±1.57 | 46.66<br>±0.57 | 28.56<br>±1.24 | 21.51<br>±0.94 | 23.54<br>±0.50 |
| TOPOAUC [] | 83.69<br>±0.32 | 73.41<br>±0.46 | — | 69.79<br>±3.93 | 82.85<br>±2.33 | — | 37.14<br>±0.95 | 25.24<br>±0.46 | 26.25<br>±1.22 |
| GraphSHA [] | 80.41<br>±0.78 | 66.40<br>±0.85 | 82.87<br>±0.14 | 78.88<br>±0.88 | 88.61<br>±4.99 | 47.32<br>±0.39 | 26.76<br>±1.89 | 21.46<br>±0.87 | 23.07<br>±0.38 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 76.36<br>±0.13 | 52.96<br>±0.55 | 60.57<br>±0.19 | 75.06<br>±0.50 | 69.80<br>±6.15 | 59.83<br>±0.23 | 26.35<br>±0.24 | 17.16<br>±0.17 | 24.06<br>±0.14 |
| DRGCN [] | 71.35<br>±0.77 | 55.22<br>±1.82 | 62.59<br>±4.62 | 67.71<br>±3.10 | 85.67<br>±5.30 | — | 26.40<br>±0.35 | 17.11<br>±0.81 | 25.03<br>±0.23 |
| DPGNN [] | 72.91<br>±3.95 | 56.78<br>±2.23 | 81.87<br>±2.80 | 68.69<br>±8.62 | 81.66<br>±9.19 | — | 30.58<br>±1.48 | 25.35<br>±1.48 | 21.66<br>±1.68 |
| ImGAGN [] | 73.48<br>±3.07 | 55.29<br>±3.00 | 72.16<br>±1.51 | 74.92<br>±1.87 | 83.10<br>±3.42 | — | 24.38<br>±2.86 | 18.75<br>±1.80 | 24.54<br>±3.38 |
| GraphSMOTE [] | 77.21<br>±0.27 | 53.55<br>±0.95 | 60.11<br>±0.27 | 76.04<br>±1.52 | 89.07<br>±1.12 | — | 27.23<br>±0.21 | 16.79<br>±0.14 | 25.08<br>±0.31 |
| GraphENS [] | 79.34<br>±0.49 | 61.98<br>±0.76 | 80.84<br>±0.17 | 80.72<br>±0.68 | 90.38<br>±0.37 | 53.23<br>±0.52 | 24.34<br>±1.62 | 20.05<br>±1.61 | 25.03<br>±0.38 |
| GraphMixup [] | 79.88<br>±0.43 | 62.66<br>±0.70 | 75.94<br>±0.09 | 86.15<br>±0.47 | 89.69<br>±0.31 | 56.08<br>±0.31 | 30.95<br>±0.40 | 17.83<br>±0.32 | 24.75<br>±0.37 |
| LTE4G [] | 80.53<br>±0.65 | 64.48<br>±1.56 | 83.02<br>±0.33 | 79.35<br>±1.39 | 87.94<br>±1.82 | — | 31.91<br>±0.34 | 19.37<br>±0.41 | 25.43<br>±0.26 |
| TAM [] | 80.69<br>±0.27 | 64.16<br>±0.24 | 81.47<br>±0.15 | 81.30<br>±0.53 | 90.35<br>±0.42 | 53.49<br>±0.54 | 23.27<br>±1.38 | 21.17<br>±0.95 | 24.53<br>±0.33 |
| TOPOAUC [] | 83.34<br>±0.31 | 69.03<br>±1.33 | — | 70.85<br>±4.55 | 83.72<br>±2.23 | — | 33.60<br>±1.51 | 21.38<br>±1.03 | 25.16<br>±0.46 |
| GraphSHA [] | 80.03<br>±0.46 | 60.51<br>±0.61 | 77.94<br>±0.36 | 82.71<br>±0.40 | 91.55<br>±0.32 | 60.30<br>±0.13 | 23.73<br>±1.97 | 20.05<br>±1.61 | 23.59<br>±1.01 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 62.20<br>±3.57 | 42.48<br>±0.24 | 47.31<br>±0.72 | 58.04<br>±0.98 | 46.54<br>±0.33 | 60.35<br>±0.24 | 25.68<br>±0.12 | 15.17<br>±0.10 | 21.70<br>±0.22 |
| DRGCN [] | 61.99<br>±2.46 | 45.69<br>±2.79 | 49.80<br>±4.33 | 66.02<br>±1.48 | 73.58<br>±5.44 | — | 25.79<br>±0.44 | 15.32<br>±0.43 | 23.03<br>±0.59 |
| DPGNN [] | 67.98<br>±3.35 | 51.10<br>±3.06 | 76.29<br>±3.38 | 70.04<br>±8.56 | 87.70<br>±0.34 | — | 28.82<br>±1.83 | 23.91<br>±1.90 | 22.37<br>±0.74 |
| ImGAGN [] | 66.16<br>±3.54 | 53.60<br>±3.32 | 64.03<br>±0.62 | 66.89<br>±4.29 | 74.92<br>±5.89 | — | 23.72<br>±2.85 | 17.30<br>±3.16 | 24.10<br>±1.26 |
| GraphSMOTE [] | 69.81<br>±0.46 | 45.72<br>±0.80 | 47.97<br>±0.76 | 56.55<br>±1.29 | 44.97<br>±0.22 | — | 25.60<br>±0.12 | 15.41<br>±0.10 | 21.76<br>±0.21 |
| GraphENS [] | 77.68<br>±0.58 | 62.85<br>±0.72 | 76.69<br>±0.31 | 80.99<br>±0.76 | 90.31<br>±0.33 | 54.13<br>±0.49 | 26.26<br>±2.42 | 20.65<br>±2.30 | 20.67<br>±2.47 |
| GraphMixup [] | 70.01<br>±0.50 | 49.63<br>±0.28 | 63.47<br>±0.08 | 79.34<br>±0.42 | 73.02<br>±4.01 | 57.40<br>±0.35 | 26.41<br>±0.08 | 15.75<br>±0.16 | 23.39<br>±0.37 |
| LTE4G [] | 73.70<br>±0.99 | 57.14<br>±1.28 | 70.58<br>±15.32 | 79.59<br>±0.94 | 89.53<br>±0.74 | — | 27.88<br>±0.60 | 16.18<br>±0.34 | 24.76<br>±0.42 |
| TAM [] | 79.36<br>±0.56 | 64.30<br>±0.46 | 80.53<br>±0.18 | 85.77<br>±0.41 | 90.28<br>±0.32 | 54.25<br>±0.70 | 23.47<br>±1.73 | 23.48<br>±1.24 | 21.92<br>±0.18 |
| TOPOAUC [] | 76.97<br>±0.99 | 67.31<br>±2.02 | — | — | 82.74<br>±3.10 | — | 30.66<br>±0.48 | 17.67<br>±1.29 | 25.35<br>±1.04 |
| GraphSHA [] | 78.66<br>±0.46 | 57.63<br>±0.82 | 70.68<br>±2.42 | 80.79<br>±0.65 | 91.27<br>±0.25 | 60.17<br>±0.17 | 24.14<br>±1.30 | 20.78<br>±2.19 | 20.82<br>±2.65 |

**Table D.2: Balanced Accuracy score (% ± standard deviation) of node classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 79.98<br>±0.63 | 62.62<br>±0.60 | 83.13<br>±0.06 | 87.20<br>±0.26 | 89.70<br>±0.26 | 45.93<br>±0.56 | 28.04<br>±1.60 | 21.47<br>±0.87 | 22.65<br>±0.33 |
| DRGCN [] | 77.20<br>±0.78 | 63.05<br>±0.82 | 82.22<br>±2.10 | 73.23<br>±23.82 | 88.22<br>±0.71 | — | 34.36<br>±1.20 | 24.89<br>±0.48 | 23.33<br>±0.34 |
| DPGNN [] | 75.79<br>±2.44 | 58.96<br>±3.21 | 81.42<br>±3.08 | 74.75<br>±10.80 | 88.15<br>±2.56 | — | 33.07<br>±1.92 | 24.99<br>±1.32 | 22.13<br>±1.79 |
| ImGAGN [] | 80.20<br>±0.41 | 62.55<br>±0.38 | 83.11<br>±0.08 | 84.20<br>±0.36 | 88.80<br>±0.27 | — | 29.65<br>±1.78 | 21.61<br>±0.84 | 22.57<br>±0.60 |
| GraphSMOTE [] | 78.04<br>±0.44 | 62.16<br>±0.41 | 82.11<br>±0.14 | 80.07<br>±0.54 | 88.89<br>±0.26 | — | 26.83<br>±2.01 | 21.34<br>±0.22 | 22.04<br>±0.32 |
| GraphENS [] | 79.98<br>±0.63 | 62.65<br>±0.60 | 83.12<br>±0.08 | 86.26<br>±0.51 | 89.85<br>±0.64 | 45.98<br>±0.49 | 28.04<br>±1.60 | 21.47<br>±0.87 | 22.65<br>±0.33 |
| GraphMixup [] | 82.41<br>±0.24 | 67.48<br>±1.01 | 84.72<br>±0.07 | 88.96<br>±0.35 | 91.90<br>±0.24 | 43.97<br>±0.49 | 35.60<br>±0.33 | 24.59<br>±0.32 | 23.50<br>±0.52 |
| LTE4G [] | 81.97<br>±1.02 | 65.10<br>±2.07 | 85.21<br>±0.13 | 83.59<br>±2.06 | 88.83<br>±3.48 | — | 35.13<br>±0.53 | 24.61<br>±0.47 | 24.88<br>±0.73 |
| TAM [] | 80.98<br>±0.33 | 62.99<br>±0.26 | 77.26<br>±0.62 | 86.06<br>±0.52 | 89.77<br>±0.74 | 46.05<br>±0.77 | 28.82<br>±0.76 | 21.51<br>±0.94 | 22.93<br>±0.45 |
| TOPOAUC [] | 84.86<br>±0.18 | 69.90<br>±0.42 | — | 77.23<br>±1.73 | 85.24<br>±1.32 | — | 37.92<br>±0.68 | 25.23<br>±0.46 | 25.68<br>±0.41 |
| GraphSHA [] | 79.98<br>±0.63 | 62.63<br>±0.59 | 83.13<br>±0.07 | 86.11<br>±0.44 | 89.81<br>±0.63 | 46.40<br>±0.83 | 28.04<br>±1.60 | 21.47<br>±0.87 | 22.65<br>±0.33 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 69.17<br>±0.26 | 47.61<br>±0.48 | 52.40<br>±0.15 | 40.86<br>±0.77 | 49.87<br>±7.16 | 37.36<br>±0.31 | 26.75<br>±0.22 | 20.83<br>±0.17 | 20.62<br>±0.10 |
| DRGCN [] | 63.04<br>±0.99 | 49.86<br>±1.68 | 56.40<br>±3.91 | 43.92<br>±2.58 | 74.82<br>±9.35 | — | 26.79<br>±0.35 | 19.98<br>±0.45 | 22.10<br>±0.21 |
| DPGNN [] | 67.64<br>±3.32 | 51.34<br>±2.01 | 81.94<br>±2.85 | 76.17<br>±9.32 | 82.20<br>±9.18 | — | 30.72<br>±1.49 | 26.52<br>±1.59 | 21.47<br>±0.80 |
| ImGAGN [] | 67.78<br>±3.46 | 50.40<br>±3.03 | 67.34<br>±1.14 | 73.92<br>±0.82 | 78.14<br>±2.13 | — | 24.50<br>±2.71 | 20.14<br>±0.74 | 23.83<br>±1.73 |
| GraphSMOTE [] | 70.54<br>±0.42 | 48.27<br>±0.91 | 52.04<br>±0.21 | 51.46<br>±4.33 | 80.21<br>±1.46 | — | 27.54<br>±0.20 | 20.63<br>±0.13 | 21.73<br>±0.31 |
| GraphENS [] | 78.54<br>±0.55 | 58.76<br>±0.95 | 79.47<br>±0.27 | 86.03<br>±0.25 | 90.26<br>±0.24 | 41.83<br>±0.79 | 24.80<br>±1.64 | 21.03<br>±1.00 | 25.64<br>±0.49 |
| GraphMixup [] | 72.63<br>±0.69 | 56.76<br>±0.68 | 72.40<br>±0.10 | 82.91<br>±0.65 | 81.21<br>±0.48 | 39.67<br>±0.36 | 31.21<br>±0.36 | 20.81<br>±0.25 | 21.68<br>±0.36 |
| LTE4G [] | 75.42<br>±1.26 | 58.52<br>±1.35 | 81.68<br>±0.22 | 72.29<br>±3.90 | 87.99<br>±1.34 | — | 32.00<br>±0.34 | 22.37<br>±0.34 | 23.11<br>±0.33 |
| TAM [] | 80.29<br>±0.37 | 60.88<br>±0.26 | 81.20<br>±0.18 | 86.19<br>±0.24 | 90.19<br>±0.21 | 41.94<br>±0.53 | 23.82<br>±1.46 | 21.11<br>±0.49 | 25.84<br>±0.30 |
| TOPOAUC [] | 79.98<br>±0.33 | 63.69<br>±0.93 | — | 77.02<br>±2.60 | 85.79<br>±1.62 | — | 33.87<br>±1.28 | 23.17<br>±0.80 | 24.24<br>±0.24 |
| GraphSHA [] | 77.11<br>±0.40 | 56.98<br>±0.74 | 75.18<br>±0.39 | 77.04<br>±0.64 | 88.83<br>±0.28 | 35.92<br>±0.48 | 24.17<br>±2.16 | 21.03<br>±1.00 | 22.54<br>±0.82 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 47.96<br>±5.26 | 38.66<br>±0.20 | 43.02<br>±0.55 | 22.83<br>±2.07 | 25.06<br>±0.36 | 30.20<br>±0.41 | 27.02<br>±0.12 | 20.62<br>±0.09 | 20.22<br>±0.12 |
| DRGCN [] | 49.11<br>±3.52 | 41.40<br>±2.34 | 44.87<br>±3.23 | 35.80<br>±1.98 | 54.85<br>±6.26 | — | 27.11<br>±0.44 | 20.57<br>±0.38 | 21.03<br>±0.36 |
| DPGNN [] | 58.09<br>±3.37 | 46.01<br>±2.71 | 74.95<br>±3.08 | 76.51<br>±7.76 | 85.55<br>±1.77 | — | 29.74<br>±2.13 | 25.88<br>±1.23 | 21.18<br>±0.92 |
| ImGAGN [] | 57.01<br>±4.30 | 48.70<br>±3.16 | 55.56<br>±0.44 | 60.84<br>±6.59 | 69.88<br>±3.24 | — | 24.76<br>±2.93 | 19.81<br>±0.63 | 22.21<br>±1.01 |
| GraphSMOTE [] | 58.91<br>±0.55 | 41.60<br>±0.74 | 43.52<br>±0.57 | 21.05<br>±0.88 | 23.91<br>±0.12 | — | 26.91<br>±0.13 | 20.67<br>±0.14 | 20.27<br>±0.12 |
| GraphENS [] | 76.25<br>±0.70 | 58.08<br>±0.59 | 73.62<br>±0.43 | 85.72<br>±0.42 | 90.19<br>±0.31 | 40.42<br>±0.59 | 27.12<br>±2.61 | 22.03<br>±1.49 | 20.99<br>±1.43 |
| GraphMixup [] | 56.43<br>±0.59 | 44.63<br>±0.22 | 57.86<br>±0.13 | 49.37<br>±0.63 | 54.60<br>±4.88 | 34.44<br>±0.19 | 27.93<br>±0.09 | 20.50<br>±0.15 | 21.25<br>±0.27 |
| LTE4G [] | 62.22<br>±1.22 | 51.16<br>±1.21 | 67.89<br>±10.50 | 72.49<br>±2.92 | 83.28<br>±1.91 | — | 29.69<br>±0.51 | 21.08<br>±0.29 | 22.79<br>±0.51 |
| TAM [] | 78.11<br>±0.39 | 59.10<br>±0.43 | 78.98<br>±0.27 | 85.77<br>±0.41 | 90.20<br>±0.24 | 40.61<br>±0.55 | 23.96<br>±1.94 | 22.74<br>±0.84 | 21.97<br>±0.15 |
| TOPOAUC [] | 71.10<br>±1.30 | 61.13<br>±2.02 | — | — | 85.13<br>±2.23 | — | 32.10<br>±0.42 | 21.22<br>±0.46 | 24.05<br>±0.61 |
| GraphSHA [] | 75.24<br>±0.54 | 53.92<br>±0.69 | 65.28<br>±0.56 | 72.59<br>±1.36 | 87.06<br>±0.58 | 28.12<br>±0.32 | 24.80<br>±1.36 | 22.05<br>±1.49 | 20.84<br>±1.34 |

**Table D.3: Macro-F1 score (% ± standard deviation) of node classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 78.26<br>±0.91 | 61.83<br>±0.78 | 82.03<br>±0.16 | 68.40<br>±0.49 | 85.03<br>±0.47 | 27.50<br>±0.17 | 23.99<br>±1.98 | 18.80<br>±1.62 | 21.91<br>±0.36 |
| DRGCN [] | 75.46<br>±0.97 | 62.65<br>±1.09 | 80.46<br>±3.08 | 55.55<br>±22.56 | 83.23<br>±0.69 | — | 32.85<br>±2.01 | 23.41<br>±0.95 | 22.30<br>±0.63 |
| DPGNN [] | 72.73<br>±2.46 | 58.77<br>±2.86 | 80.49<br>±2.78 | 55.27<br>±10.24 | 83.37<br>±2.87 | — | 30.06<br>±3.08 | 21.67<br>±1.65 | 17.38<br>±2.51 |
| ImGAGN [] | 78.60<br>±0.61 | 61.70<br>±0.54 | 81.96<br>±0.12 | 66.70<br>±1.20 | 83.79<br>±0.37 | — | 26.45<br>±2.53 | 18.76<br>±1.74 | 21.55<br>±0.86 |
| GraphSMOTE [] | 77.03<br>±0.42 | 61.20<br>±0.44 | 80.93<br>±0.18 | 65.39<br>±0.90 | 83.76<br>±0.53 | — | 22.93<br>±1.31 | 14.71<br>±1.38 | 21.13<br>±0.71 |
| GraphENS [] | 78.26<br>±0.91 | 61.86<br>±0.77 | 82.03<br>±0.16 | 68.39<br>±0.89 | 85.64<br>±1.22 | 27.92<br>±0.16 | 23.99<br>±1.98 | 18.80<br>±1.62 | 21.91<br>±0.35 |
| GraphMixup [] | 77.54<br>±0.73 | 66.34<br>±0.98 | 82.92<br>±0.10 | 70.81<br>±0.92 | 86.84<br>±0.40 | 26.14<br>±0.38 | 33.76<br>±0.38 | 23.78<br>±0.26 | 22.25<br>±0.97 |
| LTE4G [] | 78.45<br>±1.10 | 64.35<br>±2.04 | 83.19<br>±0.32 | 62.28<br>±3.47 | 84.09<br>±4.41 | — | 34.00<br>±0.67 | 23.45<br>±0.31 | 22.75<br>±1.17 |
| TAM [] | 79.34<br>±0.61 | 61.95<br>±0.33 | 74.23<br>±0.77 | 68.53<br>±0.72 | 85.48<br>±1.39 | 27.93<br>±0.22 | 25.40<br>±1.86 | 18.43<br>±2.12 | 22.10<br>±0.54 |
| TOPOAUC [] | 81.95<br>±0.36 | 69.28<br>±0.45 | — | 57.76<br>±1.85 | 79.31<br>±2.25 | — | 35.85<br>±0.79 | 23.70<br>±0.44 | 24.43<br>±0.69 |
| GraphSHA [] | 78.26<br>±0.91 | 61.84<br>±0.77 | 82.02<br>±0.15 | 68.61<br>±0.67 | 85.62<br>±1.21 | 28.20<br>±0.16 | 23.99<br>±1.98 | 18.80<br>±1.62 | 21.91<br>±0.36 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 71.15<br>±0.30 | 43.71<br>±0.54 | 45.71<br>±0.16 | 39.11<br>±0.43 | 48.99<br>±8.51 | 33.94<br>±0.26 | 16.67<br>±0.52 | 9.83<br>±0.49 | 12.18<br>±0.67 |
| DRGCN [] | 64.43<br>±1.52 | 47.50<br>±1.46 | 53.83<br>±4.78 | 41.55<br>±2.42 | 74.51<br>±8.46 | — | 17.22<br>±0.44 | 11.01<br>±0.88 | 16.43<br>±0.57 |
| DPGNN [] | 68.70<br>±3.61 | 50.06<br>±2.10 | 81.54<br>±2.42 | 66.97<br>±8.96 | 79.53<br>±8.70 | — | 26.03<br>±1.83 | 21.53<br>±2.14 | 18.48<br>±1.50 |
| ImGAGN [] | 68.69<br>±3.93 | 48.40<br>±3.58 | 67.80<br>±1.41 | 72.51<br>±1.28 | 75.49<br>±1.64 | — | 16.94<br>±2.14 | 13.91<br>±2.77 | 21.04<br>±3.16 |
| GraphSMOTE [] | 72.71<br>±0.31 | 45.21<br>±0.95 | 45.35<br>±0.21 | 49.30<br>±4.76 | 79.64<br>±0.98 | — | 18.72<br>±0.26 | 8.36<br>±0.36 | 16.26<br>±0.84 |
| GraphENS [] | 77.16<br>±0.50 | 57.80<br>±0.96 | 79.71<br>±0.24 | 77.89<br>±0.69 | 88.20<br>±0.28 | 30.16<br>±0.37 | 19.58<br>±0.99 | 16.73<br>±1.73 | 23.30<br>±0.38 |
| GraphMixup [] | 74.03<br>±0.62 | 55.31<br>±0.69 | 73.63<br>±0.11 | 81.54<br>±0.58 | 80.83<br>±0.63 | 32.38<br>±0.17 | 25.57<br>±0.76 | 13.17<br>±0.79 | 18.35<br>±0.54 |
| LTE4G [] | 76.46<br>±1.17 | 57.35<br>±1.49 | 82.12<br>±0.27 | 69.02<br>±3.78 | 85.23<br>±1.34 | — | 25.96<br>±0.35 | 15.13<br>±0.80 | 21.27<br>±0.48 |
| TAM [] | 78.83<br>±0.32 | 60.12<br>±0.31 | 80.75<br>±0.15 | 78.10<br>±0.65 | 88.16<br>±0.30 | 30.30<br>±0.29 | 19.99<br>±1.21 | 17.29<br>±0.94 | 24.01<br>±0.54 |
| TOPOAUC [] | 80.61<br>±0.30 | 62.95<br>±1.21 | — | 67.15<br>±5.38 | 81.69<br>±2.38 | — | 29.06<br>±2.35 | 18.77<br>±1.36 | 23.61<br>±0.24 |
| GraphSHA [] | 77.66<br>±0.46 | 55.76<br>±0.85 | 76.17<br>±0.37 | 75.43<br>±0.47 | 89.04<br>±0.27 | 32.09<br>±0.23 | 19.64<br>±1.26 | 16.73<br>±1.73 | 20.36<br>±0.97 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 43.97<br>±7.75 | 30.77<br>±0.21 | 34.08<br>±0.77 | 20.44<br>±1.45 | 16.99<br>±0.64 | 31.11<br>±0.50 | 14.79<br>±0.11 | 8.27<br>±0.17 | 9.01<br>±0.66 |
| DRGCN [] | 47.47<br>±4.00 | 34.83<br>±2.80 | 36.44<br>±4.29 | 33.60<br>±1.15 | 52.58<br>±6.68 | — | 15.02<br>±0.26 | 8.83<br>±1.09 | 12.38<br>±1.05 |
| DPGNN [] | 58.66<br>±3.44 | 41.53<br>±3.59 | 75.47<br>±3.04 | 68.30<br>±8.53 | 84.82<br>±1.94 | — | 23.96<br>±2.16 | 18.85<br>±2.36 | 19.62<br>±1.15 |
| ImGAGN [] | 55.03<br>±5.32 | 43.92<br>±4.61 | 50.74<br>±1.93 | 57.30<br>±5.51 | 67.27<br>±4.58 | — | 14.12<br>±2.75 | 10.62<br>±4.19 | 18.84<br>±2.87 |
| GraphSMOTE [] | 58.93<br>±0.54 | 35.40<br>±0.93 | 34.78<br>±0.80 | 17.90<br>±1.20 | 16.34<br>±0.04 | — | 15.13<br>±0.16 | 9.31<br>±0.29 | 9.05<br>±0.76 |
| GraphENS [] | 74.91<br>±0.66 | 56.58<br>±0.60 | 74.36<br>±0.40 | 78.75<br>±0.59 | 88.53<br>±0.25 | 30.89<br>±0.38 | 20.80<br>±0.64 | 17.96<br>±1.89 | 18.47<br>±2.45 |
| GraphMixup [] | 55.91<br>±0.61 | 38.36<br>±0.24 | 55.24<br>±0.21 | 46.92<br>±0.61 | 53.54<br>±5.72 | 33.18<br>±0.16 | 20.02<br>±0.11 | 10.07<br>±0.17 | 14.46<br>±0.78 |
| LTE4G [] | 62.11<br>±1.29 | 45.67<br>±1.91 | 66.79<br>±15.94 | 70.80<br>±2.70 | 83.24<br>±2.67 | — | 21.02<br>±1.06 | 10.61<br>±0.51 | 17.88<br>±0.67 |
| TAM [] | 77.07<br>±0.57 | 57.67<br>±0.46 | 79.34<br>±0.21 | 78.97<br>±0.29 | 88.44<br>±0.23 | 30.91<br>±0.45 | 20.37<br>±1.49 | 20.28<br>±1.48 | 21.33<br>±0.31 |
| TOPOAUC [] | 70.01<br>±0.95 | 58.92<br>±2.94 | — | — | 80.80<br>±3.23 | — | 24.41<br>±1.51 | 13.62<br>±2.00 | 22.40<br>±0.40 |
| GraphSHA [] | 75.86<br>±0.58 | 51.99<br>±0.68 | 64.66<br>±1.02 | 72.46<br>±1.10 | 88.36<br>±0.43 | 27.92<br>±0.33 | 19.96<br>±1.82 | 17.87<br>±1.99 | 18.05<br>±2.33 |

**Table D.4: AUC-ROC score (% ± standard deviation) of node classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 96.08<br>±0.47 | 89.74<br>±0.11 | 94.55<br>±0.04 | 97.61<br>±0.04 | 98.73<br>±0.04 | 93.39<br>±0.10 | 63.48<br>±0.66 | 51.32<br>±0.95 | 53.22<br>±0.58 |
| DRGCN [] | 95.01<br>±0.30 | 89.32<br>±0.22 | 94.73<br>±0.41 | 93.43<br>±11.13 | 98.49<br>±0.12 | — | 64.93<br>±0.49 | 55.40<br>±0.32 | 54.28<br>±0.45 |
| DPGNN [] | 93.84<br>±0.91 | 86.15<br>±1.58 | 92.59<br>±2.58 | 95.06<br>±2.35 | 97.85<br>±0.63 | — | 63.30<br>±1.93 | 55.05<br>±1.31 | 52.51<br>±2.20 |
| ImGAGN [] | 96.49<br>±0.17 | 89.97<br>±0.13 | 94.52<br>±0.03 | 97.12<br>±0.13 | 98.53<br>±0.08 | — | 64.90<br>±0.86 | 51.28<br>±0.53 | 53.66<br>±1.05 |
| GraphSMOTE [] | 95.88<br>±0.35 | 89.48<br>±0.13 | 93.94<br>±0.06 | 97.18<br>±0.09 | 98.64<br>±0.04 | — | 60.33<br>±3.34 | 51.21<br>±0.33 | 53.70<br>±0.36 |
| GraphENS [] | 96.08<br>±0.47 | 89.74<br>±0.11 | 94.55<br>±0.04 | 97.67<br>±0.07 | 98.76<br>±0.11 | 93.33<br>±0.07 | 63.48<br>±0.66 | 51.32<br>±0.95 | 53.22<br>±0.58 |
| GraphMixup [] | 96.42<br>±0.25 | 89.83<br>±0.94 | 95.16<br>±0.04 | 97.96<br>±0.13 | 98.79<br>±0.03 | 92.64<br>±0.09 | 63.16<br>±0.65 | 54.01<br>±0.31 | 53.82<br>±0.76 |
| LTE4G [] | 96.54<br>±0.39 | 89.00<br>±0.67 | 95.61<br>±0.05 | 95.88<br>±3.08 | 98.17<br>±0.56 | — | 65.42<br>±0.49 | 55.22<br>±0.40 | 57.75<br>±0.64 |
| TAM [] | 96.85<br>±0.04 | 89.77<br>±0.08 | 92.62<br>±0.12 | 97.69<br>±0.06 | 98.71<br>±0.16 | 93.34<br>±0.06 | 60.11<br>±1.56 | 51.67<br>±0.78 | 51.84<br>±0.46 |
| TOPOAUC [] | 97.56<br>±0.04 | 91.89<br>±0.23 | — | 91.26<br>±2.37 | 94.11<br>±1.46 | — | 67.70<br>±0.88 | 55.43<br>±0.09 | 57.17<br>±0.53 |
| GraphSHA [] | 96.08<br>±0.47 | 89.74<br>±0.11 | 94.54<br>±0.04 | 97.69<br>±0.06 | 98.76<br>±0.11 | 93.50<br>±0.08 | 63.48<br>±0.66 | 51.32<br>±0.95 | 53.22<br>±0.58 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 95.04<br>±0.08 | 86.57<br>±0.19 | 92.23<br>±0.09 | 94.41<br>±0.53 | 94.35<br>±0.96 | 93.54<br>±0.09 | 57.70<br>±0.42 | 51.70<br>±0.08 | 52.05<br>±0.36 |
| DRGCN [] | 92.68<br>±0.30 | 84.92<br>±0.63 | 92.04<br>±0.35 | 93.84<br>±0.50 | 98.22<br>±0.49 | — | 56.19<br>±0.66 | 49.42<br>±0.68 | 55.20<br>±0.28 |
| DPGNN [] | 92.41<br>±1.08 | 81.04<br>±1.44 | 93.24<br>±1.77 | 95.03<br>±1.93 | 96.30<br>±2.20 | — | 60.45<br>±2.11 | 55.66<br>±1.56 | 51.20<br>±0.71 |
| ImGAGN [] | 92.89<br>±0.45 | 83.52<br>±0.51 | 90.53<br>±1.69 | 94.55<br>±1.38 | 95.25<br>±1.19 | — | 53.11<br>±2.76 | 49.98<br>±0.74 | 54.92<br>±1.99 |
| GraphSMOTE [] | 95.14<br>±0.16 | 86.59<br>±0.27 | 91.77<br>±0.09 | 96.51<br>±0.41 | 98.28<br>±0.31 | — | 56.92<br>±0.23 | 51.71<br>±0.06 | 53.79<br>±0.27 |
| GraphENS [] | 96.32<br>±0.13 | 87.46<br>±0.43 | 93.26<br>±0.11 | 97.70<br>±0.09 | 98.71<br>±0.05 | 93.04<br>±0.08 | 58.54<br>±2.61 | 52.33<br>±0.77 | 56.10<br>±0.13 |
| GraphMixup [] | 96.23<br>±0.13 | 85.86<br>±0.30 | 93.81<br>±0.05 | 98.24<br>±0.05 | 98.27<br>±0.09 | 92.75<br>±0.09 | 61.05<br>±0.37 | 53.78<br>±0.39 | 52.70<br>±0.12 |
| LTE4G [] | 95.67<br>±0.33 | 86.14<br>±0.99 | 94.90<br>±0.29 | 96.85<br>±0.25 | 98.69<br>±0.25 | — | 63.31<br>±0.60 | 53.83<br>±0.29 | 54.36<br>±0.44 |
| TAM [] | 96.74<br>±0.07 | 88.41<br>±0.19 | 93.71<br>±0.07 | 97.69<br>±0.10 | 98.71<br>±0.04 | 93.07<br>±0.07 | 58.71<br>±1.96 | 51.17<br>±1.18 | 55.72<br>±0.17 |
| TOPOAUC [] | 97.09<br>±0.16 | 88.62<br>±0.59 | — | 91.04<br>±1.72 | 93.96<br>±1.62 | — | 65.86<br>±0.82 | 53.47<br>±0.49 | 54.78<br>±0.25 |
| GraphSHA [] | 96.27<br>±0.05 | 87.36<br>±0.22 | 93.14<br>±0.10 | 97.78<br>±0.06 | 98.74<br>±0.06 | 93.39<br>±0.11 | 58.19<br>±2.52 | 52.33<br>±0.77 | 52.48<br>±1.05 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 91.55<br>±0.80 | 80.26<br>±0.32 | 79.13<br>±1.41 | 87.24<br>±1.56 | 76.98<br>±1.42 | 92.87<br>±0.12 | 57.86<br>±0.65 | 51.16<br>±0.06 | 50.79<br>±0.79 |
| DRGCN [] | 89.80<br>±0.54 | 79.58<br>±1.24 | 84.19<br>±2.66 | 92.09<br>±0.75 | 96.50<br>±0.63 | — | 55.79<br>±1.06 | 49.24<br>±0.39 | 54.87<br>±0.25 |
| DPGNN [] | 87.41<br>±2.09 | 78.59<br>±1.51 | 90.02<br>±2.99 | 95.34<br>±1.58 | 97.09<br>±0.57 | — | 59.14<br>±2.36 | 54.25<br>±1.11 | 50.35<br>±0.72 |
| ImGAGN [] | 88.38<br>±1.39 | 81.37<br>±0.69 | 87.52<br>±1.15 | 92.75<br>±1.38 | 94.82<br>±0.72 | — | 52.73<br>±2.84 | 49.44<br>±0.71 | 53.60<br>±1.51 |
| GraphSMOTE [] | 93.29<br>±0.14 | 82.56<br>±0.37 | 78.88<br>±1.27 | 89.52<br>±1.39 | 84.03<br>±1.44 | — | 56.82<br>±0.53 | 51.49<br>±0.11 | 52.51<br>±2.31 |
| GraphENS [] | 95.55<br>±0.13 | 85.91<br>±0.32 | 91.38<br>±0.14 | 97.74<br>±0.06 | 98.65<br>±0.03 | 92.83<br>±0.09 | 58.15<br>±1.92 | 52.87<br>±0.55 | 50.91<br>±1.27 |
| GraphMixup [] | 92.31<br>±0.22 | 82.50<br>±0.12 | 90.58<br>±0.09 | 97.06<br>±0.17 | 93.85<br>±0.69 | 92.03<br>±0.09 | 58.73<br>±0.27 | 53.24<br>±0.08 | 52.46<br>±0.14 |
| LTE4G [] | 92.82<br>±0.56 | 83.87<br>±1.13 | 90.77<br>±2.91 | 97.19<br>±0.19 | 97.26<br>±0.46 | — | 59.10<br>±0.89 | 52.60<br>±0.18 | 53.96<br>±0.67 |
| TAM [] | 96.24<br>±0.04 | 87.22<br>±0.25 | 93.14<br>±0.05 | 97.75<br>±0.05 | 98.65<br>±0.03 | 92.84<br>±0.10 | 56.81<br>±2.37 | 52.99<br>±0.46 | 52.42<br>±0.14 |
| TOPOAUC [] | 90.42<br>±1.64 | 86.50<br>±0.50 | — | — | 93.14<br>±0.96 | — | 61.71<br>±0.80 | 52.17<br>±0.28 | 53.31<br>±0.34 |
| GraphSHA [] | 95.73<br>±0.11 | 85.10<br>±0.16 | 90.09<br>±3.59 | 97.51<br>±0.14 | 98.62<br>±0.06 | 92.18<br>±0.13 | 56.00<br>±2.91 | 52.87<br>±0.55 | 50.72<br>±0.98 |

##### D.1.2 Performance of Node-Level Local Topology-Imbalanced Algorithms

**Table D.5: Accuracy score (% ± standard deviation) of node classification on manipulated local topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 80.16<br>±0.97 | 66.99<br>±1.78 | 83.97<br>±0.14 | 70.39<br>±1.68 | 87.28<br>±2.77 | 55.45<br>±0.06 | 50.42<br>±1.22 | 30.87<br>±0.60 | 24.23<br>±1.74 |
| DEMO-Net [] | 81.40<br>±0.43 | 68.42<br>±0.72 | 82.70<br>±0.51 | 79.07<br>±0.53 | 88.06<br>±1.81 | 65.31<br>±0.15 | 56.18<br>±0.62 | 38.86<br>±0.78 | 29.34<br>±0.59 |
| meta-tail2vec [] | 38.11<br>±1.36 | 24.77<br>±2.39 | 59.93<br>±1.95 | 71.13<br>±0.41 | 77.16<br>±0.33 | 33.61<br>±0.25 | 41.45<br>±0.46 | 24.47<br>±0.18 | 25.98<br>±0.07 |
| Tail-GNN [] | 80.16<br>±0.64 | 70.37<br>±0.57 | 84.56<br>±0.30 | 86.40<br>±0.92 | 92.79<br>±0.19 | — | 51.87<br>±0.79 | 31.89<br>±0.93 | 28.67<br>±0.47 |
| Cold Brew [] | 75.37<br>±1.07 | 65.16<br>±0.59 | 86.11<br>±0.05 | 79.61<br>±0.40 | 85.94<br>±0.23 | 68.50<br>±0.07 | 58.78<br>±0.19 | 39.57<br>±0.19 | 32.93<br>±0.45 |
| LTE4G [] | 82.10<br>±0.56 | 69.17<br>±0.96 | 84.64<br>±0.30 | 81.24<br>±2.79 | 92.47<br>±0.21 | — | 58.61<br>±0.98 | 25.74<br>±2.58 | 24.53<br>±1.12 |
| RawlsGCN [] | 79.95<br>±0.29 | 72.20<br>±0.39 | 85.97<br>±0.12 | 78.74<br>±2.01 | 87.89<br>±0.10 | 41.70<br>±0.23 | 44.91<br>±1.15 | 29.68<br>±0.83 | 28.54<br>±0.12 |
| GraphPatcher [] | 84.00<br>±0.62 | 72.34<br>±0.32 | 85.58<br>±0.13 | 87.60<br>±0.23 | 93.20<br>±0.32 | 66.35<br>±0.09 | 55.77<br>±1.04 | 35.16<br>±0.22 | 27.15<br>±0.80 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 80.16<br>±1.09 | 66.87<br>±0.85 | 83.97<br>±0.13 | 71.65<br>±2.10 | 89.43<br>±0.58 | 52.93<br>±0.33 | 52.74<br>±0.60 | 28.70<br>±0.68 | 21.55<br>±1.74 |
| DEMO-Net [] | 80.37<br>±0.52 | 69.73<br>±1.31 | 84.11<br>±0.20 | 79.38<br>±0.98 | 88.09<br>±1.30 | 65.81<br>±0.11 | 55.51<br>±0.87 | 39.45<br>±0.62 | 29.12<br>±0.30 |
| meta-tail2vec [] | 32.17<br>±0.68 | 29.97<br>±3.61 | 59.82<br>±2.86 | 68.17<br>±1.07 | 79.82<br>±1.02 | 33.71<br>±1.16 | 38.78<br>±0.44 | 24.90<br>±0.25 | 26.09<br>±0.07 |
| Tail-GNN [] | 79.05<br>±1.15 | 69.97<br>±1.03 | 85.78<br>±0.41 | 84.09<br>±1.01 | 92.21<br>±0.09 | — | 53.20<br>±0.80 | 30.43<br>±1.06 | 28.02<br>±0.71 |
| Cold Brew [] | 73.84<br>±2.10 | 67.42<br>±0.97 | 86.51<br>±0.04 | 80.19<br>±0.24 | 88.13<br>±0.24 | 69.97<br>±0.07 | 59.16<br>±0.40 | 43.04<br>±0.24 | 33.01<br>±0.19 |
| LTE4G [] | 82.54<br>±0.46 | 70.55<br>±0.54 | 84.77<br>±0.78 | 81.32<br>±2.21 | 91.09<br>±0.19 | — | 55.84<br>±2.86 | 32.43<br>±3.31 | 24.00<br>±0.49 |
| RawlsGCN [] | 80.52<br>±0.14 | 72.38<br>±0.43 | 86.05<br>±0.12 | 78.78<br>±1.40 | 90.53<br>±1.32 | 40.00<br>±0.05 | 44.96<br>±0.79 | 29.93<br>±0.65 | 28.29<br>±0.24 |
| GraphPatcher [] | 83.25<br>±0.42 | 73.38<br>±0.42 | 85.60<br>±0.16 | 83.68<br>±0.69 | 92.28<br>±0.06 | 66.74<br>±0.04 | 55.19<br>±0.41 | 36.94<br>±0.11 | 23.85<br>±0.92 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 78.70<br>±1.05 | 65.07<br>±0.81 | 83.87<br>±0.32 | 68.15<br>±4.13 | 89.42<br>±1.24 | 50.72<br>±0.30 | 53.33<br>±1.09 | 29.56<br>±2.72 | 23.86<br>±0.90 |
| DEMO-Net [] | 78.23<br>±1.32 | 67.11<br>±0.44 | 83.51<br>±0.29 | 78.34<br>±0.88 | 88.08<br>±0.30 | 65.76<br>±0.18 | 54.08<br>±1.41 | 36.98<br>±1.27 | 28.96<br>±0.30 |
| meta-tail2vec [] | 38.16<br>±1.42 | 21.62<br>±1.70 | 58.39<br>±2.25 | 71.03<br>±2.20 | 66.37<br>±2.96 | 35.31<br>±0.21 | 37.94<br>±0.52 | 25.18<br>±0.30 | 25.98<br>±0.03 |
| Tail-GNN [] | 81.20<br>±0.55 | 69.69<br>±0.55 | 84.95<br>±0.37 | 86.39<br>±0.82 | 92.55<br>±0.40 | — | 53.00<br>±0.89 | 31.08<br>±0.91 | 28.36<br>±1.16 |
| Cold Brew [] | 75.44<br>±2.31 | 66.12<br>±0.71 | 86.44<br>±0.02 | 78.59<br>±0.10 | 86.83<br>±0.27 | 70.32<br>±0.08 | 59.47<br>±0.14 | 40.16<br>±0.16 | 33.44<br>±0.22 |
| LTE4G [] | 81.93<br>±1.43 | 67.09<br>±0.73 | 84.30<br>±0.49 | 83.33<br>±1.59 | 92.12<br>±0.32 | — | 56.39<br>±2.69 | 30.16<br>±4.09 | 23.83<br>±0.85 |
| RawlsGCN [] | 81.66<br>±0.17 | 69.88<br>±0.74 | 85.72<br>±0.07 | 79.27<br>±0.41 | 87.99<br>±1.16 | 39.14<br>±0.16 | 42.22<br>±0.37 | 28.54<br>±0.79 | 29.30<br>±0.17 |
| GraphPatcher [] | 80.77<br>±0.23 | 73.13<br>±0.48 | 85.74<br>±0.14 | 85.47<br>±0.16 | 93.57<br>±0.13 | 67.38<br>±0.06 | 56.74<br>±0.25 | 37.12<br>±0.18 | 25.48<br>±0.49 |

**Table D.6: Balanced Accuracy score (% ± standard deviation) of node classification on manipulated local topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. Best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 81.19<br>±0.89 | 63.72<br>±2.11 | 84.31<br>±0.14 | 77.82<br>±1.32 | 86.91<br>±2.30 | 22.36<br>±0.15 | 50.82<br>±0.89 | 30.86<br>±0.60 | 23.02<br>±1.14 |
| DEMO-Net [] | 82.53<br>±0.35 | 65.58<br>±0.71 | 83.84<br>±0.08 | 84.87<br>±0.25 | 90.06<br>±0.82 | 41.57<br>±1.20 | 56.18<br>±0.45 | 38.85<br>±0.78 | 26.59<br>±0.61 |
| meta-tail2vec [] | 27.64<br>±1.24 | 19.99<br>±1.80 | 53.78<br>±1.75 | 55.68<br>±4.36 | 80.39<br>±0.35 | 7.46<br>±0.43 | 40.58<br>±0.42 | 24.46<br>±0.16 | 20.12<br>±0.15 |
| Tail-GNN [] | 82.10<br>±0.28 | 66.78<br>±0.30 | 85.42<br>±0.41 | 90.80<br>±0.53 | 93.57<br>±0.77 | — | 51.96<br>±0.99 | 31.89<br>±0.93 | 28.28<br>±0.30 |
| Cold Brew [] | 77.41<br>±0.62 | 62.25<br>±1.02 | 86.11<br>±0.05 | 85.58<br>±0.35 | 88.67<br>±0.18 | 47.29<br>±0.12 | 58.05<br>±0.20 | 39.56<br>±0.19 | 29.01<br>±1.40 |
| LTE4G [] | 82.68<br>±0.43 | 67.45<br>±0.40 | 85.15<br>±0.25 | 87.35<br>±2.33 | 92.86<br>±0.44 | — | 58.15<br>±0.91 | 25.73<br>±2.58 | 24.31<br>±0.62 |
| RawlsGCN [] | 81.80<br>±0.21 | 68.80<br>±0.27 | 86.76<br>±0.13 | 84.67<br>±0.64 | 90.59<br>±0.31 | 13.32<br>±0.08 | 45.15<br>±0.83 | 29.69<br>±0.83 | 28.13<br>±0.12 |
| GraphPatcher [] | 84.66<br>±0.47 | 68.56<br>±0.16 | 85.68<br>±0.19 | 90.73<br>±0.18 | 93.61<br>±0.26 | 43.97<br>±0.09 | 55.28<br>±1.02 | 35.15<br>±0.22 | 22.46<br>±0.46 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 81.54<br>±0.39 | 63.00<br>±0.81 | 84.46<br>±0.13 | 78.91<br>±2.60 | 89.02<br>±0.58 | 18.12<br>±0.38 | 51.74<br>±0.65 | 28.69<br>±0.68 | 21.25<br>±0.33 |
| DEMO-Net [] | 81.75<br>±0.26 | 65.52<br>±1.00 | 84.99<br>±0.08 | 86.24<br>±0.63 | 89.43<br>±0.90 | 42.88<br>±0.66 | 55.37<br>±1.14 | 39.45<br>±0.62 | 26.70<br>±0.17 |
| meta-tail2vec [] | 32.56<br>±0.98 | 25.17<br>±1.60 | 56.16<br>±1.92 | 55.60<br>±4.13 | 81.26<br>±1.78 | 7.46<br>±0.68 | 39.92<br>±0.52 | 24.91<br>±0.25 | 20.08<br>±0.07 |
| Tail-GNN [] | 81.47<br>±0.27 | 66.05<br>±0.65 | 86.64<br>±0.30 | 90.06<br>±0.28 | 93.08<br>±0.19 | — | 53.40<br>±0.71 | 30.44<br>±1.05 | 26.26<br>±0.73 |
| Cold Brew [] | 76.00<br>±1.85 | 62.88<br>±1.10 | 86.41<br>±0.26 | 85.62<br>±0.07 | 89.20<br>±1.85 | 47.73<br>±0.13 | 58.71<br>±0.46 | 43.04<br>±0.25 | 30.65<br>±0.19 |
| LTE4G [] | 82.79<br>±0.32 | 65.79<br>±0.52 | 85.07<br>±0.67 | 87.16<br>±1.99 | 92.38<br>±0.17 | — | 55.04<br>±2.99 | 32.43<br>±3.32 | 24.14<br>±0.56 |
| RawlsGCN [] | 82.11<br>±0.18 | 67.74<br>±0.26 | 86.89<br>±0.16 | 84.76<br>±1.49 | 91.50<br>±0.20 | 11.62<br>±0.13 | 44.42<br>±1.19 | 29.93<br>±0.65 | 27.29<br>±0.20 |
| GraphPatcher [] | 83.94<br>±0.20 | 69.17<br>±0.22 | 85.72<br>±0.08 | 90.95<br>±0.21 | 93.21<br>±0.06 | 38.49<br>±0.41 | 54.39<br>±0.41 | 36.93<br>±0.11 | 23.10<br>±0.54 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 81.68<br>±0.84 | 62.76<br>±0.69 | 84.70<br>±0.07 | 78.15<br>±3.40 | 90.19<br>±0.35 | 15.93<br>±0.27 | 52.93<br>±1.49 | 29.54<br>±2.72 | 22.83<br>±0.57 |
| DEMO-Net [] | 82.14<br>±0.32 | 64.16<br>±0.76 | 84.70<br>±0.09 | 87.19<br>±0.50 | 90.51<br>±0.10 | 42.00<br>±1.23 | 54.11<br>±1.30 | 36.37<br>±1.66 | 27.16<br>±0.28 |
| meta-tail2vec [] | 25.23<br>±4.75 | 17.49<br>±1.12 | 52.61<br>±2.40 | 67.44<br>±2.57 | 72.79<br>±8.67 | 7.82<br>±0.12 | 36.66<br>±0.63 | 25.20<br>±0.30 | 20.03<br>±0.03 |
| Tail-GNN [] | 83.79<br>±0.49 | 67.15<br>±0.12 | 86.07<br>±0.12 | 90.72<br>±0.50 | 94.62<br>±0.22 | — | 53.12<br>±0.69 | 31.09<br>±0.91 | 27.36<br>±0.70 |
| Cold Brew [] | 78.25<br>±1.72 | 63.45<br>±1.10 | 86.43<br>±0.09 | 85.73<br>±0.10 | 90.14<br>±0.65 | 48.43<br>±0.16 | 59.66<br>±0.17 | 40.16<br>±0.16 | 30.68<br>±0.18 |
| LTE4G [] | 84.15<br>±1.36 | 64.63<br>±0.65 | 85.12<br>±0.38 | 89.78<br>±0.59 | 94.24<br>±0.28 | — | 56.25<br>±3.03 | 30.15<br>±4.10 | 24.03<br>±0.53 |
| RawlsGCN [] | 83.19<br>±0.24 | 67.51<br>±0.41 | 86.60<br>±0.10 | 86.25<br>±0.13 | 91.82<br>±0.24 | 10.65<br>±0.07 | 42.87<br>±0.81 | 28.54<br>±0.79 | 28.14<br>±0.20 |
| GraphPatcher [] | 83.91<br>±0.11 | 68.89<br>±0.09 | 85.78<br>±0.18 | 91.23<br>±0.05 | 93.57<br>±0.13 | 40.59<br>±0.39 | 56.78<br>±0.25 | 37.11<br>±0.18 | 23.98<br>±0.22 |

**Table D.7: Macro-F1 score (% ± standard deviation) of node classification on manipulated local topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 77.96<br>±1.22 | 63.07<br>±1.72 | 82.88<br>±0.12 | 58.70<br>±2.09 | 82.92<br>±2.33 | 21.64<br>±0.37 | 50.63<br>±1.22 | 29.19<br>±1.40 | 19.05<br>±2.75 |
| DEMO-Net [] | 79.01<br>±0.52 | 64.74<br>±0.77 | 81.93<br>±0.52 | 65.66<br>±1.07 | 84.73<br>±1.70 | 43.08<br>±1.01 | 55.67<br>±0.53 | 38.58<br>±0.69 | 26.45<br>±0.72 |
| meta-tail2vec [] | 23.87<br>±1.96 | 11.60<br>±2.38 | 53.82<br>±1.49 | 50.14<br>±3.23 | 71.66<br>±0.31 | 6.68<br>±0.82 | 40.11<br>±0.47 | 22.06<br>±1.32 | 9.48<br>±1.49 |
| Tail-GNN [] | 77.91<br>±0.37 | 66.32<br>±0.45 | 84.05<br>±0.30 | 75.59<br>±0.45 | 89.56<br>±0.35 | — | 51.09<br>±0.80 | 29.90<br>±0.46 | 26.95<br>±0.65 |
| Cold Brew [] | 73.42<br>±0.83 | 61.70<br>±0.77 | 85.41<br>±0.04 | 65.71<br>±0.27 | 81.89<br>±0.28 | 48.39<br>±0.13 | 58.50<br>±0.23 | 38.90<br>±0.47 | 26.89<br>±1.99 |
| LTE4G [] | 79.49<br>±0.55 | 66.21<br>±0.66 | 83.64<br>±0.33 | 69.51<br>±3.48 | 89.78<br>±0.28 | — | 58.48<br>±0.89 | 24.48<br>±3.27 | 23.15<br>±0.67 |
| RawlsGCN [] | 77.88<br>±0.28 | 68.20<br>±0.29 | 85.43<br>±0.12 | 67.01<br>±2.37 | 85.49<br>±0.34 | 14.56<br>±0.05 | 43.80<br>±1.19 | 29.24<br>±0.50 | 26.80<br>±0.10 |
| GraphPatcher [] | 81.64<br>±0.78 | 68.28<br>±0.22 | 84.65<br>±0.18 | 78.27<br>±0.69 | 90.48<br>±0.46 | 44.74<br>±0.04 | 55.67<br>±0.98 | 35.11<br>±0.30 | 19.03<br>±0.95 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 78.43<br>±0.94 | 62.70<br>±0.77 | 82.81<br>±0.10 | 60.43<br>±2.57 | 84.99<br>±0.76 | 17.40<br>±0.42 | 52.11<br>±0.66 | 27.48<br>±1.74 | 19.37<br>±1.28 |
| DEMO-Net [] | 78.11<br>±0.54 | 65.23<br>±1.02 | 83.44<br>±0.20 | 67.75<br>±0.73 | 84.14<br>±1.52 | 44.63<br>±0.59 | 55.17<br>±0.98 | 38.93<br>±0.60 | 26.48<br>±0.39 |
| meta-tail2vec [] | 30.58<br>±1.61 | 19.16<br>±3.28 | 54.86<br>±0.66 | 49.59<br>±1.24 | 76.33<br>±0.82 | 6.62<br>±0.98 | 38.29<br>±0.62 | 24.30<br>±0.24 | 8.70<br>±0.42 |
| Tail-GNN [] | 77.40<br>±1.05 | 65.77<br>±0.81 | 85.23<br>±0.41 | 73.31<br>±1.40 | 88.73<br>±0.13 | — | 52.53<br>±0.74 | 27.98<br>±0.79 | 25.68<br>±0.61 |
| Cold Brew [] | 71.85<br>±2.17 | 62.70<br>±1.00 | 85.69<br>±0.07 | 66.03<br>±0.20 | 84.26<br>±0.16 | 49.82<br>±0.18 | 58.91<br>±0.46 | 42.07<br>±0.40 | 30.71<br>±0.20 |
| LTE4G [] | 80.29<br>±0.45 | 65.76<br>±0.47 | 83.66<br>±0.88 | 68.65<br>±3.35 | 87.57<br>±0.13 | — | 55.32<br>±2.93 | 32.20<br>±3.71 | 22.78<br>±0.50 |
| RawlsGCN [] | 78.30<br>±0.26 | 67.50<br>±0.18 | 85.49<br>±0.14 | 66.62<br>±2.07 | 87.77<br>±1.45 | 12.56<br>±0.20 | 44.44<br>±1.11 | 29.48<br>±0.49 | 26.32<br>±0.21 |
| GraphPatcher [] | 80.92<br>±0.42 | 68.95<br>±0.25 | 84.65<br>±0.18 | 74.74<br>±0.73 | 88.89<br>±0.11 | 40.76<br>±0.32 | 54.72<br>±0.35 | 37.06<br>±0.11 | 22.28<br>±0.58 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 77.03<br>±1.19 | 61.89<br>±0.66 | 82.72<br>±0.32 | 58.78<br>±4.61 | 85.73<br>±0.84 | 14.52<br>±0.27 | 52.56<br>±1.25 | 27.43<br>±2.85 | 20.48<br>±2.59 |
| DEMO-Net [] | 76.85<br>±1.11 | 63.38<br>±0.68 | 82.87<br>±0.32 | 65.92<br>±0.62 | 84.70<br>±0.23 | 43.74<br>±1.02 | 53.73<br>±1.15 | 35.94<br>±1.44 | 27.24<br>±0.28 |
| meta-tail2vec [] | 21.82<br>±5.45 | 7.56<br>±2.36 | 52.03<br>±3.18 | 54.07<br>±2.19 | 65.22<br>±7.60 | 6.71<br>±0.18 | 34.06<br>±1.22 | 23.00<br>±0.60 | 8.30<br>±0.06 |
| Tail-GNN [] | 79.66<br>±0.57 | 66.29<br>±0.33 | 84.31<br>±0.35 | 75.04<br>±1.16 | 89.67<br>±0.39 | — | 52.67<br>±0.68 | 28.08<br>±1.18 | 25.85<br>±0.75 |
| Cold Brew [] | 73.71<br>±2.07 | 62.71<br>±0.76 | 85.72<br>±0.02 | 65.83<br>±0.13 | 83.37<br>±0.18 | 50.43<br>±0.24 | 59.18<br>±0.23 | 39.43<br>±0.41 | 30.32<br>±0.28 |
| LTE4G [] | 80.57<br>±1.66 | 63.70<br>±0.66 | 83.11<br>±0.54 | 73.38<br>±1.69 | 89.18<br>±0.52 | — | 55.92<br>±2.90 | 28.30<br>±5.09 | 22.95<br>±0.61 |
| RawlsGCN [] | 80.19<br>±0.20 | 66.41<br>±0.56 | 85.11<br>±0.08 | 69.00<br>±0.95 | 85.79<br>±1.10 | 11.24<br>±0.09 | 41.86<br>±0.35 | 27.86<br>±0.60 | 27.41<br>±0.16 |
| GraphPatcher [] | 79.35<br>±0.18 | 68.69<br>±0.20 | 84.74<br>±0.16 | 77.10<br>±0.43 | 90.94<br>±0.18 | 42.93<br>±0.29 | 56.05<br>±0.29 | 37.34<br>±0.19 | 23.10<br>±0.41 |

**Table D.8: AUC-ROC score (% ± standard deviation) of node classification on manipulated local topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 96.34<br>±0.51 | 87.80<br>±1.39 | 94.89<br>±0.06 | 95.61<br>±0.21 | 97.82<br>±0.80 | 87.84<br>±0.06 | 78.76<br>±0.27 | 62.68<br>±0.27 | 53.43<br>±1.42 |
| DEMO-Net [] | 96.27<br>±0.13 | 88.66<br>±0.30 | 94.22<br>±0.07 | 96.52<br>±0.10 | 98.04<br>±0.29 | 92.89<br>±0.32 | 80.31<br>±0.74 | 68.00<br>±0.69 | 58.96<br>±0.35 |
| meta-tail2vec [] | 62.83<br>±1.22 | 53.44<br>±2.06 | 71.50<br>±3.86 | 89.26<br>±0.64 | 94.95<br>±0.16 | 62.42<br>±2.26 | 69.63<br>±0.28 | 53.44<br>±0.62 | 50.50<br>±0.35 |
| Tail-GNN [] | 96.55<br>±0.06 | 89.11<br>±0.56 | 94.28<br>±0.69 | 97.92<br>±0.11 | 98.70<br>±0.13 | — | 76.76<br>±0.44 | 63.91<br>±1.16 | 59.72<br>±0.56 |
| Cold Brew [] | 93.87<br>±0.50 | 87.38<br>±0.98 | 95.67<br>±0.03 | 97.88<br>±0.05 | 98.71<br>±0.02 | 95.13<br>±0.10 | 78.37<br>±0.48 | 66.72<br>±0.10 | 65.12<br>±1.03 |
| LTE4G [] | 96.14<br>±0.37 | 88.78<br>±1.05 | 94.52<br>±0.45 | 92.94<br>±2.66 | 98.83<br>±0.05 | — | 78.00<br>±1.53 | 58.28<br>±2.12 | 56.17<br>±0.86 |
| RawlsGCN [] | 96.84<br>±0.07 | 91.06<br>±0.45 | 96.34<br>±0.03 | 97.47<br>±0.09 | 98.99<br>±0.02 | 79.78<br>±0.12 | 71.94<br>±0.09 | 58.89<br>±0.13 | 59.34<br>±0.16 |
| GraphPatcher [] | 97.10<br>±0.04 | 90.75<br>±0.15 | 94.98<br>±0.03 | 97.88<br>±0.05 | 98.54<br>±0.05 | 90.90<br>±0.03 | 79.09<br>±0.10 | 66.65<br>±0.30 | 53.80<br>±0.56 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 95.88<br>±0.29 | 87.55<br>±0.33 | 95.07<br>±0.06 | 95.70<br>±0.77 | 98.05<br>±0.11 | 86.55<br>±0.29 | 78.60<br>±0.38 | 62.45<br>±0.74 | 51.23<br>±0.46 |
| DEMO-Net [] | 95.59<br>±0.08 | 88.31<br>±0.26 | 94.78<br>±0.05 | 97.14<br>±0.18 | 97.75<br>±0.13 | 93.29<br>±0.35 | 80.31<br>±0.91 | 67.96<br>±0.32 | 59.54<br>±0.45 |
| meta-tail2vec [] | 65.88<br>±0.99 | 59.39<br>±0.47 | 73.30<br>±1.00 | 90.45<br>±0.24 | 94.66<br>±0.64 | 64.91<br>±1.30 | 68.34<br>±0.42 | 53.85<br>±0.04 | 49.40<br>±0.20 |
| Tail-GNN [] | 96.19<br>±0.22 | 89.73<br>±0.39 | 95.17<br>±0.55 | 97.98<br>±0.19 | 98.39<br>±0.27 | — | 76.40<br>±0.64 | 62.60<br>±1.37 | 58.11<br>±0.61 |
| Cold Brew [] | 93.14<br>±0.87 | 88.06<br>±1.14 | 96.06<br>±0.05 | 98.03<br>±0.02 | 98.40<br>±0.33 | 95.66<br>±0.06 | 77.61<br>±0.13 | 68.96<br>±0.16 | 65.47<br>±0.17 |
| LTE4G [] | 95.16<br>±0.59 | 89.69<br>±0.44 | 94.41<br>±0.96 | 93.05<br>±2.75 | 97.74<br>±0.33 | — | 77.80<br>±1.83 | 61.90<br>±1.44 | 55.08<br>±0.68 |
| RawlsGCN [] | 96.65<br>±0.07 | 91.53<br>±0.43 | 96.29<br>±0.04 | 97.53<br>±0.07 | 98.97<br>±0.02 | 79.84<br>±0.22 | 71.42<br>±0.15 | 59.10<br>±0.08 | 59.19<br>±0.14 |
| GraphPatcher [] | 96.66<br>±0.08 | 91.74<br>±0.09 | 94.63<br>±0.02 | 98.05<br>±0.07 | 98.14<br>±0.02 | 92.04<br>±0.11 | 78.36<br>±0.26 | 66.40<br>±0.12 | 54.64<br>±0.62 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 96.12<br>±0.31 | 87.93<br>±0.88 | 94.96<br>±0.08 | 95.42<br>±0.99 | 87.28<br>±2.77 | 85.44<br>±0.40 | 78.63<br>±0.38 | 63.00<br>±1.36 | 53.72<br>±0.70 |
| DEMO-Net [] | 95.40<br>±0.19 | 87.64<br>±0.09 | 94.31<br>±0.08 | 97.10<br>±0.25 | 98.34<br>±0.15 | 93.45<br>±0.78 | 79.19<br>±0.89 | 66.28<br>±1.10 | 58.89<br>±0.28 |
| meta-tail2vec [] | 61.19<br>±1.02 | 49.89<br>±1.49 | 69.63<br>±3.44 | 92.90<br>±0.31 | 91.77<br>±2.16 | 62.67<br>±1.41 | 68.62<br>±0.77 | 55.24<br>±0.23 | 50.04<br>±0.34 |
| Tail-GNN [] | 96.80<br>±0.05 | 89.96<br>±0.42 | 95.10<br>±0.15 | 97.93<br>±0.10 | 98.60<br>±0.13 | — | 76.81<br>±0.31 | 64.39<br>±0.42 | 59.60<br>±1.06 |
| Cold Brew [] | 94.04<br>±0.64 | 88.26<br>±0.37 | 95.90<br>±0.03 | 97.82<br>±0.05 | 98.87<br>±0.10 | 95.86<br>±0.06 | 78.97<br>±0.34 | 67.72<br>±0.11 | 65.52<br>±0.16 |
| LTE4G [] | 96.17<br>±0.35 | 86.40<br>±2.05 | 94.46<br>±0.31 | 95.97<br>±1.48 | 98.72<br>±0.06 | — | 77.34<br>±1.75 | 60.35<br>±2.63 | 54.98<br>±0.84 |
| RawlsGCN [] | 96.87<br>±0.03 | 90.42<br>±0.13 | 96.16<br>±0.03 | 97.51<br>±0.04 | 99.21<br>±0.02 | 79.47<br>±0.15 | 71.04<br>±0.11 | 58.32<br>±0.12 | 59.38<br>±0.13 |
| GraphPatcher [] | 96.15<br>±0.05 | 91.55<br>±0.48 | 94.90<br>±0.02 | 97.59<br>±0.05 | 98.75<br>±0.02 | 92.53<br>±0.05 | 78.67<br>±0.15 | 65.82<br>±0.40 | 56.03<br>±0.19 |

##### D.1.3 Performance of Node-Level Global Topology-Imbalanced Algorithms

**Table D.9: Accuracy score (% ± standard deviation) of node classification on manipulated global topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 81.09<br>±0.76 | 70.39<br>±1.11 | 84.44<br>±0.20 | 76.23<br>±2.16 | 88.16<br>±1.86 | 53.09<br>±0.17 | 37.80<br>±0.59 | 25.15<br>±0.57 | 24.34<br>±0.78 |
| ReNode [] | 81.94<br>±0.48 | 71.93<br>±0.88 | 83.86<br>±0.13 | 79.42<br>±1.70 | 89.91<br>±0.51 | 52.75<br>±0.14 | 37.67<br>±0.49 | 25.36<br>±0.49 | 24.65<br>±0.28 |
| TAM [] | 81.48<br>±0.30 | 74.06<br>±0.12 | 84.26<br>±0.08 | 84.17<br>±0.18 | 91.93<br>±0.22 | 54.16<br>±0.05 | 38.78<br>±0.17 | 25.64<br>±0.12 | 24.77<br>±0.33 |
| PASTEL [] | 82.49<br>±0.34 | 74.38<br>±0.31 | — | 85.08<br>±0.84 | 91.22<br>±0.40 | — | 54.05<br>±1.13 | 34.01<br>±0.57 | 29.50<br>±0.39 |
| TOPOAUC [] | 81.38<br>±0.80 | 72.31<br>±0.75 | — | 77.23<br>±1.31 | 89.04<br>±0.96 | — | 37.68<br>±0.81 | 23.52<br>±0.78 | 25.88<br>±0.97 |
| HyperIMBA [] | 80.67<br>±0.64 | 73.46<br>±0.70 | 85.19<br>±0.26 | 85.22<br>±0.64 | 92.75<br>±0.13 | — | 43.48<br>±1.30 | 32.69<br>±0.66 | 27.09<br>±3.15 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 79.10<br>±1.28 | 68.37<br>±1.73 | 83.44<br>±0.16 | 75.02<br>±2.20 | 86.32<br>±1.90 | 51.04<br>±0.18 | 33.90<br>±0.70 | 23.27<br>±0.82 | 22.40<br>±0.68 |
| ReNode [] | 79.91<br>±1.52 | 69.89<br>±0.73 | 82.97<br>±0.12 | 77.95<br>±1.71 | 87.80<br>±0.52 | 50.68<br>±0.15 | 32.92<br>±0.98 | 23.80<br>±0.59 | 22.39<br>±0.62 |
| TAM [] | 80.50<br>±0.18 | 73.14<br>±0.13 | 84.07<br>±0.12 | 82.35<br>±0.19 | 89.80<br>±0.23 | 52.09<br>±0.06 | 35.64<br>±0.27 | 24.58<br>±0.09 | 22.55<br>±0.06 |
| PASTEL [] | 80.91<br>±0.36 | 72.73<br>±0.26 | — | 83.24<br>±0.85 | 89.10<br>±0.41 | — | 47.12<br>±2.82 | 33.15<br>±0.66 | 27.56<br>±1.04 |
| TOPOAUC [] | 79.27<br>±0.52 | 70.08<br>±0.83 | — | 75.35<br>±1.32 | 87.10<br>±0.98 | — | 33.39<br>±2.09 | 22.86<br>±0.36 | 22.56<br>±0.18 |
| HyperIMBA [] | 79.81<br>±0.78 | 71.78<br>±0.40 | 84.75<br>±0.30 | 83.43<br>±0.65 | 90.65<br>±0.14 | — | 38.30<br>±2.70 | 29.97<br>±1.79 | 25.30<br>±2.56 |

**Table D.10: Balanced Accuracy score (% ± standard deviation) of node classification on manipulated global topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. Best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 82.78<br>±0.52 | 67.45<br>±0.81 | 85.17<br>±0.15 | 85.09<br>±1.63 | 89.28<br>±1.00 | 36.76<br>±0.20 | 38.28<br>±0.50 | 25.14<br>±0.57 | 23.78<br>±0.63 |
| ReNode [] | 82.89<br>±0.82 | 68.52<br>±1.14 | 84.52<br>±0.11 | 86.93<br>±0.83 | 90.03<br>±0.51 | 36.79<br>±0.18 | 38.02<br>±0.50 | 25.36<br>±0.49 | 24.04<br>±0.39 |
| TAM [] | 82.49<br>±0.11 | 70.97<br>±0.13 | 84.71<br>±0.06 | 89.91<br>±0.08 | 91.81<br>±0.13 | 39.96<br>±0.05 | 39.16<br>±0.14 | 25.63<br>±0.12 | 24.25<br>±0.19 |
| PASTEL [] | 83.46<br>±0.32 | 71.17<br>±0.28 | — | 90.41<br>±0.38 | 93.56<br>±0.11 | — | 54.27<br>±1.18 | 34.02<br>±0.57 | 26.89<br>±0.43 |
| TOPOAUC [] | 83.15<br>±0.26 | 68.07<br>±0.21 | — | 76.90<br>±4.12 | 87.93<br>±3.60 | — | 38.16<br>±0.65 | 23.51<br>±0.78 | 23.96<br>±0.33 |
| HyperIMBA [] | 82.32<br>±0.41 | 70.75<br>±0.56 | 86.45<br>±0.11 | 91.54<br>±0.30 | 92.36<br>±0.16 | — | 43.39<br>±1.43 | 32.68<br>±0.66 | 28.45<br>±3.43 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 81.99<br>±0.51 | 64.66<br>±0.91 | 84.22<br>±0.13 | 83.42<br>±1.65 | 87.36<br>±1.02 | 34.78<br>±0.21 | 34.75<br>±0.67 | 23.27<br>±0.82 | 22.52<br>±0.42 |
| ReNode [] | 82.28<br>±0.71 | 66.04<br>±0.52 | 83.85<br>±0.09 | 85.43<br>±0.84 | 88.10<br>±0.52 | 34.75<br>±0.19 | 33.87<br>±0.77 | 23.80<br>±0.59 | 22.68<br>±0.37 |
| TAM [] | 82.87<br>±0.13 | 69.81<br>±0.11 | 84.59<br>±0.08 | 87.88<br>±0.09 | 89.70<br>±0.14 | 37.92<br>±0.06 | 36.18<br>±0.35 | 24.58<br>±0.09 | 23.15<br>±0.12 |
| PASTEL [] | 83.36<br>±0.20 | 69.71<br>±0.23 | — | 88.92<br>±0.39 | 91.40<br>±0.12 | — | 47.41<br>±2.27 | 33.15<br>±0.66 | 25.55<br>±0.57 |
| TOPOAUC [] | 82.28<br>±0.35 | 65.82<br>±1.20 | — | 74.75<br>±4.13 | 86.00<br>±3.65 | — | 34.45<br>±1.56 | 22.85<br>±0.36 | 23.27<br>±0.26 |
| HyperIMBA [] | 82.54<br>±0.76 | 68.97<br>±0.38 | 85.64<br>±0.12 | 89.74<br>±0.31 | 90.25<br>±0.17 | — | 38.00<br>±3.16 | 29.96<br>±1.79 | 26.77<br>±2.45 |

**Table D.11: Macro-F1 score (% ± standard deviation) of node classification on manipulated global topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 79.45<br>±0.73 | 66.81<br>±1.04 | 83.54<br>±0.19 | 64.78<br>±2.90 | 84.82<br>±1.48 | 33.94<br>±0.21 | 36.69<br>±0.65 | 24.85<br>±0.65 | 23.13<br>±0.55 |
| ReNode [] | 80.26<br>±0.38 | 68.21<br>±0.81 | 82.98<br>±0.12 | 68.61<br>±1.47 | 86.14<br>±0.66 | 33.88<br>±0.17 | 36.60<br>±0.50 | 24.75<br>±0.61 | 23.33<br>±0.28 |
| TAM [] | 79.01<br>±0.24 | 70.30<br>±0.13 | 83.22<br>±0.08 | 75.36<br>±0.22 | 88.34<br>±0.22 | 36.75<br>±0.05 | 36.45<br>±0.19 | 23.59<br>±0.27 | 23.44<br>±0.20 |
| PASTEL [] | 80.79<br>±0.33 | 70.62<br>±0.32 | — | 73.94<br>±1.06 | 88.17<br>±0.41 | — | 53.30<br>±1.30 | 33.54<br>±0.69 | 26.34<br>±0.23 |
| TOPOAUC [] | 79.75<br>±0.63 | 68.01<br>±1.03 | — | 60.13<br>±3.52 | 84.39<br>±4.10 | — | 36.76<br>±1.01 | 21.50<br>±1.71 | 22.76<br>±0.70 |
| HyperIMBA [] | 78.85<br>±0.66 | 69.96<br>±0.53 | 84.16<br>±0.26 | 73.55<br>±0.72 | 89.45<br>±0.21 | — | 42.83<br>±1.43 | 30.26<br>±1.87 | 26.41<br>±3.17 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 78.12<br>±1.02 | 64.20<br>±1.32 | 82.55<br>±0.15 | 63.54<br>±2.95 | 82.92<br>±1.50 | 31.85<br>±0.22 | 32.39<br>±1.15 | 22.36<br>±1.62 | 21.66<br>±0.48 |
| ReNode [] | 78.80<br>±1.23 | 65.50<br>±0.69 | 82.08<br>±0.11 | 66.12<br>±1.48 | 84.20<br>±0.67 | 31.90<br>±0.18 | 30.82<br>±1.71 | 22.77<br>±1.09 | 21.69<br>±0.51 |
| TAM [] | 79.34<br>±0.23 | 69.13<br>±0.11 | 83.17<br>±0.11 | 73.25<br>±0.23 | 86.25<br>±0.23 | 34.68<br>±0.06 | 33.95<br>±0.38 | 22.52<br>±0.17 | 22.10<br>±0.06 |
| PASTEL [] | 79.37<br>±0.33 | 68.99<br>±0.25 | — | 72.45<br>±1.07 | 86.25<br>±0.42 | — | 46.59<br>±3.16 | 31.95<br>±1.06 | 25.11<br>±0.67 |
| TOPOAUC [] | 78.24<br>±0.42 | 65.48<br>±1.05 | — | 58.54<br>±3.54 | 82.50<br>±4.15 | — | 29.95<br>±3.52 | 21.06<br>±1.40 | 22.15<br>±0.18 |
| HyperIMBA [] | 78.44<br>±0.99 | 68.24<br>±0.30 | 83.83<br>±0.33 | 71.87<br>±0.73 | 87.40<br>±0.22 | — | 37.25<br>±2.98 | 28.82<br>±2.72 | 24.45<br>±2.46 |

**Table D.12: AUC-ROC score (% ± standard deviation) of node classification on manipulated global topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | Cora<br>0.81 | CiteSeer<br>0.74 | PubMed<br>0.80 | Computers<br>0.78 | Photo<br>0.82 | ogbn-arXiv<br>0.65 | Chameleon<br>0.23 | Squirrel<br>0.22 | Actor<br>0.22 |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 94.82<br>±0.72 | 88.43<br>±1.03 | 94.16<br>±0.15 | 94.98<br>±1.18 | 93.61<br>±1.67 | 88.49<br>±0.14 | 66.27<br>±0.87 | 54.98<br>±0.49 | 54.74<br>±0.22 |
| ReNode [] | 95.16<br>±0.67 | 88.41<br>±0.99 | 94.06<br>±0.40 | 94.91<br>±1.26 | 93.97<br>±1.60 | 88.42<br>±0.16 | 66.08<br>±0.30 | 55.21<br>±0.47 | 54.83<br>±0.20 |
| TAM [] | 96.75<br>±0.04 | 91.87<br>±0.07 | 94.86<br>±0.01 | 98.17<br>±0.01 | 99.01<br>±0.01 | 92.30<br>±0.02 | 65.00<br>±0.37 | 55.10<br>±0.10 | 55.44<br>±0.24 |
| PASTEL [] | 97.05<br>±0.07 | 92.90<br>±0.13 | — | 98.45<br>±0.03 | 99.28<br>±0.03 | — | 80.43<br>±0.46 | 63.47<br>±0.47 | 59.43<br>±0.30 |
| TOPOAUC [] | 97.07<br>±0.20 | 90.67<br>±0.67 | — | 92.28<br>±2.62 | 98.54<br>±0.14 | — | 65.74<br>±0.47 | 52.72<br>±0.34 | 55.21<br>±0.60 |
| HyperIMBA [] | 96.19<br>±0.19 | 91.50<br>±0.51 | 95.31<br>±0.11 | 98.39<br>±0.06 | 98.71<br>±0.09 | — | 68.48<br>±2.94 | 60.29<br>±1.42 | 59.92<br>±3.31 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |  |  |
| GCN (bb.) [] | 94.97<br>±0.67 | 87.95<br>±1.04 | 93.02<br>±0.17 | 93.05<br>±1.22 | 91.45<br>±1.70 | 86.43<br>±0.15 | 62.31<br>±1.16 | 53.67<br>±0.33 | 53.17<br>±0.29 |
| ReNode [] | 95.00<br>±0.78 | 87.86<br>±1.00 | 93.23<br>±0.21 | 93.75<br>±1.27 | 92.15<br>±1.62 | 86.42<br>±0.17 | 61.68<br>±1.15 | 54.15<br>±0.49 | 53.02<br>±0.18 |
| TAM [] | 96.78<br>±0.13 | 92.04<br>±0.12 | 94.88<br>±0.02 | 96.23<br>±0.02 | 97.20<br>±0.02 | 90.25<br>±0.03 | 62.91<br>±0.62 | 54.27<br>±0.06 | 53.49<br>±0.06 |
| PASTEL [] | 97.31<br>±0.04 | 92.65<br>±0.10 | — | 96.75<br>±0.04 | 97.10<br>±0.04 | — | 76.49<br>±0.97 | 63.78<br>±0.40 | 57.70<br>±0.37 |
| TOPOAUC [] | 96.54<br>±0.22 | 89.88<br>±0.25 | — | 90.89<br>±2.63 | 96.40<br>±0.15 | — | 60.37<br>±1.82 | 52.77<br>±0.21 | 53.96<br>±0.21 |
| HyperIMBA [] | 96.57<br>±0.30 | 92.23<br>±0.32 | 94.95<br>±0.13 | 96.85<br>±0.07 | 96.55<br>±0.10 | — | 64.57<br>±1.44 | 58.83<br>±2.05 | 57.20<br>±2.58 |

##### D.1.4 Performance of Graph-Level Class-Imbalanced Algorithms

**Table D.13: Accuracy score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 50.43<br>±2.69 | 64.27<br>±2.47 | 65.34<br>±2.72 | 64.04<br>±3.79 | 66.05<br>±2.57 | 76.66<br>±4.80 | 65.31<br>±3.25 |
| G^2GNN [] | 53.70<br>±3.87 | 63.63<br>±1.16 | 65.50<br>±2.69 | 66.07<br>±2.27 | 61.91<br>±3.77 | 72.34<br>±2.76 | 53.82<br>±2.26 |
| TopoImb [] | 50.91<br>±2.18 | 61.45<br>±3.74 | 55.04<br>±5.13 | 66.57<br>±3.81 | 66.28<br>±1.85 | 73.99<br>±1.18 | 65.92<br>±1.36 |
| DataDec [] | 54.05<br>±4.85 | 66.90<br>±3.36 | 65.24<br>±4.06 | 64.46<br>±1.88 | 64.09<br>±5.75 | 79.29<br>±8.18 | 72.24<br>±0.19 |
| ImGKB [] | 53.48<br>±3.50 | 52.54<br>±6.05 | 69.85<br>±1.95 | 65.45<br>±2.88 | 50.16<br>±0.34 | 50.24<br>±0.29 | 39.34<br>±10.88 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 47.83<br>±2.95 | 63.38<br>±1.93 | 55.38<br>±3.57 | 51.05<br>±5.07 | 62.31<br>±3.99 | 61.10<br>±4.86 | 65.01<br>±1.33 |
| G^2GNN [] | 51.88<br>±6.23 | 61.13<br>±1.05 | 63.61<br>±5.03 | 56.29<br>±7.30 | 63.87<br>±4.64 | 69.58<br>±3.59 | 62.05<br>±3.06 |
| TopoImb [] | 44.86<br>±3.52 | 49.49<br>±7.14 | 52.12<br>±10.51 | 49.97<br>±7.24 | 59.95<br>±5.19 | 59.67<br>±7.30 | 65.88<br>±0.75 |
| DataDec [] | 55.72<br>±2.88 | 67.99<br>±0.75 | 66.58<br>±1.35 | 63.51<br>±1.62 | 67.92<br>±3.37 | 78.39<br>±5.01 | 71.48<br>±1.03 |
| ImGKB [] | 50.11<br>±5.95 | 40.83<br>±0.02 | 66.60<br>±2.64 | 65.85<br>±3.70 | 47.74<br>±0.29 | 48.57<br>±2.14 | 51.21<br>±0.10 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 39.42<br>±1.87 | 56.02<br>±1.43 | 42.50<br>±2.05 | 41.54<br>±6.57 | 53.57<br>±3.21 | 55.56<br>±7.85 | 62.00<br>±3.08 |
| G^2GNN [] | 46.52<br>±9.94 | 55.41<br>±3.91 | 52.97<br>±13.44 | 55.38<br>±15.60 | 59.44<br>±6.49 | 63.22<br>±4.67 | 62.61<br>±1.14 |
| TopoImb [] | 39.42<br>±1.24 | 46.45<br>±6.77 | 39.23<br>±4.28 | 39.12<br>±1.62 | 47.75<br>±3.73 | 51.58<br>±4.69 | 64.19<br>±1.77 |
| DataDec [] | 58.69<br>±3.10 | 67.82<br>±1.88 | 61.99<br>±7.15 | 65.77<br>±2.71 | 66.30<br>±6.70 | 77.72<br>±5.12 | 71.50<br>±1.15 |
| ImGKB [] | 44.24<br>±5.65 | 38.34<br>±0.01 | 61.46<br>±10.25 | 59.99<br>±7.57 | 47.08<br>±3.72 | 51.25<br>±5.10 | 50.20<br>±0.06 |

**Table D.14: Balanced Accuracy score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 51.40<br>±1.64 | 64.33<br>±2.20 | 64.90<br>±1.51 | 63.37<br>±3.26 | 66.05<br>±2.57 | 76.66<br>±4.80 | 72.99<br>±1.83 |
| G^2GNN [] | 53.42<br>±3.72 | 63.55<br>±1.22 | 64.39<br>±2.21 | 63.79<br>±2.13 | 61.91<br>±3.77 | 72.34<br>±2.76 | 64.17<br>±0.51 |
| TopoImb [] | 53.99<br>±2.19 | 60.81<br>±2.83 | 59.71<br>±2.03 | 67.19<br>±2.46 | 66.28<br>±1.85 | 73.99<br>±1.18 | 51.93<br>±2.88 |
| DataDec [] | 53.70<br>±4.25 | 65.06<br>±5.28 | 62.39<br>±2.38 | 62.96<br>±1.21 | 64.22<br>±5.73 | 79.80<br>±7.38 | 62.31<br>±1.96 |
| ImGKB [] | 53.34<br>±3.61 | 49.98<br>±0.06 | 68.09<br>±2.49 | 62.33<br>±4.38 | 49.99<br>±0.47 | 50.24<br>±0.29 | 33.38<br>±0.10 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 51.36<br>±2.25 | 61.90<br>±2.13 | 60.39<br>±2.22 | 57.33<br>±3.16 | 63.54<br>±3.46 | 62.89<br>±4.61 | 47.03<br>±1.45 |
| G^2GNN [] | 52.75<br>±2.14 | 63.31<br>±1.14 | 66.18<br>±3.06 | 61.09<br>±4.11 | 64.28<br>±5.02 | 70.26<br>±3.41 | 60.76<br>±2.04 |
| TopoImb [] | 50.44<br>±3.75 | 56.57<br>±5.30 | 59.88<br>±6.33 | 58.33<br>±4.40 | 61.14<br>±4.56 | 61.34<br>±6.80 | 48.95<br>±1.64 |
| DataDec [] | 53.42<br>±2.33 | 66.10<br>±1.22 | 61.54<br>±2.33 | 61.27<br>±1.04 | 67.95<br>±2.77 | 78.68<br>±4.93 | 68.71<br>±1.11 |
| ImGKB [] | 51.61<br>±3.12 | 50.01<br>±0.02 | 64.72<br>±5.37 | 63.39<br>±1.76 | 50.23<br>±0.28 | 50.07<br>±0.15 | 33.33<br>±0.00 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 47.89<br>±2.12 | 54.66<br>±1.53 | 53.30<br>±1.63 | 52.47<br>±4.58 | 57.46<br>±2.77 | 59.54<br>±7.11 | 44.67<br>±2.98 |
| G^2GNN [] | 50.76<br>±1.78 | 60.38<br>±1.91 | 51.32<br>±6.16 | 53.17<br>±2.90 | 61.85<br>±5.36 | 65.97<br>±4.07 | 54.91<br>±2.09 |
| TopoImb [] | 49.99<br>±0.93 | 55.82<br>±4.93 | 53.96<br>±2.78 | 52.05<br>±1.31 | 52.82<br>±3.06 | 55.87<br>±4.09 | 47.98<br>±1.65 |
| DataDec [] | 55.22<br>±3.81 | 65.24<br>±2.16 | 60.22<br>±3.13 | 61.60<br>±2.60 | 66.30<br>±4.93 | 77.77<br>±5.49 | 68.99<br>±2.04 |
| ImGKB [] | 51.38<br>±3.53 | 50.00<br>±0.01 | 64.48<br>±5.90 | 59.14<br>±4.10 | 50.07<br>±0.35 | 50.28<br>±0.23 | 33.33<br>±0.00 |

**Table D.15: Macro-F1 score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 48.85<br>±3.33 | 63.86<br>±2.39 | 63.98<br>±2.09 | 59.87<br>±7.24 | 65.24<br>±3.21 | 76.20<br>±5.00 | 60.83<br>±3.61 |
| G^2GNN [] | 52.88<br>±3.70 | 63.28<br>±1.13 | 63.89<br>±2.39 | 63.31<br>±2.42 | 60.99<br>±3.50 | 71.74<br>±3.14 | 46.71<br>±2.55 |
| TopoImb [] | 48.33<br>±3.70 | 58.58<br>±5.21 | 53.13<br>±5.72 | 65.72<br>±3.45 | 65.85<br>±2.29 | 73.41<br>±0.01 | 51.32<br>±4.63 |
| DataDec [] | 52.98<br>±4.65 | 63.64<br>±9.26 | 62.20<br>±3.28 | 62.83<br>±1.20 | 62.42<br>±8.07 | 79.02<br>±8.63 | 63.82<br>±1.02 |
| ImGKB [] | 50.36<br>±5.89 | 34.59<br>±2.65 | 67.98<br>±2.43 | 61.06<br>±7.96 | 35.27<br>±4.74 | 33.97<br>±0.42 | 18.66<br>±3.43 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 46.63<br>±2.95 | 61.27<br>±2.51 | 55.20<br>±3.70 | 49.89<br>±6.19 | 59.66<br>±5.94 | 56.10<br>±6.75 | 37.64<br>±1.08 |
| G^2GNN [] | 47.64<br>±7.63 | 61.11<br>±1.06 | 62.89<br>±4.70 | 55.34<br>±8.20 | 61.37<br>±8.64 | 69.03<br>±3.78 | 55.48<br>±2.78 |
| TopoImb [] | 40.26<br>±2.06 | 43.64<br>±11.61 | 49.66<br>±12.86 | 47.37<br>±9.53 | 56.78<br>±8.24 | 54.07<br>±11.22 | 47.31<br>±0.03 |
| DataDec [] | 52.31<br>±3.50 | 66.22<br>±1.25 | 61.66<br>±2.33 | 61.12<br>±1.22 | 67.42<br>±3.69 | 77.96<br>±5.66 | 68.49<br>±0.60 |
| ImGKB [] | 44.62<br>±8.86 | 29.05<br>±0.08 | 62.49<br>±8.12 | 62.91<br>±2.34 | 32.70<br>±0.62 | 32.81<br>±1.21 | 22.58<br>±0.03 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 35.14<br>±4.01 | 46.81<br>±3.33 | 41.20<br>±2.65 | 38.83<br>±8.36 | 47.51<br>±5.47 | 48.74<br>±11.66 | 36.37<br>±0.93 |
| G^2GNN [] | 37.35<br>±7.10 | 54.73<br>±4.33 | 44.16<br>±10.15 | 42.22<br>±11.10 | 56.79<br>±9.27 | 61.15<br>±6.30 | 50.73<br>±4.21 |
| TopoImb [] | 32.16<br>±3.27 | 40.55<br>±10.82 | 34.48<br>±6.61 | 34.24<br>±2.40 | 36.64<br>±6.35 | 41.81<br>±9.90 | 45.32<br>±0.02 |
| DataDec [] | 54.76<br>±4.61 | 64.94<br>±2.97 | 58.47<br>±4.92 | 61.67<br>±2.67 | 64.82<br>±8.14 | 77.39<br>±5.38 | 68.87<br>±1.57 |
| ImGKB [] | 41.35<br>±7.92 | 27.73<br>±0.04 | 59.75<br>±11.28 | 57.16<br>±5.54 | 32.23<br>±1.61 | 34.31<br>±2.68 | 22.28<br>±0.02 |

**Table D.16: AUC-ROC score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 52.26<br>±2.95 | 69.20<br>±2.35 | 67.91<br>±2.87 | 66.54<br>±5.28 | 73.99<br>±2.41 | 87.61<br>±4.35 | 86.80<br>±1.38 |
| G^2GNN [] | 54.55<br>±5.56 | 68.03<br>±1.39 | 67.09<br>±3.07 | 70.05<br>±2.41 | 64.87<br>±4.48 | 80.22<br>±4.01 | 79.90<br>±0.80 |
| TopoImb [] | 56.93<br>±4.29 | 69.09<br>±1.17 | 69.33<br>±4.09 | 72.86<br>±1.46 | 74.83<br>±1.01 | 81.49<br>±3.03 | 85.12<br>±0.39 |
| DataDec [] | 54.57<br>±6.02 | 72.65<br>±3.55 | 68.80<br>±4.16 | 68.18<br>±1.32 | 72.25<br>±5.65 | 81.26<br>±13.78 | 87.29<br>±0.32 |
| ImGKB [] | 54.09<br>±5.28 | 54.78<br>±2.66 | 73.47<br>±2.00 | 66.54<br>±2.08 | 50.60<br>±1.23 | 74.36<br>±5.01 | 50.29<br>±0.86 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 51.28<br>±4.16 | 68.74<br>±2.22 | 59.21<br>±3.70 | 54.13<br>±6.72 | 74.38<br>±2.48 | 84.08<br>±4.85 | 86.05<br>±1.11 |
| G^2GNN [] | 51.90<br>±3.85 | 68.70<br>±1.13 | 69.59<br>±3.54 | 64.49<br>±5.43 | 69.02<br>±3.60 | 77.97<br>±4.62 | 78.15<br>±2.04 |
| TopoImb [] | 50.82<br>±3.94 | 67.96<br>±2.26 | 66.77<br>±5.44 | 67.76<br>±4.85 | 72.61<br>±2.10 | 83.30<br>±3.79 | 86.31<br>±1.42 |
| DataDec [] | 53.49<br>±1.94 | 73.98<br>±0.59 | 69.32<br>±1.81 | 67.05<br>±1.47 | 75.40<br>±3.23 | 81.00<br>±8.17 | 85.68<br>±2.32 |
| ImGKB [] | 52.89<br>±4.84 | 53.59<br>±1.12 | 72.57<br>±1.37 | 68.08<br>±2.00 | 51.06<br>±1.08 | 76.25<br>±3.29 | 50.42<br>±0.97 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GIN (bb.) [] | 47.04<br>±3.22 | 64.26<br>±4.79 | 59.00<br>±2.60 | 47.06<br>±5.01 | 65.96<br>±9.53 | 80.58<br>±3.45 | 81.04<br>±3.44 |
| G^2GNN [] | 49.32<br>±4.07 | 66.60<br>±1.48 | 52.10<br>±7.10 | 60.76<br>±4.90 | 65.79<br>±7.00 | 72.55<br>±5.64 | 75.67<br>±1.51 |
| TopoImb [] | 48.09<br>±3.94 | 69.48<br>±1.14 | 65.62<br>±3.19 | 61.49<br>±5.30 | 69.12<br>±7.15 | 80.08<br>±5.47 | 82.28<br>±2.86 |
| DataDec [] | 57.66<br>±5.55 | 73.51<br>±1.01 | 64.35<br>±6.86 | 69.11<br>±3.67 | 74.89<br>±4.11 | 82.59<br>±6.05 | 87.03<br>±1.21 |
| ImGKB [] | 52.80<br>±5.19 | 54.03<br>±2.17 | 71.98<br>±2.36 | 63.79<br>±4.04 | 51.04<br>±1.57 | 71.65<br>±6.48 | 50.05<br>±0.63 |

**Table D.17: Accuracy score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 48.62<br>±7.12 | 52.67<br>±6.11 | 65.44<br>±2.73 | 63.97<br>±4.09 | 59.76<br>±1.78 | 66.65<br>±1.06 | 61.23<br>±3.38 |
| G^2GNN [] | 44.35<br>±4.32 | 52.10<br>±4.27 | 68.82<br>±2.83 | 61.47<br>±7.70 | 58.35<br>±3.47 | 67.02<br>±2.55 | 49.49<br>±3.18 |
| TopoImb [] | 50.61<br>±6.39 | 48.03<br>±5.90 | 57.41<br>±5.95 | 56.13<br>±4.61 | 49.52<br>±1.01 | 58.62<br>±6.52 | 58.63<br>±1.93 |
| DataDec [] | 54.23<br>±4.16 | 63.46<br>±4.36 | 67.25<br>±5.25 | 63.10<br>±2.62 | 58.20<br>±4.05 | 69.08<br>±4.49 | 69.03<br>±1.89 |
| ImGKB [] | 52.83<br>±5.45 | 53.97<br>±5.28 | 64.57<br>±9.42 | 64.93<br>±4.44 | 50.15<br>±0.39 | 50.29<br>±0.19 | 40.44<br>±11.33 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 43.84<br>±7.03 | 48.59<br>±9.57 | 54.01<br>±2.86 | 58.32<br>±1.51 | 49.06<br>±2.17 | 61.85<br>±3.89 | 53.81<br>±1.88 |
| G^2GNN [] | 47.86<br>±9.03 | 57.28<br>±1.85 | 69.42<br>±1.80 | 65.65<br>±5.41 | 53.11<br>±3.97 | 66.02<br>±2.08 | 54.57<br>±3.30 |
| TopoImb [] | 45.90<br>±6.41 | 40.71<br>±0.33 | 38.27<br>±5.28 | 44.63<br>±4.82 | 49.75<br>±4.81 | 54.35<br>±3.13 | 57.72<br>±1.71 |
| DataDec [] | 55.86<br>±2.49 | 63.28<br>±3.54 | 64.23<br>±7.74 | 64.66<br>±2.04 | 57.06<br>±5.97 | 66.45<br>±5.38 | 71.26<br>±0.91 |
| ImGKB [] | 49.49<br>±5.12 | 40.82<br>±0.02 | 68.44<br>±2.58 | 67.44<br>±3.50 | 47.65<br>±0.23 | 48.58<br>±2.15 | 51.21<br>±0.10 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 40.58<br>±7.61 | 43.03<br>±9.39 | 37.34<br>±3.35 | 42.48<br>±2.61 | 45.09<br>±0.18 | 54.39<br>±5.16 | 50.47<br>±0.38 |
| G^2GNN [] | 41.78<br>±7.61 | 49.50<br>±11.24 | 61.27<br>±6.39 | 44.59<br>±4.72 | 56.40<br>±1.71 | 65.08<br>±3.08 | 58.02<br>±3.29 |
| TopoImb [] | 40.17<br>±2.21 | 38.50<br>±0.35 | 33.21<br>±0.05 | 36.50<br>±1.44 | 46.18<br>±3.06 | 52.21<br>±3.56 | 61.40<br>±2.44 |
| DataDec [] | 55.41<br>±3.37 | 63.82<br>±6.75 | 66.08<br>±7.51 | 65.07<br>±2.40 | 58.58<br>±5.07 | 65.56<br>±8.61 | 70.48<br>±0.49 |
| ImGKB [] | 45.98<br>±8.71 | 38.34<br>±0.02 | 65.09<br>±2.81 | 58.21<br>±10.60 | 46.06<br>±2.74 | 51.23<br>±5.09 | 50.20<br>±0.06 |

**Table D.18: Balanced Accuracy score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 50.07<br>±0.23 | 50.00<br>±0.02 | 64.60<br>±2.26 | 62.63<br>±2.06 | 59.76<br>±1.78 | 66.65<br>±1.06 | 69.44<br>±2.08 |
| G^2GNN [] | 50.02<br>±0.06 | 51.82<br>±1.81 | 67.39<br>±1.76 | 60.38<br>±5.83 | 58.35<br>±3.47 | 67.02<br>±2.55 | 61.96<br>±0.90 |
| TopoImb [] | 53.71<br>±2.88 | 51.13<br>±1.64 | 61.24<br>±5.25 | 60.56<br>±2.30 | 49.71<br>±0.34 | 58.68<br>±6.48 | 44.78<br>±3.02 |
| DataDec [] | 54.36<br>±3.61 | 62.09<br>±3.25 | 63.92<br>±4.14 | 61.41<br>±2.42 | 58.11<br>±3.96 | 69.08<br>±4.38 | 62.12<br>±4.15 |
| ImGKB [] | 53.03<br>±3.56 | 49.98<br>±0.06 | 65.28<br>±5.36 | 62.84<br>±2.56 | 50.15<br>±0.39 | 50.29<br>±0.19 | 33.35<br>±0.01 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 49.69<br>±0.68 | 50.73<br>±2.05 | 59.49<br>±1.56 | 60.53<br>±1.43 | 51.35<br>±1.88 | 63.51<br>±3.57 | 37.97<br>±2.15 |
| G^2GNN [] | 49.73<br>±0.87 | 53.76<br>±2.16 | 68.31<br>±1.72 | 65.61<br>±2.52 | 53.84<br>±3.33 | 66.54<br>±2.09 | 61.19<br>±1.44 |
| TopoImb [] | 51.60<br>±3.14 | 49.98<br>±0.02 | 51.14<br>±2.23 | 54.87<br>±2.95 | 48.94<br>±4.07 | 56.51<br>±2.84 | 46.73<br>±0.87 |
| DataDec [] | 54.50<br>±1.74 | 59.94<br>±3.73 | 61.80<br>±4.57 | 62.01<br>±1.75 | 56.87<br>±5.73 | 67.02<br>±5.12 | 67.53<br>±2.03 |
| ImGKB [] | 51.70<br>±2.33 | 49.99<br>±0.02 | 67.46<br>±1.22 | 63.70<br>±3.66 | 50.14<br>±0.22 | 50.08<br>±0.16 | 33.34<br>±0.01 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 50.36<br>±1.14 | 50.30<br>±0.61 | 51.78<br>±1.94 | 53.22<br>±2.13 | 50.08<br>±0.16 | 58.47<br>±4.64 | 33.99<br>±0.32 |
| G^2GNN [] | 49.94<br>±1.47 | 50.31<br>±0.97 | 65.24<br>±4.47 | 54.99<br>±3.11 | 58.87<br>±1.18 | 65.09<br>±3.02 | 53.69<br>±3.41 |
| TopoImb [] | 50.78<br>±0.68 | 49.99<br>±0.02 | 50.01<br>±0.03 | 49.47<br>±1.20 | 51.02<br>±2.25 | 56.40<br>±2.67 | 46.42<br>±3.04 |
| DataDec [] | 53.28<br>±2.65 | 58.87<br>±3.26 | 63.07<br>±5.35 | 60.83<br>±2.61 | 58.11<br>±4.26 | 66.61<br>±6.89 | 67.66<br>±1.56 |
| ImGKB [] | 50.19<br>±3.07 | 49.99<br>±0.02 | 64.52<br>±4.98 | 60.22<br>±4.56 | 50.06<br>±0.31 | 50.26<br>±0.22 | 33.33<br>±0.01 |

**Table D.19: Macro-F1 score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 32.82<br>±3.29 | 34.45<br>±2.70 | 64.08<br>±2.43 | 62.02<br>±2.84 | 59.32<br>±2.48 | 67.58<br>±1.06 | 56.55<br>±4.31 |
| G^2GNN [] | 31.29<br>±2.68 | 45.92<br>±8.09 | 67.11<br>±2.26 | 56.99<br>±10.85 | 56.41<br>±7.64 | 65.63<br>±3.26 | 41.15<br>±4.18 |
| TopoImb [] | 45.01<br>±8.36 | 37.18<br>±7.96 | 56.62<br>±6.11 | 55.05<br>±4.87 | 33.04<br>±0.43 | 50.17<br>±12.11 | 40.73<br>±3.28 |
| DataDec [] | 53.24<br>±3.23 | 61.26<br>±4.55 | 64.05<br>±4.48 | 61.35<br>±2.55 | 54.26<br>±7.60 | 67.37<br>±6.20 | 62.14<br>±3.48 |
| ImGKB [] | 48.53<br>±8.31 | 35.15<br>±2.37 | 62.33<br>±11.90 | 62.34<br>±3.64 | 33.84<br>±0.60 | 33.97<br>±0.41 | 18.99<br>±3.59 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 31.49<br>±5.35 | 34.14<br>±7.63 | 53.81<br>±2.94 | 58.06<br>±1.46 | 36.70<br>±6.23 | 57.56<br>±6.17 | 42.17<br>±5.55 |
| G^2GNN [] | 33.06<br>±4.46 | 51.94<br>±5.20 | 67.58<br>±1.71 | 64.18<br>±4.21 | 45.81<br>±10.04 | 65.51<br>±2.39 | 47.61<br>±4.89 |
| TopoImb [] | 39.66<br>±9.73 | 28.90<br>±0.15 | 30.36<br>±7.82 | 40.50<br>±7.73 | 37.79<br>±5.88 | 45.50<br>±5.89 | 41.59<br>±1.32 |
| DataDec [] | 54.16<br>±1.97 | 57.35<br>±6.49 | 60.87<br>±6.00 | 61.94<br>±1.91 | 50.18<br>±11.79 | 64.62<br>±6.82 | 67.94<br>±1.44 |
| ImGKB [] | 45.80<br>±7.16 | 29.04<br>±0.10 | 66.63<br>±1.90 | 63.41<br>±4.10 | 32.52<br>±0.48 | 32.82<br>±1.24 | 22.58<br>±0.03 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 29.74<br>±6.39 | 31.00<br>±6.60 | 32.66<br>±5.33 | 40.59<br>±3.18 | 31.21<br>±0.36 | 47.46<br>±8.81 | 35.27<br>±2.66 |
| G^2GNN [] | 32.13<br>±7.08 | 34.53<br>±7.98 | 60.58<br>±5.98 | 42.79<br>±6.25 | 54.41<br>±2.63 | 64.77<br>±3.25 | 45.03<br>±5.63 |
| TopoImb [] | 32.03<br>±3.31 | 27.74<br>±0.17 | 24.89<br>±0.07 | 31.98<br>±1.84 | 33.79<br>±6.25 | 44.46<br>±6.18 | 42.64<br>±3.76 |
| DataDec [] | 52.48<br>±3.00 | 56.32<br>±7.38 | 62.23<br>±5.92 | 60.89<br>±2.60 | 53.87<br>±8.76 | 62.46<br>±11.54 | 67.68<br>±0.43 |
| ImGKB [] | 39.08<br>±8.03 | 27.76<br>±0.09 | 61.19<br>±7.33 | 55.46<br>±11.43 | 31.73<br>±0.22 | 34.27<br>±2.64 | 22.28<br>±0.02 |

**Table D.20: AUC-ROC score (% ± standard deviation) of graph classification on manipulated class-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold and the runner-ups are underlined.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| $\bm{\rho}=$ 1 (Balanced) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 49.33<br>±7.50 | 47.99<br>±6.53 | 67.82<br>±1.87 | 67.24<br>±2.12 | 63.97<br>±2.24 | 75.18<br>±0.08 | 82.29<br>±1.74 |
| G^2GNN [] | 45.43<br>±5.01 | 53.96<br>±1.98 | 70.27<br>±2.46 | 68.38<br>±3.80 | 61.49<br>±6.19 | 74.01<br>±3.96 | 76.39<br>±1.05 |
| TopoImb [] | 56.98<br>±4.51 | 57.57<br>±1.02 | 69.62<br>±6.65 | 70.29<br>±1.96 | 48.80<br>±10.38 | 77.48<br>±1.84 | 74.54<br>±1.33 |
| DataDec [] | 55.99<br>±4.78 | 69.51<br>±3.35 | 69.52<br>±7.69 | 66.85<br>±3.20 | 62.53<br>±3.42 | 66.49<br>±9.00 | 77.38<br>±4.14 |
| ImGKB [] | 53.61<br>±5.87 | 54.93<br>±1.84 | 72.75<br>±1.17 | 67.82<br>±1.50 | 51.83<br>±1.56 | 72.98<br>±5.95 | 49.92<br>±0.89 |
| $\bm{\rho}=$ 20 (Low) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 45.84<br>±4.13 | 61.32<br>±4.03 | 67.36<br>±1.94 | 65.26<br>±2.20 | 62.50<br>±1.26 | 75.19<br>±1.08 | 81.28<br>±1.49 |
| G^2GNN [] | 48.93<br>±5.12 | 54.45<br>±3.61 | 71.85<br>±1.86 | 71.03<br>±1.85 | 57.06<br>±4.74 | 73.96<br>±2.66 | 76.39<br>±1.05 |
| TopoImb [] | 55.07<br>±4.49 | 57.41<br>±1.16 | 72.43<br>±5.51 | 72.19<br>±3.37 | 50.00<br>±10.14 | 77.58<br>±0.54 | 77.08<br>±0.50 |
| DataDec [] | 56.27<br>±2.77 | 68.73<br>±2.50 | 67.18<br>±7.60 | 68.13<br>±2.14 | 64.08<br>±3.48 | 65.24<br>±11.34 | 87.01<br>±0.67 |
| ImGKB [] | 52.91<br>±3.96 | 54.52<br>±2.20 | 71.14<br>±3.19 | 68.34<br>±2.86 | 51.08<br>±0.71 | 76.70<br>±3.52 | 50.16<br>±0.94 |
| $\bm{\rho}=$ 100 (High) |  |  |  |  |  |  |  |
| GCN (bb.) [] | 44.65<br>±4.74 | 46.38<br>±5.76 | 65.59<br>±1.10 | 64.67<br>±1.98 | 56.60<br>±8.91 | 76.80<br>±2.42 | 77.77<br>±2.43 |
| G^2GNN [] | 46.82<br>±4.30 | 49.91<br>±1.64 | 68.51<br>±3.63 | 67.30<br>±2.70 | 62.46<br>±2.16 | 72.42<br>±3.79 | 70.81<br>±3.61 |
| TopoImb [] | 53.31<br>±5.12 | 56.71<br>±0.63 | 70.74<br>±4.14 | 57.78<br>±6.66 | 52.42<br>±10.28 | 77.07<br>±0.24 | 75.96<br>±0.51 |
| DataDec [] | 55.65<br>±3.63 | 68.13<br>±2.76 | 69.26<br>±8.47 | 67.68<br>±2.86 | 63.17<br>±4.96 | 64.92<br>±15.31 | 87.21<br>±0.35 |
| ImGKB [] | 51.01<br>±4.09 | 53.74<br>±0.93 | 70.71<br>±1.27 | 65.42<br>±3.01 | 51.05<br>±1.00 | 71.01<br>±5.58 | 50.01<br>±0.58 |

##### D.1.5 Performance of Graph-Level Topology-Imbalanced Algorithms

**Table D.21: Accuracy score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GIN (bb.) [] | 52.17<br>±4.36 | 54.96<br>±1.00 | 63.58<br>±1.76 | 65.01<br>±0.69 | 66.38<br>±4.27 | 67.41<br>±2.32 | 64.34<br>±3.55 |
| SOLT-GNN [] | 47.54<br>±4.33 | 59.98<br>±1.11 | 65.56<br>±4.83 | 63.78<br>±1.06 | 64.20<br>±5.46 | 49.57<br>±6.78 | 61.79<br>±2.09 |
| TopoImb [] | 49.71<br>±1.98 | 53.13<br>±0.45 | 61.19<br>±4.61 | 65.16<br>±1.76 | 66.00<br>±2.41 | 69.47<br>±3.70 | 62.71<br>±2.42 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GIN (bb.) [] | 51.38<br>±6.78 | 54.82<br>±2.26 | 62.14<br>±2.43 | 61.46<br>±2.43 | 65.08<br>±5.78 | 68.32<br>±1.77 | 65.84<br>±3.12 |
| SOLT-GNN [] | 53.04<br>±3.91 | 68.71<br>±1.60 | 71.95<br>±2.36 | 63.33<br>±1.86 | 69.38<br>±1.23 | 73.51<br>±1.14 | 69.69<br>±2.45 |
| TopoImb [] | 51.59<br>±4.30 | 54.52<br>±0.87 | 64.03<br>±4.43 | 65.99<br>±1.25 | 68.10<br>±0.87 | 71.54<br>±0.75 | 68.68<br>±1.34 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GIN (bb.) [] | 48.41<br>±7.07 | 53.99<br>±7.96 | 58.00<br>±4.19 | 60.68<br>±6.89 | 62.60<br>±3.82 | 67.41<br>±2.23 | 67.05<br>±2.46 |
| SOLT-GNN [] | 51.74<br>±5.25 | 67.88<br>±2.37 | 72.04<br>±2.18 | 64.97<br>±3.24 | 65.03<br>±4.12 | 60.24<br>±2.11 | 67.12<br>±3.28 |
| TopoImb [] | 51.96<br>±1.16 | 56.32<br>±0.61 | 54.89<br>±13.58 | 64.16<br>±2.96 | 66.75<br>±0.91 | 69.14<br>±4.83 | 67.52<br>±0.77 |

**Table D.22: Balanced Accuracy score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GIN (bb.) [] | 51.08<br>±2.07 | 55.22<br>±1.39 | 59.76<br>±1.78 | 63.46<br>±0.92 | 66.38<br>±4.27 | 67.41<br>±2.32 | 64.73<br>±5.42 |
| SOLT-GNN [] | 45.47<br>±2.10 | 63.58<br>±0.82 | 66.60<br>±3.25 | 62.58<br>±0.61 | 64.20<br>±5.46 | 49.57<br>±6.78 | 70.23<br>±1.56 |
| TopoImb [] | 50.07<br>±2.77 | 54.44<br>±0.41 | 63.87<br>±1.68 | 67.24<br>±1.53 | 66.00<br>±2.41 | 69.47<br>±3.70 | 71.56<br>±1.68 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GIN (bb.) [] | 49.83<br>±1.30 | 54.43<br>±2.04 | 56.84<br>±2.54 | 62.22<br>±0.98 | 65.08<br>±5.78 | 68.32<br>±1.77 | 74.40<br>±1.72 |
| SOLT-GNN [] | 50.06<br>±0.75 | 69.36<br>±0.87 | 70.88<br>±1.67 | 59.61<br>±3.40 | 69.38<br>±1.23 | 73.51<br>±1.14 | 75.86<br>±1.12 |
| TopoImb [] | 50.88<br>±2.36 | 54.60<br>±1.03 | 59.45<br>±4.27 | 65.25<br>±2.43 | 68.10<br>±0.87 | 71.54<br>±0.75 | 76.54<br>±0.54 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GIN (bb.) [] | 50.20<br>±0.69 | 53.65<br>±3.89 | 55.82<br>±1.76 | 61.43<br>±2.36 | 62.60<br>±3.82 | 67.41<br>±2.23 | 74.99<br>±0.95 |
| SOLT-GNN [] | 48.02<br>±1.77 | 67.98<br>±2.19 | 71.07<br>±2.22 | 60.75<br>±6.03 | 65.03<br>±4.12 | 60.24<br>±2.11 | 73.58<br>±2.12 |
| TopoImb [] | 52.07<br>±0.96 | 56.84<br>±0.41 | 55.47<br>±5.17 | 66.48<br>±1.89 | 66.75<br>±0.91 | 69.14<br>±4.83 | 76.10<br>±0.32 |

**Table D.23: Micro-F1 score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GIN (bb.) [] | 48.26<br>±3.11 | 54.63<br>±0.98 | 59.67<br>±1.87 | 63.39<br>±0.84 | 65.67<br>±5.40 | 66.14<br>±1.90 | 58.45<br>±1.80 |
| SOLT-GNN [] | 43.63<br>±1.91 | 58.54<br>±1.50 | 64.60<br>±4.66 | 62.34<br>±0.66 | 63.66<br>±5.94 | 49.17<br>±6.76 | 59.76<br>±1.81 |
| TopoImb [] | 48.87<br>±2.90 | 53.07<br>±0.49 | 59.94<br>±4.32 | 64.97<br>±1.65 | 65.71<br>±2.62 | 69.15<br>±3.83 | 60.91<br>±2.15 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GIN (bb.) [] | 38.58<br>±5.97 | 50.50<br>±5.43 | 56.46<br>±2.90 | 60.89<br>±1.84 | 63.28<br>±9.06 | 67.20<br>±2.32 | 63.79<br>±2.55 |
| SOLT-GNN [] | 43.20<br>±5.36 | 68.52<br>±1.49 | 70.58<br>±2.03 | 58.67<br>±4.91 | 68.73<br>±1.97 | 73.24<br>±1.40 | 66.96<br>±1.86 |
| TopoImb [] | 49.17<br>±0.95 | 54.25<br>±0.91 | 59.03<br>±4.35 | 64.65<br>±1.76 | 67.98<br>±0.95 | 71.52<br>±0.75 | 66.58<br>±1.09 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GIN (bb.) [] | 34.56<br>±6.32 | 43.71<br>±10.57 | 53.48<br>±2.03 | 57.98<br>±5.51 | 59.75<br>±6.69 | 66.20<br>±2.77 | 64.92<br>±2.18 |
| SOLT-GNN [] | 40.70<br>±3.27 | 67.54<br>±2.28 | 70.70<br>±2.20 | 58.50<br>±10.48 | 64.53<br>±4.68 | 54.80<br>±3.23 | 64.68<br>±2.81 |
| TopoImb [] | 51.65<br>±1.07 | 56.18<br>±0.53 | 44.79<br>±14.19 | 63.97<br>±2.78 | 66.67<br>±0.91 | 68.41<br>±5.34 | 65.65<br>±0.63 |

**Table D.24: AUC-ROC score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GIN (bb.) [] | 51.36<br>±2.71 | 57.38<br>±1.46 | 60.17<br>±2.84 | 66.09<br>±0.71 | 71.34<br>±4.89 | 78.51<br>±9.44 | 77.46<br>±2.90 |
| SOLT-GNN [] | 45.70<br>±3.17 | 72.90<br>±0.24 | 70.79<br>±7.53 | 68.55<br>±0.93 | 71.29<br>±6.08 | 48.18<br>±7.14 | 82.66<br>±1.17 |
| TopoImb [] | 49.33<br>±1.90 | 55.80<br>±0.30 | 71.26<br>±3.18 | 73.92<br>±3.23 | 72.37<br>±2.68 | 65.86<br>±4.55 | 82.06<br>±1.77 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GIN (bb.) [] | 48.84<br>±2.20 | 54.01<br>±8.26 | 53.62<br>±7.67 | 67.45<br>±0.86 | 68.30<br>±6.16 | 78.44<br>±2.37 | 86.00<br>±1.23 |
| SOLT-GNN [] | 50.40<br>±2.91 | 75.83<br>±0.29 | 76.11<br>±2.55 | 68.57<br>±2.72 | 76.53<br>±1.52 | 76.14<br>±4.50 | 87.51<br>±0.66 |
| TopoImb [] | 52.09<br>±1.56 | 55.67<br>±1.09 | 63.96<br>±8.30 | 72.48<br>±2.37 | 73.33<br>±2.00 | 74.96<br>±1.51 | 88.27<br>±0.10 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GIN (bb.) [] | 49.85<br>±1.83 | 56.40<br>±9.37 | 52.96<br>±7.75 | 70.66<br>±0.82 | 69.92<br>±3.25 | 75.86<br>±5.42 | 85.97<br>±0.28 |
| SOLT-GNN [] | 47.82<br>±3.75 | 73.62<br>±1.58 | 76.43<br>±2.46 | 73.57<br>±5.28 | 70.85<br>±5.29 | 43.84<br>±5.55 | 85.61<br>±1.65 |
| TopoImb [] | 52.26<br>±1.24 | 58.29<br>±0.54 | 61.66<br>±10.19 | 73.84<br>±1.92 | 72.55<br>±1.25 | 69.04<br>±9.48 | 87.96<br>±0.71 |

**Table D.25: Accuracy score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GCN (bb.) [] | 51.59<br>±7.07 | 50.53<br>±0.87 | 65.33<br>±1.85 | 64.82<br>±0.75 | 69.15<br>±1.44 | 53.44<br>±1.78 | 64.29<br>±1.42 |
| SOLT-GNN [] | 51.45<br>±3.13 | 59.25<br>±0.91 | 65.24<br>±4.77 | 65.69<br>±2.36 | 68.23<br>±2.48 | 37.58<br>±3.04 | 63.82<br>±2.64 |
| TopoImb [] | 46.74<br>±1.57 | 54.36<br>±0.48 | 59.73<br>±5.13 | 56.18<br>±2.10 | 68.20<br>±0.70 | 56.94<br>±3.23 | 60.47<br>±0.91 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GCN (bb.) [] | 50.00<br>±5.87 | 50.10<br>±2.55 | 64.32<br>±2.81 | 63.99<br>±2.16 | 67.95<br>±2.82 | 67.96<br>±0.89 | 67.64<br>±2.04 |
| SOLT-GNN [] | 56.23<br>±0.84 | 66.42<br>±1.37 | 68.91<br>±1.89 | 62.78<br>±1.33 | 70.25<br>±1.15 | 61.95<br>±5.55 | 66.94<br>±3.67 |
| TopoImb [] | 54.13<br>±4.62 | 55.38<br>±0.90 | 49.72<br>±13.46 | 64.73<br>±7.09 | 68.75<br>±0.76 | 69.12<br>±0.52 | 66.48<br>±1.03 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GCN (bb.) [] | 49.93<br>±5.90 | 51.12<br>±1.01 | 58.02<br>±5.02 | 60.98<br>±6.71 | 64.88<br>±2.02 | 66.38<br>±0.46 | 68.99<br>±1.36 |
| SOLT-GNN [] | 54.78<br>±6.03 | 68.26<br>±0.28 | 67.38<br>±2.89 | 63.21<br>±3.40 | 69.80<br>±2.07 | 67.05<br>±2.54 | 65.57<br>±5.59 |
| TopoImb [] | 51.81<br>±1.26 | 55.20<br>±0.59 | 54.31<br>±13.19 | 69.66<br>±1.92 | 66.60<br>±0.91 | 69.09<br>±1.00 | 67.74<br>±0.63 |

**Table D.26: Balanced Accuracy score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GCN (bb.) [] | 50.47<br>±0.75 | 52.46<br>±0.50 | 61.92<br>±2.38 | 63.13<br>±0.43 | 69.15<br>±1.44 | 53.44<br>±1.78 | 70.14<br>±1.68 |
| SOLT-GNN [] | 48.24<br>±1.20 | 63.10<br>±0.74 | 61.76<br>±3.57 | 63.81<br>±1.86 | 68.23<br>±2.48 | 37.58<br>±3.04 | 69.49<br>±0.19 |
| TopoImb [] | 50.43<br>±0.87 | 55.53<br>±0.61 | 62.18<br>±2.05 | 57.64<br>±0.94 | 68.20<br>±0.70 | 56.94<br>±3.23 | 69.51<br>±0.91 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GCN (bb.) [] | 49.74<br>±2.52 | 50.83<br>±0.66 | 61.89<br>±1.10 | 58.27<br>±4.65 | 67.95<br>±2.82 | 67.96<br>±0.89 | 76.18<br>±0.89 |
| SOLT-GNN [] | 51.13<br>±0.79 | 66.62<br>±1.36 | 67.58<br>±2.10 | 59.12<br>±2.47 | 70.25<br>±1.15 | 61.95<br>±5.55 | 74.88<br>±1.59 |
| TopoImb [] | 54.34<br>±3.22 | 54.62<br>±1.00 | 54.47<br>±6.12 | 64.63<br>±3.42 | 68.75<br>±0.76 | 69.12<br>±0.52 | 74.87<br>±0.87 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GCN (bb.) [] | 49.96<br>±0.54 | 52.43<br>±1.04 | 52.66<br>±2.17 | 57.58<br>±4.32 | 64.88<br>±2.02 | 66.38<br>±0.46 | 66.80<br>±1.08 |
| SOLT-GNN [] | 51.11<br>±1.15 | 68.06<br>±0.41 | 66.34<br>±2.08 | 60.94<br>±1.68 | 69.80<br>±2.07 | 67.05<br>±2.54 | 74.16<br>±2.63 |
| TopoImb [] | 52.12<br>±0.78 | 55.50<br>±1.13 | 55.34<br>±5.76 | 66.63<br>±4.54 | 66.60<br>±0.91 | 69.09<br>±1.00 | 75.02<br>±0.79 |

**Table D.27: Macro-F1 score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GCN (bb.) [] | 36.72<br>±5.58 | 50.16<br>±1.26 | 62.08<br>±2.40 | 63.09<br>±0.46 | 69.02<br>±1.52 | 49.68<br>±8.19 | 61.44<br>±1.38 |
| SOLT-GNN [] | 45.00<br>±3.14 | 57.49<br>±1.18 | 61.41<br>±4.07 | 63.82<br>±2.01 | 67.88<br>±2.35 | 35.00<br>±2.77 | 61.07<br>±1.80 |
| TopoImb [] | 44.72<br>±2.61 | 54.31<br>±0.49 | 58.67<br>±6.03 | 55.77<br>±1.91 | 67.78<br>±1.00 | 56.09<br>±3.68 | 58.79<br>±1.01 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GCN (bb.) [] | 40.94<br>±5.67 | 48.11<br>±3.33 | 61.59<br>±1.64 | 54.22<br>±8.96 | 67.80<br>±2.84 | 67.18<br>±1.39 | 65.45<br>±1.75 |
| SOLT-GNN [] | 45.63<br>±4.84 | 66.16<br>±1.30 | 67.16<br>±2.03 | 58.14<br>±3.23 | 70.05<br>±1.19 | 57.57<br>±8.59 | 64.70<br>±3.08 |
| TopoImb [] | 51.99<br>±3.88 | 54.34<br>±0.88 | 40.81<br>±15.22 | 62.10<br>±6.59 | 68.64<br>±0.77 | 69.10<br>±0.49 | 64.49<br>±0.93 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GCN (bb.) [] | 39.32<br>±7.82 | 50.84<br>±1.33 | 51.29<br>±1.10 | 52.46<br>±8.79 | 63.65<br>±3.15 | 65.91<br>±0.31 | 66.80<br>±1.08 |
| SOLT-GNN [] | 39.57<br>±6.16 | 67.89<br>±0.33 | 65.88<br>±2.46 | 60.32<br>±2.31 | 69.54<br>±2.16 | 65.40<br>±3.77 | 63.70<br>±4.83 |
| TopoImb [] | 51.43<br>±0.98 | 54.99<br>±0.81 | 44.51<br>±14.79 | 65.66<br>±5.28 | 66.54<br>±0.89 | 68.76<br>±1.17 | 65.56<br>±0.52 |

**Table D.28: AUC-ROC score (% ± standard deviation) of graph classification on manipulated topology-imbalanced graph datasets with changing imbalance levels over 10 runs. “—” denotes out of memory or time limit. The best results are shown in bold.**
| Algorithm | PTC-MR | FRANKENSTEIN | PROTEINS | D&D | IMDB-B | REDDIT-B | COLLAB |
| --- | --- | --- | --- | --- | --- | --- | --- |
| Imbalance Ratio: Low |  |  |  |  |  |  |  |
| GCN (bb.) [] | 50.81<br>±2.98 | 53.52<br>±0.69 | 62.80<br>±5.19 | 64.25<br>±0.94 | 74.69<br>±1.04 | 50.48<br>±13.45 | 81.81<br>±0.88 |
| SOLT-GNN [] | 46.36<br>±0.64 | 73.17<br>±0.36 | 59.26<br>±6.01 | 65.61<br>±1.44 | 74.16<br>±1.36 | 32.50<br>±5.56 | 80.89<br>±1.27 |
| TopoImb [] | 52.94<br>±0.50 | 56.71<br>±0.57 | 67.71<br>±4.70 | 60.66<br>±1.62 | 74.55<br>±1.80 | 63.78<br>±2.65 | 82.67<br>±0.42 |
| Imbalance Ratio: Mid |  |  |  |  |  |  |  |
| GCN (bb.) [] | 50.03<br>±4.80 | 51.66<br>±0.64 | 62.02<br>±1.93 | 61.45<br>±4.93 | 74.23<br>±3.12 | 74.51<br>±2.91 | 87.46<br>±0.79 |
| SOLT-GNN [] | 52.54<br>±0.92 | 72.48<br>±1.32 | 71.33<br>±2.35 | 59.75<br>±4.06 | 78.21<br>±2.21 | 66.93<br>±6.74 | 86.46<br>±0.45 |
| TopoImb [] | 57.29<br>±2.45 | 56.98<br>±1.58 | 65.74<br>±3.16 | 74.47<br>±2.44 | 74.30<br>±0.66 | 77.25<br>±0.41 | 86.74<br>±0.85 |
| Imbalance Ratio: High |  |  |  |  |  |  |  |
| GCN (bb.) [] | 51.12<br>±1.94 | 52.85<br>±2.56 | 47.22<br>±5.45 | 65.50<br>±6.38 | 68.31<br>±3.07 | 73.41<br>±0.82 | 87.56<br>±0.44 |
| SOLT-GNN [] | 49.47<br>±4.36 | 73.27<br>±0.46 | 69.84<br>±3.01 | 64.79<br>±0.57 | 78.04<br>±1.14 | 72.92<br>±1.77 | 86.77<br>±1.65 |
| TopoImb [] | 53.65<br>±2.72 | 57.66<br>±0.95 | 63.26<br>±12.24 | 74.37<br>±3.19 | 71.84<br>±1.07 | 75.52<br>±1.17 | 88.42<br>±0.13 |

#### D.2 Additional Results for Algorithm Robustness (RQ2)

##### D.2.1 Robustness of Node-Level Class-Imbalanced Algorithms

Figure: Figure D.1: Generalizability analysis of the node-level algorithms under different class-imbalance degrees on Cora (homophilic). Results are reported with the algorithm performance (Accuracy) and its relative decrease (%) compared to the class-balanced data split (the green bar).
Refer to caption: /html/2406.09870/assets/x21.png

Figure: Figure D.2: Generalizability analysis of the node-level algorithms under different class-imbalance degrees on CiteSeer (homophilic). Results are reported with the algorithm performance (Accuracy) and its relative decrease (%) compared to the class-balanced data split (the green bar).
Refer to caption: /html/2406.09870/assets/x22.png

Figure: Figure D.3: Generalizability analysis of the node-level algorithms under different class-imbalance degrees on Chameleon (heterophilic). Results are reported with the algorithm performance (Accuracy) and its relative decrease (%) compared to the class-balanced data split (the green bar).
Refer to caption: /html/2406.09870/assets/x23.png

Figure: Figure D.4: Generalizability analysis of the node-level algorithms under different class-imbalance degrees on Squirrel (heterophilic). Results are reported with the algorithm performance (Accuracy) and its relative decrease (%) compared to the class-balanced data split (the green bar).
Refer to caption: /html/2406.09870/assets/x24.png

##### D.2.2 Robustness of Node-Level Local Topology-Imbalanced Algorithms

Figure: Figure D.5: Robustness analysis of the node-level algorithms under different local topology-imbalance degrees (Low, Mid, and High). Results are reported with the algorithm performance (Accuracy) with the standard deviation error area.
Refer to caption: /html/2406.09870/assets/x25.png

##### D.2.3 Robustness of Node-Level Global Topology-Imbalanced Algorithms

Figure: Figure D.6: Robustness analysis of the node-level algorithms under different global topology-imbalance degrees (Low, Mid, and High). Results are reported with the algorithm performance (Accuracy) with the standard deviation error area.
Refer to caption: /html/2406.09870/assets/x26.png

##### D.2.4 Robustness of Graph-Level Topology-Imbalanced Algorithms

Figure: Figure D.7: Robustness analysis of the graph-level algorithms under different class-imbalance degrees (Low, Mid, and High). Results are reported with the algorithm performance (Accuracy) with the standard deviation error area.
Refer to caption: /html/2406.09870/assets/x27.png

##### D.2.5 Robustness of Graph-Level Topology-Imbalanced Algorithms

Figure: Figure D.8: Robustness analysis of the graph-level algorithms under different topology-imbalance degrees (Low, Mid, and High). Results are reported with the algorithm performance (Accuracy) with the standard deviation error area.
Refer to caption: /html/2406.09870/assets/x28.png

#### D.3 Additional Results for Visualizations (RQ3)

##### D.3.1 Visualizations of Node-Level Class-Imbalanced Algorithms

Figure: Figure D.9: Visualizations of the embedding for node-level class-imbalanced algorithms.
Refer to caption: /html/2406.09870/assets/x29.png

##### D.3.2 Visualizations of Node-Level Local Topology-Imbalanced Algorithms

Figure: Figure D.10: Visualizations of the embedding for node-level local topology-imbalanced algorithms.
Refer to caption: /html/2406.09870/assets/x40.png

##### D.3.3 Visualizations of Node-Level Global Topology-Imbalanced Algorithms

Figure: Figure D.11: Visualizations of the embedding for node-level global topology-imbalanced algorithms.
Refer to caption: /html/2406.09870/assets/x48.png

##### D.3.4 Visualizations of Graph-Level Class-Imbalanced Algorithms

Figure: Figure D.12: Visualizations of the embedding for graph-level class-imbalanced algorithms.
Refer to caption: /html/2406.09870/assets/x54.png

##### D.3.5 Visualizations of Graph-Level Topology-Imbalanced Algorithms

Figure: Figure D.13: Visualizations of the embedding for global-level topology-imbalanced algorithms.
Refer to caption: /html/2406.09870/assets/x58.png

#### D.4 Additional Results for Efficiency Analysis (RQ4)

##### D.4.1 Efficiency Analysis of Node-Level Class-Imbalanced Algorithms

Figure: Figure D.14: Time and space analysis of node-level class-imbalanced IGL algorithms on Actor.
Refer to caption: /html/2406.09870/assets/x61.png

Figure: Figure D.15: Time and space analysis of node-level class-imbalanced IGL algorithms on ogbn-arXiv.
Refer to caption: /html/2406.09870/assets/x62.png

##### D.4.2 Efficiency Analysis of Node-Level Local Topology-Imbalanced Algorithms

Figure: Figure D.16: Time and space analysis of node-level local topology-imbalanced IGL algorithms on Actor.
Refer to caption: /html/2406.09870/assets/x63.png

Figure: Figure D.17: Time and space analysis of node-level local topology-imbalanced IGL algorithms on ogbn-arXiv.
Refer to caption: /html/2406.09870/assets/x64.png

##### D.4.3 Efficiency Analysis of Node-Level Global Topology-Imbalanced Algorithms

Figure: Figure D.18: Time and space analysis of node-level global topology-imbalanced IGL algorithms on Actor.
Refer to caption: /html/2406.09870/assets/x65.png

Figure: Figure D.19: Time and space analysis of node-level global topology-imbalanced IGL algorithms on ogbn-arXiv.
Refer to caption: /html/2406.09870/assets/x66.png

##### D.4.4 Efficiency Analysis of Graph-Level Class-Imbalanced Algorithms

Figure: Figure D.20: Time and space analysis of graph-level class-imbalanced IGL algorithms on COLLAB.
Refer to caption: /html/2406.09870/assets/x67.png

##### D.4.5 Efficiency Analysis of Graph-Level Topology-Imbalanced Algorithms

Figure: Figure D.21: Time and space analysis of graph-level topology-imbalanced IGL algorithms on COLLAB.
Refer to caption: /html/2406.09870/assets/x68.png

### Appendix E Package and Reproducibility

Figure: Figure E.1: The package structure of IGL-Bench, which mainly consists of four modules.
Refer to caption: /html/2406.09870/assets/x69.png

Figure: Figure E.2: The IGL-Bench package.
Refer to caption: /html/2406.09870/assets/x70.png

Package.
We established and released a comprehensive Imbalanced Graph Learning Benchmark (IGL-Bench) package, which serves as the first open-sourced(^5^55[https://github.com/RingBDStack/IGL-Bench](https://github.com/RingBDStack/IGL-Bench)) benchmark for graph-specific imbalanced learning to the best of our knowledge.
IGL-Bench encompasses 24 state-of-the-art IGL algorithms and 16 diverse graph datasets covering node-level and graph-level tasks, addressing class- and topology-imbalance issues, while also adopting consistent data processing and splitting approaches for fair comparisons over multiple metrics with different focus.

As shown in Figure [E.1](#A5.F1), the IGL-Bench package is mainly composed of four modules. ❶ The Imbalance Manipulator module performs different types of imbalance manipulations for the imbalance ratio on the built-in 16 node-level datasets, graph-level datasets, or user-defined datasets according to user configurations. ❷ The IGL Algorithms module has 24 state-of-the-art algorithms built-in and also supports calling user-defined IGL algorithms. ❸ The GNN Backbones module supports a variety of mainstream GNNs and also allows for user-defined GNNs. ❹ The Package Utils module offers a variety of utility tools, enhancing the usability and benchmarking efficiency of the package.

Documentation and Uses.
We have made a concerted effort to provide users with comprehensive documentation to ensure the seamless use of the package. Additionally, we have included necessary comments to enhance code readability. We supply the required configuration files to reproduce the experimental results, which also serve as examples of how to use the package effectively.

License.
Our package (codes and datasets) is licensed under the MIT License. This license permits users to freely use, copy, modify, merge, publish, distribute, sublicense, and sell copies of the software, provided that the original copyright notice and permission notice are included in all copies or substantial portions of the software. The MIT License is widely accepted for its simplicity and permissive terms, ensuring ease of use and contribution to the codes and datasets. We bear all responsibility in case of violation of rights, etc, and confirmation of the data license.

Code Maintenance.
We are committed to continuously updating our code and actively addressing users’ issues and feedback. Additionally, we warmly welcome community contributions to enhance our library and benchmark algorithms. Nonetheless, we will enforce strict version control measures to ensure reproducibility throughout the maintenance process.

### Appendix F Further Discussions

#### F.1 Related Works

To the best of our knowledge, there exists no established benchmark specifically dedicated to evaluating imbalanced learning on graphs. Our IGL-Bench represents the foundational effort in this domain, encompassing both node-level and graph-level challenges related to class- and topology-imbalance. This section compares and contextualizes our contributions within the broader landscape of imbalanced graph learning. We position our work in relation to notable surveys in the field.

[] comprehensively reviews the landscape of imbalanced learning on graphs, outlining key terminologies and taxonomies related to problem types and solution strategies. It establishes a foundational understanding crucial for addressing skewed data distributions in graph-based tasks.

Focused on the challenges of GNNs in practical applications, [] addresses issues such as imbalance in data distribution and the robustness against noise, privacy concerns, and out-of-distribution scenarios. It highlights solutions that enhance the reliability of GNNs in real-world settings.

[] specifically explores class-imbalanced learning on graphs, emphasizing the integration of graph representation learning with imbalanced learning techniques. It provides a taxonomy of existing approaches and outlines future directions in the evolving field of graph class-imbalanced learning.

In contrast to these surveys, our IGL-Bench offers a practical benchmarking package tailored explicitly for imbalanced graph learning. By systematically evaluating the performance of algorithms across various imbalance types, IGL-Bench provides a standardized package for assessing the efficacy and robustness of existing and future methods in this emerging field. While existing surveys establish the theoretical underpinnings and methodological approaches in imbalanced learning on graphs, IGL-Bench offers a concrete tool for empirical validation and comparison. This practical focus enables researchers and practitioners to not only understand the theoretical aspects but also to apply and benchmark algorithms effectively across diverse real-world graph datasets.

In summary, our work fills a critical gap by introducing IGL-Bench as the first benchmarking suite tailored for imbalanced graph learning, thereby advancing the state-of-the-art in the field and fostering deeper insights into the challenges and opportunities of imbalanced graph data analysis.

#### F.2 Limitations

IGL-Bench  has some limitations that we aim to address in future work.

❶ We hope to include a broader range of datasets to evaluate algorithms in different scenarios. Our current datasets are predominantly homogeneous graphs, which do not fully capture the diversity and complexity of real-world networks. Many IGL methods struggle with complex graph types, such as heterogeneous graphs with multiple types of nodes and edges. Including such datasets would provide a more robust evaluation of these algorithms and highlight their strengths and weaknesses.

❷ We hope to implement more IGL algorithms for various tasks, such as few-shot classification, dynamic graph learning, and anomaly detection, etc Our current benchmark is limited to a specific set of tasks, which might not reflect the full potential and versatility of IGL methods. By expanding the range of tasks, we can gain a deeper understanding of the progress in the field and provide insights into how different algorithms perform across diverse applications.

❸ Due to resource constraints and the availability of implementations, we could not include some of the latest state-of-the-art IGL algorithms in our benchmark. This might impact the comprehensiveness of our evaluation, as some promising methods are not represented. We aim to address this by continuously updating our package and incorporating these algorithms as they become available.

❹ Our current evaluation framework primarily focuses on the performance metrics of the algorithms. However, practical aspects such as scalability, computational efficiency, and memory usage are also crucial for real-world applications. We plan to include these factors in future evaluations to provide a more holistic view of each algorithm’s practicality and efficiency.

We will continuously update our repository to keep track of the latest advances in the field. We are also open to any suggestions and contributions that will improve the usability and effectiveness of our benchmark, ensuring it remains a valuable resource for the IGL research community.

#### F.3 Dataset Privacy and Ethics

We ensured all datasets were sourced from publicly available repositories with explicit research permissions. For user-generated or social platform data, we rely on terms including research consent. We anonymized Personally Identifiable Information (PII) and screened for offensive content, though complete risk elimination remains challenging. Users are urged to use datasets responsibly, mindful of ethical implications.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: - Can the authors elaborate on the specific challenges encountered in standardizing data splits and evaluation protocols across such a diverse set of IGL methods?
- How does IGL-Bench handle algorithm hyperparameter tuning, particularly for methods that might be sensitive to different types of imbalance?
- Are there future plans to study the scalability within IGL-Bench, e.g., for larger, more complex graph datasets?
soundness: 3
strengths: - Originality: The paper introduces a comprehensive benchmark for IGL to fill the gap in graph learning.
- Quality: Experiments valiadate the quality of the benchmark.
- Clarity: The paper is well written and organized. Easy for general audience to follow.
- Significance: The benchmark provides an easy platform for developing or comparing IGL methods, especially as graph learning expands into real-world, imbalanced datasets.
summary: This paper addresses the gap in graph learning by introducing a benchmark named IGL-Bench for imbalanced graph learning. The benchmark covers 24 algorithms across 17 datasets, tackling node-level and graph-level tasks that are affected by class and topology imbalances. The benchmark includes standardized data processing, evaluation protocols, and metrics across different datasets. Evaluation on effectiveness, robustness, boundary clarity, and efficiency of IGL methods under imbalanced conditions are further carried out. The benchmark findings reveal key insights into the strengths and limitations of current IGL algorithms, particularly around scalability, robustness, and their dependency on graph topology properties.
weaknesses: - Complex visualizations: Certain visualizations, such as multi-metric plots across multiple imbalance ratios, could benefit from clearer explanations to aid interpretability for readers less familiar with the metrics.
- New dataset: No new dataset is introduced in the paper.

---

confidence: 3
contribution: 3
initial_rating: 8
presentation: 3
questions: See Weakness.
soundness: 3
strengths: 1. Benchmarking imbalanced graph learning is important to track progress in the research community.
2. The four research questions posed are relevant and of interest to the community.
3. The paper is well-written and easy to follow.
4. The experiments are thorough and well-designed. The availability of open-source code enhances reproducibility and accessibility.
summary: This work presents a benchmark for imbalanced graph learning, encompassing 17 graph datasets and 24 imbalance-handling algorithms, along with a unified data processing pipeline, splitting strategy, and evaluation protocols. The benchmark addresses questions related to effectiveness in handling imbalance, robustness across different imbalance ratios, and efficiency in terms of time and space for both node-level and graph-level tasks. Additionally, an open-source codebase is provided to facilitate reproducible evaluations.
weaknesses: 1. For node-level class-imbalanced algorithms, it would be beneficial to include traditional methods for addressing class imbalance, such as reweighting or PC Softmax [1], to provide a comprehensive comparison. Additionally, reporting per-class F1 scores could offer more insights into model performance across majority and minority classes, enabling a more detailed analysis of effectiveness.

2. Some findings lack depth and do not offer clear insights. For instance, the observation that most algorithms perform poorly on the large-scale ogbn-arXiv dataset is presented without an explanation. It would be valuable to investigate and discuss the reasons for this poor performance, especially through additional experiments.

3. In Section 4.4, which assesses the efficiency of different models, the experiments are conducted on the Cora dataset, the smallest of the datasets used. This setup makes the time and space usage of the algorithms highly dependent on implementation details rather than their inherent algorithmic complexity. While the Appendix includes results for the ogbn-arXiv dataset, they cover only a subset of models, as other models encountered memory limitations. A theoretical analysis of the algorithms' complexities would provide a more meaningful comparison of their efficiency. Relying solely on runtime measurements can be misleading, as they may be influenced by implementation optimizations and do not necessarily reflect the algorithms' underlying efficiency.

4. On the ogbn-arXiv dataset, certain resampling algorithms, such as GraphENS and GraphSHA, run successfully, whereas others, like GraphSMOTE, encounter memory issues. It is unclear whether this is due to differences in algorithmic complexity or specific implementation choices. Given the similarity of these resampling approaches, clarifying whether the issue arises from inherent algorithm characteristics or particular implementation choices would be helpful.

[1] Disentangling label distribution for long-tailed visual recognition. CVPR. 2021.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: 1.	 How does the benchmark incorporate, or plan to incorporate, recent advances in IGL (see weaknesses), and evaluate whether these general approaches improve performance, robustness, and other metrics?
2.	Are there any plans to provide an API reference for IGL-bench? This would significantly enhance usability.
soundness: 3
strengths: -	The proposed IGL-Bench is well-constructed, it can provide a standardized testbed for future work, encouraging a more consistent evaluation process for IGL.
-	The paper is well-written and easy to follow. The authors' thorough analysis of the benchmarking results leads to interesting insights.
summary: This paper introduces a benchmark for Imbalanced Graph Learning (IGL). IGL-Bench offers a unified framework for evaluating 24 IGL algorithms across 17 datasets, addressing both class- and topology-imbalance at node and graph levels. The authors conduct a rigorous evaluation on effectiveness, robustness, and efficiency, providing a comparative analysis of existing methods. Additionally, the paper presents an open-source package to facilitate reproducible research and encourage further development in the IGL field.
weaknesses: Recently, several more general IGL methods have been proposed, which can be used independently or in combination with the IGL techniques discussed in this paper. For instance, [1] based on topological augmentation and automated loss engineering approach [2], both presented at ICML '24, are notable examples. It would be beneficial if IGL-bench could include these recent booster-type methods and provide related discussion.
[1] Liu, Zhining, et al. "Class-Imbalanced Graph Learning without Class Rebalancing." Forty-first International Conference on Machine Learning.
[2] Guo, Xinyu, et al. "Automated Loss function Search for Class-imbalanced Node Classification." Forty-first International Conference on Machine Learning.

Meta-review: This paper introduces IGL-Bench, a benchmark for Imbalanced Graph Learning (IGL) that evaluates 24 algorithms across 17 datasets, addressing both class and topology imbalances in node- and graph-level tasks. The benchmark provides a unified data processing pipeline, evaluation protocols, and metrics, allowing researchers to assess the effectiveness, robustness, and efficiency of IGL methods. Additionally, the paper offers an open-source codebase to promote reproducibility and further research in the field.

The paper addresses a significant gap in graph learning by introducing a comprehensive benchmark for Imbalanced Graph Learning (IGL), essential for standardized evaluation in this rapidly evolving field. Through thorough experiments and analysis, it provides valuable insights into the strengths and limitations of current IGL algorithms, laying a solid foundation for future research. The open-source codebase and standardized evaluation framework enhance reproducibility, ensuring that the benchmark remains accessible and impactful for the broader research community. As a result, the reviewers unanimously voted to accept this paper.

Decision: Accept (Spotlight)