{"id":"c0d20638-83e3-4521-89df-0791bc41bba1","arxiv_id":"2504.20869","paper_version":2,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A new link-noise metric, computed from node degrees and entropy-based dissimilarity, ranks candidate adversarial edges and prunes the search space for targeted graph attacks, yielding competitive or better attack success than existing methods.","lead":"This paper defines a 'noise' score for each link that could be added to a graph, then uses that score to design faster adversarial attacks against graph neural networks. It reports that on three citation networks the best proposed attack, NMAB, outperforms prior attacks like NETTACK while searching far fewer candidate links.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No direct evidence that fLN ranks per-link attack impact; NGA's weak results and missing error bars leave the pruning claim empirically underdetermined.","rationale":"The reader's weakest assumption concerns surrogate GCN fidelity and the toy-model proof; I agree these matter, but I sharpen the concern: the paper never directly validates the proposed metric fLN against actual per-link attack impact. The strongest evidence for the metric would be a rank correlation with the true margin decrease, yet the paper only reports end-to-end attack success of methods that combine fLN with margin search. The NGA result is the clearest internal warning sign: if fLN were a faithful measure of per-link attack strength, greedily taking the top-Delta links should be a strong baseline; instead NGA is the worst method in Table 3. NMA/NMAB's success could be driven by margin selection within a slightly enriched candidate set, not by accurate noise quantification. The Appendix proof does not repair this gap because it relies on one-hot features and a diagonal-like W*, which is inconsistent with using continuous cross-entropy dissimilarity in Eq. 7; at best it motivates the degree weighting, not the entropy term. The paper itself notes that code is only available on acceptance, so no independent replication is currently possible. These issues do not refute the empirical finding that NMAB attains good attack success; they do mean the central interpretability claim that noise quantifies attack strength is under-supported. Since the reader already returned CONDITIONAL and my concern reinforces rather than overturns that verdict, the appropriate verdict is UNCHANGED.","tokens_in":21908,"tokens_out":6804,"duration_ms":74178,"concrete_test":"Sample 100 targeted nodes from Cora (or all datasets). For every valid non-edge (u,v), compute fLN(u,v) via Eq. 8 from the surrogate GCN, and independently compute the exact single-link classification-margin decrease DeltaCM(u,v) = f_target(G)_u,c - f_target(G union (u,v))_u,c for each target model (GCN, SGC, GAT). Then compute: (i) the Spearman rank correlation between fLN and DeltaCM, and (ii) precision@5Delta, defined as the fraction of the true top-5Delta margin-decreasing links that appear in the top-5Delta fLN list. If the correlation is weak or precision@5Delta is near the random baseline (5Delta divided by the number of candidate non-edges), then fLN does not quantify per-link attack strength and the pruning advantage claimed for NMA/NMAB is not established. This test also controls for surrogate transfer because the target models are exactly those evaluated in Table 3.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central assertion is that fLN (Eq. 8) quantifies the attack strength of each adversarial link. The paper never measures this quantity against the actual per-link attack effect. The end-to-end results in Table 3 show that NMA/NMAB, which combine fLN pruning with margin-based search, outperform NETTACK in several cells, but this does not isolate the noise metric. In fact, NGA, which directly takes the Delta highest-fLN links, has the worst average rank (5.67 in Table 3), well behind NETTACK, FGA, and SGA; directly 'high-noise' links are therefore not demonstrably the strongest perturbations. The only evidence that the pruned candidate set is enriched is indirect, and Table 3 reports averages over 5 splits with no confidence intervals or significance tests, so the NMAB advantage (e.g., 0.9676 vs 0.9044 on Cora-GCN) could be within run-to-run variation. The toy-model proofs in Appendices A.1 and A.2 assume one-hot features and a diagonal-like optimal W*, a setting in which the continuous entropy dissimilarity of Eq. 7 is not justified; this further weakens the claim that Eq. 8 is a derived measure rather than an ad hoc heuristic. The paper also states in Section 5 that code will be released only on acceptance, so independent replication is currently impossible. Without a direct correlation test, the load-bearing premise that fLN ranking identifies the strongest adversarial links remains unverified.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a link-noise metric, fLN (Eq. 8), intended to quantify the attack strength of each candidate adversarial link in targeted structural attacks on GNNs. The metric combines the GCN aggregation weight 1/sqrt(|N_v|+1) with a cross-entropy dissimilarity between the target node and a candidate adversarial node. The authors prove two propositions in a simplified one-layer GCN with one-hot features and a diagonal-like optimal weight matrix, claiming that low-degree nodes are easier to attack and that low-degree or dissimilar adversarial nodes have larger influence. Based on this, they propose three attack strategies: NGA (greedily pick the highest-fLN links), NMA (prune candidates by fLN, then greedily select links by classification margin), and NMAB (multi-step beam search over fLN-pruned candidates). Experiments on Cora, Citeseer, and Pubmed against GCN, SGC, and GAT report that NMAB achieves the best average rank, NMA is competitive with NETTACK, and the selected adversarial nodes tend to be low-degree, class-dissimilar, and high-confidence.","tokens_in":22279,"tokens_out":4654,"duration_ms":51127,"significance":"The central claim is that fLN provides an interpretable and efficient ranking of adversarial link strength, so that pruning by fLN can reduce the search space of margin-based attacks without losing attack power. If validated, this would be a useful contribution: the candidate-pruning mechanism is simple, the algorithms are clearly specified, and the time-cost analysis in Section 5.5.5 is a genuine practical addition. The paper is also transparent about the toy-model nature of its theoretical propositions and about the fact that code will be released only upon acceptance. However, the key validation is currently missing: the paper never directly measures whether high-fLN links are actually the strongest perturbations. The only attack that isolates fLN ranking, NGA, performs worst in Table 3, and the property analysis in Section 5.5.4 is largely circular because low degree and dissimilarity are encoded into fLN by construction. The statistical evidence also lacks error bars or significance tests.","major_comments":[{"comment":"The load-bearing premise that fLN ranks per-link attack strength is not directly validated, and the one experiment that isolates this premise, NGA, gives the worst average rank (5.67) among all methods in Table 3, behind NETTACK, FGA, and SGA. The paper should add a direct ranking test: for a sample of target nodes, evaluate the effect of each valid adversarial link (e.g., the classification-margin decrease after adding that link alone) and compute the correlation with fLN. An ablation of NMA that replaces the fLN-pruned candidate set with a random or lowest-fLN candidate set of the same size would also isolate whether fLN pruning, rather than the margin search, is responsible for the observed performance.","section":"§4.2, Table 3"},{"comment":"The analysis of adversarial node properties is presented as supporting evidence for the noise concept, but the preferences it reports are encoded into the metric by construction. Equation (8) divides by sqrt(|N_v|+1), so low-degree nodes are favored by the metric itself, and the cross-entropy dissimilarity in Eq. (7) directly rewards nodes whose class distribution differs from the target. Proposition 4.1 and 4.2 derive the same degree and dissimilarity tendencies from the aggregation formula. Therefore, observing that NMA/NMAB select low-degree, dissimilar nodes does not independently validate fLN; it only confirms that the algorithms follow their own scoring function. The authors should either reframe this section as a consistency check or test whether the same properties hold for the actually strongest links as measured by margin, not for the links selected by fLN.","section":"§5.5.4 and Eq. (8)"},{"comment":"The theoretical support for Eqs. (6)-(8) rests on strong assumptions that are not connected to the actual experimental setting: one-hot features, a one-layer GCN, a 'diagonal-like optimal W*', and equal noise for all adversarial links in Proposition 4.1. In particular, the statement in the proof of Proposition 4.1 that a well-trained GCN has a diagonal-like optimal weight matrix is asserted without proof and does not follow from the softmax cross-entropy training objective, especially with real features, ReLU activations, and multiple layers. Since the surrogate model used in Eqs. (7)-(8) is a real multi-layer GCN with bag-of-words features, the derivation of fLN as a quantitative measure is not established. The authors should either explicitly label the propositions as heuristic motivation rather than derivation, or extend the analysis to settings closer to the experiments.","section":"Appendices A.1 and A.2, Propositions 4.1 and 4.2"},{"comment":"All experimental results are reported as averages over 5 random splits with no standard deviations, confidence intervals, or significance tests. This matters because several key comparisons are close or could plausibly be within run-to-run variation; for example, NMAB versus NMA on PubMed-GCN (0.9842 vs 0.9802) and NMAB versus NETTACK on Cora-SGC (0.9166 vs 0.9278) are small differences. The authors should report per-split results or paired significance tests (e.g., Wilcoxon signed-rank over the 1000 target nodes or over splits) for the main comparisons in Table 3.","section":"§5.4, Table 3"}],"minor_comments":[{"comment":"The statement that code 'will be publicly available..., depending on the acceptance' limits reproducibility; please release the code and specify the environment and versions used for the experiments.","section":"§5, first paragraph"},{"comment":"Figures 2, 3, and 4 contain corrupted placeholder text such as '/uni00000031/uni00000028/...' instead of proper axis labels and legends; these figures need to be regenerated.","section":"Figures 2-4"},{"comment":"There is a citation inconsistency: 'Zügner et al. [6] first pointed out...' refers to NETTACK, but reference [6] is Dai et al.'s ICML 2018 paper; NETTACK is reference [32]. Please correct the citation.","section":"§2.3, References"},{"comment":"The phrase 'as if the total layer of the corresponding GNN is k' is unclear; please specify whether h^(k)_u and h^(k)_v are the softmax outputs of a k-layer GCN or intermediate hidden representations.","section":"Equation (7)"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Read it. Useful, concrete paper on targeted structural graph attacks. The genuinely new piece is the link-noise metric fLN (Eq. 8) and the NMA/NMAB attack variants built on it. The metric is a plausible heuristic: degree-normalized aggregation weight times an entropy-based dissimilarity between the surrogate GCN's node representations. The authors do a solid job of motivating it from the GCN aggregation in Eq. (2), and the three proposed attacks are clearly specified. NMAB's average rank of 1.67 across nine dataset/model cells is the headline result, and the paper also shows that entropy dissimilarity beats Euclidean and cosine in their setup (Table 5). The analysis of selected adversarial nodes (low-degree, different-class, high-confidence neighbors) is a reasonable descriptive finding.\n\nThe soft spots are real and should be addressed before publication. First, the central claim that fLN quantifies per-link attack strength is not directly tested. The end-to-end results combine fLN pruning with margin-based search, so they cannot isolate the metric. The clearest signal against the strong version is in the paper's own table: NGA, which just takes the top-fLN links greedily, has the worst average rank (5.67), well behind NETTACK, FGA, and SGA. That doesn't sink the pruning idea—the margin step may be the essential part—but it does mean the paper should talk about what exactly fLN is contributing.\n\nSecond, the numbers in Table 3 are averages over 5 splits with no error bars or significance tests. Some of the NMAB advantages (e.g., 0.9676 vs 0.9044 on Cora-GCN) are large, but the reader has no idea about run-to-run variability. With 1000 target nodes per split, these could still be stable; we need the variance reported.\n\nThird, the theoretical propositions (4.1 and 4.2) rest on a one-layer GCN, one-hot features, and a 'diagonal-like' optimal W*. That's a toy model, not a derivation of Eq. (8), and the paper should not present it as theoretical grounding for the specific entropy dissimilarity. Appendix A.1 is honest about the assumptions, but the gap between the toy model and the actual heuristic is wide.\n\nFourth, the code is not released; Section 5 says it will be available 'depending on the acceptance.' That's a practical barrier to independent replication.\n\nOverall, the empirical pattern is plausible and the pruning framework is useful to the graph-attack community. The paper deserves a serious referee, not a desk rejection. My advice: ask for (a) a direct correlation or ablation between fLN ranking and per-link margin impact, (b) error bars on Table 3, and (c) code release or at least a detailed pseudocode with all hyperparameters. With those changes, I'd be comfortable seeing it accepted.","headline":"A plausible new heuristic for candidate pruning in targeted structural attacks, but the paper's central claim that its noise metric ranks per-link attack strength is under-supported and should be tested directly.","tokens_in":22772,"tokens_out":3240,"would_cite":true,"duration_ms":33679,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a per-link noise score derived from GNN hidden states ranks adversarial links by attack strength and enables cheap targeted attacks.","keywords":["graph neural networks","graph adversarial attacks","link noise","targeted attacks","noise propagation","candidate pruning","homophilic graphs","entropy dissimilarity"],"falsifier":"Train a surrogate GCN on a homophilic graph, compute $\\text{fLN}$ for every candidate edge of many target nodes, then add each edge alone and record the true classification-margin drop. If the $\\text{fLN}$ rank order is not strongly associated with the margin drop (for example, if the Spearman correlation is near zero or negative), the noise metric fails as the paper defines it.","tokens_in":21733,"feed_emoji":"🔗","tokens_out":9698,"duration_ms":93770,"temperature":0.7,"pith_summary":"This paper tries to make structural graph attacks interpretable by assigning each candidate added link a number—its noise—that measures how much that link would disturb the neighborhood aggregation of the target node. It argues that ranking candidate links by this noise, rather than searching all possible links by classification margin, finds the strongest perturbations with a much smaller candidate set. If true, targeted evasion attacks on homophilic graphs become cheaper and explainable: effective attacks connect the target to low-degree, dissimilar, confidently misclassified nodes. The paper reports that the noise-ranked strategies NMA and NMAB match or beat the full margin-based NETTACK baseline on Cora, Citeseer, and Pubmed across GCN, SGC, and GAT, with NMAB best overall.","feed_headline":"A noise score ranks the most harmful links to add","feed_subtitle":"Scoring each candidate edge by how much it disturbs a GNN's hidden states lets attacks find strong perturbations fast.","key_machinery":"The load-bearing object is the appropriate link noise fLN in Eq. (8): a per-candidate score equal to the cross-entropy between the surrogate GCN's hidden or class-probability vectors of the target $u$ and the adversarial node $v$, divided by $\\sqrt{|N_v|+1}$. The numerator is the dissimilarity term $\\text{DIS}(u,v)$ proposed in Eq. (7); the denominator is the aggregation weight the new link would receive under symmetric normalized adjacency. Two propositions justify the shape: under a one-layer GCN with one-hot features and a near-diagonal optimal weight matrix, Proposition 4.1 shows low-degree targets are easier to attack and low-degree adversarial nodes have larger influence, and Proposition 4.2 shows that, degree held equal, more dissimilar adversarial nodes disturb aggregation more. The metric packages both factors into one ranking, and this ranking is what lets NGA, NMA, and NMAB prune the candidate space.","core_discovery":"The paper's central claim is that adversarial links have measurable noise and this noise can be computed before an attack. For a target $u$ and a candidate $v$ not yet connected to it, Eq. (8) defines $$\\text{fLN}(u,v)=\\frac{-\\sum_i ($h_u^{{(k)}}$)_i \\log ($h_v^{{(k)}}$)_i}{\\sqrt{|N_v|+1}},$$ where $h^{(k)}$ are surrogate GCN hidden representations interpreted as class probabilities. The numerator captures how different the candidate's information is from the target's, and the denominator captures how strongly that information would enter the aggregation. The paper claims that ranking candidate links by this score localizes the strongest perturbations, so greedy or margin-based searches can be restricted to a small candidate set without losing attack power. It also claims, via two propositions on a one-layer GCN with one-hot features, that low-degree targets are easier to attack and low-degree, dissimilar adversarial nodes are the most influential; the experiments then show NMA and NMAB matching or beating full-margin NETTACK while using far fewer candidates, with NMAB best overall.","pith_inferences":["An efficiency gain the paper does not pursue: since fLN for a target only needs stored surrogate representations and a degree lookup, the score can be precomputed once per graph and reused across targets.","A testable premise behind NMAB's boost: the optimal-substructure observation was demonstrated on one target node; if it does not hold broadly, the boost could be replaced by a larger retain list.","An extension the paper explicitly leaves open: on heterophilic graphs the homophily assumption fails, so the metric would need a signed or re-oriented dissimilarity term before it transfers.","A possible reverse use: the same ranking identifies structurally fragile nodes, so high-fLN candidate links could be pruned or rewired to harden a GNN, not just attacked."],"forward_implications":["Attacks can run at a fraction of the search cost: NMA restricts margin evaluation to the top $5\\Delta$ noise-ranked links and still matches or beats NETTACK, which searches all valid links.","Because the surrogate is GCN and the attacks still transfer to SGC and GAT, the noise ranking is not tied to one model's parameters.","Effective adversarial links have a consistent profile—low degree, different class, high predicted confidence—so attack outcomes become explainable in structural terms.","Noise ranking can be used as a preprocessing plug-in for other attack methods, cutting unnecessary searches on low-noise candidates.","Choosing entropy as the dissimilarity measure matters: the paper's comparisons show entropy beats Euclidean and Cosine distance for every proposed strategy."],"supporting_citations":[{"why":"Margin-based targeted structural attack NETTACK; the full-search baseline whose candidate space the proposed methods prune.","marker":"[32]"},{"why":"GCN architecture used as the surrogate model supplying the hidden representations in Eqs. (7)-(8) and as one of the attacked models.","marker":"[13]"},{"why":"FGA gradient-based targeted attack used as a baseline in the experiments.","marker":"[4]"},{"why":"SGA subgraph gradient attack used as a baseline and source of the second-possible-class candidate idea.","marker":"[15]"},{"why":"Supplies the Cora, Citeseer, and Pubmed benchmark datasets used in all experiments.","marker":"[17]"},{"why":"Open-source implementation platform used to run the attacked GNNs and baselines.","marker":"[12]"},{"why":"Two prior uses of entropy or cross-entropy node dissimilarity that motivate Eq. (7).","marker":"[14, 27]"}],"fun_headline_variants":["Noise score pinpoints the most damaging graph attacks","A simple noise metric ranks which edges to attack","Scoring perturbation noise finds strong attacks fast","Noise score localizes the most damaging edges to add"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The results depend on the surrogate GCN's class-probability scores being a faithful stand-in for how much each candidate edge actually disturbs the targeted model's prediction, including for deep GNNs with real features.","fun_headline_variants_meta":{"raw":{"variants":["Noise score pinpoints the most damaging graph attacks","A simple noise metric ranks which edges to attack","Scoring perturbation noise finds strong attacks fast","Noise score localizes the most damaging edges to add"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000613,"raw_usage":{"total_tokens":2851,"prompt_tokens":948,"completion_tokens":1903,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":564,"completion_tokens_details":{"reasoning_tokens":1842}},"tokens_in":564,"tokens_out":1903,"duration_ms":12057,"temperature":1.0,"reasoning_tokens":1842,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T05:17:03.686193+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Train a surrogate GCN on a homophilic graph, compute $\\text{fLN}$ for every candidate edge of many target nodes, then add each edge alone and record the true classification-margin drop. If the $\\text{fLN}$ rank order is not strongly associated with the margin drop (for example, if the Spearman correlation is near zero or negative), the noise metric fails as the paper defines it.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Margin-based targeted structural attack NETTACK; the full-search baseline whose candidate space the proposed methods prune."},{"cited_title":"Kipf and Max Welling","cited_arxiv_id":null,"evidence_quote":"GCN architecture used as the surrogate model supplying the hidden representations in Eqs. (7)-(8) and as one of the attacked models."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"SGA subgraph gradient attack used as a baseline and source of the second-possible-class candidate idea."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Cora, Citeseer, and Pubmed benchmark datasets used in all experiments."}],"review_version":1}