Pith. sign in

REVIEW 4 major objections 5 minor 30 references

Robust OOD Graph Learning via Mean Constraints and Noise Reduction

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

Pith's one-line read Graph OOD minority-class accuracy rises with two ERM add-ons

desk verdict A useful empirical recipe for minority-class graph OOD, but NNR is underspecified and the theory's key assumption is circular; worth peer review if the method is pinned down. read the letter →

arxiv 2506.19281 v1 pith:H3AOCHLW submitted 2025-06-24 cs.LG

classification cs.LG
keywords graphout-of-distributionlearningclassimbalanceminorityaccuracydistributionallyrobustoptimizationnoisereweightingneuralnetworksDrugOODPAC-Bayesianbound
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 argues that graph out-of-distribution classification fails hardest on rare classes when labels are imbalanced and structure is noisy, and that two simple add-ons to standard empirical risk minimization fix much of that failure. The first add-on, Constrained Mean Optimization (CMO), adds a class-similarity constraint to the worst-case (distributionally robust) objective; the second, Neighbor-Aware Noise Reweighting (NNR), down-weights samples whose local neighborhood is not label-consistent. On synthetic six-class data the combined method raises the best maximum minority-class accuracy from 71.6% and 74.7% to 80.2% and 79.8% at the two highest noise levels, and on the DrugOOD benchmark it lifts upper-bound minority accuracy to 47.2%, 34.9%, and 48.0% on the Assay, Scaffold, and Size splits. A reader should care because minority-class performance under shift and noise is a practical bottleneck for deploying graph models.

What carries the argument

Two mechanisms carry the argument. CMO is a constrained optimization layer on top of distributionally robust optimization: it keeps the usual worst-case reweighting objective but adds the constraint $\Delta(Q) = \sum_{i<j} \|\mu(Q_i) - \mu(Q_j)\|^2 < \rho_2$, the sum of squared distances between class-conditional feature means, so the worst-case distribution is chosen among assignments that respect class similarity. NNR is a per-sample loss weight $w_i = N_{\mathrm{hom}}(G_i)/N_{\mathrm{sum}}(G_i)$, the fraction of same-class neighbors within a graph distance $\Gamma$, applied as $\ell_i = w_i \ell_i^{\mathrm{raw}}$; it is supposed to make noisy samples, which have fewer same-class neighbors, contribute less. These are complemented by a Lagrange update for $q$ and $\theta$, convergence theorems for convex and non-convex losses, and a PAC-Bayesian bound that expresses OOD error as three terms involving class centers, feature means, and neighbor ratios.

What would settle it

Recompute the synthetic experiments with NNR's neighborhood defined in raw input space instead of embedding space; if the best maximum minority-class accuracy drops from 80.2% to near baseline, then the gain hinges on an unspecified distance choice rather than on the proposed mechanism.

Watch

Extended reading notes

Core claim

The paper's central claim is that the minority-class drop in graph OOD classification is driven mainly by two correctable mechanisms—the model ignoring rare classes and the model overweighting noisy examples—and both can be corrected while keeping the standard ERM backbone. CMO regularizes the DRO update toward class distributions whose means are close, encoding the prior that hard classification cases are between similar classes; NNR multiplies each training loss by $w_i = N_{\mathrm{hom}}(G_i)/N_{\mathrm{sum}}(G_i)$, the fraction of nearby same-class neighbors, so isolated and likely noisy graphs contribute less. The authors report that on synthetic data the combined method reaches 80.2% and 79.8% maximum minority-class accuracy versus 71.6% and 74.7% for the best baselines, and on real-world DrugOOD data the upper-bound minority accuracy rises to 47.2% (Assay), 34.9% (Scaffold), and 48.0% (Size). They also provide convergence theorems for the CMO update and a PAC-Bayesian OOD generalization bound, arguing that the error bound decomposes into terms NNR's weights can control.

Load-bearing premise

The method assumes that counting 'same-class neighbors' of a graph makes sense, yet it never defines what a neighbor of a graph is; if that count is meaningless or mistakes rare clean samples for noise, the reported gains disappear.

Editorial extensions

If this is right

  • If the claims hold, any ERM-trained graph classifier can be retrofitted with CMO and NNR without changing the backbone architecture.
  • At high noise ratios, maximum minority-class accuracy rises from 71.6% and 74.7% to 80.2% and 79.8%, making the model substantially more usable when rare classes matter.
  • The two modules are complementary: CMO stabilizes gains across settings, while NNR adds a noise-suppression effect that occasionally costs 0.2%–0.3% average accuracy.
  • On the DrugOOD benchmark splits, upper-bound minority accuracy improves to 47.2%, 34.9%, and 48.0% respectively, indicating the method transfers beyond synthetic data.
  • The theoretical sections imply the method converges at $O(1/T)$ for convex losses and to stationary points for non-convex losses, so the reported gains are not bought by unstable optimization.

Reading between the lines

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

  • Beyond the paper's claims, a testable reading is that NNR's unspecified 'neighbor' relation can be pinned down as a nearest-neighbor query in the GNN embedding space; comparing Euclidean, cosine, and label-based neighborhoods would show which one reproduces the reported weights.
  • CMO's class-similarity prior is not graph-specific, so the same constraint could be tested on image and text classifiers, where class means are straightforward to estimate.
  • If NNR is pushed to higher noise levels, the assumption that noisy samples have fewer same-class neighbors may invert as labels themselves become random; tracking how NNR's weight distribution changes as the noise ratio crosses 0.2 would reveal where the method breaks.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes two modules for graph out-of-distribution (OOD) classification under class imbalance and label noise: Constrained Mean Optimization (CMO), which adds a class-mean constraint to a DRO objective, and Neighbor-Aware Noise Reweighting (NNR), which downweights samples with few same-class neighbors. The authors provide convergence theorems for the optimization, an OOD generalization bound based on PAC-Bayes arguments, and experiments on synthetic data plus DrugOOD, reporting gains in minority-class accuracy for the combined method.

Significance. If the empirical claims held, the work would address a practically relevant gap: minority-class robustness under both imbalance and structural noise in graph classification. The paper has some strengths: it benchmarks against a broad set of DRO baselines, it includes a code link, and the synthetic dataset explicitly varies noise and correlation strength. However, the theoretical component is not verifiable (proofs deferred to a missing supplement) and the key OOD bound relies on a circular assumption. More importantly, the NNR module is underspecified as written, and the headline empirical comparisons are based on best-over-seed numbers rather than averages. These issues undermine the central claims.

major comments (4)
  1. [Section 3.3, Eq. (18)] The NNR weight w_i = N_hom(G_i)/N_sum(G_i) is undefined as a method for graph classification. For graph-level classification, each G_i is an entire graph and there is no given neighborhood relation among the training graphs; the paper does not specify whether 'same-class neighbors within a certain distance' means neighbors in input space, in the GNN embedding space, or in label space, nor what distance function is used. Assumption 3 in Section 3.4 merely postulates that such near sets are disjoint and equal-sized without connecting to any concrete construction. As a result, Eq. (18) is not implementable from the description, and the reported NNR gains are not reproducible or falsifiable as written; if 'same-class' is defined using true labels, NNR would require oracle or unlabeled test information, and if it is defined using noisy training labels, it downweights precisely the clean minority samples the method is intended to protect.
  2. [Section 3.4.2, Assumption 5 and Theorem 3] Assumption 5 postulates a sub-exponential tail bound on A = L_test - L_train conditioned on the norm of the classifier; this is exactly the generalization gap that Theorem 3 purports to bound. Since the theorem's conclusion is a bound on L(test) - L(train), and the only mechanism preventing A from being large is Assumption 5 itself, the argument is circular and does not establish that NNR or CMO controls OOD error. In addition, Eq. (25) is not a concrete bound: the right-hand side is an O(...) expression depending on terms involving C, w, mu, and g without specifying constants or conditions under which the sum is finite; it cannot be evaluated or verified.
  3. [Section 3.2, Theorems 1 and 2] Both convergence theorems have proofs only 'in the Supplementary material', but no supplementary material is provided with the manuscript, so the claims are unverifiable as submitted. Furthermore, Theorem 2 as stated, lim_{T→∞} ∑_{t=1}^T E[||∇θ L(θ_t,q_t)||] = 0, is not a valid convergence statement: because the summands are nonnegative, a limit of zero would force each gradient to vanish almost surely in a nontrivial problem; the intended statement is presumably about a Cesàro average or infimum of gradient norms, and the current form is false. Section 3.2 also states that Eq. (16) gives 'a rate of O(1/T)' while the displayed bound decays as 1/√T, and the constants G_θ and G_q in Eq. (16) are never defined.
  4. [Section 4.5, Table 1 and Table 4] The headline comparison '80.2% and 79.8% versus 71.6% and 74.7%' is based on the 'Max%' columns, i.e., the best result over the five random seeds, which is not a valid basis for claiming an improvement. The 'Average%' columns in the same table show that at noise level 0.2, ERM+NNR+CMO-KL achieves 59.3±0.8 and ERM+NNR+CMO-Chi achieves 58.5±0.7 minority accuracy, both below ERM+CMO-Chi at 61.6±0.5; at 0.15 the combined models are only marginally ahead (67.9 and 67.2 versus 67.8 and 67.5), with overlapping error bars. The all-class average accuracy of the combined models is also lower than plain ERM. Thus the central claim that CMO+NNR 'improve minority class robustness' is not supported by the averaged results, and no significance tests are provided. The same best-over-seed reporting appears in Table 4 for the real-world data.
minor comments (5)
  1. [Section 2.2, Eq. (6)] The f-divergence formula as written uses f_k(dP/dQ) inside the integral with respect to dP; for D_k(Q||P) the standard definition is ∫ f_k(dQ/dP) dP, so the argument of f_k appears to be inverted.
  2. [Section 3.4.1, Eq. (20)] Equation (20) uses C as the Lipschitz constant in the displayed inequality while the text says 'where L is the Lipschitz constant'; the notation is inconsistent.
  3. [Section 3.3] The notation for the number of same-class neighbors is inconsistent: the text defines N_hom(G_i) but earlier uses N_hm(G_i), and the relationship between the two is never clarified.
  4. [Assumptions 1 and 3] There are several typographical issues: 'Eqal-Sized' in Assumption 3 should be 'Equal-Sized', and 'casual representation' in Assumption 1 should be 'causal representation'.
  5. [Section 4.4 and Figure 6] The sensitivity analysis reports results but does not specify the hyperparameters for the baseline methods or the ranges used for Γ, λ, and η_q; moreover, Figure 6 is largely unreadable in the manuscript due to encoding issues in the axes labels.

Circularity Check

1 steps flagged · score 6.0 of 10

Theorem 3's generalization bound is circular: Assumption 5 already postulates the tail bound on the test-train loss gap that the theorem claims to prove.

  1. self definitional [Section 3.4.2, Assumption 5 and Theorem 3 (Eqs. 24-25)]
    "Assume that there exists some 0 < α < 1/4 such that P_{h∼P}(A > B | T^L_h Γ > γ/8) ≤ exp(−|G_te|^{2α}). (24) A = L^{e_test}_{γ/4}(h) − L^{e_train}_{γ/2}(h) and B = |G_train|^{−α} + C Γ T"

    Assumption 5 defines A as the test margin loss minus the train margin loss, which is exactly the generalization gap that Theorem 3 claims to bound. The assumption asserts that A exceeds B only with exponentially small probability; Theorem 3 then concludes, with high probability, an upper bound on L(e_test) − L(e_train). Once Eq. 24 is granted, the high-probability inequality follows almost immediately by taking complements, and the elaborate class-center/weight expression in Eq. 25 does not supply independent content for the tail bound. The theorem's central probabilistic content is thus identical to its own premise, so the claimed OOD bound for NNR is assumed rather than derived.

full rationale

The only genuinely circular step I can exhibit is in the theoretical OOD bound. Assumption 5 (Eq. 24) directly postulates an exponentially small tail probability for A = L_test_{γ/4} − L_train_{γ/2}, which is precisely the generalization gap that Theorem 3 (Eq. 25) claims to bound. With Eq. 24 granted, the high-probability inequality L_test ≤ L_train + (a quantity of order B) follows by taking complements; the added class-center and weight terms do not change the fact that the key probabilistic estimate is assumed. Therefore the theoretical justification for NNR is circular in its essential step. The experimental evaluation in Tables 1, 3, and 4 is independent of this theorem: the reported minority-class accuracies are measured on held-out data, not derived from Eq. 25. There are no load-bearing self-citations; the paper relies on external prior work. The undefined 'same-class neighbor' notion in Eq. 18 is a reproducibility and correctness concern, not itself a circularity. Accordingly the circularity is confined to the theory section and merits a score of 6 rather than higher.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

The method depends on four hyperparameters whose values are not reported, and on five stated assumptions, three of which are ad hoc to the paper. No new physical or model entities are postulated.

free parameters (4)
  • Gamma (NNR distance threshold)
    Controls the neighborhood radius in Eq. 18 and the coverage radius in Theorem 3; sensitivity analysis in Fig. 6 varies it, but no default or fitting procedure is stated.
  • lambda (constraint coefficient)
    Appears in the Lagrangian (Eq. 11) and update (12); sensitivity analysis mentions varying it but gives no values.
  • rho1, rho2 (constraint radii)
    Define the feasible region in Eq. 9; values are not reported.
  • eta_q (learning rate for q)
    Update step size in Eq. 12; the paper sets eta_theta to 0.001 but does not specify eta_q.
assumptions (5)
  • domain assumption Assumption 1: each graph in class c has invariant features ~ N(mu_c, sigma^2 I) and spurious features ~ N(mu_ec, sigma^2 I)
    Underpins the class-similarity prior in CMO and the local-consistency noise proxy in NNR.
  • standard math Assumption 2: the loss is L-Lipschitz and G-smooth
    Standard regularity conditions used in Theorems 1 and 2.
  • ad hoc to paper Assumption 3: near sets of each training graph are equal-sized and disjoint
    Imposed on the embedding geometry without supporting evidence; needed for the PAC-Bayes bound.
  • ad hoc to paper Assumption 4: every test graph has a nearby training graph and near sets have minimal overlap
    Assumes cross-environment embedding coverage; unverified and strong.
  • ad hoc to paper Assumption 5: P(A > B | T^L Gamma > gamma/8) <= exp(-|G_te|^{2 alpha}) with A = L_test - L_train
    Assumes a tail bound on the exact test-train loss difference that Theorem 3 claims to bound, making the proof circular.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Robust OOD Graph Learning via Mean Constraints and Noise Reduction." pith.science (2026). https://pith.science/paper/H3AOCHLW

@misc{pith2026250619281,
  author       = {Pith},
  title        = {Pith review of: Robust OOD Graph Learning via Mean Constraints and Noise Reduction},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/H3AOCHLW}},
  note         = {Machine review of arXiv:2506.19281}
}
read the original abstract

Graph Out-of-Distribution (OOD) classification often suffers from sharp performance drops, particularly under category imbalance and structural noise. This work tackles two pressing challenges in this context: (1) the underperformance of minority classes due to skewed label distributions, and (2) their heightened sensitivity to structural noise in graph data. To address these problems, we propose two complementary solutions. First, Constrained Mean Optimization (CMO) improves minority class robustness by encouraging similarity-based instance aggregation under worst-case conditions. Second, the Neighbor-Aware Noise Reweighting (NNR) mechanism assigns dynamic weights to training samples based on local structural consistency, mitigating noise influence. We provide theoretical justification for our methods, and validate their effectiveness with extensive experiments on both synthetic and real-world datasets, showing significant improvements in Graph OOD generalization and classification accuracy. The code for our method is available at: https://anonymous.4open.science/r/CMO-NNR-2F30.

Figures

Figures reproduced from arXiv: 2506.19281 by the authors.

Figure 1
Figure 1. Accuracy for each category in different noise data [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Our framework is composed of CMO and NNR, corresponding to inter-class and inner-class reweighting, respectively. [PITH_FULL_IMAGE:figures/full_fig_p003_2.png] view at source ↗
Figure 3
Figure 3. The performance of the minority class with respect [PITH_FULL_IMAGE:figures/full_fig_p006_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Performance on real-world dataset results demonstrate that our methods effectively improve the gen￾eralization ability and robustness of graph models across diverse environments [PITH_FULL_IMAGE:figures/full_fig_p007_4.png]
Figure 5
Figure 5. Figure 5: Q value of different classes, yellow line donates the [PITH_FULL_IMAGE:figures/full_fig_p008_5.png]
Figure 6
Figure 6. Figure 6: Performance on different hyperparameters [PITH_FULL_IMAGE:figures/full_fig_p008_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

30 extracted references · 21 canonical work pages

  1. [1]

    Rangachari Anand, Kishan G Mehrotra, Chilukuri K Mohan, and Sanjay Ranka

  2. [2]

    Yongqiang Chen, Yatao Bian, Kaiwen Zhou, Binghui Xie, Bo Han, and James Cheng. 2023. Does Invariant Graph Learning via Environment Augmentation Learn Invariance?. In NeurIPS

  3. [3]

    Hyeongmin Cho and Sangkyun Lee. 2021. Data quality measures and efficient evaluation algorithms for large-scale high-dimensional data. Applied Sciences 11, 2 (2021), 472

  4. [4]

    Noel Cressie and Timothy RC Read. 1984. Multinomial goodness-of-fit tests. Journal of the Royal Statistical Society Series B: Statistical Methodology 46, 3 (1984), 440–464

  5. [5]

    Hanjun Dai, Yichen Wang, Rakshit Trivedi, and Le Song. 2016. Deep coevolu- tionary network: Embedding user and item features for recommendation. arXiv preprint arXiv:1609.03675 (2016)

  6. [6]

    Shaohua Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. 2022. Debiasing graph neural networks via learning disentangled causal substructure. InNeurIPS

  7. [7]

    Dragan Gamberger, Nada Lavrac, and Ciril Groselj. 1999. Experiments with noise filtering in a medical domain. In ICML, Vol. 99. 143–151

  8. [8]

    Cheng Hsu and Cheng-Te Li. 2021. Retagnn: Relational temporal attentive graph neural networks for holistic sequential recommendation. In Proceedings of the web conference 2021. 2968–2979

Show all 30 references
  1. [9]

    Yuanfeng Ji, Lu Zhang, Jiaxiang Wu, Bingzhe Wu, Long-Kai Huang, Tingyang Xu, Yu Rong, Lanqing Li, Jie Ren, Ding Xue, Houtim Lai, Shaoyong Xu, Jing Feng, Wei Liu, Ping Luo, Shuigeng Zhou, Junzhou Huang, Peilin Zhao, and Yatao Bian. 2022. DrugOOD: Out-of-Distribution (OOD) Datas...

  2. [10]

    Tianrui Jia, Haoyang Li, Cheng Yang, Tao Tao, and Chuan Shi. 2024. Graph Invari- ant Learning with Subgraph Co-mixup for Out-Of-Distribution Generalization. In AAAI

  3. [11]

    Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. 2022. Ood-gnn: Out-of- distribution generalized graph neural network.IEEE Transactions on Knowledge and Data Engineering 35, 7 (2022), 7328–7340

  4. [12]

    Haoyang Li, Xin Wang, Ziwei Zhang, and Wenwu Zhu. 2022. Out-of-distribution generalization on graphs: A survey. arXiv preprint arXiv:2202.07987 (2022)

  5. [13]

    Shuhan Liu and Kaize Ding. 2024. Beyond Generalization: A Survey of Out-Of- Distribution Adaptation on Graphs. arXiv preprint arXiv:2402.11153 (2024)

  6. [14]

    Jiaqi Ma, Junwei Deng, and Qiaozhu Mei. 2021. Subgroup generalization and fairness of graph neural networks. Advances in Neural Information Processing Systems 34 (2021), 1048–1061

  7. [15]

    Hongseok Namkoong and John C Duchi. 2016. Stochastic gradient methods for distributionally robust optimization with f-divergences. Advances in neural information processing systems 29 (2016)

  8. [16]

    Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro

  9. [17]

    Diana Pfau and Alexander Jung. 2024. Engineering Trustworthy AI: A Developer Guide for Empirical Risk Minimization. arXiv preprint arXiv:2410.19361 (2024)

  10. [18]

    Shiori Sagawa, Pang Wei Koh, Tatsunori B Hashimoto, and Percy Liang. 2019. Distributionally robust neural networks for group shifts: On the importance of regularization for worst-case generalization. arXiv preprint arXiv:1911.08731 (2019)

  11. [19]

    Bohao Wang, Jiawei Chen, Changdong Li, Sheng Zhou, Qihao Shi, Yang Gao, Yan Feng, Chun Chen, and Can Wang. 2024. Distributionally robust graph- based recommendation system. In Proceedings of the ACM Web Conference

  12. [20]

    Hongxin Wei, Lue Tao, Renchunzi Xie, Lei Feng, and Bo An. 2022. Open- sampling: Exploring out-of-distribution data for re-balancing long-tailed datasets. In International conference on machine learning. PMLR, 23615–23630

  13. [21]

    Man Wu, Xin Zheng, Qin Zhang, Xiao Shen, Xiong Luo, Xingquan Zhu, and Shirui Pan. 2024. Graph learning under distribution shifts: A comprehensive survey on domain adaptation, out-of-distribution, and continual learning. arXiv preprint arXiv:2402.16374 (2024)

  14. [22]

    Qitian Wu, Fan Nie, Chenxiao Yang, Tianyi Bao, and Junchi Yan. 2024. Graph Out-of-Distribution Generalization via Causal Intervention. In WWW

  15. [23]

    Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. 2022. HANDLING DISTRIBUTION SHIFTS ON GRAPHS: AN INVARIANCE PERSPECTIVE. In ICLR

  16. [24]

    Rongling Wu and Libo Jiang. 2021. Recovering dynamic networks in big static datasets. Physics Reports 912 (2021), 1–57

  17. [25]

    Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. 2022. DISCOVERING INVARIANT RATIONALES FOR GRAPH NEURAL NETWORKS. In ICLR

  18. [26]

    Carl Yang, Aditya Pal, Andrew Zhai, Nikil Pancha, Jiawei Han, Charles Rosenberg, and Jure Leskovec. 2020. Multisage: Empowering gcn with contextualized multi- embeddings on web-scale multipartite networks. In Proceedings of the 26th ACM SIGKDD international conference on knowl...

  19. [27]

    Jiaxuan You, Yichen Wang, Aditya Pal, Pong Eksombatchai, Chuck Rosenburg, and Jure Leskovec. 2019. Hierarchical temporal convolutional networks for dynamic recommender systems. In The world wide web conference. 2236–2246

  20. [28]

    Runtian Zhai, Chen Dan, Zico Kolter, and Pradeep Ravikumar. 2021. Doro: Distributional and outlier robust optimization. In International Conference on Machine Learning. PMLR, 12345–12355

  21. [1993]

    IEEE transactions on neural networks 4, 6 (1993), 962–969

    An improved algorithm for neural network classification of imbalanced training sets. IEEE transactions on neural networks 4, 6 (1993), 962–969

  22. [2009]

    SIAM Journal on optimization 19, 4 (2009), 1574–1609

    Robust stochastic approximation approach to stochastic programming. SIAM Journal on optimization 19, 4 (2009), 1574–1609

Pith tools

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