{"id":"53354290-48f3-41c7-a9cd-53c5f0b7e1e1","arxiv_id":"2412.05735","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"REGE adds per-node uncertainty radii to graph embeddings and combines curriculum learning with conformal quantile regression to improve robustness to structural attacks.","lead":"REGE is a training method that gives every node in a graph embedding an uncertainty radius, then adds noise proportional to that radius while training. The paper reports that this makes node classification under adversarial graph attacks more accurate than eight existing defenses, by about 1.5% on average.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The claimed 1.5% robustness advantage is not established because the evaluation relies on non-adaptive surrogate-based attacks and lacks significance testing; the headline effect may vanish under adaptive attacks.","rationale":"The reader's weakest_assumption focuses on whether the radii are genuine uncertainty measures; this affects the mechanism and novelty but does not directly threaten the headline empirical accuracy claim. The single most load-bearing concern is that the experimental protocol used to substantiate the 1.5% improvement is not a valid adversarial robustness evaluation. If the attacks are generated once with a surrogate GCN and then reused for all defenses, the comparison is essentially a fixed-transformation robustness test, not adversarial robustness against each model. The paper itself reports no adaptive attacks, and the under-specified details (which model is attacked, what budget definition, what surrogate) make the results non-reproducible and potentially misleading. This is more fundamental than the conformal calibration issue because it challenges the evidence for the central claim rather than only the interpretation of the radii. The reader's rationale does mention 'attack protocol is under-specified' and 'no significance testing,' so we partially agree, but the reader's chosen weakest_assumption (radii validity) is not, in my view, the most load-bearing. The verdict should remain CONDITIONAL because the paper could be made acceptable by running adaptive attacks and significance tests; however, until those tests are reported, the headline claim is unverified. Thus I keep the reader's CONDITIONAL verdict.","tokens_in":18757,"tokens_out":10559,"duration_ms":107072,"concrete_test":"Re-run all REGE and baseline models under adaptive attacks: generate perturbations at 1% and 10% budgets on Citeseer, Cora, PolBlogs and CoraML using the same CE-PGD and Meta-Attack objectives but with gradients computed against each defense's own loss (white-box for each model), and apply a paired Wilcoxon signed-rank test over the 4 datasets × 3 attacks × 2 budgets comparing REGE-D/REGE-M to the best baseline. If the mean advantage is <1.5% or not significant at p<0.05, the headline claim fails; if it persists, the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section 3.1 states that Meta-Attack graphs were 'computed using a standard GCN surrogate model' and does not specify whether MinMax/GraD perturbations are optimized against each defense or transferred from a surrogate. If all models are tested on the same surrogate-generated attacked graphs, the comparison measures sensitivity to one fixed perturbation, not robustness to adversarially-optimized inputs for each defense. This is a known pitfall: defenses can appear robust because the attack is not tailored to them (Athalye et al., 2018). The paper also reports no paired significance tests, and the tables contain ties and losses: Table 3 (PolBlogs, GraD 10%) REGE-D .865 ties GCN-SVD and Ricci-GNN; Table 1 (Citeseer, GraD 10%) REGE-M .696 ± .057 underperforms GADC .701 ± .004; Table 6 (Citeseer, GraD 3%) REGE-M .694 loses to GADC .696. With only 10 runs and overlapping standard deviations, the average 1.5% advantage may not be statistically reliable. Therefore the central claim that REGE 'performs better under adversarial attacks' is not yet supported by the reported protocol.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces REGE, a training-time method for graph neural networks that computes per-node uncertainty radii from two sources: (i) data-dependent radii (DDR) obtained by averaging a consensus of low-rank eigen-reconstructions of the adjacency matrix and applying a 'binary deviation' function; and (ii) model-dependent radii (MDR) obtained from a student-teacher setup in which a student MLP predicts quantiles of a teacher GCN's output embeddings, refined by conformal quantile regression. These radii are used to inject Gaussian noise into hidden representations (Eq. 2.9), and training proceeds with curriculum learning on the sequence of graph views. The paper evaluates REGE on node classification under MinMax, Meta-Attack, and GraD structural attacks on Cora, Citeseer, and PolBlogs (plus CoraML in the appendix), reporting that REGE outperforms eight defense baselines by an average of 1.5% accuracy.","tokens_in":19046,"tokens_out":8688,"duration_ms":75715,"significance":"If the robustness gains are real and the radii genuinely reflect node-level uncertainty, REGE would be a simple and inexpensive addition to GCN training. The method is straightforward to implement, the code is released, and the idea of injecting uncertainty-scaled noise into hidden layers is plausible. However, the current evaluation does not establish the central claim: the attack protocol appears to use surrogate-generated perturbations rather than adaptive attacks, the conformal calibration is performed on the training set, which voids the stated coverage guarantee, and the ablation study does not isolate the effect of the radius noise. These gaps currently prevent the reader from attributing the reported improvements to the proposed mechanism.","major_comments":[{"comment":"The paper does not state whether the MinMax, Meta-Attack, and GraD perturbations are optimized against each defense or generated once with a surrogate GCN and then reused for all methods. The sentence 'adversarial graphs for Meta-Attack were computed using a standard GCN surrogate model' suggests the latter for at least one attack. If all defenses are tested on the same surrogate-attacked graphs, the evaluation measures performance on one fixed perturbation set, not robustness to attacks tailored to each defense, which is a known failure mode for non-adaptive evaluations (Athalye et al., 2018). The authors should specify the protocol for all three attacks and add at least one adaptive attack (e.g., attacking the final REGE model with the same budget) to support the central robustness claim.","section":"Section 3.1, Tables 1-3"},{"comment":"The text first says conformal calibration requires a set 'different from validation or testing data,' then states that conformal learning is applied 'using the training set as the calibration set.' Since the student MLP is trained on the teacher's outputs, using the training set for calibration violates the exchangeability requirement of conformal prediction, so the MDR intervals have no stated coverage guarantee. The authors should use a held-out calibration set or revise the claim that the intervals provide guaranteed coverage.","section":"Section 2.2, Eq. (2.5)-(2.7)"},{"comment":"The ablation study only removes curriculum learning (REGE-NCT); every variant still injects radius-scaled noise. To support the claim that incorporating uncertainty improves robustness, the paper needs a control without the noise (e.g., GCN with curriculum learning only, or with uniform/random noise) to show that the specific radius values matter. Without this control, the improvement might be attributable to curriculum learning or to noise injection in general.","section":"Section 3.3, Table 4"},{"comment":"The paper reports 10-run means with standard deviations but no paired significance tests. Many of the reported gains are within one standard deviation of the best baseline (e.g., Table 2, Cora MinMax 1%: REGE-D .837±.004 vs GraphReshape .834±.003; Table 1, Citeseer GraD 10%: REGE-M .696±.057 vs GADC .701±.004 is a loss; Table 3, PolBlogs GraD 10%: REGE-D .865 ties GCN-SVD and Ricci-GNN; Table 6, Citeseer GraD 3%: REGE-M .694 vs GADC .696 loses). The headline 'average 1.5%' therefore lacks statistical support and should be accompanied by paired tests or bootstrap intervals, along with a per-condition breakdown of gains and losses.","section":"Tables 1-6"},{"comment":"The abstract claims an average improvement of 1.5% without specifying the exact settings, and the conclusion says 'across four datasets,' but the main experimental section evaluates only three datasets (Cora, Citeseer, PolBlogs); CoraML appears only in the appendix. The paper should specify exactly which tables and settings are averaged, report the per-condition gains/losses, and correct the dataset count.","section":"Abstract and Conclusion"}],"minor_comments":[{"comment":"The binary deviation function is one of many possible edge-uncertainty measures; Figure 2 gives a qualitative comparison but no quantitative ablation of alternative functions (e.g., standard deviation or entropy). Consider adding such an ablation to justify the choice.","section":"Section 2.1, Eq. (2.2)"},{"comment":"The student MLP predicts the teacher GCN's embedding outputs, but the paper does not specify how the teacher is trained (e.g., the loss and the label splits) or how the student's quantile predictions are converted into a final radius after averaging over dimensions. A precise description would improve reproducibility.","section":"Section 2.2"},{"comment":"The noise variance is set to the radius ri, but the paper does not discuss the range of MDR values or whether clipping is needed; if radii can exceed 1, the noise may overwhelm the hidden representations.","section":"Section 2.3, Eq. (2.9)"},{"comment":"Algorithm 2 iterates k over q, q+1, ..., n, while the appendix says components are incremented by 5; these should be made consistent.","section":"Algorithm 2 and Section A.5"},{"comment":"The dataset splits and the number of labeled examples per class are not reported, which makes the node classification setup difficult to reproduce.","section":"Section 3.1"},{"comment":"Section 2.1 contains a duplicated phrase ('uncertainty arising fr In this paper'); Table 5 caption has 'consistenly' and Table 3 caption has 'consistenly' as well.","section":"Typos"},{"comment":"UAG (Feng et al., 2021) is discussed in Related Work but is not included in the experimental comparisons; given that UAG also uses uncertainty for robustness, it would be a relevant baseline.","section":"Related Work"}],"recommendation":"major_revision","confidential_remarks":"The paper's strength is the clear presentation and the release of code. The main concerns are methodological: the attack protocol appears non-adaptive, the conformal calibration is done on the training set, and the ablation does not isolate the radii component. These are fixable with additional experiments, so I recommend major revision rather than rejection. The novelty is moderate; the uncertainty-noise idea is reminiscent of VAE noise and of existing uncertainty-aware GNNs. The paper could be a good fit for a graph-learning or robustness venue, but the empirical claims need to be made more rigorous."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Zohair and colleagues propose REGE, a training-time defense that computes per-node uncertainty radii from eigen-decomposed graph views and from a student-teacher conformal procedure, then injects Gaussian noise of that variance during curriculum training. The assembly is new, and the paper is honestly written: algorithms are explicit, an ablation separates curriculum learning from noise injection, and code is linked. On the main tables REGE-D and REGE-M win the majority of conditions, and some margins are real—PolBlogs Meta 10% shows roughly 2 points over the next best.\n\nThe problems are in the claims and the evaluation, not the idea. The abstract says 'better by an average of 1.5% against state-of-the-art methods,' but against the strongest baseline per condition the average is closer to 1.0%, and the paper's own tables contain ties and losses (Citeseer GraD 10% REGE-D .699 vs GADC .701; PolBlogs GraD 10% ties GCN-SVD and Ricci-GNN). 'Consistently outperforms' is not supported. There is no significance testing; 10 runs with overlapping standard deviations are not enough to establish a 1-point edge.\n\nThe conformal step is also mis-sold. Calibrating on the training set does not give the stated coverage guarantee—this is a heuristic interval adjustment, not conformal prediction. The authors should either hold out a calibration set or drop the statistical claim.\n\nThe attack protocol is the load-bearing concern. Meta-Attack graphs are computed from a standard GCN surrogate, and it is unclear whether MinMax and GraD perturbations are optimized against each defense or transferred. If all methods are tested on one fixed attacked graph, the comparison is sensitivity to a single perturbation, not robustness to adversarial inputs. Adaptive attacks may shrink or reverse the result.\n\nMinor: the minimum number of eigen-components q is never stated in the main text or appendix; the code presumably has it, but the paper should. Also, the paper does not report run-to-run variance across seeds in a way that permits paired comparisons.\n\nBottom line: there is a plausible heuristic here and the paper deserves peer review. It is for people working on graph adversarial defenses. I would send it back for major revision—fix the statistics, the conformal claim, the attack protocol, and the headline. The method might survive; the current evidence is conditional.","headline":"A plausible new uncertainty-based defense whose headline accuracy gain is overstated and whose attack evaluation needs adaptive baselines; worth a serious revision.","tokens_in":19546,"tokens_out":2939,"would_cite":false,"duration_ms":29746,"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":"REGE incorporates per-node uncertainty radii into graph embedding training and reports average accuracy gains of 1.5% over eight state-of-the-art defenses under structural attacks on four datasets.","keywords":["graph embeddings","uncertainty quantification","adversarial robustness","graph neural networks","conformal prediction","curriculum learning","eigen-decomposition","node classification"],"falsifier":"An experiment that replaces each node's radius with a random value in [0,1] (or with the same constant) while keeping the curriculum schedule unchanged; if the accuracy under MinMax, Meta-Attack, and GraD remains within 0.5% of REGE with true radii, then the specific radius values are not what drives the reported improvement.","tokens_in":18519,"feed_emoji":"🛡️","tokens_out":7930,"duration_ms":61129,"temperature":0.7,"pith_summary":"The paper argues that graph embeddings should carry an explicit per-node uncertainty radius, and that training with noise proportional to that radius makes node classification more robust to adversarial attacks on the graph structure. It proposes REGE, which derives two kinds of radii: data-dependent radii from low-rank eigen-reconstructions of the adjacency matrix, and model-dependent radii from a student-teacher setup with conformal quantile regression. It then trains a GCN with curriculum learning on progressively fuller graph reconstructions while injecting Gaussian noise with variance equal to the radius into hidden layers. Across Cora, Citeseer, CoraML, and PolBlogs, under MinMax, Meta-Attack, and GraD perturbations of 1–10%, REGE outperforms eight existing defenses by an average of 1.5% accuracy.","feed_headline":"Graph embeddings with uncertainty radii beat attacks by 1.5%","feed_subtitle":"REGE computes a per-node uncertainty radius from the graph and the model, then injects it as training noise.","key_machinery":"The central object is the per-node uncertainty radius r_i, paired with the rule that hidden representations are perturbed as x_i^l ← x_i^l + N(0, r_i). The radius is produced by two procedures: the data-dependent radius (DDR) averages, row-wise, the binary deviation of entries in a consensus weighted adjacency matrix built from low-rank eigen-reconstructions of the graph; the model-dependent radius (MDR) conformalizes student-teacher quantile intervals across embedding dimensions. These radii are then used both as noise variances and as the curriculum schedule, since the graph views with few components are treated as easy examples and more components are added progressively.","core_discovery":"REGE's central claim is that measuring and incorporating uncertainty into graph embedding training yields embeddings that are more resistant to adversarial structural perturbations. The method computes, for each node i, a scalar radius r_i in [0,1] from either the data (DDR) or the model (MDR). DDR uses the eigen-decomposition of the adjacency matrix to generate graph views with increasing numbers of components, averages them into a weighted adjacency matrix W, and maps each row through a binary deviation function to a node-level radius. MDR trains a teacher GCN, then a student MLP with quantile loss to predict per-dimension quantiles of the teacher's embeddings, conformalizes those intervals using the training set as calibration, and averages the dimensional interval widths into a radius. During training, Gaussian noise N(0, r_i) is added to each node's hidden representation, and the model is trained with curriculum learning on the sequence of graph views. The paper reports that this consistently improves node classification accuracy under MinMax, Meta-Attack, and GraD perturbations, by an average of 1.5% against state-of-the-art defenses.","pith_inferences":["A natural next test is whether the radius values carry meaning beyond the training objective: for instance, whether nodes with large MDR correspond to misclassified or low-degree nodes in other graph tasks, which would make REGE a source of calibrated confidence scores as well as a defense.","The conformal step in REGE is applied with the training set as calibration, which breaks the standard distribution-free coverage guarantee; a held-out calibration set would be needed to claim that the model-dependent radii are statistically calibrated.","If the gains come mainly from the curriculum over low-rank views rather than from the radius noise, then a simpler method that trains on a few low-rank views without radii might match REGE; the paper isolates curriculum but not the radii, so this decomposition is an open empirical question."],"forward_implications":["If REGE's central claim holds, any downstream task that uses the produced embeddings inherits a measurable per-node uncertainty that can flag unreliable predictions.","Adding radius-proportional noise during training is a defense that requires no separate attack model, unlike adversarial training.","Because the radii are computed from an eigen-decomposition and a teacher GCN, the same recipe can be attached to any differentiable graph embedding function, not just GCNs.","The 1.5% average accuracy gain is consistent across perturbation levels from 1% to 10% and across three attack families, suggesting the defense is not attack-specific.","Curriculum learning over graph views with increasing eigen-components contributes beyond the noise injection: the REGE-NCT ablation (no curriculum) underperforms full REGE in most cases."],"supporting_citations":[{"why":"Supplies the conformal quantile regression used to refine model-dependent prediction intervals.","marker":"[7]"},{"why":"Provides the curriculum learning schedule that trains on graph views from few to many eigen-components.","marker":"[8]"},{"why":"Establishes the student-teacher framework used to estimate per-dimension embedding quantiles.","marker":"[5, 6]"},{"why":"Gives the variational autoencoder analogy for treating hidden representations as samples with fixed variances.","marker":"[21]"},{"why":"Supports the claim that graphs reconstructed from large eigenvalues contain high-certainty edges, the basis of data-dependent radii.","marker":"[15, 16, 17]"},{"why":"Defines the MinMax attack used as an adversarial perturbation in evaluation.","marker":"[9]"},{"why":"Defines the Meta-Attack used as an adversarial perturbation in evaluation.","marker":"[10]"},{"why":"Defines the GraD attack used as an adversarial perturbation in evaluation.","marker":"[11]"},{"why":"A defense baseline that also uses Gaussian hidden representations, against which REGE's noise-injection design is compared.","marker":"[24]"},{"why":"A low-rank defense baseline; REGE is compared against it especially in the component-variation analysis.","marker":"[25]"}],"fun_headline_variants":["Uncertainty-aware graph embeddings: +1.5% robustness","REGE: Embeddings with radii that resist graph attacks","Adding uncertainty radii to graph embeddings boosts attack resilience","Graph learning gets a radius: REGE improves adversarial robustness","REGE embeds uncertainty into graphs for 1.5% attack gain"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the computed radius values genuinely measure node uncertainty, so that adding Gaussian noise to hidden representations with variance equal to the radius is what improves robustness, rather than the noise or the curriculum alone.","fun_headline_variants_meta":{"raw":{"variants":["Uncertainty-aware graph embeddings: +1.5% robustness","REGE: Embeddings with radii that resist graph attacks","Adding uncertainty radii to graph embeddings boosts attack resilience","Graph learning gets a radius: REGE improves adversarial robustness","REGE embeds uncertainty into graphs for 1.5% attack gain"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000207,"raw_usage":{"total_tokens":1385,"prompt_tokens":915,"completion_tokens":470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":385}},"tokens_in":531,"tokens_out":470,"duration_ms":4556,"temperature":1.0,"reasoning_tokens":385,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T20:25:05.633153+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"An experiment that replaces each node's radius with a random value in [0,1] (or with the same constant) while keeping the curriculum schedule unchanged; if the accuracy under MinMax, Meta-Attack, and GraD remains within 0.5% of REGE with true radii, then the specific radius values are not what drives the reported improvement.","supporting_citations":[{"cited_title":"Curriculum learning,","cited_arxiv_id":null,"evidence_quote":"Provides the curriculum learning schedule that trains on graph views from few to many eigen-components."},{"cited_title":"Topology attack and defense for graph neural networks: an optimization perspective,","cited_arxiv_id":null,"evidence_quote":"Defines the MinMax attack used as an adversarial perturbation in evaluation."},{"cited_title":"Adversarial attacks on graph neural networks via meta learning,","cited_arxiv_id":null,"evidence_quote":"Defines the Meta-Attack used as an adversarial perturbation in evaluation."},{"cited_title":"Towards reasonable budget allocation in untargeted graph struc- ture attacks via gradient debias,","cited_arxiv_id":null,"evidence_quote":"Defines the GraD attack used as an adversarial perturbation in evaluation."},{"cited_title":"Robust graph convolutional networks against adversarial attacks,","cited_arxiv_id":null,"evidence_quote":"A defense baseline that also uses Gaussian hidden representations, against which REGE's noise-injection design is compared."},{"cited_title":"All you need is low (rank) defend- ing against adversarial attacks on graphs,","cited_arxiv_id":null,"evidence_quote":"A low-rank defense baseline; REGE is compared against it especially in the component-variation analysis."}],"review_version":1}