¹

1 Introduction↩︎

Graph data is prevalent across many domains, making graph analysis, particularly node classification, a significant research focus [1], [2]. With the rise of deep learning, Graph Neural Networks (GNNs) [3]–[6] have become the go-to method for node-level graph analysis, achieving notable success on benchmark datasets. However, GNNs often falter when applied to real-world graphs with imbalanced node class distributions [7]–[11]. In these scenarios, majority classes have significantly more labeled nodes for training than minority classes, leading to performance bias that favors majority classes and marginalizes minority classes, resulting in sub-optimal classification outcomes.

To address class-imbalanced node classification, researchers have developed various solutions, which can be broadly categorized into algorithm-level and data-level approaches [12]. Most of these methods can be regarded as identifying and prioritizing important nodes during training to mitigate the imbalance issue. Algorithm-level approaches enhance the importance of minority classes by assigning higher weights to them or expanding their margins [9], [13]–[16]. However, these methods typically determine a node’s importance based solely on its class size, disregarding its specific features or position within the graph. This oversight of intrinsic differences among nodes of the same class oversimplifies the problem and poses challenges to model training. For instance, outliers within minority classes may introduce noise, and overemphasizing these outliers can skew the model towards misleading patterns. Additionally, certain instances within majority classes, especially those near class boundaries, may be crucial in forming a clear decision boundary that benefits both majority and minority classes. Furthermore, static weighting mechanisms are agnostic to the model’s current status and cannot adapt to the model’s training progress. Since neural networks tend to learn patterns of increasing complexity as training progresses [17], a dynamic weighting mechanism that adapts to the model’s learning progress is preferable to a fixed scheme.

On the other hand, data-level approaches balance class sizes by oversampling minority classes through node synthesis [7], [18]–[21]. Most methods follow a MixUp-like style [22], [23], sampling pairs of nodes and mixing their features and neighbors to generate new nodes. The generation process serves as an implicit measure of importance, with various heuristics refining each stage of the synthesis pipeline to produce potentially important nodes. However, data-level approaches have limited flexibility, as their implicit importance measures cannot be easily extended to unlabeled nodes, which have significant potential to augment the dataset and address the class imbalance issue [11], [24]–[26].

In this work, we propose a different strategy to identify valuable nodes for training to address class-imbalanced node classification, using a balanced meta-set for importance measurement. Our approach is based on a simple yet fundamental assumption [14], [27]–[29]: a training node is deemed important if the model, after being trained on it, performs better under an unbiased setting. This strategy offers two main advantages. First, by evaluating the contributions of individual nodes to model performance in a balanced scenario, we can dynamically distinguish important nodes from negligible ones within a class at different training phases. Second, this assumption allows for increased flexibility. For instance, with node oversampling, we can utilize any off-the-shelf node synthesis techniques to generate new nodes and then use the balanced meta-set to identify those that can alleviate class imbalance.

However, straightforwardly applying a meta-set for node filtering in graph-structured data poses unique challenges, leading to two urgent issues. First, assessing node importance with a meta-set requires a bi-level evaluation process: training the model on each node individually and then evaluating the trained model on the meta-set. This process is computationally demanding and time-consuming, which calls for a relaxation of the bi-level evaluation process to achieve higher efficiency. Second, in class-imbalanced node classification scenarios, the balanced meta-set we could construct is generally quite small, making its quality sensitive to random noise. Since the quality of the meta-set is crucial to the overall performance, a carefully designed method is needed to build a high-quality meta-set from the training set.

To tackle these issues, we introduce NodeImport, a versatile framework for class-imbalanced node classification tasks that employs an unbiased meta-set to identify important nodes for training. By expanding the bi-level evaluation process and adopting a series of graph-specific assumptions, we derive a formula to directly calculate the importance of a node in the graph, thereby reducing computational overhead. The derived formula indicates that node importance is influenced not only by static graph characteristics but also by dynamic model prediction behaviors, providing an intuitive interpretation of the formula. Moreover, this formula naturally gives rise to a meaningful threshold for node selection, eliminating the need for manual threshold tuning. Leveraging our importance formula, we can seamlessly incorporate unlabeled and synthetic nodes into model training, in addition to labeled nodes. Since the computation of node importance is orthogonal to the node generation process, we decouple the node generation process from the filtering process, allowing us to use any existing methods to synthesize nodes or create pseudo-labels for unlabeled nodes, while the filtering process, using the importance formula, then selects valuable nodes able to address class imbalance. Furthermore, to build a high-quality meta-set, we conduct clustering within the embedding space of each class and select representative samples as meta-samples to capture the intrinsic patterns of each class.

We perform a comprehensive empirical evaluation of NodeImport using three popular GNN architectures: GCN [3], GAT [5], and GraphSAGE [4]. This evaluation utilizes multiple benchmark datasets, comprising three citation datasets [30] and two Amazon co-purchase datasets [31], under a long-tailed imbalance setting [32]. The experimental results highlight the effectiveness of the derived importance formula for selecting valuable nodes for training. In addition, it demonstrates the efficiency of the proposed framework in incorporating various node sources to augment the training set and address class imbalance in node-level classification tasks. Overall, the major contributions of this work are summarized as:

• To address class imbalance in node classification, we propose using a balanced meta-set to select nodes valuable to model training. This approach allows a detailed examination of individual nodes’ contributions and provides increased flexibility in the node selection process.

• We theoretically derive a formula to directly assess node importance, thus largely reducing the computational overhead. Furthermore, this formula naturally gives rise to a filtering threshold and has an intuitive interpretation.

• Leveraging the derived formula, we introduce NodeImport, a versatile framework that incorporates valuable labeled, unlabeled, and synthetic nodes for training to counter class distribution imbalance. Additionally, we build a component to extract a high-quality meta-set from labeled nodes.

• Comprehensive experiments on various public benchmark datasets demonstrate the superiority of NodeImport compared to state-of-the-art baselines. Detailed analyses highlight the necessity and effectiveness of its components.

2 Related works↩︎

Existing solutions to the class imbalance problem can be broadly categorized into algorithm-level and data-level approaches [12]. Algorithm-level methods aim to guide the model to focus more on minority classes. This can be achieved by assigning higher weights to minority classes [13], [32]–[35] or by expanding the margins for minority classes [14], [15], [36]–[38]. However, these methods gauge a training sample’s importance according to its class size, treating all samples from minority classes as equally important without considering their intrinsic characteristics. Although some methods tailored for graph data, such as TAM [9] and ReNode [16], consider a node’s topological location when assigning weights, their weights do not dynamically adapt to the model’s status during training. Other algorithm-level approaches include imposing additional regularization constraints [39], [40], employing multi-expert training with knowledge distillation [41], or by correcting nodes with ineffective message passing caused by topological disparities. [42].

Data-level techniques balance class sizes through resampling [41], [43]–[45] or generative methods [46]–[48]. In the graph domain, most works [7], [18]–[21] adopt MixUp-like [22], [23] generative methods to augment minority classes, differing in how they sample node pairs, mix node features, and construct edges for synthetic nodes. These generative techniques synthesize potentially important minority nodes based on heuristics adopted in the synthesis pipeline. However, these heuristics implicitly define an importance measure that cannot be directly applied to unlabeled nodes, thus limiting their flexibility. Recently, GraphSR [11] was proposed to identify valuable unlabeled nodes to augment minority classes, but its rules cannot be extended to evaluate synthetic nodes. In contrast, our work employs a balanced meta-set to identify important nodes capable of handling class imbalance for training, positing that a training node is essential if it can improve the model’s performance under an unbiased condition.

For an in-depth discussion of class imbalance learning, please kindly refer to the following surveys [12], [49]–[52].

In the image domain, several works employ a balanced meta-set to learn instance-wise weights [27], [28] or class-wise sampling rates [14] to counter class imbalance. However, these approaches often require bi-level optimization during training, imposing a significant computational burden. On the contrary, we focus on graph-structured data and theoretically derive a formula to simplify the bi-level optimization process, thus saving computing resources. In addition, the derived formula naturally gives a filtering threshold and has a specific interpretation related to the graph domain.

In the active learning domain, meta-sets are used to identify valuable training nodes [29], [53], [54], aiming to train a model with as few samples as possible to speed up the training process. Meta-sets in these works usually bear the same class distribution as the training set and do not need to be balanced. The most relevant work to our derived formula is the RHO-Loss [29], which derives a formula to simplify the computation of sample importance. However, the RHO-Loss still requires an extra model trained on the meta-set and a pre-defined filtering threshold. By contrast, our work customizes the RHO-Loss to the graph domain, deriving a formula with semantic meaning specific to graphs. This formula is more straightforward and does not require storing an additional model trained on the meta-set, thus cutting down memory consumption. Additionally, it naturally provides a filtering threshold for node selection, eliminating the need for manual threshold tuning.

3 Preliminary↩︎

A graph \(G\) is represented as \(\mathcal{G} = \{\mathcal{V}, \mathcal{E}, X\}\), where \(\mathcal{V}\) is the set of \(n\) nodes, \(\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}\) is the set of edges, and \(X \in \mathbb{R}^{n \times d}\) is the node feature matrix with each row \(x_v \in \mathbb{R}^d\) being the feature vector for node \(v \in \mathcal{V}\). The graph structure can also be described by an adjacency matrix \(A \in \{0,1\}^{n \times n}\), where \(A_{i,j} = 1\) if there is an edge \(\langle i,j \rangle\) and \(A_{i,j} = 0\) otherwise. Each node \(v\) is associated with a one-hot encoded label vector \(y_v \in \{0,1\}^{1 \times c}\) over \(c\) classes, and \(Y \in \{0,1\}^{n \times c}\) is the label matrix containing these label vectors. Given a graph encoder \(g(\cdot; \theta)\) with parameters \(\theta\) (e.g., a GNN model), nodes within the graph can be mapped into probability distributions \(H \in \mathbb{R}^{n \times c}\) indicating the likelihood of each node belonging to different classes, formulated as \(H = g(\mathcal{G}; \theta)\). We denote the predictive distribution of the GNN model on node \(v\) as \(p(y_v | v; \theta)\) for the ease of analysis.

Class-imbalanced node classification involves categorizing nodes into their respective classes when the label distribution among classes is uneven, often resulting in a performance bias favoring majority classes [7], [55]. The imbalance ratio \(IR=r_0/r_1\) quantifies the degree of imbalance, where \(r_0\) and \(r_1\) represent the sizes of the largest and smallest classes, respectively [12]. The optimal parameters of the graph encoder \(\theta^*\) are obtained by minimizing the cross-entropy loss on the training set \({\mathcal{D}}_{tr}=\{(v, y_v)\}\) defined as: \[\label{eq46main-loss} \textstyle \theta^* = \underset{\theta}{\arg\min} \sum_{(v,y_v)\in {\mathcal{D}}_{tr}} - \text{log } p(y_v | v ; \theta).\tag{1}\] Here, we utilize \(L[y_v | v; \theta]=-\text{log } p(y_v | v ; \theta)\) to denote the cross-entropy loss for an individual training point \((v, y_v)\in{\mathcal{D}}_{tr}\).

We introduce an unbiased meta-set \({\mathcal{D}}_{meta}=\{(v^{(meta)}, y_v^{(meta)})\}\) with a balanced class distribution for evaluating node importance. For simplicity, this meta-set is written as \({\boldsymbol{v}}^{(meta)}\) and \({\boldsymbol{y}}^{(meta)}\). The meta-set is usually much smaller than the training set (i.e., \(|{\mathcal{D}}_{tr}| \gg |{\mathcal{D}}_{meta}|\)), and helps rectify the graph encoder in cases of imbalanced training data. Given a training point \((v, y_v) \in {\mathcal{D}}_{tr}\), we define the following metric \(\eta_v\) to evaluate its importance to model training: \[\label{eq46model-objective} \begin{align} \eta_v &= \text{log} \frac{p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t; (v,y_v))}{ p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t)} \\ &= \text{log } p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t; (v,y_v)) \\ &\quad - \text{log } p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t). \end{align}\tag{2}\] Intuitively, this metric assesses whether the current model’s performance on the balanced meta-set improves after being trained on the given point. When \(\eta_v > 0\), the node is considered important and used in the next training step. Calculating this metric involves training the current model on each data point individually and determining if the updated model performs better on the meta-set. This process is computationally intensive, which necessitates a more tractable approximation.

4 The Proposed Model: NodeImport↩︎

In this section, we start by deriving a tractable formula to approximate Eq. 2 , which simplifies the bi-level selection process to pinpoint important nodes. Subsequently, we illustrate how this formula can be utilized to identify crucial labeled, unlabeled, and synthetic nodes to augment the training set. Finally, we introduce our meta-set construction method, which selects representative meta-samples. The entire framework architecture is illustrated in Figure 1, while its pseudocode and complexity analysis are provided in Appendix 8.

4.1 Tractable Importance Metric for Node Selection↩︎

Following [29], we employ Bayesian probability theory to derive a more tractable form of Eq. 2 . By applying Bayes’ theorem and assuming conditional independence, \(p(y_v|v,u;\theta_t)=p(y_v|v;\theta_t)\), we arrive at the following equation: \[\label{eq:bayes95rule} \begin{align} \eta_v &= \text{log } p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t; (v,y_v)) \\ &\quad - \text{log } p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t) \\ &= \text{log } \frac{p(y_v | v; {\boldsymbol{v}}^{(meta)}, {\boldsymbol{y}}^{(meta)}; \theta_t) \cdot p({\boldsymbol{y}}^{(meta)} | {\boldsymbol{v}}^{(meta)}, v; \theta_t)}{p(y_v|v, {\boldsymbol{v}}^{(meta)}; \theta_t)} \\ &\quad - \text{log } p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t) \\ &= \text{log } \frac{p(y_v | v; {\boldsymbol{v}}^{(meta)}, {\boldsymbol{y}}^{(meta)}; \theta_t) \cdot p({\boldsymbol{y}}^{(meta)} | {\boldsymbol{v}}^{(meta)}; \theta_t)}{p(y_v|v; \theta_t)} \\ &\quad - \text{log } p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t) \\ &= \text{log } p(y_v | v; ({\boldsymbol{v}}^{(meta)}, {\boldsymbol{y}}^{(meta)}); \theta_t) - \text{log } p(y_v|v; \theta_t), \end{align}\tag{3}\] where the second equation applies Bayes’ theorem to decompose \(p({\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)}; \theta_t; (v,y_v))\), and the third equation simplifies terms using the assumption of conditional independence. Intuitively, the final equation in Eq. 3 can be interpreted as the difference in performance at the training point \((v,y_v)\) between the current model and the one updated with the meta-set. Let \(\hat{\theta}_t\) denote the parameters of the updated model, we have: \[\label{eq:expression951} \begin{align} \eta_v &= \text{log } p(y_v | v; \hat{\theta}_t) - \text{log } p(y_v|v; \theta_t) \\ &= L[y_v|v;\theta_t] - L[y_v|v;\hat{\theta}_t], \end{align}\tag{4}\] where, in the second equation, we adopt the definition of cross-entropy loss on point \((v, y_v)\). Given Eq. 4 , the calculation process simplifies to training the current model on the meta-set and monitoring the change of loss values on training points, which incurs only one extra round of training and is thus more efficient. However, it remains computationally demanding as we need to update the model on the meta-set at each training step.

Suppose that \(\hat{\theta}_t = \theta_t + \Delta\), where \(\Delta\) represents the parameter updates based on the meta-set, we employ a first-order Taylor series expansion to express \(L[y_v|v;\hat{\theta}_t]\) in terms of \(L[y_v|v;\theta_t]\) and turn Eq. 4 into the following format: \[\label{eq:expression952} \begin{align} \eta_{v} &= L[y_v|v;\theta_t] - L[y_v|v;\theta_t+\Delta] \\ &= L[y_v|v;\theta_t] - (L[y_v|v;\theta_t] + \langle \nabla_\theta L[y_v|v;\theta_t], \Delta \rangle_F + o(\Delta^2)) \\ &\approx - \langle \nabla_\theta L[y_v|v;\theta_t], \Delta \rangle_F, \end{align}\tag{5}\] where \(\nabla_\theta L[y_v|v;\theta_t]\) is the gradient of the individual loss function with regard to weights \(\theta\) at \(\theta_t\), and \(\langle \cdot,\cdot \rangle _F\) represents the Frobenius inner product. To get a cheaper estimate of parameter updates \(\Delta\), we assume that a single optimization step is taken for model \(\theta_t\) on the meta-set \({\mathcal{D}}_{meta}\), which gives the following assumption.

With the assumption above, the importance of a node is determined by the alignment of gradient descent directions between the training point and the meta-set, which is compatible with findings from previous works on meta-learning [27], [28], [56], [57]: \[\label{eq:expression953} \begin{align} \eta_{v} &\approx \kappa \cdot \langle \nabla_\theta L[y_v|v;\theta_t], \nabla_\theta L[{\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)};\theta_t] \rangle_F. \end{align}\tag{6}\] To obtain a more explicit expression of the cross-entropy loss function \(L[y_v|v;\theta_t]\), we make the following assumption about the architecture of the GNN encoders used for ease of analysis.

Given this assumption, the individual loss function \(L[y_v|v;\theta_t]\) can be expressed in terms of the underlying GNN model. Let \(\tilde{A}_v\in\mathbb{R}^{1\times n}\) be the aggregation matrix associated with node \(v\), we get: \[\label{eq:loss95format} \begin{align} L[y_v|v;\theta_t] &= - \mathrm{\small LogSoftMax}(\tilde{A}_v X \theta)y_v^T, \end{align}\tag{7}\] where \(\mathrm{\small LogSoftMax}\) represents the function that applies element-wise logarithm to the output of softmax. To proceed with the derivation of Eq. 6 , it is necessary to compute the derivative of the cross-entropy loss function \(L[\cdot]\) defined in Eq. 7 with respect to the model parameters \(\theta\). Given \(H=\mathrm{\small SoftMax}(\tilde{A}X\theta)\), the derivative of the cross-entropy loss with regard to model parameters \(\theta\) is: \[\label{eq:matrix95gradient} \begin{align} \nabla_\theta L &= (\tilde{A} X)^T(H-Y). \end{align}\tag{8}\] The detailed derivation of Eq. 8 is provided in Appendix 7.1. In essence, we work in differential form to compute the derivative. Substituting Eq. 8 into Eq. 6 gives our final importance metric: \[\label{eq:final95expression} \begin{align} \eta_{v} &\approx \kappa \cdot \langle \nabla_\theta L[y_v|v;\theta_t], \nabla_\theta L[{\boldsymbol{y}}^{(meta)}|{\boldsymbol{v}}^{(meta)};\theta_t] \rangle_F \\ &= \kappa \cdot \text{tr}( (h_v-y_v)^T (\tilde{A}_v X) (\tilde{A}_{meta}X)^T (H_{meta} - Y_{meta}) ) \\ &= \kappa \cdot (\tilde{A}_v X) (\tilde{A}_{meta}X)^T (H_{meta} - Y_{meta}) (h_v-y_v)^T, \end{align}\tag{9}\] where \(\tilde{A}_{meta}\in\mathbb{R}^{m\times n}\), \(H_{meta}\in \mathbb{R}^{m\times c}\), and \(Y_{meta}\in [0,1]^{m\times c}\) represent the aggregation matrix, model prediction, and label matrix associated with nodes in the meta-set, respectively.

We offer an explanation of the functioning of our derived importance metric in Eq. 9 by breaking it down into two constituent components:

• Context similarity \((\tilde{A}_v X) (\tilde{A}_{meta}X)^T\): This component measures the similarity between the node sample \((v,y_v)\) and the meta-set \({\mathcal{D}}_{meta}\) by considering both the input features of the nodes and the structure of their local subgraphs. It captures the local context similarity within the graph, reflecting static graph characteristics and being agnostic to the underlying GNN model.

• Prediction behavior similarity \((H_{meta} - Y_{meta}) (h_v-y_v)^T\): This component evaluates the similarity in the prediction behavior of the model between the node sample \((v, y_v)\) and the meta-set \({\mathcal{D}}_{meta}\). It is relevant to the underlying GNN model and captures the model’s dynamics during training.

By examining the importance metric as a whole, we observe that training samples from under-represented classes (i.e., minority classes) are more favored by the metric compared to those from over-represented classes (i.e., majority classes). This is partly because our meta-set is balanced, ensuring that each class has an equal voting opportunity. Additionally, the term \((H_{meta}-Y_{meta})\) specifically assesses the current model performance on each class and places more emphasis on classes with poor performance. Furthermore, the context similarity and prediction behavior similarity between a node and the meta-samples of its class are also crucial, aiding in the removal of outliers in the minority classes. This explains why our metric is capable of effectively addressing class-imbalanced issues.

In practice, we employ existing polynomials of the adjacency matrix \(A\) (such as those used in APPNP [61] or SSGC [60]) to calculate the aggregation matrix \(\tilde{A}\) and utilize the calculated matrix to compute the context similarity. It is important to note that the context similarity is computed once at the beginning of the program and is used throughout the entire training process. The prediction behavior similarity is computed using the output of the current model, which requires no additional computation. In general, applying our formula to evaluate the importance of nodes incurs minimal extra computational overhead.

4.2 Framework↩︎

Based on the importance metric derived in Eq.@eq:eq:final95expression , our primary approach is to apply this metric to labeled nodes. This allows us to filter out valuable nodes for model training, which can effectively counter class imbalance. Additionally, this metric can be extended to include unlabeled and synthetic nodes, which has been proven beneficial for augmenting the training set and addressing class imbalance issues [7], [11], [18]. To utilize this metric, we need to generate pseudo-labels for unlabeled nodes. As for synthetic nodes, we synthesize their input features, edge connections, and labels. A key advantage of our metric lies in its independence from specific methods for generating pseudo-labels and synthesizing nodes, ensuring compatibility with any existing techniques in the literature. In this work, we demonstrate that even the simplest methods yield superior performance when equipped with our metric. In the subsequent sections, we describe how we incorporate valuable labeled, unlabeled, and synthetic nodes into the training set, each of which forms a distinct component.

4.2.0.1 Component 1

The first component we construct is to identify labeled nodes that are worth training in a class-imbalanced setting using our importance metric. Let \({\mathcal{D}}_{l}=\{(v, y_v)\}\) denote the set of labeled nodes. The set of valuable labeled nodes \(\tilde{D}_{l}\) is defined as: \[\label{eq:valuable95labeled} \begin{align} \tilde{D}_{l} = \{(v, y_v) \in D_{l}\;|\;\eta_v >0 \}. \end{align}\tag{10}\]

4.2.0.2 Component 2

As the labels for the unlabeled nodes are unavailable during training, we generate pseudo-labels for them before applying the importance metric. In this study, we choose the class with the highest prediction probability from the model as the pseudo-label. For each unlabeled node \(v \in {\mathcal{D}}_{ul}\), its pseudo-label \(\hat{y}_v\) is: \[\label{eq:pesudo-label} \begin{align} \hat{y}_v = \arg\max_{k} h_{v}[k], \end{align}\tag{11}\] where \(h_{v}=H[v,:] \in\mathbb{R}^{1\times c}\) is the prediction probability distribution of the current GNN model on node \(v\). With the pseudo-label \(\hat{y}_v\), we replace \(y_v\) in Eq.@eq:eq:final95expression with it to compute the importance \(\eta_v\) for the unlabeled node. The filtered set of unlabeled nodes \(\tilde{D}_{ul}\) is then: \[\label{eq:valuable95unlabeled} \begin{align} \tilde{D}_{ul} = \{(v, \hat{y}_{v})\;|\;v \in D_{ul} \text{ and } \eta_v >0 \}. \end{align}\tag{12}\]

4.2.0.3 Component 3

In this study, we adopt a MixUp-like methodology to generate synthetic nodes, augmenting the training dataset to mitigate class imbalance. Firstly, we draw a set of node pairs \({\mathcal{S}}=\{\langle(v_s,y_s), (v_t, y_t)\rangle\}\) from the training set. Specifically, nodes \(v_s\) are sampled until each class reaches the maximum sample count among all classes in the training set, while nodes \(v_t\) are sampled based on the probability \(p_t(u)\) defined as follows: \[\label{eq:sample95probability} \begin{align} p_t(u) = \frac{\text{log }(|{\mathcal{V}}_k|+1)}{(|{\mathcal{V}}_k|+1)\sum_{j=1}^{c}\text{log }(|{\mathcal{V}}_j|+1)}. \end{align}\tag{13}\] where \(k\) is the label of node \(u\) and \(|{\mathcal{V}}_k|\) stands for the subset of nodes with label \(k\). This increases the likelihood of selecting nodes from minority classes for synthesis, thereby enriching their patterns within the training set. For each node pair \(\langle (v_s, y_s), (v_t, y_t) \rangle \in {\mathcal{S}}\), we generate a new node \(v_{syn}\) by employing MixUp [22] from three aspects, namely feature, neighborhood, and label mixing: \[\label{eq46synthetic95formula} \begin{cases} x_{syn} = \lambda \cdot x_s + (1-\lambda) \cdot x_t,\\ {A'}_{syn} = \lambda \cdot A_{s} + (1-\lambda) \cdot A_{t}, \\ y_{syn} = \lambda \cdot y_s + (1-\lambda) \cdot y_t. \end{cases}\tag{14}\] where \(\lambda \sim \text{Beta}(\alpha,\alpha)\) represents the synthetic scale drawn from the Beta distribution with the parameter \(\alpha\), and \(A'_{syn}\in\mathbb{R}^{1\times n}\) denotes the combined adjacency matrix for nodes \(v_s\) and \(v_t\). Since \(A'_{syn}\) consists of real numbers, it must be converted into a discrete version. This involves sampling a specific number of neighbors for node \(v_{syn}\) based on \(A'_{syn}\), resulting in a discrete form \(A_{syn}\): \[\begin{align} A_{syn} = \text{Sample} (A'_{syn}), \end{align}\] where the probability of an item \(A_{syn}[k]\) being one is proportional to the corresponding value in \(A'_{syn}[k]\). To maintain consistent degree statistics as per common practice in prior research [19], [20], the number of sampled neighbors is drawn from a separate degree distribution of the entire graph. In this way, we produce a set of new nodes, i.e., \({\mathcal{D}}_{syn}=\{(v_{syn},y_{syn})\}\), based on the sampled node pairs \({\mathcal{S}}\). Combining Eq. 9 and Eq. 14 , we calculate the importance of a synthetic node \(\eta_{v_{syn}}\) to determine whether to use it for training. Finally, we build a set of valuable synthetic nodes: \[\label{eq:valuable95synthetic} \begin{align} \tilde{D}_{syn} = \{(v_{syn}, {y}_{syn})\;\in {\mathcal{D}}_{syn}\;|\;\eta_{v_{syn}} >0 \}. \end{align}\tag{15}\]

The overall training objective \({\mathcal{L}}\) is defined as the sum of the cross entropy loss on high-quality labeled nodes \({\mathcal{L}}_{l}\), unlabeled nodes \({\mathcal{L}}_{ul}\), and synthetic nodes \({\mathcal{L}}_{syn}\): \[\label{eq:final95loss} \begin{align} {\mathcal{L}}= {\mathcal{L}}_{l} + \beta \cdot {\mathcal{L}}_{ul} + \gamma \cdot {\mathcal{L}}_{syn}, \end{align}\tag{16}\] where \(\beta\) and \(\gamma\) are scaling factors for the losses of the unlabeled and synthetic nodes, respectively.

4.3 Meta-set construction↩︎

The effectiveness of our framework is heavily dependent on the quality of the meta-set due to its small size. Our goal is to select a fixed number of nodes for each class \(k\) that can accurately reflect the distribution of the initial training pool \(\mathcal{V}_k\). Let \(\mathcal{M}_k \subseteq \mathcal{V}_k\) denote the set of meta-samples for class \(k\). We aim to find the optimal set \(\tilde{\mathcal{M}}_k\) by minimizing the following objective: \[\begin{align} \textstyle \tilde{{\mathcal{M}}}_k = \arg\min_{{\mathcal{M}}_k} \frac{1}{|{\mathcal{V}}_k|} \sum_{v\in{\mathcal{V}}_k} D(v, {\mathcal{M}}_k), \end{align}\] where \(D(\cdot,\cdot)\) represents the distance between a node \(v\) and the meta-set \({\mathcal{M}}_k\). To calculate this distance, we exploit the context embedding for the nodes, \(F=\tilde{A} X\), which captures not only the nodes’ features but also their local structures. Let \(f_v\) be the context embedding vector of a node \(v\), and we define the distance \(D(v, {\mathcal{M}}_k)\) between the node and the meta-set \({\mathcal{M}}_k\) as: \[\textstyle \begin{align} D(v,{\mathcal{M}}_k) = \min_{u \in {\mathcal{M}}_k} \text{dist}(f_v, f_u), \end{align}\] where \(\text{dist}(\cdot, \cdot)\) denotes the distance metric between two vectors. In this work, this metric can be the Euclidean distance or the Manhattan distance. Intuitively, the distance between a node and the meta-set is formulated as the distance to its closest meta-sample in the meta-set. Given the impracticality of finding the optimal solution through exhaustive search, we employ a heuristic search method. In particular, we utilize the Partitioning Around Medoids (PAM) algorithm [62] to identify meta-samples for each class. The meta-set utilized is then the union of meta-samples from each class: \[\begin{align} \textstyle {\mathcal{D}}_{meta} = \{ (v,y_v)\;|\;v \in \bigcup_{k=1}^{c} \tilde{{\mathcal{M}}}_k \}. \end{align}\] In the end, we exclude the meta-set \({\mathcal{D}}_{meta}\) from the training set \({\mathcal{D}}_{tr}\) to form the set of labeled nodes \({\mathcal{D}}_{l}\).

5 Experiments↩︎

5.1 Experimental Setup↩︎

We adopt five benchmark datasets, which consist of three citation networks (Cora, CiteSeer, and PubMed) [30] and two Amazon co-purchase networks (Amazon-Photo and Amazon-Computers) [31]. Dataset statistics are summarized in Table 1. For all datasets, we set the imbalance ratio \(IR\) to 50 and construct a long-tailed training set following  [32]. For the citation datasets, we use the public data splits from  [63] and iteratively remove nodes from the training set to create a long-tailed distribution. For the co-purchase networks, we set the training ratio to 10% and sample nodes for each class to follow a long-tailed distribution. The remaining data is split into a 1:8 ratio for validation and testing. Unlike the citation datasets, the co-purchase datasets are naturally imbalanced, meaning that their validation and test sets are also highly imbalanced. More details on the data sets are available in Appendix 9.

We compare our model against eleven established baselines, which are categorized into three groups: (1) Traditional methods, which include the vanilla approach using conventional cross-entropy loss and GRAND [26], which utilizes unlabeled nodes to enhance model training; (2) Algorithm-level methods, consisting of Re-weight [13], Balanced Softmax [14], PC Softmax [15], ReNode [16], TAM [9], ReVar [40], and BAT [42]; (3) Data-level methods, including GraphENS [19] and GraphSHA [20]. To ensure a comprehensive evaluation, we integrate TAM with Balanced Softmax, ReNode, and GraphENS. Detailed descriptions of baselines and their hyper-parameter configurations are in Appendix 10.

In this study, we deploy both our proposed model and the selected baselines across three representative GNN architectures: GCN [3], GAT [5], and GraphSAGE [4]. Nodes that are not part of the training set are treated as unlabeled in our setting. For the evaluation of model performance, we employ three metrics: Accuracy (Acc.), balanced Accuracy (BAcc.), and the Macro F1 score (Macro F1). All these metrics are scaled between 0 and 1, where higher values represent better model performance. We conduct ten independent runs for each method and report the average score and the standard error for a robust statistical analysis. More details about the evaluation process are provided in Appendix 11.

5.2 Model Performance↩︎

The results in Table ¿tbl:table:main95imb9550? demonstrate that our model consistently surpasses the current state-of-the-art methods across various GNN backbones, achieving significant improvements. This can be attributed to our model’s capacity to identify valuable unlabeled nodes for enhancing the training set and effectively address class imbalance by integrating high-quality synthetic nodes into minority classes. Notably, our model’s performance remains consistent across different GNN architectures, indicating reduced dependency on the underlying GNN structures.

Furthermore, our evaluation reveals that node oversampling strategies, such as GraphENS [19] and GraphSHA [20], generally yield better results compared to algorithm-level techniques. Among algorithm-level approaches, Balanced Softmax [14] and PC Softmax [15] prove to be effective in most scenarios. When comparing GRAND [26] to the vanilla approach, we observe that leveraging unlabeled nodes can boost performance in some cases, highlighting their potential to mitigate class imbalance. However, in most instances, the vanilla approach outperforms GRAND, suggesting that careful handling of unlabeled nodes is crucial under class imbalance conditions to avoid negative impacts on model performance. The results in terms of accuracy are deferred to Appendix 12.2.

Figure 2 illustrates the behavior of various methods under different imbalance ratios (\(\text{IR}\in\{5,20,50\}\)). As the imbalance ratio decreases, the performance gap in Macro F1 scores among different methods narrows. Conversely, as the imbalance ratio increases, our model’s superiority becomes more pronounced, demonstrating its effectiveness in handling highly imbalanced problems. Even with a small imbalance ratio, our model delivers slight performance improvements, likely due to the integration of valuable unlabeled and synthetic nodes, which helps regularize model training. Results for other metrics, which are available in Appendix 12.3, exhibit a similar trend.

5.3 Model Analysis↩︎

We conduct a comprehensive analysis of various facets of NodeImport. However, due to space limitations, here we focus on presenting the ablation study, analysis of the meta-set construction method, and a case study on per-class F1 scores. For further details, additional experimental results are provided in Appendix 12, including evaluations on a large-scale dataset (Appendix 12.1), a sensitivity analysis of hyper-parameters (Appendix 12.4), and a case study on the class distribution of filtered labeled nodes (Appendix 12.5).

2pt

We evaluate the contributions of the three main components introduced in Section 4.2. Table ¿tbl:table:main95component95effectiveness? presents the results of an ablation study that assesses the individual and combined impacts of each component. When component 1 is excluded, we train with all labeled nodes without filtering. The results confirm the importance of all three components in enhancing the model’s capacity to address class imbalance in graphs. Each component individually improves performance, with component 3 (synthetic nodes) generally providing the most significant enhancement. This improvement is likely due to the introduction of diverse patterns into minority classes during node synthesis, which helps balance the class distribution. Furthermore, the combination of components 2 and 3 nearly matches the performance of the full model. Adding component 1 to this combination offers a modest incremental benefit, usually within a one-percent range.

We evaluate the effectiveness of our meta-set construction method proposed in Section 4.3 by comparing it with three alternatives: Random sampling, ReNode [16] (which uses Totoro metrics to select top-ranked nodes), and CoreSet [64] (which iteratively selects nodes farthest from current selections). Results in Figure 3 show that our proposed method consistently outperforms the other techniques across all metrics. Notably, Random sampling and ReNode exhibit similar performance levels, while CoreSet performs the worst. The inferior performance of CoreSet is likely due to the inclusion of many outliers in the meta-set, which negatively impacts the performance.

2pt

Table 2 presents the per-class F1 scores on the Cora dataset using the GraphSAGE architecture. Baseline methods designed to mitigate class imbalance demonstrate improvements in F1 scores for both minority and majority classes, indicating that addressing class imbalance can refine decision boundaries and benefit all classes. Our model not only achieves the most significant improvements across most classes but also substantially reduces the performance gap between minority and majority classes. Notably, the improvement from our method is particularly pronounced in smaller classes, such as \(C_0\), \(C_1\), and \(C_6\). Compared to the Vanilla method, the GRAND method shows a sharp decrease in the F1 score for the smallest class, \(C_6\). This suggests that directly using unlabeled nodes for model training without considering class imbalance can lead to the misclassification of unlabeled nodes from extremely small classes like \(C_6\), further exacerbating the class imbalance issue.

6 Conclusions↩︎

In this work, we introduce NodeImport, a framework for class-imbalanced node classification. Our method dynamically evaluates node importance and incorporates key nodes into the training process to address class imbalance. We develop an efficient formula for assessing node importance and a framework for selecting high-quality labeled, unlabeled, and synthetic nodes. Additionally, we extract representative meta-samples from the training set. Experiments on benchmark datasets demonstrate that NodeImport outperforms state-of-the-art methods, effectively mitigating class imbalance in node classification tasks.

7 Proofs for Theoretical Analysis↩︎

In this section, we present theoretical proofs for the equations used in the manuscript.

7.1 Gradient Derivation of the Cross-Entropy Loss Function↩︎

To derive Eq. 6 , we need to find the derivative of the cross-entropy loss function \(L[\cdot]\), as defined in Eq. 7 , with respect to the model parameters \(\theta\). More generally, when dealing with a subset of \(p\) nodes represented by \(\tilde{A} \in \mathbb{R}^{p\times n}\) and their associated labels \(Y \in [0,1]^{p\times c}\), the computation of the loss function can be broken down into several steps. At the first step, we calculate the output logits of the GNN encoder \(S\in \mathbb{R}^{p\times c}\): \[S = \tilde{A} X \theta\] Next, we employ element-wise exponential operation to \(S\) and obtain \(E\in \mathbb{R}^{p\times c}\): \[E = \text{exp}(S)\] Then, we normalize \(E\) along each row and get \(H\in \mathbb{R}^{p\times c}\), which can be seen as the softmax of the output logits \(S\): \[H = E \oslash EJ\] where \(\oslash\) denotes the Hadamard division and \(J\in\mathbb{R}^{c\times c}\) represents an all-one matrix. After that, we apply the element-wise logarithm to \(H\) and get \(Z \in \mathbb{R}^{p\times c}\) \[Z = \text{log}(H)\] Finally, the cross-entropy loss \(L\) is calculated as follows: \[\label{eq:loss95formula} L = - \langle Y, Z\rangle_F\tag{17}\] where \(\langle \cdot,\cdot \rangle _F\) denotes the Frobenius inner product. For simplicity, the symbol \(:\) can be used to represent the Frobenius inner product \(\langle \cdot,\cdot \rangle _F\). Henceforth, these two symbols will be used interchangeably to indicate the Frobenius inner product.

Since directly computing the derivatives \(\nabla\) is intractable and unrealistic, we choose to work in the differential form ². In particular, starting from the cross-entropy loss (Eq. 17 ), we have: \[\label{eq:first95diff} dL = -Y : dZ\tag{18}\] Next, \[dZ = dH \oslash H\] Then, \[\begin{align} dH &= dE \odot EJ \oslash EJ \oslash EJ - d(EJ) \odot E \oslash EJ \oslash EJ \\ &= dE \oslash EJ - (dE)J \odot H \oslash EJ \\ \end{align}\] where \(\odot\) represents the Hadamard product. After that, \[\begin{align} dE &= E \odot dS \end{align}\] Finally, \[\label{eq:last95diff} \begin{align} dS &= \tilde{A} X d\theta \end{align}\tag{19}\] Putting Eq. 18 to Eq. 19 together, we have the following: \[\begin{align} dL &= -Y : dZ \\ &= -Y : dH \oslash H \\ &= -Y : (dE \oslash EJ - (dE)J \odot H \oslash EJ) \oslash H \\ &= -Y : ((E \odot dS) \oslash EJ - (E \odot dS)J \odot H \oslash EJ) \oslash H \\ &= -Y : (E \odot dS) \oslash EJ \oslash H - (E \odot dS)J \oslash EJ) \\ &= -Y : dS - (E \odot dS)J \oslash EJ) \\ &= -Y : dS + Y : (E \odot dS)J \oslash EJ \\ &= -Y : dS + (Y \oslash EJ)J \odot E : (dS) \\ &= ((Y \oslash EJ)J \odot E -Y) : (dS) \\ &= ((Y \oslash EJ)J \odot E -Y) : \tilde{A} X d\theta \\ &= (\tilde{A} X)^T((Y \oslash EJ)J \odot E -Y) : d\theta \\ \end{align}\] In this way, we can get the gradient \(\nabla L\) of the loss function in terms of the denominator layout: \[\label{eq:matrix95gradient951} \begin{align} \nabla_\theta L&= \frac{dL}{d\theta} \\ &= (\tilde{A} X)^T((Y \oslash EJ)J \odot E -Y) \end{align}\tag{20}\] Given that \(Y\) is the label matrix with each row as a one-hot vector, we can simplify Eq.@eq:eq:matrix95gradient951 and get: \[\label{eq:matrix95gradient952} \begin{align} \nabla_\theta L &= (\tilde{A} X)^T(H-Y) \\ \end{align}\tag{21}\] Hence, the proof is complete.

8 Algorithm↩︎

Algorithm [alg:main95algorithm] describes our approach. First, in lines 1-8, we derive the aggregation matrix and apply the PAM algorithm to each class’s context embedding space to create a balanced meta-set. In lines 10-19, we generate synthetic nodes using a MixUp-like method. Subsequently, in lines 20-21, we assign pseudo-labels to the unlabeled nodes based on the highest predicted probabilities. In lines 22-24, we compute the importance scores of the nodes and filter out the important ones according to these scores. Lastly, in lines 25-29, we apply the cross-entropy loss to the filtered nodes and update the GNN model accordingly.

Compared to the backbone GNN model, our algorithm adds additional computations in three main areas: meta-set construction (lines 1-8), synthetic node generation (lines 10-19), and node importance computation (lines 22-24). We will examine each part individually and elaborate on their impact on computational overhead. Let \({\mathcal{V}}_{tr}\) represent the set of nodes within the training set \(D_{tr}\), and \({\mathcal{V}}_{ul}\) denote the set of unlabeled nodes.

• Meta-set construction. The adjacency matrix \(A\) is sparse with \(|\mathcal{E}|\) non-zero elements, the degree matrix \(D\) is diagonal, and the feature matrix \(X\) is dense. Thus, computing the context embedding \(\tilde{A}X\) involves sparse-dense matrix multiplications, with a complexity of \(\mathcal{O}(K|\mathcal{E}|d)\) where \(K\) is the number of steps and \(d\) is the feature dimension. Running the PAM algorithm on a class of size \(|\mathcal{V}^{k}|\) for \(\tau\) meta-samples incurs a complexity of \(\mathcal{O}(\tau^2|\mathcal{V}^{k}|^2)\). Therefore, the overall complexity of the meta-set construction procedure is \(\mathcal{O}(K|\mathcal{E}|d+\sum_{c\in\mathcal{C}}\tau|\mathcal{V}_c^{L}|^2)\).

• Synthetic node generation. The number of synthetic nodes generated per class is \(\mathcal{O}(|\mathcal{V}_{tr}|)\). The process begins with sampling pairs of nodes, which incurs a complexity of \(\mathcal{O}(|\mathcal{V}_{tr}|^2)\). For each sampled pair, generating synthetic node features and labels involves simple arithmetic operations with a complexity of \(\mathcal{O}(|\mathcal{V}_{tr}|d)\). Furthermore, generating edges for these synthetic nodes to maintain the original degree distribution of the graph has a complexity of \(\mathcal{O}(|\mathcal{V}_{tr}| \cdot \bar{d})\), where \(\bar{d}\) represents the average degree of the graph. Therefore, the overall complexity of producing synthetic nodes is \(\mathcal{O}(|\mathcal{V}_{tr}|^2+|\mathcal{V}_{tr}|d+|\mathcal{V}_{tr}| \cdot \bar{d})\).

• Node importance computation. Given that the amount of synthetic nodes is \(\mathcal{O}(|\mathcal{V}_{tr}|)\) and these synthetic edges maintain the original degree distribution, the augmented graph with synthetic nodes consists of \(\mathcal{O}(|\mathcal{E}|)\) edges. Moreover, generating pseudo-labels for unlabeled nodes requires a complexity of \(\mathcal{O}(|\mathcal{V}_{ul}|c)\). Calculating node importance scores requires computing the context embedding for the augmented graph, which incurs a complexity of \(\mathcal{O}(K|\mathcal{E}|d)\), and performing dense matrix multiplications and element-wise operations, which incurs a complexity of \(\mathcal{O}(|\mathcal{V}|d\cdot c\tau+|\mathcal{V}|c^2\tau)\). Consequently, the complexity to determine node importance is \(\mathcal{O}(K|\mathcal{E}|d+|\mathcal{V}_{ul}|c+|\mathcal{V}|d\cdot c\tau+|\mathcal{V}|c^2\tau)\).

Given that \(|\mathcal{E}|\gg|\mathcal{V}_{tr}|\) and \(c\), \(\tau\), and \(d\) are typically small constants, in a class-imbalanced node classification scenario, the added overhead for \(T\) training epochs is simplified to \(\mathcal{O}(T \cdot K|\mathcal{E}|d)\), which scales linearly with the number of graph edges. Therefore, the computational overhead is comparable to that of the primary GNN model, resulting in a lightweight additional computation.

9 Descriptions of Datasets↩︎

Our experiment adopts five commonly used benchmark datasets: three citation graphs and two Amazon co-purchase graphs. The dataset statistics are listed in Table 1. In our implementation, we load these datasets via the PyTorch Geometric library [65].

• Cora, CiteSeer, and PubMed [30]: These three citation datasets consist of nodes representing academic papers and edges indicating the citation links. In Cora and CiteSeer, node features are binary vectors indicating the presence of specific words, whereas in PubMed, they are represented by TF/IDF weighted word vectors. The objective of these datasets is to classify papers into their respective categories. These datasets are publicly accessible at https://github.com/kimiyoung/planetoid/raw/master/data. For each citation dataset, we use the ten public splits created by  [63].

• Amazon-Photo and Amazon-Computer [31]: These two co-purchase datasets consist of nodes representing goods and edges representing frequent co-purchase patterns between pairs of products. Node features in these datasets are encoded as bag-of-words representations derived from corresponding product reviews. The objective of these datasets is to classify products into their respective categories. These datasets are publicly accessible at https://github.com/shchur/gnn-benchmark/raw/master/data.

10 Descriptions of the Baselines↩︎

This section will introduce baselines used in more detail and their hyper-parameter configurations.

• Graph Random Neural Networks (GRAND) [26]: This approach employs consistency regularization to ensure consistent model predictions across various augmented versions of an unlabeled node. These versions are created through data augmentation, and the average of their prediction outcomes is used as the pseudo-label for the unlabeled node. In the experiments, the sharpening temperature is set to 0.5, the scale of the unlabeled loss is set to 1, and the augmentation sampling for each unlabeled node occurs 4 times.

• Re-weight [13]: In this approach, higher weights are assigned to samples from minority classes. During the experiment, the weight of each sample is inversely proportional to the number of training samples in its class.

• Balanced Softmax [14]: This approach seeks to reduce the distribution shift between the training and test data. It adjusts the output logits by adding the logarithm of the class size before applying Softmax to calculate the cross-entropy loss.

• Post-Compensated Softmax (PC Softmax) [15]: This approach disentangles the training label distribution from model predictions and incorporates the testing label distribution into the disentangled predictions. It adjusts the output logits during the inference stage by subtracting the logarithm of the class size before applying Softmax.

• ReNode [16]: This work devises a re-weighting strategy based on nodes’ relative topological positions within their classes. Nodes closer to the topological class centers tend to receive higher weights, while those near class boundaries will receive lower weights. In the experiment, the cosine annealing lower bound \(w_{min}\) is set to 0.5, and the upper bound \(w_{max}\) is set to 1.5. The teleport probability \(\alpha\) in the PageRank is set to 0.15.

• Topology-Aware Margin (TAM) [9]: This approach adjusts the logits of training nodes when computing the loss function using two types of margins. The Anomalous Connectivity Margin (ACM) accounts for a node’s neighbor label distribution and the average connectivity patterns within its class. The Anomalous Distribution-aware Margin (ADM) considers a node’s relative distance to other classes compared to its own class based on neighbor label distribution. In the experiment, we integrate TAM with Balanced Softmax, ReNode, and GraphENS for a comprehensive evaluation. We set the coefficient of the ACM term \(\alpha\) to 2.5, the coefficient of the ADM term \(\beta\) to 0.5, the minimum temperature of the class-wise temperature \(\phi\) to 1.2, and the warmup period to 5 iterations.

• Regularize Variance (ReVar) [40]: This work leverages data augmentation to estimate model variance and uses the estimated variance as a regularization term during training. The two intensity terms \(\lambda_1\) and \(\lambda_2\) are set to \(0.25\) and \(2.85\), respectively.

• BAlanced Topological augmentation (BAT) [42]: This work addresses class imbalance by identifying and correcting nodes with ineffective message passing due to topological disparities. We adapt BAT with 1st-order estimation during experiment.

• GraphENS [19]: This over-sampling method generates new minority nodes by combining nodes from minority classes with other nodes based on their similarity, preserving the semantics of the minority classes. It also uses a gradient-based approach to determine the importance of each feature dimension to model prediction and randomly masks important feature dimensions during feature mixing. In the experiment, the mixing ratio \(\lambda\) is sampled from a \(\text{Beta}(2,2)\) distribution, the feature masking hyperparameter \(K\) is set to 1, the prediction temperature \(\tau\) is set to 2, and the warmup period is set to 5 iterations.

• GraphSHA [20]: This method synthesizes new nodes by combining minority nodes (anchors) with other nodes (auxiliaries). The sampling of node pairs is based on the predictive output from the GNN encoder. Each synthetic node’s features are generated through a convex combination of features. Edges are sampled only from the anchor node to construct the new neighborhood, utilizing a smoothed version of the adjacency matrix via graph diffusion-based smoothing. In the experiment, the mixing ratio \(\delta\) is sampled from a \(\text{Beta}(1,100)\) distribution. The Personalized PageRank (PPR) version of the adjacency matrix is used, and the temperature \(T\) of the SoftMax function is set to 2 for the calculating model confidence.

11 Deatials on the Evaluation Process↩︎

11.1 Experimental Environment↩︎

We conducted all experiments on a server running Ubuntu 22.04.3, equipped with a 2.90GHz Intel Xeon Gold 6226R CPU, 512GB of RAM, and 8 NVIDIA GeForce RTX 3090 GPUs, each with 24GB of memory. Our model is implemented using Python 3.8.0, PyTorch 1.13.0 with CUDA 11.7, and PyTorch Geometric 2.4.0. Additional libraries used include scikit-learn and scikit-learn-extra.

11.2 Configurations of GNN Backbones↩︎

• Graph Convolutional Network (GCN) [3]: The network is built with two GCN layers, with a hidden dimension of 256. Following the first convolutional layer, a ReLU activation function is used, coupled with a dropout layer with a dropping rate of 0.5.

• Graph Attention Networks (GAT) [5]: The network is constructed with two GAT layers, with a hidden dimension size of 256. The multi-head attention mechanism is applied, with the number of heads set to 4. Following the first convolutional layer, a ReLU activation function is used, coupled with a dropout layer with a dropping rate of 0.5.

• Graph Sample and AggregatE (GraphSAGE) [4]): The network is structured with two SAGE layers, with a hidden dimension size of 256. The mean aggregator is used to aggregate neighboring features. Following the first convolutional layer, a ReLU activation function is utilized, coupled with a dropout layer with a dropping rate of 0.5.

11.3 Configuration of Our Model↩︎

For the computation of the aggregation matrix \(\tilde{A}\), the depth \(K\) is selected from \(\{2,4,8,16\}\)m and the teleport probability \(\alpha\) is selected from \(\{0.05, 0.10, 0.15, 0.20\}\). The scaling factors for the losses of the unlabeled and synthetic nodes, \(\beta\) and \(\gamma\), are selected from \(\{0.5, 1.0, 2.0, 4.0\}\). We control the number of meta-samples per class to around \(40\%\) of the smallest class in the training set.

11.4 Training Details↩︎

All methods are trained for 2000 epochs, and the parameters of GNN backbones are optimized via the Adam optimizer [66]. The initial learning rate is set to 0.01, subject to a halving adjustment upon observing no improvement over 100 epochs in terms of the validation loss. Except for parameters in the final graph convolutional layer, a weight decay of 0.0005 is applied to all learnable parameters. The average of accuracy and macro F1 score on the validation set is employed to select the final model for testing.

12 Additional Experimental Results↩︎

12.1 Experiments with a large-scale dataset↩︎

In this subsection, we evaluate our method on the large-scale arXiv dataset from the OGB benchmark [67], summarized in Table ¿tbl:table:ogbn95data95statistics?. Due to its size, data-level methods like GraphENS and GraphSHA encounter memory limitations, and our full model faces similar issues with C3 due to node synthesis. As a result, we evaluated our model using only C1 and C2. Table ¿tbl:table:ogbn95performance? presents the results in terms of balanced accuracy, execution time, and peak GPU memory usage. Despite the absence of C3, our model demonstrates competitive performance, with execution time and memory usage comparable to the vanilla method. The ogbn-arxiv dataset also poses unique challenges for class-imbalanced node classification, including an extremely long-tailed distribution and varying majority and minority class compositions across the train, validation, and test sets, highlighting its potential for further investigation.

12.2 Overall Performance in Terms of Accuracy↩︎

Table ¿tbl:table:main95imb955095acc? lists the model performance against selected baselines in terms of the accuracy metric. The result is consistent with that discussed in Section 5.2.

12.3 Performance Trends Under Different Imbalance Ratios↩︎

Figure 4 and Figure 5 present the performance trends of different methods under various imbalance ratios in terms of the accuracy and balanced accuracy metrics, respectively. These findings align with the discussions presented in Section 5.2.

12.4 Hyper-Parameters Sensitivity↩︎

This analysis examines how the two scaling factors \(\beta\) and \(\gamma\) of the loss function in Eq. 16 affect the model performance. Specifically, we explore a range of values for \(\beta\) and \(\gamma\): {0.1, 0.5, 1.0, 2.0, 4.0}, and assess the performance for each pairing of these factors. The results, as shown in Figure 6, illustrate that the model maintains stable performance when \(\beta\) and \(\gamma\) are set around \(1.0\). However, as these parameters increase far beyond this point, a noticeable decrease in performance is observed. This decline is likely due to the model overfitting, where excessively high scaling factors disproportionately amplify the unlabeled or synthetic losses, thus degrading the capability of the model.

Furthermore, we evaluate the impact of meta-set size on model performance, as shown in Figure 7, which presents the results in terms of balanced accuracy. The findings indicate that moderate-sized meta-sets achieve better overall performance.

12.5 Class Distribution of the Filtered Labeled Nodes↩︎

Figure 8 shows the cumulative class distribution of the filtered labeled nodes over training epochs for the Cora (GraphSAGE) and CiteSeer (GAT) datasets. At each epoch, we count the number of nodes on which the model is trained for each class up to that point and normalize these counts among the classes to represent their relative proportions. In the Cora dataset (Figure 8a), the majority classes (Red and Green lines) are progressively down-sampled, as indicated by the decreasing trends. In contrast, minority classes (e.g., Brown and Blue lines) are up-sampled, showing increasing trends. Similarly, in the CiteSeer dataset (Figures 8b), the majority classes (Red and Green lines) are down-sampled, while minority classes (e.g., Brown and Orange lines) are up-sampled. In addition, the extent of up-sampling and down-sampling varies across classes, demonstrating our model’s capability to dynamically adjust the training label distribution and effectively address node imbalance.

References↩︎

---

1. \(^*\)The corresponding authors.↩︎

2. We draw the inspiration from this blog https://math.stackexchange.com/a/3850121/1237687↩︎