{"id":"f27586ea-dca2-43ab-b121-3956a98ae933","arxiv_id":"2502.00716","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":6,"one_line_summary":"The paper derives a per-class generalization bound for imbalanced transductive node classification and introduces UPL, a pseudo-labeling algorithm that filters minority-class pseudo-labels by entropy variance across edge-perturbed graphs.","lead":"This paper presents UPL, a pseudo-labeling method for imbalanced node classification on graphs, plus an upper bound on transductive population risk. The bound and algorithm aim to improve classification of minority-class nodes without corrupting graph structure.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The uncertainty proxy in UPL (low entropy variance under edge removal) is not shown to correlate with pseudo-label correctness, and ablations show BS+PL alone captures most gains, so the novel SER component may be unnecessary.","rationale":"I agree with the reader's weakest assumption: the load-bearing point is whether the SER uncertainty proxy identifies trustworthy pseudo-labels under heavy imbalance. The ablation evidence is the most direct way to see this: the uncertainty block has no effect when added alone, and UPL minus uncertainty (BS+PL) achieves close to the full method's performance on several datasets, sometimes within noise. This makes the novel contribution fragile. The theory in Theorem 4.6 is a reasonable per-class transductive bound and does not depend on the uncertainty mechanism, so the theoretical half of the paper is in better shape; however, the algorithm's practical superiority, which is half of the central claim, hinges entirely on the pseudo-label selection quality. The paper also contains auxiliary concerns, such as the algorithm-text inconsistency about restricting pseudo-labels to minority classes and the use of a combined GraphENS+TAM baseline, but these are secondary. The concrete test I propose would settle whether the uncertainty component matters: randomized gating at the same selection rate isolates the SER signal end-to-end, and an oracle precision check directly tests the stated reliability assumption. Given the reader already issued a CONDITIONAL verdict and my concern is the same one, the verdict should remain CONDITIONAL; no change is needed.","tokens_in":30860,"tokens_out":6792,"duration_ms":72437,"concrete_test":"On Cora and Chameleon with ρ=10, run UPL but replace the SER uncertainty ranking (Equation 3) with a random subset of unlabeled nodes of the same size (same Q_α quantile), keeping BS+PL and all hyperparameters identical. If the random-gate version matches UPL's balanced accuracy and F1 within one standard error over 10 seeds, the uncertainty proxy is not responsible for the gains and the central algorithm claim is unsupported. Independently, compute the oracle precision of SER-selected pseudo-labels versus random selection on the unlabeled nodes; if SER precision is not significantly higher, the proxy does not track label correctness.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central practical claim is that UPL's uncertainty-aware pseudo-labeling improves imbalanced node classification. That claim rests on the assumption in Section 5.1 that nodes with low variance of prediction entropy across edge-perturbed graphs are reliable enough to pseudo-label. The paper offers no direct evidence for this correlation in a heavily imbalanced regime. The ablations in Tables 3 and 17 are consistent with the uncertainty component being nearly inert: adding uncertainty alone leaves results essentially unchanged (e.g., Cora 53.28 to 53.28, Squirrel 37.70 to 37.78), and the full UPL only marginally exceeds BS+PL on most datasets (e.g., Cora 76.16 vs 75.27, PubMed 77.50 vs 76.08; Chameleon is slightly worse 61.19 vs 61.26). Because the theory in Theorem 4.6 motivates adding minority samples but does not analyze pseudo-label selection, the algorithm's novel SER mechanism is the only part of the practical contribution that is not independently supported. If low entropy variance simply tracks the model's confidence or node degree, SER may be an expensive proxy that adds no signal beyond ordinary confidence-based pseudo-labeling, and the reported gains would come from BS plus generic pseudo-labeling rather than from uncertainty-awareness.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":31178,"tokens_out":10481,"duration_ms":92502,"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":[{"comment":"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.","section":"Appendix C, Prop. 4.5, and Section 4"},{"comment":"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":"Table 3 and Table 17"},{"comment":"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":"Section 6 and Appendix E (Figure 2, Table 7)"},{"comment":"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.","section":"Section 5.1, Eq. (3), Algorithm 1"},{"comment":"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.","section":"Tables 1 and 2"}],"minor_comments":[{"comment":"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":"Section 3"},{"comment":"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.","section":"Section 4"},{"comment":"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.","section":"Theorem 4.6"},{"comment":"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.","section":"Table 2 and Appendix F"},{"comment":"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.","section":"Algorithm 1"}],"recommendation":"major_revision","confidential_remarks":"The paper does not include code or a reproducibility statement; given the hyperparameter-selection concerns, a code release or detailed protocol would be valuable. The combined 'GraphENS+TAM' baseline is unusual; if it is not a published method, the editor may wish to ask the authors to justify its use. The closest prior work, KLCE (Jervakani et al., 2024), is cited but never compared experimentally; this is a notable omission given that the same group proposed it."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe 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.\n\nWhat 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.\n\nThe 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.\n\nSmaller 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.\n\nWho 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.\n\nMy 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.","headline":"A decent per-class Rademacher bound, but the uncertainty mechanism the paper sells is not supported by its own ablations.","tokens_in":31707,"tokens_out":4612,"would_cite":false,"duration_ms":42667,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["imbalanced node classification","transductive learning","population risk bound","pseudo-labeling","uncertainty estimation","graph neural networks","balanced softmax","selective edge removal"],"falsifier":"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.","tokens_in":30679,"feed_emoji":"⚖️","tokens_out":12661,"duration_ms":101573,"temperature":0.7,"pith_summary":"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.","feed_headline":"Minority-class size and degree drive imbalanced graph risk","feed_subtitle":"Theorem 4.6 ties transductive risk to per-class counts and degrees; UPL adds stable minority pseudo-labels.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the transductive Rademacher complexity bound (their Corollary 1) that the paper splits class-by-class to prove Proposition 4.4.","marker":"(El-Yaniv & Pechyony, 2009)"},{"why":"Supplies the $\\gamma$-margin loss whose class-wise empirical risk appears in Theorem 4.6.","marker":"(Bartlett et al., 2017)"},{"why":"Supplies the symmetric normalized graph filter that Lemma C.1 bounds per class.","marker":"(Kipf & Welling, 2016b)"},{"why":"Supplies the bounded-difference and sub-Gaussian concentration argument used in the proof of Proposition 4.5.","marker":"(Boucheron et al., 2003)"},{"why":"Supplies the uncertainty-aware pseudo-label selection design (confidence thresholds plus uncertainty filtering) that UPL adapts with graph-based edge removal.","marker":"(Rizve et al., 2021)"},{"why":"Supplies the balanced softmax loss that UPL uses to reweight minority pseudo-labels.","marker":"(Ren et al., 2020)"}],"fun_headline_variants":["UPL: Uncertainty-aware pseudo-labels for imbalanced graphs","New bound ties graph risk to minority class size and degree","UPL cuts pseudo-label noise to boost imbalanced node classification","Uncertainty masks improve pseudo-labels for minority graph nodes","Imbalanced graph learning improved by uncertainty filtering"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["UPL: Uncertainty-aware pseudo-labels for imbalanced graphs","New bound ties graph risk to minority class size and degree","UPL cuts pseudo-label noise to boost imbalanced node classification","Uncertainty masks improve pseudo-labels for minority graph nodes","Imbalanced graph learning improved by uncertainty filtering"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000272,"raw_usage":{"total_tokens":1650,"prompt_tokens":978,"completion_tokens":672,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":594,"completion_tokens_details":{"reasoning_tokens":591}},"tokens_in":594,"tokens_out":672,"duration_ms":7422,"temperature":1.0,"reasoning_tokens":591,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-09T17:59:01.263093+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"(Kou et al.,","cited_arxiv_id":null,"evidence_quote":"Supplies the uncertainty-aware pseudo-label selection design (confidence thresholds plus uncertainty filtering) that UPL adapts with graph-based edge removal."}],"review_version":1}