{"id":"9b1ce14a-8507-49b1-a567-81f0500604cd","arxiv_id":"2603.26136","paper_version":3,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Injecting virtual nodes along the dominant eigenvector of a GNN's own output embeddings degrades task performance in a single black-box query, with no gradients or surrogate models.","lead":"A new black-box attack adds fake nodes to a graph to make a trained graph neural network produce worse predictions, using only one look at the model's output embeddings and no gradients or surrogate models. It works across several graph tasks and architectures, but the clean theory covers only a simplified linear GNN, and the broader claims rest on a shaky approximation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 1's claimed maximizer violates its own budget constraint, so Theorem 1 and the budget-matched attack claims are not correct as stated.","rationale":"The reader's weakest assumption was the invalid black-box derivation in Eqs. 7–10, and that is indeed a real gap. However, I see a more fundamental problem one step earlier: the core optimization theorem is not correct as stated. Lemma 1's proof itself selects Y = Δ e1 e1^T, which corresponds to BB^T = Δ u1 u1^T, not Δ^2 u1 u1^T; the claimed B = Δ u1 v^T gives the latter. This is a Δ-versus-Δ^2 inconsistency. Since all experimental budgets are >1, the implemented attack exceeds the nominal budget unless the model renormalizes in a way that exactly compensates, which the paper does not specify. This directly weakens the headline claim of a 'tight budget' injection attack and makes the baseline comparisons in Table 2 not necessarily budget-matched. The black-box derivation (Eqs. 7–10) is also non-rigorous, but even if that were fixed, the white-box theorem would still need the scaling correction. The paper could be salvaged by correcting the scaling, re-running experiments with matched budgets, and reframing the black-box variant as a heuristic rather than a proven optimal attack; in its current form the central correctness claim is not established.","tokens_in":27106,"tokens_out":12986,"duration_ms":128555,"concrete_test":"Numerically instantiate Lemma 1 with a random Z ∈ R^{100×10} and Δ=2: compute the dominant eigenvector u1 of ZZ^T and compare the claimed B = Δ u1 v^T against B = √Δ u1 v^T under the constraint ||BB^T||_F ≤ Δ. The claimed solution gives ||BB^T||_F = 4 > 2, while the √Δ version is feasible; if the objective values confirm this, Theorem 1's exact-maximizer statement is false as stated. A follow-up re-run of the Cora r=0.01 attack with √Δ scaling would show whether the reported accuracy/F1 drops remain at the same magnitude when the budget is actually matched.","verdict_should_be":"REJECT","load_bearing_attack":"Lemma 1 claims B* = Δ u1 v^T solves max ||BB^T Z||_F^2 s.t. ||BB^T||_F ≤ Δ. But ||B*B*^T||_F = Δ^2, so for Δ > 1 the claimed solution is infeasible. In the experiments Δ = r|V|deg(G) (node tasks) or r|E| (graph tasks), which is > 1 in every reported setting (e.g., Cora r=0.01 has Δ≈132). The feasible optimizer under the stated constraint is √Δ u1 v^T, not Δ u1 v^T. Thus Theorem 1's claim that S_v* = Δ u1 v^T maximizes L(S_v) in Eq. 3 is false as written. This is not cosmetic: Algorithm 1 inserts A_v = Δ u1 v^T, so the attack's actual perturbation budget is not the advertised Δ unless the target model applies a normalization that precisely cancels Δ^2, which is neither stated nor standard. The black-box derivation is also invalid: Eq. 10 asserts ||S_v S_v^T XΘ||_F^2 = Δ^2||H||_F^2, but for S_v=Δ u1 v^T the left side equals Δ^4 ||u1^T H||^2, not Δ^2||H||_F^2. This equality holds only in degenerate rank-one or Δ=1 cases. Therefore the formal support for both the exact-optimality claim and the 'same budget' comparisons with baselines is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes PEANUT/PEA, a graph injection attack for GNNs under a restricted black-box threat model. The attacker observes only the final node-level embeddings (output logits for node classification, pre-pooling embeddings for graph-level tasks), injects virtual nodes with zero features, and sets the perturbation matrix to a rank-one outer product of the dominant eigenvector of ZZ^T with a random unit vector, scaled by a budget Δ. For a two-layer SGC, Theorem 1 claims this construction exactly maximizes the Frobenius norm of the change in real-node embeddings subject to ||S_vS_v^T||_F ≤ Δ. The paper then argues via Equations 7–10 that using observed Z in place of the hidden H = XΘ gives a single-query black-box attack, and empirically evaluates the method on node classification (Cora, Citeseer, Pubmed), graph classification (six datasets), and graph regression (five datasets) across SGC, GCN, GIN, and SAGE architectures.","tokens_in":27501,"tokens_out":9611,"duration_ms":96957,"significance":"If the theoretical claims were correct, the attack would be notable for its extreme simplicity: one forward pass and one eigendecomposition, no surrogate training, no iterative optimization, and applicability to underexplored graph-level tasks such as regression. The empirical evaluation is broad and the paper explicitly acknowledges several limitations (e.g., norm discrepancy may not change classification rankings; non-monotonic effects on some graph-classification datasets). However, the formal foundation as written has load-bearing errors: the claimed maximizer violates its own budget constraint, and the black-box proxy equality is not generally true. The empirical results may still support a heuristic attack, but the current paper does not establish the advertised optimality guarantees or budget-matched comparisons.","major_comments":[{"comment":"The claimed maximizer B* = Δ·u1v^T violates the stated constraint ||BB^T||_F ≤ Δ when Δ > 1, because ||B*B*^T||_F = Δ^2. In every experimental configuration reported, Δ is greater than 1 (e.g., Cora with r=0.01 has Δ≈132; Table 3). Algorithm 1 inserts A_v = ReLU(Δ·u1v^T), so the actual perturbation has squared Frobenius norm Δ^2, not Δ, unless an unstated normalization is applied. The feasible maximizer under the stated constraint is √Δ·u1v^T, or equivalently the constraint should be written on ||BB^T||_F^2. This must be corrected before the exact-optimality claim or the budget-matched comparisons with AGIA/TDGIA can be accepted.","section":"§4, Lemma 1 and Theorem 1; Appendix A"},{"comment":"Equation (10) asserts Δ²||H||²_F = ||S_vS_v^T XΘ||²_F. This is not an identity. For S_v = Δ·u1v^T, the right-hand side equals Δ⁴||u1^T H||², while the left-hand side is Δ²||H||²; the two coincide only in degenerate cases. The Cauchy–Schwarz chain gives an upper bound, not an equivalence. Therefore the statement that maximizing ||S_vS_v^T Z||_F 'would also push up' the true objective L(S_v) is not proven. The black-box variant should be presented as a heuristic, or supported by an additional argument establishing conditions under which the two objectives are aligned.","section":"§4, 'Working with Limited Information', Eqs. (7)–(10)"},{"comment":"The theoretical guarantee covers only a two-layer SGC with zero virtual-node features. The extension to GCN/GIN/SAGE relies on removing nonlinearities ('naïve assumption,' Eq. 14) and on empirical validation. The empirical evidence is mixed: on SAGE, accuracy drops are only 1.65–10.61% (Table 6), and on MUTAG and IMDB-BINARY the effect is non-monotonic in budget (§5.2.3). If the paper's central claim is an attack that 'consistently degrades' performance across topology-driven MPNNs, this claim needs to be qualified; if the claim is only that PEA is a simple heuristic that often degrades performance, the text should say so explicitly.","section":"§4 'Applicability to other GNNs'; §5.2"},{"comment":"The statement that for binary S_v the constraint ||S_vS_v^T||_F ≤ Δ 'would correspond to a bound on the exact number of new edges being added' is incorrect. For a binary N×n_v matrix A_v, (A_vA_v^T)_{ij} counts the number of virtual nodes shared by nodes i and j, and the Frobenius norm of that co-occurrence matrix is not the edge count. This affects the interpretation of Δ = r|V|·deg(G) and Δ = r|E| used in §5.1.3, and therefore the fairness of comparisons with baselines. Please clarify what quantity is actually budgeted.","section":"§3, 'Attack Efficacy and Constraints'"}],"minor_comments":[{"comment":"The proof writes the constraint as ||BB^T||_F^2 ≤ Δ^2, which is inconsistent with the Lemma statement ||BB^T||_F ≤ Δ. Align the notation for squared vs. unsquared norms throughout.","section":"Appendix A"},{"comment":"The caption and prose should be clarified: the figure appears to plot L(S_v) for PEA-W and PEA, but the relationship to Eq. (10) and the meaning of the 'with ||S2||F' variant are not explained. There is also a grammatical issue in the sentence following Eq. (7).","section":"Figure 5 and surrounding text"},{"comment":"The claim that the generated perturbations are 'positive with values ∈[0,1]' is not guaranteed by A_v = ReLU(Δ·u1v^T) when Δ > 1 and u1 is a unit vector. State explicitly any clipping or normalization step, or revise the claim.","section":"§4.1.1"},{"comment":"The 'Avg. Δ' row in Table 1 would benefit from a self-contained formula; the definition Δ = r|E| is given later in §5.1.3, but the table caption should not rely on forward references. Table 3 already gives Δ for NC; consider making the two tables consistent.","section":"Tables 1 and 3"},{"comment":"In the manuscript version reviewed, the text inside these figures appears as corrupted glyph strings (e.g., '/uni00000013/...'). If this reflects the actual PDF, the figures are unreadable and must be regenerated; otherwise the submission PDF is corrupted.","section":"Figures 2–4, 6–8"}],"recommendation":"major_revision","confidential_remarks":"The scaling bug in Lemma 1 is locally fixable, but the Eq. (10) equality is a more fundamental issue: it changes the nature of the contribution from a proven single-query attack to a heuristic proxy. The empirical study is broad and the attack is cheap, so a revised version that either proves a correct proxy relationship or explicitly frames PEA as a heuristic with supporting experiments could be publishable. I would not recommend rejection if the authors are willing to make that reframing and rerun the budget-matched comparisons with the corrected scaling."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: the attack idea is real and the node-classification results are worth a look, but the formal support has a load-bearing bug and the graph-level evaluation is underdone.\n\nWhat's new: PEA is a single-query, gradient-free injection attack that uses the dominant eigenvector of ZZ^T to construct a weighted virtual-node block, with zero features on injected nodes. That packaging is not in the cited baselines, and the empirical comparison on Cora/Citeseer/PubMed at 5-10% budget shows much larger accuracy drops than TDGIA/AGIA/ATDGIA. The paper also does the first systematic injection evaluation on graph regression, which is a real gap in the literature.\n\nWhere it breaks: Lemma 1's maximizer violates its own constraint. For B = Δ u v^T, ||BB^T||_F = Δ^2, so the solution is feasible only when Δ ≤ 1. The proof itself derives Y* = Δ e1 e1^T, which implies B should be sqrt(Δ) u v^T, not Δ u v^T. In every reported experiment Δ is > 1 (e.g., Cora r=0.01 has Δ≈132), so Theorem 1 as stated is false, and Algorithm 1 actually spends a budget of Δ^2, not Δ. That makes the 'same budget' comparisons with baselines not apples-to-apples. This is not cosmetic; it is the paper's central formal claim.\n\nThe black-box extension is also under-justified. Equations 7-10 assert an equality that only holds in degenerate cases; the chain gives an upper bound, so maximizing the computable quantity is not proven to maximize the true SGC objective. The transfer to GCN/GIN is openly heuristic. None of this means the attack doesn't work — the empirical trends in Figure 2 and Table 2 are plausible — but the paper states the claim more strongly than the evidence supports.\n\nOther gaps: graph-level results have no baselines, no error bars in the figures, and no code. The paper acknowledges some of this (norm changes need not flip classifications) which is honest.\n\nBottom line: the attack is simple and effective enough to deserve a serious referee, but the authors need to fix the scaling in the theorem, re-run the budget-matched comparisons, add error bars and baselines for GC/GR, and release code. I'd send it to review, and ask for a revision.","headline":"The core attack idea is genuinely new and the node-classification numbers are strong, but the formal theorem has a budget-scaling error that invalidates the claimed optimality, and the black-box proxy is not justified as an equality.","tokens_in":27950,"tokens_out":5710,"would_cite":false,"duration_ms":53041,"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":"Topology-driven graph neural networks can be attacked with a single black-box query by injecting virtual nodes aligned with the dominant eigenvector of the observed embeddings, and for a two-layer SGC this perturbation is provably the budge","keywords":["graph neural networks","adversarial attack","graph injection attack","black-box attack","virtual node injection","eigenvector alignment","graph regression","node classification"],"falsifier":"Train a two-layer SGC with random weights such that the dominant eigenvectors of HH^T and ZZ^T are nearly orthogonal. Apply the black-box PEA perturbation and a same-budget random perturbation; if the PEA-induced L = ||Z_p - Z||_F is not statistically larger than random, the black-box equivalence in Equations 7-10 fails. For nonlinear models, repeat on GCN/GIN and check whether performance drops are separable from random injection; if not, the transfer claim is unsupported.","tokens_in":26989,"feed_emoji":"📉","tokens_out":8868,"duration_ms":85078,"temperature":0.7,"pith_summary":"The paper is trying to establish that graph neural networks which consume the adjacency matrix or Laplacian during message passing have a structural vulnerability: an attacker who can only see the model's final node embeddings and inject new nodes can force large output changes without gradients, training, or iterative optimization. It proves that for a two-layer SGC the budget-constrained perturbation maximizing the embedding-norm change is exactly Δ u1 v^T, where u1 is the dominant eigenvector of the hidden feature Gram matrix HH^T. It then turns this into a black-box attack by using the observed embeddings Z in place of H, injecting virtual nodes with zero features whose edge weights come from that dominant eigenvector. The paper reports consistent performance degradation across node classification, graph classification, and graph regression benchmarks, including large accuracy drops on citation networks at modest budgets. A sympathetic reader would care because, if true, the result shows a cheap and practical attack surface in deployed topology-driven GNNs, and suggests the exact linear analysis identifies the mechanism behind it.","feed_headline":"A single-query eigenvector attack drops GNN accuracy by over 50 points","feed_subtitle":"Aligned virtual nodes with the dominant output eigenvector degrade node and graph tasks in one black-box query.","key_machinery":"The central object is a rank-one perturbation S_v = Δ u1 v^T built from u1, the dominant eigenvector of the embedding Gram matrix—HH^T for the white-box SGC variant, ZZ^T for the black-box variant. This is the 'eigenvector alignment' in the paper's name. The mechanism is an identity: for zero-feature virtual nodes, the attack objective equals ||S_v S_v^T XΘ||_F², and the trace trick rewrites this as a weighted sum of the eigenvalues of ZZ^T (or HH^T), with weights coming from the budget matrix. Concentrating all weight on the largest eigenvalue is then provably optimal in the linear case; the virtual-node injection is the device that realizes this perturbation in the adjacency matrix without","core_discovery":"For a two-layer SGC with embeddings Z = S²XΘ, the paper shows that after injecting virtual nodes with zero features, the clean-versus-perturbed embedding difference reduces to ||S_v S_v^T XΘ||_F². Lemma 1 solves the budget-constrained maximization of this quantity in closed form: the optimal perturbation is S_v* = Δ u1 v^T, where u1 is the dominant eigenvector of HH^T = (XΘ)(XΘ)^T and v is an arbitrary unit vector. The black-box variant replaces H with the observed node embeddings Z, so the attacker needs only one forward pass; the perturbation is then thresholded with ReLU (or discretized for binary-adjacency architectures) to produce non-negative or binary edge weights. The paper claims th","pith_inferences":["The exact optimality is proven only for a linear two-layer SGC; in my reading the empirical transfer to GCN/GIN suggests the load-bearing path is the linear adjacency multiplication, which would predict weaker attacks on architectures with attention or gating that renormalize messages—a testable comparison.","A natural improvement left implicit: spending a second query or accessing an intermediate representation to estimate H (rather than using Z) could push the black-box attack closer to the proven SGC optimum.","The same spectral logic can be inverted for defense: filtering or clipping injected edges that align with the dominant embedding eigenvector, or constraining the spectral norm of the message-passing matrix, would directly counter the mechanism; the paper notes filtering mitigates the worst effects but does not develop it.","The attack leaves a rank-one fingerprint in the augmented adjacency matrix, so an anomaly detector that checks whether new columns are approximately proportional to a single vector could flag it; this is an extension the paper does not explore."],"forward_implications":["Topology-consuming GNNs are exposed to single-query black-box injection even when injected nodes have zero features and the original graph is untouched; defenses must therefore consider input filtering or architectural changes rather than assuming attackers need large budgets or white-box access.","For two-layer SGCs the attack is exactly optimal under the Frobenius budget, so no same-budget rank-one perturbation can induce a larger change in embedding norm; the bound is tight.","Graph-level objectives, including regression, are vulnerable: maximizing the norm difference of node embeddings before pooling is sufficient to degrade RMSE/MAE, extending injection attacks beyond node classification.","Node classification degrades strongly at higher budgets even though the attack does not optimize for label flips, because the norm change disturbs logit rankings enough to flip classes.","Because no surrogate model or iterative optimization is needed, the attack applies immediately to an already-trained model and avoids transfer failures that come from surrogate models."],"fun_headline_variants":["Single-query eigenvector attack cripples GNN accuracy","One black-box query: eigenvector injection drops GNN performance","GNN attack aligned with embeddings needs only one query","Eigenvector-aligned injection: single-query GNN attack","Gradient-free GNN attack: one query, eigenvector perturbation"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The paper's black-box version assumes that the embeddings the attacker can observe are a good stand-in for the model's hidden feature matrix when picking the eigenvector, and that maximizing the change in observed embeddings also maximizes the change the attacker actually cares about; this equivalence is only approximate, and the same assumption is carried unproven into nonlinear GNNs.","fun_headline_variants_meta":{"raw":{"variants":["Single-query eigenvector attack cripples GNN accuracy","One black-box query: eigenvector injection drops GNN performance","GNN attack aligned with embeddings needs only one query","Eigenvector-aligned injection: single-query GNN attack","Gradient-free GNN attack: one query, eigenvector perturbation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000456,"raw_usage":{"total_tokens":2168,"prompt_tokens":828,"completion_tokens":1340,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":1255}},"tokens_in":572,"tokens_out":1340,"duration_ms":9542,"temperature":1.0,"reasoning_tokens":1255,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-02T17:18:00.266800+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a two-layer SGC with random weights such that the dominant eigenvectors of HH^T and ZZ^T are nearly orthogonal. Apply the black-box PEA perturbation and a same-budget random perturbation; if the PEA-induced L = ||Z_p - Z||_F is not statistically larger than random, the black-box equivalence in Equations 7-10 fails. For nonlinear models, repeat on GCN/GIN and check whether performance drops are separable from random injection; if not, the transfer claim is unsupported.","supporting_citations":[],"review_version":1}