arXiv:2607.13837v1 [cs.LG] 15 Jul 2026
NodeImport: Imbalanced Node Classification with Node Importance Assessment Nan Chen
Zemin Liu∗
Bryan Hooi
Johns Hopkins University Baltimore, Maryland, USA [email protected]
Zhejiang University Hangzhou, Zhejiang, China [email protected]
National University of Singapore Singapore, Singapore [email protected]
Bingsheng He∗
Jun Hu
Jia Chen
National University of Singapore Singapore, Singapore [email protected]
National University of Singapore Singapore, Singapore [email protected]
Grabtaxi Holdings Pte Ltd Singapore, Singapore [email protected]
Abstract
CCS Concepts
In real-world applications, node classification on graphs often faces the challenge of class imbalance, where majority classes dominate training, resulting in biased model performance. Traditional Graph Neural Networks (GNNs) often struggle in such scenarios, as they tend to overfit to majority classes while underrepresenting minority classes. Existing solutions, which either prioritize nodes based on class size or synthesize new nodes for minority classes, often fall short of effectively addressing this imbalance issue. This paper introduces a novel approach to class-imbalanced node classification by utilizing a balanced meta-set for importance measurement, where a training node is considered significant if it enhances model performance under an unbiased setting. Our method identifies important nodes that can counteract class imbalance and utilizes them for model training, allowing for fine-grained and dynamic node selection throughout the training process. We theoretically derive a formula to directly assess node importance, reducing computational overhead and providing an intuitive threshold for node selection. Guided by this metric, we develop a novel framework that filters valuable labeled, unlabeled, and synthetic nodes that enhance model performance in an unbiased context. A key advantage of this framework is its separation of the synthetic node generation process from the filtering process, ensuring compatibility with various node generation techniques. Furthermore, we introduce a strategy to construct a high-quality meta-set that closely approximates the overall feature distribution, ensuring robust representation of each class. We evaluate our framework, NodeImport, across multiple benchmark datasets using popular GNN architectures, demonstrating its superiority over state-of-theart baselines. Our results highlight the flexibility and effectiveness of the framework in mitigating class imbalance, leading to improved node classification outcomes. The source code is available at https://github.com/NanChanNN/NodeImport.
• Computing methodologies → Learning latent representations; Neural networks; • Mathematics of computing → Graph algorithms.
∗ The corresponding authors.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). KDD ’25, August 3–7, 2025, Toronto, ON, Canada © 2025 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-1245-6/25/08 https://doi.org/10.1145/3690624.3709215
Keywords Graph Neural Networks; Node Classification; Class Imbalanced Learning ACM Reference Format: Nan Chen, Zemin Liu∗ , Bryan Hooi, Bingsheng He∗ , Jun Hu, and Jia Chen. 2025. NodeImport: Imbalanced Node Classification with Node Importance Assessment. In Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V.1 (KDD ’25), August 3–7, 2025, Toronto, ON, Canada. ACM, New York, NY, USA, 16 pages. https://doi.org/10.1145/ 3690624.3709215
1
Introduction
Graph data is prevalent across many domains, making graph analysis, particularly node classification, a significant research focus [2, 54]. With the rise of deep learning, Graph Neural Networks (GNNs) [16, 23, 49, 55] 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 [6, 47, 64, 65, 67]. 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 [30]. 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 [5, 18, 20, 39, 47]. 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
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
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 [58], 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 [26, 28, 36, 53, 64]. Most methods follow a MixUp-like style [50, 61], 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 [1, 11, 46, 65]. 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 [34, 39, 40, 45]: 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 timeconsuming, 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
Nan Chen et al.
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 [23], GAT [49], and GraphSAGE [16]. This evaluation utilizes multiple benchmark datasets, comprising three citation datasets [59] and two Amazon co-purchase datasets [42], under a long-tailed imbalance setting [9]. 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
Class imbalance classification. Existing solutions to the class imbalance problem can be broadly categorized into algorithm-level and data-level approaches [30]. 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 [9, 15, 20, 27, 56] or by expanding the margins for minority classes [3, 18, 33, 39, 48]. 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 [47] and ReNode [5], consider a node’s topological
NodeImport: Imbalanced Node Classification with Node Importance Assessment
location when assigning weights, their weights do not dynamically adapt to the model’s status during training. Other algorithmlevel approaches include imposing additional regularization constraints [43, 57], employing multi-expert training with knowledge distillation [60], or by correcting nodes with ineffective message passing caused by topological disparities. [31]. Data-level techniques balance class sizes through resampling [8, 29, 60, 63] or generative methods [4, 38, 51]. In the graph domain, most works [26, 28, 36, 53, 64] adopt MixUp-like [50, 61] 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 [65] 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 [17, 25, 30, 32, 62]. Meta-set guided data selection. In the image domain, several works employ a balanced meta-set to learn instance-wise weights [40, 45] or class-wise sampling rates [39] 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 [21, 24, 34], 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 [34], 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
Graph representation learning. A graph 𝐺 is represented as G = {V, E, 𝑋 }, where V is the set of 𝑛 nodes, E ⊆ V × V is the set of edges, and 𝑋 ∈ R𝑛×𝑑 is the node feature matrix with each row 𝑥 𝑣 ∈ R𝑑 being the feature vector for node 𝑣 ∈ V. The graph structure can also be described by an adjacency matrix 𝐴 ∈
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
{0, 1}𝑛×𝑛 , where 𝐴𝑖,𝑗 = 1 if there is an edge ⟨𝑖, 𝑗⟩ and 𝐴𝑖,𝑗 = 0 otherwise. Each node 𝑣 is associated with a one-hot encoded label vector 𝑦 𝑣 ∈ {0, 1}1×𝑐 over 𝑐 classes, and 𝑌 ∈ {0, 1}𝑛×𝑐 is the label matrix containing these label vectors. Given a graph encoder 𝑔(·; 𝜃 ) with parameters 𝜃 (e.g., a GNN model), nodes within the graph can be mapped into probability distributions 𝐻 ∈ R𝑛×𝑐 indicating the likelihood of each node belonging to different classes, formulated as 𝐻 = 𝑔(G; 𝜃 ). We denote the predictive distribution of the GNN model on node 𝑣 as 𝑝 (𝑦 𝑣 |𝑣; 𝜃 ) for the ease of analysis. Class-imbalanced node classification. 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 [44, 64]. The imbalance ratio 𝐼𝑅 = 𝑟 0 /𝑟 1 quantifies the degree of imbalance, where 𝑟 0 and 𝑟 1 represent the sizes of the largest and smallest classes, respectively [30]. The optimal parameters of the graph encoder 𝜃 ∗ are obtained by minimizing the cross-entropy loss on the training set D𝑡𝑟 = {(𝑣, 𝑦 𝑣 )} defined as: 𝜃 ∗ = arg min
Í
(𝑣,𝑦𝑣 ) ∈ D𝑡𝑟 −log 𝑝 (𝑦 𝑣 |𝑣; 𝜃 ).
(1)
𝜃
Here, we utilize 𝐿[𝑦 𝑣 |𝑣; 𝜃 ] = −log 𝑝 (𝑦 𝑣 |𝑣; 𝜃 ) to denote the crossentropy loss for an individual training point (𝑣, 𝑦 𝑣 ) ∈ D𝑡𝑟 . Importance assessment using meta-sets. We introduce an unbiased meta-set D𝑚𝑒𝑡𝑎 = {(𝑣 (𝑚𝑒𝑡𝑎) , 𝑦 𝑣(𝑚𝑒𝑡𝑎) )} with a balanced class distribution for evaluating node importance. For simplicity, this meta-set is written as 𝒗 (𝑚𝑒𝑡𝑎) and 𝒚 (𝑚𝑒𝑡𝑎) . The meta-set is usually much smaller than the training set (i.e., |D𝑡𝑟 | ≫ |D𝑚𝑒𝑡𝑎 |), and helps rectify the graph encoder in cases of imbalanced training data. Given a training point (𝑣, 𝑦 𝑣 ) ∈ D𝑡𝑟 , we define the following metric 𝜂 𝑣 to evaluate its importance to model training: 𝜂 𝑣 = log
𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ; (𝑣, 𝑦 𝑣 )) 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 )
= log 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ; (𝑣, 𝑦 𝑣 ))
(2)
− log 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ). Intuitively, this metric assesses whether the current model’s performance on the balanced meta-set improves after being trained on the given point. When 𝜂 𝑣 > 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 metaset 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 B.
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
Nan Chen et al.
Meta-set
Guide Training set
Meta-set selection
Labeled nodes
Neighbor sampling
Synthetic pool
Sample
Feature MixUp
Labeled nodes
Synthetic nodes
Filtering valuable Model training
nodes based on the importance metric 𝜼𝒗
Label MixUp "𝒗𝑿 𝑨 " 𝒎𝒆𝒕𝒂 𝑿 𝑻 𝑯𝒎𝒆𝒕𝒂 − 𝒀𝒎𝒆𝒕𝒂 𝒉𝒗 − 𝒚𝒗 𝑻 𝑨
Pseudo-label generation
Unlabeled nodes
Unlabeled nodes with pseudo-labels
Figure 1: The structure of the proposed framework. The blue, green, and red sections indicate component 1, 2, and 3, respectively.
4.1
Tractable Importance Metric for Node Selection
Following [34], we employ Bayesian probability theory to derive a more tractable form of Eq. 2. By applying Bayes’ theorem and assuming conditional independence, 𝑝 (𝑦 𝑣 |𝑣, 𝑢; 𝜃 𝑡 ) = 𝑝 (𝑦 𝑣 |𝑣; 𝜃 𝑡 ), we arrive at the following equation:
− log 𝑝 (𝒚
|𝒗
(𝑚𝑒𝑡𝑎)
𝑝 (𝑦 𝑣 |𝑣; 𝒗 (𝑚𝑒𝑡𝑎) , 𝒚 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ) · 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ) 𝑝 (𝑦 𝑣 |𝑣; 𝜃 𝑡 )
Assumption 4.1. We update the current model weights 𝜃 𝑡 on the meta-set D𝑚𝑒𝑡𝑎 through one gradient descent step to obtain 𝜃ˆ𝑡 , meaning that 𝜃ˆ𝑡 = 𝜃 𝑡 −𝜅 · ∇𝜃 𝐿[𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ] where 𝜅 is a predefined learning rate. Therefore, Δ = −𝜅 · ∇𝜃 𝐿[𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ].
− log 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ) = log 𝑝 (𝑦 𝑣 |𝑣; (𝒗 (𝑚𝑒𝑡𝑎) , 𝒚 (𝑚𝑒𝑡𝑎) ); 𝜃 𝑡 ) − log 𝑝 (𝑦 𝑣 |𝑣; 𝜃 𝑡 ), (3) where the second equation applies Bayes’ theorem to decompose 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ; (𝑣, 𝑦 𝑣 )), 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 (𝑣, 𝑦 𝑣 ) between the current model and the one updated with the meta-set. Let 𝜃ˆ𝑡 denote the parameters of the updated model, we have: 𝜂 𝑣 = log 𝑝 (𝑦 𝑣 |𝑣; 𝜃ˆ𝑡 ) − log 𝑝 (𝑦 𝑣 |𝑣; 𝜃 𝑡 ) = 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] − 𝐿[𝑦 𝑣 |𝑣; 𝜃ˆ𝑡 ],
= 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] − (𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] + ⟨∇𝜃 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ], Δ⟩𝐹 + 𝑜 (Δ2 )) (5) where ∇𝜃 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] is the gradient of the individual loss function with regard to weights 𝜃 at 𝜃 𝑡 , and ⟨·, ·⟩𝐹 represents the Frobenius inner product. To get a cheaper estimate of parameter updates Δ, we assume that a single optimization step is taken for model 𝜃 𝑡 on the meta-set D𝑚𝑒𝑡𝑎 , which gives the following assumption.
; 𝜃𝑡 )
𝑝 (𝑦 𝑣 |𝑣; 𝒗 (𝑚𝑒𝑡𝑎) , 𝒚 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ) · 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) , 𝑣; 𝜃 𝑡 ) = log 𝑝 (𝑦 𝑣 |𝑣, 𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ) (𝑚𝑒𝑡𝑎) (𝑚𝑒𝑡𝑎) − log 𝑝 (𝒚 |𝒗 ; 𝜃𝑡 ) = log
𝜂 𝑣 = 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] − 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 + Δ] ≈ −⟨∇𝜃 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ], Δ⟩𝐹 ,
𝜂 𝑣 = log 𝑝 (𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ; (𝑣, 𝑦 𝑣 )) (𝑚𝑒𝑡𝑎)
Suppose that 𝜃ˆ𝑡 = 𝜃 𝑡 + Δ, where Δ represents the parameter updates based on the meta-set, we employ a first-order Taylor series expansion to express 𝐿[𝑦 𝑣 |𝑣; 𝜃ˆ𝑡 ] in terms of 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] and turn Eq. 4 into the following format:
(4)
where, in the second equation, we adopt the definition of crossentropy loss on point (𝑣, 𝑦 𝑣 ). 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.
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 [10, 13, 40, 45]: 𝜂 𝑣 ≈ 𝜅 · ⟨∇𝜃 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ], ∇𝜃 𝐿[𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ]⟩𝐹 .
(6)
To obtain a more explicit expression of the cross-entropy loss function 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ], we make the following assumption about the architecture of the GNN encoders used for ease of analysis. Assumption 4.2. We assume that the GNN encoder in use follows ˜ ), where 𝐴˜ ∈ R𝑛×𝑛 is the aggrethe format 𝐻 = SoftMax(𝐴𝑋𝜃 gation matrix, 𝜃 ∈ R𝑑 ×𝑐 the model parameters, and 𝐻 ∈ R𝑛×𝑐 the output of the model. Note that the aggregation matrix 𝐴˜ is not necessarily equivalent to the adjacency matrix 𝐴; it can be any polyÍ∞ 1 1 nomial of 𝐴, such as 𝑘=0 𝛾𝑘 𝐴𝑘 in GPR-GNN [7], (𝐷 − 2 𝐴𝐷 − 2 ) 𝐾 in Í𝐾 1 1 SGC [52], or 𝐾1 𝑘=1 ((1 − 𝛼)(𝐷 − 2 𝐴𝐷 − 2 )𝑘 + 𝛼𝐼 ) in SSGC [66]. Given this assumption, the individual loss function 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] can be expressed in terms of the underlying GNN model. Let 𝐴˜ 𝑣 ∈
NodeImport: Imbalanced Node Classification with Node Importance Assessment
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
R1×𝑛 be the aggregation matrix associated with node 𝑣, we get: 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ] = −LogSoftMax(𝐴˜ 𝑣 𝑋𝜃 )𝑦𝑇𝑣 ,
(7)
where LogSoftMax represents the function that applies elementwise logarithm to the output of softmax. To proceed with the derivation of Eq. 6, it is necessary to compute the derivative of the crossentropy loss function 𝐿[·] defined in Eq. 7 with respect to the ˜ ), the derivative of model parameters 𝜃 . Given 𝐻 = SoftMax(𝐴𝑋𝜃 the cross-entropy loss with regard to model parameters 𝜃 is: ˜ )𝑇 (𝐻 − 𝑌 ). ∇𝜃 𝐿 = (𝐴𝑋
(8)
The detailed derivation of Eq. 8 is provided in Appendix A.1. In essence, we work in differential form to compute the derivative. Substituting Eq. 8 into Eq. 6 gives our final importance metric: 𝜂 𝑣 ≈ 𝜅 · ⟨∇𝜃 𝐿[𝑦 𝑣 |𝑣; 𝜃 𝑡 ], ∇𝜃 𝐿[𝒚 (𝑚𝑒𝑡𝑎) |𝒗 (𝑚𝑒𝑡𝑎) ; 𝜃 𝑡 ]⟩𝐹 = 𝜅 · tr((ℎ 𝑣 − 𝑦 𝑣 )𝑇 (𝐴˜ 𝑣 𝑋 )(𝐴˜𝑚𝑒𝑡𝑎 𝑋 )𝑇 (𝐻𝑚𝑒𝑡𝑎 − 𝑌𝑚𝑒𝑡𝑎 ))
(9)
= 𝜅 · (𝐴˜ 𝑣 𝑋 ) (𝐴˜𝑚𝑒𝑡𝑎 𝑋 )𝑇 (𝐻𝑚𝑒𝑡𝑎 − 𝑌𝑚𝑒𝑡𝑎 )(ℎ 𝑣 − 𝑦 𝑣 )𝑇 , where 𝐴˜𝑚𝑒𝑡𝑎 ∈ R𝑚×𝑛 , 𝐻𝑚𝑒𝑡𝑎 ∈ R𝑚×𝑐 , and 𝑌𝑚𝑒𝑡𝑎 ∈ [0, 1]𝑚×𝑐 represent the aggregation matrix, model prediction, and label matrix associated with nodes in the meta-set, respectively. Understanding the importance metric 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 (𝐴˜ 𝑣 𝑋 )(𝐴˜𝑚𝑒𝑡𝑎 𝑋 )𝑇 : This component measures the similarity between the node sample (𝑣, 𝑦 𝑣 ) and the meta-set D𝑚𝑒𝑡𝑎 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 (𝐻𝑚𝑒𝑡𝑎 −𝑌𝑚𝑒𝑡𝑎 )(ℎ 𝑣 −𝑦 𝑣 )𝑇 : This component evaluates the similarity in the prediction behavior of the model between the node sample (𝑣, 𝑦 𝑣 ) and the meta-set D𝑚𝑒𝑡𝑎 . 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 overrepresented 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 (𝐻𝑚𝑒𝑡𝑎 − 𝑌𝑚𝑒𝑡𝑎 ) 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. Instantiating the importance metric. In practice, we employ existing polynomials of the adjacency matrix 𝐴 (such as those used in APPNP [14] or SSGC [66]) to calculate the aggregation matrix 𝐴˜ 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.9, 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 [53, 64, 65]. 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. 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 D𝑙 = {(𝑣, 𝑦 𝑣 )} denote the set of labeled nodes. The set of valuable labeled nodes 𝐷˜ 𝑙 is defined as: 𝐷˜ 𝑙 = {(𝑣, 𝑦 𝑣 ) ∈ 𝐷𝑙 | 𝜂 𝑣 > 0}.
(10)
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 pseudolabel. For each unlabeled node 𝑣 ∈ D𝑢𝑙 , its pseudo-label 𝑦ˆ𝑣 is: 𝑦ˆ𝑣 = arg max ℎ 𝑣 [𝑘], 𝑘
(11)
where ℎ 𝑣 = 𝐻 [𝑣, :] ∈ R1×𝑐 is the prediction probability distribution of the current GNN model on node 𝑣. With the pseudo-label 𝑦ˆ𝑣 , we replace 𝑦 𝑣 in Eq.9 with it to compute the importance 𝜂 𝑣 for the unlabeled node. The filtered set of unlabeled nodes 𝐷˜ 𝑢𝑙 is then: 𝐷˜ 𝑢𝑙 = {(𝑣, 𝑦ˆ𝑣 ) | 𝑣 ∈ 𝐷𝑢𝑙 and 𝜂 𝑣 > 0}.
(12)
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 S = {⟨(𝑣𝑠 , 𝑦𝑠 ), (𝑣𝑡 , 𝑦𝑡 )⟩} from the training set. Specifically, nodes 𝑣𝑠 are sampled until each class reaches the maximum sample count among all classes in the training set, while nodes 𝑣𝑡 are sampled based on the probability 𝑝𝑡 (𝑢) defined as follows: 𝑝𝑡 (𝑢) =
log (|V𝑘 | + 1) Í . (|V𝑘 | + 1) 𝑐𝑗=1 log (|V𝑗 | + 1)
(13)
where 𝑘 is the label of node 𝑢 and |V𝑘 | stands for the subset of nodes with label 𝑘. This increases the likelihood of selecting nodes from minority classes for synthesis, thereby enriching their patterns within the training set. For each node pair ⟨(𝑣𝑠 , 𝑦𝑠 ), (𝑣𝑡 , 𝑦𝑡 )⟩ ∈ S, we generate a new node 𝑣𝑠𝑦𝑛 by employing MixUp [61] from three
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
Nan Chen et al.
Table 1: Statistics of datasets adopted in this work
aspects, namely feature, neighborhood, and label mixing: 𝑥 = 𝜆 · 𝑥𝑠 + (1 − 𝜆) · 𝑥𝑡 , 𝑠𝑦𝑛 (14) 𝐴′𝑠𝑦𝑛 = 𝜆 · 𝐴𝑠 + (1 − 𝜆) · 𝐴𝑡 , 𝑦𝑠𝑦𝑛 = 𝜆 · 𝑦𝑠 + (1 − 𝜆) · 𝑦𝑡 . where 𝜆 ∼ Beta(𝛼, 𝛼) represents the synthetic scale drawn from the ′ Beta distribution with the parameter 𝛼, and 𝐴𝑠𝑦𝑛 ∈ R1×𝑛 denotes ′ the combined adjacency matrix for nodes 𝑣𝑠 and 𝑣𝑡 . Since 𝐴𝑠𝑦𝑛 consists of real numbers, it must be converted into a discrete version. This involves sampling a specific number of neighbors for node ′ , resulting in a discrete form 𝐴 𝑣𝑠𝑦𝑛 based on 𝐴𝑠𝑦𝑛 𝑠𝑦𝑛 : ′ 𝐴𝑠𝑦𝑛 = Sample(𝐴𝑠𝑦𝑛 ),
(15)
where the probability of an item 𝐴𝑠𝑦𝑛 [𝑘] being one is proportional ′ [𝑘]. To maintain consistent deto the corresponding value in 𝐴𝑠𝑦𝑛 gree statistics as per common practice in prior research [26, 36], 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., D𝑠𝑦𝑛 = {(𝑣𝑠𝑦𝑛 , 𝑦𝑠𝑦𝑛 )}, based on the sampled node pairs S. Combining Eq. 9 and Eq. 14, we calculate the importance of a synthetic node 𝜂 𝑣𝑠𝑦𝑛 to determine whether to use it for training. Finally, we build a set of valuable synthetic nodes: 𝐷˜ 𝑠𝑦𝑛 = {(𝑣𝑠𝑦𝑛 , 𝑦𝑠𝑦𝑛 ) ∈ D𝑠𝑦𝑛 | 𝜂 𝑣𝑠𝑦𝑛 > 0}.
(16)
Training objective. The overall training objective L is defined as the sum of the cross entropy loss on high-quality labeled nodes L𝑙 , unlabeled nodes L𝑢𝑙 , and synthetic nodes L𝑠𝑦𝑛 : L = L𝑙 + 𝛽 · L𝑢𝑙 + 𝛾 · L𝑠𝑦𝑛 ,
(17)
where 𝛽 and 𝛾 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 𝑘 that can accurately reflect the distribution of the initial training pool V𝑘 . Let M𝑘 ⊆ V𝑘 denote the set of meta-samples for class 𝑘. We aim to find the optimal set M̃𝑘 by minimizing the following objective: Í M̃𝑘 = arg min M𝑘 | V1 | 𝑣 ∈ V𝑘 𝐷 (𝑣, M𝑘 ), (18) 𝑘 where 𝐷 (·, ·) represents the distance between a node 𝑣 and the meta-set M𝑘 . To calculate this distance, we exploit the context ˜ , which captures not only the embedding for the nodes, 𝐹 = 𝐴𝑋 nodes’ features but also their local structures. Let 𝑓𝑣 be the context embedding vector of a node 𝑣, and we define the distance 𝐷 (𝑣, M𝑘 ) between the node and the meta-set M𝑘 as: 𝐷 (𝑣, M𝑘 ) = min dist(𝑓𝑣 , 𝑓𝑢 ), 𝑢 ∈ M𝑘
(19)
where dist(·, ·) 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
Dataset
Nodes
Edges
Features
Classes
Cora CiteSeer PubMed Amazon-Photo Amazon-Computers
2,708 3,327 19,717 7,650 13,752
10,556 9,104 88,648 119,081 245,861
1,433 3,703 500 745 767
7 6 3 8 10
(PAM) algorithm [35] to identify meta-samples for each class. The meta-set utilized is then the union of meta-samples from each class: Ð (20) D𝑚𝑒𝑡𝑎 = {(𝑣, 𝑦 𝑣 ) | 𝑣 ∈ 𝑐𝑘=1 M̃𝑘 }. In the end, we exclude the meta-set D𝑚𝑒𝑡𝑎 from the training set D𝑡𝑟 to form the set of labeled nodes D𝑙 .
5 Experiments 5.1 Experimental Setup Datasets. We adopt five benchmark datasets, which consist of three citation networks (Cora, CiteSeer, and PubMed) [59] and two Amazon co-purchase networks (Amazon-Photo and AmazonComputers) [42]. Dataset statistics are summarized in Table 1. For all datasets, we set the imbalance ratio 𝐼𝑅 to 50 and construct a longtailed training set following [9]. For the citation datasets, we use the public data splits from [37] 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 C. Baselines. We compare our model against eleven established baselines, which are categorized into three groups: (1) Traditional methods, which include the vanilla approach using conventional crossentropy loss and GRAND [11], which utilizes unlabeled nodes to enhance model training; (2) Algorithm-level methods, consisting of Re-weight [20], Balanced Softmax [39], PC Softmax [18], ReNode [5], TAM [47], ReVar [57], and BAT [31]; (3) Data-level methods, including GraphENS [36] and GraphSHA [26]. 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 D. Evaluation protocol. In this study, we deploy both our proposed model and the selected baselines across three representative GNN architectures: GCN [23], GAT [49], and GraphSAGE [16]. 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 E.
NodeImport: Imbalanced Node Classification with Node Importance Assessment
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
GraphSAGE
GAT
GCN
Table 2: Performance comparison (%) on benchmark graphs with an imbalance ratio of 50. The best results are in bold. Models with performances within the standard error are statistically comparable.
5.2
Cora Macro F1
CiteSeer bAcc. Macro F1
PubMed bAcc. Macro F1
bAcc.
77.98 ±0.65 74.35±0.92
51.78±0.88 47.41±0.78
49.14±1.37 43.78±1.20
52.08±0.67 46.30±0.80
48.31±1.02 39.86±0.91
78.08±0.17 78.67±0.15
78.44±0.12 79.05±0.14
66.91±1.29 70.78±0.40
68.18±1.39 72.26±0.40
81.65±0.72 81.68±0.70 81.90±0.64 82.42±0.63 81.19±0.61 80.56±0.72 75.01±0.66 76.70±0.47
81.85±0.66 79.68±0.62 81.51±0.61 82.12±0.55 81.82±0.53 81.79±0.65 77.52±0.70 79.21±0.48
60.99±0.86 62.10±0.84 64.93±0.67 64.94±0.64 60.50±0.79 60.74±0.64 61.10±0.95 54.39±1.17
60.19±0.97 62.24±0.81 64.86±0.66 64.89±0.65 59.64±0.92 59.92±0.83 59.01±1.27 52.38±1.65
81.06±0.37 79.81±0.43 82.37±0.33 81.54±0.38 80.90±0.38 80.65±0.66 70.93±0.93 52.50±0.83
80.90±0.31 76.69±0.63 81.65±0.26 80.64±0.37 80.61±0.38 81.05±0.64 71.25±0.83 48.70±1.22
90.45±0.04 89.76±0.28 90.02±0.11 86.19±0.12 90.27±0.08 88.31±0.08 81.17±0.11 78.40±0.21
90.28±0.10 88.13±0.24 88.67±0.19 82.87±0.10 90.01±0.04 88.08±0.10 80.36±0.09 78.83±0.18
87.76±0.17 85.84±0.78 86.27±0.35 77.76±1.42 87.84±0.08 84.34±0.25 85.11±0.40 66.01±1.32
84.74±0.16 82.29±0.67 81.76±0.64 71.50±1.20 85.06±0.15 82.21±0.19 86.02±0.24 67.02±1.50
GraphENS TAM(G-ENS) GraphSHA
82.17±0.55 82.08±0.56 83.42±0.54
81.73±0.49 81.96±0.44 82.80±0.50
63.07±0.82 63.59±0.78 62.25±0.87
62.38±0.96 63.09±0.95 62.32±0.97
81.62±0.36 82.63±0.30 79.17±0.37
81.22±0.30 82.10±0.29 79.46±0.35
91.25±0.07 88.55±0.12 88.34±0.35
90.54±0.11 86.67±0.20 88.55±0.22
86.82±0.15 84.18±0.20 83.31±0.16
84.07±0.10 81.84±0.22 83.09±0.13
NodeImport
83.71 ±0.49
83.24 ±0.51
65.13 ±0.69
64.28±0.78
84.00 ±0.25
83.65 ±0.21
91.75 ±0.09
92.00 ±0.05
90.77 ±0.04
87.91 ±0.04
Vanilla GRAND
61.58±1.59 56.28±1.29
63.90±1.77 58.58±1.29
48.65±0.78 42.91±0.87
45.37±1.27 38.60±0.97
45.56±1.47 44.22±1.35
38.52±1.88 36.98±1.78
70.26±0.99 72.43±0.80
70.22±1.13 72.97±0.81
63.14±1.02 64.55±1.19
64.30±1.32 66.32±1.29
ReWeight PC Softmax Balanced Softmax TAM(BS) ReNode TAM(ReNode) ReVar BAT
82.09±0.69 74.91±0.99 75.19±1.40 74.43±0.90 79.82±1.00 77.96±0.87 75.82±0.63 66.20±1.67
81.34±0.61 74.56±1.00 74.49±1.24 74.36±0.99 80.38±0.86 79.07±0.75 78.08±0.64 68.48±1.83
60.78±0.92 62.43±0.89 62.05±0.47 63.50±0.63 57.94±0.72 57.71±0.87 61.67±0.94 50.09±0.98
60.17±0.97 62.25±0.91 62.16±0.49 63.53±0.66 56.80±0.79 56.30±0.96 59.61±1.30 47.59±1.47
79.58±0.48 79.81±0.29 80.68±0.35 80.86±0.48 79.15±0.51 79.44±1.15 66.77±1.79 45.48±1.50
79.65±0.29 79.12±0.21 80.13±0.44 80.56±0.41 79.26±0.33 79.68±1.02 66.56±2.47 38.40±1.93
84.13±0.40 83.23±0.57 85.33±0.53 81.69±0.57 83.31±0.40 80.54±0.60 81.67±0.02 72.31±1.00
83.93±0.33 81.66±0.53 84.31±0.48 79.52±0.51 83.71±0.48 80.33±0.65 80.52±0.02 72.50±1.03
78.99±0.33 76.44±0.66 79.25±0.19 76.40±1.13 78.65±0.32 77.92±0.44 83.28±0.76 63.54±1.52
78.44±0.39 72.47±0.79 76.33±0.38 72.06±1.50 78.14±0.31 76.61±0.36 84.71±0.72 64.52±1.93
GraphENS TAM(G-ENS) GraphSHA
80.20±0.80 81.25±0.62 81.22±0.66
80.14±0.79 81.45±0.59 81.07±0.64
61.72±0.61 62.11±0.74 60.51±0.84
61.14±0.69 61.42±0.91 60.53±0.95
81.06±0.32 82.33±0.27 80.59±0.33
80.73±0.29 81.75±0.25 80.77±0.25
88.81±0.19 86.99±0.16 85.93±0.30
88.94±0.16 86.13±0.22 87.07±0.27
87.39±0.32 85.19±0.23 83.29±0.32
85.33±0.16 82.76±0.16 83.11±0.28
Dataset (IR=50)
bAcc.
Vanilla GRAND
75.38 ±0.67 71.55±0.82
ReWeight PC Softmax Balanced Softmax TAM(BS) ReNode TAM(ReNode) ReVar BAT
Photo Macro F1
Computers bAcc. Macro F1
NodeImport
82.60 ±0.48
82.55 ±0.43
64.78 ±0.62
63.38 ±0.73
84.07 ±0.18
83.28 ±0.25
92.00 ±0.08
91.81 ±0.17
90.50 ±0.09
88.76 ±0.04
Vanilla GRAND
71.99±0.72 62.39±1.00
75.19±0.72 65.12±1.17
48.20 ±1.07 43.41±0.87
45.70 ±1.46 39.99±1.19
59.60±0.63 54.53±0.26
58.04±0.96 48.86±0.30
84.87 ±0.49 77.32±0.85
86.95 ±0.46 77.85±0.83
77.28±0.93 71.78±0.60
78.97±0.94 73.11±0.63
ReWeight PC Softmax Balanced Softmax TAM(BS) ReNode TAM(ReNode) ReVar BAT
78.34±0.81 81.16±0.49 80.71±0.70 80.73±0.51 78.07±0.60 78.93±0.67 66.80±0.64 77.58±0.64
79.85±0.65 80.37±0.40 80.73±0.59 81.06±0.43 79.89±0.53 80.80±0.65 66.80±0.71 79.77±0.55
55.56±0.93 60.69±0.92 59.82±1.19 59.44±1.07 55.07±1.20 55.52±0.98 57.70±0.87 51.17±1.09
54.74±0.95 60.56±0.95 59.94±1.25 59.61±1.06 54.22±1.18 54.78±0.98 55.01±1.23 49.69±1.51
76.88±0.37 81.42±0.28 79.70±0.42 78.94±0.44 75.72±0.16 76.30±0.57 75.98±0.97 59.69±0.60
77.41±0.35 80.37±0.24 78.87±0.40 78.50±0.43 76.52±0.17 76.95±0.56 75.89±0.71 58.51±0.84
90.26±0.14 91.97±0.12 92.10±0.21 87.22±0.37 89.79±0.13 88.00±0.18 85.72±0.03 83.15±0.18
91.39±0.07 91.89±0.09 91.57±0.11 85.08±0.24 90.95±0.08 89.10±0.14 87.56±0.03 84.59±0.26
86.91±0.13 87.67±0.15 87.38±0.33 85.15±0.48 87.13±0.12 84.75±0.27 82.45±0.36 78.56±0.45
86.39±0.08 85.09±0.21 84.37±0.21 81.12±0.39 86.45±0.03 84.36±0.17 84.34±0.19 80.35±0.49
GraphENS TAM(G-ENS) GraphSHA
80.40±0.66 81.19±0.49 80.29±0.29
80.44±0.60 81.35±0.45 80.09±0.47
62.20±0.85 63.44±0.75 57.69±1.18
61.33±0.98 62.65±0.92 57.78±1.32
82.30±0.19 82.29±0.18 75.40±0.46
82.20±0.11 82.04±0.17 75.77±0.28
91.70±0.13 90.23±0.29 90.56±0.17
92.06±0.07 89.62±0.16 91.68±0.10
87.94±0.20 86.75±0.22 87.75±0.17
85.92±0.07 84.40±0.15 86.93±0.07
NodeImport
82.90 ±0.41
83.28 ±0.37
64.22 ±0.62
62.89 ±0.78
86.25 ±0.24
85.90 ±0.17
93.02 ±0.15
92.71 ±0.10
88.94 ±0.22
86.92 ±0.11
Model Performance
Overall performance. The results in Table 2 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 [36] and GraphSHA [26], generally yield better results compared to algorithm-level techniques. Among algorithm-level approaches, Balanced Softmax [39] and PC Softmax [18] prove to be effective in most scenarios. When comparing
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
Nan Chen et al.
GRAND [11] 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 F.2. 85
75.38 ±0.67 79.92 ±0.80 81.13 ±0.13 80.39 ±0.73 83.85 ±0.53 81.36 ±0.71 82.56 ±0.43 83.71 ±0.49
77.98 ±0.65 81.12 ±0.70 82.01 ±0.27 81.58 ±0.60 83.50 ±0.46 82.05 ±0.60 82.48 ±0.44 83.24 ±0.51
✗ ✓ ✗ CiteSeer ✗ + GraphSAGE ✗ ✓ ✓ ✓
✗ ✗ ✓ ✗ ✓ ✗ ✓ ✓
✗ 56.07 ±1.65 ✗ 62.71 ±1.18 ✗ 66.65 ±1.12 ✓ 64.01 ±1.35 ✓ 70.45 ±1.04 ✓ 65.30 ±1.13 ✗ 68.99 ±0.87 ✓ 71.12 ±0.84
48.20 ±1.07 55.67 ±0.80 59.99 ±0.99 56.44 ±0.83 63.42 ±0.95 58.14 ±0.86 62.31 ±0.54 64.22 ±0.62
45.70 ±1.46 53.95 ±1.02 57.91 ±1.05 54.68 ±1.06 61.91 ±1.17 56.56 ±1.04 60.98 ±0.69 62.89 ±0.78
✗ ✓ ✗ photo ✗ + GraphSAGE ✗ ✓ ✓ ✓
✗ ✗ ✓ ✗ ✓ ✗ ✓ ✓
✗ ✗ ✗ ✓ ✓ ✓ ✗ ✓
84.87 ±0.49 84.59 ±0.41 88.42 ±0.39 88.01 ±0.63 92.56 ±0.18 88.64 ±0.43 87.93 ±0.95 93.02 ±0.15
86.95 ±0.46 86.04 ±0.43 89.58 ±0.32 88.43 ±0.45 92.49 ±0.08 88.99 ±0.18 88.92 ±1.12 92.71 ±0.10
Cora + GCN
55 5
GraphSHA TAM(ReNode) TAM(G-ENS) NodeImport
20
Imbalance Ratio (a) Cora - GAT
50
65
Vanillar PC Softmax Balanced Softmax GraphENS
60 55 50
5
20
GraphSHA TAM(ReNode) TAM(G-ENS) NodeImport
Imbalance Ratio (b) PubMed - SAGE
50
Figure 2: Model performance under varying imbalance ratios in terms of Macro F1 score. Performance under different imbalance ratios. Figure 2 illustrates the behavior of various methods under different imbalance ratios (IR ∈ {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 F.3, exhibit a similar trend.
88
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 F, including evaluations on a large-scale dataset (Appendix F.1), a sensitivity analysis of hyper-parameters (Appendix F.4), and a case study on the class distribution of filtered labeled nodes (Appendix F.5). Ablation study. We evaluate the contributions of the three main components introduced in Section 4.2. Table 3 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.
86 84
Score (%)
Macro F1 (%)
Vanillar PC Softmax Balanced Softmax GraphENS
60
Macro F1
✗ 81.55 ±0.51 ✗ 83.70 ±0.61 ✗ 84.12 ±0.28 ✓ 83.72 ±0.56 ✓ 85.33 ±0.33 ✓ 83.82 ±0.60 ✗ 84.53 ±0.41 ✓ 85.11 ±0.42
70
65
bAcc.
✗ ✗ ✓ ✗ ✓ ✗ ✓ ✓
75
70
Acc.
✗ ✓ ✗ ✗ ✗ ✓ ✓ ✓
80
75
5.3
C1 C2 C3
85
80
50
Table 3: Ablation study of model components. ✓ indicates the inclusion of a component, whereas ✗ denotes its exclusion.
90.53 ±0.30 90.49 ±0.12 91.16 ±0.30 90.92 ±0.11 93.78 ±0.04 91.11 ±0.09 91.36 ±0.42 93.94 ±0.06
ReNode Random
CoreSet NodeImport
BAcc. (a) Cora - SAGE
Macro F1
ReNode Random
CoreSet NodeImport
82 80 78 76 74 72 70
Acc.
Acc.
BAcc. Macro F1 (b) PubMed - GAT
Figure 3: Comparison of meta-set construction methods.
Analysis of the meta-set construction method. We evaluate the effectiveness of our meta-set construction method proposed in Section 4.3 by comparing it with three alternatives: Random sampling, ReNode [5] (which uses Totoro metrics to select top-ranked nodes), and CoreSet [41] (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.
NodeImport: Imbalanced Node Classification with Node Importance Assessment
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
Table 4: F1 scores for each class on the Cora dataset using the GraphSAGE backbone, under an imbalance ratio of 50. The table header presents each class, labeled from 𝐶 0 to 𝐶 6 , with its corresponding distribution located below each class label.
Singapore under its AI Singapore Programme (AISG Award No: AISG2-TC-2021-002).
References Class Distribution
𝐶0 𝐶1 𝐶2 𝐶3 𝐶4 𝐶5 𝐶6 6.80% 1.80% 25.24% 48.54% 13.18% 3.47% 0.97%
Vanilla GRAND
67.14 69.64 92.21 64.57 52.59 93.10
81.36 73.54
83.47 78.95 53.58 84.34 72.94 14.75
93.43 93.51 93.12 92.62 93.34 92.75
84.13 86.53 85.41 85.05 83.95 83.68
84.45 84.54 84.36 84.78 84.52 85.01
GraphENS TAM(G-ENS) GraphSHA
72.00 81.14 93.38 72.14 82.33 93.54 71.28 80.09 93.19
85.37 85.45 85.43
83.98 79.07 68.18 84.32 81.60 70.07 84.73 79.91 66.00
NodeImport
75.99 83.84 93.11
87.12 86.28 82.48 74.09
ReWeight 71.68 78.88 PC Softmax 72.63 80.58 Balanced Softmax 72.18 80.84 TAM(BS) 72.69 80.34 ReNode 71.96 77.94 TAM(ReNode) 73.62 78.35
80.49 65.88 79.77 65.03 80.83 68.38 81.52 70.44 80.50 67.03 81.40 70.80
Case study on per-class F1 scores. Table 4 presents the perclass 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 𝐶 0 , 𝐶 1 , and 𝐶 6 . Compared to the Vanilla method, the GRAND method shows a sharp decrease in the F1 score for the smallest class, 𝐶 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 𝐶 6 , further exacerbating the class imbalance issue.
6
Conclusions
In this work, we introduce NodeImport, a framework for classimbalanced 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.
Acknowledgments This research is supported by the National Research Foundation, Singapore and Infocomm Media Development Authority under its Trust Tech Funding Initiative, the National Research Foundation,
[1] David Berthelot, Nicholas Carlini, Ian Goodfellow, Nicolas Papernot, Avital Oliver, and Colin A Raffel. 2019. Mixmatch: A holistic approach to semi-supervised learning. Advances in neural information processing systems 32 (2019). [2] Hongyun Cai, Vincent W Zheng, and Kevin Chen-Chuan Chang. 2018. A comprehensive survey of graph embedding: Problems, techniques, and applications. IEEE Transactions on Knowledge and Data Engineering 30, 9 (2018), 1616–1637. [3] Kaidi Cao, Colin Wei, Adrien Gaidon, Nikos Arechiga, and Tengyu Ma. 2019. Learning imbalanced datasets with label-distribution-aware margin loss. Advances in neural information processing systems 32 (2019). [4] Nitesh V Chawla, Kevin W Bowyer, Lawrence O Hall, and W Philip Kegelmeyer. 2002. SMOTE: synthetic minority over-sampling technique. Journal of artificial intelligence research 16 (2002), 321–357. [5] Deli Chen, Yankai Lin, Guangxiang Zhao, Xuancheng Ren, Peng Li, Jie Zhou, and Xu Sun. 2021. Topology-imbalance learning for semi-supervised node classification. Advances in Neural Information Processing Systems 34 (2021), 29885–29897. [6] Nan Chen, Zemin Liu, Bryan Hooi, Bingsheng He, Rizal Fathony, Jun Hu, and Jia Chen. 2024. Consistency Training with Learnable Data Augmentation for Graph Anomaly Detection with Limited Supervision. In The Twelfth International Conference on Learning Representations. https://openreview.net/forum?id=elMKXvhhQ9 [7] Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. 2020. Adaptive universal generalized pagerank graph neural network. arXiv preprint arXiv:2006.07988 (2020). [8] Limeng Cui, Xianfeng Tang, Sumeet Katariya, Nikhil Rao, Pallav Agrawal, Karthik Subbian, and Dongwon Lee. 2022. ALLIE: Active learning on large-scale imbalanced graphs. In Proceedings of the ACM Web Conference 2022. 690–698. [9] Yin Cui, Menglin Jia, Tsung-Yi Lin, Yang Song, and Serge Belongie. 2019. Classbalanced loss based on effective number of samples. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 9268–9277. [10] Amir Erfan Eshratifar, David Eigen, and Massoud Pedram. 2018. Gradient agreement as an optimization objective for meta-learning. arXiv preprint arXiv:1810.08178 (2018). [11] Wenzheng Feng, Jie Zhang, Yuxiao Dong, Yu Han, Huanbo Luan, Qian Xu, Qiang Yang, Evgeny Kharlamov, and Jie Tang. 2020. Graph random neural networks for semi-supervised learning on graphs. Advances in neural information processing systems 33 (2020), 22092–22103. [12] Matthias Fey and Jan Eric Lenssen. 2019. Fast graph representation learning with PyTorch Geometric. arXiv preprint arXiv:1903.02428 (2019). [13] Chelsea Finn, Pieter Abbeel, and Sergey Levine. 2017. Model-agnostic metalearning for fast adaptation of deep networks. In International conference on machine learning. PMLR, 1126–1135. [14] Johannes Gasteiger, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Predict then propagate: Graph neural networks meet personalized pagerank. arXiv preprint arXiv:1810.05997 (2018). [15] Xinyu Guo, Kai Wu, Xiaoyu Zhang, and Jing Liu. 2024. Automated Loss function Search for Class-imbalanced Node Classification. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net. https://openreview.net/forum?id=O1hmwi51pp [16] Will Hamilton, Zhitao Ying, and Jure Leskovec. 2017. Inductive representation learning on large graphs. Advances in neural information processing systems 30 (2017). [17] Haibo He and Edwardo A Garcia. 2009. Learning from imbalanced data. IEEE Transactions on knowledge and data engineering 21, 9 (2009), 1263–1284. [18] Youngkyu Hong, Seungju Han, Kwanghee Choi, Seokjun Seo, Beomsu Kim, and Buru Chang. 2021. Disentangling label distribution for long-tailed visual recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 6626–6636. [19] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. 2020. Open graph benchmark: datasets for machine learning on graphs. In Proceedings of the 34th International Conference on Neural Information Processing Systems (Vancouver, BC, Canada) (NIPS ’20). Curran Associates Inc., Red Hook, NY, USA, Article 1855, 16 pages. [20] Nathalie Japkowicz and Shaju Stephen. 2002. The class imbalance problem: A systematic study. Intelligent data analysis 6, 5 (2002), 429–449. [21] Krishnateja Killamsetty, Durga Sivasubramanian, Ganesh Ramakrishnan, and Rishabh Iyer. 2021. Glister: Generalization based data subset selection for efficient and robust learning. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35. 8110–8118. [22] Diederik P. Kingma and Jimmy Ba. 2015. Adam: A Method for Stochastic Optimization. In 3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings.
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
[23] Thomas N. Kipf and Max Welling. 2017. Semi-Supervised Classification with Graph Convolutional Networks. In International Conference on Learning Representations. [24] Andreas Kirsch, Tom Rainforth, and Yarin Gal. 2021. Test distribution-aware active learning: A principled approach against distribution shift and outliers. arXiv preprint arXiv:2106.11719 (2021). [25] Bartosz Krawczyk. 2016. Learning from imbalanced data: open challenges and future directions. Progress in artificial intelligence 5, 4 (2016), 221–232. [26] Wen-Zhi Li, Chang-Dong Wang, Hui Xiong, and Jian-Huang Lai. 2023. GraphSHA: Synthesizing Harder Samples for Class-Imbalanced Node Classification. SIGKDD (2023). [27] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and Piotr Dollár. 2017. Focal loss for dense object detection. In Proceedings of the IEEE international conference on computer vision. 2980–2988. [28] Jie Liu, Mengting He, Guangtao Wang, Nguyen Quoc Viet Hung, Xuequn Shang, and Hongzhi Yin. 2023. Imbalanced node classification beyond homophilic assumption. arXiv preprint arXiv:2304.14635 (2023). [29] Yang Liu, Xiang Ao, Zidi Qin, Jianfeng Chi, Jinghua Feng, Hao Yang, and Qing He. 2021. Pick and choose: a GNN-based imbalanced learning approach for fraud detection. In Proceedings of the web conference 2021. 3168–3177. [30] Zemin Liu, Yuan Li, Nan Chen, Qian Wang, Bryan Hooi, and Bingsheng He. 2023. A survey of imbalanced learning on graphs: Problems, techniques, and future directions. arXiv preprint arXiv:2308.13821 (2023). [31] Zhining Liu, Ruizhong Qiu, Zhichen Zeng, Hyunsik Yoo, David Zhou, Zhe Xu, Yada Zhu, Kommy Weldemariam, Jingrui He, and Hanghang Tong. 2024. ClassImbalanced Graph Learning without Class Rebalancing. In Forty-first International Conference on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net. https://openreview.net/forum?id=pPnkpvBeZN [32] Yihong Ma, Yijun Tian, Nuno Moniz, and Nitesh V Chawla. 2023. Classimbalanced learning on graphs: A survey. arXiv preprint arXiv:2304.04300 (2023). [33] Aditya Krishna Menon, Sadeep Jayasumana, Ankit Singh Rawat, Himanshu Jain, Andreas Veit, and Sanjiv Kumar. 2021. Long-tail learning via logit adjustment. In International Conference on Learning Representations. https://openreview.net/ forum?id=37nvvqkCo5 [34] Sören Mindermann, Jan M Brauner, Muhammed T Razzak, Mrinank Sharma, Andreas Kirsch, Winnie Xu, Benedikt Höltgen, Aidan N Gomez, Adrien Morisot, Sebastian Farquhar, et al. 2022. Prioritized training on points that are learnable, worth learning, and not yet learnt. In International Conference on Machine Learning. PMLR, 15630–15649. [35] Hae-Sang Park and Chi-Hyuck Jun. 2009. A simple and fast algorithm for Kmedoids clustering. Expert systems with applications 36, 2 (2009), 3336–3341. [36] Joonhyung Park, Jaeyun Song, and Eunho Yang. 2022. GraphENS: NeighborAware Ego Network Synthesis for Class-Imbalanced Node Classification. In International Conference on Learning Representations. https://openreview.net/ forum?id=MXEl7i-iru [37] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. 2020. Geom-gcn: Geometric graph convolutional networks. arXiv preprint arXiv:2002.05287 (2020). [38] Liang Qu, Huaisheng Zhu, Ruiqi Zheng, Yuhui Shi, and Hongzhi Yin. 2021. Imgagn: Imbalanced network embedding via generative adversarial graph networks. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery & Data Mining. 1390–1398. [39] Jiawei Ren, Cunjun Yu, Xiao Ma, Haiyu Zhao, Shuai Yi, et al. 2020. Balanced meta-softmax for long-tailed visual recognition. Advances in neural information processing systems 33 (2020), 4175–4186. [40] Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. 2018. Learning to reweight examples for robust deep learning. In International conference on machine learning. PMLR, 4334–4343. [41] Ozan Sener and Silvio Savarese. 2017. Active learning for convolutional neural networks: A core-set approach. arXiv preprint arXiv:1708.00489 (2017). [42] Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. 2018. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.05868 (2018). [43] Min Shi, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. 2020. Multiclass imbalanced graph convolutional network learning. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20). [44] Min Shi, Yufei Tang, Xingquan Zhu, David Wilson, and Jianxun Liu. 2020. Multiclass imbalanced graph convolutional network learning. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20). [45] Jun Shu, Qi Xie, Lixuan Yi, Qian Zhao, Sanping Zhou, Zongben Xu, and Deyu Meng. 2019. Meta-weight-net: Learning an explicit mapping for sample weighting. Advances in neural information processing systems 32 (2019). [46] Kihyuk Sohn, David Berthelot, Nicholas Carlini, Zizhao Zhang, Han Zhang, Colin A Raffel, Ekin Dogus Cubuk, Alexey Kurakin, and Chun-Liang Li. 2020. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. Advances in neural information processing systems 33 (2020), 596–608. [47] Jaeyun Song, Joonhyung Park, and Eunho Yang. 2022. TAM: topology-aware margin loss for class-imbalanced node classification. In International Conference
Nan Chen et al.
on Machine Learning. PMLR, 20369–20383. [48] Jingru Tan, Changbao Wang, Buyu Li, Quanquan Li, Wanli Ouyang, Changqing Yin, and Junjie Yan. 2020. Equalization loss for long-tailed object recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition. 11662–11671. [49] Petar Velicković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. 2018. Graph Attention Networks. In International Conference on Learning Representations. [50] Vikas Verma, Alex Lamb, Christopher Beckham, Amir Najafi, Ioannis Mitliagkas, David Lopez-Paz, and Yoshua Bengio. 2019. Manifold mixup: Better representations by interpolating hidden states. In International conference on machine learning. 6438–6447. [51] Jianfeng Wang, Thomas Lukasiewicz, Xiaolin Hu, Jianfei Cai, and Zhenghua Xu. 2021. Rsg: A simple but effective module for learning imbalanced datasets. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition. 3784–3793. [52] Felix Wu, Amauri Souza, Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Weinberger. 2019. Simplifying graph convolutional networks. In International conference on machine learning. PMLR, 6861–6871. [53] Lirong Wu, Haitao Lin, Zhangyang Gao, Cheng Tan, Stan Li, et al. 2021. Graphmixup: Improving class-imbalanced node classification on graphs by selfsupervised context prediction. arXiv preprint arXiv:2106.11133 (2021). [54] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. 2020. A comprehensive survey on graph neural networks. IEEE transactions on neural networks and learning systems 32, 1 (2020), 4–24. [55] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. 2019. How Powerful are Graph Neural Networks?. In International Conference on Learning Representations. [56] Ziyu Xu, Chen Dan, Justin Khim, and Pradeep Ravikumar. 2020. Class-weighted classification: Trade-offs and robust approaches. In International conference on machine learning. PMLR, 10544–10554. [57] Divin Yan, Gengchen Wei, Chen Yang, Shengzhong Zhang, and Zengfeng Huang. 2023. Rethinking Semi-Supervised Imbalanced Node Classification from BiasVariance Decomposition. In Thirty-seventh Conference on Neural Information Processing Systems. https://openreview.net/forum?id=0gvtoxhvMY [58] Yu Yang, Hao Kang, and Baharan Mirzasoleiman. 2023. Towards sustainable learning: Coresets for data-efficient deep learning. In International Conference on Machine Learning. PMLR, 39314–39330. [59] Zhilin Yang, William Cohen, and Ruslan Salakhudinov. 2016. Revisiting semisupervised learning with graph embeddings. In International conference on machine learning. PMLR, 40–48. [60] Sukwon Yun, Kibum Kim, Kanghoon Yoon, and Chanyoung Park. 2022. Lte4g: long-tail experts for graph neural networks. In Proceedings of the 31st ACM International Conference on Information & Knowledge Management. 2434–2443. [61] Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. 2018. mixup: Beyond Empirical Risk Minimization. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 - May 3, 2018, Conference Track Proceedings. [62] Yifan Zhang, Bingyi Kang, Bryan Hooi, Shuicheng Yan, and Jiashi Feng. 2023. Deep long-tailed learning: A survey. IEEE Transactions on Pattern Analysis and Machine Intelligence 45, 9 (2023), 10795–10816. [63] Yongshun Zhang, Xiu-Shen Wei, Boyan Zhou, and Jianxin Wu. 2021. Bag of tricks for long-tailed visual recognition with deep convolutional neural networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 35. 3447–3455. [64] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. 2021. Graphsmote: Imbalanced node classification on graphs with graph neural networks. In Proceedings of the 14th ACM international conference on web search and data mining. 833–841. [65] Mengting Zhou and Zhiguo Gong. 2023. GraphSR: A Data Augmentation Algorithm for Imbalanced Node Classification. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 37. 4954–4962. [66] Hao Zhu and Piotr Koniusz. 2020. Simple spectral graph convolution. In International conference on learning representations. [67] Wei Zhuo, Zemin Liu, Bryan Hooi, Bingsheng He, Guang Tan, Rizal Fathony, and Jia Chen. 2024. Partitioning Message Passing for Graph Fraud Detection. In The Twelfth International Conference on Learning Representations. https: //openreview.net/forum?id=tEgrUrUuwA
A
Proofs for Theoretical Analysis
In this section, we present theoretical proofs for the equations used in the manuscript.
NodeImport: Imbalanced Node Classification with Node Importance Assessment
A.1
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
Gradient Derivation of the Cross-Entropy Loss Function
Putting Eq. 26 to Eq. 30 together, we have the following: 𝑑𝐿 = −𝑌 : 𝑑𝑍
To derive Eq. 6, we need to find the derivative of the cross-entropy loss function 𝐿[·], as defined in Eq. 7, with respect to the model parameters 𝜃 . More generally, when dealing with a subset of 𝑝 nodes represented by 𝐴˜ ∈ R𝑝 ×𝑛 and their associated labels 𝑌 ∈ [0, 1] 𝑝 ×𝑐 , 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 𝑆 ∈ R𝑝 ×𝑐 : ˜ 𝑆 = 𝐴𝑋𝜃
= −𝑌 : 𝑑𝐻 ⊘ 𝐻 = −𝑌 : (𝑑𝐸 ⊘ 𝐸 𝐽 − (𝑑𝐸)𝐽 ⊙ 𝐻 ⊘ 𝐸 𝐽 ) ⊘ 𝐻 = −𝑌 : ((𝐸 ⊙ 𝑑𝑆) ⊘ 𝐸 𝐽 − (𝐸 ⊙ 𝑑𝑆)𝐽 ⊙ 𝐻 ⊘ 𝐸 𝐽 ) ⊘ 𝐻 = −𝑌 : (𝐸 ⊙ 𝑑𝑆) ⊘ 𝐸 𝐽 ⊘ 𝐻 − (𝐸 ⊙ 𝑑𝑆)𝐽 ⊘ 𝐸 𝐽 ) = −𝑌 : 𝑑𝑆 − (𝐸 ⊙ 𝑑𝑆)𝐽 ⊘ 𝐸 𝐽 )
(21)
= −𝑌 : 𝑑𝑆 + (𝑌 ⊘ 𝐸 𝐽 )𝐽 ⊙ 𝐸 : (𝑑𝑆) = ((𝑌 ⊘ 𝐸 𝐽 )𝐽 ⊙ 𝐸 − 𝑌 ) : (𝑑𝑆)
Next, we employ element-wise exponential operation to 𝑆 and obtain 𝐸 ∈ R𝑝 ×𝑐 : 𝐸 = exp(𝑆)
𝐻 = 𝐸 ⊘ 𝐸𝐽
In this way, we can get the gradient ∇𝐿 of the loss function in terms of the denominator layout: 𝑑𝐿 𝑑𝜃 ˜ )𝑇 ((𝑌 ⊘ 𝐸 𝐽 )𝐽 ⊙ 𝐸 − 𝑌 ) = (𝐴𝑋
∇𝜃 𝐿 =
˜ )𝑇 (𝐻 − 𝑌 ) ∇𝜃 𝐿 = (𝐴𝑋
(33)
Hence, the proof is complete. (25)
B where ⟨·, ·⟩𝐹 denotes the Frobenius inner product. For simplicity, the symbol : can be used to represent the Frobenius inner product ⟨·, ·⟩𝐹 . Henceforth, these two symbols will be used interchangeably to indicate the Frobenius inner product. Since directly computing the derivatives ∇ is intractable and unrealistic, we choose to work in the differential form 1 . In particular, starting from the cross-entropy loss (Eq. 25), we have: 𝑑𝐿 = −𝑌 : 𝑑𝑍
(26)
𝑑𝑍 = 𝑑𝐻 ⊘ 𝐻
(27)
Next,
Then, 𝑑𝐻 = 𝑑𝐸 ⊙ 𝐸 𝐽 ⊘ 𝐸 𝐽 ⊘ 𝐸 𝐽 − 𝑑 (𝐸 𝐽 ) ⊙ 𝐸 ⊘ 𝐸 𝐽 ⊘ 𝐸 𝐽 = 𝑑𝐸 ⊘ 𝐸 𝐽 − (𝑑𝐸)𝐽 ⊙ 𝐻 ⊘ 𝐸 𝐽
(32)
Given that 𝑌 is the label matrix with each row as a one-hot vector, we can simplify Eq.32 and get:
(24)
Finally, the cross-entropy loss 𝐿 is calculated as follows: 𝐿 = −⟨𝑌, 𝑍 ⟩𝐹
˜ )𝑇 ((𝑌 ⊘ 𝐸 𝐽 )𝐽 ⊙ 𝐸 − 𝑌 ) : 𝑑𝜃 = (𝐴𝑋
(23)
where ⊘ denotes the Hadamard division and 𝐽 ∈ R𝑐 ×𝑐 represents an all-one matrix. After that, we apply the element-wise logarithm to 𝐻 and get 𝑍 ∈ R𝑝 ×𝑐 𝑍 = log(𝐻 )
˜ = ((𝑌 ⊘ 𝐸 𝐽 )𝐽 ⊙ 𝐸 − 𝑌 ) : 𝐴𝑋𝑑𝜃
(22)
Then, we normalize 𝐸 along each row and get 𝐻 ∈ R𝑝 ×𝑐 , which can be seen as the softmax of the output logits 𝑆:
(31)
= −𝑌 : 𝑑𝑆 + 𝑌 : (𝐸 ⊙ 𝑑𝑆)𝐽 ⊘ 𝐸 𝐽
(28)
where ⊙ represents the Hadamard product. After that, 𝑑𝐸 = 𝐸 ⊙ 𝑑𝑆
(29)
˜ 𝑑𝑆 = 𝐴𝑋𝑑𝜃
(30)
Finally,
1We draw the inspiration from this blog https://math.stackexchange.com/a/3850121/ 1237687
Algorithm
Pseudo-Code Algorithm 1 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 metaset. 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. Complexity analysis 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 V𝑡𝑟 represent the set of nodes within the training set 𝐷𝑡𝑟 , and V𝑢𝑙 denote the set of unlabeled nodes. • Meta-set construction. The adjacency matrix 𝐴 is sparse with |E | non-zero elements, the degree matrix 𝐷 is diagonal, and the feature matrix 𝑋 is dense. Thus, computing the context embed˜ involves sparse-dense matrix multiplications, with a ding 𝐴𝑋 complexity of O (𝐾 |E |𝑑) where 𝐾 is the number of steps and 𝑑 is the feature dimension. Running the PAM algorithm on a class of size |V 𝑘 | for 𝜏 meta-samples incurs a complexity of O (𝜏 2 |V 𝑘 | 2 ). Therefore, the overall complexity of the meta-set construction Í procedure is O (𝐾 |E |𝑑 + 𝑐 ∈ C 𝜏 |V𝑐𝐿 | 2 ).
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
Nan Chen et al.
Algorithm 1 Pseudo-code of the framework Require: Input graph G = (V, E, 𝐴, 𝑋 ), class set C = {1, . . . , 𝑐}, training set D𝑡𝑟 = {(𝑣, 𝑦 𝑣 )}, set of unlabeled nodes D𝑢𝑙 , GNN model 𝑔(·, 𝜃 ), depth of the aggregation matrix 𝐾, teleport probability when calculating the aggregation matrix 𝛼, meta-set size per class 𝜏, scale for loss on unlabeled nodes 𝛽, scale for loss on synthetic nodes 𝛾, learning rate 𝜅, vector with all ones 𝐽 , degree matrix 𝐷 Ensure: Trained GNN parameters 𝜃 1 1 1 Í𝐾 1: Calculate the aggregation matrix 𝐴˜ = 𝐾 𝑘=1 ((1 − 𝛼)(𝐷 − 2 𝐴𝐷 − 2 )𝑘 + 𝛼𝐼 ) 2: Initialize the set of meta-samples M ← ∅ 3: for 𝑐 ∈ C do ˜ V 𝑘 , 𝜏) 4: Apply PAM algorithm to find meta-samples in the class M̃𝑘 ← PAM(𝐴𝑋, 𝑘 5: M ← M ∪ M̃ 6: end for 7: Construct the meta-set D𝑚𝑒𝑡𝑎 from M. 8: Remove meta-samples from the training set D𝑙 = D𝑡𝑟 \ D𝑚𝑒𝑡𝑎 9: while not converged do 10: Sample a set of node pairs S = {⟨(𝑣𝑠 , 𝑦𝑠 ), (𝑣𝑡 , 𝑦𝑡 )⟩} from the training set 𝐷𝑡𝑟 based on Eq.13 11: Initialize the set of synthetic nodes D𝑠𝑦𝑛 ← ∅ 12: for ⟨(𝑣𝑠 , 𝑦𝑠 ), (𝑣𝑡 , 𝑦𝑡 )⟩ ∈ S do 13: Sample the mixing ratio 𝜆 ∼ Beta(2, 2)xw 14: Generate synthetic node feature 𝑥𝑠𝑦𝑛 = 𝜆 · 𝑥𝑠 + (1 − 𝜆) · 𝑥𝑡 ′ 15: Construct distribution for neighbor sampling 𝐴𝑠𝑦𝑛 = 𝜆 · 𝐴𝑠 + (1 − 𝜆) · 𝐴𝑡 16: Generate synthetic node label 𝑦𝑠𝑦𝑛 = 𝜆 · 𝑦𝑠 + (1 − 𝜆) · 𝑦𝑡 ′ ) 17: Generate synthetic edges by sampling neighbors from the calculated distribution 𝐴𝑠𝑦𝑛 = Sample(𝐴𝑠𝑦𝑛 18: D𝑠𝑦𝑛 ← D𝑠𝑦𝑛 ∪ {(𝑣𝑠𝑦𝑛 , 𝑦𝑠𝑦𝑛 )} 19: end for 20: Obtain predictions from the GNN model 𝐻 ← 𝑔(G, 𝜃 ) 21: Generate pseudo-labels for unlabeled nodes D𝑢𝑙 according to Eq.11 22: Construct the set of valuable labeled nodes 𝐷˜ 𝑙 = {(𝑣, 𝑦 𝑣 ) ∈ 𝐷𝑙 | 𝜂 𝑣 > 0} 23: Construct the set of valuable unlabeled nodes 𝐷˜ 𝑢𝑙 = {(𝑣, 𝑦ˆ𝑣 ) | 𝑣 ∈ 𝐷𝑢𝑙 and 𝜂 𝑣 > 0} 24: Construct the set of valuable synthetic nodes 𝐷˜ 𝑠𝑦𝑛 = {(𝑣𝑠𝑦𝑛 , 𝑦𝑠𝑦𝑛 ) ∈ D𝑠𝑦𝑛 | 𝜂 𝑣𝑠𝑦𝑛 > 0} Í 25: Compute loss for labeled nodes L𝑙 ← (𝑣,𝑦𝑣 ) ∈ D̃𝑙 Cross-Entropy(𝑦 𝑣 , ℎ 𝑣 ) Í 26: Compute loss for unlabeled nodes L𝑢𝑙 ← (𝑣,𝑦ˆ𝑣 ) ∈ 𝐷˜ 𝑢𝑙 Cross-Entropy(𝑦ˆ𝑣 , ℎ𝑢 ) Í 27: Compute loss for synthetic nodes L𝑠𝑦𝑛 ← (𝑣𝑠𝑦𝑛 ,𝑦𝑠𝑦𝑛 ) ∈ D̃𝑠𝑦𝑛 Cross-Entropy(𝑦𝑠𝑦𝑛 , ℎ 𝑣𝑠𝑦𝑛 ) 28: Compute the final loss L ← L𝑙 + 𝛽 · L𝑢𝑙 + 𝛾 · L𝑠𝑦𝑛 29: Update the GNN model 𝜃 ← 𝜃 − 𝜅 · ∇𝜃 L 30: end while 31: return 𝜃 • Synthetic node generation. The number of synthetic nodes generated per class is O (|V𝑡𝑟 |). The process begins with sampling pairs of nodes, which incurs a complexity of O (|V𝑡𝑟 | 2 ). For each sampled pair, generating synthetic node features and labels involves simple arithmetic operations with a complexity of O (|V𝑡𝑟 |𝑑). Furthermore, generating edges for these synthetic nodes to maintain the original degree distribution of the graph ¯ where 𝑑¯ represents the averhas a complexity of O (|V𝑡𝑟 | · 𝑑), age degree of the graph. Therefore, the overall complexity of ¯ producing synthetic nodes is O (|V𝑡𝑟 | 2 + |V𝑡𝑟 |𝑑 + |V𝑡𝑟 | · 𝑑). • Node importance computation. Given that the amount of synthetic nodes is O (|V𝑡𝑟 |) and these synthetic edges maintain the original degree distribution, the augmented graph with synthetic nodes consists of O (|E |) edges. Moreover, generating pseudolabels for unlabeled nodes requires a complexity of O (|V𝑢𝑙 |𝑐).
Calculating node importance scores requires computing the context embedding for the augmented graph, which incurs a complexity of O (𝐾 |E |𝑑), and performing dense matrix multiplications and element-wise operations, which incurs a complexity of O (|V |𝑑 ·𝑐𝜏 +|V |𝑐 2𝜏). Consequently, the complexity to determine node importance is O (𝐾 |E |𝑑 + |V𝑢𝑙 |𝑐 + |V |𝑑 · 𝑐𝜏 + |V |𝑐 2𝜏). Given that |E | ≫ |V𝑡𝑟 | and 𝑐, 𝜏, and 𝑑 are typically small constants, in a class-imbalanced node classification scenario, the added overhead for 𝑇 training epochs is simplified to O (𝑇 · 𝐾 |E |𝑑), 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.
C
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 [12].
NodeImport: Imbalanced Node Classification with Node Importance Assessment
• Cora, CiteSeer, and PubMed [59]: 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 [37]. • Amazon-Photo and Amazon-Computer [42]: These two copurchase 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 bagof-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.
D
Descriptions of the Baselines
This section will introduce baselines used in more detail and their hyper-parameter configurations. • Graph Random Neural Networks (GRAND) [11]: 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 [20]: 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 [39]: 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) [18]: 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 [5]: 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 𝑤𝑚𝑖𝑛 is set to 0.5, and the upper bound 𝑤𝑚𝑎𝑥 is set to 1.5. The teleport probability 𝛼 in the PageRank is set to 0.15. • Topology-Aware Margin (TAM) [47]: 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
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
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 𝛼 to 2.5, the coefficient of the ADM term 𝛽 to 0.5, the minimum temperature of the class-wise temperature 𝜙 to 1.2, and the warmup period to 5 iterations. • Regularize Variance (ReVar) [57]: This work leverages data augmentation to estimate model variance and uses the estimated variance as a regularization term during training. The two intensity terms 𝜆1 and 𝜆2 are set to 0.25 and 2.85, respectively. • BAlanced Topological augmentation (BAT) [31]: 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 [36]: 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 𝜆 is sampled from a Beta(2, 2) distribution, the feature masking hyperparameter 𝐾 is set to 1, the prediction temperature 𝜏 is set to 2, and the warmup period is set to 5 iterations. • GraphSHA [26]: 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 𝛿 is sampled from a Beta(1, 100) distribution. The Personalized PageRank (PPR) version of the adjacency matrix is used, and the temperature 𝑇 of the SoftMax function is set to 2 for the calculating model confidence.
E Deatials on the Evaluation Process E.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.
E.2
Configurations of GNN Backbones
• Graph Convolutional Network (GCN) [23]: 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) [49]: The network is constructed with two GAT layers, with a hidden dimension size of 256. The multi-head attention mechanism is applied, with the
Acc. (%)
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
85
85
80
80
75
Table 5: Statistics of the ogbn-arxiv dataset
75
Vanillar PC Softmax Balanced Softmax GraphENS
70 65 60
Nan Chen et al.
5
GraphSHA TAM(ReNode) TAM(G-ENS) NodeImport
20
50
Imbalance Ratio (a) Cora - GAT
Vanillar PC Softmax Balanced Softmax GraphENS
70 65 60
5
GraphSHA TAM(ReNode) TAM(G-ENS) NodeImport
20
Imbalance Ratio (b) PubMed - SAGE
bAcc. (%)
85
80
80
75
75
70
Vanillar PC Softmax Balanced Softmax GraphENS
60 55 50
5
GraphSHA TAM(ReNode) TAM(G-ENS) NodeImport
20
Imbalance Ratio (a) Cora - GAT
50
65
Vanillar PC Softmax Balanced Softmax GraphENS
60 55 50
5
20
GraphSHA TAM(ReNode) TAM(G-ENS) NodeImport
Imbalance Ratio (b) PubMed - SAGE
50
Figure 5: Experiments under varying imbalance ratios in terms of balanced accuracy.
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) [16]): 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.
E.3
Configuration of Our Model
˜ the depth 𝐾 For the computation of the aggregation matrix 𝐴, is selected from {2, 4, 8, 16}m and the teleport probability 𝛼 is selected from {0.05, 0.10, 0.15, 0.20}. The scaling factors for the losses of the unlabeled and synthetic nodes, 𝛽 and 𝛾, 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.
E.4
Edges
Features
Classes
ogbn-arxiv
169,343
1,166,243
128
40
F Additional Experimental Results F.1 Experiments with a large-scale dataset
70
65
Nodes
50
Figure 4: Experiments under varying imbalance ratios in terms of accuracy.
85
Dataset
Training Details
All methods are trained for 2000 epochs, and the parameters of GNN backbones are optimized via the Adam optimizer [22]. 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.
In this subsection, we evaluate our method on the large-scale arXiv dataset from the OGB benchmark [19], summarized in Table 5. 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 6 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. Table 6: Experimental results on the ogbn-arxiv dataset, showcasing model performance across balanced accuracy, execution time, and peak GPU memory usage (columns 2–4). Methods
bAcc.
Exec Time(s)
Peak GPU Mem (GB)
Vanilla
44.43±0.13
3325±13
6.29
ReWeight TAM(BS)
56.52±0.16 53.45±0.23
3333±6 3436±18
6.29 6.29
ours(w/o C3)
55.59±0.14
3473±13
6.72
F.2
Overall Performance in Terms of Accuracy
Table 7 lists the model performance against selected baselines in terms of the accuracy metric. The result is consistent with that discussed in Section 5.2.
F.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.
F.4
Hyper-Parameters Sensitivity
This analysis examines how the two scaling factors 𝛽 and 𝛾 of the loss function in Eq. 17 affect the model performance. Specifically, we explore a range of values for 𝛽 and 𝛾: {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 𝛽 and 𝛾 are set around 1.0. However,
NodeImport: Imbalanced Node Classification with Node Importance Assessment
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
GraphSAGE
GAT
GCN
Table 7: Performance comparison (%) on benchmark graphs with an imbalance ratio of 50. The best results are in bold. Models with performances within the standard error are statistically comparable.
Dataset IR=50
Cora Acc.
CiteSeer Acc.
PubMed Acc.
Photo Acc.
Computers Acc.
Vanilla GRAND
81.55 ±0.51 79.98±0.58
59.74±1.32 55.59±1.35
60.68±0.51 55.06±0.93
87.35±0.12 88.06±0.07
82.23±0.26 83.78±0.17
ReWeight PC Softmax Balanced Softmax TAM(BS) ReNode TAM(ReNode) ReVar BAT
83.74±0.48 81.99±0.59 83.72±0.54 84.10±0.51 83.86±0.38 83.90±0.57 81.19±0.57 82.33±0.31
67.33±1.00 65.39±1.13 69.09±0.86 69.30±0.77 67.51±1.05 68.00±1.01 68.81±0.93 62.14±1.44
81.93±0.27 77.40±0.58 82.53±0.19 81.44±0.31 81.59±0.37 81.79±0.61 72.35±0.74 61.19±0.68
91.71±0.09 90.04±0.16 90.55±0.17 84.01±0.12 91.53±0.04 90.00±0.08 89.41±0.05 87.57±0.11
85.24±0.19 85.27±0.46 84.65±0.50 77.56±0.44 85.67±0.18 82.19±0.16 88.65±0.08 81.97±0.34
GraphENS TAM(G-ENS) GraphSHA
83.34±0.40 83.66±0.41 84.87±0.47
69.43±0.96 69.84±0.90 67.92±1.13
82.24±0.23 82.95±0.24 79.86±0.30
91.84±0.07 87.45±0.15 90.77±0.12
84.84±0.13 81.36±0.19 85.72±0.11
NodeImport
85.11 ±0.42
71.47 ±0.72
84.42 ±0.16
92.71 ±0.04
88.80 ±0.04
Vanilla GRAND
72.17±1.13 68.43±0.95
56.81±1.36 50.86±1.62
54.20±1.74 52.60±1.56
82.81±0.57 84.02±0.48
79.94±0.29 80.76±0.38
ReWeight PC Softmax Balanced Softmax TAM(BS) ReNode TAM(ReNode) ReVar BAT
83.14±0.45 79.20±0.73 78.91±0.96 77.83±0.73 82.78±0.59 81.49±0.54 81.57±0.39 75.03±1.21
66.98±1.12 66.87±1.04 66.76±0.83 68.03±0.92 65.15±1.12 65.02±1.17 69.34±0.98 57.91±1.53
80.98±0.19 80.24±0.24 81.01±0.46 81.37±0.36 80.63±0.22 80.65±0.93 71.92±1.10 54.12±1.78
86.38±0.30 84.73±0.47 87.01±0.42 81.74±0.42 86.35±0.50 82.81±0.64 89.37±0.02 83.98±0.62
81.92±0.35 78.95±0.38 81.63±0.32 76.95±0.86 82.06±0.29 79.71±0.36 88.27±0.11 80.42±0.47
GraphENS TAM(G-ENS) GraphSHA
82.27±0.60 83.42±0.51 83.30±0.60
68.25±0.83 68.57±0.83 66.52±1.15
81.78±0.24 82.56±0.19 81.76±0.18
90.68±0.15 87.47±0.31 89.22±0.24
86.01±0.17 82.86±0.25 85.06±0.26
NodeImport
84.21 ±0.46
71.54 ±0.71
83.92 ±0.23
92.76 ±0.15
89.55 ±0.06
Vanilla GRAND
79.52±0.44 74.35±0.72
56.07 ±1.65 51.28±1.33
67.97±0.45 64.76±0.34
90.53 ±0.30 88.22±0.36
85.98±0.17 84.99±0.16
ReWeight PC Softmax Balanced Softmax TAM(BS) ReNode TAM(ReNode) ReVar BAT
82.29±0.49 82.78±0.41 82.74±0.53 82.84±0.37 82.31±0.43 82.72±0.39 77.40±0.55 82.17±0.52
62.10±1.38 64.11±1.29 64.63±1.35 64.32±1.41 61.99±1.68 62.66±1.44 65.70±1.03 58.65±1.61
78.94±0.31 81.13±0.23 79.80±0.37 79.35±0.38 78.41±0.15 78.13±0.54 76.80±0.65 67.80±0.49
92.77±0.06 93.15±0.07 92.91±0.08 86.29±0.19 92.43±0.07 90.54±0.15 91.82±0.02 90.63±0.09
88.00±0.03 87.46±0.17 86.87±0.20 84.06±0.33 87.83±0.04 84.83±0.13 88.33±0.13 86.41±0.18
GraphENS TAM(G-ENS) GraphSHA
82.49±0.53 83.06±0.42 82.43±0.46
68.89±1.00 69.67±0.86 62.95±1.63
83.05±0.09 82.90±0.14 77.23±0.15
93.29±0.06 90.49±0.18 93.11±0.06
87.47±0.08 85.05±0.16 88.28±0.05
NodeImport
84.87 ±0.40
71.12 ±0.84
86.30 ±0.13
93.94 ±0.06
88.00 ±0.07
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 moderatesized meta-sets achieve better overall performance.
F.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
63
63
61
64
87
88
88
88
87
62
64
64 64
61
62
61
62
60
61
62
62
61
58
0.1
0.5
1.0
2.0
4.0
62 61 60
88
2.0
63
88
88
88
87
88.4
88 88
88 89
88 88
88 88
88 88
88.0 87.8 87.6
59
89
89
88
88
87
58
0.1
0.5
1.0
2.0
4.0
(a) CiteSeer - GCN
87.4
84.0
85.0
83.5
bAcc. (%)
50
48.54% 13.18%
3.47% 0.97%
50
40
40
30
30
20
20
10 0
1.00% 5.17%
60
25.00% 55.00%
11.50% 2.33%
10 0
250
500
750
1000 1250 1500 1750 2000
Training Epoch (a) Cora - SAGE
0
0
250
500
750
1000 1250 1500 1750 2000
Training Epoch (b) CiteSeer - GAT
(b) computers - GAT
Figure 6: Sensitivity analysis of hyper-parameters 𝛽 and 𝛾.
Figure 8: Cumulative class distribution of the filtered labeled nodes as training progresses. Each line represents the cumulative distribution of a class, with the percentage in the legend indicating its initial distribution in the training set.
84.5
83.0 82.5
84.0
82.0
83.5
81.5 81.0
6.80% 1.80% 25.24%
60
88.6
88.2 1.0
64
64
0.5
62
63
Macro F1 (%)
62
0.1
0.1
0.5
1.0
2.0
63
Ratio (%)
63
Nan Chen et al.
Macro F1 (%)
61
4.0
4.0
KDD ’25, August 3–7, 2025, Toronto, ON, Canada
2
3
4
# Meta sample per class (a) Cora - GAT
5
83.0
4
8
10
# Meta sample per class (b) PubMed - GAT
15
Figure 7: Sensitivity analysis of the size of the meta-set.
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.