acceptodds
Under review as a conference paper at ICLR 2027

THE PRICE OF FORGED EVIDENCE IN SIMILARITY-BASED DEFENSES FOR GRAPH NEURAL NETWORKS

33 views

Abstract

Similarity-based defenses for graph neural networks decide whether an edge is genuine by comparing the features of its endpoints. If the attacker can also write those features, that evidence can be forged. Adaptive attacks are known to break such defenses; what has not been measured is how cheap the forgery is and how much of the damage it explains. We price it exactly: for Jaccard and cosine filters we give the fewest feature changes that make an inserted edge pass, in closed form, and about one copied word for each inserted edge the filter would remove makes GCN-Jaccard keep every edge that Metattack or PRBCD inserts, with no change to the attack, for at most 0.46% of the non-zero feature entries on the citation graphs (1.31 to 5.84% on the heterophilous ones). The defense then does harm: on Cora, 136 copied words added to Metattack’s graph leave GCN-Jaccard losing more accuracy than an undefended GCN (15.7 against 13.3 points). We also measure forgery edge by edge: we count which inserted edges each defense keeps, and rerun the defense on clean features while its model still trains on poisoned ones, which separates blinding from ordinary feature damage that no edge filter was built to stop; the pruning counts this literature reports conflate the two. Every countermeasure we test that reads raw features, a higher threshold, a rule that discounts shared words, an edge-aware corroboration check, and GNNGuard’s stricter cosine, only raises the price, while the defender pays in clean edges. Defenses that learn their evidence first are the exception: on Cora and CiteSeer the same copies change neither a STABLE-style purifier nor SimP-GCN by more than 2.8 points, though a large feature budget still blinds them. A joint bilevel attack, CLASP, finds the forgery without seeing the defense. The pattern holds across six graphs spanning homophily 0.22 to 0.81, wherever the attacker’s edges do damage.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, adversarial robustness, graph poisoning, feature poisoning, similarity-based defenses, graph purification, adaptive attacks

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_szgDOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the additional feature-edit cost of making existing structural attacks survive similarity-based graph defenses. It gives exact single-edge costs for binary Jaccard and one-endpoint continuous cosine thresholds, evaluates post-hoc camouflage on Metattack and PRBCD graphs, and measures edge survival with poisoned versus clean evidence while keeping victim-training features fixed. CLASP supplies jointly poisoned graphs for a broader budget sweep. The strongest contribution is the quantitative audit of inexpensive raw-feature forgery, rather than a new state-of-the-art attack.

Critical strengths
  1. The fixed-graph camouflage experiment is a clear mechanism test and quantitatively demonstrates cheap raw-feature forgery. On Cora, 136 copied words raise Metattack inserted-edge survival from 47% to 100%, while GCN-Jaccard's loss increases from 7.6 to 15.7 percentage points (Table 2). The exact single-edge cost characterizations help explain the mechanism under their stated assumptions.

  2. The study includes unusually extensive, auditable controls: feature-only and sequential attacks, matched total edit counts, matched-node random feature changes, untouched test nodes, alternative splits, and attack-seed replication. Negative findings, including CLASP's weakness on heterophilous graphs, are reported. Appendices I and J examine adaptive attacks and purifier strength, and stored graphs/results plus the full evidence/training-feature intervention grid make several claims directly checkable.

Critical weaknesses
  1. The proposed decomposition is interpreted too strongly. The clean-evidence intervention measures a conditional effect of changing filtering evidence, but the remaining loss is not entirely feature damage as stated in Section 5.2 and Figure 2. For the same Cora joint-10% adjacency, Table 38 gives 66.17% accuracy with clean evidence and clean training features, versus the clean-graph baseline of 77.93%; approximately 11.77 points of structural damage remain. The supplementary grid gives 40.47% with clean evidence and poisoned training features, and 36.30% with both poisoned. These support a conditional evidence effect of 4.17 points, not a complete two-way attribution of total loss. The intervention also changes retention of clean edges. Because this attribution is a central claimed contribution, the existing full grid should be used to report the structural residual and interaction, and the causal interpretation should be narrowed.

  2. The structural comparisons appear to mix label-access assumptions. Section 3.1 exposes training labels, whereas supplementary a_rbcd calls pass data.y together with test-node indices to PRBCD/GRBCD (unified_bench.py:151–154; extend_bench.py:143–146). This appears to provide true test labels, unlike CLASP's pseudo-label objective. Table 3 acknowledges evasion-to-poisoning transfer but does not clarify this information difference. The exact dependency behavior should be confirmed, and key comparisons should either use matched pseudo-label access or be identified as oracle-label stress tests. This affects comparative and threat-model conclusions; it does not invalidate the fact that a given stored graph can be camouflaged.

Questions for authors

Clarifications or checks that could materially change the assessment:

  1. Can the existing 2×2 intervention grid be used to report residual structural damage, the training-feature channel, the conditional evidence-channel effect, and their interaction separately? How will the Section 5.2/Figure 2 claim that the remaining clean-evidence loss is feature damage be revised, given the clean-feature attacked-graph condition and changes in clean-edge retention?

  2. Do the PRBCD/GRBCD calls consume true test labels in the exact dependency version used for the reported experiments? Please clarify this access explicitly and provide matched-information key comparisons, or label the relevant rows as oracle-label stress tests. The static call-site evidence is direct; the actual pinned implementation behavior still requires confirmation.

  3. What justifies the learned-evidence 'price floor'? Appendix I is a useful adaptive control, but its edits are donor words, it uses five greedy rounds, and it does not optimize through encoder training. Failure to find cheaper severe blinding with this attack does not lower-bound the best adaptive attack. Appendix J usefully addresses purifier strength. Can the broader conclusion be limited to the tested attacks/implementations, or supported by budget curves at matched damage targets?

  4. Under what independence conditions does Appendix M's sum of isolated cosine projection costs equal a graph-level exact minimum or floor? Appendix S correctly notes multi-edge coupling; shared moving nodes and changing opposite endpoints can invalidate a direct sum interpretation. Please state the necessary conditions or present the sum as an independent-edge reference. Also distinguish L1 moved mass, sum-of-row-L2 normalization, and median relative edge price.

The existing evidence supports cheap raw-feature forgery; these questions concern the scope of the quantitative and causal conclusions. A minor correction, not a standalone decision driver: in Appendix S, deleting a shared word at one endpoint reduces the intersection but leaves the union unchanged. The Proposition 1 conclusion still follows after correcting this case.

6 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for a review that engaged with the appendices and with the code, and whose points have led to real changes in the paper. We hope our revisions and responses merit reconsideration of a higher evaluation.

W1 and Q1. The decomposition of the loss

Review: "The proposed decomposition is interpreted too strongly. The clean-evidence intervention measures a conditional effect of changing filtering evidence, but the remaining loss is not entirely feature damage as stated in Section 5.2 and Figure 2 ... the existing full grid should be used to report the structural residual and interaction, and the causal interpretation should be narrowed."

Response: The reviewer's arithmetic is correct and our wording was too strong. Table 1 gives the four cells for the Cora joint 10% graph, against GCN-Jaccard's 77.93 on the clean graph.

Table 1: the intervention grid, Cora joint 10%, GCN-Jaccard

evidencevictim's training featuresaccuracyedges pruned
cleanclean66.17657
cleanpoisoned40.47657
poisonedclean63.03432
poisonedpoisoned (as deployed)36.30432

The total loss of 41.63 points decomposes into a structural residual of 11.77, a training-feature channel of 25.70, an evidence main effect of 3.13 and an interaction of 1.03. The conditional evidence effect as deployed is 4.17, which is the quantity we reported. CiteSeer at the same budget gives 11.27, 31.37, 4.97 and -1.87 against a total of 45.73, with a conditional effect of 3.10. The revision reports all four components at every budget, and reports the clean-edge retention change the reviewer noticed, which is the 657 against 432 in Table 1.

The causal wording is narrowed in three places.

Revised text, Sec. 5.2: "What it measures is the conditional effect of changing the filter's evidence while the victim's training features stay poisoned. The rest of the defended model's loss survives filtering, and it is not feature damage alone: with the filter's evidence and the victim's training features both clean, the attacker's edges still cost the defended model accuracy (App. P), so the residual combines structural damage with feature poisoning, and the two channels interact."

Revised text, Fig. 2 caption: "the gap between the curves is the conditional effect of corrupting the filter's evidence, and the rise of the dashed curve is the loss that survives filtering, which combines structural damage with feature poisoning that no edge filter was built to stop."

Revised text, Contributions: "The gap is the conditional effect of corrupting the evidence; what it does not explain is the loss that survives filtering, which combines structural damage with feature poisoning that no edge filter was designed to stop."

The remaining points are in the next comment.

AuthorsOpenReview ↗

Response 2

W1 and Q1, continued. Why the camouflage experiment is separate

The criticism above is about the joint condition, where the feature budget is 10% of the non-zero entries and the two channels genuinely mix. The camouflage experiment of Table 2 is a different setting, and it has a direct control that we should have placed in the main text. On Cora, with Metattack's stored graph and the 136 copied words:

  • the copies alone, with no structural attack, leave an undefended GCN at 80.60, against 80.14 on the clean graph;
  • structure together with the copies leaves the undefended GCN at 66.87, against 66.90 for structure alone;
  • GCN-Jaccard's loss rises from 7.63 to 15.67 points;
  • the filter prunes 572 edges, which is what it prunes on the clean graph.

Since the copies do not measurably change an undefended model, either alone or in combination with the structural attack, we think the 8.03 point rise in the defended loss can only be acting through the filter. The pattern is the same in all six camouflage cases: copies-only accuracy stays within 0.69 points of the clean GCN, the undefended loss moves by at most 0.67 points, and GCN-Jaccard loses an extra 8.03, 4.07 and 8.33 points on Cora and 1.13, 2.97 and 4.13 points on CiteSeer under Metattack, PRBCD and CLASP. Read off the grid, the training-feature channel in the camouflage rows lies between -0.73 and 0.60 points, which is the same statement.

What our text did not do, and what the reviewer is right to object to, is keep these two experiments apart. The revision reports the joint condition as a four-way decomposition with no causal attribution beyond the conditional effect, and lets the camouflage experiment carry the causal claim, with the control above moved into the main text.

W2 and Q2. Label access in the PRBCD and GRBCD calls

Review: "The structural comparisons appear to mix label-access assumptions. Section 3.1 exposes training labels, whereas supplementary a_rbcd calls pass data.y together with test-node indices to PRBCD/GRBCD ... This appears to provide true test labels, unlike CLASP's pseudo-label objective."

Response: The reviewer has read the code correctly. Both call sites are

a.attack(data.x.float(), to_ei(A0), data.y, budget=B,
         idx_attack=data.test_mask.nonzero().flatten())

so the attack receives the true labels of the attacked test nodes, while CLASP optimises a surrogate's pseudo-labels. We should have stated this rather than leaving it to be found in the code. The effect is to make the baselines stronger than the threat model of Sec. 3.1 allows, so the structural comparison was conservative with respect to CLASP, but it is not a matched comparison.

Revised text, Sec. 3.1: "One departure from this is worth stating plainly: PRBCD and GRBCD are run through their reference implementation, which scores the attacked nodes against their true labels, so those rows give the baselines oracle labels on the attacked set, while CLASP optimises a surrogate's pseudo-labels. Those rows are therefore oracle-label stress tests and are marked as such in App. Q."

This does not affect the results that take a stored poisoned graph as input and price the feature edit on it. Those are Table 2, the edge-level survival counts, the intervention grid and Props. 1 and 2, none of which depend on how the graph was produced. We are rerunning PRBCD and GRBCD with the information CLASP is given, which is true labels on the training split and the surrogate's argmax elsewhere, and will post the matched rows in this thread. We expect the attack to become weaker or to stay where it is.

A related point, since the reviewer raised matched information. CLASP's homophily switch is set from labels. A control in the supplementary material (pseudo_homophily.json) shows that homophily estimated from the surrogate's pseudo-labels on the unlabelled nodes selects the same rule as the true homophily on all six graphs, cross-class on Cora, CiteSeer and PubMed and same-class on chameleon, squirrel and actor. That access can be removed at no cost, and the revision says so.

The remaining points are in the next comment.

AuthorsOpenReview ↗

Response 3

Q3. What justifies the learned-evidence price

Review: "What justifies the learned-evidence 'price floor'? Appendix I is a useful adaptive control, but its edits are donor words, it uses five greedy rounds, and it does not optimize through encoder training. Failure to find cheaper severe blinding with this attack does not lower-bound the best adaptive attack."

Response: We accept this and have removed the word floor. App. I gives an upper bound on the price paid by the strongest adaptive attack we were able to construct, and we agree it does not lower-bound the best adaptive attack that exists. The limitations the reviewer identifies are the right ones. The appendix's own numbers suggest the attack is not at a limit: under Metattack, 140 of 263 inserted edges on Cora and 110 of 227 on CiteSeer bought nothing at all, and between 22 and 62 edges reached the five-word cap. The gap bought is 1.67 to 2.47 points for 0.22 to 0.85% of the non-zero entries.

The conclusion is now scoped to the attacks and implementations we tested: across every adaptive attack and every purifier cut we tried, the copies bought at most 2.47 points, and we make no claim about what a stronger adaptive attack could do. App. J supports that scoping rather than a bound, since sweeping the keep fraction from 0.90 to 0.50 leaves the gap between -1.00 and 2.17 points on all four graph and attack pairs. We agree that budget curves at matched damage targets are the right comparison and we are running them.

Q4. The conditions under which App. M's sum is exact

Review: "Under what independence conditions does Appendix M's sum of isolated cosine projection costs equal a graph-level exact minimum or floor? ... Please state the necessary conditions or present the sum as an independent-edge reference. Also distinguish L1 moved mass, sum-of-row-L2 normalization, and median relative edge price."

Response: The reviewer is right that we left the conditions implicit. The sum equals the graph-level minimum when no two rejected edges share a moving endpoint, and no moving endpoint is also the fixed endpoint of another rejected edge, so that moving one node cannot change another edge's target. We did measure how often this holds but reported it as a remark. Table 2 gives it.

Table 2: share of moves that can be priced in isolation, PubMed

cosine threshold0.010.050.10.2
PRBCD1.0000.9410.9220.908
CLASP0.9740.9170.8960.885

At the threshold where the forgery is cheapest the condition holds exactly, since all 140 moving nodes carry exactly one rejected edge. At the higher thresholds the revision presents the sum as an independent-edge reference and not as a graph-level minimum.

We have also separated the three quantities. Normalising by the sum of row L2 norms, 7680.26 on PubMed, the exact L2 cost of Prop. 2's minimiser is 0.0036% of the mass at a threshold of 0.01 and rises to 1.51% at 0.2. The feasible interpolation that App. M also reports moves 0.074% of the L1 mass at 0.01 and overpays the exact minimiser by a factor of 16.68, falling to 1.40 at 0.2. The median relative price of a single edge is 0.0038 at 0.01 and 0.1533 at 0.2. These are labelled separately in the revision.

The minor correction in App. S

Review: "in Appendix S, deleting a shared word at one endpoint reduces the intersection but leaves the union unchanged. The Proposition 1 conclusion still follows after correcting this case."

Response: Thank you, the case was stated wrongly and the correction is the reviewer's. Deleting a word both endpoints share removes it from the intersection but leaves it in the union, so the flip takes i to i-1 with U unchanged and the ratio falls.

Revised text, App. S: "it deletes a shared word, so i falls by one while U is unchanged, since the other endpoint still has the word, and the ratio falls".

Only copying a word the other endpoint has and deleting a word it lacks can help, so the argument and the bound are unaffected.

Reviewer_h1tcOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies how an attacker who can poison both structure and node features can “forge” the evidence used by similarity-based GNN defenses. It gives closed-form minimal costs for passing a Jaccard filter and a cosine filter and shows that about one copied word per inserted edge makes GCN-Jaccard keep all edges inserted by Metattack or PRBCD.

Critical strengths
  1. The clean-versus-poisoned evidence measurement is a useful idea that separates blinding from feature damage, which accuracy and pruning counts cannot.
  2. The minimal forgery cost is simple, exact, and makes the weakness of raw-feature filters very concrete.
Critical weaknesses
  1. The novelty is limited. That adaptive attacks break similarity defenses is known [1, 2], and Props. 1–2 are elementary.
  2. CLASP is weak: far below PRBCD on all heterophilous graphs (e.g., 0.75 vs 16.5 pp on actor), class conditioning does not help, it is the most memory-hungry attack, and it uses all labels to set h.
  3. The defense evaluation is limited. The purifier [3] and recent robust GNNs such as RUNG [4] are untested. 4.Scale is limited. There is no OGB [5], and dense or learned features are untested.
  4. The presentation is very dense.

[1] Mujkanovic et al., Are Defenses for GNNs Robust?, NeurIPS 2022. [2] Chen et al., Understanding and Improving Graph Injection Attack, ICLR 2022. [3] Lee & Park, Self-Supervised Adversarial Purification for GNNs, ICML 2025. [4] RUNG, NeurIPS 2024. [5] Hu et al., Open Graph Benchmark, NeurIPS 2020.

Questions for authors

See Weaknesses.

4 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for the review, and in particular for identifying the two contributions we most wanted a reader to take away: that the clean-versus-poisoned evidence measurement "separates blinding from feature damage, which accuracy and pruning counts cannot", and that the minimal forgery cost is "simple, exact, and makes the weakness of raw-feature filters very concrete". We accept several of the weaknesses and are addressing them. On novelty and on soundness we would ask the reviewer to reconsider, and we set out why below. We hope our revisions and responses merit reconsideration of a higher evaluation.

On the soundness score

We would be grateful for guidance here, because we cannot locate the concern. The five weaknesses listed are about novelty, the strength of CLASP, the coverage of defenses, scale, and presentation. None of them states that a reported number is wrong, that an experiment is incorrectly constructed, or that a conclusion does not follow from its evidence.

If there is a specific result the reviewer believes is unsound, we would like to address it directly while the discussion period is open. Every table in the paper is generated from stored result files, a second script checks each number quoted in the prose and captions against those files, and the stored graphs and results are in the supplementary material, so any individual claim can be rechecked. We would rather repair a real error than leave it standing.

W1. Novelty

Review: "The novelty is limited. That adaptive attacks break similarity defenses is known [1, 2], and Props. 1-2 are elementary."

Response: We agree that the qualitative fact is known, and Sec. 2 says so. What we claim is different in kind, and we do not believe either reference contains it.

Neither reference prices the forgery. Mujkanovic et al. show that defenses lose their apparent robustness under adapted attacks; they do not report what the adaptation costs per edge, in closed form. Chen et al. preserve homophily while injecting new nodes, which is a different threat model from editing the features of existing nodes.

Neither reference measures which edges survive. We count, for each defense, which of the attacker's inserted edges it keeps, and we rerun each defense on clean features while the victim still trains on the poisoned ones. The review's own strengths section identifies this as something accuracy and pruning counts cannot do.

The result is not that the defense fails but that it is worse than no defense. On Cora, 136 copied words, 0.28% of the non-zero entries, leave GCN-Jaccard losing 15.67 points where an undefended GCN loses 13.30. "Brittle under adaptive attack" and "actively harmful for the price of one word per edge" are different claims, and only the second tells a practitioner to switch the filter off.

That Props. 1 and 2 are elementary is the finding rather than a defect in it. The price of forging a Jaccard filter's evidence is one line of arithmetic, which is why the filter cannot be repaired by tuning its threshold.

W2. CLASP is weak

Review: "CLASP is weak: far below PRBCD on all heterophilous graphs (e.g., 0.75 vs 16.5 pp on actor), class conditioning does not help, it is the most memory-hungry attack, and it uses all labels to set h."

Response: All four are correct and all four are reported in the paper. We would stress that they do not reach the paper's claims. Every camouflage result uses Metattack's and PRBCD's stored graphs and no CLASP at all, so the central finding stands with CLASP removed entirely. CLASP is present because it reaches joint feature budgets the published structural attacks cannot, not as a proposed state-of-the-art attack. The reviewer is the second to read it the other way, so we accept that the framing is at fault and have moved this statement into the abstract. On the homophily switch, a supplementary control shows that pseudo-labels select the same rule as the true labels on all six graphs, so that access costs nothing to remove.

The remaining points are in the next comment.

AuthorsOpenReview ↗

Response 2

W3. The purifier and RUNG

Review: "The defense evaluation is limited. The purifier [3] and recent robust GNNs such as RUNG [4] are untested."

Response: The purifier is evaluated, in App. G, H, I and J. It is a STABLE-style design that learns its evidence before pruning, swept across keep fractions from 0.90 to 0.50, and attacked by an adversary given its architecture, seed and cut. It is the paper's resistant case. The caveat, which Reviewer M4j1 also raises and which we accept, is that our reimplementation omits the recovery step; we are adding it and will report the result in this thread. We will also add the Lee and Park citation, which we should have included.

On robust aggregation, we do evaluate a dimension-wise median GCN on all six graphs, which is the family RUNG belongs to. We report it here because we think it is consistent with the paper's framing rather than a gap in it.

Table 1: dimension-wise median GCN, accuracy drop in points

CoraCiteSeer
Metattack, no copies9.808.70
Metattack with the minimal copies10.937.67
joint 10% budget46.2348.70

Median aggregation reads no pairwise feature similarity, so the copies do not blind it: the camouflage moves its loss by 1.13 points on Cora and by -1.03 points on CiteSeer. It is also not robust to the joint attack, losing 46.23 points on Cora against a plain GCN's 41.06. This is what the paper would predict: defenses that do not use raw-feature similarity as evidence are not blinded in this way, and not being blinded is not the same as being robust. We will add RUNG to the discussion, and we will run it if we can get the implementation working in time rather than claiming it.

W4. Scale

Review: "Scale is limited. There is no OGB [5], and dense or learned features are untested."

Response: This is the one weakness we cannot answer with experiments that are already complete, and we accept it. An ogbn-arxiv evaluation is running on a GPU and we will report whatever finishes before Nov 18. It prices the forgery using Prop. 2's exact minimiser against cosine thresholds set at quantiles of the clean edge-similarity distribution, on PRBCD's inserted edges. That part of the result does not require the bilevel attack and therefore does not inherit CLASP's memory cost. We will also state CLASP's memory bound explicitly rather than describing it in words, as the reviewer asks. On dense features, App. M evaluates raw TF-IDF on PubMed, where the defended model falls to the undefended model's accuracy for 0.58% of the feature mass; ogbn-arxiv's 128 dimensional dense features are the nearest case to learned representations we can reach before the deadline.

W5. Presentation

Review: "The presentation is very dense."

Response: We accept this. Three reviewers scored presentation 1, 2 and 3, so we read it as a defect rather than a difference of taste. The revision adds a workflow figure to the main text, using the additional page the rebuttal period allows, moves two tables to the appendix, and rewrites the abstract and the results commentary in shorter sentences. If there are particular passages that defeated the reviewer, we would be glad to know which, and we will rewrite those first.

AuthorsOpenReview ↗

Response 3: Clarifying Our Contribution and New Experimental Evidence

Your concerns about novelty, scale, and the role of CLASP prompted us to reconsider how we present the main contribution of this work.

We agree that adaptive attacks against similarity-based defenses are not new. Our contribution is a different question: how much does it cost to forge the evidence a defense relies on, how many adversarial edges does that forgery preserve, and what happens to prediction accuracy as a result?

We have reorganized the manuscript around these three measurements. The exact forgery-pricing propositions and the 2×2 evidence intervention now appear together in the main methodological section. CLASP is presented as one way to study joint poisoning, rather than as an attack intended to outperform every existing baseline.

We have also completed a large-scale experiment on ogbn-arxiv (169,343 nodes, 128-dimensional features). On a fixed PRBCD-attacked graph, malicious-edge retention increased from 14.52% to 91.32% through feature projection. A subsequent warm-start repair achieved 100% retention of all 11,577 inserted edges, with 0.8079% normalized feature movement.

The earlier projection was also evaluated through paired victim training, showing a 1.93-percentage-point conditional evidence effect. We do not attribute that accuracy result to the subsequent 100% retention repair.

An additional corroboration experiment provides a useful contrast. Combining cosine similarity with structural evidence reduced forged-edge retention from 91.32% to 3.19% at matched clean-edge pruning, with a 2.10-point accuracy improvement. The topology-only control performed even stronger rejection, helping explain where that protection comes from.

These results do not establish large-scale CLASP optimization or full STABLE/RUNG robustness. What they establish is a quantitative way to study when defensive evidence can be manipulated, at what cost, and with what consequences.

We hope the revised manuscript makes this distinction and the broader contribution clearer. We appreciate the opportunity to address your concerns with additional evidence.

AuthorsOpenReview ↗

Scale & Novelty

Dear Reviewer,

We have incorporated additional ogbn-arxiv experiments, graph-wide forgery validation, and independent corroboration results into the revised manuscript. We would sincerely appreciate your feedback on whether these additions address your concerns regarding novelty, scalability, and evaluation scope.

Reviewer_M4j1OpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper investigates why similarity-based defenses retain maliciously inserted edges after an attacker modifies node features. The authors derive the cost of modifying a single edge to exceed the similarity threshold and use controlled experiments to distinguish between the effects of compromised defense evidence and feature contamination.

Critical strengths
  1. The research question is specific, expanding the focus from post-attack accuracy to whether malicious edges are retained, which facilitates understanding the causes of defense failure.
  2. A small number of feature replicas were added to attacks with fixed structures, and the defense criteria were calculated using clean features; the resulting comparisons are quite persuasive.
Critical weaknesses
  1. All experimental features are represented using the bag-of-words model, and experiments with continuous features are limited to TF-IDF on PubMed; the applicability of dense learning representations has not yet been verified.
  2. The STABLE style filter is a reimplementation that omits the recovery step; therefore, the relevant results primarily support this simplified design, and caution should be exercised when generalizing to the full defense method.
Questions for authors
  1. Will the effect of small-scale feature replication change after incorporating the recovery steps for the purifier?
  2. Can edge-level statistics for different attack seeds—in addition to those from Cora and CiteSeer—be provided to confirm the robustness of the conclusions?
5 comments
AuthorsOpenReview ↗

Response 1

We thank the reviewer for the careful reading of the mechanism experiments. We accept both weaknesses as stated, and we hope our revisions and responses merit reconsideration of a higher evaluation.

Q1. The purifier's recovery step

Review: "Will the effect of small-scale feature replication change after incorporating the recovery steps for the purifier?"

Response: Our purifier is a reimplementation that prunes by embedding similarity and omits STABLE's recovery step, as App. G notes, and the reviewer is right that the results therefore speak to the simplified design rather than to the full method. We are implementing the recovery step and will report the result in this thread during the discussion period.

Our expectation, which the measurement will test, is that the purifier remains the resistant case, because the recovery step reads embedding similarity, and App. I suggests this is the channel that is expensive to forge. In that appendix the attacker is given the purifier's architecture, seed and keep fraction. It buys the word that most raises the embedding cosine of its own inserted edges, and re-trains the encoder between rounds. It gains 1.67 to 2.47 points for 0.22 to 0.85% of the non-zero entries. A budget of that kind buys 100% edge survival against GCN-Jaccard. We may be wrong about the direction, and if the recovery step makes the purifier easier to blind we will report that, since the paper's claim concerns which evidence channel is cheap to forge and a result either way is informative.

Q2. Edge-level statistics for further attack seeds and graphs

Review: "Can edge-level statistics for different attack seeds, in addition to those from Cora and CiteSeer, be provided to confirm the robustness of the conclusions?"

Response: The replication exists for the two citation graphs and we are extending it to the other four. Table 1 gives what we have.

Table 1: attack-seed replication of the minimal copies, PRBCD, GCN-Jaccard

graphseedscopiessurvival beforesurvival afterpaired extra loss
Cora386 +- 967.05 +- 3.10%100.00%4.49 +- 1.11
CiteSeer254.5 +- 13.475.95 +- 5.86%100.00%3.32 +- 0.35

The paired extra loss on Cora ranges from 3.77 to 5.77 across the three seeds. The filter reaches 100% survival in every seed we have run, which is the part of the result that does not vary. We are now running the same protocol on chameleon, squirrel, actor and PubMed, and raising the two citation graphs to eight seeds, and will post the table here as the runs complete. The quantity we summarise is the paired difference within a seed, so each seed is self-contained and partial results are meaningful.

The remaining point is in the next comment.

AuthorsOpenReview ↗

Response 2

W1. Dense and learned representations

Review: "All experimental features are represented using the bag-of-words model, and experiments with continuous features are limited to TF-IDF on PubMed; the applicability of dense learning representations has not yet been verified."

Response: This limitation is real and we will state it more precisely. What we have is PubMed with raw TF-IDF features, left continuous, against a cosine filter, in App. M. At a threshold of 0.05, the fewest moves that lift PRBCD's inserted edges take survival from 49.8% to 100%, the defended model falls from 49.90 to 27.77 against an undefended 27.57, and the cost is 0.58% of the feature mass. On continuous features the defended model ends up where the undefended model is, so the mechanism does not appear to depend on binarisation. A control on the same moves shows that an MLP trained on the clean features changes 1.24% of its predictions, against 0.29% for a random move of the same mass.

What we do not have is dense learned representations used as input features, where the sparsity that the Jaccard forgery exploits is absent. We expect the Jaccard analysis not to transfer to that setting, and the cosine analysis of Prop. 2 to transfer at a different price, but we have not measured it. The revision names it as untested rather than implying coverage, and an ogbn-arxiv evaluation is running, whose 128 dimensional dense features are the nearest case we can reach before Nov 18.

AuthorsOpenReview ↗

Response 3: Additional Experiments and Large-Scale Validation

We have now completed the additional experiments we mentioned in our earlier responses, and the results have helped us strengthen the paper.

First, we extended our feature-forgery experiments across all six graphs, including PubMed, Actor, Chameleon, and Squirrel. Targeted feature copying achieved 100% inserted-edge retention across the evaluated attack draws, while matched-node random edits did not produce the same effect.

We also tested our DGI-based purifier with top-k neighborhood recovery. The results showed only small and inconsistent changes in edge retention and accuracy, suggesting that learned evidence is harder to manipulate under this particular attack. This remains a recovery ablation rather than an evaluation of the complete official STABLE implementation.

Our most significant addition is the ogbn-arxiv experiment, involving 169,343 nodes and 128-dimensional features. Feature projection initially increased malicious-edge retention from 14.52% to 91.32%. We then addressed shared-node conflicts with a warm-start repair, reaching 100% retention (11,577/11,577 edges) with just 0.8079% normalized feature movement.

In a separate paired evaluation, the earlier projection produced a 1.93-percentage-point conditional evidence effect across three victim-training seeds. We have kept this result separate from the final warm-start repair, for which accuracy has not yet been re-evaluated.

We believe these additions provide a much clearer picture of how the mechanism behaves across different graphs and feature representations. Thank you for encouraging us to examine these settings more carefully.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.