ECGN: A CLUSTER-AWARE APPROACH TO GRAPH NEURAL NETWORKS FOR IMBALANCED CLASSIFICATION.

## Abstract

Abstract Classifying nodes in a graph is a common problem.
The ideal classifier must adapt to any imbalances in the class distribution.
It must also use information in the clustering structure of real-world graphs.
Existing Graph Neural Networks (GNNs) have not addressed both problems together.
We propose the Enhanced Cluster-aware Graph Network ( ECGN ), a novel method that addresses these issues by integrating cluster-specific training with synthetic node generation.
Unlike traditional GNNs that apply the same node update process for all nodes, ECGN learns different aggregations for different clusters.
We also use the clusters to generate new minority-class nodes in a way that helps clarify the inter-class decision boundary.
By combining cluster-aware embeddings with a global integration step, ECGN enhances the quality of the resulting node embeddings.
Our method works with any underlying GNN and any cluster generation technique.
Experimental results show that ECGN consistently outperforms its closest competitors by up to 11 % percent 11 11\% 11 % on some widely-studied benchmark datasets.
The GitHub implementation for implementation and replication is publicly available on CodeLink .

## 1 Introduction

Graph Neural Networks (GNNs) have shown remarkable success in various tasks involving graph-structured data, including node classification [], link prediction [], and recommender systems []. Indeed, GNNs have achieved state-of-the-art performance in many of these tasks. However, existing methods often expect all node classes and labels to be equally frequent.
But in many real-world scenarios, node classes are imbalanced.
For instance, most users on social network platforms are legitimate, but a small percentage are bots.
This imbalance hurts the accuracy of bot detection [].
A similar challenge emerges when classifying websites by topics [].
A few topics are extremely popular, while most are rare.
The popular topics (the majority classes) tend to dominate the loss function.
Hence, the GNN focuses on these classes during training.
This undermines the accuracy of the GNN for nodes of the minority classes.
Hence, there is a need for GNN models capable of handling class-imbalanced node classification.

The class imbalance problem has been extensively studied in traditional machine learning.
The solutions typically fall into three categories.
Data-level methods balance the class distribution by over-sampling or under-sampling
[, ].
Algorithm-level approaches adjust the training process by using different misclassification penalties or prior probabilities for different classes
[, ].
Hybrid methods combine both strategies to mitigate class imbalance [].
However, all these methods assume independent and identically distributed data.
By its very nature, the graph structure introduces dependencies between the nodes.
Hence, such methods can yield suboptimal results when applied directly to graph datasets.

Compounding the class imbalance problem is the issue of uniform node updates in GNNs.
Recall that GNNs update each node’s embedding using information from the node’s neighbors.
The information exchange is mediated by trainable weight matrices.
The same weights are uniformly applied to all nodes.
However, such uniform node updates can cause two problems.

First, uniform updates can make the GNN overlook rich local structures in the graph.
Indeed, graphs have intricate substructures, such as clustered communities or hubs [].
Nodes within the same cluster exhibit higher similarity and stronger dependencies than nodes from different clusters.
Current GNNs can miss these nuanced local patterns and community-specific behaviors by treating all nodes identically.
Second, since the weights are optimized over the entire graph, they can be biased towards the majority class.
Hence, the node update process is sub-optimal for nodes from the minority class.
These problems can lead to poor embedding quality and underperformance in classification.

Our Contributions:
Although some existing studies have addressed either label imbalance [, ] or cluster-aware updates [], there is little work on tackling both issues simultaneously.
We propose the Enhanced Cluster-aware Graph Network (ECGN) to bridge this gap.

ECGN operates through a three-phase process.
In the pre-training phase, we train cluster-specific GNNs in parallel.
These GNNs extract information from local structures in the graph while ensuring that all embeddings map to the same latent space.
The node generation phase is a novel way to generate synthetic nodes for the minority class.
In particular, the synthetic node representations incorporate cluster-specific features.
Finally, the global-integration phase integrates the outputs of the previous stages into a cohesive set of node embeddings.
These capture the global information across the entire graph.
Our framework can be used with any existing GNN and is applicable whether or not the clusters are known a priori.

ECGN makes four significant contributions:

- •
cluster-aware node updates, that capture local cluster-specific information;
- •
addressing label imbalance via innovative synthetic cluster-aware node generation;
- •
seamless local to global integration, allowing the embeddings to learn from different scales; and
- •
broad applicability, by enabling any underlying GNN model to be used.

We verify the accuracy of ECGN on five benchmark datasets and show that we consistently outperform our closest competitors, with a lift of up to $11\%$ in F1 score on the widely studied Citeseer dataset.
These results confirm the applicability of ECGN for a wide range of real-world applications.

## 2 Related Works

We discuss the related work on learning under class imbalance, and Graph Neural Networks.

### 2.1 Class Imbalance Learning

Class imbalance in representation learning is a well-established topic in the field of machine learning, having been extensively studied over the years []. The primary objective is to develop an unbiased classifier for a labeled dataset where the distribution is skewed, with majority classes having a substantially larger number of samples than minority classes. Notable contributions to this area include re-weighting and re-sampling techniques. Re-weighting methods modify the loss function by assigning greater importance to minority classes [, ], or by enlarging the margins for these classes [, , ]. On the other hand, re-sampling methods aim to balance the dataset by pre-processing the training samples, employing strategies like over-sampling the minority classes [], under-sampling the majority classes [], or a combination of both [].

With advancements in neural networks, re-sampling strategies have evolved to not only include traditional sampling techniques but also to incorporate generative approaches. For instance, modern approaches augment minority class samples through generative methods [], where techniques such as SMOTE [] generate new samples by interpolating between existing minority samples and their nearest neighbors. Additionally, other methods synthesize minority class samples by transferring knowledge from majority classes [, ]. However, most of these existing methods are tailored to independent and identically distributed samples and are not directly applicable to graph-structured data, where the relational context between samples must be considered.

### 2.2 Graph Neural Networks

Graph Neural Networks, first introduced in 2005 [], have gained tremendous momentum in recent years with the advancements in deep learning, proving to be highly effective in processing non-Euclidean structured data. GNNs typically operate using a message-passing framework, where nodes iteratively gather information from their neighbors to learn low-dimensional embeddings that capture the graph’s structural and feature information []. These techniques are generally divided into two categories: spectral-based and spatial-based methods. Spectral-based methods exploit graph signal processing and leverage the graph Laplacian matrix to perform node filtering [, , ], while spatial-based methods aggregate information directly from the local neighborhood of each node based on the graph topology [, , ].

Addressing the challenge of class imbalance within GNNs has been an active area of research. Approaches such as GraphSMOTE [] extend the popular SMOTE technique to the embedding space of GNNs by synthesizing new minority nodes while also generating additional edges, improving performance in imbalanced settings. Another approach, GraphENS [], generates synthetic minority node features by mixing existing nodes from other classes. These methods face some limitations; for instance, altering the graph structure introduces complexities, and finding the optimal mixing ratio between node features can be difficult, often leading to noisy results that hurt performance. In contrast, ClusterGCN [] leverages METIS-based graph partitioning to create subclusters and trains the GNN in an SGD-based framework to capture cluster-specific information. However, while ClusterGCN captures local structural information by operating on clusters, it still applies uniform node updates within each subcluster and across the entire graph, meaning the same update rules and aggregation functions are uniformly applied to all nodes without adapting to their unique local structures or roles within the graph. This uniformity prevents ClusterGCN from fully addressing the issue of uniform node updates during training, leading to a loss of fine-grained local-global patterns crucial for capturing nuanced relationships and dependencies in graph learning.

While existing methods have made significant advancements, they often fail to simultaneously address both the intricate local structures of graphs and the class imbalance problem. Most algorithms excel in one area but compromise in the other. To bridge this gap, we propose ECGN, a method that combines subcluster-specific training to capture fine-grained local structures with a novel cluster-specific synthetic node generation technique inspired by SMOTE in the latent space. By focusing on nodes with high across-cluster connectivity, our synthetic node generation ensures that the new nodes are contextually relevant and contribute meaningfully to the learning process. Our approach not only addresses the class imbalance challenge but also preserves both global and local graph structures, making it especially advantageous in scenarios with large-scale data and readily available cluster information, as often encountered in big organizations. By overcoming the limitations of existing methods, ECGN provides a robust and comprehensive solution for graph learning tasks that require capturing fine-grained local structures and effectively handling class imbalance.

## 3 Proposed Algorithm

We are given a graph $G=(V,E)$, where $V$ represents the set of nodes and $E$ denotes the set of edges. Each node $v_{i}\in V$ is associated with a feature vector $\mathbf{x}_{i}\in\mathbb{R}^{d}$, forming the node feature matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$, where $n=|V|$ is the number of nodes and $d$ is the feature dimension. The graph structure is represented by the adjacency matrix $A\in\{0,1\}^{n\times n}$, where $A_{ij}=1$ if there is an edge between nodes $v_{i}$ and $v_{j}$, and $A_{ij}=0$ otherwise.
Each node $v_{i}\in V$ belongs to a class $y_{i}\in\{Y_{1},Y_{2},\ldots,Y_{c}\}$, where $c$ is the number of classes. The class distribution can be imbalanced. The classes for a subset of the nodes are known, and our goal is to predict the classes for the remaining nodes.

Next, we discuss ECGN’s architecture and algorithm, and provide details of our novel node generation step.

### 3.1 Architecture of ECGN

Figure: Figure 1: Working framework of ECGN architecture. We perform clustering on the nodes initially, train the sub-clusters independently in parallel, update the node embeddings to the original graph followed by Cluster-Aware SMOTE step and finally global integration.
Refer to caption: extracted/5929257/figures/ECGN_Submission.png

The architecture of ECGN is presented in Figure 1.
The algorithm begins by clustering the graph, unless the clusters are already known.
To compute clusters, one can use any fast algorithm such as Locality Sensitive Hashing (LSH) [] or METIS [] (see Appendix A.4 for details).
The choice of clustering algorithm is orthogonal to our method.

Next comes the pre-training step.
We first create a subgraph for each cluster.
This subgraph includes only the nodes and edges within the cluster.
Then, for each subgraph, we run a GNN to generate embeddings for nodes in that cluster.
All GNNs are run separately but share the same initialization.
The result of this stage is a node embedding $\{{\mathbf{h}}_{i}\}$ for every node $i$ in the graph.
Unlike embeddings from a global GNN, these embeddings focus on information from the local cluster of each node.
Appendix A.2 provides a detailed description.

The next stage tackles the class imbalance problem.
For this, we generate new nodes and edge with a new technique called Cluster-Aware SMOTE.
This differs from standard SMOTE in several ways.
First, our method operates on the latent space of the cluster-aware node embeddings ${\mathbf{h}}_{i}$ instead of the node features ${\mathbf{x}}_{i}$.
Second, unlike SMOTE, our approach focuses on minority-class nodes that lie on cluster boundaries.
The intuition is that in many real-world datasets, nodes from a given minority-class collect within one or a few clusters.
Hence, the cluster boundaries are a proxy for inter-class decision boundaries.
By generating nodes on the cluster borders, we can improve the decision boundary for node classification.
Finally, after generating nodes with new embeddings, we link them to existing nodes.
This step is needed for the following global aggregation step of ECGN.
Details of Cluster-Aware SMOTE are presented in Section 3.2.

The last step is global integration.
Here, we propagation global information throughout the nodes through graph convolution.
The result is a set of node embeddings that combine information from local clusters as well as global patterns.
Finally, these refined embeddings are used for node classification.
Algorithm 1 provides the pseudo-code for ECGN.

Figure: Algorithm 1 ECGN for Node Classification

### 3.2 Cluster-Aware SMOTE

Previous applications of SMOTE in graph contexts had several limitations.
Synthetic nodes have been generated using graph features, but this ignores the link structure of the graph
[, ].
Also, synthetic nodes were derived from minority-class seed nodes that were chosen randomly.
If the seeds have poor connectivity, so do the synthetic nodes.
Hence, the GNN’s node updates may not efficiently convey information about the minority class.

Our proposed approach, named Cluster-Aware SMOTE, addresses these challenges by leveraging both intra- and inter-cluster connectivity information.
Our method prioritizes minority-class nodes that lie on the borders of their clusters.
The resulting synthetic nodes lead to a more accurate decision boundary between classes.
Also, instead of using the node features, we use the cluster-aware node embeddings from the pre-training step.
This ensures that both features and connectivity information is used in creating the synthetic nodes.

The synthetic node generation process involves the following steps:

- 1.
Identify Highly Connected Nodes: For each minority node $v$ in class $Y_{m}$, we compute its connectivity to nodes in other clusters:
$\text{connectivity}(v)=\sum_{u\in V\setminus Y_{m}}A_{vu}$
We select the top $k$ nodes with the highest connectivity scores as the seed nodes for generating synthetic samples.
- 2.
Nearest Neighbor Selection: For each seed node $v$ from the minority class, we find its nearest neighbor $\text{nn}(v)$ within the same class in the embedding space:
$\text{nn}(v)=\arg\min_{u\in Y_{m},v\neq u}\|\mathbf{h}_{v}-\mathbf{h}_{u}\|$
where $\mathbf{h}_{i}$ is the cluster-aware embedding for node $i$ from the pre-training step, and $\|\cdot\|$ denotes the Euclidean distance. For very large graphs, techniques like FAISS [] can be used.
- 3.
Synthetic Node Generation: We generate a synthetic node $v^{\prime}$ by interpolating between the embeddings of $v$ and its nearest neighbor $\text{nn}(v)$:
$\mathbf{x}_{v^{\prime}}=(1-\delta)\mathbf{x}_{v}+\delta\mathbf{x}_{\text{nn}(v)}$
where $\delta$ is a random variable drawn from a uniform distribution in the range $[0,1]$.
- 4.
Edge Preservation:
We add the synthetic node $v^{\prime}$ to the graph, and add edges from $v^{\prime}$ to all the neighbors of $v$.
Thus, $v^{\prime}$ inherits the edges of $v$.
We also add a link from $v^{\prime}$ to $v$.
These steps ensure that the addition of the synthetic node $v^{\prime}$ preserves the local graph topology.
The updated adjacency matrix is as follows:
$\displaystyle A_{v^{\prime}i}$
$\displaystyle=\begin{cases}A_{vi}&\text{if $i\neq v$}\\
1&\text{if $i=v$}\end{cases}$
- 5.
Oversampling Control:
To control the number of generated nodes, we introduce a parameter $\alpha$.
For each minority class $Y_{m}$, we generate $\alpha\cdot|Y_{m}|$ synthetic nodes.
We restrict the value of $\alpha$ such that the number of synthetic nodes remains less than 50% of the majority class size.
This ensures that the synthetic nodes do not degrade performance for the majority class.

By focusing on nodes with high
inter-cluster
connectivity and generating synthetic samples in the latent space, our approach improves the diversity of synthetic nodes and better captures the underlying graph structure. This not only helps in addressing class imbalance but also enhances the overall classification performance by providing more representative samples for the minority class.

## 4 Experiments

We verify the accuracy of ECGN on five well-studied benchmark datasets.
We first describe the datasets and the competing baselines.
Then, we compare all algorithms on the node classification task.
Finally, we show via ablation studies the need for the various steps of ECGN.

Datasets: We evaluate ECGN on several widely-used public datasets for the node classification task.
Table 1 show the statistics and experimental setup for each dataset.
Further details are presented in Appendix A.1.

Table: Table 1: Experimental settings to simulate imbalanced scenario for each datasets

Baselines:
We compared ECGN against several state of the art methods.
These include GraphSAGE (with and without cluster information), cluster-aware GNNs such as ClusterGCN [], GNNs for imbalanced classification such as GraphSMOTE [], and various other reweighting and oversampling schemes.
Appendices A.1 and  A.5 provide more details about the baselines and their hyperparameters.
All methods were tested on node classification tasks, and compared on the basis of their F1 scores.
To ensure robust and reliable results, we averaged the F1-scores over four different random seeds.

For ECGN, we clusters the graphs using METIS.
We used $3$ clusters for CORA and CITESEER, $7$ for Amazon Computers, $40$ for Reddit, and $20$ for ogbn-arxiv.
Section 4.4 discusses how the number of clusters affect classification accuracy.

### 4.1 Results

Table 2 shows the classification accuracy for all the datasets.
We observe the following.

ECGN consistently outperforms other models across all datasets.
The closest competitors are ClusterGCN and GraphSMOTE.
However, ECGN’s F1-scores are higher by an average of nearly $5\%$.
ECGN outperforms its closest competitors by up to $\mathbf{11\%}$ (e.g., on the Citeseer dataset).

Cluster-aware node updates are necessary.
Consider two seemingly simple alternatives to the cluster-aware node updates of ECGN.
One is to just provide the clusters as features to GraphSAGE.
The second is to just use the Cluster-Aware SMOTE without the pre-training step of ECGN.
However, ECGN outperforms the former by $21\%$ on average, and the latter by $14\%$ on average.

Cluster-Aware SMOTE improves classification accuracy.
The F1 score of ECGN using Cluster-Aware SMOTE is $3\%$ higher that ECGN without this step.
For Citeseer, the difference increases to $6\%$.
Thus, Cluster-Aware SMOTE adds value.

These experiments further validate the structure and robustness of ECGN, demonstrating its ability to generalize effectively across both local subcluster models and global models.

**Table 2: Results across different graph benchmark datasets: ECGN outperforms other methods. The lift in F1-Score is up to $10-12\%$ over the closest competitors (for Citeseer).**
| (a) Results for CORA and CITESEER<br>Dataset<br>Method<br>F1-Score<br>CORA<br>GraphSAGE<br>0.66<br>GraphSAGE ($+$ Cluster Features)<br>0.68<br>SMOTE<br>0.69<br>Re-Weighting<br>0.67<br>EN-Weighting<br>0.68<br>Over-Sampling<br>0.63<br>CB-Sampling<br>0.71<br>GraphSMOTE<br>0.71<br>ClusterGCN<br>0.72<br>Cluster-Aware SMOTE only<br>0.70<br>ECGN (Without SMOTE)<br>0.73<br>ECGN (With SMOTE)<br>0.74<br>CITESEER<br>GraphSAGE Baseline<br>0.37<br>GraphSAGE ($+$ Cluster Features)<br>0.38<br>SMOTE<br>0.45<br>Re-Weighting<br>0.56<br>EN-Weighting<br>0.52<br>Over-Sampling<br>0.35<br>CB-Sampling<br>0.51<br>GraphSMOTE<br>0.59<br>ClusterGCN<br>0.58<br>Cluster-Aware SMOTE only<br>0.46<br>ECGN (Without SMOTE)<br>0.61<br>ECGN (With SMOTE)<br>0.65 | (b) Results for Reddit and ogbn-arxiv<br>Dataset<br>Method<br>F1-Score<br>Reddit<br>GraphSAGE Baseline<br>0.74<br>GraphSAGE ($+$ Cluster Features)<br>0.74<br>SMOTE<br>0.76<br>Re-Weighting<br>0.77<br>EN-Weighting<br>0.75<br>Over-Sampling<br>0.75<br>CB-Sampling<br>0.72<br>GraphSMOTE<br>0.77<br>ClusterGCN<br>0.76<br>Cluster-Aware SMOTE only<br>0.76<br>ECGN (Without SMOTE)<br>0.77<br>ECGN (With SMOTE)<br>0.79<br>ogbn-arxiv<br>GraphSAGE Baseline<br>0.37<br>GraphSAGE ($+$ Cluster Features)<br>0.38<br>SMOTE<br>0.39<br>Re-Weighting<br>0.40<br>EN-Weighting<br>0.41<br>Over-Sampling<br>0.38<br>CB-Sampling<br>0.39<br>GraphSMOTE<br>0.41<br>ClusterGCN<br>0.43<br>Cluster-Aware SMOTE only<br>0.39<br>ECGN (Without SMOTE)<br>0.44<br>ECGN (With SMOTE)<br>0.45 |
| --- | --- |

### 4.2 Direct Inference from Subclusters: Why Do We Need Global Integration?

In this section, we explore the impact of bypassing the global integration step and directly inferring from subclusters. This approach leverages local structures within each subcluster but neglects the global graph structure. To evaluate this, we conducted experiments on the Cora and Citeseer datasets, which offer manageable complexity for detailed analysis.

**Table 3: Performance results when directly inferring from subclusters without global integration.**
| Dataset | Num Clusters | F1-Score Without Global Integration | Best ECGN F1-Score |
| --- | --- | --- | --- |
| Citeseer | 3 | 0.26 | 0.65 |
| Cora | 3 | 0.32 | 0.74 |

Table 3 shows that skipping global integration leads to significantly lower F1-scores: 0.26 for Citeseer and 0.32 for Cora.
This highlights the importance of integrating the global graph after subcluster training. Without it, the model learns Cluster-Aware relations but fails to generalize and learn inter-cluster relations, causing lower performance.

In conclusion, the global integration step is crucial as it bridges the gap between local subcluster structures and the overarching global graph. It ensures that the final node embeddings are both locally accurate and globally consistent, leading to better performance, as evidenced by the increased F1-scores after global integration.

### 4.3 Reusing GNN Weights from Pre-training in Global Integration

We can think of ECGN as a transfer learning approach.
In the pre-training step, we learn separately from each cluster.
Then, we transfer the learnt embeddings to the global integration step.
This ensures a balance between local and global structures in the graph, which yields the strong performance of ECGN.

Extending this idea, we can ask: what if we transferred the GNN model weights from pre-training alongside the node embeddings?
To explore this, we experimented with three different strategies for transferring weights:

- 1.
Average Weights: Initialize the weights of the global GNN with the averaged weights of all subcluster GNNs.
- 2.
Largest Subcluster Weights: GNN weights from the largest subcluster are transferred to the global model.
- 3.
Best Performing Subcluster Weights: Weights from the best-performing subcluster are transferred to the global model.

**Table 4: Performance results when transferring weights along with feature representations across different strategies.**
| Dataset | Weight Transfer Strategy | F1-Score with Weight Transfer | Best ECGN F1-Score |
| --- | --- | --- | --- |
| Citeseer | Average | 0.51 | 0.65 |
| Largest | 0.65 | 0.65 |  |
| Best | 0.66 | 0.65 |  |
| Cora | Average | 0.52 | 0.74 |
| Largest | 0.66 | 0.74 |  |
| Best | 0.67 | 0.74 |  |
| Amazon Computers | Average | 0.54 | 0.78 |
| Largest | 0.68 | 0.78 |  |
| Best | 0.69 | 0.78 |  |

The results in Table 4 show that transferring pre-trained weights alongside the node embeddings yields mixed outcomes. The Average Weights strategy consistently performed the worst, likely because averaging diluted the unique structural information from each subcluster. The Largest Subcluster Weights and Best Performing Subcluster Weights improved performance over averaging but did not outperform ECGN without weight transfer.
Overall, we find that the best performance comes from ignoring the pre-trained GNN weights in the global integration.
This is what ECGN does.

We believe the reason for the above results lies in the delicate balancing act between learning from the graph’s local structure and its global context.
The introduction of pre-trained weights $\mathbf{W}$ into the global model appears to disrupt this balance.
The pre-trained weights are perhaps too tailored to specific clusters.
So, they may not generalize well when applied to the entire graph.

In conclusion, weight transfer offers no significant advantage and may reduce performance. The success of ECGN lies in combining local embeddings through global integration, capturing both local and global structures without transferring subcluster-specific weights.

### 4.4 Selecting the Number of Clusters

The number of clusters affects both the effectiveness of the cluster-aware embeddings and ECGN’s computational efficiency. The key challenge lies in balancing the capture of fine-grained local patterns with the retention of important global structures.

Figure: Figure 2: Effect of Number of Clusters on F1-Score for Various Datasets
Refer to caption: x1.png

In our experiments, we observed that the model’s performance is relatively robust to the number of clusters within a reasonable range. As shown in Figure 2, the F1-Score varies with the number of clusters across different datasets.
For datasets like Cora and Citeseer, using 3 to 5 clusters yielded comparable results, while extreme values—either too low or too high—led to decreased performance. This suggests that while the number of clusters is important, the model can tolerate variations without significant loss of effectiveness.

## 5 Conclusion and Limitations

In this paper, we introduced the Enhanced Cluster-aware Graph Network (ECGN), a novel framework designed to address the challenges of class imbalance and subcluster-specific training in graph neural networks. By integrating cluster-specific updates, synthetic node generation, and a global integration step, ECGN demonstrates significant improvements in classification performance on imbalanced datasets. Our experimental results show that ECGN not only enhances the representation of minority classes but also maintains the structural integrity of the original graph, leading to more accurate and robust predictions. We also stated that modifying ECGN either by bypassing global tuning or integrating weight transfer learning hurts the performance. A detailed analysis of why ECGN works is provided in Appendix A.3 for more clarity.

However, there are limitations to our approach. The reliance on subcluster partitioning may introduce sensitivity to the quality of the clustering algorithm, and potentially impact the overall performance if the clusters are not well-formed. Additionally, the synthetic node generation process, while beneficial for handling imbalance, may introduce noise if not carefully managed, especially in graphs with highly complex structures. Future work will focus on refining these aspects for broader graph tasks like graph/link predictions, and evaluating ECGN on more diverse graph datasets to further validate its effectiveness.

## Appendix A Appendix

### A.1 Details of Baselines and Experimental Datasets

Here, we first provide the details of the baselines implemented.

- •
Cluster-GCN: A most popular GCN algorithm that is suitable for SGD-based training by exploiting the graph clustering structure based on METIS partitioning. [].
- •
GraphSMOTE: An oversampling method specifically designed for graphs that generates synthetic minority nodes by interpolating between existing nodes within the minority class [].
- •
Re-Weighting: A classic cost-sensitive approach that adjusts the loss function with weights inversely proportional to the number of samples in each class [].
- •
EN-Weighting: A variant of the re-weighting method, which assigns weights based on the Effective Number of samples in each class [].
- •
Over-Sampling: A traditional re-sampling method where minority nodes are repeatedly sampled until each minority class has the same number of samples as the majority classes.
- •
CB-Sampling: A re-sampling method inspired by [], which first selects a class and then randomly samples a node from that class.
- •
RU-Selection: A baseline model that supplements the minority class by randomly selecting unlabeled nodes with pseudo-labels corresponding to the minority class until the class distribution is balanced.
- •
SU-Selection: An extension of RU-Selection that selects unlabeled nodes based on their similarity to the minority class, rather than random selection.

Here, we provide the details and explain the settings for the imbalanced scenario.

- •
Cora Dataset: Contains 2708 scientific publications categorized into 7 classes with 5429 links. We simulated a highly imbalanced scenario by sampling only 30% of the total samples available for the last 3 classes. Full-batch GD training was done, and number of METIS partition clusters were fixed to be 3. Synthetic nodes were added such that the minority class samples increases to 100 from 20 for each of the imbalanced class.
- •
Citeseer Dataset: Contains 3327 scientific publications classified into 6 categories with 4732 links. Full-batch GD training was done, and number of METIS partition clusters were fixed to be 3. Synthetic nodes were added such that the minority class samples increases to 100 from 20 for each of the imbalanced class.
- •
Reddit Dataset: Consists of posts made by users on the Reddit online discussion forum, categorized into 50 classes with over 230K nodes and 11M edges. The training was done with stochastic neighborhood sampling with batch size of 1024. The number of METIS partition clusters were fixed to be 40. Synthetic nodes were added such that the minority class samples increases to 400 from 50 for each of the imbalanced class.
- •
Amazon Computers Dataset: Contains 13,752 nodes categorized into 10 classes with 245,861 edges. Full-batch GD training was done, and the number of METIS partition clusters was fixed to 7. Synthetic nodes were added such that the minority class samples increases to 600 from 100 for each of the imbalanced class.
- •
ogbn-arxiv Dataset: Comprises 169,343 scientific publications from arXiv, categorized into 40 classes with 1,166,243 edges. To simulate an imbalanced scenario, we sampled only 100 nodes for the last 10 classes. The training was done with stochastic neighborhood sampling with batch size of 1024. The number of METIS partition clusters were fixed to be 20. Synthetic nodes were added such that the minority class samples increases to 600 from 100 for each of the imbalanced classes.

### A.2 Original GraphSAGE vs. Subclustered GraphSAGE

##### Original GraphSAGE

GraphSAGE [] generates node embeddings by aggregating features from a node’s local neighborhood. Given a graph $G=(V,E)$ with $N=|V|$ nodes and initial node features $\mathbf{X}\in\mathbb{R}^{N\times F}$, the embedding of node $v$ at layer $k$ is updated as:

- 1.
Neighborhood Aggregation:
$\mathbf{h}_{\mathcal{N}(v)}^{(k)}=\text{AGGREGATE}^{(k)}\left(\left\{\mathbf{h
}_{u}^{(k-1)}\mid u\in\mathcal{N}(v)\right\}\right),$
(1)
where $\mathcal{N}(v)$ is the set of neighbors of node $v$, and $\mathbf{h}_{u}^{(k-1)}$ is the embedding from the previous layer.
- 2.
Node Embedding Update:
$\mathbf{h}_{v}^{(k)}=\sigma\left(\mathbf{W}^{(k)}\cdot\text{CONCAT}\left(
\mathbf{h}_{v}^{(k-1)},\mathbf{h}_{\mathcal{N}(v)}^{(k)}\right)\right),$
(2)
where $\mathbf{W}^{(k)}$ is the weight matrix, $\sigma$ is an activation function, and $\mathbf{h}_{v}^{(0)}=\mathbf{x}_{v}$.

This process is repeated for $K$ layers to capture $K$-hop neighborhood information. The final embeddings $\mathbf{h}_{v}^{(K)}$ are used for tasks like node classification.

##### Subcluster-Based GraphSAGE

In ECGN, we enhance GraphSAGE by incorporating cluster-specific information:

- 1.
Graph Partitioning: Divide $G$ into $M$ disjoint subclusters $\{G_{1},G_{2},\dots,G_{M}\}$, with corresponding feature matrices $\mathbf{X}_{i}$.
- 2.
Localized Learning: For each subcluster $G_{i}$, perform GraphSAGE focusing only on Cluster-Aware edges:
$\mathbf{h}_{v}^{(k)}=\sigma\left(\mathbf{W}^{(k)}\cdot\text{CONCAT}\left(
\mathbf{h}_{v}^{(k-1)},\text{AGGREGATE}_{i}^{(k)}\left(\left\{\mathbf{h}_{u}^{
(k-1)}\mid u\in\mathcal{N}_{i}(v)\right\}\right)\right)\right),$
(3)
where $\mathcal{N}_{i}(v)$ denotes Cluster-Aware neighbors.
- 3.
Embedding Compilation: Combine embeddings from all subclusters:
$\mathbf{H}^{(K)}=\begin{pmatrix}\mathbf{H}_{1}^{(K)}\\
\mathbf{H}_{2}^{(K)}\\
\vdots\\
\mathbf{H}_{M}^{(K)}\end{pmatrix}.$
(4)
- 4.
Global Integration: Perform an additional GraphSAGE layer over $G$ to integrate global information:
$\mathbf{h}_{v}^{(\text{final})}=\sigma\left(\mathbf{W}^{(K+1)}\cdot\text{
CONCAT}\left(\mathbf{h}_{v}^{(K)},\text{AGGREGATE}^{(K+1)}\left(\left\{\mathbf
{h}_{u}^{(K)}\mid u\in\mathcal{N}(v)\right\}\right)\right)\right).$
(5)

##### Key Advantages

- •
Enhanced Local Patterns: Captures fine-grained structures within clusters.
- •
Computational Efficiency: Allows parallel processing of subclusters.
- •
Global Coherence: Global aggregation integrates inter-cluster relationships.
- •
Improved Handling of Imbalance: Clustering aids in addressing class imbalance by focusing on underrepresented nodes within clusters.

By combining localized learning with global integration, the subcluster-based approach in ECGN effectively captures both local and global graph structures, leading to improved performance in node classification tasks.

### A.3 Visualizing the Clustered Communities and Analyzing the Sub-Clustered Approach

In this section, we visualize the clustered communities within the Cora and Citeseer datasets and we try to provide a theoretical explanation of why our sub-clustered approach is effective. We selected these datasets due to their manageable size and well-documented structure, which makes them ideal candidates for visual analysis. We divided the datasets into three clusters using the METIS algorithm and present the visualizations below.

Figure: (a) Cora Original
Refer to caption: extracted/5929257/figures/Cora_RAW.png

The figures in Figure 3 depict both the original and clustered versions of the Cora and Citeseer datasets. The original graphs (3(a) and 3(c)) exhibit dense connectivity, which often leads to an entangled representation where the underlying community structure is not immediately apparent. By applying the METIS algorithm, we break down these dense graphs into distinct clusters (3(b) and 3(d)), revealing the internal structure of the communities.

In this section, we try to provide a theoretical explanation of why our sub-clustered approach is effective.

##### Why does the Sub-Clustered Approach Work?

The effectiveness of the sub-clustered approach can be theoretically explained through the following principles:

##### 1. Capturing Localized Patterns

When the graph is clustered into $k$ subgraphs using METIS, we obtain subgraphs $G_{1},G_{2},\ldots,G_{k}$ such that:

$$ $G_{i}=(V_{i},E_{i}),\quad\text{where}\quad V_{i}\subseteq V\quad\text{and} \quad E_{i}\subseteq E$ $$

The feature matrix for each subgraph is $\mathbf{X}_{i}\in\mathbb{R}^{n_{i}\times d}$, where $n_{i}=|V_{i}|$ is the number of nodes in subgraph $G_{i}$.

By training on these subgraphs independently, the model learns localized patterns within each $G_{i}$, which are typically more homogeneous and easier to capture than the global patterns in $G$. The local loss function for each subgraph can be expressed as:

$$ $\mathcal{L}_{i}=\frac{1}{n_{i}}\sum_{v_{j}\in V_{i}}\mathcal{L}(f(\mathbf{x}_{ j}),y_{j})$ $$

where $f(\mathbf{x}_{j})$ is the model’s prediction for node $v_{j}$, and $y_{j}$ is the true label. Training on localized loss functions $\mathcal{L}_{i}$ allows the model to optimize performance within each cluster before aggregating the knowledge during global integration.

##### 2. Reducing Computational Complexity

The computational complexity of training a GNN on a large graph $G$ is often dominated by the cost of message passing and aggregation across the entire graph. However, by decomposing $G$ into smaller subgraphs $G_{1},G_{2},\ldots,G_{k}$, and being able to train them parallel independently, the computational cost is significantly reduced.

The overall complexity can be approximated as:

$$ $\text{Total Complexity}\approx\sum_{i=1}^{k}\mathcal{O}(|E_{i}|)$ $$

where $|E_{i}|$ is the number of edges in subgraph $G_{i}$. Since each $|E_{i}|$ is smaller than $|E|$ (the total number of edges in the original graph), the sub-clustered approach leads to more efficient training.

##### 3. Addressing Imbalanced Data

In imbalanced graphs, certain classes of nodes may be underrepresented, making it difficult for the model to learn their characteristics. By isolating these nodes within sub-clusters, the model can pay more focused attention to the minority classes.

Let $C$ be the set of classes in the graph, with $|C_{\text{min}}|$ and $|C_{\text{maj}}|$ representing the number of nodes in the minority and majority classes, respectively. After clustering, the number of minority nodes in a subgraph $G_{i}$ can be denoted as $|C_{\text{min},i}|$. The training process can now focus on balancing the loss contributions:

$$ $\mathcal{L}_{i}^{\text{balance}}=\frac{1}{|C_{\text{min},i}|}\sum_{v_{j}\in C_ {\text{min},i}}\mathcal{L}(f(\mathbf{x}_{j}),y_{j})+\frac{1}{|C_{\text{maj},i} |}\sum_{v_{j}\in C_{\text{maj},i}}\mathcal{L}(f(\mathbf{x}_{j}),y_{j})$ $$

This ensures that the minority class nodes have a more significant influence on the model’s learning process within each cluster.

##### 4. Global Structure Integration

After the initial training on sub-clusters, the model undergoes global aggregation on the global graph $G$. This step integrates the knowledge learned from each sub-cluster and ensures that node representations are coherent across the entire graph. The global integration process can be represented as:

$$ $\mathcal{L}_{\text{global}}=\frac{1}{n}\sum_{v_{j}\in V}\mathcal{L}(f(\mathbf{ x}_{j}),y_{j})$ $$

This global loss function aligns the local representations and improves the overall performance of the model.

By training on these clusters and then performing the global integration, the model leverages both localized knowledge and global context, resulting in more accurate and generalizable node representations. The sub-clustered approach mitigates the risk of overfitting to dominant structures and promotes a more balanced and comprehensive understanding of the graph.

### A.4 Clustering and Community detection techniques

#### A.4.1 Locality-Sensitive Hashing Clustering (Feature based Clustering)

We present an standard version of LSH clustering algorithm to efficiently handle large-scale datasets with millions of nodes. The algorithm uses sparse random projections to group similar feature vectors into clusters.

Algorithm Description

Given a feature matrix $\mathbf{X}\in\mathbb{R}^{n\times d}$, where $n$ is the number of samples and $d$ is the number of features, the goal is to cluster the samples based on their similarity. The optimized algorithm proceeds as follows:

- 1.
Hash Table Creation:
We create $T$ hash tables, each using $P$ random projections. Each hash table is represented by a sparse random projection matrix $\mathbf{R}\in\mathbb{R}^{d\times P}$.
$\mathbf{R}_{t}\sim\text{SparseRandomProjection}(d,P)\quad\text{for}\quad t=1,2
,\ldots,T$
- 2.
Hashing Feature Vectors:
Each feature vector $\mathbf{x}_{i}\in\mathbb{R}^{d}$ is projected into a lower-dimensional space using the hash tables. The projection is followed by taking the sign of the resulting vector to create hash keys.
$\mathbf{h}_{i}^{t}=\text{sign}(\mathbf{x}_{i}\mathbf{R}_{t})\quad\text{for}
\quad i=1,2,\ldots,n\quad\text{and}\quad t=1,2,\ldots,T$
The sign function is applied element-wise, resulting in a hash key $\mathbf{h}_{i}^{t}\in\{-1,1\}^{P}$.
- 3.
Bucket Assignment:
Each hash key is used to group feature vectors into buckets. A bucket $\mathcal{B}_{t}(\mathbf{h})$ contains all vectors that share the same hash key $\mathbf{h}$ for the $t$-th hash table.
$\mathcal{B}_{t}(\mathbf{h})=\{i\mid\mathbf{h}_{i}^{t}=\mathbf{h}\}$
- 4.
Merging Buckets:
We merge buckets from all hash tables into preliminary clusters. Each node is assigned to a cluster based on its initial bucket assignments, ensuring unique assignments.
$\text{clusters}[i]=\text{cluster_id}\quad\text{if}\quad i\in\mathcal{B}_{t}(
\mathbf{h})\quad\forall\,t$
- 5.
Cluster Refinement:
Each preliminary cluster is refined by computing the centroid of its feature vectors and using cosine similarity with a threshold to ensure nodes belong to the most similar cluster.
$\text{similarity}(\mathbf{x}_{i},\mathcal{C})=\frac{\mathbf{x}_{i}\cdot\mathbf
{c}_{\mathcal{C}}}{\|\mathbf{x}_{i}\|\|\mathbf{c}_{\mathcal{C}}\|}\quad\text{
where}\quad\mathbf{c}_{\mathcal{C}}=\frac{1}{|\mathcal{C}|}\sum_{\mathbf{x}_{j
}\in\mathcal{C}}\mathbf{x}_{j}$
Each node $i$ is assigned to cluster $\mathcal{C}^{*}$ if $\text{similarity}(\mathbf{x}_{i},\mathcal{C}^{*})>0.5$.
- 6.
Final Cluster Formation:
The final clusters are formed by ensuring each node belongs to one and only one cluster.
$\mathcal{C}_{k}\rightarrow\mathbf{C}_{k}\quad\text{where}\quad\mathbf{C}_{k}
\in\mathbb{R}^{|\mathcal{C}_{k}|\times d}$

The algorithm ensures efficient clustering of high-dimensional data by leveraging the properties of locality-sensitive hashing and sparse random projections. The resulting clusters can be used in subsequent tasks such as classification, anomaly detection, and data summarization.

#### A.4.2 METIS partitioning (Structure based Clustering)

METIS partitioning is a graph partitioning technique designed to divide a graph into smaller, roughly equal-sized subgraphs while minimizing the edge cuts between them. The primary objective is to balance the load across subgraphs and reduce the communication volume in parallel computing environments.

Given a graph $G=(V,E)$ with vertices $V$ and edges $E$, the goal is to partition $G$ into $k$ subgraphs $G_{1},G_{2},\ldots,G_{k}$ such that:

1. The size of each subgraph is approximately equal, i.e., $\left|V_{i}\right|\approx\frac{\left|V\right|}{k}$ for $i=1,2,\ldots,k$.
2. The number of edges cut, denoted as $\text{cut}(G)$, is minimized. This is mathematically represented as minimizing the sum of weights of edges that have endpoints in different subgraphs:

$$ $\text{cut}(G)=\sum_{\begin{subarray}{c}(u,v)\in E\\ u\in G_{i},v\in G_{j}\\ i\neq j\end{subarray}}w(u,v)$ $$

where $w(u,v)$ is the weight of the edge between nodes $u$ and $v$.

METIS employs a multilevel approach, which involves three main phases:

1. Coarsening Phase: The graph is iteratively coarsened by collapsing vertices and edges to form a series of progressively smaller graphs.
2. Partitioning Phase: A partitioning algorithm, often a variant of the Kernighan-Lin or Fiduccia-Mattheyses heuristic, is applied to the smallest graph to obtain an initial partition.
3. Uncoarsening Phase: The initial partition is projected back through the series of intermediate graphs, refining the partition at each level to improve the quality of the final partition.

This multilevel approach ensures that the partitioning process is both efficient and effective in producing high-quality partitions with balanced subgraph sizes and minimal edge cuts.

### A.5 Experimental settings for Baseline experiments

In our experiments, we use METIS partitioning to create subclusters for all the datasets.
The experiments were configured with consistent training hyperparameters across datasets, including an initial learning rate of 0.01 for most datasets (with Reddit using 0.001), and the Adam optimizer. Each experiment ran for up to 1500 epochs, with early stopping after 40 steps if the validation performance did not improve. A batch size of 128 was used for Cora and Citeseer, while larger datasets such as Reddit, AmazonComputer, and ogbn_arxiv used batch sizes of 1024 or 2048 to accommodate their size. For model architecture, we adopted 2-layer GraphSAGE with a layer dimension of 128 for most datasets, though Reddit employed a smaller 64-dimensional GNN with 1 layer. We used the ’mean’ aggregator for message passing and allowed for dynamic learning rates across layers. Full-batch training was used for Cora, Citeseer, and ogbn_arxiv, whereas AmazonComputer and Reddit were trained with neighborhood sampling (as documented in [https://docs.dgl.ai/en/0.8.x/guide/minibatch-node.html#guide-minibatch-node-classification-sampler](https://docs.dgl.ai/en/0.8.x/guide/minibatch-node.html#guide-minibatch-node-classification-sampler)) with 4-layer deep neighborhood samples with sizes [4,4,4,4] due to their size. Additionally, datasets were clustered, with the number of clusters ranging from 3 (Cora, Citeseer), 7(AmazonComputer), 20(obgn-arxiv) to 40 (Reddit).

## Peer Reviews

confidence: 4
contribution: 2
initial_rating: 3
presentation: 1
questions: See Weakness.
soundness: 2
strengths: 1. The experiments are thorough, covering datasets of various sizes, including a large-scale dataset.
2. The source code is available for review, and the repository is well-organized.
summary: This paper introduces ECGN, a method designed to address class-imbalanced node classification. The approach begins by clustering nodes into groups, then computing node embeddings within each cluster through separate GNN models. Using these embeddings, it applies SMOTE to oversample minority nodes, augmenting the original graph, which is then processed by another GNN model for further training. Extensive experiments on datasets of varying sizes are conducted to evaluate the model, including ablation studies to assess the contribution of each component.
weaknesses: 1. The paper is poorly organized. It devotes excessive space to related work and includes figures and tables, such as Figure 2, Table 3, and Table 4, that take up significant space without providing much information. Meanwhile, important details are missing from the main paper, particularly about the pre-training step in Proposed Algorithm section, which is crucial as an ablation study references it. However, placing these contents in the appendix forces readers to flip back and forth to follow this paper.

2. I have concerns about the pre-training stage. It appears to involve simple feature aggregation with separate GNNs within each cluster. Are these GNNs trained independently? If so, what is the training objective? If not, why not consider a non-parametric model for feature aggregation instead?

3. The clustering stage raises some concerns. Given the high class imbalance in the graph, minority nodes may end up grouped with a large number of majority nodes within the same cluster, leading to a poor clustering quality. Have the authors considered this possibility?

4. Equations in the paper lack indexing, making them difficult to reference. Additionally, in line 257, the paper states that connectivity measures the connections between minority nodes and nodes in other clusters. However, the equation that follows counts connections between minority nodes and nodes in other classes.

5. Standard deviations are missing from the reported results. This is particularly concerning given that each model is only run four times, which could yield results with high variability.

6. In Table 2, the performance difference between ECGN with and without SMOTE is minimal. This raises questions about the necessity of this component. Is synthesizing minority nodes essential for addressing class imbalance in this context? Again, the absence of standard deviation reporting makes it unclear whether this improvement is statistically significant.

7. In the related work section, the paper critiques previous generative methods, stating, “altering the graph structure introduces complexities, and finding the optimal mixing ratio between node features can be difficult, often leading to noisy results that hurt performance.” However, this work does not address these issues, as its node synthesis method appears to share the same limitations as previous node generative approaches.

---

confidence: 4
contribution: 3
initial_rating: 6
presentation: 2
questions: Q1:
a) What are the specifics of “Cluster-Aware SMOTE only” in the benchmark results, i.e. Table 2? Section 3.2 described “Cluster-Aware SMOTE” to synthesize nodes, but there is no mention of building a classifier. 
b) What’s the difference between “Cluster-Aware SMOTE only” and “ECGN with SMOTE”, and 
c) What’s the difference between “Cluster-Aware SMOTE only” and GraphSMOTE?
d) Why is “Cluster-Aware SMOTE only” showing inferior performance than GraphSMOTE if the cluster-aware SMOTE is supposed to be more effective than non-cluster-aware SMOTE?

Q2:
Cluster aware node synthesis in 3.2, especially synthesizing nodes around the cluster boundary seems to be an important and novel step compared to GraphSMOTE. How effective is this approach, what if it reverts to a baseline approach? Is there any experiment validating the contribution of this step?

Q3:
Related to Q2, the embeddings for the synthesized nodes are generated from their neighborhood. Neighborhood nodes could come from different clusters, but all embeddings were pre-trained within each cluster. Was any inter-cluster graph structure lost in this process?
soundness: 3
strengths: The overall framework is novel and quite reasonable. It combines the strength from both GraphSMOTE and ClusterGCN while introducing innovative improvements on top of the previous SOTA in various aspects, including:
1. Carrying out SMOTE with a cluster aware approach. Synthesizing nodes around the cluster boundary would be more effective for imbalanced classification problems.
2. Using cluster specific GCN instead of a single GCN at the pre-training stage followed by global aggregation at a later stage. This balanced approach captures both local and global information, with trade-offs in compute and storage efficiency.

The proposed ECGN has been compared to a wide range of methods, and the experimental results consistently outperform the references across all evaluated datasets, demonstrating its effectiveness.
summary: This paper proposes an improved framework for building graph neural networks for imbalanced node classification tasks. The end-to-end flow includes the following steps:
1. Cluster-Specific Training: The input graph is partitioned into smaller clusters, and graph neural networks are pre-trained for each cluster to generate node embeddings.
2. Cluster-Aware SMOTE: Synthetic nodes are generated for minority classes, with a focus on nodes located near cluster boundaries. The embeddings from Step 1 are used to identify nearest neighbors, enabling interpolation to create new embeddings for the synthesized nodes.
3. Global Integration: All embeddings from Steps 1 and 2 are used to train a global classifier.

The framework leverages local structural information in Step 1 and global information in Step 3, while Step 2 addresses class imbalance. Experimental results demonstrate substantial improvement over previous state-of-the-art, including GraphSMOTE and Cluster-GCN.
weaknesses: Presentation:
1. The network architecture for cluster specific pretraining and global aggregation in Figure 1 are illustrative at high level, lacking details of network architecture. It didn’t clarify whether local and global network structures are identical. Additionally, the Global aggregation is only described as “H′ ← convolution of G′ using H′ as node features.” in Algorithm 1, without clear correspondence from Figure 1.
2. The methods in experiment evaluation could be more clearly linked to references or description, specifically “Cluster-Aware SMOTE only” is confusing; see Q1 in the Question section.
3. No information on computational cost has been provided, so it is unclear what trade-offs were made to achieve accuracy improvements.

Reference:
The reference to (Chiang et al., 2019) should include the conference information (KDD ’19) rather than only an arXiv link. Additionally, (Zhao et al., 2021b) is not the correct reference for GraphSMOTE, and the information provided in the reference is also incorrect.

Experiments:
More detailed experiments are expected to clarify the value of Cluster-Aware SMOTE; see Q2 in the Question section.

---

confidence: 4
contribution: 3
initial_rating: 5
presentation: 2
questions: 1. The summary of related work is incomplete. Considering that the main contribution of this paper lies in addressing the graph class imbalance problem, the authors should discuss recent papers that tackle this issue, such as [1][2][3][4][5][6], to strengthen the paper's motivation and contribution.

2. The methodology section lacks clarity. The most confusing aspect is the distinction between class and cluster. Specifically, when clustering algorithms like LSH group nodes with similar features into a cluster, is there any correlation between the clusters and the node labels (classes)? The authors should provide a specific example or diagram illustrating how classes and clusters relate in their approach.

3. Continuing from question 2: To what extent does the quality of the clustering algorithm affect the final results? If the clustering algorithm is optimal and clusters nodes perfectly according to their labels, would that improve prediction performance? How should we interpret the statement on line 200, "The choice of clustering algorithm is orthogonal to our method"? Does this imply that the clustering results have no impact on the final outcome of the method? It is recommended that the authors add an ablation study or sensitivity analysis to quantify how different clustering algorithms or their qualities affect the final results.

4.  Continuing from question 2: On line 257, the paper states, "For each minority node v in class Y_m, we compute its connectivity to nodes in other clusters." This statement blurs the distinction between class and cluster. How should we understand the relationship between class and cluster in this context?

5.  The experiments are insufficient. On one hand, the authors mention that the baselines are somewhat outdated. It is recommended to compare against more recent methods, such as [1][2][3][4][5][6]. On the other hand, even when comparing with the baselines mentioned in the paper, the performance improvements across several datasets are marginal, with numerical increases of only 0.02 to 0.03, representing less than a 5% improvement. It is suggested that the authors conduct comparisons with more updated work; this way, even modest improvements could be considered acceptable in the context of advancing the state of the art.

6.  Continuing from question 5: The authors are encouraged to provide training time and training parameters such as training time per epoch, total training time, and memory usage for both ECGN and baseline methods in the paper or appendix. Given that the framework appears to require training multiple GNNs, it is important to clarify whether the performance improvements come at the cost of significantly higher computational overhead.

References:  
[1]	Park, Joonhyung, Jaeyun Song, and Eunho Yang. "Graphens: Neighbor-aware ego network synthesis for class-imbalanced node classification." International conference on learning representations. 2021.  
[2]	Qian, Yiyue, et al. "Co-modality graph contrastive learning for imbalanced node classification." Advances in Neural Information Processing Systems 35 (2022): 15862-15874.  
[3]	Wang, Yu, Charu Aggarwal, and Tyler Derr. "Distance-wise Prototypical Graph Neural Network for Imbalanced Node Classification." Proceedings of the 17th International Workshop on Mining and Learning with Graphs (MLG). 2022.  
[4]	Song, Jaeyun, Joonhyung Park, and Eunho Yang. "TAM: topology-aware margin loss for class-imbalanced node classification." International Conference on Machine Learning. PMLR, 2022.  
[5]	Zeng, Liang, et al. "Imgcl: Revisiting graph contrastive learning on imbalanced node classification." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 9. 2023.  
[6]	Zhou, Mengting, and Zhiguo Gong. "GraphSR: a data augmentation algorithm for imbalanced node classification." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 37. No. 4. 2023.
soundness: 2
strengths: 1. This paper proposes a novel framework for addressing the problem of label imbalance in graph data.

2. The method demonstrates strong performance on specific benchmark datasets.

3. The code is publicly available, which is beneficial for the community in terms of reproducibility and further research.
summary: This paper introduces ECGN, a framework that enhances Graph Neural Networks (GNNs) by incorporating cluster-specific training and synthetic node generation to address class imbalance in graph data, applicable to node classification tasks. ECGN employs a novel technique called Cluster-Aware SMOTE, which generates synthetic minority-class nodes, improving the decision boundary between classes and enhancing overall model performance. By combining cluster-aware updates with a global integration step, ECGN captures both local cluster-specific information and global graph structures. The model was evaluated on five benchmark datasets, including Citeseer and Reddit, and consistently outperformed existing state-of-the-art methods, with up to an 11% improvement in F1-score on imbalanced node classification tasks.
weaknesses: 1. The summary of related work is incomplete. See question 1.

2. The description of the methodology is not clear enough. See questions 2, 3, and 4.

3. The experiments are not comprehensive enough. See questions 5 and 6.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: Please refer to weaknesses above.
soundness: 2
strengths: - The paper is well-written, clear, and easy to follow. 
- Extensive experiments are conducted to validate ECGN's performance, and the inclusion of the code enhances reproducibility and supports the credibility of results. 
- ECGN is highly adaptable, functioning as a versatile enhancement for any GNN backbone, which underscores its potential generalizability across various GNN architectures.
summary: The paper introduces ECGN, a new method in Graph Neural Networks designed to improve node classification in class-imbalanced datasets by leveraging cluster-specific embeddings and synthetic node generation. ECGN operates by first pre-training subclusters to capture local graph structures, then generating synthetic nodes in boundary areas of minority clusters to enhance classification for underrepresented classes, and finally integrating these local representations into a global structure. This approach outperforms existing models, achieving up to an 11% improvement on benchmark datasets, highlighting its ability to maintain both global and local graph consistency for balanced, high-accuracy node classification.
weaknesses: - Motivation Clarity: Imbalanced classification and node clustering on graphs are two orthogonal problems. The motivation behind combining these two aspects is not sufficiently clear, and further elaboration is necessary to explain why clustering is beneficial for addressing class imbalance.
- Related Work: The related work lacks coverage of recent advancements in class-imbalanced node classification. Key methods such as "GraphENS: Neighbor-Aware Ego Network Synthesis for Class-Imbalanced Node Classification" (ICLR 2022), "TAM: Topology-Aware Margin Loss for Class-Imbalanced Node Classification" (ICML 2022), "GraphSHA: Synthesizing Harder Samples for Class-Imbalanced Node Classification" (KDD 2023), and "Class-Imbalanced Graph Learning without Class Rebalancing" (ICML 2024) should be discussed and ideally included in the empirical comparisons.
- Inappropriate claims: The statement in line 54, “uniform updates can make the GNN overlook rich local structures,” is Inappropriate. Through simple uniform aggregation, message passing in GNNs can also capture local structures. 
- Evaluation: The F1-score improvements shown in Table 2 are modest across all datasets. Incorporating additional evaluation metrics for imbalanced learning, such as balanced accuracy would provide a more nuanced view of the model’s performance.

Meta-review: ### Summary
The paper introduces ECGN, a framework to address class-imbalanced node classification. ECGN employs cluster-specific GNN pre-training to generate node embeddings, Cluster-Aware SMOTE to oversample minority nodes near cluster boundaries, and a global GNN for final integration and classification. The method combines local cluster-level structural information with global graph insights. Extensive experiments on benchmark datasets show that ECGN achieves competitive results, outperforming state-of-the-art methods.

### Strengths
- The paper combines clustering-based local pre-training, cluster-aware SMOTE, and global GNN training to tackle class imbalance, which is a novel approach in the graph learning domain.
- The method is evaluated on diverse datasets, with ablation studies assessing the contributions of key components. Results show improvement over baseline methods.
- The availability of well-organized code ensures that the method can be reproduced and facilitates further research in this area.

### Weaknesses
- Unclear Motivation and Methodology: The motivation for combining clustering and SMOTE to handle class imbalance is underexplained, particularly how clusters relate to node classes.
- Ambiguities exist in key notations and descriptions (e.g., distinction between classes and clusters, undefined symbols in equations).
- The reported F1-score improvements over baselines are minor (often under 5%), raising questions about the necessity of the SMOTE component and overall method complexity.
- The paper lacks comparisons with recent methods in class-imbalanced graph learning, such as GraphENS (ICLR 2022) and TAM (ICML 2022), which could contextualize its contributions more clearly.

While the paper proposes an innovative framework for addressing class imbalance in graph data, it suffers from unclear methodology, modest empirical improvements, and missing comparisons with recent work. The limited motivation for combining clustering with SMOTE further weakens its contributions. Improvements in clarity, stronger baselines, and more rigorous experimental analysis are needed for acceptance.

Decision: Reject