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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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.
- [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)
- [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.
- [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.
- [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.
- [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'.
- [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
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.
-
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
free parameters (4)
- Gamma (NNR distance threshold)
- lambda (constraint coefficient)
- rho1, rho2 (constraint radii)
- eta_q (learning rate for 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)
- standard math Assumption 2: the loss is L-Lipschitz and G-smooth
- ad hoc to paper Assumption 3: near sets of each training graph are equal-sized and disjoint
- ad hoc to paper Assumption 4: every test graph has a nearby training graph and near sets have minimal overlap
- 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
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 from the paper (3 more)
Reference graph
Works this paper leans on
-
[1]
Rangachari Anand, Kishan G Mehrotra, Chilukuri K Mohan, and Sanjay Ranka
-
[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
work page 2023
-
[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
work page 2021
-
[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
work page 1984
-
[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)
arXiv 2016
-
[6]
Shaohua Fan, Xiao Wang, Yanhu Mo, Chuan Shi, and Jian Tang. 2022. Debiasing graph neural networks via learning disentangled causal substructure. InNeurIPS
work page 2022
-
[7]
Dragan Gamberger, Nada Lavrac, and Ciril Groselj. 1999. Experiments with noise filtering in a medical domain. In ICML, Vol. 99. 143–151
work page 1999
-
[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
2021
Show all 30 references
-
[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...
2022 arXiv
-
[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
2024
-
[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
2022
-
[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)
2022 arXiv
-
[13]
Shuhan Liu and Kaize Ding. 2024. Beyond Generalization: A Survey of Out-Of- Distribution Adaptation on Graphs. arXiv preprint arXiv:2402.11153 (2024)
2024 arXiv
-
[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
2021
-
[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)
2016
-
[16]
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro
-
[17]
Diana Pfau and Alexander Jung. 2024. Engineering Trustworthy AI: A Developer Guide for Empirical Risk Minimization. arXiv preprint arXiv:2410.19361 (2024)
2024 arXiv
-
[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)
2019 arXiv
-
[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
2024
-
[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
2022
-
[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)
2024 arXiv
-
[22]
Qitian Wu, Fan Nie, Chenxiao Yang, Tianyi Bao, and Junchi Yan. 2024. Graph Out-of-Distribution Generalization via Causal Intervention. In WWW
2024
-
[23]
Qitian Wu, Hengrui Zhang, Junchi Yan, and David Wipf. 2022. HANDLING DISTRIBUTION SHIFTS ON GRAPHS: AN INVARIANCE PERSPECTIVE. In ICLR
2022
-
[24]
Rongling Wu and Libo Jiang. 2021. Recovering dynamic networks in big static datasets. Physics Reports 912 (2021), 1–57
2021
-
[25]
Ying-Xin Wu, Xiang Wang, An Zhang, Xiangnan He, and Tat-Seng Chua. 2022. DISCOVERING INVARIANT RATIONALES FOR GRAPH NEURAL NETWORKS. In ICLR
2022
-
[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...
2020
-
[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
2019
-
[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
2021
-
[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
1993
-
[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
2009
Reviewed August 15, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.