{"id":"04f01641-e17f-459d-ab32-ad4473305a9b","arxiv_id":"2501.10985","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"GRID adds crafted noise to prediction vectors of selected core nodes so linked node pairs look like n-hop unlinked pairs, while preserving predicted labels.","lead":"The paper presents GRID, a defense that adds small noise to a graph neural network's prediction vectors so an attacker cannot tell whether two nodes are connected by a link. The defense aims to keep model predictions unchanged while pushing link-stealing attack accuracy down toward random guessing.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"GRID's per-node noise objective (Eq. 8) is optimized against unperturbed neighbor predictions, but Algorithm 1 can select both endpoints of an edge as core nodes, so the final deployed similarity is not the quantity minimized and the central disguise guarantee is not formally established.","rationale":"The reader's weakest assumption about undefined Pi/Qi for inductive queries is a real gap, but the more direct threat to the central claim is that the optimization objective in Eq. (8) does not match the deployed quantity when both endpoints of an edge are core nodes. This is an internal inconsistency in the formal argument, not merely a missing deployment detail. The experiments may still show good empirical defense, and the paper gives useful evidence: Tables 2-6 show substantial attack degradation with unchanged model accuracy, and the ablation in Table 7 supports the core-node-selection idea over noise on all nodes. However, those empirical results do not establish the abstract's unconditional 'can ensure' formulation. A concrete counterexample or a measurement on real data would settle whether the mismatch actually causes the final similarity to deviate from target. Because the paper is otherwise promising but this formal gap is real, the reader's CONDITIONAL verdict remains appropriate; I would not move it to ACCEPT or REJECT without seeing the test result or a revised objective that accounts for both endpoints' noises.","tokens_in":36089,"tokens_out":11828,"duration_ms":130968,"concrete_test":"Run Algorithm 1 on a small graph containing a triangle (or a random 20-node subgraph of Cora) with edge similarities above the threshold delta, then solve OPT-GRID for each selected core node with the paper's Algorithm 2/3 at theta=0.4 and n=3. For every edge whose both endpoints are in Nc, compare the deployed similarity sim(vi+si, vj+sj) against (a) the value sim(vi+si, vj) that the objective actually minimized, and (b) the n-hop baseline delta. If a material fraction of such edges has deployed similarity far from delta, or no closer than the undefended similarity, the central disguise guarantee is not delivered by the stated formulation.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central guarantee is that noisy prediction vectors of adjacent nodes become similar to those of n-hop indirect neighbors (abstract, Section 4.2). For a core node i, OPT-GRID minimizes Di in Eq. (8), which uses sim(vi + si, vj) for each neighbor j, where vj is the original, unperturbed prediction of j. However, at deployment every core node's prediction is perturbed. If both endpoints of an edge (i, j) are in the core set, the attacker observes sim(vi + si, vj + sj), while the optimization for i minimized against vj and the optimization for j minimized against vi. No term in the formulation controls or even evaluates sim(vi + si, vj + sj). Algorithm 1 does not prevent this situation: it greedily builds a vertex cover, and a vertex cover is not an independent set. In a triangle, for example, processing one edge can add B, and processing another edge incident to A can add A, leaving edge AB with both endpoints in Nc. The text in Section 4.2 claims 'only one node in each edge is considered,' but the algorithm provides no such guarantee. Consequently, for any edge with two core endpoints, the independently computed noises can interact in an uncontrolled way, and the paper provides no argument that the final pairwise similarity falls near the n-hop baseline. This is not a question of empirical tuning; it is a mismatch between the optimized objective and the quantity the defense claims to control, so the 'can ensure' claim in the abstract is unsupported as stated.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes GRID, a defense that adds noise to the prediction vectors of a selected subset of nodes (core nodes) after a GNN has been trained, with the goal of making the similarity of any adjacent node pair look like the similarity of an n-hop indirect pair, while constraining the noise so that the predicted label of every node is preserved and the distortion is bounded. The defense is formulated as a constrained optimization problem (OPT-GRID) and solved per core node by KKT-based projected gradient descent; core nodes are chosen by a threshold-based vertex-cover heuristic. Experiments on Citeseer, Cora, Pubmed, AIDS, and ENZYMES with GCN, GAT, GraphSAGE, and GIN report large reductions in link-stealing attack accuracy, unchanged model accuracy, and a better privacy-utility trade-off than five baselines.","tokens_in":36360,"tokens_out":8833,"duration_ms":102905,"significance":"The paper addresses an important and timely problem, and the experimental picture is broad: five datasets, eight similarity-based attacks, the ILS attacks, two influence-based attacks, four GNN backbones, and five baseline defenses, with ablations over the distortion budget, the hop count, and similarity metrics. The idea of disguising linked node pairs as n-hop indirect pairs is intuitive, and the reported attack degradation is consistent across tables, with model accuracy unchanged, which supports the empirical utility claim. However, the paper has no released code, no error bars or seeds, and several load-bearing formal claims are not supported by the provided algorithms, so the significance is contingent on fixing those gaps.","major_comments":[{"comment":"The assertion in Section 4.2 that 'only one node in each edge is considered' is not guaranteed by Algorithm 1. As printed, the else branch (lines 17-19) adds nj whenever at least one endpoint is already in Nc, so after processing a triangle both endpoints of an edge can end up in Nc; moreover, even for a standard vertex-cover algorithm, a vertex cover is not an independent set and can contain both endpoints of an edge. For any edge (i,j) with i and j both in Nc, the per-node objectives Di and Dj in Eq. (8) are minimized against the unperturbed vectors vj and vi respectively, so the deployed quantity sim(vi+si, vj+sj) is not the quantity controlled by the optimization. The paper therefore does not establish the abstract's claim that the noisy prediction vectors of any two adjacent nodes have n-hop-like similarity; this is a load-bearing gap, not a tuning issue.","section":"4.2, Algorithm 1, Eq. (8)"},{"comment":"The paper claims a formal utility guarantee, but Algorithm 3 does not provably enforce the constraints of OPT-GRID. In Step 1 the vector is centered to satisfy sum_a s_a = 0 and then each coordinate is clamped to [-v_a, 1-v_a]; clamping changes the sum, and no subsequent step restores sum_a s_a = 0, so the returned noise can violate the probability-distribution constraint (6). The label-preservation adjustment in Step 3 is also heuristic: fixing one violated inequality can perturb earlier ones, and no termination or feasibility proof is given for the loop. A formal claim requires either a projection sequence with an invariant or an explicit statement that utility is guaranteed only when the solver converges to a feasible point.","section":"4.3.4, Algorithm 3"},{"comment":"Eq. (8) defines the similarity gap using the adjacent set Pi and n-hop set Qi of the node being perturbed. For nodes outside the training graph, which is the actual inductive setting described in Section 2.1, the defender does not have a neighborhood in the training graph, so Pi and Qi are undefined and no noise can be computed. The experimental protocol in Section 5.1.3 samples attack node pairs from D1, the training graph, so the reported GAT results do not demonstrate defense for unseen inductive queries. The paper should either restrict its claims to nodes with known adjacency or specify how Pi and Qi are obtained for out-of-training-graph queries.","section":"5.1.3, Eq. (8), Section 6.1"}],"minor_comments":[{"comment":"The experimental tables report no error bars or standard deviations over random seeds, which makes it difficult to assess the stability of the claimed attack degradation.","section":"Section 5.1"},{"comment":"Table 5 appears to be a duplicate of Table 4 with only the GCN values; the numbering and content should be checked.","section":"Section 5.2, Tables 4-5"},{"comment":"The description of the dataset splits is confusing: the text introduces D3 and D4, then says the defender classifier uses D4, and the testing pairs are later described as sampled 'In D1'; the relationship between these sets should be clarified.","section":"Section 5.1.3"},{"comment":"There is a typo on line 11 ('countine' instead of 'continue'), and the condition 'ni, nj /∈ Nc' should be written explicitly as 'ni notin Nc and nj notin Nc' to avoid ambiguity.","section":"Algorithm 1"},{"comment":"Reference [3] has a malformed URL and is labelled 'Moco' while the text says it is the GAT code, and several figure axis labels appear corrupted (e.g., Figure 1 and Figure 2), so the figures need to be regenerated with proper text.","section":"References and Figures"},{"comment":"The introduction claims that attack accuracy drops to around 50%, but the tables at the default setting θ=0.4 report Attack-6 accuracy around 68-69%; the settings under which the 50% figure holds should be stated near the first occurrence.","section":"Section 1 and Section 5.2"}],"recommendation":"major_revision","confidential_remarks":"The stress-test concern about both endpoints of an edge being core nodes is valid and central to the paper's guarantee; the same issue is independently visible in the printed Algorithm 1. The formal utility guarantee is also not actually proven, because the constraint-handling heuristic in Algorithm 3 can violate the probability-distribution constraint. The inductive setting needs clarification. These are fixable with a substantial revision, so I recommend major revision rather than rejection, but the current manuscript should not be accepted as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this is a solid candidate for a defense paper, not a finished one. GRID adds noise to GNN prediction vectors so adjacent nodes look like n-hop indirect neighbors, and it selects a thresholded vertex cover of core nodes to cut computation. That is a genuine extension of MemGuard's idea to link stealing, and the experiments are extensive: five datasets, GCN/GAT/GraphSAGE/GIN, eight similarity attacks plus two influence attacks, all with unchanged model accuracy. The zero-utility-loss constraint is satisfied by construction (noise keeps argmax), and the comparison to GAP and MemGuard is fair. Credit where due: core-node selection is a real contribution, and the empirical effect is consistent.\n\nThe problem is the central guarantee. Eq. (8) optimizes Di using sim(vi+si, vj) with vj unperturbed. At deployment every core node is perturbed. Algorithm 1 is a vertex cover, not an independent set, so an edge can have both endpoints in the core set; then the attacker observes sim(vi+si, vj+sj), which no term in the objective controls. The text says \"only one node in each edge is considered,\" but that is false for the algorithm as written. So the abstract's \"can ensure\" overclaims. This does not kill the empirical direction, but it makes the defense heuristic rather than guaranteed, and the authors should either prove a bound or soften the claim.\n\nOther soft spots: for inductive queries, it is never specified who supplies the queried node's neighbor set for noise crafting; the ALS metric in 5.5.2 is inverted; there are no error bars or seeds and no code. Also, at the default θ=0.4 the strongest gray-box attack stays near 70% AUC, so \"close to random guessing\" is only true for weaker attacks.\n\nBottom line: worth engaging. The idea is plausible, the evaluation is broad, and the flaw is fixable with a corrected analysis or a modified selection scheme. I would send it to review, but I would push hard on the guarantee.","headline":"GRID is a plausible prediction-perturbation defense for link stealing with broad experiments, but its core disguise guarantee is not actually ensured by the algorithm, and the strongest attack still lands near 70% AUC at the default budget.","tokens_in":36946,"tokens_out":2579,"would_cite":false,"duration_ms":29085,"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":"GRID defends GNN link privacy by adding noise only to a vertex cover of core nodes, so adjacent pairs look like distant pairs while every predicted label is unchanged.","keywords":["link stealing attack","graph neural network privacy","prediction vector perturbation","core node selection","vertex cover","zero utility loss defense","inductive GNN defense"],"falsifier":"Query an inductive GAT model with node pairs that were not part of the training graph $D_1$ and run Attack-6 on the returned prediction vectors. If GRID does not specify how the defender obtains $P_i$ and $Q_i$ for these unseen nodes, the attack accuracy on that held-out pair set should remain close to the no-defense baseline, which would show that the zero-utility guarantee does not transfer to inductive queries.","tokens_in":35850,"feed_emoji":"🛡️","tokens_out":6297,"duration_ms":65666,"temperature":0.7,"pith_summary":"The paper proposes a defense, called GRID, against link-stealing attacks on graph neural networks. It adds small noise vectors to the prediction outputs of a carefully chosen subset of nodes, the core nodes, so that the similarity of any two adjacent nodes' predictions is pushed down to the level of nodes that are several hops apart. The added noise is constrained so that the argmax of every prediction vector stays the same, giving zero change in classification accuracy, while the distortion stays within a budget. On five datasets, the paper reports that attack accuracy and AUC fall from the 85–98 percent range to roughly 50–74 percent for eight similarity-based attacks and the strongest inductive attacks, while model accuracy is unchanged.","feed_headline":"Link-stealing attacks drop to near-random guessing","feed_subtitle":"GRID noises only a small vertex-cover node set, so attack accuracy falls while classification stays intact.","key_machinery":"The load-bearing object is the similarity gap $D_i$ of Eq. (8), which is minimized for each core node so that adjacent nodes become similarity-indistinguishable from $n$-hop indirect neighbors. The core node set is a threshold-based vertex cover: each edge with similarity above a threshold gets at least one endpoint noised, while low-similarity edges are left alone, which avoids noise offset and cuts computation. The optimization OPT-GRID is a constrained non-linear problem solved by iterative gradient descent with KKT conditions and a projection-based constraint check that enforces the label-preservation, probability-distribution, and distortion-budget constraints.","core_discovery":"The central claim is that a trained GNN can be wrapped by a post-processing step that makes link-stealing attacks statistically useless without changing the model's predictions. For every edge, GRID selects at least one endpoint as a core node and optimizes a noise vector $s_i$ for that node's prediction vector $v_i$ so that the similarity gap $D_i = \\sum_{j \\in P_i} \\operatorname{sim}(v_i+s_i, v_j) - \\sum_{k \\in Q_i} \\operatorname{sim}(v_i+s_i, v_k)$ is minimized, where $P_i$ is the adjacent-node set and $Q_i$ is the $n$-hop indirect set. Minimizing this gap makes the noisy prediction of a core node look as similar to its neighbors as to nodes $n$ hops away, thereby disguising links. The optimization is constrained so that the argmax of each prediction vector is preserved (zero label loss), the noisy vector remains a probability distribution, and the $\\ell^1$ distortion stays under a budget $\\theta$. In the paper's experiments, eight similarity-based attacks and the strongest inductive ILS attacks lose most of their advantage, with AUC and accuracy falling from roughly 85–98 percent to 50–74 percent while model accuracy is exactly unchanged.","pith_inferences":["In inductive settings the paper does not specify who provides $P_i$ and $Q_i$ for nodes outside the training graph; if the provider must know a query node's neighborhood to noise it, the defense either fails for unseen nodes or leaks the very adjacency it protects.","Because the disguise target is a single global threshold $\\delta$ estimated from sampled $n$-hop pairs, graphs with heterogeneous local density may be over-noised in sparse regions and under-noised in dense regions; per-region thresholds are a natural testable extension.","An attacker who ignores prediction similarity and uses other signals, such as influence-based or attribute-based cues, could bypass GRID; the paper's own numbers show influence-attack recall falls only about 10 percent, suggesting the defense is tuned specifically to similarity statistics.","The zero-utility guarantee covers label prediction only; downstream tasks that consume the full prediction vectors still see distortion up to $\\theta$, so 'zero utility loss' is narrower than zero information loss."],"forward_implications":["Similarity-based link-stealing attacks, including unsupervised Attack-0 and supervised black-box and gray-box attacks, drop from roughly 85–98 percent AUC to 56–74 percent across Citeseer, Cora, Pubmed, AIDS, and ENZYMES.","The strongest inductive ILS attacks A2 and A9 on GAT fall to 57–69 percent AUC, so the defense transfers from transductive GCN to inductive GAT, GraphSAGE, and GIN models.","Noising only core nodes avoids the noise-offset problem: full-graph noising leaves attack accuracy several points higher and costs about six times more computation, e.g., 45,052 seconds versus 7,938 seconds on Pubmed with $n=5$.","With distortion budget $\\theta=0.4$, recall of all eight original attacks drops below roughly 70 percent, and as $\\theta$ approaches 1.0 the recall approaches 50 percent, i.e., random guessing.","Compared with the differential-privacy defense GAP, GRID keeps model accuracy flat while GAP's accuracy falls toward 60 percent at small privacy budgets, giving a better reported privacy-utility trade-off but with empirical rather than formal privacy guarantees."],"supporting_citations":[{"why":"It defines the eight similarity-based link-stealing attacks and the correlation-plus-cosine similarity metrics that GRID targets.","marker":"[11]"},{"why":"It introduces the ILS attacks A2 and A9 against inductive GNNs, which the paper uses to evaluate GRID under inductive settings.","marker":"[46]"},{"why":"It supplies the Link-Infiltrator influence-based attack that GRID is tested against in Section 6.1.","marker":"[21]"},{"why":"It supplies the LinkTeller influence-based attack used to measure GRID's effect on influence-based link stealing.","marker":"[45]"},{"why":"It provides the GAP differentially private GNN defense that GRID compares against on the privacy-utility trade-off.","marker":"[26]"},{"why":"It provides MemGuard, the prior prediction-noise defense that GRID extends and outperforms in the comparison.","marker":"[15]"},{"why":"It supplies the L2-Regularizer defense and the membership-inference attack framing used as a counterpart baseline.","marker":"[32]"},{"why":"It supplies the Min-Max Game adversarial-regularization defense used as a counterpart baseline.","marker":"[23]"},{"why":"It supplies the Dropout regularization defense used as a counterpart baseline.","marker":"[36]"}],"fun_headline_variants":["GRID disguises links, cutting attack accuracy to near-random","Zero-loss GRID defense blinds link-stealing attacks","Link-stealing attacks on GNNs become coin flips with GRID","GRID noise makes link inference no better than guessing"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The defense only works if the model provider already knows, for every node whose predictions are queried, which other nodes it is directly connected to and which nodes lie several hops away.","fun_headline_variants_meta":{"raw":{"variants":["GRID disguises links, cutting attack accuracy to near-random","Zero-loss GRID defense blinds link-stealing attacks","Link-stealing attacks on GNNs become coin flips with GRID","GRID noise makes link inference no better than guessing"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000692,"raw_usage":{"total_tokens":3204,"prompt_tokens":1087,"completion_tokens":2117,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":703,"completion_tokens_details":{"reasoning_tokens":2047}},"tokens_in":703,"tokens_out":2117,"duration_ms":17525,"temperature":1.0,"reasoning_tokens":2047,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T18:45:59.116289+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Query an inductive GAT model with node pairs that were not part of the training graph $D_1$ and run Attack-6 on the returned prediction vectors. If GRID does not specify how the defender obtains $P_i$ and $Q_i$ for these unseen nodes, the attack accuracy on that held-out pair set should remain close to the no-defense baseline, which would show that the zero-utility guarantee does not transfer to inductive queries.","supporting_citations":[{"cited_title":"Stealing links from graph neural networks","cited_arxiv_id":null,"evidence_quote":"It defines the eight similarity-based link-stealing attacks and the correlation-plus-cosine similarity metrics that GRID targets."},{"cited_title":"Devil in disguise: Breaching graph neural networks privacy through infiltration","cited_arxiv_id":null,"evidence_quote":"It supplies the Link-Infiltrator influence-based attack that GRID is tested against in Section 6.1."},{"cited_title":"Linkteller: Recovering private edges from graph neural networks via influence analysis","cited_arxiv_id":null,"evidence_quote":"It supplies the LinkTeller influence-based attack used to measure GRID's effect on influence-based link stealing."},{"cited_title":"Gap: Differentially private graph neural net- works with aggregation perturbation","cited_arxiv_id":null,"evidence_quote":"It provides the GAP differentially private GNN defense that GRID compares against on the privacy-utility trade-off."},{"cited_title":"Memguard: Defending against black-box membership inference attacks via adversarial examples","cited_arxiv_id":null,"evidence_quote":"It provides MemGuard, the prior prediction-noise defense that GRID extends and outperforms in the comparison."},{"cited_title":"Membership inference attacks against machine learning models","cited_arxiv_id":null,"evidence_quote":"It supplies the L2-Regularizer defense and the membership-inference attack framing used as a counterpart baseline."},{"cited_title":"Machine learning with membership privacy using adversarial regularization","cited_arxiv_id":null,"evidence_quote":"It supplies the Min-Max Game adversarial-regularization defense used as a counterpart baseline."}],"review_version":1}