UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classification

Gholamali Aminian; Hamid R. Rabiee; Mohammad T. Teimuri; Zahra Dehghanian

REVIEW 5 major objections 5 minor 28 references

UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classification

T0 review · 5 major / 5 minor · reviewed 2026-08-09 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The paper proves a population-risk bound for imbalanced transductive node classification with GCNs that is driven by minority-class sample counts and degree ratios, and proposes UPL, an uncertainty-aware pseudo-labeling method.

desk verdict A decent per-class Rademacher bound, but the uncertainty mechanism the paper sells is not supported by its own ablations. read the letter →

arxiv 2502.00716 v1 pith:4VEECBA3 submitted 2025-02-02 cs.LG

Mohammad T. Teimuri , Zahra Dehghanian , Gholamali Aminian , Hamid R. Rabiee This is my paper · ORCID

classification cs.LG

keywords imbalancednodeclassificationtransductivelearningpopulationriskboundpseudo-labelinguncertaintyestimationgraphneuralnetworksbalancedsoftmaxselectiveedgeremoval

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper tries to establish that imbalanced transductive node classification has a provable generalization bottleneck, and that a specific pseudo-labeling recipe can push past it. Theorem 4.6 bounds the population risk of a depth-$d$ GCN by class-wise margin risk plus per-class terms of the form $(u_i/u)[((\deg_{\max}^{(i)}+1)/(\deg_{\min}+1))^{d-1}/\sqrt{m_i+u_i}+1/\sqrt{\min(m_i,u_i)}]$, so minority-class sample count and minority-class degree dominate the bound. The companion algorithm, UPL, pseudo-labels unlabeled minority nodes whose prediction entropy stays stable across edge-removed graphs and trains with balanced softmax. Across homophilic and heterophilic benchmarks at imbalance ratios 10, 5, and 2, UPL reports the best or second-best balanced accuracy and F1, with lower variance than prior methods. If the bound is right, it gives a theoretical reason to augment minority classes; if the empirical claim holds, UPL is a simple way to do it that also avoids the heavy clustering and reordering steps of earlier methods.

What carries the argument

The machinery is a per-class transductive Rademacher complexity bound for deep GNNs. Proposition 4.5 bounds the class-wise complexity by $B_f(\sqrt{2\log 2}\,d+1)\prod_{j=1}^d U_F(j)\,\|G_f(A)[i]\|_\infty^{2(d-1)}/\sqrt{m_i+u_i}$, and Lemma C.1 bounds the per-class graph-filter norm by $\sqrt{(\deg_{\max}^{(i)}+1)/(\deg_{\min}+1)}$, which inserts the degree ratio into Theorem 4.6 and makes the bound depend on both class sizes and topology. On the algorithmic side, the carrying mechanism is Selective Edge Removal (SER): edges are deleted with probability proportional to node degree, several inferences are run on the perturbed graphs, and the variance of prediction entropy across those runs is the uncertainty score; only nodes below a quantile $Q_\alpha$ of that score, and inside the confidence band, receive pseudo-labels. Balanced softmax then reweights the loss so that minority pseudo-labels contribute more. The result is a direct pipeline from the theoretical bottleneck—minority scarcity amplified by high-degree minority nodes—to the nodes the uncertainty signal says are safe to label.

What would settle it

Fix one dataset, imbalance ratio, and confidence band, and compare UPL against the same pipeline with the uncertainty mask replaced by random selection among nodes inside the band; if balanced accuracy and F1 do not drop, the SER uncertainty signal is not the source of the gains. The theoretical claim can be probed by constructing two Cora training splits with identical class sizes but the highest-degree node placed in the minority class versus the majority class: Theorem 4.6 predicts a measurable drop in the minority-hub split, and the absence of such a gap would undercut the degree-ratio dependence.

Watch

Extended reading notes

Core claim

On its own terms, the paper's central discovery is Theorem 4.6: for binary transductive node classification with a $d$-layer GCN, with probability at least $1-\delta$, the unlabeled risk satisfies $R(Z_u,h_\theta)\le \sum_{i=1}^2 [ R_\gamma(Z_{m_i},h_\theta) + \frac{u_i}{u}( \frac{B_f(\sqrt{2\log 2}\,d+1)\prod_{j=1}^d U_F(j)}{\gamma\sqrt{m_i+u_i}} (\frac{\deg_{\max}^{(i)}+1}{\deg_{\min}+1})^{d-1} + c_0\frac{Q_i}{\sqrt{\min(m_i,u_i)}} + \sqrt{\frac{S_iQ_i}{2}\log(1/\delta)} ) ]$. The authors read this bound as saying that the risk is dominated by the number of labeled samples in the minority class and by the maximum degree within that class. That reading motivates the UPL algorithm, which adds pseudo-labels to minority-class nodes selected by a band-pass confidence filter ($\eta_l\le P\le\eta_u$) and an uncertainty mask computed as the variance of prediction entropy over graphs with randomly removed edges. UPL trains with balanced softmax and, in the paper's experiments, reaches the highest or second-highest balanced accuracy and F1 score on Cora, CiteSeer, PubMed, Chameleon, Squirrel, Wisconsin, Computers, and Photo, while using less compute than UNREAL.

Load-bearing premise

The load-bearing premise is that low variance of prediction entropy under selective edge removal marks nodes whose pseudo-labels are worth trusting; if that proxy stops tracking label correctness under heavy imbalance, the pseudo-labels inject noise and the reported gains shrink.

Editorial extensions

If this is right

Because the dominant risk term scales as $1/\sqrt{m_i+u_i}$ for the minority class, the bound directly justifies adding pseudo-labeled minority nodes: it decreases the per-class complexity term and reduces imbalance.
The factor $((\deg_{\max}^{(i)}+1)/(\deg_{\min}+1))^{d-1}$ implies that very deep GCNs pay an exponentially larger generalization penalty on graphs where minority nodes are hubs, so depth choices should be informed by per-class degree structure.
UPL combines a band-pass confidence filter with a topology-based uncertainty mask; in the paper's ablations this combination reaches the best balanced accuracy and F1 on every main dataset, and the full method retains that ranking across GCN, GAT, and GraphSage backbones.
Compared with UNREAL, UPL avoids $O(N^2)$ node-reordering and clustering steps; the paper reports about 0.66 minutes for 10 PubMed runs versus 14.1 minutes for UNREAL with comparable or better accuracy.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

Extension: the theorem predicts a testable ordering—fix the imbalance ratio and class sizes, then vary which class contains the highest-degree nodes; balanced accuracy should drop when the minority class has the hubs, and a clean experiment on Cora or CiteSeer could confirm or refute that prediction.
Extension: because the ablation tables show that adding SER-based uncertainty without pseudo-labeling changes almost nothing, an important follow-up is to measure whether entropy-variance selection actually tracks pseudo-label correctness on the selected nodes; if it does not, the gains attributed to uncertainty may be carried by the balanced-softmax and pseudo-labeling components.
Extension: the per-class degree ratio suggests a degree-aware weighting scheme—down-weighting majority hubs or up-weighting minority low-degree nodes—that the paper does not test but that follows naturally from Theorem 4.6.
Inference: the bound is stated for binary classification with $\gamma$-margin loss, so the practical message for multiclass graphs is indirect; adapting the proof to multiclass losses would be needed before the theoretical guarantee covers the experiments UPL actually runs.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

The one thing to know: the theory is the honest part of this paper, and the algorithm's selling point—Selective Edge Removal for uncertainty—is the part that doesn't hold up. The per-class transductive Rademacher bound in Theorem 4.6 is a legitimate extension of El-Yaniv and Pechyony's framework to imbalanced node classification. It gives a class-dependent degree term, which is new as far as I know. The proof is sketchy but plausible, with standard constants. If the paper just shipped the bound and a simple pseudo-labeling baseline, it would be a solid theory paper.

What the paper does well: it states the bound cleanly, reports results across homophilic and heterophilic graphs, and the combination of balanced softmax with pseudo-labels clearly helps on most datasets. The runtime measurements showing UPL is much faster than UNREAL are concrete.

The problems are in the empirical story, and they are not minor. The ablation tables are the key evidence, and they point against the novelty. Adding uncertainty alone to vanilla changes nothing (Cora 53.28 to 53.28). Adding uncertainty to pseudo-labeling actually hurts on most datasets: on CiteSeer, +PL alone gets 48.81 bAcc and +Uncertainty+PL drops to 40.01. On Chameleon, Squirrel, and Wisconsin it also drops; only on PubMed and Photo does it help. So the central claim that uncertainty-aware selection improves pseudo-label quality is not supported by the authors' own numbers. The full UPL beats +BS+PL on several datasets, but the difference is often a couple of points, and on Chameleon it is slightly worse. Since the hyperparameters (ηl, ηu, Qα) appear to be tuned on the test set—the sensitivity plots show test F1 curves—I would not trust these small gains.

Smaller issues: UNREAL outperforms UPL on Cora in the main table, which weakens the 'superior performance' claim. The text says 'retaining the lowest 90%' while the equation uses Qα, so the selection criterion is ambiguous. No code is released. The self-citation to the authors' earlier KLCE paper is fine in context.

Who should read this: researchers working on imbalanced graph learning or transductive bounds. The bound is worth a look; the algorithm needs more careful evaluation before anyone should adopt it.

My recommendation: send it to peer review. The theory deserves scrutiny, and the negative ablation results are useful even if they contradict the paper's narrative. But I would ask for a major revision that isolates the effect of the uncertainty component, removes the test-set tuning, and releases code.

Referee Report

5 major / 5 minor

Summary. This paper studies imbalanced transductive node classification. It first derives an upper bound on the population risk (Theorem 4.6) for a depth-d GCN, expressing the bound as a sum over classes of class-wise margin risk plus terms that depend on per-class labeled/unlabeled counts and per-class maximum degrees. The paper then proposes UPL, an iterative pseudo-labeling algorithm that selects unlabeled nodes using two confidence thresholds and a topology-based uncertainty score (variance of predictive entropy across edge-perturbed graphs), trains with balanced softmax, and reports improved balanced accuracy and F1 over several baselines on homophilic and heterophilic datasets.

Significance. If the theoretical bound and empirical results both hold, the paper would provide a useful per-class generalization handle for imbalanced node classification and a practical pseudo-labeling method. The theory extends existing transductive Rademacher analysis to per-class terms, and the experiments cover multiple architectures and imbalance ratios, with UPL often achieving competitive or best results and noticeably lower variance on several datasets. The paper does not include code or machine-checked proofs, so the theoretical results rest on the correctness of the analytic derivations. However, the load-bearing components—the proof of the Rademacher bound, the claimed benefit of the uncertainty module, and the fairness of the hyperparameter selection—need to be substantiated before the claims can be accepted.

major comments (5)

[Appendix C, Prop. 4.5, and Section 4] The proof of Proposition 4.5 contains an algebraic error: the line 'E[Z] ≤ V sqrt(E_epsilon[||Σ ε_i X_i||²]) = V sqrt(E_epsilon[Σ_{i,i'} ε_i ε_i' X_i^T X_i']) = 2 V p sqrt(Σ ||X_i||²)' is incorrect. Since E[||Σ ε_i X_i||²] = 2p Σ ||X_i||², the correct factor is V sqrt(2p) sqrt(Σ ||X_i||²), not 2 V p sqrt(...). This error propagates to the choice of λ and to the final constant in Theorem 4.6, where an extra factor of 2 appears after substituting p = m_k u_k / (m_k + u_k)². In addition, the main text defines p as 'm+u/(m+u)²', which is inconsistent with the appendix's p = m_k u_k/(m_k + u_k)². Since Theorem 4.6 is the central theoretical contribution, these issues must be fixed or the theorem restated with the correct constant.
[Table 3 and Table 17] The ablation study does not support the claim that uncertainty-aware selection (SER) contributes to UPL's performance. Adding the uncertainty module to Vanilla leaves results essentially unchanged (Cora bAcc 53.28 → 53.28; CiteSeer 35.53 → 35.53; PubMed 61.96 → 61.96), adding it to Balanced Softmax gives identical or slightly worse numbers (Squirrel 41.76 → 41.70), and adding it to PL degrades results on several datasets (CiteSeer 48.81 → 40.01; Wisconsin 38.62 → 36.92). The only consistent improvements come from the BS+PL combination, not from the SER uncertainty component. The paper should either provide evidence (e.g., pseudo-label accuracy under SER vs confidence-only selection) that low entropy variance correlates with label correctness, or reposition the contribution away from uncertainty-awareness.
[Section 6 and Appendix E (Figure 2, Table 7)] The hyperparameters ηl, ηu, and Qα are selected using test-set F1: Figure 2 plots 'Test f1-score' and 'Validation f1-score' for the sweep, and the text reports that optimal thresholds are chosen from these curves. Appendix E confirms that ηl, ηu, and Qα are fine-tuned. Tuning on the test set invalidates the reported performance comparisons as estimates of generalization. The authors should use a separate validation split (or nested cross-validation) and report the selection procedure explicitly.
[Section 5.1, Eq. (3), Algorithm 1] The prose in Section 5.1 states 'we also add pseudo-labels to minority classes and avoid the pseudo-labels for majority classes during training,' but neither Eq. (3) nor Algorithm 1 conditions pseudo-label selection on the predicted class being a minority class. The pseudocode loops over all unlabeled nodes and selects any node satisfying the thresholds and uncertainty bound. This discrepancy makes the method ambiguous and the implementation irreproducible; the authors should state whether minority-class restriction is applied and, if so, add it to the equation and pseudocode.
[Tables 1 and 2] The 'GraphENS + TAM' baseline is a combination of two separately proposed methods, but no description is given of how the two are combined, which hyperparameters are used for the combination, or whether this combined baseline has been published. Comparing against an ad-hoc combined baseline is nonstandard and makes the superiority claim harder to interpret; the authors should compare against GraphENS and TAM individually and justify or remove the combined row.

minor comments (5)

[Section 3] The definitions of P_j and H(P,Q) are malformed; for example, 'Pj = |mj |Pk i=1 |mi|' lacks the division sign, and the cross-entropy integral is written incorrectly.
[Section 4] The definition of p as 'm+u/(m+u)²' is likely a typo; it should be p = mu/(m+u)² to match Appendix C and the standard transductive Rademacher setup.
[Theorem 4.6] The degree ratio in the bound is written with 'degmin +1' without a subscript, while the discussion refers to the minimum degree of all graph nodes; please clarify the notation in the theorem statement.
[Table 2 and Appendix F] The caption of Table 2 says ρ=10, but Appendix F reports Wisconsin with ρ=11.63; either change the imbalance ratio for Wisconsin or label the row separately.
[Algorithm 1] The line 'Y p ← Ynew' appears to be a typo for 'Yp ← Ynew'; also the algorithm does not specify how many pseudo-labels are added per minority class, which is relevant to the imbalance-ratio discussion.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 4.6 is assembled from external transductive Rademacher bounds and elementary graph-filter norm estimates, and UPL's empirical claims rest on experiments rather than fitted quantities relabeled as predictions.

full rationale

The derivation chain is self-contained and non-circular. Proposition 4.4 applies the external transductive Rademacher bound of El-Yaniv and Pechyony per class (Appendix C, Eq. 9), Proposition 4.5 bounds the GNN transductive Rademacher complexity from Assumptions 4.1-4.3 using a sub-Gaussian concentration argument, and Theorem 4.6 combines these with Lemma C.1, an elementary bound on the infinite norm of the symmetric normalized graph filter. No step defines the target bound in terms of itself, and no fitted parameter is later reported as a prediction. The UPL algorithm's pseudo-label mask (Eq. 3) and thresholds ηl, ηu, Qα are tuned and evaluated empirically (Table 7, Section 6), which is selection bias rather than circularity. The only self-citation, Jervakani et al. (2024), appears in Related Work as background and is not load-bearing for Theorem 4.6 or for UPL. A separate support concern, not a circularity one, is flagged: Section 5.1 assumes low variance of prediction entropy across edge-perturbed graphs identifies reliable nodes, but no evidence links this proxy to label correctness under heavy imbalance, and Tables 3 and 17 show +Uncertainty alone leaves results essentially unchanged while BS+PL captures most of the UPL gain; this weakens empirical support for the novel SER component but does not make any prediction equivalent to its input.

Assumptions & free parameters 6 free parameters · 8 assumptions · 0 invented entities

The theoretical bound rests on standard boundedness and Lipschitz assumptions, prior transductive Rademacher results, and an i.i.d. feature assumption that is standard but not realistic for graphs. The algorithm rests on an unproved correlation between entropy variance after edge perturbations and pseudo-label correctness. Main tuned quantities are pseudo-label thresholds and uncertainty quantiles.

free parameters (6)

eta_l (lower pseudo-label threshold) = range 0.25 to 0.90; optimal range 0.25-0.45 on CiteSeer sweep
Lower threshold for confidence band in Eq. (3); tuned per dataset in Section 6 and Appendix F.1.
eta_u (upper pseudo-label threshold) = range min(eta_l + 0.25n, 1.00), n <= 3; optimal range 0.35-0.45 on Cora sweep
Upper threshold creating a band-pass confidence selection; tuned per dataset.
Q_alpha (uncertainty quantile) = alpha in {0.7, 0.8, 0.9}
Quantile threshold for retaining low-uncertainty nodes; selected per dataset from three values.
t (number of edge-perturbation iterations) = 100
Number of perturbed graph inferences; chosen from sensitivity sweep in Figure 3.
S_k (edges removed per iteration) = 100
Number of edges removed each iteration; chosen from sensitivity sweep in Figure 3.
BalancedSoftmax alpha = same values as Song et al. (2022)
Borrowed from prior work rather than tuned; controls class-frequency weighting in Eq. (5).

assumptions (8)

domain assumption Bounded node features: ||X[i,:]||_2 <= B_f for all nodes
Assumption 4.1, used in the Rademacher complexity bound.
domain assumption Bounded layer parameter norms: ||theta_i||_F <= U_F(i)
Assumption 4.2, used in the Rademacher complexity bound.
domain assumption Activation functions are 1-Lipschitz and zero-centered
Assumption 4.3, used in the Rademacher complexity bound.
domain assumption Node features are i.i.d. samples from the feature space
Section 3 Preliminaries; standard but unrealistic for graph nodes whose structure is fixed.
domain assumption Graph is undirected, has no self-loops or multiple edges, and adjacency is fixed
Section 3, defines the setting for the transductive analysis.
standard math El-Yaniv and Pechyony transductive Rademacher bound holds when applied per class
Used directly in the proof of Proposition 4.4 as Corollary 1 of El-Yaniv and Pechyony (2009).
domain assumption Binary classification and gamma-margin loss for the theoretical analysis
Section 4 restricts the theory to binary classification with gamma-margin loss.
ad hoc to paper Low variance of prediction entropy across edge-perturbed graphs indicates reliable pseudo-labels
Section 5.1, Eq. (3); this is the core heuristic behind UPL and is not proven.

how reviews work

0 comments

Cite this review

Pith. "Pith review of UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classification." pith.science (2026). https://pith.science/paper/4VEECBA3

@misc{pith2026250200716,
  author       = {Pith},
  title        = {Pith review of: UPL: Uncertainty-aware Pseudo-labeling for Imbalance Transductive Node Classification},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4VEECBA3}},
  note         = {Machine review of arXiv:2502.00716}
}

read the original abstract

Graph-structured datasets often suffer from class imbalance, which complicates node classification tasks. In this work, we address this issue by first providing an upper bound on population risk for imbalanced transductive node classification. We then propose a simple and novel algorithm, Uncertainty-aware Pseudo-labeling (UPL). Our approach leverages pseudo-labels assigned to unlabeled nodes to mitigate the adverse effects of imbalance on classification accuracy. Furthermore, the UPL algorithm enhances the accuracy of pseudo-labeling by reducing training noise of pseudo-labels through a novel uncertainty-aware approach. We comprehensively evaluate the UPL algorithm across various benchmark datasets, demonstrating its superior performance compared to existing state-of-the-art methods.

Figures

Figures reproduced from arXiv: 2502.00716 by the authors.

**Figure 1.** Pipeline of the UPL Algorithm 5. UPL Algorithm In this section, we introduce the Uncertainty-aware Pseudolabeling (UPL) Algorithm to mitigate the imbalance effect in transductive node classification. In the UPL algorithm, we add pseudo-labels to unlabeled nodes of minority classes to mitigate the effect of imbalance node classification. Our UPL algorithm contains two blocks: uncertainty-aware pseudo-labeling, and b… view at source ↗

**Figure 2.** F1-score for different values of upper and lower [PITH_FULL_IMAGE:figures/full_fig_p007_2.png] view at source ↗

**Figure 3.** Selection Edge Removal: F1 score versus number of iterations and number of edges for removal. Each plot is [PITH_FULL_IMAGE:figures/full_fig_p024_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

28 extracted references · 22 canonical work pages

[1]

Repeating the process, we arrive at mkuk mk + uk ˆRmi+ui (H) ≤ 1 λ log 2d · Eϵ exp M λ mk+ukX i=1 ϵiXi !!

· ∥Gf (A)∥2 ∞λ mk+ukX i=1 ϵiNθd−1 (Xuk+mk ) !! . Repeating the process, we arrive at mkuk mk + uk ˆRmi+ui (H) ≤ 1 λ log 2d · Eϵ exp M λ mk+ukX i=1 ϵiXi !! . (11) where V = ∥Gf (A)∥2(d−1) ∞ Qd j=1 UF (j). Define a random variable Z = V · mX i=1 ϵiXi , (random as a function of the random variables ϵ1, . . . , ϵm). Then 1 λ log 2d · E exp λZ = d log(2) λ + 1...

work page 2003
[2]

Then, with probability at least (1 − δ) over the choice of the training set from nodes of graphs, for all hθ ∈ H, R(Zu, hθ) ≤ 2X i=1 Rγ(Zmi , hθ) + ui u 1 γ Rmi+ui (H) + c0Qi p min(mi, ui) + r SiQi 2 log(1/δ) , where Rmi+ui (H) is the transductive Rademacher complexity for i-th class, Rγ(Zmi , hθ) is the empirical risk based on γ-margin loss for i-th clas...

work page 2009
[5]

Jervakani, M. T. T., Dehghanian, Z., Aminian, G., and Rabiee, H. R. Klce: Regularized imbalance node- classification via kl-divergence and cross-entropy. In The Second Tiny Papers Track at ICLR 2024,

work page 2024
[6]

Table 6: Dataset statistics

Note that in the Amazon Computers and Amazon Photos datasets (Shchur et al., 2019), nodes represent products and edges denote co-purchasing relationships between them. Table 6: Dataset statistics. Dataset Nodes Edges Classes Features CiteSeer 3,327 4,732 6 3,703 Cora 2,708 5,429 7 1,433 Pubmed 19,717 44,338 3 500 Chameleon 2277 36101 5 2325 Squirrel 5201 ...

work page 2019
[7]

Experiments Setup UPL contains two tunable hyperparameters used for the pseudo labels threshold and three fixed ones which have approximated using a few experiments

F. Experiments Setup UPL contains two tunable hyperparameters used for the pseudo labels threshold and three fixed ones which have approximated using a few experiments. Other extra hyperparameters have been adjusted according to (Song et al., 2022). We will discuss the setting for these parameters in the following sections. F.1. UPL We employ two threshol...

work page 2022
[8]

Confidence may cheat: Self-training on graph neural networks under distribution shift

Liu, H., Hu, B., Wang, X., Shi, C., Zhang, Z., and Zhou, J. Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference, pp. 1454–1463, 2022a. Liu, Y ., Zhang, Z., Liu, Y ., and Zhu, Y . Gatsmote: Improv- ing imbalanced node classification on graphs via attention and homophily. Mathematic...

work page 2022
[10]

E., Rahmani, A

Mohammadrezaei, M., Shiri, M. E., Rahmani, A. M., et al. Identifying fake accounts on social networks based on graph analysis and classification algorithms. Security and Communication Networks, 2018,

work page 2018
[15]

Towards Understanding the Generalization of Graph Neural Networks

Tang, H. and Liu, Y . Towards understanding the gen- eralization of graph neural networks. arXiv preprint arXiv:2305.08048,

work page Pith review arXiv

Show all 28 references

[16]

Effective-aggregation graph convolutional network for imbalanced classifica- tion

Wang, K., An, J., and Kang, Q. Effective-aggregation graph convolutional network for imbalanced classifica- tion. In 2022 IEEE International Conference on Net- working, Sensing and Control (ICNSC), pp. 1–5. IEEE,

2022
[17]

Unreal: Unlabeled nodes retrieval and labeling for heavily-imbalanced node classification

11 Imbalance Transductive Node Classification Yan, L., Zhang, S., Li, B., Zhou, M., and Huang, Z. Unreal: Unlabeled nodes retrieval and labeling for heavily-imbalanced node classification. arXiv preprint arXiv:2303.10371,
[18]

Flexmatch: Boosting semi- supervised learning with curriculum pseudo labeling

Zhang, B., Wang, Y ., Hou, W., Wu, H., Wang, J., Oku- mura, M., and Shinozaki, T. Flexmatch: Boosting semi- supervised learning with curriculum pseudo labeling. Ad- vances in Neural Information Processing Systems , 34: 18408–18419, 2021a. Zhang, W., Shen, Y ., Li, Y ., Chen, L...

2021
[19]

Table 5: Summary of notations in the paper Notation Definition Notation Definition A Adjacency matrices space Xi i-th node feature degmax i Maximum node degree i-th class degmin i Minimum node degree i-th class Yi i-th node’s label Zi i-th node sample pair(Xi, Yi) Zm The set o...

2013
[20]

(Kou et al.,

and (Rizve et al., 2021). (Kou et al.,

2021
[21]

The study by Pham et al

shows that semi-supervised learning with pseudo-labeling can achieve near-zero test loss under some conditions. The study by Pham et al. (2020) introduced meta pseudo-labeling. This method enhanced pseudo-labels’ accuracy by incorporating feedback from the student model. (Rizv...

2020
[22]

In contrast, our work is focused on transductive node classification, and we employed the Pseudo-labels to mitigate the imbalance effect

suggests soft-labeling with the MixUp method to reduce over-fitting to model predictions and confirmation bias. In contrast, our work is focused on transductive node classification, and we employed the Pseudo-labels to mitigate the imbalance effect. Imbalance Classification: E...

2018
[28]

Both Sk and t are fixed to 100, and the quantile for uncertainty-based node selection is chosen from {Q0.7, Q0.8, Q0.9}

| n ≤ 3, n∈ N}. Both Sk and t are fixed to 100, and the quantile for uncertainty-based node selection is chosen from {Q0.7, Q0.8, Q0.9}. 18 Imbalance Transductive Node Classification Table 7: Tuned hyperparameters used in our work compared with those from previous methods Meth...

2020
[29]

Training: To choose the training mask, we use the training masks provided by Pytorch Geometric

C0 C1 C2 C3 C4 C5 C6 C7 C8 C9 Cora 20 20 20 20 2 2 2 - - - CiteSeer 20 20 20 2 2 2 - - - - PubMed 20 20 2 - - - - - - - Chameleon 225 220 218 22 22 - - - - - Squirrel 487 494 501 50 50 - - - - - Wisconsin (ρ = 11.63) 4 38 50 5 5 - - - - - Computers 20 20 20 20 20 2 2 2 2 2 Pho...

1904
[30]

bAcc. F1 bAcc. F1 bAcc. F1 GCN Vanilla 66.95 ± 0.73 66.67 ± 0.69 49.53 ± 0.38 49.59 ± 0.38 39.63 ± 2.14 38.28 ± 2.26 BalancedSoftmax 67.10 ± 0.79 66.78 ± 0.73 50.00 ± 0.47 49.74 ± 0.48 44.81 ± 3.18 41.32 ± 2.32 Graphens + TAM 43.76 ± 1.08 41.49 ± 1.38 26.98 ± 0.79 23.69 ± 0.67...

2018
[2002]

V ., Lazarevic, A., Hall, L

Chawla, N. V ., Lazarevic, A., Hall, L. O., and Bowyer, K. W. Smoteboost: Improving prediction of the minority class in boosting. In Knowledge Discovery in Databases: PKDD 2003: 7th European Conference on Principles and Practice of Knowledge Discovery in Databases, Cavtat- Dub...

2003
[2003]

W., and Chang, K

Cai, H., Zheng, V . W., and Chang, K. C.-C. Active learning for graph embedding. arXiv preprint arXiv:1705.05085,

arXiv
[2006]

This imbalance often presents challenges, as many classifiers tend to prefer the majority class, sometimes to the extent of completely overlooking the minority class

such as fraud detection in finance applications (Wei et al., 2013). This imbalance often presents challenges, as many classifiers tend to prefer the majority class, sometimes to the extent of completely overlooking the minority class. Traditional Class Imbalance Learning metho...

2013
[2017]

A., and Li, S

He, H., Bai, Y ., Garcia, E. A., and Li, S. Adasyn: Adap- tive synthetic sampling approach for imbalanced learning. In 2008 IEEE international joint conference on neural networks (IEEE world congress on computational intelli- gence), pp. 1322–1328. Ieee,

2008
[2018]

and Pechyony, D

El-Yaniv, R. and Pechyony, D. Stable transductive learn- ing. In Learning Theory: 19th Annual Conference on Learning Theory, COLT 2006, Pittsburgh, PA, USA, June 22-25,

2006
[2019]

Shi, M., Tang, Y ., Zhu, X., Wilson, D., and Liu, J

URL https://arxiv.org/abs/1811.05868. Shi, M., Tang, Y ., Zhu, X., Wilson, D., and Liu, J. Multi- class imbalanced graph convolutional network learning. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI-20),

arXiv
[2020]

Pham, H., Dai, Z., Xie, Q., and Le, Q

URL https: //arxiv.org/abs/2003.10580. Pham, H., Dai, Z., Xie, Q., and Le, Q. V . Meta pseudo labels. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 11557–11568,

2003 arXiv
[2022]

Ma, Y ., Tian, Y ., Moniz, N., and Chawla, N. V . Class- imbalanced learning on graphs: A survey. arXiv preprint arXiv:2304.04300,

arXiv
[2023]

Laurikkala, J

URL https: //openreview.net/forum?id=Dzmd-Cc8OI. Laurikkala, J. Improving identification of difficult small classes by balancing class distribution. In Artificial Intel- ligence in Medicine: 8th Conference on Artificial Intelli- gence in Medicine in Europe, AIME 2001 Cascais, ...

2001
[2024]

Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. arXiv preprint arXiv:1609.02907, 2016a. Kipf, T. N. and Welling, M. Semi-supervised classifica- tion with graph convolutional networks. In International Conference on Learning Repre...

arXiv

Pith tools

Reviewed August 9, 2026 · model on record in the stance chip above.

[1] [1]

Repeating the process, we arrive at mkuk mk + uk ˆRmi+ui (H) ≤ 1 λ log 2d · Eϵ exp M λ mk+ukX i=1 ϵiXi !!

· ∥Gf (A)∥2 ∞λ mk+ukX i=1 ϵiNθd−1 (Xuk+mk ) !! . Repeating the process, we arrive at mkuk mk + uk ˆRmi+ui (H) ≤ 1 λ log 2d · Eϵ exp M λ mk+ukX i=1 ϵiXi !! . (11) where V = ∥Gf (A)∥2(d−1) ∞ Qd j=1 UF (j). Define a random variable Z = V · mX i=1 ϵiXi , (random as a function of the random variables ϵ1, . . . , ϵm). Then 1 λ log 2d · E exp λZ = d log(2) λ + 1...

work page 2003

[2] [2]

Then, with probability at least (1 − δ) over the choice of the training set from nodes of graphs, for all hθ ∈ H, R(Zu, hθ) ≤ 2X i=1 Rγ(Zmi , hθ) + ui u 1 γ Rmi+ui (H) + c0Qi p min(mi, ui) + r SiQi 2 log(1/δ) , where Rmi+ui (H) is the transductive Rademacher complexity for i-th class, Rγ(Zmi , hθ) is the empirical risk based on γ-margin loss for i-th clas...

work page 2009

[3] [5]

Jervakani, M. T. T., Dehghanian, Z., Aminian, G., and Rabiee, H. R. Klce: Regularized imbalance node- classification via kl-divergence and cross-entropy. In The Second Tiny Papers Track at ICLR 2024,

work page 2024

[4] [6]

Table 6: Dataset statistics

Note that in the Amazon Computers and Amazon Photos datasets (Shchur et al., 2019), nodes represent products and edges denote co-purchasing relationships between them. Table 6: Dataset statistics. Dataset Nodes Edges Classes Features CiteSeer 3,327 4,732 6 3,703 Cora 2,708 5,429 7 1,433 Pubmed 19,717 44,338 3 500 Chameleon 2277 36101 5 2325 Squirrel 5201 ...

work page 2019

[5] [7]

Experiments Setup UPL contains two tunable hyperparameters used for the pseudo labels threshold and three fixed ones which have approximated using a few experiments

F. Experiments Setup UPL contains two tunable hyperparameters used for the pseudo labels threshold and three fixed ones which have approximated using a few experiments. Other extra hyperparameters have been adjusted according to (Song et al., 2022). We will discuss the setting for these parameters in the following sections. F.1. UPL We employ two threshol...

work page 2022

[6] [8]

Confidence may cheat: Self-training on graph neural networks under distribution shift

Liu, H., Hu, B., Wang, X., Shi, C., Zhang, Z., and Zhou, J. Confidence may cheat: Self-training on graph neural networks under distribution shift. In Proceedings of the ACM Web Conference, pp. 1454–1463, 2022a. Liu, Y ., Zhang, Z., Liu, Y ., and Zhu, Y . Gatsmote: Improv- ing imbalanced node classification on graphs via attention and homophily. Mathematic...

work page 2022

[7] [10]

E., Rahmani, A

Mohammadrezaei, M., Shiri, M. E., Rahmani, A. M., et al. Identifying fake accounts on social networks based on graph analysis and classification algorithms. Security and Communication Networks, 2018,

work page 2018

[8] [15]

Towards Understanding the Generalization of Graph Neural Networks

Tang, H. and Liu, Y . Towards understanding the gen- eralization of graph neural networks. arXiv preprint arXiv:2305.08048,

work page Pith review arXiv